§2. Логические формулы и их равносильности

n1. Понятие логической формулы

Так как при рассмотрении высказываний в первую очередь интересуются лишь истинностными значениями этих высказываний, то иногда разрешается отождествлять высказывания с его истинностным значением. Так, например, сложное высказывание АВА при условии |В| = И можно записать в виде АИА.

Числовым выражениям элементарной алгебры соответствуют сложные высказывания математической логики, а буквенным выражениям алгебры сопоставляются так называемые логические формулы логики. Если в алгебре чаще всего рассматриваются действительные переменные, то есть переменные, множества значений которых совпадают с R, то в логике при построении логических формул используются так называемые высказывательные переменные, то есть переменные, множества всех значений которых совпадают с семейством всевозможных высказываний.

Логическую формулу можно получить, если в некотором сложном высказывании, построенном на базе элементарных высказываний А, В, С, ..., каждое из этих элементарных высказываний заменить на символы из списка: И, Л, X, Y, Z ..., где X, Y, Z, ... – некоторые высказывательные переменные, а И, Л – «специфические» высказывательные переменные, множества всех значений которых совпадают с семейством всевозможных истинных высказываний и ложных высказываний соответственно.

Дадим более строгое определение логической формулы.

Определение 3.

1) Всякая высказывательная переменная называется логической формулой.

2) Символы И, Л называются логическими формулами.

3) Если F₁ и F₂ – логические формулы, то символы (F₁), (₁), (F₁F₂), (F₁F₂), (F₁F₂), (F₁F₂) так же называются логическими формулами.

4) Только те символы называются логическими формулами, которые можно построить используя 1, 2 и 3 пункты определения.

(Определения такого типа называют индуктивными.)

Если F – некоторая логическая формула, то символы (F₁) и понимаются как различные способы записи одной и той же формулы.

Пример 1. Если X, Y, и Z – некоторые высказывательные переменные, то символ ((((XY))(XИ))Z) является логической формулой. Действительно, по требованиям 1 и 2 определения 1 символы X, Y, Z и И являются логическими формулами. Но тогда по требованию 3 того же определения символы (XY), (XИ), ((XY)), (((XY))(XИ)), ((((XY))(XИ))Z) являются логическими формулами.

Число скобок в записи логических формул часто можно уменьшить, используя соглашения, аналогичные принятым для записи сложных высказываний в nº1 §1.

Так, например, логическая формула, рассмотренная в примере 1, может быть записана в более простом виде: (XY)(XИ)Z.

n2. Равносильность логических формул. Тавтологии

Определение 4. Если (Х₁, Х₂, ..., Х_n) где nN, – упорядоченный набор всех высказывательных переменных, входящих в запись логической формулы F, то Х₁, Х₂, ... , Х_n, называются переменными логической формулы F, а саму логическую формулу обозначают символом F(Х₁, Х₂, ... , Х _n).

Истинностное значение высказывания F(A₁, A₂, …, A_n), полученного при замене в записи логической формулы F(Х₁, Х₂, ... , Х_n), переменных Х₁, Х₂, ... , Х_n на их конкретные значения A₁, A₂, …, A_n соответственно, называется истинностным значением логической формулы F(Х₁, Х₂, ... , Х_n) при значениях переменных X₁=A₁, X₂=A₂, …, X_n=A_n. Логическая формула, истинностные значения которой равны И (Л) при любых значениях переменных называется тождественно истинной или тавтологией (тождественно ложной или противоречием). Тот факт, что логическая формула F является тавтологией, записывается следующим образом: |=F.

Две логические формулы F₁ и F₂ с одним и тем же упорядоченным набором переменных называют равносильными и пишут F₁F₂ или F₁F₂, если истинностные значения этих логических формул совпадают при любых конкретных значениях переменных.

Заметим, что слово «тавтология» происходит от греческого «tauto» – то же самое слово. Тавтологию называют ещё законом логики. Приведём примеры простейших тавтологий: X Х (закон исключенного третьего), (ХХ) (закон отрицания противоречия),   (закон двойного отрицания). Можно указать связь между понятиями тавтологии и равносильности логических формул: логические формулы F₁ и F₂ равносильны тогда, и только тогда, когда формула F₁F₂ является тавтологией.

Пример 2. Установим следующие равносильности логических формул с переменными Х и Y:

, (1)

, (2)

(ХY)  ((ХY)(YХ)). (3)

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

|X|	|Y|			|XY|
и	и	л	л	и	и	Л	л
и	л	л	и	л	л	И	и
л	и	и	л	и	и	Л	л
л	л	и	и	и	и	Л	л

Сравнивая содержание 5-ого и 6-ого, 7-ого и 8-ого столбцов, делаем вывод об истинности равносильностей (1) и (2). Аналогично доказывается равносильность (3).

Пример 3. Установить следующие равносильности логических формул, где Х, Y, Z – высказывательные переменные:

; (4)

; (5)

; (6)

. (7)

Решение. Ограничимся доказательством равносильности (6), остальные равносильности устанавливаются аналогично. С этой целью составим таблицы истинности логических формул, записанных в левой и правой частях равносильности (6):

Х	Y	Z			ХY
и	и	и	л	л	И	л	л	и
и	и	л	л	и	И	л	л	и
и	л	и	и	л	л	и	л	л
и	л	л	и	и	л	и	л	л
л	и	и	л	л	и	л	л	и
л	и	л	л	и	и	л	л	и
л	л	и	и	л	и	л	л	и
л	л	л	и	и	и	л	л	и

Сравнивая содержание 6-ого и 9-ого столбцов, делаем вывод о равносильности логических формул ХY и .

Теорема 1. Пусть Х, Y и Z – какие-либо высказывательные переменные. Тогда имеют место следующие равносильности логических формул:

1) ХY YХ; 1) ХY  YХ;

2) (ХY)ZХ(YZ); 2) (ХY)ZХ(YZ);

3) (ХY)Z(ХZ)(YZ); 3) (ХY)Z(ХZ)(YZ);

4) ХХХ и ХЛХ; 4) ХХХ и ХИХ;

5) ; 5) .

Доказательство теоремы провести самостоятельно (см. примеры 1,2).

Следует обратить внимание на далеко не случайное сходство формулировок этой теоремы и теоремы 1 из §2 главы 1.