Реферат на тему:
Булева алгебра. Реалізація булевых функцій.
План.
1. Поняття булевої алгебри.
2. Таблиці іcтиності.
3. Реалізація булевых функцій.
Поняття булевої алгебри.
Щоб описати схеми, які будуються шляхом сполучення різних вентилів,
потрібний особливий тип алгебри, у якій всі змінні й функції можуть
приймати тільки два значення: 0 і 1. Така алгебра називається булевою
алгеброю. Вона названа на честь англійського математика Джорджа Буля
(1815-1864). Насправді в цьому випадку ми говоримо про особливий тип
булевої алгебри, а саме про алгебру релейних схем, але термін “булева
алгебра” дуже часто використається в значенні “алгебра релейних схем”,
тому ми не будемо їх розрізняти.
Як і у звичайній алгебрі, в буревій алгебрі є свої функції. Булева
функція має одну або кілька змінних і видає результат, що залежить
тільки від значень цих змінних. Можна визначити просту функцію f,
сказавши, що f(A)=l, якщо А=0, і f(A)=0, якщо А=1. Така функція буде
функцією НЕ (див. рис. 3.2, а).
Таблиці іcтиності.
Булева функція від N змінних має тільки 2N можливих комбінацій значень
змінних, таку функцію можна повністю описати в таблицею з 2N рядками. У
кожному рядку буде даватися значення функції для різних комбінацій
значень змінних. Така таблиця називається таблицею істинності. Всі
таблиці на рис. 2 являють собою таблиці істинності. Домовимося завжди
розташовувати рядки таблиці істинності порядку номерів, тобто для двох
змінних в порядку 00, 01, 10, 11, то функцію можна полносю описати 2-х
-бітним двійковим числом, що виходить якщо зчитувати по вертикалі
колонку результатів у таблиці істинності. Таким чином, НЕ-І – це 1110,
НЕ- АБО – 1000, І – 0001 та АБО – 0111. Очевидно, що існує тільки 16
булевих функцій від двох змінних, котрим відповідають 16 можливих
4-бітних ланцюгів. У звичайній алгебрі існує нескінченне число функцій
від двох змінних, і ні одну з них не можна описати, давши таблицю
значень цієї функції.
На рис. 3(а) показана таблиця істинності для булевої функції від трьох
змінних: M = f(A, В, С). Це функція більшості, що приймає значення 0,
якщо більшість змінних дорівнює 0 та 1 якщо більшість змінних дорівнює
1. Хоча будь-яка булева функція може бути визначена за допомогою таблиці
істинності, зі зростанням кількості змінних такий тип запису стає
громіздким. Тому замість таблиць істинності часто використається інший
тип запису. Щоб побачити, яким чином здійснюється цей інший тип запису,
відмітимо що будь-яку булеву функцію можна визначити, вказавши, які
комбінації значень змінних дають значення функції 1. Для функції,
наведеної на рис. 3(а) існує 4 комбінації змінних, які дають значення
функції 1.
Малюватимемо риску над змінною, щоб показати, що її значення
інвертується. Відсутність риски означає, що значення змінної не
інвертується. Крім того, ми будемо використати знак множення (крапку),
для зазначення булевої функції „І” та + для позначення булевой функції
АБО. Наприклад, ABC приймає значення 1, тільки якщо А=1, В=0 та С=1.
АВ+ВС приймає значення 1, тільки якщо (А=1 і В=0) або (В=1 і С=0). У
таблиці на рис. 3(а) функція приймає значення 1 у чотирьох рядках: АВС,
АВС, ABC та ABC. Функція М приймає значення істини (тобто 1), якщо одне
із цих чотирьох умов істинно. Отже, ми можемо написати
М=АВС+АВС+АВС+АВС.
Це компактний запис таблиці істинності. Важливо розуміти розходження
між абстрактної булевою функцією та її реалізацією за допомогою
електронної схеми. Булева функція складається зі змінних, наприклад А, В
та С, та операторів І, АБО та НЕ. Булева функція описується за
допомогою таблиці істинності або спеціального запису, наприклад:
F=ABC+ABC;
Булева функція може реалізовуватися за допомогою електронної схеми
(часто різними способами) з використанням сигналів, які представляють
вхідні та вихідні змінні, та вентилів, наприклад – І, АБО та НЕ.
Рис. 3. Таблиця істинності для функції більшості від трьох
змінних (а); схема для цієї функції (б)
Реалізація булевых функцій.
Як було сказано вище , представлення булевої функції у вигляді суми
максимум 2N добутків дає можливість реалізації цієї функції.
На малюнку 3.3 можна побачити, як це здійснюється. На рисунку 3(б)
вхідні сигнали А, В та С показані з лівої сторони, а функція М,
отримана на виході, показана із правої сторони. Оскільки необхідні
додаткові величини (інверсії) вхідних змінних, вони утворюються шляхом
проведення сигналу через інвертори 1,2 і 3. Щоб зробити малюнок
зрозумілим, намалюємо 6 вертикальних ліній, 3 з яких пов’язані із
вхідними змінними, а 3 інших – з їхніми інверсіями. Ці лінії
забезпечують передачу вхідного сигналу до вентилів.
Схема містить чотири вентилі „І”, по одному для кожного члена в
рівнянні для М (тобто по одному для кожного рядка в таблиці істинності
з результатом 1). Кожний вентиль „І” обчислює однин із зазначених рядків
таблиці істинності. Зрештою всі дані добутків сумуються (мається на
увазі операція АБО) для одержання кінцевого результату.
На рис. 3(б) будемо використати наступне позначення: якщо дві лінії на
малюнку перетинаються, зв’язок мається на увазі тільки в тому випадку,
якщо на перетинанні зазначена жирна крапка. Наприклад, вихід вентиля 3
перетинає всі 6 вертикальних ліній, але зв’язаний він тільки із С.
З рисунка 3 бачимо як реалізувати схему для будь-якої булевой функції:
1. Скласти таблицю істинності для даної функції.
2. Забезпечити інвертори, щоб породжувати інверсії для кожного вхідного
сигналу.
3. Намалювати вентиль „І” для кожного рядка таблиці істинності з
результатом 1.
4. З’єднати вентилі „І” з відповідними вхідними сигналами.
5. Вивести виходи всіх вентилів „І” в вентиль АБО.
Таким чином реалізовується будь-яка булева функцію з використанням
вентилів НЕ, І та АБО. Однак набагато зручніше будувати схеми з
використанням одного типу вентилів. На щастя, можна легко перетворити
схеми, побудовані по попередньому алгоритмі, у форму НЕ-І або НЕ-АБО.
Щоб здійснити таке перетворення, усе, що нам потрібно, – це спосіб
втілення НЕ, І и АБО за допомогою одного типу вентилів. На малюнку 3.4
показано, як це можна зробити, використовуючи тільки вентилі НЕ-І або
тільки вентилі НЕ-АБО. Для того щоб реалізувати булеву функцію з
використанням тільки вентилій НЕ-І або тільки вентилів НЕ-АБО, можна
спочатку слідувати алгоритму, описаному вище, і сконструювати схему з
вентилями НЕ,І та АБО.
Потім потрібно замінити багатовхідні вентилі еквівалентними схемами з
використанням двохвхідних вентилів. Наприклад, A+B+C+D можна поміняти на
(A+B)+(C+D), використовуючи три двохвхідні вентилі. Потім вентилі НЕ, І
та АБО заміняються схемами, зображеними на рис. 4. Хоча така процедура
й не приводить до оптимальних схем з погляду мінімального числа
вентилів, вона демонструє, що подібне перетворення може бути здійснено.
Вентилі НЕ-І та НЕ-АБО вважаються повними, тому що можна
обчислити будь-яку булеву функцію, використовуючи тільки вентилі НЕ-І
або тільки вентилі НЕ-АБО. Жоден інший вентиль не має такої
властивості, це причиною того, що ці два типи вентилів кращі при
побудові схем.
Рис.4. Конструювання вентилів НЕ (а), І (б) та АБО (в) з використанням
тільки вентилів НЕ-І або тільки вентилів НЕ-АБО
Нашли опечатку? Выделите и нажмите CTRL+Enter
