Основные законы алгебры логики

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

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

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

А = . Двойное отрицание исключает отрицание.

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

А v B = B v A; — для логического сложения:

A & B = B & A. — для логического умножения:

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

В обычной алгебре a + b = b + a, a v b = b v a.

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

(A v B) v C = A v (B v C) — для логического сложения:

(A & B)& C = A &(B & C)— для логического умножения:

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

В обычной алгебре:

(a + b) + c = a + (b + c) = a + b + c,

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

(A v B)&C = (A&C) v (B&C); — для логического сложения

(A & B) v C = (A v C)&(B v C). — для логического умножения:

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

В обычной алгебре:

(a + b) * c = a * c + b * c.

5. Закон общей инверсии (законы де Моргана):

= & ; — для логического сложения

= v — для логического умножения:

6. Закон идемпотентности (от латинских слов idem — тот же самый и potens —сильный; дословно — равносильный):

A v A = A; — для логического сложения:

A & A = A. — для логического умножения

Закон означает отсутствие показателей степени.

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

A v 1 = 1, A v 0 = A; — для логического сложения:

A &1 = A, A &0 = 0. — для логического умножения:

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

A & = 0.

Невозможно, чтобы противоречащие высказывания были одновременно истинными.

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

A v = 1.

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

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

A v (A & B) = A; — для логического сложения:

A &(A v B) = A. — для логического умножения

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

(A & B) v ( & B) = B; — для логического сложения:

(A v B)&( v B) = B. — для логического умножения:

12. Закон контрапозиции (правило перевертывания):

(A Û B) = (B Û A).

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

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