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

Примеры задач с решениями по этой теме Пройти тестирование по теме Контрольная по теме

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

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

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

Закон

Формулировка

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

Х = Х

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

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

 

X \/ ¬X = 1

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

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

 

X/\ ¬X = 0

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

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

¬¬X = X

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

5.      Переместительный (коммутативный) закон

X /\ Y = Y /\ X

X /\ Y = YX /\ 

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

6.      Сочетательный (ассоциативный) закон

(X \/Y) \/Z = X \/  (Y \/Z)

(X/\Y)/\Z=X/\(Y/\Z)

При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

5.      Распределительный (дистрибутивный) закон

(X /\ Y) \/ Z= (X /\ Z) \/ (Y /\ Z)

(X /\ Y) \/ Z =  (X \/ Z) /\ (Y \/ Z)

Определяет правило выноса общего высказывания за скобку.

7.      Закон общей инверсии Закон де Моргана

¬(X \/ Y) = ¬X /\ ¬Y

¬(X /\ Y) = ¬X \/ ¬Y

Закон общей инверсии.

           8.    Закон равносильности (идемпотентности)

A\/A= A;

A/\ A = A.

от латинских слов idem — тот же самый и potens —сильный

 

            9.      Законы исключения констант:

A\/ 1 = 1,     A\/ 0 = A;

A/\1 = A,     A/\0 = 0.

 

10.      Закон поглощения:

A\/ (A/\B) = A;

A/\ (A\/B) = A.

 

         11.  Закон исключения (склеивания):

(A/\B) \/ (¬A/\B) = B;

(A\/B)/\(¬A \/B) = B.

 

12.  Закон контрапозиции

(правило перевертывания):

(A<=>B) = (B<=>A).

 

13.  А => В = ¬A \/ В;

14.  ¬ (A=>B)=A/\B

 

      14.  А <=>В = (А /\ В) \/ (¬A /\ ¬B);

 

      15.  А <=>В = (¬A \/ В) /\ (А \/¬B).

 

 

 

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

      1)      (A/\B) \/ (A/\¬B) = A /\ (B \/ B)= A /\ 1 = A

      2)      ¬ (X \/ Y) /\ (X /\ ¬Y)

Законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами.

      ¬ (X \/ Y) /\ (X /\ ¬Y) = ¬ X /\ ¬Y /\ (X /\ ¬Y) = ¬ X /\ X/\¬Y /\¬Y= 0 ¬Y /\¬Y

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

      4)      ¬ X /\ Y \/ ¬ (X \/ Y) \/ X = ¬ X /\ Y \/ ¬ X /\ ¬Y \/ X= ¬ X /\ (Y \/ ¬Y) \/ X= ¬ X \/ X= 1