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

Рівносильні перетворення формул

На відміну від табличного Задача подання функції формулою не єдино. Наприклад, дві різні формули

Ø 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-10-17