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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

а) Ø(A & B) ºØ A VØ B (отрицание конъюнкции есть дизъюнкция отрицаний);

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

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

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

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

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

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

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

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

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

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

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

Ø(Ø A) º A.

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

а) A &1 º A; б) A &0 º 0; в) A V1 º 1; г) A V0 º A; д) Ø0 º 1; е) Ø1 º 0.

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

A &Ø A º 0.

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

A VØ A º 1.

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

Таблица 4.5

A	B	A & B	Ø(A & B)	Ø A	Ø B	Ø A VØ B

Из таблицы 4.5 видно, что Ø(A & B) º Ø A VØ B, что и требовалось доказать.

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

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

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

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

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

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

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

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

A ₁& B ₁V A ₁& B ₂V...V A ₁& B_m V...V A_n & B ₁V A_n & B ₂V...V A_n & B_m.

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

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

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

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

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

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

Дата добавления: 2014-11-06