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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Приклади[ред.ред. код]

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

A \or B
A\!
(A \and B) \or \neg A
(A \and B \and \neg C) \or (\neg D \and E \and F) \or (C \and D) \or B

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

\neg(B \and C)
A \or (B \and (C \or D))

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

\neg B \or \neg C
A \or (B \and C) \or (B \and D).

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

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

Крок 1 : Усі логічні зв'язки виразити через кон'юнкцію, диз'юнкцію і заперечення.
Крок 2 : Скасувати всі подвійні заперечення і використати, де можливо, закони де Моргана. Тобто замінити:
\lnot \lnot A на A\;
\lnot(A \land B) на (\lnot A \lor \lnot B)
\lnot(A \lor B) на (\lnot A \land \lnot B)
Крок 3 : Використати де можливо дистрибутивність кон'юнкції, тобто замінити:
(A \land (B \lor C)) ((B \lor C) \land A) на ((A \land B)\lor (A \land C))

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

(X_1 \or Y_1) \and (X_2 \or Y_2) \and \dots \and (X_n \or Y_n)

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

(X_1 \vee \cdots \vee X_{n-1} \vee X_n) \wedge 
(X_1 \and \cdots \and X_{n-1} \and Y_n) \or
\cdots \or
(Y_1 \and \cdots \and Y_{n-1} \and Y_n).

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

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

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

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

Див. також[ред.ред. код]

Джерела[ред.ред. код]

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