Русская Википедия:Дизъюнктивная нормальная форма

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Определение

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

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

• <math>1</math> — единственная элементарная конъюнкция ранга 0;
• <math>x_1,\ldots,x_n,\overline{x_1},\ldots,\overline{x_2}</math> — все элементарные конъюнкции ранга 1;
• <math>x_1\land x_2, x_1\land x_3, \overline{x_1} \land x_2, \overline{x_1} \land \overline{x_2}</math> — элементарные конъюнкции ранга 2. Операнды можно менять местами, получится та же самая элементарная конъюнкция: <math>x_1\land x_2</math> и <math>x_2 \land x_1</math> — одна и та же элементарная конъюнкция;
• <math>x_1\land \overline{x_2} \land x_3</math> — элементарная конъюнкция ранга 3. Выражения <math>\overline{x_2} \land x_1 \land x_3</math>, <math>x_1 \land x_3 \land \overline{x_2}</math> определяют ту же самую элементарную конъюнкцию.

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

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

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

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

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

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

Выражения <math>x_1 \lor x_1</math>, <math>(x_1 \land \overline{x_2}) \lor x_3 \lor (x_1 \land \overline{x_2})</math> ДНФ не являются, так как в ДНФ элементарные конъюнкции не повторяются. Выражения <math>\overline{(x_1 \lor x_2)}</math>, <math>x_1 \lor (x_2 \land (x_3 \lor x_4))</math>, <math>x_1 \lor x_2 \lor 0</math> ДНФ не являются, так как в ДНФ в качестве операндов дизъюнкций допускаются лишь элементарные конъюнкции (с одним особым случаем: ДНФ длины 0, она имеет вид <math>0</math>).

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

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

Любая булева функция может быть выражена в виде ДНФ. Например, приведённая выше функция <math>\overline{(x_1 \lor x_2)}</math> может быть задана ДНФ <math>\overline{x_1} \land \overline{x_2}</math>, функция <math>x_1 \lor (x_2 \land (x_3 \lor x_4))</math> — задана ДНФ <math>x_1 \lor (x_2 \land x_3) \lor (x_2 \land x_4)</math>, а функция <math>x_1 \lor x_2 \lor 0</math> — задана ДНФ <math>x_1 \lor x_2</math>. Как уже было сказано выше, одна и та же функция может иметь несколько ДНФ, однако существует некоторые особые виды ДНФ, которые существуют и единственны для каждой булевой функции: такие как совершенная ДНФ и сокращённая ДНФ.

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

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

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

<math>A \rightarrow B = \neg A \vee B</math>

<math>A \leftrightarrow B = (A \wedge B) \vee (\neg A \wedge \neg B)</math>

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

<math>\neg (A \vee B) = \neg A \wedge \neg B</math>

<math>\neg (A \wedge B) = \neg A \vee \neg B</math>

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

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

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

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

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

<math>F = \neg ((\neg X \vee Y) \vee \neg (\neg Y \vee Z))</math>

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

<math>F = (\neg \neg X \wedge \neg Y) \wedge (\neg Y \vee Z) = (X \wedge \neg Y) \wedge (\neg Y \vee Z)</math>

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

<math>F = (X \wedge \neg Y \wedge \neg Y) \vee (X \wedge \neg Y \wedge Z)</math>

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

<math>F = (X \wedge \neg Y ) \vee (X \wedge \neg Y \wedge Z)</math>

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

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

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

<math>(A \land B) \lor (\neg B \land C) \lor (B \land \neg C)</math>

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

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

<math>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}</math>,

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

Таким образом, для построения СДНФ по таблице истинности достаточно пройтись по всем наборам <math>\sigma_1,\ldots,\sigma_n</math>, на которых функция равна <math>1</math>, и добавить элементарную конъюнкцию вида <math>x_1^{\sigma_1} \land \ldots \land x_n^{\sigma_n}</math>.

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

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

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

<math>Z \vee \neg Z = 1</math>,

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

<math>X \vee \neg Y \neg Z = X(Y \vee \neg Y)(Z \vee \neg Z) \vee (X \vee \neg X)\neg Y \neg Z =</math>

<math>

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 = </math>

<math> = XYZ \vee X \neg YZ \vee XY \neg Z \vee X \neg Y \neg Z \vee \neg X \neg Y \neg Z</math>

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

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

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

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

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

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

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

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

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

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

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

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

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

<math>(A \land B \land \overline{C}) \lor (\overline{D} \land E \land F) \lor (C \land D) \lor B;</math>

<math>(A \cdot B \cdot \overline{C}) \lor (\overline{D} \cdot E \cdot F) \lor (C \cdot D) \lor B;</math>

<math>AB\overline{C} \lor \overline{D}EF \lor CD \lor B;</math>

<math>AB\overline{C} + \overline{D}EF + CD + B.</math>

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

См. также

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

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

Литература

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

Ссылки

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