Основні закони алгебри логіки та їх використання для подання одних функцій логіки через інші
Вперше логічні функції були використані в алгебрі логіки, початок якій покладено працями англійського математика Дж. Буля, її також називають булевою алгеброю або алгеброю висловлень.
Під висловленням розуміється будь-яке твердження, яке може бути істинним або хибним.
Істинному висловленню приписується 1, хибному – 0. Висловлення можуть бути простими і складними. Складні висловлення складаються з простих.
Для об’єднання простих висловлень в складні використовуються логічні зв’язки, що відповідають логічним функціям, аргументами яких є прості висловлення.
Логічний зв’язок “І” (кон’юнкція). Кон’юнкцією називають складне висловлення, що містить 2 або більше простих висловлень і яке є істинним тоді і лише тоді, коли істинними є прості висловлення, і хибним, якщо хоч одне з простих висловлень хибне.
Кон’юнкція являє собою логічний зв’язок “І” (див. табл. 1.5).
З’єднання двох висловлень читається як “
і 
”. Позначається 
або 
.
Таблиця 1.5
|
|
0 |
0 |
1 |
1 |
|
|
0 |
1 |
0 |
1 |
|
|
0 |
0 |
0 |
1 |
Логічний зв’язок “АБО” (диз’юнкція). Диз’юнкцією називають складне висловлення, що містить декілька простих висловлень і яке є істинним тоді, коли істинним буде хоч одне з простих висловлень, які входять в це складне висловлення, і хибним, якщо всі прості висловлення хибні.
Диз’юнкція являє собою логічний зв’язок “АБО” (табл. 1.6) і позначається 
. Читається “
або 
”.
Таблиця 1.6
|
|
|
|
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
1 |
= ”
або 
”Логічний зв’язок “НЕ” (заперечення). Логічний зв’язок “НЕ” означає заперечення висловлення і читається “НЕ 
”, позначається 
абоШ
(табл. 1.7)
Таблиця 1.7
|
|
0 |
1 |
|
|
1 |
0 |
Запереченням висловлення 
називають складне висловлення “НЕ 
”, яке є істинним, коли 
хибне, і хибним, коли 
істинне.
Для зручності подальших викладок використаємо позначення: “∙” – кон’юнкція, “
” – диз’юнкція і “
” – заперечення.
Булевою алгеброю називається множина 
, що складається не менше ніж з двох елементів, на якій визначені три операції – диз’юнкції (
), кон’юнкції (
), заперечення (
). Для будь-яких елементів 
виділяємо набір незалежних властивостей, які вважають аксіомами булевої алгебри, а саме:
– закон комутативності:
; (1.1)
– закон асоціативності:
; (1.2)
– закон дистрибутивності:
; (1.3)
для спрощення формул крім аксіом використовують такі співвідношення або закони алгебри логіки:
– логічне додавання до нуля:
; (1.4)
– логічне додавання до одиниці:
; (1.5)
– логічне множення на 0:
; (1.6)
– логічне множення на 1:
; (1.7)
– закон протиріччя:
; (1.8)
– закон виключеного третього:
. (1.9)
Всі інші закони є наслідком зазначених вище:
– закон ідемпотентності:
; (1.10)
– закон подвійного заперечення:
; (1.11)
– закон поглинання (х поглинає у):
; (1.12)
– закон де Моргана:
(1.13)
(1.14)
– наслідки законів де Моргана:
; (1.15)
. (1.16)
За допомогою розглянутих співвідношень можна виконувати різні тотожні перетворення булевих виразів.
При цьому порядок виконання дій такий:
При відсутності дужок виконуються операції заперечення, потім кон’юнкції, останніми – диз’юнкції.
Подання одних функцій алгебри логіки через інші
1. Операція заборони:
. (1.17)
Для доведення цього і наступних співвідношень будемо підставляти в ліву і праву частини виразу окремі значення аргументів і перевіряти правильність рівності.
Таблиця 1.8
|
|
|
|
|
0 |
0 |
0 |
|
0 |
1 |
0 |
|
1 |
0 |
1 |
|
1 |
1 |
0 |
Таблиця 1.9
|
|
|
|
|
|
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
0 |
2. Сума за модулем 2:
. (1.18)
3. Операція Пірса:
(операція АБО-НЕ). (1.19)
4. Логічна рівнозначність:
. (1.20)
Справедливість першої рівності може бути встановлена безпосередньо по таблицях істинності функції логічної рівнозначності і суми по модулю 2; наступних рівностей - шляхом інвертування лівої і правої частин виразу і перетворення за формулами де Моргана.
5. Імплікація:
. (1.21)
6. Функція Шеффера:
(операція І-НЕ). (1.22)
Поделиться с друзьями: