При построении формул логики высказываний мы будем использовать символы логических операций, скобки и символы X, Y, Z, … (быть может, с индексами) для обозначения переменных высказываний (высказывательных, или пропозициональных переменных). Совокупность этих символов мы будем называть алфавитом логики высказываний. Любая конечная последовательность символов алфавита называется словом. Среди всех слов мы выделяем те, которые построены по определенным правилам, и называем их формулами логики высказываний. Запись (X∧(Y))→Z естественно считать формулой, а запись ∧(ZY))→ – нет.
Уточним понятие формулы, описав процедуру построения формул.
Во-первых, мы считаем формулой символ любой пропозициональной переменной. Во-вторых, если U и V – формулы, то (U), (U∧V), (U∨V), (U→V) – также формулы. Слово в алфавите логики высказываний считается формулой, если оно получено в соответствии с этим правилами.
Часть формулы, которая сама является формулой, называется подформулой. Так, формула U является подформулой формулы (U), а формулы U и V – подформулами формул (U∧V), (U∨V), (U→V). Мы будем называть формулу булевой, если в ее записи не используется импликация.
Для упрощения записи условимся опускать в формулах внешние скобки. Далее будем считать, что отрицание «выполняется» раньше остальных операций, и опускать скобки, если отрицание относится к кратчайшей, стоящей за ним подформуле. Часто мы будем записывать отрицание с помощью горизонтальной черты над подформулой, к которой оно относится. Мы будем иногда опускать знак конъюнкции и вместо U∧V писать просто UV. Наконец, мы будем считать, что конъюнкция выполняется раньше, чем дизъюнкция (подобно тому, как в арифметических выражениях умножение выполняется раньше, чем сложение), и опускать скобки, которые могут быть с учетом этого восстановлены. Например, формула
(((((X))∧(Y))∨((X)∧((Y))))
может быть коротко записана в виде
XY∨XY.
Чтобы указать, что в записи формулы U участвуют пропозициональные переменные X, Y, …, Z (а никаких других нет), мы будем писать U=U(X,Y,…,Z).
Формула превращается в высказывание, если в ней каждую пропозициональную переменную заменить некоторым высказыванием. Так, подставив в формулу
U(X,Y)=XY∨XY
высказывание A:(1=2) вместо X и высказывание B:(3>2) вместо Y, получим высказывание
U(A,B)=(1≠2)(3>2)∨(1=2)(3≤2).
Несложно посчитать значение истинности полученного высказывания: [U(A,B)]=1. Ясно, что значение истинности высказывания U(A,B) зависит не от самих высказываний A и B, а лишь от их значений истинности. Каковы бы ни были высказывания A и B, если только [A]=0, а [B]=1, мы получим [U(A,B)]=1. Составим таблицу, в которой вычисляется значение истинности высказывания, полученного при замене в формуле U переменных X и Y высказываниями, в зависимости от значений истинности этих высказываний.
Назовем оценкой списка переменных формулы U=U(X,Y,…,Z) сопоставление каждой переменной некоторого истинностного значения. Допуская некоторую вольность речи, можно сказать, что каждой оценке переменных соответствует значение истинности формулы U.
Пример.Составим таблицу истинности для формулы X→(Y→Z).
Формулы U=U(X,Y,…,Z) и V=V(X,Y,…,Z) называются равносильными, если они принимают одинаковые значения для любой оценки переменных X,Y,…,Z.
Если для формул U и V построены таблицы истинности, то равносильность означает, что итоговые столбцы в этих таблицах совпадают. Равносильность формул U и V будем обозначать через U≅V. Легко заметить, что отношение равносильности рефлексивно, симметрично и транзитивно и, значит, является отношением эквивалентности. Каждый класс эквивалентности состоит из равносильных между собой формул.
Теорема (основные равносильности). Имеют место следующие равносильности.
Коммутативность конъюнкции и дизъюнкции:
X∧Y≅Y∧X; X∨Y≅Y∨X.
Ассоциативность конъюнкции и дизъюнкции:
(X∧Y)∧Z≅X∧(Y∧Z); (X∨Y)∨Z≅X∨(Y∨Z).
Идемпотентность конъюнкции и дизъюнкции:
X∧X≅X; X∨X≅X.
Дистрибутивность конъюнкции и дизъюнкции друг относительно друга:
X∧(Y∨Z)≅(X∧Y)∨(X∧Z); X∨(Y∧Z)≅(X∨Y)∧(X∨Z).
Законы поглощения: X∧(X∨Y)≅X; X∨(X∧Y)≅X.
Снятие двойного отрицания:
X≅X.
Законы де Моргана:
(X∧Y)≅X∨Y; (X∨Y)≅X∧Y.
Законы расщепления:
(X∧Y)∨(X∧Y)≅X; (X∨Y)∧(X∨Y)≅X.
Устранение импликации:
X→Y≅X∨Y.
Любая из перечисленных равносильностей легко может быть доказана с помощью таблиц истинности. Используя основные равносильности, удобно записывать последовательность равносильных преобразований формулы в виде цепочки. Например:
X→(Y→Z) ≅ X→(Y∨Z) ≅ X∨(Y∨Z) ≅ (X∨Y)∨Z ≅
≅ (Y∨X)∨Z ≅ Y∨(X∨Z) ≅ Y→(X∨Z) ≅ Y→(X→Z).
При записи равносильных преобразований удобно использовать и некоторые другие равносильности. Например, покажем, что
X∨(YY) ≅ X.
Последовательно применяя законы дистрибутивности и расщепления, получаем: X∨(YY) ≅ (X∨Y)(X∨Y) ≅ X.
Аналогично
X(Y∨Y) ≅ X.
Сформулируем еще несколько правил, которые позволяют получать равносильные формулы без непосредственной проверки по таблицам истинности.
Если в равносильных формулах пропозициональные переменные заменить формулами (одинаковые переменные одинаковыми формулами) получатся равносильные формулы.
Если формулы U и V равносильны, U≅V, а W – произвольная формула, то имеют место следующие равносильности:
U≅V; U∧W≅V∧W; U∨W≅V∨W;
U→W≅V→W; W→U≅W→V.
Используя устранение импликации, любую формулу можно с помощью равносильных преобразований привести к булевой формуле.
