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

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

Основные законы логики
А = А	– закон тождества
А & А = 0	– закон противоречия
А  А = 1	– закон исключения третьего
А = А	– закон двойного отрицания
Свойства констант
 0 = 1			1 = 0
А  0 = А			А & 0 = 0
А  1 = 1			А & 1 = А
Законы идемпотентности
А  А = А			А & А = А
Переместительный (коммутативный) закон
А  В = В  А			А & В = В & А
Сочетательный (ассоциативный) закон
А  ( В  С ) = ( А  В )  С			А & ( В & С )= ( А & В ) & С
Распределительный (дистрибутивный) закон
А  ( В & С ) = ( А  В ) & ( А  С )			А & ( В  С ) = ( А & В )  ( А & С )
Закон исключения (склеивания)
( А & В )  ( А & В ) = В			( А  В ) & ( А  В ) = В
Законы поглощения
А  ( А & В ) = А			А & ( А  В ) = А
Законы общей инверсии (законы де Моргана)
2-й закон инверсии			1-й закон инверсии
 ( А  В ) =  А &  В			 ( А & В ) =  А   В
Правила замены операции импликации
А  В =  А  В			А  В =  В   А
Закон контрапозиции (правило перевертывания)
А  В = В  А
Правила замены операции эквивалентности
А  В = ( А & В )  ( А & В )
А  В = ( А   В ) & ( А  В )
А  В = ( А  В ) & ( В  А )

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

Если высказывание истинно на всех значениях входящих в него переменных, то такое высказывание называется тождественно истинным или тавтологией (обозначается константой 1).

Если высказывание ложно на всех значениях входящих в него переменных, то такое высказывание называется тождественно ложным (обозначается константой 0).

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

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

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

Пример 2

















Преобразуем выражение , для этого применим к  правило де Моргана, получим , затем сочетательный закон ко всему выражению, получим ,  по закону противоречия даст 0,  упроститься по закону идемпотентности, применив к  свойство констант получим в результате 0..

Пример 3.















Преобразуем выражение , для этого к  применим правило де Моргана, получим , в  вынесем за скобки общий множитель и получим в скобках  по закону исключения третьего получим 1,  также представляет закон исключения третьего.

Пример 4.

































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