Диз'юнкти́вна норма́льна фо́рма (ДНФ) в булевій логіці — (нормальна форма) в якій булева формула має вид диз'юнкції декількох кон'юнктів (де кон'юнктами називаються кон'юнкції декількох пропозиційних символів або їх заперечень).
Приклади
Наступні формули записані в ДНФ:
Наступні формули не є в ДНФ:
Проте ці формули еквівалентні наступним формулам записаним у диз'юнктивній нормальній формі:
Приведення булевої формули до ДНФ
Довільна може бути приведена до ДНФ за допомогою наступного алгоритму:
- Крок 1 : Усі логічні зв'язки виразити через кон'юнкцію, диз'юнкцію і заперечення.
- Крок 2 : Скасувати всі подвійні заперечення і використати, де можливо, закони де Моргана. Тобто замінити:
на
на
на
- Крок 3 : Використати де можливо дистрибутивність кон'юнкції, тобто замінити:
на
Втім, при цьому розмір булевої формули може зрости експоненціально. Так, наприклад, щоб записати наступну формулу буде потрібно 2n кон'юнктів:
КНФ цієї формули має вигляд:
Формальна граматика, що описує ДНФ
Наступна формальна граматика описує всі формули, приведені до ДНФ:
- <ДНФ> → <кон'юнкт>
- <ДНФ> → <ДНФ> ∨ <кон'юнкт>
- <кон'юнкт> → <літерал>
- <кон'юнкт> → (<кон'юнкт> ∧ <літерал>)
- <літерал> → <терм>
- <літерал> → ¬<терм>
де <терм> позначає довільну булеву змінну.
Див. також
- Кон'юнктивна нормальна форма
- (Нормальна форма формули у логіці предикатів)
- Числення висловлень
- (Алгоритм Блейка)
- (Досконала диз'юнктивна нормальна форма)
Джерела
Shawn Hedman. A First Course in Logic. Oxford University Press 2004
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет