Эквивалентность высказываний

 

С помощью таблиц истинности можно установить эквивалентность двух или нескольких высказываний.

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

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

Примеры решения задач

Пример 1

 

Утверждается, что высказывание А+В· С эквивалентно высказыванию (А+В)·(А+С).Проверить это утверждение.

Решение. Проверка ведется путем составления таблицы истинности.

А	В	С	В· С	А+В· С	А+В	А+С	(А+В)· (А+С)
0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

Сравнивая 5-ю и 8-ю колонки, убеждаемся, что все значения, получаемые по формуле А+В·С, совпадают со значениями, получаемыми по формуле (А+В)·(А+С), т. е. высказывания эквивалентны (равносильны). Одно может заменить другое.

Эквивалентные (равносильные) высказывания соединяют знаком º

 

А + В× Сº(А+В)· (А+С).

 

Отметим различие между эквивалентностью и эквиваленцией.

Эквиваленция является логической операцией, позволяющей по двум заданным высказываниям А и В построить новое А«В.

Эквивалентность же является отношением между двумя составными высказываниями, состоящим в том, что их значения истинности всегда одни и те же.

Пример 2

Эквивалентны ли высказывания:

        и     

Решение.

1	2	3	4	5	6	7	8	9	10
А	В	С
0	0	0	1	1	1	1	0	0	0
0	0	1	1	1	1	1	0	0	0
0	1	0	0	0	0	1	0	1	1
0	1	1	0	0	1	1	0	1	1
1	0	0	1	1	1	0	0	0	0
1	0	1	1	1	1	0	1	0	1
1	1	0	0	1	1	0	0	0	0
1	1	1	0	1	1	0	1	0	1

Вывод.

Высказывание () и высказывание () не эквивалентны.

Тавтология

 

Пусть дано высказывание А × А и необходимо составить таблицу истинности.

 

А		А×
1	0	0
0	1	0

Высказывание А ×  ложно, истинность его не зависит от истинности высказывания А.

 

Рассмотрим высказывание В+ .

В		В+
1	0	1
0	1	1

В этом случае высказывание В +  всегда истинно, независимо от истинности В.

 

 

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

Различают тождественно-истинные и тождественно-ложные высказывания.

Если высказывание истинно при всех значениях входящих в него переменных, то такое высказывание называется тождественно истинным или тавтологией (обозначается константой 1)

Если высказывание ложно при всех значениях входящих в него переменных, то такое высказывание называется тождественно ложным (обозначается константой 0)

 

В формулах каждое тождественно-истинное высказывание заменяется 1, а тождественно-ложное – 0. Закон исключенного третьего. A× º0                         В+ º1

Примеры решения задач

Пример 1

Докажите тавтологию (XÙY)®(XÚY).

Решение

X	Y	XÙY	XÚY	(XÙY)®(XÚY)
0	0	0	0	1
0	1	0	1	1
1	0	0	1	1
1	1	1	1	1

Пример 2

Докажите тавтологию ((X®Y)Ù(Y®Z))®(X®Z).

 

Решение

                                                    F1               F2           F3

X	Y	Z	X®Y	Y®Z	X®Z	F1ÙF2	(F1ÙF2) ®F3
0	0	0	1	1	1	1	1
0	0	1	1	1	1	1	1
0	1	0	1	0	1	0	1
0	1	1	1	1	1	1	1
1	0	0	0	1	0	0	1
1	0	1	0	1	1	0	1
1	1	0	1	0	0	0	1
1	1	1	1	1	1	1	1

Вывод. Высказывание ((X®Y)Ù(Y®Z))®(X®Z) является тавтологий (тождественно-истинное высказывание).

Пример 3

Установить является ли данное высказывание тавтологией.

A	B	AÙB
0	0	0	1	1	1	1	1
0	1	0	1	1	0	1	1
1	0	0	1	0	1	1	1
1	1	1	0	0	0	0	1

Вывод. Высказывание  является тавтологией

Классификация высказываний

· тавтологии (тождественно истинные);

· тождественно ложные;

· эквивалентные.

 

Пример. Из простых высказываний: “Виктор хороший пловец” – А; “Виктор хорошо ныряет” – В; “Виктор хорошо поет” – С, составлено сложное высказывание, формула которого имеет вид: X=(AÚC)Ù(AÚB). Установить, эквивалентно ли высказывание Х высказыванию: “Виктор – хороший пловец и Виктор хорошо поет”.

Решение. Y=AÙC

1	2	3	4	5	6	7
А	В	С	AÚC	AÚB	X	Y=AÙC
0	0	0	0	0	0	0
0	0	1	1	0	0	0
0	1	0	0	1	0	0
0	1	1	1	1	1	0
1	0	0	1	1	1	0
1	0	1	1	1	1	1
1	1	0	1	1	1	0
1	1	1	1	1	1	1

Вывод. Высказывание X не эквивалентно высказыванию Y.

СДНФ и СКНФ

 

На практике при конструировании различных электронных устройств часто возникает задача – от таблицы истинности перейти к формуле, чтобы на ее основе построить функциональную схему. Переменные структурной формулы соответствуют входам функциональной схемы. Значения переменных в таблице истинности соответствуют значениям входов функциональной схемы.

Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые.

Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые.

Всякую дизъюнкцию элементарных конъюнкций назовем дизъюнктивной нормальной формой (ДНФ).

Всякую конъюнкцию элементарных дизъюнкций назовем конъюнктивной нормальной формой (КНФ).

Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно, с отрицанием).

Совершенной конъюнктивной нормальной формой (СКНФ) называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все дизъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно, с отрицанием).