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

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

Определение

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

Пусть задан алфавит переменных ${\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 с. - (Высшее образование).

Ссылки

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

Эта страница в последний раз была отредактирована 8 сентября 2023 в 18:49.