1.2.4. Закони булевої алгебри

Всі наведені приклади (1.7–1.10) відомі вам з шкільного курсу алгебри. Виникає питання, які властивості мають булеві операції. Ці властивості, які називаються законами булевої алгебри перелічені в табл.1.11. Всі вони не є аксіомами і потребують доведення.

Таблиця 1.11
№ пор.	Тотожність	Найменування законів
1	2	3
1	а) або б) або	Комутативні закони для кон’юнкції та диз’юнкції
Продовження таблиці 1.11
1	2	3
2	а) б)	Асоціативні закони
3	а) б)	Дистрибутивні закони: а) кон’юнкція відносно диз’юнкції б) диз’юнкція відносно кон’юнкції
4	а) б)	Закони повторення (тавтології)
5	а) б)	Закони поглинання (абсорбції)
6		Закони доповнення
7	а) б)	Правила де Моргана
8		Закон подвійного заперечення
9	а) б)	Закони склеювання
10	а) б)	Закони універсальної множини
11	а) б)	Закони нульової множини
12

Як ми вже казали, всі властивості потребують доведення. Кожна властивість із табл.1.11 являє собою тотожність (рівність) двох формул, яку треба довести. Для доведення можна використати спосіб, описаний раніше (за допомогою таблиць істинності). Доведемо, наприклад, другу властивість, так звану дистрибутивність кон’юнкції відносно диз’юнкції, 3 а), а також дистрибутивність диз’юнкції відносно кон’юнкції 3 б) за допомогою таблиць істинності:

Приклад 1.11. Доведемо 3а) . Побудуємо таблицю істинності (табл.1.12.), за якою видно, що тотожність доведено.

Таблиця 1.12
1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	0
0	1	0	1	0	0	0	0
0	1	1	1	1	0	1	1
Продовження таблиці 1.12
1	2	3	4	5	6	7	8
1	0	0	1	0	0	0	0
1	0	1	1	1	1	0	0
1	1	0	1	0	0	0	0
1	1	1	1	1	1	1	1

Ми називали закон 3 а) дистрибутивністю кон’юнкції відносно диз’юнкції, а фактично довели дистрибутивність справа кон’юнкції відносно диз’юнкції. Цього достатньо, тому що операція кон’юнкції комутативна (див. закон 1 а)).

Приклад 1.12. Доведемо 3б) . Доведення у табл.1.13.

Таблиця 1.13
0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

За допомогою таблиць істинності можна довести будь-яку тотожність алгебри логіки. Вважатимемо, що всі властивості табл.1.11 доведено (саме таким способом, і ніяким іншим, можна довести властивості 1 і 2)

Усі наведені властивості мають велике значення в булевій алгебрі. Наприклад, дві наступні:

1. , що означає можливість вилучення з логічного виразу всіх членів, які мають подвійне заперечення, замінивши їх початковою величиною;

2. – правила подібних перетворень, що дають змогу скорочувати довжину логічних виразів.

Існують інші способи доведення тотожностей формул алгебри логіки. Так званий алгебраїчний спосіб передбачає перетворення формул з використанням властивостей, які наведені в табл.1.11. Причому, якщо ми доводитимемо деяку властивість із табл.1.11, то всі інші вважатимемо доведеними.

Диз’юнкція та кон’юнкція мають властивості, аналогічні властивостям арифметичних операцій додавання і множення:

1. властивість комутативності (переставний закон):

;

2. властивість асоціативності (сполучний закон):

;

3. властивість дистрибутивності (розподільний закон):

3а) для кон’юнкції відносно диз’юнкції:

,

3б) для диз’юнкції відносно кон’юнкції:

.

Властивість дистрибутивності фактично означає правила розкриття дужок і взяття в них логічних виразів. Правильність наведених властивостей легко доводиться за допомогою викладених вище законів.

Приклад 1.13. Доведемо, що

.

Справді, використовуючи комутативність, асоціативність і послідовно закони 3а), 3а), 4а), 10а), 3а), 10б), маємо

Аналогічно можна довести також інші закони. Нескладно встановити правильність співвідношень, відомих як закони де Моргана (закони 7 табл.1.11):

;

.

Приклад 1.14.

1. Доведемо

. Доведено.

2. Доведемо, що

;

.

Із законів де Моргана маємо

і .

За допомогою доведених в прикладі 1.14 співвідношень можна виражати кон’юнкцію через диз’юнкцію та заперечення або диз’юнкцію через кон’юнкцію і заперечення. Закони де Моргана та наслідки їх є дійсними для будь-якої кількості змінних:

;

.

Для логічних функцій встановлюються співвідношення, відомі як закони поглинання (див. 5 табл.1.11):

;

.

У табл. 1.14 доведені закони поглинання.

Таблиця 1.14
0	0	0	0	0	0
0	1	1	0	0	0
1	0	1	0	1	1
1	1	1	1	1	1

Розглянемо функцію додавання за модулем 2.

Приклад 1.15. Довести, що

.

Першу рівносильність доведено за допомогою таблиць істинності (табл. 1.15):

Таблиця 1.15
0	0	0	1	0	1	0	0
0	1	1	0	0	1	1	1
1	0	1	1	1	0	0	1
1	1	0	0	0	0	0	0

Другу рівносильність теж можна довести за таблицею істинності, але ми спробуємо алгебраїчним способом, використовуючи вже доведену першу рівносильність:

Функція додавання за модулем 2 (нерівносильність) має такі властивості:

1. комутативність (сполучний закон)

;

2. асоціативність (переставний закон)

;

3. дистрибутивність (розподільний закон)

;

4. ;	6. ;
5. ;	7. .

Ці властивості дуже легко можна довести.

На основі властивостей можна вивести правила подання функцій І, АБО, НІ через функцію додавання за модулем 2 і навпаки:

;

;

.

Приклад 1.16. Доведемо, що за таблицею істинності (табл.1.16)

Таблиця 1.16
0	0	0	0	0	0
0	1	1	1	0	1
1	0	1	1	0	1
1	1	1	0	1	1

Функція імплікації () – це функція, що виражається як . Для цієї функції справджуються такі очевидні властивості:

1. ;	3. ;	5. ;
2. ;	4. ;	6. .

Приклад 1.17. Доведемо, що імплікація має властивість (табл.1.17).

Таблиця 1.17
0	0	1	1	1	1
0	1	1	0	1	1
1	0	0	1	0	0
1	1	0	0	1	1

Доведемо, що властивість асоціативності для цієї функції не справджується (табл.1.18).

Таблиця 1.18
0	0	1	1	1
0	1	1	1	1
1	0	0	0	0
1	1	0	1	1

Функції І, АБО, НІ через імплікацію виражаються таким чином:

;

;

.

Приклад 1.18. Доведемо, що (табл.1.19):

Таблиця 1.19
0	0	0	1	1	0
0	1	0	0	1	0
1	0	0	1	1	0
1	1	1	0	0	1

Функція Шеффера – це функція, що може бути виражена співвідношенням .

Для цієї функції справджуються такі властивості:

1. ;	3. ;	5. ;
2. ;	4. ;	6. .

Для функції Шеффера справджується тільки властивість комутативності

і не справджується властивість асоціативності:

.

З основних властивостей функції Шеффера можна дістати такі формули перетворення:

Функція стрілка Пірса-Вебба – це функція, що описується виразом

Для цієї функції легко показати справедливість таких аксіом:

1. ;	3. ;
2. ;	4. .

На підставі цих аксіом можна встановити, що для функції стрілка Пірса-Вебба справджується тільки властивість комутативності: .

Функції І, АБО, НІ виражаються через функцію стрілка Пірса-Вебба таким чином:

Приклад 1.19.

1. Довести тотожність 5 б) з табл.1.11. Маємо

Таким чином , тобто дістаємо правило поглинання добутку співмножником .

2. Спростити вираз . Маємо

3. Довести, що . Маємо

.

4. Довести, що . Маємо

.

5. Довести, що . Маємо

.

Вправа 1.2.

1. Довести рівносильність (еквівалентність) формул двома способами: за допомогою таблиць істинності та алгебраїчним способом.

1. ;	7. ;
2. ;	8. ;
3. ;	9. ;
4. ;	10. ;
5. ;	11. ;
6. ;	12. ;

2. Довести рівносильності формул будь-яким способом:

1. ;	5. ;	9. ;
2. ;	6. ;	10. ;
3. ;	7. ;	11. ;
4. ;	8. ;	12. ;