Приводимые основные эквивалентности часто оказываются полезными при оперировании с булевыми функциями.
Ниже H, H1, H2 … означают некоторые булевы функции.
1. Закон двойного отрицания:
H=¬(¬H)
2. Идемпотентность:
H&H=H
HvH=H
3. Коммутативность:
H1*H2=H2*H1, где символ * означает одну из связок &, v, ⊕, ∼, |, ↓
4. Ассоциативность:
H1*(H2*H3)=(H1*H2)*H3, где символ * означает одну из связок &, v, ⊕, ∼
5. Дистрибутивность:
H1&(H2vH3)=(H1&H2)v(H1&H3)
H1v(H2&H3)=(H1vH2)&(H1vH3)
H1&(H2⊕H3)=(H1&H2)⊕(H1&H3)
6. Законы де Моргана:
¬(H1&H2)=¬H1v¬H2
¬(H1vH2)=¬H1&¬H2
7. Правила поглощения:
H1v(H1&H2)=H1
H1&(H1vH2)=H1
8. Законы склеивания:
H1&H2vH1&¬H2=H1
(H1vH2)&(H1v¬H2)=H1
9. Законы инверсий:
Hv¬H=1
H&¬H=0
10. Правила операций с константами:
Hv1=1
H&1=H
Hv0=H
H&0=0
Для проверки истинности приведенных эквивалентностей достаточно построить соответствующие таблицы истинности.
Отметим, что свойство ассоциативности операции позволяет распространить эту операцию для любого количества переменных. Так, например, запись XvYvZvW корректна, т.к. любая расстановка скобок приводит к одной и той же функции. Коммутативность операции позволяет менять местами переменные в формуле. Например, X&Y&Z&W=W&Y&X&Z.