§ 4. Равносильность формул

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

Например, формула ¬x∨y равносильна формуле x ⇒ y, в чем легко убедиться с помощью таблиц истинности:

В этих таблицах результирующие столбцы совпадают, т.е. при одинаковых значениях переменных x и y значения формул ¬x∨y и x⇒y равны, следовательно, эти формулы равносильны. Далее, формула x∨x&y равносильна x. Действительно, имеем следующую таблицу:

Также, очевидно, x∨¬x равносильно y∨¬y.

При определении равносильности двух формул не обязательно предполагать, что они содержат одни и те же переменные.

Высказывание «А равносильно В» будем обозначать следующим образом: А ~ B.

Пусть А, В, C - произвольные формулы. Отношение равносильности формул, как легко видеть, обладает следующими свойствами:

• рефлексивностью: А ~ А;
• симметричностью: если А ~ В, то В ~ А;
• транзитивностью: если А ~ В и В ~ C, то А ~ C.

Следовательно, отношение равносильности является отношением эквивалентности на множестве формул и разбивает множество формул на непересекающиеся классы. В каждый из классов попадают равносильные между собой формулы.

Формула, тождественно равная единице, называется тавтологией.

Примером тавтологии является формула x∨¬x, в чем легко убедиться, составив таблицу истинности. Другие примеры тавтологий: x⇒x, (x≡y)≡ (y≡x).

Формула, тождественно равная нулю, называется противоречием.

Примеры противоречий: x&¬x, ¬(x⇒x), x≡¬x.

Очевидно, что формула А является тавтологией тогда и только тогда, когда ¬А есть противоречие.

Тавтологию будем обозначать через Т, а противоречие - через П.

Легко доказать следующую теорему.

Теорема 3.1. Если А есть тавтология, содержащая переменные x1, x2,..., xn, и В получается из А подстановкой в А произвольных формул А1, А2,... Аn вместо переменных x1, x2,..., xn соответственно, то В есть тавтология, т.е. подстановка в тавтологию приводит к тавтологии.

Формула называется выполнимой, если она принимает значения 1 хотя бы для одной совокупности значений переменных, в нее входящих.

Например, x&y является выполнимой формулой, так как принимает значения 1, когда x=1 и y=1, а формула x&¬x не будет выполнимой, так как всегда равна нулю.

Очевидно, что формула А выполнима тогда и только тогда, когда А не является противоречием.

Докажем следующую теорему.

Теорема 3.2. Формулы А и В равносильны тогда и только тогда, когда А≡В является тавтологией.

Доказательство. Необходимость. Пусть А и В равносильны, следовательно, они при каждой совокупности значений всех переменных, входящих в них, принимают одинаковые значения, тогда по определению операции ≡ формула А≡В всегда принимает значение 1, т.е. является тавтологией.

Достаточность. Пусть А≡В тавтология, т.е. принимает всегда значение 1. Это означает, что А и В имеют всегда одинаковые значения, т.е. они равносильны. Теорема доказана.