Законы логики

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

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

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

Х = Х.

Закон идемпотентности

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

Х V Х = Х, Х & Х = Х.

Закон исключения констант

Для логического сложения Х V 1 = 1, Х V 0 = Х. Для логического умножения Х & 1 = Х, Х& 0=0.

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

Для логического сложения Х V (Х & Y) = X. Для логического умножения X & (X V Y) = X

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

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

X & X = 0.

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

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

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

X V X = 1.

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

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

Х = Х.

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

XÚ Y = X&Y,

X&Y = X V Y.

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

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

Закон переместительный (коммутативности)

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

X & Y = Y & X,

X V Y = Y V XА.

Закон сочетательный (ассоциативности)

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

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

(X & Y) & Z = X & (Y & Z),

(X V Y) V Z= X V (Y V Z).

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

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

множители, так и общие слагаемые.

Дистрибутивность умножения относительно сложения:

(X & Y) V (X & Z) = X&(Y V Z).