преобразования логических выражений
Логические выражения называются равносильными, если их истинностные значения совпадают при любых значениях, входящих в них логических переменных. В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений. Приведем соотношения, отражающие эти законы.
1. Закон двойного отрицания:
А
= 
. Двойное отрицание исключает отрицание.
2. Переместительный (коммутативный) закон:
для логического сложения: А к B = B к A;
для логического умножения: A&B = B&A.
Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.
В обычной алгебре a + b = b + a, a Д b = b Д a.
3. Сочетательный (ассоциативный) закон:
для логического сложения: (A к B) к C = A к (B к C);
для логического умножения: (A&B)&C = A&(B&C).
При одинаковых знаках скобки можно ставить произвольно или вообще опускать.
В обычной алгебре: (a + b) + c = a + (b + c) = a + b + c,
а Д (b Д c) = a Д (b Д c) = a Д b Д c.
4. Распределительный (дистрибутивный) закон:
для логического сложения: (A к B)&C = (A&C) к (B&C);
для логического умножения: (A&B) к C = (A к C)&(B к C).
Определяет правило выноса общего высказывания за скобку.
В обычной алгебре: (a + b) Д c = a Д c + b Д c.
5. Закон общей инверсии (законы де Моргана):
для логического сложения
= 
&
;
для логического умножения:
= к
6. Закон идемпотентности ( от латинских слов idem тот же самый и potens сильный; дословно равносильный):
для логического сложения: A к A = A;
для логического умножения: A&A = A.
Закон означает отсутствие показателей степени.
7. Законы исключения констант:
для логического сложения: A к 1 = 1, A к 0 = A;
для логического умножения: A&1 = A, A&0 = 0.
8.
Закон противоречия:
A&
=
0.
Невозможно, чтобы противоречащие высказывания были одновременно истинными.
9. Закон исключения третьего:
A
к =
1.
Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе ложно, третьего не дано.
10. Закон поглощения:
для логического сложения: A к (A&B) = A;
для логического умножения: A&(A к B) = A.
11. Закон исключения (склеивания):
для логического сложения: (A&B)
к (
&B)
= B;
для логического умножения: (A
к
B)&( к
B) = B.
12. Закон контрапозиции (правило перевертывания): (A л B) = (Bл A).
Справедливость приведенных законов можно доказать табличным способом: выписать все наборы значений А и В, вычислить на них значения левой и правой частей доказываемого выражения и убедиться, что результирующие столбцы совпадут.
Пример.
Найдите X, если
к 
=
В.
Для преобразования левой части равенства последовательно воспользуемся законом де Моргана для логического сложения и законом двойного отрицания:
( 
& 
)
к ( &A)
Согласно распределительному закону для логического сложения:
&( к
A)
Согласно закону исключения третьего и закона исключения констант:
&1
=
Полученную левую часть приравняем правой:
=
В
Окончательно получим, что X = 
.
Пример 2.
Упростите логическое выражение (A
к
B
к
C)& 
Правильность упрощения проверьте с помощью таблиц истинности для исходного и полученного логического выражения.
Согласно закону общей инверсии для логического сложения (первому закону Моргана) и закону двойного отрицания:
(A
к
B
к C)& 
=
(A
к B
к
C)&( &B& 
)
Согласно распределительному (дистрибутивному) закону для логического сложения:
(A
к B
к
C)&(
&B&
)
= (A&
)
к (B&
)
к (C&
)
к (A&B)
к (B&B)
к (C&B)
к (A&
)
к (B&
)
к (C&
)
Согласно закона противоречия: (A& )
= 0; (C& )
= 0
Согласно закона идемпотентности (B&B) = B
Подставляем значения и, используя переместительный (коммутативный) закон и группируя слагаемые, получаем:
0 к (A&B)
к ( &B)
к B
к (C&B)
к ( &B)
к (C& )
к (A& )
к 0
Согласно закона исключения (склеивания)
(A&B)
к ( &B)
= B
(C&B)
к ( &B)
= B
Подставляем значения и получаем:
0 к
B
к B
к
B
к (C& )
к (A& )
к 0
Согласно закона исключения констант для логического сложения и закона идемпотентности:
0 к B к 0 к B к B = B
Подставляем значения и получаем:
B
к (C& )
к (A& )
Согласно распределительному (дистрибутивному) закону для логического умножения:
(C& )
к (A& )
= (C
к A)&(C
к
)&( к
A)&( к
)
Согласно закона исключения третьего: (C
к
)
= 1 ( к
A) = 1
Подставляем значения и окончательно получаем: B&
&
.
