2.1.5. Равносильные формулы

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

Например, формула АВ равносильна формуле (АВ)(ВА).

Теорема. Для формулы А и В являются равносильными т. и т. т., когда АВ тавтология.

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

Перечислим важнейшие равносильности:

1.	ù ù А А	13.	Аù А 0
2.	АВ ВА	14.	А0 0
3.	АВ ВА	15.	А1 1
4.	(АВ)С А(ВС)	16.	1А А
5.	(АВ) С А(ВС)	17.	А1 1
6.	А(ВС) (АВ) (АС)	18.	А0 ù А
7.	А(ВС) (АВ) (АС)	19.	AB ù AB
8.	ù (АВ) ù В ù А	20.	АВ ( ù AB)( ù ВА)
9.	ù (АВ) ù Вù А	21.	АВ ABù Аù В
10.	АА А	22.	АВС (АВ)(АС)
11.	АА А	23.	АВС А(ВС)
12.	А0 А	24.	Аù ВВù А

Все эти равносильности вытекают из соответствующих тавтологий. По-другому убедиться в справедливости вышеприведенных (и других) равносильностей можно сравнив таблицы истинности их левой и правой частей. Кроме того, некоторые равносильности могут быть получены из других путем тождественных преобразований. Например, из 1 и 8 следует 9.

Действительно, в 8 заменим А и В на ù А и ù В. Получим ù( ùАùВ) º ù ù Аù ù В АВ, откуда ù ù ( ù Аù В) ù (АВ) ù Аù Вù (АВ) 9.

< Предыдущая		Следующая >