Равносильность логических операций.

Одна функция может иметь множество реализаций над данным базисом (т. е. ее можно записать с помощью различных формул). Формулы, реализующие одну и ту же функцию, называют равносильными. Обозначают .

ПРИМЕР.

Пусть , . Доказать, что .

Равносильность двух формул можно доказать с помощью таблиц истинности. Формулы равносильны, если их значения истинности совпадают на любом наборе значений истинности, входящих в них переменных.

 

Таблица истинности для формулы А.

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

 

Тот факт, что равносильность формул логики высказываний можно проверить непосредственно, связан с тем, что переменные, входящие в формулу могут принимать конечное число значений (2 ⁿ).

Для логики имеют место следующие равносильности (рассмотрим только формулы, которые содержат знаки ):

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.

Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.

В выражении присутствует импликация. Сначала преобразуем импликацию .

Воспользуемся правилом де Моргана, затем законом двойного отрицания, затем раскроем скобки.

Применим закон идемпотенции и перегруппируем логические слагаемые.

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

Воспользуемся операцией с константами.

Таким образом,