Раздел 2. Логическая равносильность формул. Нормальные формы для формул алгебры высказываний

2.1. Отношение равносильности

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

В логике говорят, что два предложения равносильны, если они одновременно истинны, либо одновременно ложны. Слово «одновременно» в этой фразе неоднозначно. Так, для предложений «Завтра будет вторник» и «Вчера было воскресенье» это слово имеет буквальный смысл: в понедельник они оба истинны, а в остальные дни недели – оба ложны. Для уравнений «х = 2» и «2х = 4» «одновременно» означает «при одних и тех же значениях переменной». Прогнозы «Завтра будет дождь» и «Неверно, что завтра не будет дождя» одновременно подтвердятся (окажутся истинными) либо не подтвердятся (окажутся ложными). В сущности, это один и тот же прогноз, выраженный в двух разных формах, которые можно представить формулами Х и . Эти формулы одновременно принимают значение «истина» либо значение «ложь». Для проверки достаточно составить таблицу истинности:

Х
1	0	1
0	1	0

Видим, что значения истинности в первом и последнем столбцах совпадают. Такие формулы, как и соответствующие им предложения, естественно считать равносильными.

Формулы F₁ и F₂ называются равносильными, если их эквиваленция – тавтология.

Равносильность двух формул записывается так: (читается: формулаF₁ равносильна формуле F₂).

Проверить, равносильны ли формулы, можно тремя способами: 1) составить их эквиваленцию и с помощью таблицы истинности проверить, не является ли она тавтологией; 2) для каждой формулы составить таблицу истинности и сравнить итоговые результаты; если в итоговых столбцах при одинаковых наборах значений переменных значения истинности обеих формул будут равны, то формулы являются равносильными; 3) с помощью равносильных преобразований.

Пример 2.1: Выяснить, являются ли формулы равносильными: 1) ,; 2),.

Решение.

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

Составим эквиваленцию формул: . Полученная формула содержит две различные переменные (А и В) и 6 операций: 1) ; 2); 3); 4); 5); 6). Значит, в соответствующей таблице истинности будет 5 строк и 8 столбцов:

А	В
1	1	0	0	0	1	0	1
1	0	0	1	1	0	1	1
0	1	1	0	1	0	1	1
0	0	1	1	1	0	1	1

Из итогового столбца таблицы истинности видно, что составленная эквиваленция является тавтологией и, значит, .

2) Для того чтобы выяснить являются ли формулы иравносильными, используем второй способ, то есть составим для каждой из формул таблицу истинности и сравним итоговые столбцы. (Замечание. Для того чтобы эффективно использовать второй способ, необходимо, чтобы все составленные таблицы истинности начинались одинаково, то есть наборы значений переменных были одинаковы в соответствующих строках.)

В формуле две различные переменные и 2 операции, значит, в соответствующей таблице истинности 5 строк и 4 столбца:

А	В
1	1	1	0
1	0	0	1
0	1	1	0
0	0	1	0

В формуле две различные переменные и 3 операции, значит, в соответствующей таблице истинности 5 строк и 5 столбцов:

А	В
1	1	0	0	1
1	0	0	1	1
0	1	1	0	0
0	0	1	1	1

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

Выражение не является формулой (так как символ «» не относится к какой-либо логической операции). Оно выражаетотношение между формулами (также как равенство между числами, параллельность между прямыми и т.п.).

Справедлива теорема о свойствах отношения равносильности:

Теорема 2.1. Отношение равносильности между формулами алгебры высказываний:

1) рефлексивно: ;

2) симметрично: если , то;

3) транзитивно: если и, то.