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

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

Определение

Пусть задан алфавит переменных $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}\lor {\overline {x_{1}}}$, $x_{2}\lor {\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 \ldots \vee B)=\neg A\wedge \ldots \wedge \neg B$

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

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

$\neg \neg A=A$

4) Раскрыть скобки по дистрибутивности дистрибутивности:

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

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

5). Избавиться от одинаковых литералов:

$A\land A=A\lor A=A$

$A\land \neg A=0$

$A\lor \neg A=1$

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

Приведем к ДНФ формулу $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».

Сокращённая ДНФ

Элементарная конъюнкция $K$ называется простой импликантой функции $f$, если:

1. $K$ — импликанта $f$;
2. не существует такой элементарной конъюнкции $K'$, что $K'\neq K$, $K'$ поглощает $K$ и $K'$ — импликанта $f$.

Дизъюнкция всех простых импликант функции $f$ равна самой функции $f$ и называется сокращённой дизъюнктивной нормальной формой.

Тупиковая ДНФ

Для ДНФ можно определить две элементарные операции упрощения:

1. вычёркивание из одной из элементарных конъюнкций литерала;
2. вычёркивание элементарной конъюнкции.

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

См. также

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

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

Литература

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

Ссылки

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