• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Бульові функції.

Логічні елементи і мінімізація бульових функцій

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

де Bi двоїчні цифри “0” і “1”, 2 – основа системи. Наприклад, число 13 в двоїчній системі має вигляд 1101, або .

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

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

В основі булевої алгебри лежать три операції над двоїчними змінними x1; x2; …xn .

1. Логічне складання, так звана диз’юнкція чи операція АБО, позначається символами “v”, чи “+”:

2. Логічне множення, так звана кон’юнкція чи операція І, позначається символами “ ^ ” чи “.”:

3. Логічне заперечення, так звана інверсія чи операція НІ:

Правила виконування цих операцій для двох змінних мають такий вид:

Операція АБО Операція І Операція НІ

При операціях над однією змінною Х використовують такі теореми:

1. 4. 7.

2. 5. 8.

3. 6. 9.

Для двох та більше змінних використовують теореми:

10. x + y = y + x; xy = yx (переставний закон).

11. x + y + z =x + (y + z) = (x + y) +z; x ∙ y ∙ z =x(y ∙ z) = (x ∙ y)z (сполучний закон).

12. x(y + z)=xy + xz; x + yz = (x + y)(x + z) (розподільний закон).

13. x+ xy = x; x(x+y) = x (закон поглинання).

14.;

15.; (закон склеювання).

16. ; (теорема де Моргана).

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

Задати булеву функцію – значить вказати функцію (0 чи 1) при всіх можливих комбінаціях значень аргументів. Кожну конкретну комбінацію значень всіх аргументів називають набором. Для короткості набір записують у вигляді двоїчного числа, цифрами якого є значення змінних, розташованих у визначеному порядку, за звичай в алфавітному: А, В, С, D… . Наприклад, замість А=0, В=1, С=1 пишуть 011. Двоїчне число, яке представляє набір, називають номером набору. В нашому випадку 3 – третій набір.

При n аргументах існує 2ⁿ наборів, при n=3, наборів буде 8.

Якщо функція визначена на всіх наборах, така функція називається повністю визначеною; якщо на деяких наборах значення функції не задано, - частково визначеною.

Існують різні способи задання бульових функцій:

1. Представлення на словах. Наприклад, функція трьох аргументів приймає значення 1, якщо два будь-яких аргумента або усі три дорівнюють одиниці. У всіх інших випадках функція дорівнює нулю (мажоритарна функція).

2. Табличний спосіб. Функція представлена у вигляді таблиці, в якій виписуються усі можливі набори аргументів у порядку зростання їх номерів, і для кожного набору встановлюється значення функції 0 чи 1. Для мажоритарної функції це таблиця 5.1.

Таблиця 5.1

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

Якщо кожний доданок містить усі змінні чи їх заперечення, маємо першу стандартну форму або досконалу диз’юктивну нормальну форму (ДДНФ):

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

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

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

Таку процедуру називають складанням структурної формули за нулями.

4. Числовий спосіб. Для числового способу представлення функції в першій стандартній формі під знаком суми перераховуються номера наборів, на яких функція дорівнює одиниці, так для табл.5.1:

Для другої стандартної форми під знаком добутку перераховуються номера наборів, на яких функція дорівнює нулю:

Найчастіше застосовується перша форма.

Для мінімізації функції найбільш ефективним і часто використовуваним є закон склеювання й закон поглинання:

; x + xy = x, де під x, y розуміють будь-які функції. Для зручності склеювання вводять доданки, які є у вихідній структурній формулі. Наприклад, для функції:

помічаємо, що четвертий доданок АВС є сусіднім з будь-яким з перших трьох, тому додаємо його 2-а рази:

Шляхом попарного склеювання отримаємо ту ж саму функцію в іншій формі:

Рисунок 5.1 Логічна cхема до мінімізації функції 5.1.

Рисунок 5.2 Логічна cхема після мінімізації функції 5.1,формула 5.2.

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

При великій кількості змінних застосовують різні способи систематизації доданків, які полегшують їх склеювання, наприклад карти Карно. Карта Карно представляє собою прямокутик, розбитий на квадрати, кількість яких дорівнює загальній кількості наборів для даної функції для n змінних 2ⁿ набори, тобто для n = 4 їх 16. Кожний квадрат відповідає визначеному набору, причому вони розташовуються так, щоб сусідні доданки відповідали сусіднім квадратам на карті. Функцію в першій стандартній формі наносять на карту, відмічаючи знаком “1” квадрати, які відповідають тим наборам, на яких функція дорівнює одиниці, інші квадрати відмічають знаком “0” або залишають без позначки.

На рис. 5.3 показана карта Карно для чотирьох змінних.

Рисунок 5.3 Карта Карно для чотирьох змінних

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

Після нанесення одиниць на карту їх обводять контурами. Вимоги такі:

1. Контур має бути прямокутник і охоплювати кількість одиниць тільки ту, що дорівнює 2, 4, 8, 16 і т.п.

2. Одна і та ж одиниця може знаходитись в різних контурах.

3. Контури повинні бути якомога більшого розміру і їх кількість найменшою.

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

Приклад. Дана функція

Наносимо цю функцію на карту Карно (рис. 5.4) і проводимо можливі контури

Рисунок 5.4 Мінімізація бульової функції 5.3

Після склеювання із чотирьох контурів отримаємо значно простішу мінімальну бульову функцію:

Логічні елементи, які реалізують операцію АБО, називаються диз’юнкторами чи елементами АБО (рис. 5.5, а). Логічні елементи, які реалізують операцію І, називають кон’юнкторами, або елементами І (рис. 5.5, б). Елементи, які реалізують операцію НІ, називаються інверторами (рис. 5.5, в).

Рисунок 5.5. Позначення типових логічних елементів

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

Прикладами таких схем є :

1. Система, яка складається з елементів АБО та НІ.

2. Система, яка складається з елементів І та НІ.

3. Система, яка складається з одного елемента АБО-НІ.

Елемент АБО-НІ (рис. 5.5, г) реалізує функцію двох аргументів. Ця функція називається функцією АБО-НІ чи стрілкою Пірса та позначається . Функціональна повнота цієї системи доводиться тим, що через неї можна виразити всі три основні операції бульової алгебри. Дійсно,

- для операції НІ (рис. 5.6, а);

- для операції АБО (рис. 5.6, б);

- для операції І (рис. 5.6, в).

Рисунок 5.6. Використання універсального логічного елемента „АБО-НІ”

Отже, при достатній кількості елементів АБО-НІ можна будувати логічну схему будь-якої складності.

4.Система, яка складається з елементів І-НІ. Реалізуюча функція двох аргументів має вигляд Вона називається функцією Шеффера (штрих Шеффера) або функцією І-НІ і позначається F = X / Y, тобто X / Y =.

Функціональна повнота доводиться аналогічно попередньому:

Рисунок 5.7. Використання універсального логічного елемента „І-НІ”

- для операції НІ (рис. 5.7, а);

- для операції АБО (рис. 5.7, б);

- для операції І (рис. 5.7, в).

Властивості логічних елементів ЛЕ оцінюються рядом параметрів:

- статичною характеристикою передачі;

- швидкодією;

- коефіцієнтом об’єднання за входом;

- коефіцієнтом розгалуження за виходом;

- завадостійкістю;

- споживаною потужністю та ін.

Статична характеристика передачі – це залежність напруги Uвих. на виході елементу від напруги Uвх. на вході (рис. 5.8). На цьому ж рисунку позначено основні характеристики логічного елементу .

Напруга логічної одиниці U¹; напруга логічного нуля U⁰; порогова напруга логічного нуля U⁰_пор; завадостійкість статична U_зст; порогова напруга логічної одиниці U¹_пор.

Швидкодія будь-якого елементу оцінюється як середній час затримки розповсюдження сигналу tз - інтервал часу, який дорівнює півсумі часу затримки розповсюдження сигналу при вмиканні та вимиканні елемента (рис. 5.9). За швидкодією логічні елементи умовно поділяються на надшвидкодіючі (tз < 5нс), швидкодіючі (tз = 5…10нс) , з середньою швидкодією (tз = 10…50нс) та повільнодіючі (tз > 50нс).

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

Споживана потужність Рn – значення потужності, споживаної від джерела живлення в заданому режимі.

Логічні елементи в залежності від форми використовуваних у них електричних сигналів поділяються на такі групи:

- потенціальні, в яких логічному нулю та логічній одиниці відповідають два різних рівня потенціалу;

- імпульсно-потенціальні, в яких використовується як імпульсні так і потенціальні сигнали.

В залежності від типу компонентів, на яких побудовані схеми логічних елементів, розрізняють елементи з резисторно-транзисторною (РТЛ), діодно-транзисторною (ДТЛ), транзисторно-транзисторною (ТТЛ) та транзисторною (ТЛ) логікою.

В залежності від типу зв’язку між логічною схемою І та АБО і ключа інвертора розрізняють безпосередній (БЗ), резистивний (РЗ), резистивно-ємнісний (РЄЗ) та діодний (ДЗ) зв’язок.

Діодно-транзисторний логічний елемент

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

Дійсно, якщо Х₁= Х₂= Х_п=1, то вхідні діоди закриті, а вихідний транзистор VT

насичений, що відповідає F = 0. Якщо хоча б на один з входів подати логічний 0, транзистор VT стає надійно закритим (завдяки діодам VDзм1 і VDзм2), що відповідає F = 1. ДТЛ – елементи мають середню швидкодію (середній час затримки – десятки наносекунд), кількість входів не перевищує 8, навантажувальна здатність 4…6. Для підвищення навантажувальної здатності використовують складний інвертор.

Транзисторно-транзисторний логічний елемент (рис. 5.11) містить багатоемітерний транзистор (БЕТ) , фазовий інвертор (, , ),

вихідний двохтактний каскад (, ,). Якщо на всі входи елемента подати сигнал І (високий рівень потенціалу), то БЕТ працює в активному інверсному режимі: переходи ЕБ зміщені в зворотному напрямку і перехід БК – в прямому. Струм колектора БЕТ, втікаючи в базу транзистора , забезпечує його насичений стан і транзистор закривається ,а відкривається, тобто F = 0. Якщо хоча б на один зі входів подати логічний 0, то в відповідній структурі БЕТ перехід ЕБ зміщується в прямому напрямку, а перехід БК – в зворотному. Струм колектора VT1, який витікає з бази VT2, забезпечує замкнутий стан VT2, тобто на виході маємо F = 1. Отже, даний елемент реалізує функцію І-НІ.

Швидкодія ТТЛ-елементів висока (tз одиниці наносекунд), кількість входів, звичайно, не перевищує 8, навантажувальна здатність (у випадку застосування складного інвертора) може досягти 10.

Схеми на перемикачах струму(рис. 5.12) відносяться до емітерно зв’язаної транзисторної логіки (ЕЗЛ) . При надходженні на всі входи U⁰_вх<U_on, напруги яка відповідає логічному 0, всі вхідні транзистори закриті, і струм від генератора струму протікає через відкритий транзистор VT0, в результаті чого на вих2. сигнал відповідає 0 (F2 = 0), а на вих1. F1 = 1.

При надходженні хоча б на один вхід логічної І (напруга U¹_вх<U_on) відповідний транзистор відкривається і весь струм від генератора струму I0 замикається через цей транзистор,

забезпечуючи на вих1. F1 = 0, на вих2. F2 = 1. Отже, даний елемент реалізує функцію АБО/АБО-НІ

Рисунок 5.12. Емітерно зв’зана логіка

Схеми ЕЗЛ є найбільш швидкодіючими, що пояснюється малими перепадами напруги:

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

перевищує 5, навантажувальна здатність звичайно ≤ 15, але може досягати і 100 за рахунок зниження швидкодії. Недоліком ЕЗЛ є її високе споживання енергії.

Логічні схеми на польових транзисторах використовують транзистори з індуційованими каналами різного типу провідності (рис. 5.13).

Рисунок 5.13 ЛЕ „АБО-НІ”на польових транзисторах

Читайте також:

1. Банківська система: сутність, принципи побудови та функції. особливості побудови банківської системи в Україн
2. Банківська система: сутність, принципи побудови та функції. Особливості побудови банківської системи в Україні.
3. Банківська система: сутність, принципи побудови та функції. Особливості побудови банківської системи в Україні.
4. Вартість робочої сили. Заробітна плата, її форми і функції.
5. Види речень в ділових паперах та їх стилістичні функції.
6. Види речень в ділових паперах та їх стилістичні функції.
7. Вказівники на функції. Масиви вказівників на функції
8. Границя функції. Означення границі функції за Гейне й за Коші.
9. Гроші, їх функції.
10. Державне регулювання економіки: поняття, необхідність, функції. Об’єкти та суб’єкти ДРЕ
11. Диференціал функції.

Переглядів: 1968