Одна функция может иметь множество реализаций над данным базисом (т. е. ее можно записать с помощью различных формул). Формулы, реализующие одну и ту же функцию, называют равносильными. Обозначают .
ПРИМЕР.
Пусть , . Доказать, что .
Равносильность двух формул можно доказать с помощью таблиц истинности. Формулы равносильны, если их значения истинности совпадают на любом наборе значений истинности, входящих в них переменных.
Таблица истинности для формулы А.
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.
Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.
В выражении присутствует импликация. Сначала преобразуем импликацию .
Воспользуемся правилом де Моргана, затем законом двойного отрицания, затем раскроем скобки.
Применим закон идемпотенции и перегруппируем логические слагаемые.
Воспользуемся законом дистрибутивности и вынесем за скобки общий логический множитель.
Воспользуемся операцией с константами.
Таким образом,