Законы булевой алгебры.

Таблицы истинности могут применяться для анализа и сопоставления любых сложных высказываний. Такие проблемы возникают при анализе отрицаний. Например, отрицание "неверно, что 0<x<1" означает, что "x<=0" или "x>=1".

Приведенный выше пример является частным случаем закона отрицания логического умножения.

Существует два основных закона булевой алгебры, законы де Моргана:

1-ый закон де Моргана: (отрицание конъюнкции)

Отрицание логического умножения равносильно логическому сложению отрицаний, т.е.

not (A and B) = (not A) or (not B)

2-ый закон де Моргана:(отрицание дизъюнкции)

Отрицание логического сложения равносильно логическому умножению отрицаний, т.е.

not (A or B) = (not A) and (not B)

Кроме этого, в булевой алгебре существует следующие законы, позволяющие делать эквивалентные преобразования:

Ассоциативность сложения и умножения:

X1 or (X2 or X3) = (X1 or X2) or X3 = X1 or X2 or X3

X1 and (X2 and X3) = (X1 and X2) and X3 = X1 and X2 and X3

Коммутативность сложения и умножения:

X1 or X2 = X2 or X1

X1 and X2 = X2 and X1

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

X1 and (X2 or X3) = X1 and X2 or X1 and X3

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

X1 or (X2 and X3) = (X1 or X2) and (X1 or X3)

Идемпотентность (отсутствие степеней и коэффициентов):

X and X = X

X or X = X

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

not not X = X

Свойства констант 0("ложь") и 1("истина"):

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

X and not X = 0

X or not X = 1

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

X or X and Y = X and 1 or X and Y = X and (1 or Y) = X (поглощение)

X and Y or X and not Y = X and (Y or not Y) = X and 1 = X (склеивание)

X or not X and Y = (X or not X) and (X or Y) = 1 and (X or Y) = X or Y