Что такое днф и кнф

«Учебник по дискретной математике ДНФ, СДНФ, КНФ, СКНФ»

Например, является простой конъюнкцией,

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций.

Например, выражение является ДНФ.

Например, выражение является ДНФ, но не СДНФ. Выражение является СДНФ.

Аналогичные определения (с заменой конъюнкции на дизъюнкцию и наоборот) верны для КНФ и СКНФ. Приведем точные формулировки.

Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных, при этом каждая переменная входит не более одного раза (либо сама, либо ее отрицание).Например, выражение – простая дизъюнкция,

Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций (например выражение – КНФ).

Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одинаковом порядке.

Например, выражение является СКНФ.

Приведем алгоритмы переходов от одной формы к другой. Естественно, что в конкретных случаях (при определенном творческом подходе) применение алгоритмов бывает более трудоемким, чем простые преобразования, использующие конкретный вид данной формы:

а) переход от ДНФ к КНФ

Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения (или правила Блейка). Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:

Заметим, что КНФ можно получить и из первоначального выражения, если вынести у за скобки;

б) переход от КНФ к ДНФ

Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения)

Таким образом, получили ДНФ.

Обратный переход (от СДНФ к ДНФ) связан с проблемой минимизации ДНФ. Подробнее об этом будет рассказано в разд. 5, здесь же мы покажем, как упростить ДНФ (или СДНФ) по правилу Блейка. Такая ДНФ называется сокращенной ДНФ;

в) сокращение ДНФ (или СДНФ) по правилу Блейка

Применение этого правила состоит из двух частей:

— если среди дизъюнктных слагаемых в ДНФ имеются слагаемые , то ко всей дизъюнкции добавляем слагаемое К₁К₂. Проделываем эту операцию несколько раз (можно последовательно, можно одновременно) для всех возможных пар слагаемых, а затем, применяем обычное поглощение;

— если добавляемое слагаемое уже содержалось в ДНФ, то его можно отбросить совсем, например,

Разумеется, сокращенная ДНФ не определяется единственным образом, но все они содержат одинаковое число букв (например, имеется ДНФ , после применения к ней правила Блейка можно прийти к ДНФ, равносильной данной):

в) переход от ДНФ к СДНФ

Если в какой-то простой конъюнкции недостает переменной, например, z, вставляем в нее выражение ,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:

г) переход от КНФ к СКНФ

Этот переход осуществляется способом, аналогичным предыдущему: если в простой дизъюнкции не хватает какой-то переменной (например, z, то добавляем в нее выражение (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона):

Таким образом, из КНФ получена СКНФ.

Заметим, что минимальную или сокращенную КНФ обычно получают из соответствующей ДНФ.

Источник

Дизъюнктивные и конъюнктивные нормальные формы ДНФ, КНФ

Лекция 2. Формы представления высказываний

План лекции:

Дизъюнктивные и конъюнктивные нормальные формы ДНФ, КНФ.

Совершенные нормальные формы СДНФ, СКНФ

Дизъюнктивные и конъюнктивные нормальные формы ДНФ, КНФ

Нормальная форма – это синтаксически однозначный способ записи формулы, реализующей данную функцию.

Любая n-членная операция, обозначаемая, например, , будет полностью определена, если установлено, при каких значениях высказываний результат будет истинным или ложным. Один из способов задания такой операции – заполнение таблицы значений:

1	1		1	1 или 0
0	0		0	1 или 0

В таблице значений высказывания, образованного от n простейших высказываний , имеется строк. Столбец значений имеет также позиций. Следовательно, имеется различных вариантов его заполнения, и, соответственно, число всех n-членных операций равно . При n=1 число одночленных операций равно 4, при n=2 число двучленных – 16, при n=3 количество трехчленных – 256 и т.д.

Рассмотрим некоторые специальные виды формул.

Формулу называют элементарной конъюнкцией, если она является конъюнкцией переменных и отрицаний переменных. Например, формулы , , , – элементарные конъюнкции.

Формулу, представляющую собой дизъюнкцию (возможно одночленную) элементарных конъюнкций, называют дизъюнктивной нормальной формой (д. н. ф.). Например, формулы , , .

Теорема 2.1.(о приведении к ДНФ). Для любой формулы U можно найти равносильную ей формулу V, являющуюся ДНФ.

Формулу называют элементарной дизъюнкцией, если она является дизъюнкцией переменных и отрицаний переменных. Например, формулы , , и т.д.

Пример.

Такая форма называется дизъюнктивной нормальной формой (ДНФ). Отдельный элемент ДНФ называется элементарной конъюнкцией или конституентой единицы.

Формулу, являющуюся конъюнкцией (возможно одночленной) элементарных дизъюнкций, называют конъюнктивной нормальной формой (КНФ). Например, формулы , .

Теорема 2.2.(о приведении к КНФ). Для любой формулы U можно найти равносильную ей формулу V, являющуюся КНФ.

Пример.

Отдельный элемент КНФ называется элементарной дизъюнкцией или конституентой нуля.

Алгоритм построения КНФ и ДНФ.

1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы (см. Лекцию 1).

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании закона де Моргана.

3) Избавиться от знаков двойного отрицания.

4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.

Примеры.

1. Приведем к КНФ формулу

Преобразуем формулу F к формуле, не содержащей импликацию:

В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

По закону дистрибутивности получим КНФ:

2. Приведем к ДНФ формулу:

.

Выразим логические операции импликации и стрелку Пирса через конъюнкцию, дизъюнкцию и инверсию:

В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

Используя закон дистрибутивности, приводим формулу к ДНФ:

Источник

Раскрыто понятие совершенная ДНФ и КНФ. Приведены примеры преобразований

Логические функции, СДНФ СКНФ

1.4 Формы представления функций алгебры логики

Функции алгебры логики могут быть заданы различными способами:

Если функция имеет значения на всех наборах, то она называется полностью определенной.

– это не минтерм, так как перем и зависимы.

Для аналитической записи функций используют две формы:

2) Конъюнктивную Нормальную Форму – КНФ

ДНФ это дизъюнкция минтермов разл ранга

КНФ это конъюнкция макстермов различного ранга

— это СДНФ

— это СКНФ

Составление совершенных форм по табл истинности

СКНФ =для каждого набора переменных, на которых функция=0, записывают макстерм ранга n, в кот с отрицанием берутся переменные, имеющие значение=1 на данном наборе. Все макстермы объединены конъюнктивно

Для компактной записи функций исп числовую форму, в которой заданы только номера наборов. Числовая форма для СДНФ:

Числовая форма для СКНФ:

Алгоритм преобразованияя в ДНФ

1) Сначала избавляемся от операций импликации, эквивалентности и неравнозначности, выразив их через логические связки ¬, & и ∨ по законам:

2) Доводят знаки отрицания до независимых переменных, используя законы де Моргана:

3) Применяя з-н дистрибутивности

преобразуют формулу к дизъюнкции элементарных конъюнкций

4) 4) Постоянно избавляются от двойных отрицаний:
ДНФ A наз совершенной и обозн СДНФ, если каждая переменная формулы A входит с отрицанием или без отрицания в каждый конъюнкт точно 1 раз.

Алгебраическая форма представления булевых функций используется для минимизации (упрощения формулл) и для построения логических схем. Существукт 2 формы алгебраических функций – дизъюнктивная и конъюнктивн. Дизъюнктивная нормальная форма представляет сумму элементарных произведения аргументов, например

Если кажд слаг содер все арг или их отриц, то получ соверш дизъюнкт норм форму (СДФН), напр

Для перехода от табл истинн к СДНФ учит только те сост, для кот функц= 1. Для каждого такого сост запис элем произв всех ар. Если арг имеет зн «0», то запис его отриц. Для привед примера СДНФ имеет вид (17.4)

Совершенная конъюнктивная нормальная форма (СКНФ) представляет логическое произведение элементарных логических сумм, причем каждая сумма содержит все аргументы или их отрицания, например

ДНФ, но не СДНФ от 3 перем

-представл импликации в виде ДНФ.

-СДНФ для импликации

-СДНФ для оп эквивалентности

-СДНФ для оп неравнозначности

Прим.1 Привести к ДНФ формулу

2. Привести ту же формулу к СДНФ. Начав преобразования с ДНФ

Нахождение СДНФ по табл истинности функции

Нахождение СКНФ по табл истинности функции

1)Отметить те строки таблицы истинности, в последнем столбце которых стоят 1.

3)Все полученные конъюнкции связать в дизъюнкцию.

1)Отметить те строки таблицы истинности, в последнем столбце которых стоят 0.

2)Выписать для каждой отмеченной строки дизъюнкцию всех переменных так: если значение некоторой переменной в данной строке= 1, то в дизъюнкцию включать саму эту переменную, если равно 0, то ее отрицание.

3)Все полученные дизъюнкции связать в конъюнкцию.

Источник

Эквивалентность формул и нормальные формы

Дизъюнктивные и конъюнктивные нормальные формы

Определение ДНФ и КНФ

В этом разделе мы интересуемся представлением произвольной булевой функции посредством формул специального вида, использующих только операции и

Пусть — это множество пропозициональных переменных. Введем для каждого i=1. n обозначения: и . Формула , в которой и все переменные разные, т.е. при , называется элементарной конъюнкцией ( элементарной дизъюнкцией ).

Совершенные ДНФ и КНФ

Определим по этим множествам две формулы:

Доказательство получается непосредственным вычислением значения каждой из указанных формул с учетом того, что для любого имеют место равенства: и (см. задачу 4.4).

Следствие 4.1.1. Каждая булева функция может быть задана формулой, содержащей переменные и функции конъюнкции, дизъюнкции и отрицания.

Процедура Приведение к совершенной ДНФ

Поскольку каждая из формул , имеет меньшую глубину, чем формула , то предположим по индукции, что для них уже построены эквивалентные ДНФ и , соответственно.

Тогда в случае (а) имеем:

Из формулировок эквивалентностей (7) и (8) непосредственно вытекает

Доказательство этого предложения оставляем в виде упражнения (см. задачу 4.7).

Следующее утверждение гарантирует корректность этапа (2).

Предложение 4.2. На этапе (2) процедуры при любом порядке выполнения преобразований групп (4) и (5) до тех пор, пока ни одно из них не применимо, в полученной в результате формуле все знаки отрицания будут стоять непосредственно перед переменными.

Перед доказательством этого утверждения введем некоторые обозначения. Напомним, что в определениях 3.2 и 3.3 для каждой формулы была определена ее глубина . Например, формула , построенная над системой , имеет глубину .

Доказательство предложения 4.2 проведем индукцией по высоте формул.

Базис индукции. Если , то либо в нет отрицаний, либо все отрицания находятся непосредственно перед переменными. Следовательно, удовлетворяет требованию предложения 4.2.

Рассмотрим применение процедуры приведения к совершенной ДНФ на примере.

Пример 4.1. Пусть формула .

На (1)-ом этапе процедуры получаем следующую цепочку эквивалентностей:

На (2)-ом этапе вносим отрицание внутрь первой скобки и получаем формулу

Устранив двойное отрицание, получим

Эта ДНФ не является совершенной, так как в каждую из ее трех конъюнкций входят не все переменные. Построим на этапе (5) для них эквивалентные совершенные ДНФ (используя решение задачи 4.5).

Мы видим, что ДНФ , полученная после 4-го этапа, выглядит существенно проще, т.е. является более короткой, чем совершенная ДНФ . Однако совершенные ДНФ и КНФ обладают важным свойством единственности, которое следует из их конструкции в теореме 4.1.

Это следствие позволяет предложить следующую процедуру для проверки эквивалентности формул и

Источник