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

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

Определение

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

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

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

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

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

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

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

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

• $0$ — единственная ДНФ длины 0, её ранг равен 0;
• любая элементарная конъюнкция есть ДНФ длины 1, её ранг равен её рангу как элементарной конъюнкции;
• $x_{1}\lor x_{2}$ — ДНФ длины 2 и ранга 2. Выражение $x_{2}\lor x_{1}$ задаёт ту же самую ДНФ;
• $(x_{1}\land x_{2})\lor {\overline {x_{2}}}$ — ДНФ длины 2 и ранга 3.
• $(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.

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

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

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

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

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

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

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

$A\rightarrow B=\neg A\vee B$

$A\leftrightarrow B=(A\wedge B)\vee (\neg A\wedge \neg B)$

$A\oplus B=(\neg A\land B)\lor (A\land \neg B)$

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

$\neg (A\vee B)=\neg A\wedge \neg B$

$\neg (A\wedge B)=\neg A\vee \neg B$

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

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

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

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

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

$F=\neg ((\neg X\vee Y)\vee \neg (\neg Y\vee Z))$

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

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

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

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

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

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

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

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

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

$(A\land B)\lor (\neg B\land C)\lor (B\land \neg C)$

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

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

$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}}$,

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

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

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

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

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

$Z\vee \neg Z=1$,

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

$X\vee \neg Y\neg Z=X(Y\vee \neg Y)(Z\vee \neg Z)\vee (X\vee \neg X)\neg Y\neg Z=$

$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=$

$=XYZ\vee X\neg YZ\vee XY\neg Z\vee X\neg Y\neg Z\vee \neg X\neg Y\neg Z$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

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

Литература

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

Ссылки

• ДНФ, СДНФ, КНФ, СКНФ
• Disjunctive Normal Form
• Дизъюнктивная и Конъюнктивная нормальные формы
• Определение ДНФ и КНФ