Основні тотожності
Кожній формулі відповідає функція, різним формулам – різні функції.
Означення 1. Формули F1 й F2 називаються тотожними, або еквівалентними, якщо відповідні функції f1 та f2 – рівні, тобто f1 = f2. Тоді запис F1 = F2 означає, що F1 й F2 – тотожні формули.
Означення 2. Дві формули F1 й F2 називаються еквівалентними, якщо вони задають одну і ту саму булеву функцію всіх змінних, що входять у ці формули.
Кон’юнкція, диз’юнкція, заперечення (функції ТА, АБО, НЕ). Використовуючи основні положення, легко переконатися у правильності таких аксіом. Нехай x – деяка логічна змінна. Тоді:
1) = x, що означає можливість вилучення з логічного виразу всіх членів, які мають подвійне заперечення, замінивши їх початковою величиною;
2) x + x = x, xx = x – правила подібних перетворень, що дають змогу скорочувати довжину логічних виразів;
3) x + 0 = x;
4) x + 1 = 1;
5) x 0 = 0;
6) x 1 = x;
7)
x
= 0;
8) x + = 1.
Диз’юнкція та кон’юнкція мають властивості, аналогічні властивостям арифметичних операцій додавання і множення:
1) сполучний закон:
x1 + (x2 + x3) = (x1 + x2) + x3; x1(x2x3) = (x1x2)x3.
2) переставний закон:
x1 + x2 = x2 + x1; x1x2 = x2x1.
3) розподільчий закон:
для кон’юнкції відносно диз’юнкції
x1(x2 + x3) = x1x2 + x1x3;
для диз’юнкції відносно кон’юнкції
x1 + x2x3 =(x1 + x2)(x1 + x3).
Доведемо останню рівність: (x1 + x2)(x1 + x3) = x1x1 + x1x3 + x2x1 + x2x3 = x1(1 + x2 + x3) + x2x3 = x1 + x2x3 (оскільки 1 + x2 + x3 = 1).
Справедливі такі співвідношення (закони де Моргана):
=
+
,
=
,
звідси випливає, що
x1x2
=
,
x1
+ x2
=
.
За допомогою цих співвідношень можна виразити кон’юнкцію через диз’юнкцію та заперечення, або диз’юнкцію через кон’юнкцію і заперечення.
Для логічних функцій встановлюються співвідношення, відомі як закони поглинання:
x1 + x1x2 = x1, x1(x1 + x2) = x1
x1 |
x2 |
x1 + x2 |
x1 x2 |
x1 + x1x2 |
x1 + (x1 + x2) |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
Функція x1 x2 = x1 + x2 = (x1 + x2)( + ) – додавання за модулем 2 – має такі властивості:
1) сполучний закон
x1 (x2 x3) = (x1 x2) x3;
2) переставний закон
x1 x2 = x2 x1;
3) розподільчий закон
x1(x2 x3) = x1x2 x1x3.
Для цієї функції справджуються такі властивості
x x = 0; x 1 = , x = 1, x 0 = x.
Функції ТА, АБО, НЕ виражаються через функцію додавання за модулем 2:
x1x2 = (x1 x2) (x1 x2),
x1 + x2 = x1 x2 x1x2,
=
x1
1.
Для функції імплікації x1 x2 = + x2 справджуються такі аксіоми:
x x = 1, x 1 = 1, 0 x = 1, x = , x 0 = , 1 = x.
Отже, імплікація має тільки властивість комутативності (переставний закон) у зміненому вигляді: x1 x2 = . Властивість асоціативності для цієї функції не справджується:
x1 |
x2 |
x3 |
x1 (x2 x3) |
(x1 x2) x3 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Функції ТА, АБО, НЕ через імплікацію виражаються так:
x1x2
=
,
x1 + x2 = x2,
= x1 0.
Для функції Шеффера x1 / x2 = справджуються такі аксіоми:
x / x = , x / = 1, x / 0 = 1, x / 1 = , / 0 = 1, / 1 = x.
Для функції Шеффера справджується тільки властивість комутативності: x1 / x2 = x2 / x1, для трьох і більше змінних x1 / (x2 / x3) (x1 / x2) / x3.
Доведемо
цей факт:
(x1
/ x2)
/ x3
= (
)
/ x3
=
= x1x2
+
,
x1
/ ( x2
/ x3)
= (x1
/ x2)
/ x3
= (
)
/ x3
=
= x1x2
+
.
При розгляді властивості дистрибутивності функції Шеффера матимемо на увазі, що
x1(x2 + x3) = (x1x2) + (x1x3), x1 + (x2 x3) = (x1 + x2)(x1 + x3).
Приклади: 1) Перетворимо вираз
x1
/ (x2
/ x3)
=
=
+ x2x3
=
= x1
/
x1
/
=
=
= [x1
/ (x2
/ 1) / (x3
/ 1)];
2)
(x1
/ x2)
/ (x1
/ x3)
=
= (x1x2)
+ x1x3
= x1(
)
=
=
x1(
)
=
=
=
= [x1 / (x2 / 1) / x1 / (x3 / 1) / 1].
З основних властивостей функції Шеффера можна дістати такі формули перетворення:
x1x2
=
= x1
/ x2
/ x1
/ x2;
= x / x;
x1 + x2 = = / = x1 / x2 / x2 / x2.
Для
функції стрілка Пірса-Вебба x1
x2
=
=
мають місце такі аксіоми:
x x = , x 0 = x, x = 0, x 1 = 0.
Для цієї функції справедлива властивість комутативності: x1 x2 = x2 x1.
Функції ТА, АБО, НЕ виражаються через функцію стрілка Пірса-Вебба так:
x1x2 = (x1 x1) (x2 x2),
x1 + x2 = (x1 x2) (x1 x2),
= x x.