Преобразования логических формул

Равносильные преобразования логических формул имеют то же

Назначение, что и преобразования формул в обычной алгебре. Они

Служат для упрощения формул или приведения их к определенному

Виду путем использования основных законов алгебры логики.

Глава 1. Вычислительные приборы и устройства...

Под упрощением формулы, не содержащей операции импликации

И эквиваленции, понимают равносильное преобразование, приводя-

Щее к формуле, которая либо содержит по сравнению с исходной

Меньшее число операций конъюнкции и дизъюнкции и не содержит

Отрицаний неэлементарных формул, либо содержит меньшее число

Вхождений переменных.

Некоторые преобразования логических формул похожи на пре-

Образования формул в обычной алгебре (вынесение общего множи-

Теля за скобки, использование переместительного и сочетательного

Законов и т. п.), тогда как другие преобразования основаны на

Свойствах, которыми не обладают операции обычной алгебры (ис-

Пользование распределительного закона для конъюнкции, свойств

Поглощения и склеивания, законы де Моргана и др.).

Приведем несколько примеров, иллюстрирующих методы, при-

меняемые при упрощении логических формул:

1) (xvy)л(xлy)=x/\yл(x/\y)=x/\xлyлy =

= 0 л у л _у =0 /\у = 0

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

ности: закон Де Моргана, сочетательный закон, правило конъ-

Юнкции переменной с ее инверсией и правило операций с кон-

Стантами);

2) x/\yvxvyvx=x/\y\/XAyvx =

= x/\(yvy)vx=xvx=l

(применяется правило де Моргана, выносится за скобки общий

Множитель, используется правило операций переменной с ее инвер-

Сией);

3) (х vy) л (xv у) л (xv у) =

(xv у) л (xv у)(х v у) л (х v у) = у л х

(повторяется второй сомножитель, что разрешено законом идемпо-

Тенции; затем комбинируются два первых и два последних сомно-