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

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

Определение

править

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

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

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

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

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

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

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

править

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

править

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

 
 
 

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

 
 

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

 

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

 
 

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

 
 
 

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

править

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

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

 

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

 

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

 

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

 

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

править

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

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

 

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

править

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

 ,

где  

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

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

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

править

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

 ,

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

 
 
 

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

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

править

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

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

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

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

править

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

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

 
 
 
 

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

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

править

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

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

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

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

править

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

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

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

См. также

править

Примечания

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

Литература

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

Ссылки

править