Основи булевої алгебри

Аналіз комбінаційних пристроїв і цифрових логічних схем простіше всього проводити за допомогою булевої математики, що оперує лише з двома поняттями: істинним (логічна 1) і хибним (логічний 0). В результаті функції, що відображають інформацію, приймають в кожен момент часу лише значення 0 або 1. Такі функції називають логічними. Логічні функції Y кількох змінних (X0, X1, ..., Xn-1) визначають характер логічних операцій, в результаті яких набору вхідних змінних ставиться у відповідність змінна Y

Y=f(X0, X1, ..., Xn-1).

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

Таблиця 1

Основними логічними функціями є логічне множення (кон'юнкція), логічне складання (диз'юнкція) і логічне заперечення (інверсія). При логічному множенні вхідні змінні (дві або більше) з'єднують союзом І (AND). Таку операцію позначають /\ або знаком множення (*). Функція Y1=X1*X2 приймає значення логічної 1 лише при рівності 1 всіх вхідних змінних. Якщо хоч одна змінна дорівнює 0, то й вихідна функція дорівнює 0 (таблиця 1).

При логічному складанні два і більше висловлювань з'єднують союзом АБО (OR). Позначають цю операцію символом \/ або знаком складання (+) Таблиця істинності для диз'юнкції має такий вигляд.

Таблиця 2

Висловлення (Х1+Х2) істинне, якщо істинне хоч одне з висловлювань, що входять до її складу.

При логічному запереченні функція НІ (NOT) значення вихідної функції протилежне вхідній змінній (табл. 3). Цю операцію позначають Х (читається "НІ X").

Таблиця 3

Кон'юнкцією, диз'юнкцією і інверсією можна виразити будь-які інші більш складні операції над висловленнями. Тому система функцій Y1=Х1*Х2, Y2=Х1+Х2 і Y3=-Х має функціональну повноту. В якості прикладу розглянемо кілька функцій, реалізованих за допомогою елементів обчислювальної техніки. Рівнозначністю (або еквівалентною) називають функцію Y двох аргументів X1 і Х2, яка приймає значення Y=1 при Х1=Х2=1 або при Х1=Х2=0. При різних значеннях аргументів Х1≠Х2 значення функції Y=0. Можна показати, що функція Y має вигляд Y=X1*Х2+(-Х1)*(-Х2), що підтверджується підстановкою в вираження відповідних значень аргументів. Нерівнозначністю називають функцію Y двох аргументів X1 і Х2, що приймає значення 1 при Х1≠Х2, і значення 0 при Х1=Х2=0 або, при Х1=Х2=1. В цьому випадку будемо мати Y=Х1*Х2+Х1*Х2. Операцію нерівнозначності частіше називають сумуванням за модулем 2 і позначають Y=Х1(+)Х2. Існують також функціонально повні системи, що складаються лише з однієї функції. До них, зокрема, відносяться функції І-НІ (Y= -(Х1*Х2) і АБО-НІ (Y=-(Х1+Х2)), широко використовувані при моделюванні цифрових пристроїв. Приведемо таблицю істинності функцій І-НІ і АБО-НІ двох змінних X1 і Х2.

Таблиця 4

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