Основні правил булевих формул.

Для будь-яких формул A, B, C справедливі наступні Рівносильністи:

1. Комутативність.

а) A&B º B&A (для кон’юнкції);

б) AVB º BVA (для диз'юнкції).

2. Асоціативність.

а) A&(B&C) º (A&C)&C (для кон’юнкції);

б) AV(BVC) º (AVB)VC (для диз'юнкції).

3. Дистрибутивність.

а) A&(BVC) º A&BVA&C (для кон’юнкції щодо диз'юнкції);

б) AV(B&C) º (AVB)&(AVC) (для диз'юнкції відносно кон’юнкції).

4. Закон де Моргана.

а) Ø(A&B) ºØAVØB (заперечення кон’юнкції є диз'юнкція заперечень);

б) Ø(AVB) º ØA&ØB (заперечення диз'юнкції є кон’юнкція заперечень).

5. Ідемпотентність.

а) A&A º A (для кон’юнкції);

б) AVA º A (для диз'юнкції).

6. Поглинання.

а) A&(AVB) º A (1– ий закон поглинання);

б) AVA&B º A (2– ий закон поглинання).

7. Розщеплення (склеювання).

а) A&B V A&(ØB) º A (1-ий закон розщеплення);

б) (AVB) & (AVØB) º A (2-ий закон розщеплення).

8. Подвійне заперечення.

Ø(ØA) º A.

9. Властивості констант.

а)A&1 º A; б) A&0 º 0; в)AV1 º 1; г) AV0 º A; д) Ø0 º 1; е) Ø1 º 0.

10. Закон протиріччя.

A&ØA º 0.

11. Закон “виключення третього”.

AVØA º 1.

Кожна з перерахованих правил може бути доведена за допомогою таблиць значень функцій, складених для виражень, що коштують ліворуч і праворуч від символу “º”. Доведемо, наприклад, рівносильність 4а. Для цього складемо таблицю 4.5.

Таблиця 4.5

З таблиці 4.5 видно, що Ø(A&B) º ØAVØB, що й було потрібно довести.

Наступні важливі рівносильністі показують, що всі логічні операції можуть бути виражені через операції кон’юнкції, диз'юнкції й заперечення:

12. AÉB ºØAVB º Ø(A&ØB).

13. A~B º (AÉB)&(BÉA) º (A&B) V (ØA&ØB) º (АVØB)&(ØAVB).

14. AÅB º (AVØB) V (ØA&B).

15. A¯B º Ø(AVB) º ØA&ØB.

16. AïB º Ø(A&B) º ØAVØB.

Використовуючи рівносильністі 3а й 3б і метод математичної індукції, неважко одержати також наступні рівносильністі (узагальнені закони дистрибутивності):

17. (A₁VA₂V...VA_n)&(B₁VB₂V...VB_m) º

A₁&B₁VA₁&B₂V...VA₁&B_mV...VA_n&B₁VA_n&B₂V...VA_n&B_m.

18. (A₁&A₂&...&A_n)V(B₁&B₂&...&B_m) º

(A₁VB₁)&(A₁VB₂)&...&(A₁VB_m)&...&(A_nVB₁)&(A_nVB₂)&...&(A_nVB_m).

Використовуючи рівносильністі 4а й 4б і метод математичної індукції, можна одержати також наступні рівносильністі (узагальнені закони де Моргана):

19. Ø(A₁&A₂&...&A_n) º ØA₁VØA₂V...VØA_n.

20. Ø(A₁VA₂V...VA_n) ºØA₁&ØA₂&...&ØA_n

У рівносильностях 1 – 20 у якості A, B, A_i, B_i можуть бути підставлені будь-які формули й, зокрема, змінні. Приведемо правило, за допомогою якого можна переходити від одних Рівносильністей до інших.