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

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

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

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

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

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

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

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

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

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

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

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

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

Определение 5. Совершенной дизъюнктивной нормальной формой формулы А(x₁,x₂,…,x_n) называется ДНФ, обладающая следующими свойствами:

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

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

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

г) в каждой элементарной конъюнкции содержится либо X_i, либо , где i=.

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

1) если какая-нибудь элементарная конъюнкция не содержит высказывание X_i, то заменим выражением ;

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

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

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

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

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

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

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

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

г) каждая элементарная дизъюнкция содержит либо X_i, либо , где i=.

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

1) если какая-нибудь элементарная дизъюнкция не содержит высказывание X_i, то заменим выражением ;

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

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

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

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

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