11 ЛОГІЧНІ ОСНОВИ КОМП'ЮТЕРІВ 

11.1 Поняття логічної функції

Змінна, яка приймає тільки два значення, позначені символами 0 або 1, називається логічною або булевою змінною.

Різні логічні змінні можуть бути зв’язані функціональними залежностями подання. Наприклад, вираз y = f (x1, x2) вказує на функціональну залежність логічної змінної Y від логічних змінних х1 та х2, які називаються аргументами (або вхідними змінними).

Функцію логічних змінних, область значень якої має тільки два значення: 0 або 1, будемо називати логічною або булевою, або перемикальною. ЇЇ позначають Р1(А, В,…) або f(x1, x2,…, xn). Оскільки логічні змінні можуть приймати тільки два значення (значення істинності або значення хибності), можна показати, що в загальному випадку логічна функція n-змінних включає 2n можливих наборів змінних. А всього в цьому випадку існує  логічних функцій. Для n=1 кількість наборів змінної дорівнює двом, а всього логічних функцій чотири. Для n=2 кількість наборів змінних дорівнює чотирьом, а логічних функцій – шістнадцять і т.д. З ростом числа змінних число функцій росте дуже швидко.

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

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

Логічні функції двох змінних

Розглянемо логічні функції двох змінних Y = f(A, B). Для n=2 число можливих різних наборів дорівнює 22=4, а кількість різних логічних функцій  = 16. Ці 16 логічних функцій подані в таблиці 11.1.

Із цих 16-ти функцій 6 – це функції однієї змінної: f0 – константа 0; f3 – змінна А; f5 - змінна В; f10- інверсія В; f12 - інверсія А; f15 - константа 1.

Таблиця 11.1 – Функції двох змінних

Розглянемо інші десять функцій.

1. Функція 

 називається кон’юнкцією або логічним множенням, або функцією "I":

Логічний елемент, який реалізує функцію “кон’юнкція” називається кон’юнктором, або елементом "I" і має таке графічне зображення (рис. 11.1).

Рисунок 11.1 – Логічний елемент I

Сигнал на виході такого елемента з’являється тоді і тільки тоді, коли є сигнал на обох його входах.

2. Функції 

називаються функціями заборони по В і по А відповідно.

Рисунок 11.2 – Елемент заборони по В   Рисунок 11.3 – Елемент заборони по А

3. Функція 

 - нерівнозначність або сума по модулю два:

4. Функція

  - рівнозначність:

Функції f6 і f9 реалізуються на елементах, які показані на рис. 11.4.

Рисунок 11.4 – Елементи, що реалізують операції:  а-нерівнозначність, б-рівнозначність

5. Функція 

– називається диз’юнкцією або логічним додаванням, або функцією "АБО":

Логічний елемент, який реалізує цю функцію, називається диз’юнктором або елементом "АБО", який має вигляд, що показаний на рис. 11.5.

Сигнал на виході такого елементу з’являється тоді, коли хоч би на одному вході або на обох входах одночасно з’являється сигнал.

6. Функція 

– називається операцією (стрілкою) Пірса або запереченням диз’юнкції:

Ця функція реалізується на елементах Пірса (рис. 11.6).

Рисунок 11.5 – Логічний елемент "АБО"                      Рисунок 11.6 – Елемент Пірса

7. Функції 

– називаються зворотною імплікацією і імплікацією відповідно:

Ці функції графічно зображуються, як показано на рис. 11.7.

Рисунок 11.7 – Елементи імплікації

8. Функція 

– називається операцією Шеффера: 

Ця функція реалізується на елементі, який називається елементом Шеффера (рис. 11.8).

Рисунок 11.8 – Елемент Шеффера

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

В алгебрі логіки є чотири основні закони:

- переміщувальний (властивість комутативності);

- сполучний (властивість асоціативності);

- розподільчий (властивість дистрибутивності);

- інверсії (правило де Моргана).

Відношення, які відображають ці закони для двох чи трьох змінних, приведені в табл. 11.2.

Таблиця 11.2 – Рівносильності для двох чи трьох змінних

Більшість названих законів зустрічається у звичайній алгебрі і не викликає сумніву. Розподільчого закону для множення і закону інверсії у звичайній алгебрі немає. Доведення цих законів може бути виконано шляхом складання таблиць істинності для правої та лівої частин рівняння, що описують той чи інший закон, або ж методом безпосередніх перетворень. Для прикладу доведемо за допомогою таблиці істинності справедливість закону інверсії при додаванні двох змінних А та В.

В табл. 11.3 вказані значення лівої і правої частини рівняння, яке характеризує закон інверсії при додаванні. Збіг таблиць істинності для лівої і правої частин підтверджує справедливість закону інверсії для двох змінних. Неважко показати справедливість основних законів алгебри логіки і для більшого числа змінних.

Таблиця 11.3 – Закон інверсії при додаванні двох змінних А та В.

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

Ці правила зведені в табл. 11.4.

Перші три правила фактично описують властивості операції "НІ", "І", "АБО". Четверте правило вказує на те, що множення на коефіцієнти, які відрізняються від логічного нуля і логічної одиниці, а також піднесення до степеня не мають смислу в алгебрі логіки.

Таблиця 11.4 – Правила алгебри логіки

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

Доведемо правила склеювання методом безпосередніх перетворень. При цьому методі виходять із вірності деяких законів, і застосовуючи ці вірні закони, доводять вірність інших.

Будемо вважати, що вірні відношення:

Тоді для логічного додавання:

Для логічного множення:

Аналогічно доводяться правила поглинання. Варто звернути увагу на властивість симетрії, яка властива основним законам і правилам булевої алгебри. Всі правила (крім останнього) подані в таблиці 11.4 парою співвідношень. В кожній парі одне співвідношення витікає з іншого заміною додавання множенням і навпаки. Крім того, всі значення 0 замінюються на 1 і, навпаки, всі значення 1 – на 0. Ця властивість симетрії в булевій алгебрі відома як принцип двоїстості.

11.3 Форми подання логічних функцій

Логічні функції можуть мати різну форму подання. Вибір тієї або іншої форми подання визначається цілями завдання функції. Звичайно кінцевою метою подання є синтез цифрового пристрою, який реалізує це подання. Ось найбільш вживані подання логічних функцій:

-   таблиця істинності;

-   номери наборів, на яких логічна функція дорівнює одиниці або нулю;

-   аналітичне довільне подання;

-   аналітичне канонічне подання.

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

Для подання функції можна використовувати номери наборів. Наприклад, для табл. 11.5 функцію можна задавати у вигляді наборів 2, 3, 5 і 6, де вона дорівнює одиниці. Довільне аналітичне подання логічної функції найбільш компактне і наочне. Крім того, деякі спеціальні методи спрощення (мінімізації) логічних функцій потребують їх подання в спеціальному (канонічному) вигляді.

Таблиця 11.5 – Таблиця  істинності для деякої логічної функції трьох змінних

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

Нормальною формою булевої функції називається така форма, яка складається тільки з диз’юнкції елементарних кон’юнкцій або з кон’юнкції елементарних диз’юнкцій.

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

Наприклад, 

Елементарною диз’юнкцією називається логічний вираз, який складається із довільного кінцевого числа змінних або їх інверсій, що логічно додаються.

Наприклад, 

Розрізняють диз’юнктивні нормальні форми (ДНФ) подання логічних функцій і кон’юнктивні нормальні форми (КНФ).

ДНФ являє собою диз’юнкцію кінцевої множини елементарних кон’юнкцій. 

Наприклад, 

КНФ являє собою кон’юнкцію кінцевої множини елементарних диз’юнкцій. 

Наприклад, 

Елементарна кон’юнкція, яка складається з усіх змінних, причому деякі або всі з них можуть бути з запереченням, називається конституентою одиниці і позначається Ki(1), де і – номер набору, на якому логічна функція дорівнює одиниці.

   Розглянемо запис конституент одиниці на прикладі функції трьох змінних. В табл. 11.5 показані номери наборів, можливі набори функції трьох змінних і вирази для Ki(1). Вираз для Ki(1) складається таким чином: записується елементарна кон’юнкція всіх змінних. Потім ті змінні, які на даному наборі приймають значення 0, беруться з запереченням. 

Наприклад, 

  Елементарна диз’юнкція, яка складається з усіх змінних, причому деякі або всі з них можуть бути з запереченням, називається конституентою нуля і позначається Ki(0), де – і номер набору, на якому Ki(0) = 0. В табл. 11.5 показано запис Ki(0) для функції трьох змінних. Вираз для Ki(0) складається таким чином: записується елементарна диз’юнкція всіх змінних. Потім ті змінні, які на даному наборі приймають значення 1, беруться з запереченням. 

Наприклад 

З цих виразів виходить що

Досконалою диз’юнктивною нормальною формою (ДДНФ) логічної функції називається диз’юнкція конституент одиниці тих наборів, на яких логічна функція приймає значення 1.

Досконалою кон’юнктивною нормальною формою (ДКНФ) логічної функції називається кон’юкція конституент нуля тих наборів, на яких логічна функція приймає значення 0.

ДДНФ і ДКНФ є канонічними формами завдання логічних функцій.

Приклад. Подати функцію, що задана в табл. 11.5, в ДДНФ і ДКНФ.

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

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