Дизъюнкти́вная норма́льная фо́рма
(
ДНФ
) в
булевой логике
—
нормальная форма
, в которой
булева формула
имеет вид
дизъюнкции
конъюнкций
литералов
. Любая
булева формула
может быть приведена к ДНФ.
Для этого можно использовать
закон двойного отрицания
,
закон де Моргана
,
закон дистрибутивности
. Дизъюнктивная нормальная форма удобна для
автоматического доказательства теорем
.
Определение
Элементарные конъюнкции
Пусть задан алфавит переменных
. Выражение, представляющее собой конечную конъюнкцию переменных
и их отрицаний, в которую каждая из переменных входит не более одного раза, называется
элементарной конъюнкцией
над алфавитом переменных
. Случай когда в элементарную конъюнкцию входит ноль переменных тоже допускается: в этом случае выражение записывается как
. Количество операндов в элементарной конъюнкции называется её
рангом
. Две элементарные конъюнкции, отличающиеся лишь порядком операндов, считаются одинаковыми. Примеры элементарных конъюнкций над алфавитом
:
-
— единственная элементарная конъюнкция ранга 0;
-
— все элементарные конъюнкции ранга 1;
-
— элементарные конъюнкции ранга 2. Операнды можно менять местами, получится та же самая элементарная конъюнкция:
и
— одна и та же элементарная конъюнкция;
-
— элементарная конъюнкция ранга 3. Выражения
,
определяют ту же самую элементарную конъюнкцию.
Выражения
,
элементарными конъюнкциями не являются, так как каждая переменная должна входить в элементарную конъюнкцию всего один раз; выражения
,
,
также не являются элементарными конъюнкциями, так как в элементарных конъюнкциях в качестве операндов допускаются лишь выражения вида
и
(с одним особым случаем: элементарной конъюнкции ранга 0, она имеет вид
).
Таким образом, для каждой переменной есть ровно 3 возможности для заданной элементарной конъюнкции: переменная либо не входит в неё, либо входит как есть, либо входит с отрицанием. Задание для каждой переменной одной из этих трёх возможностей полностью определяет конкретную элементарную конъюнкцию. Таким образом, над любым конечным множеством переменных
количество элементарных конъюнкций равно
.
Две различные элементарные конъюнкции задают различные булевы функции; благодаря этому можно отождествлять элементарные конъюнкции с задаваемыми ими функциями. Не любая булева функция может быть задана в виде элементарной конъюнкции, простейший пример — тождественный
.
Определение ДНФ
Пусть задан алфавит переменных
. Выражение, представляющее собой конечную дизъюнкцию элементарных конъюнкций над
, в которую каждая из элементарных конъюнкций входит не более одного раза, называется
дизъюнктивной нормальной формой
(сокращённо ДНФ) над алфавитом переменных
. Случай когда в ДНФ входит ноль элементарных конъюнкций тоже допускается: в этом случае выражение записывается как
. Количество элементарных конъюнкций в ДНФ называется её
длиной
, а сумма рангов всех входящих в неё элементарных конъюнкций —
рангом
. Две ДНФ, отличающиеся лишь порядком операндов, считаются одинаковыми. Примеры ДНФ над алфавитом
:
-
— единственная ДНФ длины 0, её ранг равен 0;
-
любая элементарная конъюнкция есть ДНФ длины 1, её ранг равен её рангу как элементарной конъюнкции;
-
— ДНФ длины 2 и ранга 2. Выражение
задаёт ту же самую ДНФ;
-
— ДНФ длины 2 и ранга 3.
-
— ДНФ длины 4 и ранга 9.
Выражения
,
ДНФ не являются, так как в ДНФ элементарные конъюнкции не повторяются. Выражения
,
,
ДНФ не являются, так как в ДНФ в качестве операндов дизъюнкций допускаются лишь элементарные конъюнкции (с одним особым случаем: ДНФ длины 0, она имеет вид
).
Для каждой элементарной конъюнкции есть ровно 2 возможности для заданной ДНФ: она либо входит в неё, либо не входит. Задание для каждой элементарной конъюнкции одной из этих двух возможностей полностью определяет конкретную ДНФ. Так как над любым конечным множеством переменных
количество элементарных конъюнкций равно
, то количество ДНФ над ним будет равно
.
Разные ДНФ могут задавать одну и ту же функцию. Простейший пример: тождественная единица. Для неё можно построить две разные ДНФ:
,
. Даже более того, выражения
,
— это тоже ДНФ, задающие тождественный
. Поэтому ДНФ нельзя отождествлять с задаваемыми ими функциями. Две ДНФ, задающие одну и ту же функцию, называются
эквивалентными
. Стоит понимать разницу между равными ДНФ и эквивалентными. Например, выражения
и
— это одна и та же ДНФ. Выражения же
и
— это разные ДНФ, задающие одну и ту же функцию.
Любая булева функция может быть выражена в виде ДНФ. Например, приведённая выше функция
может быть задана ДНФ
, функция
— задана ДНФ
, а функция
— задана ДНФ
. Как уже было сказано выше, одна и та же функция может иметь несколько ДНФ, однако существует некоторые особые виды ДНФ, которые существуют и единственны для каждой булевой функции: такие как совершенная ДНФ и сокращённая ДНФ.
Построение ДНФ
Алгоритм построения ДНФ
1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:
-
-
-
2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:
-
-
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства
дистрибутивности
и формулы поглощения.
Пример построения ДНФ
Приведем к ДНФ формулу
Выразим логическую операцию → через
-
В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:
-
Используя закон
дистрибутивности
, получаем:
-
Используя
идемпотентность
конъюкции, получаем ДНФ:
-
k
-дизъюнктивная нормальная форма
k
-дизъюнктивной нормальной формой называют дизъюнктивную нормальную форму, в которой каждая конъюнкция содержит ровно
k
литералов
.
Например, следующая формула записана в 2-ДНФ:
-
Совершенная ДНФ
Совершенной ДНФ
над конечным алфавитом переменных
называется ДНФ, в каждую элементарную конъюнкцию которой входят все переменные. Совершенные ДНФ сокращённо называются СДНФ или совДНФ (второе используется для того, чтобы подчеркнуть отличие от сокращённой ДНФ). Особенность СДНФ состоит в том, что она существует и единственна для любой булевой функции от
переменных и очень просто строится по таблице истинности функции. Для СДНФ функции существует конкретная формула:
-
,
где
Таким образом, для построения СДНФ по таблице истинности достаточно пройтись по всем наборам
, на которых функция равна
, и добавить элементарную конъюнкцию вида
.
СДНФ обладает особым свойством: на любом наборе значений не более одной элементарной конъюнкции обращается в 1.
Переход от ДНФ к СДНФ
Существует и способ построения СДНФ по не совершенной ДНФ при помощи преобразований выражения. Если в какой-то простой конъюнкции недостаёт переменной, например, Z, вставляем в неё выражение
-
,
после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем, так как
по закону
идемпотентности
). Например:
-
-
-
Таким образом, из ДНФ получили
СДНФ
.
Формальная грамматика, описывающая ДНФ
Следующая
формальная грамматика
описывает все формулы, приведенные к ДНФ:
-
<ДНФ> → <конъюнкт>
-
<ДНФ> → <ДНФ> ∨ <конъюнкт>
-
<конъюнкт> → <литерал>
-
<конъюнкт> → (<конъюнкт> ∧ <литерал>)
-
<литерал> → <терм>
-
<литерал> → ¬<терм>
где <терм> обозначает произвольную булеву переменную.
Особенности обозначений
Следует отметить, что для удобства восприятия в качестве обозначения конъюнкции и дизъюнкции часто используют символы арифметического умножения и сложения, при этом символ умножения часто опускается. В этом случае формулы булевой алгебры выглядят как алгебраические полиномы, что более привычно для глаза, однако иногда может привести к недоразумениям.
Например, следующие записи эквивалентны:
-
-
-
-
По этой причине ДНФ в русскоязычной литературе иногда называют «суммой произведений», что является калькой с английского термина «sum of products».
См. также
Примечания
-
Поздняков С.Н., Рыбин С.В.
Дискретная математика. — С. 303.
Литература
-
Ю.И. Галушкина, А.Н. Марьямов: Конспект лекций по дискретной математике - 2-е изд., испр. - М.: Айрис-пресс, 2008. - 176 с. - (Высшее образование).
Ссылки