A ~ с ≡ b ~ с; с ~ a ≡ с ~b

и т. д.

а = Л; b = Л, с = Л

убедиться в правильности каждой равносильности.

Теорема 2 (правило равносильных замен переменных).

Пусть а = b и с — формула, в которой выделено одно вхождение переменной X. Пусть с_а получается из с заменой этого вхожде­ния X на а, а с_b из с заменой того же вхождения X на b. Тогда c_а ≡ c_b.

Доказательство. Эту теорему докажем методом математи­ческой индукции по числу п логических связок в формуле с.

Для п = 0 формула с = X (не имеет логических связок). Тогда с_а = а и с_b = b. Следовательно, утверждение теоремы верно.

Пусть теорема верна для формулы с числом связок, не пре­восходящим натурального п > 0.

Рассмотрим случай, когда имеется п + 1 логическая связка. Тогда формула имеет один из пяти возможных видов с = d, с = f g, с = f&g, с = (f => g), с = (f ~g). Здесь d, f, g — формулы с числом логических связок не более n, для которых теорема спра­ведлива. Заметим, что с_а = d_a, c_b = d_b или с_а = f_a g_а, с_b = f_b g_b, или с_а = f_a & g_a, с_b = f_b g_b или и т. д. Так как для формул d, f, g теорема справедлива, имеем d_a ≡ d_b, f_a ≡ f_b, g_a ≡ g_b. Тогда в силу предыдущей теоремы получим то, что требовалось доказать.

Определение 12. Подформулой формулы с называется любое подслово с, само являющееся формулой.

Следующие правила приведем без доказательств [Нефедов В.Н. Курс дискретной математика. – М.: Изд-во МАИ, 1992].

Теорема 3 (правило равносильных замен подформул).

Пусть с_а — формула, содержащая а в качестве своей подформу­лы. Пусть с_b получается из с_а заменой а в этом вхождении на b. Тогда, если а ≡ b, то с_а ≡ c_b,.

Теорема 4 (правило устранения импликаций и эквивалентностей).

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

Правило перехода к булевым функциям.

Нетрудно показать, что всякая формула логики высказываний может быть представлена булевой функцией и, наоборот, всякая бу­лева функция соответствует некоторой формуле логики выска­зываний. Для этого достаточно перекодировать (пе­реобозначить) логическое значение истинностной оценки языко­вых текстов следующим образом. Значение истина обозначить числом 1, а значение ложь числом 0. Далее, всякую атомар­ную формулу X, Y,... логики высказываний, с помощью кото­рой моделируем языковый текст, надо обозначить булевой пере­менной х, у,... Теперь всякая оценка атомарной формулы будет соответствовать заданию значения булевой переменной. Всякая формула логики высказываний будет соответствовать своей бу­левой функции. При этом таблица истинности формулы будет соответствовать табличному заданию булевой функции, а анали­тическое задание формулы аналитическому заданию булевой функции. Логические связки логики высказываний будут знака­ми алгебраических операций над булевыми переменными и кон­стантами.

Например, формула логики высказываний

будет соответствовать булевой функции

.

Здесь X, Y обозначено через х,у, знак конъюнкции & — через •, знак отрицания X — через .

Рассмотрим текстовую логическую задачу.

Нормальные формы формул логики высказываний

Определим теперь нормальные формы формул. Сначала за­метим, что, в силу ассоциативности операций & и , как бы не расставляли скобки в выражениях:

А₁ & А₂ &... & А_к; A₁ A₂ ... A_k (к > 3),

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

Определение 13. Формулу называют элементарной конъюнкцией, или конъюнктом, если она является конъюнк­цией переменных или их отрицаний.

Пример 3. Элементарные конъюнкции: Х₂& Х₃; Х₁ & Х₂ & Х₄ & Х₂.

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

Пример 4. Рассмотрим формулу (X₁ & Х₂ & Х₃) (X₁ & Х₂ & Х₃). Эта формула находится в ДНФ.

Справедлива следующая теорема, которую приведем без до­казательства.

Теорема 5. Для любой формулы а можно найти такую формулу b, находящуюся в ДНФ, что а = b. В этом случае фор­мула b называется дизъюнктивно нормальной формой форму­лы а.

Определение 15. Пусть формула а не содержит символов =>, ~. Формула а* называется двойственной формуле а, если она получена из а одновременной заменой всех символов &, на им двойственные, т. е. & на , на &.

Определение 16. Говорят, что формула а находится в конъюнктивной нормальной форме (КНФ), если формула а* находится в ДНФ.

Сформулируем без доказательства еще одну важную теорему.

Теорема 6. Для любой формулы а можно найти такую формулу b, что b находится в КНФ и а = b. В этом случае форму­ла b называется конъюнктивно нормальной формой формулы а.

Замечание 4. ДНФ и КНФ формулы а, не являются однознач­но определенными. Кроме ДНФ и КНФ вводятся еще другие нормаль­ные формы, например совершенные дизъюнктивные и конъюнктивные нормальные формы (СДНФ и СКНФ) [4, 6, 10, 11], как и для булевых функций (см. подразд. 6.2).

Законы логики высказываний. Тавтологии

Пусть формула а зависит от множества переменных Х₁,..., Х_n.

Определение 17. Формула а называется тавтологией (или тождественно-истинной формулой), если на любых оцен­ках списка переменных она принимает значение И, т. е. а ≡ И.

Здесь под оценкой списка переменных понимается сопоставле­ние каждой переменной этого списка некоторого истиностного значения.

Формула а называется выполнимой, если на некоторой оценке списка переменных Х₁,...,Х_п она принимает значение И. Формула а называется опровержимой, если на некоторой оценке списка переменных Х₁,...,Х_п она принимает значение Л.