Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний

Конъюнктивным одночленом от переменных x₁, x₂,..., х_п называется конъюнкция этих переменных или их отрицаний.

Дизъюнктивным одночленом от переменных x₁, x₂,..., х_п называется дизъюнкция этих переменных или их отрицаний.

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

Например: — ДНФ.

Формула, равносильная данной формуле алгебры высказываний и являющаяся конъюнкцией элементарных дизъюнктивных одночленов, называется конъюнктивной нормальной формой (КНФ) данной формулы.

Например: — КНФ.

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

Алгоритм построения

(1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием.
Это можно сделать, используя равносильные формулы:

(2) Заменить знак отрицания, относящийся к выражениям типа
или , знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

= ; =

(3) Избавиться от знаков двойного отрицания.

(4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.

Дата добавления: 2014-11-07