Щоб описати схеми, одержувані поєднанням різних вентилів, потрібен особливий тип алгебри, в якій всі змінні і функції можуть приймати тільки два значення: 0 і 1. Така алгебра називається булевої. Вона названа на честь англійського математика Джорджа Буля (1815-1864). Насправді в даному випадку ми говоримо про особливий тип булевої алгебри, а саме - про алгебри релейних схем, але термін «булева алгебра» дуже часто використовується в значенні «алгебра релейних схем», тому ми не будемо їх розрізняти.
Як і в звичайній алгебрі (тобто в тій, яку вивчають в школі), у булевої алгебри є свої функції. Булева функція на вході отримує одну або кілька змінних і видає результат, який залежить тільки від значень цих змінних. Можна визначити просту функцію F, сказавши, чтоF (A) = 1, якщо А = 0, іF (А) = 0, якщо А = 1. Така функція буде функцією НЕ (див. Рис. 3.2, а).
Так як булева функція від nпеременних має тільки 2nвозможних комбінацій значень змінних, то таку функцію можна повністю описати в таблиці з 2nстрокамі. У кожному рядку буде даватися значення функції для різних комбінацій значень змінних. Така таблиця називається таблицею істинності. Всі таблиці на рис. 3.2 представляють собою таблиці істинності.
Якщо ми домовимося завжди розташовувати рядки таблиці істинності своєю чергою номерів, тобто для двох змінних в порядку 00, 01, 10, 11, то функцію можна повністю описати 2n-розрядних двійковим числом, яке виходить, якщо зчитувати по вертикалі колонку результатів в таблиці істинності . Таким чином, НЕ-І - це 1110, НЕ-АБО - 1000, І - 0001 і АБО - 0111. Очевидно, що існують тільки 16 булевих функцій від двох змінних, яким відповідають 16 можливих 4-розрядних ланцюжків. У звичайній алгебрі, навпаки, є нескінченне число функцій від двох змінних, і жодну з них не можна описати, давши таблицю значень цієї функції для всіх можливих значень вхідних змінних, оскільки кожна змінна може приймати нескінченне число значень.
На рис. 3.3, а показана таблиця істинності для булевої функції від трьох змінних: М = F (A, B, С). Це функція більшості, яка приймає значення 0, якщо більшість змінних рівні 0, або 1, якщо більшість змінних рівні 1. Хоча будь-яка булева функція може бути визначена за допомогою таблиці істинності, зі зростанням кількості змінних такий тип запису стає громіздким. Тому замість таблиць істинності часто використовується інший варіант запису.
Щоб побачити цей інший тип запису, відзначимо, що будь-яку булеву функцію можна визначити, вказавши, які комбінації значень вхідних змінних призводять до одиничному значенню функції. Для функції, наведеної на рис. 3.3, а, існує 4 комбінації змінних, які дають середнє арифметичне значення функції. Ми будемо малювати межу над змінної, показуючи, що її значення інвертується. Відсутність межі означає, що значення змінної не інвертується.
Крім того, ми будемо використовувати знак множення (точку) для позначення булевої функції І (цей знак може опускатися) і знак складання (+) для позначення булевої функції АБО. Наприклад, AВС приймає значення 1, тільки есліA = 1, B = 0 і С = 1. Крім того, АВ + ВС приймає значення 1, тільки якщо (А = 1 і В = 0) або (В = 1 і С = 0). У таблиці на рис. 3.3, а функція приймає значення 1 в чотирьох рядках:
Розробники схем часто намагаються скоротити число вентилів, щоб знизити ціну, зменшити займане схемою місце, скоротити споживання енергії і т. Д. Щоб спростити схему, розробник повинен знайти іншу схему, яка може обчислювати ту ж функцію, але при цьому вимагає меншої кількості вентилів ( або може працювати з більш простими вентилями, наприклад, двухвходових замість чотиривходових). Булева алгебра є цінним інструментом в пошуку еквівалентних схем.
