Г. И. Анкудинов - Математическая логика и теория алгоритмов

коммутативности:
(P1 & P2) ↔ (P2 & P1),

(1.8)

(P1 \/ P2) ↔ (P2 \/ P1).

(1.9)

Законы ассоциативности:
[(P1 & P2) & P3] ↔ [P1 & (P2 & P3)],

(1.10)

[(P1 \/ P2) \/ P3] ↔ [P1 \/ (P2 \/ P3)].

(1.11)

Законы дистрибутивности:
[(P1 \/ P2) & P3] ↔ [(P1 & P3) \/ (P2 & P3)],

(1.12)

[(P1&P2)\/P3]↔[(P1\/P3)&(P2\/P3)].

(1.13)

Закон де-Моргана:
⎤(P1 & P2) ↔ (⎯P1 \/⎯P2),

(1.14)

⎤(P1 \/ P2) ↔ (⎯P1 &⎯P2).

(1.15)

Следующие законы
эквивалентности.
Закон тождества:

выражают

свойства

P → P.

импликации

и

(1.16)

Закон контрапозиции:
(P1 → P2) ↔ (⎯P2 →⎯P1)).

(1.17)

Правило цепного заключения:
[(P1 → P2) & (P2 → P3)] → (P1 → P3).
91

(1.18)

Законы рефлексивности, симметричности и транзитивности:
P ↔ P,

(1.19)

(P1 ↔ P2) ↔ (P2 ↔ P1),

(1.20)

[(P1 ↔ P2) & (P2 ↔ P3)] → (P1 ↔ P3).

(1.21)

Закон противоположности:
(P1↔P2)↔(⎯P1↔⎯P2).

(1.22)

Следующие законы выражают зависимости между основными
логическими операциями.
Выражение конъюнкции через дизъюнкцию и отрицание и
дизъюнкции через конъюнкцию и отрицание:
(P1 & P2) ↔ ⎤(⎯P1 \/⎯P2),

(1.23)

(P1 \/ P2) ↔⎤ (⎯P1 & ⎯P2).

(1.24)

Выражение эквивалентности через конъюнкцию и импликацию:
(P1 ↔ P2) ↔ [(P1 → P2) & (P2 → P1)].

(1.25)

Выражение импликации через конъюнкцию и отрицание и через
дизъюнкцию и отрицание:
(P1 → P2) ↔ ⎤(P1 & ⎯P2),

(1.26)

(P1 → P2) ↔ (⎯P1 \/ P2).

(1.27)

Выражение конъюнкции и дизъюнкции через отрицание и
импликацию:
(P1 & P2) ↔ ⎤(P1 →⎯P2),

(1.28)

(P1 \/ P2) ↔ (⎯P1 → P2).

(1.29)

92

1.4. Равносильные формулы
Две формулы исчисления высказываний Ф1(P1,...,PN) и
Ф2(P1,...PN) называются равносильными, если они принимают
одинаковое значение для любых значений P1,...PN. Две равносильные
формулы имеют одну и ту же таблицу истинности и, наоборот,
формулы, имеющие одну и ту же таблицу истинности, равносильны.
Условие равносильности формул выражает
Теорема 1.1. Формулы Ф1(P1,...PN) и Ф2(P1,...PN) равносильны
тогда и только тогда, когда их эквивалентность
Ф1(P1,...PN) ↔ Ф2(P1,...PN)
является тавтологией.
Отношение равносильности обозначается символом
Например, из законов (1.12) и (1.13) следуют равносильности:
(P1 \/ P2) & P3 ⇔ (P1 & P3) \/ (P2 & P3),
(P1 & P2) \/ P3 ⇔ (P1 \/ P3) & (P2 \/ P3).

⇔.

(1.30)
(1.31)

Из законов (1.14) и (1.15) следуют равносильности:
(1.32)
(1.33)

⎤(P1 & P2) ⇔⎯P1 \/⎯P2,
⎤(P1 \/ P2) ⇔⎯P1 &⎯P2.
Из тавтологий (1.23,...,1.29) следуют равносильности:
P1 & P2 ⇔ ⎤(⎯P1 \/⎯P2),
P1 \/ P2 ⇔ ⎤(⎯P1 &⎯P2),
P1 ↔ P2 ⇔ (P1 → P2) & (P2 → P1),
P1 → P2 ⇔ ⎤(P1 &⎯P2),
P1 → P2 ⇔ ⎯P1 \/ P2,
P1 & P2 ⇔ ⎤(P1 →⎯P2),
P1 \/ P2 ⇔ ⎯P1 → P2.
Полезно также использовать следующие
логическими константами:
P \/ 1 ⇔ 1,

93

(1.34)
(1.35)
(1.36)
(1.37)
(1.38)
(1.39)
(1.40)
равносильности

с

(1.41)

P \/ 0 ⇔ P,
P & 1 ⇔ P,
P & 0 ⇔ 0.

(1.42)
(1.43)
(1.44)

Для упрощения формул исчисления высказываний полезны
следующие равносильности, называемые правилами склеивания:
(P1 & P2) \/ (P1 &⎯P2) ⇔ P1,
(P1 \/ P2) & (P1 \/⎯P2) ⇔ P1;

(1.45)
(1.46)

правила поглощения:
P1 \/ (P1 & P2) ⇔ P1,
P1 & (P1 \/ P2) ⇔ P1;

(1.47)
(1.48)

формулы Блейка - Порецкого:
(P1&P2)\/(P3&⎯P2) ⇔ (P1&P2)\/(P3&⎯P2)\/(P1&P3),
(P1\/P2) & (P3\/⎯P2) ⇔ (P1\/P2)&(P3\/⎯P2)&(P1\/P3)

(1.49)
(1.50)

и формулы равносильности:
P1 \/ (⎯P1 & P2) ⇔ P1 \/ P2,
P1 & (⎯P1 \/ P2) ⇔ P1 & P2,
P &⎯P ⇔ 0,
P \/⎯P ⇔ 1,
P & P ⇔ P,
P \/ P ⇔ P.
⎤⎯P ⇔ P.

(1.51)
(1.52)
(1.53)
(1.54)
(1.55)
(1.56)
(1.57)

Часто требуется упростить формулу исчисления высказываний,
т.е. получить формулу равносильную исходной, но содержащую по
возможности меньшее число пропозициональных букв и символов
логических операций. Например, дана формула
(X1\/X2\/X3)&(X1\/⎯X2\/X3)&(X1\/⎯X3)&(X2\/X3\/X4)&
(X1\/⎯X2\/⎯X3)& (X1\/ X3\/⎯X4)&(X1\/X2).

94

Применим к первым двум подформулам (X1\/X2\/X3)&(X1\/⎯X2\/X3)
равносильность (1.46), считая P1 = X1\/X3 и P2 = X2, тогда их можно
заменить одной подформулой (X1\/X3), что дает более простую
формулу, равносильную исходной:
(X1\/X3)&(X1\/⎯X3)(X2\/X3\/X4)&(X1\/⎯X2\/⎯X3)&(X1\/X3\/⎯X4)&(X1\/X2).
К подформулам (X1\/X3) и (X1 \/⎯X3) снова применим равносильность
(1.46) и получаем еще более простую формулу, равносильную
исходной:
X1& (X2\/X3\/X4)&(X1\/⎯X2\/⎯X3)&(X1\/X3\/⎯X4)& (X1\/X2).
Коммутативность конъюнкции позволяет переписать последнее
выражение, а равносильность (1.48) – выполнить дальнейшее
упрощение
X1&(X1\/⎯X2\/⎯X3)&(X1\/X3\/⎯X4)& (X1\/X2) & (X2\/X3\/X4)=
X1& (X2\/X3\/X4).
Если в формуле используются операции импликации и
эквивалентности, то, как правило, их следует преобразовать с
помощью --">