Дизъюнктивная нормальная форма (:n[aZutmnfugx ukjbgl,ugx skjbg)

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

Определение

Пусть задан алфавит переменных $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».

Минимизация ДНФ

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

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

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

В смысле определённого выше понятия упрощения тупиковые ДНФ по сути являются самыми простыми возможными эквивалентными ДНФ, однако тупиковых ДНФ, эквивалентных данной, может быть довольно много, причём они могут иметь совершенно разную длину или ранг. Это означает, что одна тупиковая ДНФ может быть интуитивно проще другой, но формализовать эту меру простоты в терминах элементарных упрощений уже не получится. Тут требуется иной подход. Один из таких подходов — индекс простоты. Индексом простоты называется отображение $L$ из множества ДНФ в множество натуральных чисел с нулём, удовлетворяющее следующим свойствам:

1. Для любой ДНФ $R$ выполнено $L(R)\geq 0$ (неотрицательность);
2. Пусть $R'$ получена из $R$ удалением литерала. Тогда $L(R)\geq L(R')$ (монотонность);
3. Пусть $R'$ получена из $R$ удалением элементарной конъюнкции. Тогда $L(R)\geq L(R')$ (выпуклость);
4. Пусть $R'$ получена из $R$ переименованием переменных. Тогда $L(R)\geq L(R')$ (инвариантность).

Простейшими примерами индексов простоты являются длина ДНФ и ранг ДНФ. ДНФ $R$ такая, что не существует эквивалентных ей ДНФ со значением $L$ меньше, чем $L(R)$, называется минимальной ДНФ относительно $L$. Минимальную ДНФ относительно длины называют также кратчайшей ДНФ, а минимальную ДНФ относительно ранга ― просто минимальной без уточнения индекса простоты. Нахождение минимальной ДНФ (относительно некоторого индекса) называется минимизацией ДНФ.

Минимальная ДНФ относительно некоторого индекса $L$ не обязательно является тупиковой. Однако операции элементарного упрощения никогда не увеличивают индекс простоты ДНФ. Поэтому из любой минимальной ДНФ относительно любого индекса $L$ можно получить минимальную ДНФ относительно этого же индекса также являющуюся тупиковой (просто применяя операции элементарного упрощения до того, пока это приводит к эквивалентной ДНФ). Так что если задачей является найти какую-нибудь минимальную ДНФ относительно индекса, а не все, то можно ограничиться рассмотрением только тупиковых: просто посчитать индекс простоты для всех тупиковых и выбрать ДНФ с наименьшим. Минимальная относительно $L$ ДНФ, являющаяся одновременно с этим и тупиковой, называется простой минимальной ДНФ относительно $L$. Для ранга все минимальные ДНФ являются простыми, а для длины существуют и не простые.

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

Для любой функции дизъюнкция всех её простых импликант является её ДНФ и называется сокращённой дизъюнктивной нормальной формой (сокДНФ). Сокращённая ДНФ имеет очень много важных свойств и при этом очень легко строится при помощи различных алгоритмов, таких как Метод Куайна — Мак-Класки. Все тупиковые ДНФ состоят только из простых импликант и поэтому могут быть получены упрощением сокращённой ДНФ. Из этого получается известный способ минимизации функции (а если точнее нахождения всех простых минимальных относительно индекса ДНФ):

• Строим сокДНФ функции по алгоритму;
• Получаем все тупиковые ДНФ при помощи упрощения сокДНФ по всем возможным путям;
• Для каждой из тупиковых ДНФ считаем индекс простоты и выбираем ДНФ с наименьшим.

Булева функция монотонна тогда и только тогда, когда её сокДНФ не содержит отрицаний.

См. также

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

Литература

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

• Яблонский С. В. Введение в дискретную математику. — 5-е изд. — М.: Высшая школа, 2008. — 384 с. — ISBN 978-5-06-005943-4.

Ссылки

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