Операції та закони алгебри логіки.

Отримана аналітична формула складається із операндів[21], об’єднаних символами логічних операцій.

Серед основних логічних операцій можна відзначити наступні

Операція «НЕ» (інші назви: інверсія, логічне заперечення, NOT). Нехай є деяке висловлювання А. Заперечення цього висловлювання позначається` (прийнято читати: «не А»). Якщо висловлювання А має значення «істина» (А = 1), то висловлювання набуває значення «не істина» ( = 0). Якщо висловлювання А – «не істина» (А = 0), то висловлювання – «істина» ( = 1). Таблиця істинності функції, що визначається тільки цією однією операцією, має вид:

А

Зокрема, справедливі наступні співвідношення: = 1; = 0.

Позначення операції НЕ в схемах логічних перетворень[22]:

Операція «логічне заперечення» відноситься до одномісних операцій (унарних, або монадичних), оскільки виконується над одним операндом.

Операція «І» (інші назви: кон’юнкція, логічне множення, AND). Операцію логічного множення двох змінних А і В позначають А Ù В (прийнято читати: А і В). Висловлювання А Ù В набуває значення «істина» (А Ù В= 1) тільки в тому випадку, якщо одночасно А має значення «істина» (А = 1) і В – «істина» (В = 1). У всіх інших випадках це висловлювання набуває значення «не істина», тобто А Ù В= 0. Отже, правила логічного множення визначаються наступною таблицею істинності:

А	В	А Ù В

Правило логічного множення справедливе не тільки для двох співмножників, але і для будь-якої їх кількості, тобто A ÙB ÙC ÙD Ù…, тобто ця операція багатомісна (поліадична). Позначення операції в схемах логічних перетворень (для трьох змінних х₁, х₂, х₃):

Операція «АБО» (інші назви: диз’юнкція, логічне додавання, OR). Операцію логічного додавання двох змінних А і В позначають А Ú В (прийнято читати: А або В). Висловлювання А Ú В – «істина», (А Ú В= 1) в тому випадку, якщо хоча б одна із змінних А або В має значення «істина» (А = 1 або В = 1). Якщо ж ця умова не виконується, то висловлювання – «не істина», (А Ú В= 0). Отже, правила логічного додавання визначаються наступною таблицею істинності:

А	В	А Ú В

Правило логічного додавання справедливе не тільки для двох доданків, але і для будь-якої їх кількості, тобто A ÚB ÚC ÚD Ú…. Позначення операції в схемах логічних перетворень:

Операція «АБОіз виключенням» (інші назви: додавання за модулем 2, нееквівалентність, XOR (Exclusive OR)). Операція «АБО із виключенням» над двома змінними А і В позначають А Å В. Висловлювання А Å В має значення «істина» (А Å В= 1) в тому випадку, якщо тільки одна із змінних А або В має значення «істина» (А = 1, В = 0 або А = 0, В = 1). Якщо ж ця умова не виконується, то висловлювання – «не істина» (А Å В=0). Перша назва операції зумовлена тим, що результат даної операції збігається із результатом операції «АБО» за виключенням одного випадку – одночасної істинності аргументів (виключається). Друга назва – тим, що дійсно є складанням в кільці вирахувань за модулем 2. Третя назва – результат операції істинний тільки тоді, коли значення операндів не співпадають. Отже, правила виконання операції «АБО із виключенням» визначаються наступною таблицею істинності:

А	В	А Å В

Позначення операції в схемах логічних перетворень (для трьох змінних х₁, х₂, х₃):

На основі розглянутих логічних висловлювань можна уявити будь-яке складне висловлювання, тобто будь-який логічний зв’язок можна виразити за допомогою логічних операцій додавання, множення і заперечення.

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

Операції «І», «АБО» і «АБО із виключенням» є не тільки комутативними, але і асоціативними, і тому узагальнюються на випадок кількох аргументів.

Інші логічні операції:

Операція «АБО–НЕ»(стрілка Пірса, NOR) – двомісна логічна операція, введена в розгляд Ч. Пірсом. Операцію «АБО–НЕ» над двома змінними А і В позначають А↓ В. Її результатом є інвертований результат операції «АБО». Операція «АБО–НЕ» визначається такою таблицею істинності:

А	В	А ↓ В

Висловлювання А↓ В прийнято читати «ні А, ні В». Позначення операції в схемах логічних перетворень:

Стрілка Пірса має ту властивість, що через її одну виражаються всі інші логічні операції. Наприклад, висловлювання (не A) еквівалентно висловлюванню А↓ A; кон’юнкція A Ù B висловлювань A і B виражається так: (А↓ A)↓(В↓ В); диз’юнкція А Ú Веквівалентна (А↓ В)↓(А↓ В).

Операція «І–НЕ» (штрих Шеффера, NAND) – є результатом інвертування результату операції «І», тобто видає значення 0 тільки коли обидва операнди 1. Операцію «І–НЕ» над двома змінними А і В позначають А| В і виконують за таким правилом:

А	В	А | В

Позначення операції в схемах логічних перетворень:

Операція імплікація («якщо – то»). Операцію «якщо – то» над двома змінними А і В позначають АÌ В (іноді А→ В). Результат співпадає з результатом операції «АБО» з інвертованим першим аргументом, видає значення 0 тільки коли перший операнд дорівнює 1 а другий – 0. Ця операція не є комутативною, на відміну від всіх вищеописаних операцій. Її можна розуміти як арифметичне ≤ (менше або дорівнює). Операція «якщо – то» виконується за таблицею істинності:

А	В	А Ì В

В операції АÌ В операнди мають спеціальні назви: А – антецедент (передуючий), В – консеквент (подальший). Імплікація неістинна тоді і тільки тоді, коли антецедент – «істина», а консеквент – «неістина». Отже, «з правди не може випливати неправда!».

Операція еквіваленція. Еквіваленцією двох висловлювань А і В називається таке висловлювання, яке набуває значення «істина» тоді і тільки тоді, коли обидва ці висловлювання А і В – «істина» або обидва – «не істина», тобто видає 1, якщо і тільки якщо обидва аргументи рівні між собою. Є результатом інвертування результату операції «АБО із виключенням». Позначають операцію символом ««». Операція виконується за таблицею істинності:

А	В	А«В

При розробці вузлів МП-систем значення неістинного або істинного висловлювання А, В, С до уваги не приймається; апарат алгебри логіки використовується для виконання заданих логічних перетворень. Наприклад, арифметичні перетворення (складання, віднімання) задаються у вигляді сукупності логічних перетворень над аргументами.

Важливе значення мають правила і закони перетворень для логічних виразів. Основні з них, які є властивостями, законами і аксіомами, мають такий вид:

- Комутативність (переміщуваність):

АÚВ = ВÚА; АÙВ = ВÙА.

- Асоціативність (сполученість):

АÚ(ВÚС) = (АÚВ)ÚС; АÙ(ВÙС) = (АÙВ)ÙС.

- Дистрибутивність (розподіленість):

Кон’юнкція відносно диз’юнкції АÚ(ВÙС) = (АÚВ) Ù (АÚС);

Диз’юнкція відносно кон’юнкції АÙ(ВÚС) = (АÙВ) Ú (АÙС).

- Комплементність (доповненість) (властивість заперечення):

- Закон інверсії (правило Де Моргана):

; .

- Закони поглинання:

АÚ(AÙB) = А; АÙ(AÚB) = А.

- Закони Блейка-Порецького:

; .

- Ідемпотентність[23]:

АÚА = А; АÙА = А.

- Інволютивність[24] заперечення (закон подвійного заперечення):

.

- Склеювання:

; .

- Властивості констант:

АÚ0 = А; АÙ1 = А;

АÚ1 = 1; АÙ0 = 0.

= 1 (доповнення 0 є 1);

= 0 (доповнення 1 є 0).

Два логічних вирази вважаються рівними, якщо їх таблиці істинності співпадають. Існує два основні способи перевірки рівності двох логічних виразів: за допомогою таблиць істинності і за допомогою тотожних перетворень. Очевидно, що таблиця істинності може бути побудована для будь-якого логічного виразу.