Главная

Учебник :
Глава 1
Глава 2
Глава 3
Глава 4
Глава 5
Глава 6

Тест

Глава 4

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

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

Закон тождества

Всякое высказывание тождественно самому себе.

А=А

Закон непротиворечия

Высказывание не может быть одновременно истинным и ложным. Если высказывание А - истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывание и его отрицания должно быть ложно.

А и не А =0

Закон исключения третьего

Высказывание може быть либо истинным либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания принимает значение истинна.

А или не А = 1

Закон двойного отрицания

Если дважды отрицаеть некоторое высказывание, то в результате мы получим исхходное высказывание.

не не А=А

Законы Моргана

не(А или В)= не А и не В
не(А и В)= не А или не В

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

Правило Комуникативности - при операция логического умножения и слоения перевенные можно менять местами.

Правило ассоциативности - если в выражении используются только операции логичческого умножения или логического сложения то можно пренебрегать скобками или произвольно расставлять переменные.

Правило дистрибьютивности - в алгебре высказываний можно выносить за скобки как общие множители так и общие слагаемые.

Как упростить логическую формулу?

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

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

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

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

2)
(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией);

3)
(повторяется второй сомножитель, что разрешено законом идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания);

4)
(вводится вспомогательный логический сомножитель (); затем комбинируются два крайних и два средних логических слагаемых и используется закон поглощения);

5)
(сначала добиваемся, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого дважды применяем правило де Моргана; затем используем закон двойного отрицания);

6)
(выносятся за скобки общие множители; применяется правило операций с константами);

Проверь себя сам