Нормальные формы

Основной из задач алгебры высказываний является проблема разрешения, т.е. является ли данная формула тавтологией или противоречием или выполнимой формулой. Эта проблема легко решается с помощью нормальных форм.

Элементарной конъюнкцией $n$ высказываний называется конъюнкция высказываний или их отрицаний.

Элементарной дизъюнкцией $n$ высказываний называется дизъюнкция высказываний или их отрицаний.

Чтобы элементарная дизъюнкция была тождественно истинной, необходимо и достаточно, чтобы в ней содержалось два высказывания, из которых одно является отрицанием другого.

Чтобы элементарная конъюнкция была тождественно ложной, необходимо и достаточно, чтобы в ней присутствовала пара высказываний, из которых одно является отрицанием другого

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

Формула равносильная данной и представляющая собой дизъюнкцию элементарных конъюнкций называется дизъюнктивной нормальной формой данной формулы. { ДНФ } .

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

Формула равносильная данной и представляющая собой конъюнкцию элементарных дизъюнкций называется конъюнктивной нормальной формой данной формулы. { КНФ } .

Обобщим существование ДНФ или КНФ для каждой формулы:

Все логические операции можно заменить тремя: конъюнкцией, дизъюнкцией и отрицанием.

Знак отрицания с помощью законов де Моргана можно отнести к пропозициональным переменным.

С помощью дистрибутивных законов формула преобразовывается в конъюнкцию элементарных дизъюнкций или дизъюнкцию элементарных конъюнкций.

Для каждой формулы может быть составлено несколько ДНФ и КНФ. Но все ДНФ { или КНФ } данной формулы равносильны между собой.

Совершенная дизъюнктивная нормальная форма

Совершенной дизъюнктивной нормальной формой формулы $A(x_1,x_2,…,x_n)$ называется ДНФ, обладающая следующими свойствами:

а } в ней нет одинаковых дизъюнктивных элементов;

б } ни одна элементарная конъюнкция не содержит двух одинаковых высказываний;

в } ни какая элементарная конъюнкция не содержит высказывание вместе с ее отрицанием;

г } в каждой элементарной конъюнкции содержится либо $X_i$, либо $\overline { X } _i$, где $i = 1, n$.

Условие а } – г } являются необходимыми и достаточными для того, чтобы ДНФ стала СДНФ. В свою очередь эти условия дают возможность составить алгоритм получения СДНФ из ДНФ:

1. если какая-нибудь элементарная конъюнкция не содержит высказывание $X_i$, то заменим выражением $B\wedge (X_i\vee \overline { X } _i) \equiv (B\wedge X_i)\vee (B\wedge \overline { X } _i)$;

2. если в полученном выражении окажутся одинаковые элементарные конъюнкции, то лишние опускаются;

3. если в некоторых элементарных конъюнкциях окажутся одинаковые высказывания, то лишние опускаются;

4. удаляем элементарные конъюнкции, в которых содержатся высказывания вместе с их отрицанием.

Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.

Совершенная конъюнктивная нормальная форма

Совершенная конъюнктивная нормальная форма – это ее КНФ обладающая свойствами:

а } в ней нет двух одинаковых конъюнктивных элементов;

б } ни одна элементарная дизъюнкция не содержит двух одинаковых высказываний;

в } ни одна элементарная дизъюнкция не содержит какой-нибудь переменной с ее отрицанием;

г } каждая элементарная дизъюнкция содержит либо $X_i$, либо $\overline { X } _i$, где $i = 1, n$.

В свою очередь эти условия дают возможность составить алгоритм получения СКНФ из КНФ:

1. если какая-нибудь элементарная дизъюнкция не содержит высказывание $X_i$, то заменим выражением $B\vee (X_i\wedge \overline { X } _i)\equiv (B\vee X_i)\wedge (B\vee \overline { X } _i)$;

2. если в полученном выражении окажутся одинаковые элементарные дизъюнкции, то лишние опускаются;

3. если в некоторых элементарных дизъюнкциях окажутся одинаковые высказывания, то лишние опускаются;

4. удаляем элементарные дизъюнкции, в которых содержатся высказывания вместе с их отрицанием.

Для тождественно истинных формул СКНФ не существует.

Для любой формулы алгебры высказываний существует только одна СДНФ и только одна СКНФ, кроме противоречий и тавтологий, т.е. для противоречий будет существовать СКНФ, а для тавтологий – только СДНФ.