X,y,z, . . . Или их отрицаний.

Пример. B = Y ∧ ￢Y ∧ Z ∧ Y ∧￢X

Отметим, что в формуле A входит буква Y вместе со своим отрицанием

￢Y . Придадим любые значения И, Л буквам X, Y,Z в формуле A. Тогда

одно из значений Y или ￢Y в A будет истинно. Поэтому значение форму-

лы A всегда равно И. Следовательно, A является тождественно истинной

формулой.

ТЕОРЕМА 1 Элементарная дизъюнкция является тождествен-

но истиной, тогда и только тогда, когда в нее входит некоторая

буква вместе со своим отрицанием.

Доказательство. Предположим, что в элементарную дизъюнкцию A вхо-

дит некоторая буква вместе со своим отрицанием. Как и выше получим,

что A—тождественно истинна.

Обратно, пусть A—тождественно истинна. Предположим противное,

что в A нет буквы, входящей вместе со своим отрицанием. Построим на-

бор значений букв, при которых A ложна, это противоречит условию и

завершит доказательство. Правило построения набора следующее. Про-

сматриваем слева направо буквы в формуле A. Если буква входит в фор-

мулу без отрицания, то присваиваем ей значение Л, если с отрицанием –

значение И. Тогда значение формулы A имеет вид Л∨ Л∨ . . .∨Л и рав-

но Л. Заметим, что осуществимость процедуры присваивания возможна

лишь тогда, когда в A нет буквы, входящей вместе со своим отрицанием.

Иначе, нам пришлось бы одной и тойже букве присваивать одновременно

значение Ии значение Л. Теорема доказана.

ТЕОРЕМА 2 Элементарная конъюнкция является тождествен-

но ложной, тогда и только тогда, когда в нее входит некоторая

буква вместе со своим отрицанием.

Доказательство. Предположим, что в элементарную конъюнкцию A вхо-

дит некоторая буква вместе со своим отрицанием. Очевидно, чтоA– тож-

дественно ложная формула.

Обратно, пусть A тождественно ложна. Предположим противное, в A

нет буквы, входящей вместе со своим отрицанием. Найдем набор значе-

ний букв, при которых A истинна, это противоречит условию. Просмат-

риваем слева направо буквы в формуле A. Если буква входит в формулу

без отрицания, то присваиваем ей значение И, если с отрицанием – зна-

чение Л. Тогда значение формулы A имеет вид И∧ И∧ . . .∧Ии, поэтому,

равно И, противоречие. Теорема доказана.

Напомним определение равносильности формул.

ОПРЕДЕЛЕНИЕ 4 Две формулы A и B называются равносильны-

ми, если при любом наборе значений переменных, входящих в эти

формулы, истинностные значения формул A и B равны.

Если формулы A и B равносильны, то записываем A ≡ B.

Приведем основные законы, связанные с равносильностью формул,

полученные во вводном курсе математики.

ТЕОРЕМА 3 Пусть A, B, C —произвольные формулы алгебры вы-

сказываний. Тогда справедливы следующие утверждения:

1. A ∧ A ≡ A,

2. A ∨ A ≡ A,

_

—свойства идемпотентности

3. A ∧ B ≡ B ∧ A,

4. A ∨ B ≡ B ∨ A,

_

—свойства коммутативности

5. A ∧ (B ∧ C) ≡ (A ∧ B) ∧ C,

6. A ∨ (B ∨ C) ≡ (A ∨ B) ∨ C,

_

—свойства ассоциативности

7. A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C),

8. A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C),

_

—свойства дистрибутивности

12

9. ￢(A ∧ B) ≡ ￢A∨￢B,

10. ￢(A ∨ B) ≡ ￢A∧￢B,

_

—свойства де Моргана

11. ￢(￢A) ≡ A, —свойство двойного отрицания

12. A → B ≡ ￢B →￢A, —свойство контрапозиции

13. A → B ≡ ￢A ∨ B,

14. A ↔ B ≡ (A → B) ∧ (B → A),

Как в математике, так и в обычной речи можно заменять высказывание

на равносильное. Например, можно сказать «неверно, что 3 больше 1 и

11 делится на 2», или сказать «неверно, что 3 больше 1 или неверно, что

11 делится на 2».Мы применили равносильность вида (9).

Мы можем заменить произвольную формулу X на равносильную фор-

мулу Y , в котором есть только следующие логические знаки: ∨, ∧ и ￢.

Для этого выполним следующие преобразования формулы X.

1. Заменим любую часть A ↔ B в формуле X на (A → B) ∧ (B → A)

по (14). Получится равносильная с X формула без знака↔.

2. Заменим любую часть A → B на ￢A ∨ B и избавимся от знака→.

Итак, в алгебре высказываний обойтись только следующими логически-

ми знаками: ∨, ∧ и ￢.

ОПРЕДЕЛЕНИЕ 5 Конъюнктивной нормальной формой (КНФ)

для формулы X называется равносильная ей формула Y , являюща-

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

Укажем способ для получения конъюнктивной нормальной формы для

формулы X. Избавимся, как было сказано выше, от знаков, отличных от

∨, ∧ и ￢. С помощью дистрибутивных законов и законов ￢(A ∧ B) ≡

￢A∨￢B , ￢(A∨B) ≡ ￢A∧￢B и ￢￢A ≡ A постепенно преобразуем X и

промежуточные формулы к виду X1 ∧ X2. Проделав тоже самое с X1, X2

и их частями мы получим конъюнкцию элементарных дизъюнкций.

ОПРЕДЕЛЕНИЕ 6 Дизъюнктивной нормальной формой (ДНФ)

для формулы X называется равносильная ей формула Y , являюща-

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

13

Рассмотрим способ для получения дизъюнктивной нормальной формой

для формулы X. Как и выше избавимся вначале от знаков, отличных от

∨, ∧ и ￢. Затем преобразуем X и промежуточные формулы к видуX1∨X2.

Проделав это несколько раз, получим дизъюнкцией элементарных конъ-

юнкций. Можно привести и более строгое доказательство индукцией по

числу букв в формуле X.

Теперь можно получить критерий тождественно истинной и тожде-

ственно ложной формулы.

ТЕОРЕМА 4 ФормулаX является тождественно истинной, то-

гда и только тогда, когда в ее КНФ каждая элементарная дизъ-

юнкция имеет вхождение некоторой буквы вместе со своим отри-

цанием.

Доказательство. Предположим, что X1 — КНФ для формулы X и X1 =

Y ∧ Z ∧ . . ., где Y,Z, . . . – элементарные дизъюнкции.

Если каждая элементарная дизъюнкция Y,Z, . . . имеет вхождение

некоторой буквы вместе со своим отрицанием, то при любом значении

букв, входящих в A, значения Y,Z, . . . равны И. Тогда значения X1 и X

равны И.

Обратно, пусть формула X тождественно истинна.

Тогда элементарные дизъюнкции Y,Z, . . . также тождественно истин-

ны и, поэтому, имеют вхождение некоторой буквы вместе со своим отри-

цанием. Теорема доказана.

Аналогично получаем критерий тождественно тождественно ложной

формулы.

ТЕОРЕМА 5 ФормулаX являетсятождественно ложной,тогда

и только тогда, когда в ее ДНФ каждая элементарная конъюнк-

ция имеет вхождение некоторой буквы вместе со своим отрица-

нием.