Главная | Обратная связь

Основные равносильности булевых формул.

Для любых формул A, B, C справедливы следующие равносильности:

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

а) A B º B A (для конъюнкции);

б) AÚB º BÚA (для дизъюнкции).

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

а) A (B C) º (A C) C (для конъюнкции);

б) AÚ(BÚC) º (AÚB)ÚC (для дизъюнкции).

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

а) A (BÚC) º A BÚA C (для конъюнкции относительно дизъюнкции);

б) AÚ(B C) º (AÚB) (AÚC) (для дизъюнкции относительно конъюнкции).

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

а) ( ) º Ú (отрицание конъюнкции есть дизъюнкция отрицаний);

б) ( ) º (отрицание дизъюнкции есть конъюнкция отрицаний).

5. Идемпотентность.

а) A A º A (для конъюнкции);

б) AÚA º A (для дизъюнкции).

6. Поглощение.

а) A (AÚB) º A (1– ый закон поглощения);

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

7. Расщепление (склеивание).

а)(A B) Ú (A ) º A (1–ый закон расщепления);

б) (AÚB) (AÚ ) º A (2–ой закон расщепления).

8. Двойное отрицание.

º A.

9. Свойства констант.

а)A 1 º A; б) A 0 º 0; в)AÚ1 º 1; г) AÚ0 º A; д) º 1; е) º 0.

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

A º 0.

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

AÚ º 1.

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

Таблица 10

A	B	A B				Ú

Из таблицы 5 видно, что , что и требовалось доказать.

Следующие важные равносильности показывают, что все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания:

12. A®B º

13. A«B º (A®B) (B®A)

Используя равносильности 3а и 3б и метод математической индукции, нетрудно получить также следующие равносильности (обобщенные законы дистрибутивности):

14. (A₁ÚA₂Ú...ÚA_n) (B₁ÚB₂Ú...ÚB_m) º

A₁ B₁ÚA₁ B₂Ú...ÚA₁ B_mÚ...ÚA_n B₁ÚA_n B₂Ú...ÚA_n B_m.

15. (A₁ A₂ ... A_n)Ú(B₁ B₂ ... B_m) º

(A₁ÚB₁) (A₁ÚB₂) ... (A₁ÚB_m) ... (A_nÚB₁) (A_nÚB₂) ... (A_nÚB_m).

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

16. ( ) º ₁Ú ₂Ú...Ú _n.

17. ( ) º _{1 2} ... _n

В равносильностях 1 – 17 в качестве A, B, A_i, B_i могут быть подставлены любые формулы и, в частности, переменные.