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

Диз'юнкти́вна норма́льна фо́рма (ДНФ) в булевій логіці — нормальна форма в якій булева формула має вид диз'юнкції декількох кон'юнктів (де кон'юнктами називаються кон'юнкції декількох пропозиційних символів або їх заперечень).

Приклади

Наступні формули записані в ДНФ:

${\displaystyle A\lor B}$

${\displaystyle A\!}$

${\displaystyle (A\land B)\lor \neg A}$

${\displaystyle (A\land B\land \neg C)\lor (\neg D\land E\land F)\lor (C\land D)\lor B}$

Наступні формули не є в ДНФ:

${\displaystyle \neg (B\land C)}$

${\displaystyle A\lor (B\land (C\lor D))}$

Проте ці формули еквівалентні наступним формулам записаним у диз'юнктивній нормальній формі:

${\displaystyle \neg B\lor \neg C}$

${\displaystyle A\lor (B\land C)\lor (B\land D).}$

Приведення булевої формули до ДНФ

Довільна булева формула може бути приведена до ДНФ за допомогою наступного алгоритму:

Крок 1 : Усі логічні зв'язки виразити через кон'юнкцію, диз'юнкцію і заперечення.

Крок 2 : Скасувати всі подвійні заперечення і використати, де можливо, закони де Моргана. Тобто замінити:

${\displaystyle \lnot \lnot A}$ на ${\displaystyle A\;}$

${\displaystyle \lnot (A\land B)}$ на ${\displaystyle (\lnot A\lor \lnot B)}$

${\displaystyle \lnot (A\lor B)}$ на ${\displaystyle (\lnot A\land \lnot B)}$

Крок 3 : Використати де можливо дистрибутивність кон'юнкції, тобто замінити:

${\displaystyle (A\land (B\lor C))}$ ${\displaystyle ((B\lor C)\land A)}$ на ${\displaystyle ((A\land B)\lor (A\land C))}$

Втім, при цьому розмір булевої формули може зрости експоненціально. Так, наприклад, щоб записати наступну формулу буде потрібно 2ⁿ кон'юнктів:

${\displaystyle (X_{1}\lor Y_{1})\land (X_{2}\lor Y_{2})\land \dots \land (X_{n}\lor Y_{n})}$

КНФ цієї формули має вигляд:

${\displaystyle (X_{1}\vee \cdots \vee X_{n-1}\vee X_{n})\wedge (X_{1}\land \cdots \land X_{n-1}\land Y_{n})\lor \cdots \lor (Y_{1}\land \cdots \land Y_{n-1}\land Y_{n}).}$

Формальна граматика, що описує ДНФ

Наступна формальна граматика описує всі формули, приведені до ДНФ:

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

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

<кон'юнкт> → <літерал>

<кон'юнкт> → (<кон'юнкт> ∧ <літерал>)

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

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

де <терм> позначає довільну булеву змінну.

Див. також

• Кон'юнктивна нормальна форма
• Нормальна форма формули у логіці предикатів
• Числення висловлень
• Алгоритм Блейка
• Досконала диз'юнктивна нормальна форма

Джерела

Shawn Hedman. A First Course in Logic. Oxford University Press 2004 ISBN 0-19-852980-5