2020-04-12
195
Одна функция может иметь множество реализаций над данным базисом (т. е. ее можно записать с помощью различных формул). Формулы, реализующие одну и ту же функцию, называют равносильными. Обозначают 
.
ПРИМЕР.
Пусть 
, 
. Доказать, что .
Равносильность двух формул можно доказать с помощью таблиц истинности. Формулы равносильны, если их значения истинности совпадают на любом наборе значений истинности, входящих в них переменных.
Таблица истинности для формулы А.
| x | y | z | x~y | xz | A |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Таблица истинности для формулы B.
| x | y | z | 
| 
| xz | B |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 |
Тот факт, что равносильность формул логики высказываний можно проверить непосредственно, связан с тем, что переменные, входящие в формулу могут принимать конечное число значений (2n).
Для логики имеют место следующие равносильности (рассмотрим только формулы, которые содержат знаки 
):
1. Коммутативный
АÚВ 
ВÚА АВ=ВА
2. Ассоциативный
АÚ(ВÚС) (АÚВ) ÚС А(ВС)=(АВ)С
3. Дистрибутивный
АÚ(ВС) (АÚВ)(АÚС) А(ВÚС)=АВÚАС
4. Идемпотентности (Рефлективности)
АÚА А А·А А
5. Поглощения
АÚАВ А А(АÚВ) А
6. АÚ 0 А А· 0 = 0
7. АÚ1=1 А·1=А
8. АÚ 
=1 А× =0
9. Закон де Моргана
10. 
= 0 
= 1
11 Двойное отрицание
= А
12. А 
В 
ÚВ
13. А~В=А·ВÚ 
14. А 
В= ·ВÚА· 
15. А çВ = АÚВ = А·В
16. А ¯ В = 
= Ú
17. Закон склеивания. Закон склеивания базируется на понятии соседних конъюнкций. Соседними называются конъюнкции, отличающиеся представлением одной переменной.
(А^В) Ú ( ^B)=B (АÚВ) ^ ( ÚB)=B
18. Закон контрапозиции
(А 
В) ( ) ( ) (А В) (А 
) 
(B 
)
19. Закон Клавия
( А) А
20. Закон свертки
АÚ ^B AÚ B Ú A^ B Ú B
ПРИМЕРЫ. Упростить логическое выражение.
1. 
Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций:
Воспользуемся законом дистрибутивности и вынесем за скобки общий множитель, затем операцией переменной с ее инверсией.
Воспользуемся законом дистрибутивности и вынесем за скобки общий множитель, затем операцией переменной с ее инверсией, затем операцией с константами.
Таким образом, 
2. 
Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций. В выражении присутствуют два выражения в скобках, соединенных дизъюнкцией. Сначала преобразуем выражения в скобках.
В первой скобке воспользуемся законом дистрибутивности, во второй скобке – раскроем инверсию по правилу де Моргана и избавимся от инверсии по закону двойного отрицания.
Воспользуемся операцией переменной с ее инверсией.
Таким образом, 
3. 
Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций. В выражении присутствуют два выражения в скобках, соединенных конъюнкцией. Сначала преобразуем выражения в скобках.
Раскроем инверсию по правилу де Моргана, избавимся от инверсии по закону двойного отрицания.
Воспользуемся законом коммутативности и поменяем порядок логических сомножителей.
Применим закон склеивания 
Получим 
Воспользуемся законом дистрибутивности, затем операцией переменной с ее инверсией, затем операцией с константами.
Таким образом, 
4. 
Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.
В выражении присутствует импликация. Сначала преобразуем импликацию 
.
Воспользуемся правилом де Моргана, затем законом двойного отрицания, затем раскроем скобки.
Применим закон идемпотенции и перегруппируем логические слагаемые.
Воспользуемся законом дистрибутивности и вынесем за скобки общий логический множитель. 
Воспользуемся операцией с константами.
Таким образом, 
