Правила преобразования логических выражений

с помощью законов логики

    Если логическое выражение содержит большое число операций, то составлять для него таблицу истинности достаточно сложно, так как приходится перебирать большое количество вариантов. В таких случаях формулы удобно привести к нормальной форме.

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

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

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

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

    

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

Пример 8 Упростить логическое выражение   F=(¬AvB)&¬(A&B). Используя закон де Моргана, получим:       (¬AvB)&¬(A&B)=(¬AvB)&(¬Av¬B). Применим правило дистрибутивности, т.е.вынесем общий множитель за скобки:       (¬AvB)&(¬Av¬B)=¬Av(B&¬B). По закону противоречия во второй скобке получаем:       ¬Av(B&¬B)=¬Av0. Применяя свойства констант, получим:       ¬Av0=¬A. Таким образом, F=(¬AvB)&¬(A&B)=¬A.    Пример 9 Упростить логическое выражение   F=(X=>Y)v(Y=>X).  Используя закон де Моргана, получим:    (X=>Y)v(Y=>X)=(¬XvY)v(¬YvX). Используя правило ассоциативности, перегруппируем слагаемые:    (¬XvY)v(¬YvX)=(¬XvX)v(¬YvY). По закону исключения третьего получим:    (¬XvX)v(¬YvY)=1v1=1. Таким образом, F=(X=>Y)v(Y=>X)=1.

 

 Упражнение 14

 Упростите логические выражения, используя законы логики.

    F₁=¬(A&B)v¬(ВvС)

    F₂=A&Сv¬A&С

    F₃=¬Av¬Bv¬СvAvBvС

    F₄=¬((А&В)v¬(А&В))

    F₅=¬А&¬(¬ВvА)

                                                       Проверьте себя (эталон ответов)