Диз'юнкти́вна норма́льна фо́рма (ДНФ) в булевій логіці — нормальна форма в якій булева формула має вид диз'юнкції декількох кон'юнктів (де кон'юнктами називаються кон'юнкції декількох пропозиційних символів або їх заперечень).
Приклади
Наступні формули записані в ДНФ:
Наступні формули не є в ДНФ:
Проте ці формули еквівалентні наступним формулам записаним у диз'юнктивній нормальній формі:
Приведення булевої формули до ДНФ
Довільна булева формула може бути приведена до ДНФ за допомогою наступного алгоритму:
Крок 1 : Усі логічні зв'язки виразити через кон'юнкцію, диз'юнкцію і заперечення. Крок 2 : Скасувати всі подвійні заперечення і використати, де можливо, закони де Моргана. Тобто замінити: на на на Крок 3 : Використати де можливо дистрибутивність кон'юнкції, тобто замінити: на
Втім, при цьому розмір булевої формули може зрости експоненціально. Так, наприклад, щоб записати наступну формулу буде потрібно 2n кон'юнктів:
КНФ цієї формули має вигляд:
Формальна граматика, що описує ДНФ
Наступна формальна граматика описує всі формули, приведені до ДНФ: <ДНФ> → <кон'юнкт> <ДНФ> → <ДНФ> ∨ <кон'юнкт> <кон'юнкт> → <літерал> <кон'юнкт> → (<кон'юнкт> ∧ <літерал>) <літерал> → <терм> <літерал> → ¬<терм>
де <терм> позначає довільну булеву змінну.
Див. також Кон'юнктивна нормальна форма Нормальна форма формули у логіці предикатів Числення висловлень Алгоритм Блейка Досконала диз'юнктивна нормальна форма
Джерела