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

Определение

Элементарные конъюнкции

Пусть задан алфавит переменных ${\displaystyle X=\{x_{i}\}_{i\in I}}$ . Выражение, представляющее собой конечную конъюнкцию переменных ${\displaystyle x_{i}\in X}$ и их отрицаний, в которую каждая из переменных входит не более одного раза, называется элементарной конъюнкцией над алфавитом переменных ${\displaystyle X}$ . Случай когда в элементарную конъюнкцию входит ноль переменных тоже допускается: в этом случае выражение записывается как ${\displaystyle 1}$ . Количество операндов в элементарной конъюнкции называется её рангом . Две элементарные конъюнкции, отличающиеся лишь порядком операндов, считаются одинаковыми. Примеры элементарных конъюнкций над алфавитом ${\displaystyle X=\{x_{1},\ldots ,x_{n}\}}$ :

• ${\displaystyle 1}$ — единственная элементарная конъюнкция ранга 0;
• ${\displaystyle x_{1},\ldots ,x_{n},{\overline {x_{1}}},\ldots ,{\overline {x_{2}}}}$ — все элементарные конъюнкции ранга 1;
• ${\displaystyle x_{1}\land x_{2},x_{1}\land x_{3},{\overline {x_{1}}}\land x_{2},{\overline {x_{1}}}\land {\overline {x_{2}}}}$ — элементарные конъюнкции ранга 2. Операнды можно менять местами, получится та же самая элементарная конъюнкция: ${\displaystyle x_{1}\land x_{2}}$ и ${\displaystyle x_{2}\land x_{1}}$ — одна и та же элементарная конъюнкция;
• ${\displaystyle x_{1}\land {\overline {x_{2}}}\land x_{3}}$ — элементарная конъюнкция ранга 3. Выражения ${\displaystyle {\overline {x_{2}}}\land x_{1}\land x_{3}}$ , ${\displaystyle x_{1}\land x_{3}\land {\overline {x_{2}}}}$ определяют ту же самую элементарную конъюнкцию.

Выражения ${\displaystyle x_{1}\land x_{1}}$ , ${\displaystyle {\overline {x_{1}}}\land x_{1}}$ элементарными конъюнкциями не являются, так как каждая переменная должна входить в элементарную конъюнкцию всего один раз; выражения ${\displaystyle x_{1}\land 0}$ , ${\displaystyle x_{1}\land 1}$ , ${\displaystyle 0}$ также не являются элементарными конъюнкциями, так как в элементарных конъюнкциях в качестве операндов допускаются лишь выражения вида ${\displaystyle x_{i}}$ и ${\displaystyle {\overline {x_{i}}}}$ (с одним особым случаем: элементарной конъюнкции ранга 0, она имеет вид ${\displaystyle 1}$ ).

Таким образом, для каждой переменной есть ровно 3 возможности для заданной элементарной конъюнкции: переменная либо не входит в неё, либо входит как есть, либо входит с отрицанием. Задание для каждой переменной одной из этих трёх возможностей полностью определяет конкретную элементарную конъюнкцию. Таким образом, над любым конечным множеством переменных ${\displaystyle X,|X|=n}$ количество элементарных конъюнкций равно ${\displaystyle 3^{n}}$ .

Две различные элементарные конъюнкции задают различные булевы функции; благодаря этому можно отождествлять элементарные конъюнкции с задаваемыми ими функциями. Не любая булева функция может быть задана в виде элементарной конъюнкции, простейший пример — тождественный ${\displaystyle 0}$ .

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

Пусть задан алфавит переменных ${\displaystyle X=\{x_{i}\}_{i\in I}}$ . Выражение, представляющее собой конечную дизъюнкцию элементарных конъюнкций над ${\displaystyle X}$ , в которую каждая из элементарных конъюнкций входит не более одного раза, называется дизъюнктивной нормальной формой (сокращённо ДНФ) над алфавитом переменных ${\displaystyle X}$ . Случай когда в ДНФ входит ноль элементарных конъюнкций тоже допускается: в этом случае выражение записывается как ${\displaystyle 0}$ . Количество элементарных конъюнкций в ДНФ называется её длиной , а сумма рангов всех входящих в неё элементарных конъюнкций — рангом . Две ДНФ, отличающиеся лишь порядком операндов, считаются одинаковыми. Примеры ДНФ над алфавитом ${\displaystyle X=\{x_{1},\ldots ,x_{n}\}}$ :

• ${\displaystyle 0}$ — единственная ДНФ длины 0, её ранг равен 0;
• любая элементарная конъюнкция есть ДНФ длины 1, её ранг равен её рангу как элементарной конъюнкции;
• ${\displaystyle x_{1}\lor x_{2}}$ — ДНФ длины 2 и ранга 2. Выражение ${\displaystyle x_{2}\lor x_{1}}$ задаёт ту же самую ДНФ;
• ${\displaystyle (x_{1}\land x_{2})\lor {\overline {x_{2}}}}$ — ДНФ длины 2 и ранга 3.
• ${\displaystyle (x_{1}\land x_{2}\land {\overline {x_{3}}})\lor ({\overline {x_{4}}}\land x_{5}\land x_{6})\lor (x_{3}\land x_{4})\lor x_{2}}$ — ДНФ длины 4 и ранга 9.

Выражения ${\displaystyle x_{1}\lor x_{1}}$ , ${\displaystyle (x_{1}\land {\overline {x_{2}}})\lor x_{3}\lor (x_{1}\land {\overline {x_{2}}})}$ ДНФ не являются, так как в ДНФ элементарные конъюнкции не повторяются. Выражения ${\displaystyle {\overline {(x_{1}\lor x_{2})}}}$ , ${\displaystyle x_{1}\lor (x_{2}\land (x_{3}\lor x_{4}))}$ , ${\displaystyle x_{1}\lor x_{2}\lor 0}$ ДНФ не являются, так как в ДНФ в качестве операндов дизъюнкций допускаются лишь элементарные конъюнкции (с одним особым случаем: ДНФ длины 0, она имеет вид ${\displaystyle 0}$ ).

Для каждой элементарной конъюнкции есть ровно 2 возможности для заданной ДНФ: она либо входит в неё, либо не входит. Задание для каждой элементарной конъюнкции одной из этих двух возможностей полностью определяет конкретную ДНФ. Так как над любым конечным множеством переменных ${\displaystyle X,|X|=n}$ количество элементарных конъюнкций равно ${\displaystyle 3^{n}}$ , то количество ДНФ над ним будет равно ${\displaystyle 2^{3^{n}}}$ .

Разные ДНФ могут задавать одну и ту же функцию. Простейший пример: тождественная единица. Для неё можно построить две разные ДНФ: ${\displaystyle x_{1}\land {\overline {x_{1}}}}$ , ${\displaystyle x_{2}\land {\overline {x_{2}}}}$ . Даже более того, выражения ${\displaystyle 1}$ , ${\displaystyle x_{1}\lor 1}$ — это тоже ДНФ, задающие тождественный ${\displaystyle 1}$ . Поэтому ДНФ нельзя отождествлять с задаваемыми ими функциями. Две ДНФ, задающие одну и ту же функцию, называются эквивалентными . Стоит понимать разницу между равными ДНФ и эквивалентными. Например, выражения ${\displaystyle x_{1}\lor {\overline {x_{1}}}}$ и ${\displaystyle {\overline {x_{1}}}\lor x_{1}}$ — это одна и та же ДНФ. Выражения же ${\displaystyle x_{1}\lor {\overline {x_{1}}}}$ и ${\displaystyle x_{2}\lor {\overline {x_{2}}}}$ — это разные ДНФ, задающие одну и ту же функцию.

Любая булева функция может быть выражена в виде ДНФ. Например, приведённая выше функция ${\displaystyle {\overline {(x_{1}\lor x_{2})}}}$ может быть задана ДНФ ${\displaystyle {\overline {x_{1}}}\land {\overline {x_{2}}}}$ , функция ${\displaystyle x_{1}\lor (x_{2}\land (x_{3}\lor x_{4}))}$ — задана ДНФ ${\displaystyle x_{1}\lor (x_{2}\land x_{3})\lor (x_{2}\land x_{4})}$ , а функция ${\displaystyle x_{1}\lor x_{2}\lor 0}$ — задана ДНФ ${\displaystyle x_{1}\lor x_{2}}$ . Как уже было сказано выше, одна и та же функция может иметь несколько ДНФ, однако существует некоторые особые виды ДНФ, которые существуют и единственны для каждой булевой функции: такие как совершенная ДНФ и сокращённая ДНФ.

Построение ДНФ

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

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

${\displaystyle A\rightarrow B=\neg A\vee B}$

${\displaystyle A\leftrightarrow B=(A\wedge B)\vee (\neg A\wedge \neg B)}$

${\displaystyle A\oplus B=(\neg A\land B)\lor (A\land \neg B)}$

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

${\displaystyle \neg (A\vee B)=\neg A\wedge \neg B}$

${\displaystyle \neg (A\wedge B)=\neg A\vee \neg B}$

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

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

Пример построения ДНФ

Приведем к ДНФ формулу ${\displaystyle F=\neg ((X\rightarrow Y)\vee \neg (Y\rightarrow Z))}$

Выразим логическую операцию → через ${\displaystyle \vee \wedge \neg }$

${\displaystyle F=\neg ((\neg X\vee Y)\vee \neg (\neg Y\vee Z))}$

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

${\displaystyle F=(\neg \neg X\wedge \neg Y)\wedge (\neg Y\vee Z)=(X\wedge \neg Y)\wedge (\neg Y\vee Z)}$

Используя закон дистрибутивности , получаем:

${\displaystyle F=(X\wedge \neg Y\wedge \neg Y)\vee (X\wedge \neg Y\wedge Z)}$

Используя идемпотентность конъюкции, получаем ДНФ:

${\displaystyle F=(X\wedge \neg Y)\vee (X\wedge \neg Y\wedge Z)}$

k -дизъюнктивная нормальная форма

k -дизъюнктивной нормальной формой называют дизъюнктивную нормальную форму, в которой каждая конъюнкция содержит ровно k литералов .

Например, следующая формула записана в 2-ДНФ:

${\displaystyle (A\land B)\lor (\neg B\land C)\lor (B\land \neg C)}$

Совершенная ДНФ

Совершенной ДНФ над конечным алфавитом переменных ${\displaystyle X,|X|=n}$ называется ДНФ, в каждую элементарную конъюнкцию которой входят все переменные. Совершенные ДНФ сокращённо называются СДНФ или совДНФ (второе используется для того, чтобы подчеркнуть отличие от сокращённой ДНФ). Особенность СДНФ состоит в том, что она существует и единственна для любой булевой функции от ${\displaystyle n}$ переменных и очень просто строится по таблице истинности функции. Для СДНФ функции существует конкретная формула:

${\displaystyle f(x_{1},\ldots ,x_{n})=\bigvee \limits _{f(\sigma _{1},\ldots ,\sigma _{n})=1}x_{1}^{\sigma _{1}}\land \ldots \land x_{n}^{\sigma _{n}}}$ ,

где ${\displaystyle x^{\sigma }={\begin{cases}x,&\sigma =1;\\{\overline {x}},&\sigma =0.\end{cases}}}$

Таким образом, для построения СДНФ по таблице истинности достаточно пройтись по всем наборам ${\displaystyle \sigma _{1},\ldots ,\sigma _{n}}$ , на которых функция равна ${\displaystyle 1}$ , и добавить элементарную конъюнкцию вида ${\displaystyle x_{1}^{\sigma _{1}}\land \ldots \land x_{n}^{\sigma _{n}}}$ .

СДНФ обладает особым свойством: на любом наборе значений не более одной элементарной конъюнкции обращается в 1.

Переход от ДНФ к СДНФ

Существует и способ построения СДНФ по не совершенной ДНФ при помощи преобразований выражения. Если в какой-то простой конъюнкции недостаёт переменной, например, Z, вставляем в неё выражение

${\displaystyle Z\vee \neg Z=1}$ ,

после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем, так как ${\displaystyle Z\vee Z=Z}$ по закону идемпотентности ). Например:

${\displaystyle X\vee \neg Y\neg Z=X(Y\vee \neg Y)(Z\vee \neg Z)\vee (X\vee \neg X)\neg Y\neg Z=}$

${\displaystyle XYZ\vee X\neg YZ\vee XY\neg Z\vee X\neg Y\neg Z\vee X\neg Y\neg Z\vee \neg X\neg Y\neg Z=}$

${\displaystyle =XYZ\vee X\neg YZ\vee XY\neg Z\vee X\neg Y\neg Z\vee \neg X\neg Y\neg Z}$

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

Формальная грамматика, описывающая ДНФ

Следующая формальная грамматика описывает все формулы, приведенные к ДНФ:

<ДНФ> → <конъюнкт>

<ДНФ> → <ДНФ> ∨ <конъюнкт>

<конъюнкт> → <литерал>

<конъюнкт> → (<конъюнкт> ∧ <литерал>)

<литерал> → <терм>

<литерал> → ¬<терм>

где <терм> обозначает произвольную булеву переменную.

Особенности обозначений

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

Например, следующие записи эквивалентны:

${\displaystyle (A\land B\land {\overline {C}})\lor ({\overline {D}}\land E\land F)\lor (C\land D)\lor B;}$

${\displaystyle (A\cdot B\cdot {\overline {C}})\lor ({\overline {D}}\cdot E\cdot F)\lor (C\cdot D)\lor B;}$

${\displaystyle AB{\overline {C}}\lor {\overline {D}}EF\lor CD\lor B;}$

${\displaystyle AB{\overline {C}}+{\overline {D}}EF+CD+B.}$

По этой причине ДНФ в русскоязычной литературе иногда называют «суммой произведений», что является калькой с английского термина «sum of products».

См. также

• Конъюнктивная нормальная форма
• Совершенная дизъюнктивная нормальная форма
• Совершенная конъюнктивная нормальная форма

• Конъюнктивный одночлен
• Дизъюнктивный одночлен

Примечания

Литература

• Ю.И. Галушкина, А.Н. Марьямов: Конспект лекций по дискретной математике - 2-е изд., испр. - М.: Айрис-пресс, 2008. - 176 с. - (Высшее образование).

Ссылки