Правила преобразования логических выражений
с помощью законов логики
Если логическое выражение содержит большое число операций, то составлять для него таблицу истинности достаточно сложно, так как приходится перебирать большое количество вариантов. В таких случаях формулы удобно привести к нормальной форме.
Формула имеет нормальную форму, если в ней отсутствуют знаки эквиваленции, импликации, двойного отрицания, при этом знаки отрицания находятся только при логических переменных.
Для приведения формулы к нормальной форме используют законы логики и правила логических преобразований.
Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).
Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул:
Пример 1 Упростить логическое выражение 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. Пример 2 Упростить логическое выражение 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. |
Упражнение 1
Упростите логические выражения, используя законы логики.
F1=A&Сv¬A&С
F2=¬Av¬Bv¬СvAvBvС
F3=¬((А&В)v¬(А&В))
F4=¬А&¬(¬ВvА)
Ответы к упражнению 1
F1=A&Сv¬A&С =С&(Аv¬A)= С&1 =С.
F2=¬Av¬Bv¬СvAvBvС=(¬AvA)v(¬BvB)v(¬СvС)=1v1v1=1.
F3=¬((А&В)v¬(А&В))= ¬(А&В)&¬(¬(А&В)) =(¬Av¬B)&А&В=¬A&А&Вv¬В&А&В=0&Вv0&А=0v0=0.
F4=¬А&¬(¬ВvА)=¬А&В&¬А=¬А&В.