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

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

Определение

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

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

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

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

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

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

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

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

  • — единственная ДНФ длины 0, её ранг равен 0;
  • любая элементарная конъюнкция есть ДНФ длины 1, её ранг равен её рангу как элементарной конъюнкции;
  • — ДНФ длины 2 и ранга 2. Выражение задаёт ту же самую ДНФ;
  • — ДНФ длины 2 и ранга 3.
  • — ДНФ длины 4 и ранга 9.

Выражения , ДНФ не являются, так как в ДНФ элементарные конъюнкции не повторяются. Выражения , , ДНФ не являются, так как в ДНФ в качестве операндов дизъюнкций допускаются лишь элементарные конъюнкции (с одним особым случаем: ДНФ длины 0, она имеет вид ).

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

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

Любая булева функция может быть выражена в виде ДНФ. Например, приведённая выше функция может быть задана ДНФ , функция — задана ДНФ , а функция — задана ДНФ . Как уже было сказано выше, одна и та же функция может иметь несколько ДНФ, однако существует некоторые особые виды ДНФ, которые существуют и единственны для каждой булевой функции: такие как совершенная ДНФ и сокращённая ДНФ.

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

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

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

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

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

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

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

Приведем к ДНФ формулу

Выразим логическую операцию → через

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

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

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

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

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

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

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

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

,

где

Таким образом, для построения СДНФ по таблице истинности достаточно пройтись по всем наборам , на которых функция равна , и добавить элементарную конъюнкцию вида .

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

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

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

,

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

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

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

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

<ДНФ> → <конъюнкт>
<ДНФ> → <ДНФ> ∨ <конъюнкт>
<конъюнкт> → <литерал>
<конъюнкт> → (<конъюнкт> ∧ <литерал>)
<литерал> → <терм>
<литерал> → ¬<терм>

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

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

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

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

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

См. также

Примечания

  1. Поздняков С.Н., Рыбин С.В. Дискретная математика. — С. 303.

Литература

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

Ссылки

Источник —

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