Упражнение. Пусть .Построим КНФ для этой формулы.

Пусть . Построим КНФ для этой формулы.

1) избавимся от знаков импликации, получим:

( Ú B)«( Ú );

2) избавимся от знака двойной импликации:

;

3) избавимся от знака отрицания, относящегося к выражениям, состоящим более чем из одной переменной:

;

4) избавимся от двойных и тройных отрицаний:

;

5) применим законы дистрибутивности:

,

.

Получим S= . Это КНФ для данной формулы S.

Используя свойства AÚ A=A и AA=A, упростим КНФ для S:

S= .

Теорема 3. Формула алгебры высказываний является тождественно истинной тогда и только тогда, когда каждый множитель ее КНФ содержит пару слагаемых, одно из которых является элементарным высказыванием, а другое - его отрицанием.

Теорема 4. Формула алгебры высказываний является тождественно ложной тогда и только тогда, когда каждое слагаемое (т. е. каждое элементарное произведение) ее ДНФ содержит пару сомножителей, один из которых есть элементарное высказывание, другой - его отрицание.

Теоремы 3, 4 позволяют решить вопрос о выполнимости любой формулы алгебры высказываний.

Нужно построить для этой формулы ее ДНФ или ее КНФ. Если построена ДНФ и оказывается, что она удовлетворяет условиям теоремы 4, то формула является невыполнимой. Можно построить КНФ для отрицания исходной формулы. Если окажется, что она удовлетворяет условиям теоремы 3, то исходная формула невыполнима, т. к. ее отрицание тождественно истинно. В остальных случаях формулы являются выполнимыми.