| [ следующий ] [ начало главы ] [ предыдущий ] | [ содержание ] |
5.11. Как упростить логическую формулу?
Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определённому виду путем использования основных законов алгебры логики.
| Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных. |
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).
Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул:
1) 
(законы алгебры логики применяются в
следующей последовательности: правило де
Моргана, сочетательный закон, правило
операций переменной с её инверсией и
правило операций с константами);
2) 
(применяется правило де Моргана, выносится
за скобки общий множитель, используется
правило операций переменной с её инверсией);
3) 
(повторяется второй сомножитель,
что разрешено законом идемпотенции; затем
комбинируются два первых и два последних
сомножителя и используется закон
склеивания);
4) 
(вводится вспомогательный логический
сомножитель (
); затем
комбинируются два крайних и два средних
логических слагаемых и используется закон
поглощения);
5) 
(сначала добиваемся, чтобы знак
отрицания стоял только перед отдельными
переменными, а не перед их комбинациями, для
этого дважды применяем правило де Моргана;
затем используем закон двойного отрицания);
6) 
(выносятся за скобки общие множители;
применяется правило операций с константами);
7) 
(к отрицаниям неэлементарных формул
применяется правило де Моргана;
используются законы двойного отрицания и
склеивания);
8) 
(общий множитель x выносится за скобки,
комбинируются слагаемые в скобках — первое
с третьим и второе с четвертым, к дизъюнкции
применяется правило операции
переменной с её инверсией);
9) 
(используются распределительный закон для
дизъюнкции, правило операции переменной с
ее инверсией, правило операций с
константами, переместительный закон и
распределительный закон для конъюнкции);
10) 
(используются правило де Моргана, закон
двойного отрицания и закон поглощения).
Из этих примеров видно, что при упрощении логических формул не всегда очевидно, какой из законов алгебры логики следует применить на том или ином шаге. Навыки приходят с опытом.
