2015-05-12
761
В алгебре логики выполняются следующие основные законы, позволяющие производить тождественные преобразования логических выражений:
| Закон | Для ИЛИ | Для И |
| Переместительный |  |  |
| Сочетательный |  |  |
| Распределительный |  |  |
| Правила де Моргана |  |  |
| Идемпотенции |  |  |
| Поглощения |  |  |
| Склеивания |  |  |
| Операция переменной с ее инверсией |  |  |
| Операция с константами |  |  |
| Двойного отрицания |  |
Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул:
1) 
(законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами);
2) 
(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией);
3) 
(повторяется второй сомножитель, что разрешено законом идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания);
4) 
(вводится вспомогательный логический сомножитель (
); затем комбинируются два крайних и два средних логических слагаемых и используется закон поглощения);
5) 
(сначаладобиваемся, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого дважды применяем правило де Моргана; затем используем закон двойного отрицания);
6) 
(выносятся за скобки общие множители; применяется правило операций с константами);
7) 
(к отрицаниям неэлементарных формул применяется правило де Моргана; используются законы двойного отрицания и склеивания);
8) 
(общий множитель x выносится за скобки, комбинируются слагаемые в скобках — первое с третьим и второе с четвертым, к дизъюнкции 
применяется правило операции переменной с её инверсией);
9) 
(используются распределительный закон для дизъюнкции, правило операции переменной с ее инверсией, правило операций с константами, переместительный закон и распределительный закон для конъюнкции);
10) 
(используются правило де Моргана, закон двойного отрицания и закон поглощения).
Из этих примеров видно, что при упрощении логических формул не всегда очевидно, какой из законов алгебры логики следует применить на том или ином шаге. Навыки приходят с опытом.
