Алгебра Логики

ЗАКОНЫ ЛОГИКИ И ПРАВИЛА ПРЕОБРАЗОВАНИЯ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ

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

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

    Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение «истина»:
        A v ¬A = 1

    Закон двойного отрицания. Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание:
         ¬¬A = A

    Законы де Моргана.
        ¬(AvB) = ¬A & ¬B
        ¬(A&B) = ¬A v ¬B

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

    Закон коммутативности. В обычной алгебре слагаемые и множители можно менять местами. В алгебре высказываний можно менять местами логические переменные при операциях логического умножения и логического сложения:
        Логическое умножение: A&B = B&A
        Логическое сложение: AvB = BvA

    Закон ассоциативности. Если в логическом выражении используются только операция логического умножения или только операция логического сложения, то можно пренебрегать скобками или произвольно их расставлять:
        Логическое умножение: (A&B)&C = A&(B&C)
        Логическое сложение: (AvB)vC = Av(BvC)

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

Дистрибутивность умножения относительно сложения
        аb + ас = а(b+с) — в алгебре
        (А&В)v(А&С)=А&{ВvС)

Дистрибутивность сложения относительно умножения
        (А v В) & (А v С) = А v {В & C)

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

Воспользуемся законом дистрибутивности и вынесем за скобки A:
        (А & В) V (A & В) = А & (В v В).

По закону исключенного третьего В v ¬В =1, следовательно:
         А& (ВvВ) « А&1 = А.