Урок "Логические законы " 


 

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

логических выражений

 

 

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

 

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

 

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

 

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

 

 

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

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

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

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

 

А & ¬ A = 0

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

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

 

А \/ ¬ A = 1

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

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

¬ (¬ A) = A

 

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

 

¬(А & B) = ¬А \/ ¬B

¬(А \/ B) = ¬А & ¬B

 

 

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

 

Закон коммутативности

(переместительный)

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

 

А & В = В & А

А \/ В = А \/ В

 

Закон ассоциативности

(сочетательный)

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

(А & B) & С = А & (В & С)

(А \/ В) \/ С= А \/ (В \/ С)

Закон дистрибутивности

(распределительный)

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

(А&В) \/ (А&С) = А&(В\/С)

(А\/В) & (А\/С) = А \/ (В&С)

 

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

 

A & (A \/ B) = A

A \/ A & B = A

ØA & (A \/ B) = ØA & B

A \/ ØA & B = A \/ B

       

 

 

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

(А & B) v (А & ¬В).

Воспользуемся законом дистрибутивности и вынесем за скобки А:

(А & В) v (А & ¬В) = А & (В v ¬В).

По закону исключенного третьего В v В =1, следовательно:

А & (В v ¬В) = А & 1 = А.