 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Логические законы и правила преобразования логических выражений
|
|
Логические выражения называются равносильными, если их истинностные значения совпадают при любых значениях, входящих в них логических переменных.
В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений. Приведем соотношения, отражающие эти законы.
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).
Справедливость приведенных законов можно доказать табличным способом: выписать все наборы значений А и В, вычислить на них значения левой и правой частей доказываемого выражения и убедиться, что результирующие столбцы совпадут.
Пример 3.11. Найдите X, если 
Ú 
= В.
Для преобразования левой части равенства последовательно воспользуемся законом де Моргана для логического сложения и законом двойного отрицания:
(
& 
) Ú ( & A)
Согласно распределительному закону для логического сложения:
&( Ú A)
Согласно закону исключения третьего и закона исключения констант:
&1 =
Полученную левую часть приравняем правой:
= В
Окончательно получим, что X = 
.
Пример 3.12. Упростите логическое выражение (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 & & .
Дата публикования: 2015-09-17; Прочитано: 532 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
