Упрощение логических выражений

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

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

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

Пример 1.

(законы алгебры логики применяются в следующей последовательности:
правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами);  

Пример 2.

(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией); 

Пример 3

 (повторяется второй сомножитель, что разрешено законом идемпотентности; затем комбинируются два первых и два последних сомножителя и используется закон склеивания); 

Пример 4 

(вводится вспомогательный логический сомножительзатем комбинируются два крайних и два средних логических слагаемых и используется закон поглощения);  

Пример 5

(сначала добиваемся, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого дважды применяем правило де Моргана; затем используем закон двойного отрицания); 

 

Пример 6

(выносятся за скобки общие множители; применяется правило операций с константами);  

 

Пример 7

(к отрицаниям неэлементарных формул применяется правило де Моргана; используются законы двойного отрицания и склеивания); 

 

Пример 8

(общий множитель x выносится за скобки, комбинируются слагаемые в скобках — первое с третьим и второе с четвертым, к дизъюнкции  применяется правило операции переменной с её инверсией).

  Из этих примеров видно, что при упрощении логических формул не всегда очевидно, какой из законов алгебры логики следует применить на том или ином шаге. Навыки приходят с опытом.