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

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з ДНФ)
Перейти до навігації Перейти до пошуку

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

Приклади

[ред. | ред. код]

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

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

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

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

[ред. | ред. код]

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

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

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

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

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

[ред. | ред. код]

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

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

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

Див. також

[ред. | ред. код]

Джерела

[ред. | ред. код]

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