Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

1.3. Методы доказательства в логике Буля

Основные законы логики Буля

В качестве основных законов логики Буля чаще других называют:

1) законы идемпотентности:

a = а ∧ a,     a = а ∨ a;

2) законы коммутативности:

а ∧ b = b ∧ a,    а ∨ b = b ∨ a;

3) законы ассоциативности:

а ∧ (b ∧ c) = (а ∧ b) ∧ c,

а ∨ (b ∨ c) = (а ∨ b) ∨ c;

4) законы дистрибутивности:

а ∧ (b ∨ c) = (а ∧ b)∨ (a ∧ c),

а ∨ (b ∧ c) = (а ∨ b) ∧ (a ∨ c);

5) законы нуля и единицы:

а ∧ a = 0, a ∧ 1 = а, 

а ∨ a = 1, а ∨ 0 = a;

6) законы поглощения:

а ∨ (а ∧ b) = а,

а ∧ (а ∨ b) = а;

7) законы де Моргана:

а ∨ b = а ∧ b,

а ∧ b = а ∨ b;

8) законы склеивания:

(а ∨ b) ∧ (а ∨ b) = а,

(а ∧ b) ∨ (а ∧ b) = а.

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

а = а ∨ (а ∧ b) = (а ∨ a) ∧ (а ∨ b) =

= (а ∧ (а ∨ b)) ∨ (а ∧ (а ∨ b)) = а ∨ a

Закон поглощения может быть выведен из закона нуля и единицы:

а ∨ (а ∧ b) = (a ∧ 1) ∨ (а ∧ b) =

= a ∧ (1 ∨ b) = a ∧ 1 = а.

Закон идемпотентности относительно дизъюнкции непосредственно выводится из законов нуля и единицы:

а ∨ a = (а ∨ a) ∧ 1 = (а ∨ a) ∧ (а ∨ a) =

= а ∨ (a ∧ а) = а ∨ 0 = а.

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

а ∧ (а ∨ b) = (a ∨ 0) ∧ (а ∨ b) =

= a ∨ (0 ∧ b) = a ∨ 0 = а.

Итак, в качестве независимой системы законов можно выбрать законы: коммутативности, ассоциативности, дистрибутивности, нуля и единицы.