5.1.5. Рівносильність формул. Властивості логічних операцій

Означення 5.1.13. Формули алгебри висловлень f (p₁ , , p_n) і g ( p₁ , , p_n) називають рівносильними або логіч­но еквівалентними, якщо їх функції істин­ності |f| і |g| тотожно рівні, тобто, якщо їх значення на всіх 2ⁿ наборах збігаються.

Рівносильність формул f і g позначатимемо fg Символ “” не є символом операції алгебри висловлень, а означає певне відношення між формулами.

Основні рівносильності (закони) алгебри висловлень:

1. pqqp – комутативність кон’юнкції.

2. pqqp – комутативність диз’юнкції.

3. p(qr)(pq)r – асоціативність кон’юнкції.

4. p(qr)(pq)r – асоціативність диз’юнкції.

5. p(qr)pqpr – перший дистрибутивний закон.

6. p(qr)(pq)(pr) – другий дистрибутивний закон.

7. (pq)  закони

8. (pq) де Моргана.

9. pqq.

10. pq(pq)(qp).

11. p – закон подвійного заперечення.

12. ppp. закони

13. ppp. ідемподентності.

14. pq .

15. ppqp. закони

16. p(pq)p. поглинання.

17. u1u. правила

18. u00. співвідно-

19. u11. шення

20. u0u. констант

21. p1 – закон виключення третього.

22. p0 – закон протиріччя.

Формули 1-8, 11-13, 15-22 – називають аксіомами булевої алгебри або властивостями операцій кон’юнкція, диз’юнкція і заперечення.

Наступні властивості називають аксіомами алгебри Жегалкіна.

1ж. p(qr)(pq)r – асоціативність кон’юнкції.

2ж. p(qr)(pq)r – асоціативність строгої диз’юнкції.

3ж. pqqp – комутативність кон’юнкції.

4ж. pqqp – комутативність кон’юнкції.

Тема 5.4. Булеві функції

5.4.1. Поняття булевої функції. Способи задання

Алгебра булевих функцій – зручний формалізм для використання логічних умов у програмах, записаних сучасними мовами програмування.

Означення 5.4.1. Булевою називають функцію, область визначення і множина значень якої належать заданій двоелементній множині.

Зафіксуємо цю двоелементну множину як {0,1}. Тоді п-місна булева функція (від п аргументів) є відображенням {0,1}^п на {0,1}.

Булеву функцію f(x₁, x₂, …, x_n) можна задати різними способами:

Спосіб 1: за допомогою таблиці істинності, за якою визначають, яке значення f відповідає кожній окремій п-ці (набору) значень аргументів x₁, x₂, …, x_n.

x1, x2, …, xn	f(x1, x2, …, xn)
0, 0, ..., 0, 0 0, 0, ..., 0, 1 0, 0, ..., 1, 0 0, 0, ..., 1, 1 ... 1, 1, ..., 1, 1	f (0, 0, ..., 0, 0) f (0, 0, ..., 0, 1) f (0, 0, ..., 1, 0) f (0, 0, ..., 1, 1) ... f (1, 1, ..., 1, 1)

Оскільки кількість всіх наборів x₁, x₂, …, x_n становить 2^п, то кількість всіх булевих функцій дорівнює кількості розміщень з повтореннями з 2 елементів по 2^п:

.

Отже, для п=1 існує 4 одномісних булевих функцій.

Таблиця 5.1

x1	f1	f2	f3	f4
0 1	0 0	0 1	1 0	1 1

Для п=2 існує 16 двомісних булевих функцій.

Таблиця 2

x1	x2	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15	f16
0 0 1 1	0 1 0 1	0 0 0 0	0 0 0 1	0 0 1 0	0 0 1 1	0 1 0 0	0 1 0 1	0 1 1 0	0 1 1 1	1 0 0 0	1 0 0 1	1 0 1 0	1 0 1 1	1 1 0 0	1 1 0 1	1 1 1 0	1 1 1 1

Таблиці істинності булевих функцій із ростом кількості аргументів стають громіздкими і незручними. Тому існує потреба в зручнішому способі їх задання.

Спосіб 2: за допомогою формули, в якій задають логічні операції над аргументами x₁, x₂, …, x_n .

Наприклад, у таблиці 1: f₁ і f₄ – константи, f₂(х₁)=х₁, f₂(х₁)=.

У таблиці 2: f₁ (х₁,х₂) і f₁₆(х₁,х₂) – константи;

– кон’юнкція;

– антиімплікація;

;

– обернена антиімплікація;

;

– строга диз’юнкція (антиеквіваленція)

– диз’юнкція;

– антидиз’юнкція або стрілка Пірса;

– еквіваленція;

– заперечення х₂;

– обернена імплікація;

– заперечення х₁;

– імплікація;

– антикон’юнкція або штрих Шеффера.

Теорема 5.4.1. Кожна булева функція зображується формулою алгебри висловлень, яка містить символи не більше, ніж трьох логічних операцій – кон’юнкції, диз’юнкції і заперечення.