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

Равносильные преобразования формул

В отличие от табличного задания представление функции формулой не единственно. Например, две различные формулы

Øx₁VØx₂ и Ø(x₁&x₂)

реализуют одну функцию – штрих Шеффера.

Две формулы, реализующие одну и ту же функцию, называются равносильными.

Равносильность формул A и B будем обозначать следующтм образом: A º B.

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

Для любых формул 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 могут быть подставлены любые формулы и, в частности, переменные. Приведем правило, с помощью которого можно переходить от одних равносильностей к другим.