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

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

Например, следующие формулы записаны в ДНФ:

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

Дизъюнктивная нормальная форма удобна для автоматического доказывания теорем.

Приведение булевой формулы к ДНФ

Любая булева формула может быть приведена к ДНФ. Впрочем, при этом размер булевой формулы может возрасти экспоненциально. Так, например, 2n конъюнктов потребуется, чтобы записать следующую формулу:

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

Формальная грамматика, описывающая ДНФ

Следующая формальная грамматика описывает все формулы, приведенные к ДНФ:

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

где <терм> обозначает произвольную булеву переменную.

См. также

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home