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

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

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

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

А = .

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

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

— для логического сложения:

А Ú B = B Ú A;

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

A & B = B & A.

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

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

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

— для логического сложения:

(A Ú B) Ú C = A Ú (B Ú C);

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

(A & B)& C = A &(B & C).

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

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

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

а ´ (b ´ c) = a ´ (b ´ c) = a ´ b ´ c.

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

— для логического сложения:

(A Ú B)&C = (A&C) Ú (B&C);

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

(A & B) Ú C = (A Ú C)&(B Ú C).

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

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

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

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

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

= & ;

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

= Ú

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

— для логического сложения:

A Ú A = A;

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

A & A = A.

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

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

— для логического сложения:

A Ú 1 = 1, A Ú 0 = A;

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

A &1 = A, A &0 = 0.

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

A & = 0.

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

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

A Ú = 1.

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

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

— для логического сложения:

A Ú (A & B) = A;

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

A &(A Ú B) = A.

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

— для логического сложения:

(A & B) Ú ( & B) = B;

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

(A Ú B)&( Ú B) = B.

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

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

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