1.4Таблица основных логических тождеств. Двойственность. Вывод новых тождеств с помощью основных.

Результаты упражнений 5 вместе с замечаниями перед упражнениями 4 позволяют свести в таблицу сводку основных логических тождеств (эквивалентных формул):

закон двойного отрицания: ØØpÛp
закон замены импликации: (pÞq)ÛØpÚq.
законы сокращения
pÚTÛT; pÙTÛp	pÙFÛF; pÚFÛp
законы идемпотентности
pÚpÛp	pÙpÛp
Закон исключённого третьего
pÚØpÛТ	pÙØpÛ F
законы коммутативности
pÚqÛqÚp	pÙqÛqÙp
законы ассоциативности
(pÚq)ÚrÛpÚ(qÚr)	(pÙq)ÙrÛ pÙ(qÙr)
законы дистрибутивности
(pÚq)ÙrÛ(pÙr)Ú(qÙr)	(pÙq)ÚrÛ(pÚr)Ù(qÚr)
законы де Моргана
Ø(pÚq) ÛØp ÙØq	Ø(pÙq) ÛØp ÚØq
законы поглощения.
pÚ(pÙq) Ûp	pÙ(pÚq) Ûp

Таблица наглядно демонстрирует двойственность, характеризующую исчисление высказываний: если заменить в левой колонке таблицы значки Ù на Ú а истину на ложь и наоборот, то обнаружим полученное новое (верное) утверждение в правой колонке таблицы. Так что «учить» придётся только половину таблицы.

Но и запоминать специально эти тождества не придётся: мы просто применяем эту таблицу при упрощении логических выражений, имея её всегда под рукой, так что, в конце концов, она запомнится непроизвольно.

Проиллюстрируем на примере, как, применяя тождества из этого списка можно доказывать другие тождества. Докажем, что формула ((pÞq)Ù(qÞr))Þ(pÞr) является тавтологией (т.е. истинна при всех значениях переменных p, q, r.).

Читается эта логическая функция так: если из p следует q и из q следует r, то из p следует r. (свойство транзитивности импликации).

Сначала применим 2 ко всем внутренним импликациям:

((pq)(qr))(pr)

Теперь заменим внешнюю импликацию:

((pq)(qr))(pr)

К левой части дизъюнкции применяем 16 а в правой опускаем скобки:

(pq)(qr))pr Применяем 17 к каждой скобке:

pqqrpr Применяем 1:

pqqrpr Применяем 17: pp(Øpq); rrÚ(rq)

pqqrp(Øpq)rÚ(rq) Применяем 10 и 9:

pqØpqqr Úqrpr Применяем 13:

( pÚØp)ÙØq Ú qÙ(rÚr)Úpr Применяем 7:

ТÙØqÚqÙТÚpr Применяем 3:

ØqÚqÚpr Снова применяем 7:

ТÚpr и, наконец, дважды применяя 3, получим Т.

Упражнение 7

Доказать, что следующие логические функции являются тавтологиями:

1. (pq)(p q)

2. (pq)(q  p)

3. p(q(pÙq))

4. (pÞq) Þ((qÞr) Þ(pÞr))

5. (ØpÞØq)(qÞp)

6. pÞ(qÞp)

7. (pq)Þp

8. p(pq)

i) (pq)((pÙq)(ØpÙØq))

Обозначения. Помимо знаков «» и «» для эквивалентности используется ещё символ «». Также для конъюнкции используются символы “&”, “”. Таким образом, записи АВ; АВ и АВ означают одно и то же, а именно: А логически эквивалентно В. Точно так же конъюнкцию А и В можно записать как АВ, как А&В и как АВ.