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

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

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

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

Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул.

1.

В этом примере применены законы противоречия (11) и исключения констант (7).

2.

В этом примере применён закон противоречия (11) и определение операции «Логического сложения».

3.

В примере 3 применены законы противоречия (11) и исключения констант (7).

4.

В примере (4) применён закон противоречия (11) и определение операции «Логического умножения».

5.

Законы алгебры логики в этом примере применяются в следующей последовательности: правило де Моргана (14), сочетательный закон (6), закон противоречия (11) и правило операций с константами (7).

6.

Законы алгебры логики в этом примере применяется в таком порядке: правило де Моргана (14), выносится за скобки общий множитель (закон дистрибутивности (8)), закон противоречия (11).

7.

В этом примере к отрицаниям неэлементарных формул применяется правило де Моргана ((14) и (15)); сочетательный закон (6), используются законы двойного отрицания (13) и определение операции «Логического сложения».

Часто для упрощения логических выражений применяют следующие тождества:

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

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