Подання булевих функцій формулами можна надати наступний "інженерно-конструктивний" зміст. Розглянемо формулу над якимось довільно фіксованим безліччю як "чорний ящик", якийсь пристрій, на вхід якого подаються всілякі набори значень змінних, а на виході з'являються відповідні цим наборам значення функції, представленої формулою (рис. 6.22).
Щоб зрозуміти, як влаштовано "чорну скриньку", ми повинні розібрати процес побудови формули з підформул. Добираючись до " базових " підформул, тобто. елементів множини , ми приходимо до "цеглинок", структурних елементів, з яких зібраний "чорний ящик", що обчислює функцію . Кожна функція "базису" обчислюється відповідним "вузлом", який розглядається як найдрібніша структурна одиниця нашої "чорної скриньки", та її внутрішня структура вже не аналізується.
Приклад 6.22.Виберемо як безліч стандартний базис. Тоді формула над стандартним базисом, що представляє функцію (еквівалентність), будується так:
Обчислення за цією формулою (і процес її побудови з елементів стандартного базису) можна схематично зобразити так, як показано на рис. 6.23.
Змінне (точніше значення цього змінного) подається на вхід структурного елемента, званого інвертором (рис. 6.24, а) і обчислює заперечення. Знімається з виходу інвертора заперечення, тобто. функція , що подається на один із входів кон'юнктора (рис. 6.24,5), на другий вхід якого подається змінне . На виході кон'юнктора з'являється функція. Аналогічно простежується обчислення функції. Обидві ці функції подаються на входи диз'юнктора (рис. 6.24 в), з виходу якого знімається функція (це не що інше, як сума за модулем 2: ). І, нарешті, ця функція подається на вхід інвертора, на виході якого вже виходить функція (еквівалентність).
Таким чином, ми приходимо до ідеї "схеми" - математичної моделі обчислювача булевої функції, представленої деякою формулою, зібраного із структурних елементів, кожен з яких обчислює одну з "базових" булевих функцій. У загальному випадку "схема" обчислює булев оператор, причому кожна координатна функція цього оператора знімається з одного з виходів схеми.
Математично "схема" визначається як орієнтований граф спеціального виду, в якому і вершини, і дуги мають деякі мітки.
Введемо позначення: якщо - якась множина булевих функцій, то через позначаємо підмножину, що складається з усіх функцій від змінних.
Визначення 6.14. Нехай фіксовані безлічі: (бульових функцій) та (бульових змінних).
Схемою з функціональних елементів над базисом (СФЕ), або просто схемою над базисом , також (F,X)-схемою називають безконтурний орієнтований граф (тобто мережа), кожна вершина якого позначена одним з елементів множини так, що виконуються наступні вимоги:
1) кожен вхід мережі позначений або деяким змінним з або деякою константою з ;
2) якщо вершина v мережі позначена функцією від змінних (тобто ), її півступінь заходу дорівнює , причому на безлічі дуг, що входять у вершину , задана (взаємно однозначна) нумерація, коли кожна дуга отримує номер від 1 до .
При зображенні схем входи позначаються кружальцями, а вершини, які є входами, - трикутниками, всередині яких записано позначення функції, позначає цю вершину. Виходи відзначаються "вихідними" стрілками. На рис. 6.25 наведено СФЕ над базисом.
Якщо базис мається на увазі, ми говоритимемо просто " схема " . Крім того, якщо безліч змінних фіксовано "раз і назавжди" і при розгляді різних схем ми змінюємо тільки безліч функцій, то, як це ми робили, вводячи поняття формули та суперпозиції над заданим базисом, говоритимемо про СФЕ над базисом, вважаючи щоразу, що мається на увазі якось фіксоване безліч змінних , яке (якщо це шкодить точності) не згадується.
Визначимо тепер по індукції поняття булевої функції, що обчислюється вершиною схеми.
Визначення 6.15. Нехай задана СФЕ над базисом, безліч вершин якої є.
1. Приймається, що кожен вхід СФЕ обчислює булеву функцію, якою він позначений (тобто деяке змінне чи константу).
2. Якщо вершина позначена функцією дуга з номером, що входить до неї, виходить з вершини, яка обчислює функцію, то вершина v обчислює суперпозицію.
Отже, якщо кожна вершина СФЭ над обчислює деяку функцію, то порядок, у якому перераховуються функції , підставлювані місця змінних функції , у випадку істотний. Природно назвати булеву функцію від змінних комутативною, якщо вона зберігає значення при довільній перестановці її змінних. У цьому випадку ми можемо не дбати про нумерацію дуг, що заходять у вершину схеми, позначену такою функцією.
Приклад 6.23.Розглянемо СФЕ на рис. 6.25. Вершини та - входи СФЕ. Ці вершини обчислюють відповідно до функції і . Тоді вершина , як і вершина , згідно з визначенням 6.15, обчислює функцію (штрих Шеффера), а вершина (вихід мережі) - функцію , яка, як відомо, дорівнює кон'юнкції .
СФЕ, зображена на рис. 6.26, має два виходи, що обчислюють функції та .
Визначення 6.16. Бульова функція, що обчислюється СФЕ над базисом , - це функція, що обчислюється якимсь із її виходів.
Таким чином, СФЕ обчислює рівно стільки булевих функцій, скільки має виходи. СФЕ на рис. 6.25 обчислює одну функцію, а СФЕ на рис. 6.26 – дві.
У випадку, якщо - безліч всіх змінних, які є мітками входів схеми над базисом , має га виходів, СФЕ визначає відображення булева куба в булев куб , тобто. булев оператор.
Зауваження 6.10.У деяких випадках функцію, що обчислюється даною СФЕ, визначають дещо інакше, вважаючи, що це функція, що обчислюється будь-якою вершиною з підмножини виділених вершин СФЕ. Зокрема це можуть бути і виходи. У будь-якому разі домовимося з виділених (у щойно зазначеному сенсі) вершин схеми проводити "вихідну" стрілку.
Таким чином, кожна схема з функціональних елементів обчислює деякий булев оператор, зокрема, якщо число виходів схеми дорівнює 1, то вона обчислює деяку булеву функцію.
Можна довести і зворотне: за будь-яким булевим оператором може бути побудована СФЕ над базисом , де - повна множина, що обчислює даний оператор.
Приклад 6.24.Задамо таблицею булев оператор, що відображає (табл. 6.9).
З таблиці легко побачити, що (функція є нічим іншим, як мажоритарна функція від змінних , і вище написана мінімальна ДНФ нею, див. приклад 6.12). Уявімо функцію в базисі Жегалкіна. Використовуючи закони де Моргана, отримаємо
Враховуючи, що , будемо мати
(нагадаємо, що сума за модулем 2 будь-якого парного числа рівних доданків дорівнює 0). Отже,
СФЕ для булева оператора, заданого в табл. 6.9 над базисом Жегалкіна наведена на рис. 6.27.
При проектуванні СФЕ корисно пам'ятати числовий параметр, званий її складністю.
Складність СФЕ - це її вершин, які є входами.
Наведена на рис. 6.27 СФЕ над базисом Жегалкіна має складність 5.
Розглянемо тепер СФЕ того самого оператора над стандартним базисом. По таблиці (див. табл. 6.9) будуємо СДНФ для функції
Карна Карно для цієї функції, зображена на рис. 6.28 показує, що її не можна мінімізувати (точніше, записана вище СДНФ і є мінімальна ДНФ для цієї функції).
Але можна піти іншим шляхом. Ми можемо розглядати таблицю. 6.9 як таблицю, що визначає часткову булеву функцію . Мінімізуючи цю функцію картою Карно*, зображеної на рис. 6.29, отримуємо
*На цій карті ми явно позначили набори, на яких функція набуває значення 0, проставивши нулі у відповідних клітинах. Тим самим ми хочемо ще раз зафіксувати увагу на тому, що не слід плутати нулі з прочерками: прочерк у клітці карти, що задає часткову функцію, означає, що у цьому наборі значення функції визначено, тобто. не дорівнює ні 0, ні 1.
СФЕ над стандартним базисом для розглянутого булева оператора наведено на рис. 6.30. Складність цієї СФЕ становить 11. Зауважимо, що вершина, що обчислює функцію, не є виходом.
Булев оператор, розглянутий у цьому прикладі, обчислює дворозрядну суму (за модулем 2) трьох однорозрядних доданків. Його можна вважати також однорозрядним двійковим суматором – функціональним блоком багаторозрядного двійкового суматора – для двох доданків. Тоді функція г/1 інтерпретується як сигнал перенесення в старший розряд. На рис. 6.31 зображено "з'єднання" трьох СФЕ (таких, як показано на рис. 6.30), за допомогою якого обчислюється сума двох трирозрядних двійкових чисел. На третій вхід суматора для молодшого розряду подається константа 0, а сигнал перенесення старшого розряду є старший розряд суми, яка в загальному випадку буде чотирирозрядним числом.
31. Схеми з функціональних елементів, правила побудови та функціонування, метод синтезу фе, заснований на сднф та скнф.
ВизначенняВизначення.Функціональний елемент – це математична модель елементарного дискретного перетворювача, який за певним законом здійснює перетворення вступників на вхід сигналів у сигнал на виході перетворювача. З функціональних елементів за допомогою деяких правил можна будувати складніші за структурою та функціонуванням моделі – схеми з функціональних елементів. У цих моделях вхідні та вихідні сигнали кодуються символами 0 та 1.
Правила побудови.Для отримання складних СФЕ з більш простих до них послідовно застосовують операції розщеплення входу або виходу схеми, приєднання функціонального елемента до схеми і підключення функціонального елемента до входу або виходу схеми. Ці операції нагадують правила отримання складної формули більш простих за допомогою суперпозиції.
Синтез СФЕ.Оскільки диз'юнкція, кон'юнкція та заперечення утворюють повну системув класі Р 2 , то будь-яку булеву функцію від nаргументів можна реалізувати схемою з функціональних елементів – диз'юнкторів, кон'юнкторів та інверторів – з nвходами та одним виходом. Для цього можна, наприклад, виразити цю булеву функцію через СДНФ або СКНФ і потім синтезувати отриману формулу у вигляді схеми з функціональних елементів, послідовно застосовуючи перераховані вище операції розщеплення, приєднання і підключення.
32. Метод синтезу сфери, заснований на компактній реалізації всіх кон'юнкцій за допомогою універсального багатополюсника, складність одержуваних схем.
Визначення. Функція відnаргументів називається булевою функцією (або функцією алгебри логіки), якщо кожному набору вона ставить у відповідність число.
Для завдання булевих функцій ми будемо використовувати таблиці, вектори, формули та графіки. Приймемо таке позначення: це безліч всіх наборів, де.
Визначення.Функціональний елемент – це математична модель елементарного дискретного перетворювача, який за певним законом здійснює перетворення вступників на вхід сигналів у сигнал на виході перетворювача. З функціональних елементів за допомогою деяких правил можна будувати складніші за структурою та функціонуванням моделі – схеми з функціональних елементів. У цих моделях вхідні та вихідні сигнали кодуються символами 0 та 1.
Метод синтезу СФЕ, що базується на компактній реалізації всіх кон'юнкцій за допомогою універсального багатополюсника. Даний метод також ґрунтується на поданні функції у вигляді СДНФ, але дозволяє будувати менш складні схеми за рахунок компактнішої реалізації кон'юнкцій. Розкладання функції СДНФ може містити кон'юнкції, що мають загальні множники. Якщо дві таких кон'юнкції реалізувати однією підсхемою в блоці, то для цього потрібно кон'юнкторів хоча б на одиницю менше, ніж їх потрібно раніше, за незалежної реалізації всіх кон'юнкцій першим методом синтезу. Компактної реалізації всіх можливих кон'юнкцій довжини nможна досягти за допомогою індуктивно побудованого універсального багатополюсника, що має nвходів та 2 n виходів, де n = 1,2,3,… Переваги методу особливо помітні, коли схемою потрібно реалізувати систему з кількох булевих функцій. У цьому випадку можна було б розщепити і далі пропустити через диз'юнктори ті виходи багатополюсника універсального, які відповідають кон'юнкціям, що входять в СДНФ функцій заданої системи. Це дозволило б обійтися меншою кількістю кон'юнкторів, ніж якби кожну функцію заданої системи реалізували незалежно своєю власною підсхемою.
Складність такого багатополюсника дорівнює L() =.
Якщо схема з функціональних елементів містить рівно rфункціональних елементів, то кажуть, що вона має складність rі записують це у вигляді рівності L(Σ) = r.
| " |
Лекція 2. Схеми із функціональних елементів
(СФЕ) у деякому базисі. Складність та глибина
схеми. приклади. Метод синтезу СФЕ з ДНФ.
Лектор – доцент Селезньова Світлана Миколаївна
Лекції з “Дискретної математики 2”.
1-й курс, група 141,
факультет ВМК МДУ імені М.В. Ломоносова
Лекції на сайті http://mk.cs.msu.su
СФЕ Приклади Синтез СФЕ з ДНФ
Схеми із функціональних елементів
Визначимо схеми із функціональних елементів у деякому базисі.
Нехай нам задано деяку множину булевих функцій B = (g1 (x1, ..., xn1), ..., gs (x1, ..., xns)) P2 де n1, ..., ns 0.
Назвемо це безліч базисом.
Зауважимо, що це поняття базису не пов'язане з поняттям базису P2, яке розглядалося в алгебрі логіки.
Як правило, ми розглядатимемо стандартний базис B0 = (x&y, x y, x).
СФЕ Приклади Синтез СФЕ за ДНФ Визначення схеми з функціональних елементів Схема з функціональних елементів (СФЕ) у базисі B0 = (x&y, x y, x) – це
1) орієнтований ациклічний граф G = (V, E), кожна вершина v V якого має півступінь заходу d (v), що не перевищує двох (d (v) 2);
2) кожна вершина v з напівступенем заходу, що дорівнює 0 (d (v) = 0), називається вхідний (або входом схеми) і їй приписується деяка булева змінна xi;
3) усі інші вершини (крім входів) називаються внутрішніми вершинами схеми;
4) кожній вершині v з півступенем заходу, що дорівнює 1 (d (v) = 1) приписується (функціональний) елемент заперечення; усі такі вершини називаються інверторами;
5) кожній вершині v з півступенем заходу, що дорівнює 2 (d (v) = 2) приписується або (функціональний) елемент кон'юнкції &, або (функціональний) елемент диз'юнкції; всі вершини, яким приписані елементи кон'юнкції, називаються кон'юнкторами; всі вершини, яким приписані елементи диз'юнкції, називаються диз'юнкторами;
СФЕ Приклади Синтез СФЕ з ДНФ Визначення схеми із функціональних елементів (продовження)
6) крім того, деяким з вершин приписані попарно різні вихідні змінні y1,..., ym.
Якщо задана СФЕ S, входам якої приписані тільки змінні x1,..., xn, і з вихідними змінними y1,..., ym, то будемо позначати цю СФЕ через S(x1,..., xn; y1,. ., ym).
СФЕ Приклади Синтез СФЕ з ДНФ
– – –
Визначення глибини вершини СФЕ За індукцією визначимо глибину d(v) вершини v СФЕ S.
1. Базис індукції. Кожен вхід v СФЕ S має глибину, що дорівнює 0: d(v) = 0.
– – –
СФЕ та його характеристики Схеми з функціональних елементів є обчислювальної моделлю.
Введені нами характеристики СФЕ показують різні аспекти ефективності обчислень.
Складність СФЕ відповідає часу послідовного обчислення.
Глибина СФЕ відповідає часу паралельного обчислення.
Максимальна кількість вершин з однаковою глибиною в СФЕ відповідає кількості процесорів при паралельному обчисленні.
СФЕ Прімери Синтез СФЕ по ДНФ Приклад: сума трьох біт Рішення. Аналогічно прикладу 6 запишемо таблицю суми трьох бітів x, y та z. Ця сума може бути числом теж із двома двійковими розрядами, тому введемо дві булеві змінні
u0, u1, такі, що x + y + z = 2u1 + u0:
– – –
Література до лекції 4
1. Яблонський С.В. Введення у дискретну математику. М.:
Вища школа, 2001. Ч. V, гол. 2, с. 336-355.
2. Гаврилов Г.П., Сапоженко О.О. Завдання та вправи з дискретної математики. М.: Фізматліт, 2004. Гол. X 1.1, 1.5, 1.7, 1.17, 1.18.
СФЕ Приклади Синтез СФЕ з ДНФ
Подання булевих функцій формулами можна надати наступний "інженерно-конструктивний" зміст. Розглянемо формулу Ф(x 1 ,..., x n) над якимось довільно фіксованим безліччю F як "чорний ящик", якийсь пристрій, на вхід якого подаються всілякі набори значень змінних, а на виході з'являються відповідні цим наборам значення функції f , що подається формулою Ф (рис. 6.22).
Щоб зрозуміти, як влаштовано "чорну скриньку", ми повинні розібрати процес побудови формули з підформул. Добираючись до " базових " підформул, тобто. елементів множини F, ми приходимо до "цеглинок", структурних елементів, з яких зібраний "чорний ящик", що обчислює функцію f. Кожна функція "базису" F обчислюється відповідним "вузлом", який розглядається як найдрібніша структурна одиниця нашої "чорної скриньки", та її внутрішня структура вже не аналізується.
Приклад 6.22.Виберемо як безліч F стандартний базис. Тоді формула над стандартним базисом, що представляє функцію ~ (еквівалентність), будується так:
Обчислення за цією формулою (і процес її побудови з елементів стандартного базису) можна схематично зобразити так, як показано на рис. 6.23.
Змінне х 1 (точніше значення цього змінного) подається на вхід структурного елемента, званого інвертором (рис. 6.24, а) і обчислює заперечення. Знімається з виходу інвертора заперечення х 1 , тобто. функція x 1 подається на один із входів кон'юнктора (рис. 6.24 б), на другий вхід якого подається змінне х 2 . На виході кон'юнктора з'являється функція х 1 х 2 . Аналогічно простежується обчислення функції х 1 x 2 Обидві ці функції подаються на входи диз'юнктора (рис. 6.24, в), з виходу якого знімається функція х 1 x 2 ∨ х 1 x 2 (це не що інше, як сума за модулем 2: х 1 ⊕ х 2). І, нарешті, ця функція подається на вхід інвертора, на виході якого вже виходить функція ~ (еквівалентність). #
Таким чином, ми приходимо до ідеї "схеми" - математичної моделі обчислювача булевої функції, представленої деякою формулою, зібраного із структурних елементів, кожен з яких обчислює одну з "базових" булевих функцій. У загальному випадку "схема" обчислює булев оператор, причому кожна координатна функція цього оператора знімається з одного з виходів схеми.
Математично "схема" визначається як орієнтований граф спеціального виду, в якому і вершини, і дуги мають деякі мітки.
Введемо позначення: якщо F - якась множина булевих функцій, то через F(n) позначаємо підмножину F, що складається з усіх функцій від n змінних (n≥0).
Визначення 6.14.Нехай фіксовані множини: F (булевих функцій) і Х (булевих змінних).
Схема з функціональних елементів над базисом F ∪ X (С Ф Е), або просто стиснутої над базисом F ∪ X, також (F,Х)-схемою, називають безконтурний орієнтований граф (тобто мережа), кожна вершина якого позначена одним з елементів множини F U Х так , що виконуються такі вимоги:
- кожен вхід мережі позначений або деяким змінним з Х або деякою константою з F (0) ;
- якщо вершина v мережі позначена функцією f від n змінних (тобто f ∈ F(n)), то її півступінь заходу дорівнює n, причому на безлічі дуг, що заходять у вершину v, задана (взаємно однозначна) нумерація, при якій кожна Дуга отримує номер від 1 до n.
Якщо базис мається на увазі, ми говоритимемо просто " схема " . Крім того, якщо безліч змінних фіксовано "раз і назавжди" і при розгляді різних схем ми змінюємо тільки безліч функцій F, то, як це ми робили, вводячи поняття формули та суперпозиції над заданим базисом, говоритимемо про СФЕ над базисом F, вважаючи кожен раз, що мається на увазі якось фіксована безліч змінних Х, яка (якщо це не шкодить точності) не згадується.
Визначимо тепер з індукції поняття бульової функції, що обчислюється вершиною схеми .
Визначення 6.15.Нехай задана СФЕ S над базисом F ∪ Х, множина вершин якої є V.
- Приймається, що кожен вхід СФЕ обчислює булеву функцію, якою він позначений (тобто деяке змінне чи константу).
- Якщо вершина v ∈ V позначена функцією f ∈ F (n) , дуга з номером i (1≤i≤n), що входить до неї, виходить з вершини u i ∈ V, яка обчислює функцію g i , то вершина v обчислює суперпозицію f(g 1 , ..., gn).
Отже, якщо кожна вершина СФЭ над F обчислює деяку функцію, то порядок, у якому перераховуються функції g 1 , ... ,g n , підставлюються місця змінних функції f, у випадку істотний. Природно назвати булеву функцію f від n змінних комутативною, якщо вона зберігає значення при довільній перестановці її змінних. У цьому випадку ми можемо не дбати про нумерацію дуг, що заходять у вершину схеми, позначену такою функцією.
Приклад 6.23.Розглянемо СФЕ на рис. 6.25. Вершини v 1 і v 2 – входи СФЕ. Ці вершини обчислюють відповідно до функції х і у. Тоді вершина v 3 , так само як і вершина v 4 згідно з визначенням 6.15, обчислює функцію x|y (штрих Шеффера), а вершина v 5 (вихід мережі) - функцію (x|y)l(x|y), яка, як відомо, дорівнює кон'юнкції х · у.
СФЕ, зображена на рис. 6.26 має два виходи, що обчислюють функції (x|x)|(y|y) =x ∨ y і (x|y)|(x|y) =х·у.
Визначення 6.16. Бульова функція, що обчислюється СФЕ над базисом F ∪ Х, - це функція, яка обчислюється будь-яким з її виходів.
Таким чином, СФЕ обчислює рівно стільки булевих функцій, скільки має виходів. СФЕ на рис. 6.25 обчислює одну функцію, а СФЕ на рис. 6.26 – дві.
У випадку, якщо (x 1 ,..., x n ) - безліч всіх змінних, які є мітками входів схеми S над базисом F ∪ Х, що має m виходів, СФЕ S визначає відображення бульова куба B n в булев куб B m, тобто. булев оператор.
Зауваження 6.10.У деяких випадках функцію, що обчислюється даною СФЕ, визначають дещо інакше, вважаючи, що це функція, що обчислюється будь-якою вершиною з підмножини виділених вершин СФЕ. Зокрема це можуть бути і виходи. У будь-якому разі домовимося з виділених (у щойно зазначеному сенсі) вершин схеми проводити "вихідну" стрілку. #
Таким чином, кожна схема з функціональних елементів обчислює деякий булев оператор, зокрема, якщо число виходів схеми дорівнює 1, то вона обчислює деяку булеву функцію.
Можна довести і зворотне: за будь-яким булевим оператором може бути побудована СФЕ над базисом F, де F - повна множина, що обчислює даний оператор.
Представимо функцію y 1 у базисі Жегалкіна. Використовуючи закони де Моргана, отримаємо
(нагадаємо, що сума за модулем 2 будь-якого парного числа рівних доданків дорівнює 0).
y 1 = х 1 х 2 ⊕ х 1 х 3 ⊕ х 2 х 3 = х 1 х 2 ⊕ х 3 (х 1 ⊕ х 2).
СФЕ для булева оператора, заданого в табл. 6.9 над базисом Жегалкіна наведена на рис. 6.27.
При проектуванні СФЕ корисно пам'ятати числовий параметр, званий її складністю.
Складність СФЕ - це число її вершин, які є входами.
Наведена на рис. 6.27 СФЕ над базисом Жегалкіна має складність 5.
Розглянемо тепер СФЕ того самого оператора над стандартним базисом.
По таблиці (див. табл. 6.9) будуємо СДНФ для функції y 2:
y 2 = x 1 x 2 х 3 ∨ x 1 х 2 x 3 ∨ х 1 x 2 x 3 ∨ х 1 х 2 х 3 .
Карна Карно для цієї функції, зображена на рис. 6.28 показує, що її не можна мінімізувати (точніше, записана вище СДНФ і є мінімальна ДНФ для цієї функції). Але можна піти іншим шляхом. Ми можемо розглядати таблицю. 6.9 як таблицю, що визначає часткову булеву функцію y 2 = y 2 (х 1 х 2 х 3 y 1). Мінімізуючи цю функцію по
карті Карно*, зображеної на рис. 6.29, отримуємо
* На цій карті ми позначили набори, на яких функція набуває значення 0, простовив нулі у відповідних клітинах. Тим самим ми хочемо ще раз зафіксувати увагу на тому, що не слід плутати нулі з прочерками: прочерк у клітці карти, що задає часткову функцію, означає, що у цьому наборі значення функції визначено, тобто. не дорівнює ні 0, ні 1.
y 2 = х 1 х 2 х 3 ∨ y 1 (х 1 ∨ х 2 ∨ х 3).
СФЕ над стандартним базисом для розглянутого булева оператора наведено на рис. 6.30. Складність цієї СФЕ становить 11. Зауважимо, що вершина, що обчислює функцію y 1 не є виходом.
Булев оператор, розглянутий у цьому прикладі, обчислює дворозрядну суму (за модулем 2) трьох однорозрядних доданків. Його можна вважати також однорозрядним двійковим суматором – функціональним блоком багаторозрядного двійкового суматора – для двох доданків. Тоді функція y 1 інтерпретується як "сигнал перенесення" у старший розряд. На рис. 6.31 зображено "з'єднання" трьох СФЕ (таких, як показано на рис. 6.30), за допомогою якого обчислюється сума двох трирозрядних двійкових чисел. На третій вхід суматора для молодшого розряду подається константа 0, а сигнал перенесення старшого розряду є старший розряд суми, яка в загальному випадку буде чотирирозрядним числом.
Зауваження 6.11.Якщо ми проектуємо СФЕ над стандартним базисом та хочемо мінімізувати її складність, то нам необхідно насамперед побудувати відповідну мінімальну ДНФ. У цьому випадку ми можемо взяти до уваги ще один критерій, за яким мінімізується сама ДНФ, - кількість заперечень. Серед усіх мінімальних (у сенсі визначення 6.6) ДНФ слід відібрати ті, у яких кількість змінних вхідних під знаком заперечення є найменшою. З точки зору складності СФЕ, яка буде побудована за мінімальною ДНФ, це означає, що в ній мінімізується кількість "інверторів" - вершин СФЕ, позначених функцією заперечення.
Наприклад, для функції, заданої картою Карно (рис. 6.32), до ядра, що складається з простих імплікант х 1 х 2 х 4 і x 1 х 3 x 4 слід додати просту імпліканту х 2 х 3 х 4 , а не x 1 х 2 х 3 оскільки вона не містить заперечень.
Функціональні схеми (ФС) призначені перетворення логічної інформації. Вихідна інформація, закодована у вигляді дискретних сигналів, подається на входи схеми `х n. Потім дана інформаціяпереробляється та в дискретній формі зчитується з виходів схеми `у m(n, m– числа її входів та виходів). Розглянемо ФС, що функціонують у двозначній логіці та мають один вихід ( m=1). Перетворення інформації в них може бути задано у вигляді алгебри функції логіки у=f(х n). Замість релейних елементів ФС використовуються функціональні елементи (ФЕ), що реалізують, як правило, елементарні логічні функції.
Визначення.Аналізомназивається побудова формули алгебри логіки (якщо необхідно – її таблиці істинності) за заданою ФС.
Для побудови формули за заданою схемою необхідно зв'язки між ФЕ у ФС подати у вигляді підстановок у відповідні елементарні функції. При цьому передбачається, що переробка інформації провадиться поетапно від входів до виходів. У реальних схемах задля забезпечення тимчасового узгодження роботи всіх ФС використовують додаткові елементи.
Аналіз ФС можна виконувати двома способами - від входів до виходів та від виходів до входів. Розглянемо перший спосіб, застосовуючи додаткові позначення проміжних сполук схеми.
приклад 1.Як ФЕ прийняті (&, Ú, Ø). Провести аналіз ФС, фізична структура якої дана на рис.1.19.
Рішення.Позначивши проміжні з'єднання ФЕ так, як показано на малюнку, кроками визначаємо сигнали, що відповідають їм . При цьому переміщуємось від входів схеми до її виходу.
Рис.1.19
КРОК 1. R=`y, Q = `z.
КРОК 2. X=x&R= x&`y, P=x& y, W=P&Q= x&y&`z.
КРОК 3. Y=X&z=x&`y& z, U=P&z = x&y&z.
КРОК 4. Z = YÚ U=x&`y&zÚ x&y&z.
КРОК 5. F = ZÚ W=x&`y& zÚ x&y&zÚ x&y&`z.
Таким чином, розглянута ФС реалізує наступну алгебри формулу логіки:
F(x,y,z) = x&`y&zÚ x&y&zÚ x&y&`z.
Знайдена формула є СДНФ. Вектор її значень істинності має вигляд (00000111). .
Залежно від вихідних даних серед завдань синтезу (проектування) ФС можна виділити:
1) синтез схем за заданими формулами,
2) синтез схем за заданими функціями.
Визначення.Синтезом ФС за заданою формулоюназивають побудову структури ФС, що відповідає заданій формулі алгебри логіки.
Вирішення подібних завдань здійснюється за алгоритмом, зворотним методом аналізу. Як зазначено в параграфі 1.7, структура алгебри формул логіки дозволяє ізоморфно відобразити тільки системи з паралельними і послідовними сполукамиелементів. Тому у ФС, що ізоморфно відповідає формулі, повинні бути тільки сполуки даного виду.
Визначення.Синтезом ФС щодо заданої функціїназивають побудову структурної схеми, що реалізує задану функцію логіки алгебри.
Оскільки уявлення функцій формулами неоднозначно, це завдання має єдине рішення. Як і у разі релейних схем, оптимальними є ФС, що складаються з мінімальної кількості ФЕ та з'єднань між ними. Такі ФС можна одержати, використовуючи формули з мінімальним числом змінних.
Як і для РС, окремо розглядатимемо формули, оптимальні в класі нормальних форм(які рівні відповідним мінімальним формам), і навіть абсолютно оптимальні формули, одержувані з мінімальних нормальних форм їх подальшого скорочення із застосуванням законів алгебри логіки. Способи отримання оптимальних формул – ті ж, що у релейних схемах. У Прикладі 1 розглядається ФС, що реалізує функцію (00000111) . Ця ФС не оптимальна, оскільки відповідна їй формула описує СДНФ F = x`y z Ú x y zÚ x y`zяка не є мінімальною. Мінімізуючи її, отримаємо МДНФ такого виду: F = x yÚ x z.Їй відповідає ФС на рис.1.20
Рис.1.20
Якщо застосувати дистрибутивний закон до МДНФ, то отримаємо формулу із ще меншим числом змінних: f = x(yÚ z). Для цієї функції вона збіглася з МКНФ. Їй відповідає абсолютно оптимальна схема
Рис.1.21
Вочевидь, ця схема значно простіше вихідної (рис.1.19). Оскільки синтез оптимальних ФС зводиться до побудови мінімальних формул, то аналогічно будуються оптимальні схеми та інших базисах. Аналоги першого і другого дистрибутивних законів логіки алгебри для шефферових і веббових форм можна отримати, замінюючи в даних законах:
&(x,y)= Ø ½ ( x,y) = ¯ (Ø x,Ø y);
Ú ( x,y)= ½ (Ø x, Ø y) =Ø ¯ ( x,y).
приклад 2.Побудувати ФС, що реалізує однорозрядний двійковий суматор двох чисел за допомогою ФЕ, що відповідають базису (?,?), А також у базисі (?).
Рішення.Позначимо однорозрядні двійкові числа, що подаються на вхід через ( х,у). На виході має бути отримана їх сума двійковій системі. Якщо х= 1, у = 1, то S = 2 10 = 10 2 тому для зображення її в загальному випадку необхідно використовувати два двійкових знаки, а ФС повинна мати два виходи. Позначимо їх f(старший розряд суми) та g(Молодший розряд). Таблиці істинності функцій f (х,у),g(х,у):
| x | y | f(x,y) | g(x,y) |
Будуємо СВНФ функцій у базисі (?,?). fмає у векторі істинності одну одиницю, тому її форма складається з однієї конституенти: f=¯ (Ø х,Ø у). У функції gСВНФ має вигляд: g=د(¯( х,Ø у),¯(Ø х,у)). Ці форми є мінімальними. При об'єднанні входів елементів функціональну схему можна подати у такому вигляді:
Рис.1.22
У розглянутому прикладі неможливе спрощення веббових нормальних форм за допомогою законів логіки алгебри. В однофункціональному базисі (¯) ФС отримаємо, застосовуючи підстановку Ø х= ¯ ( х,х). Відповідна схема дана на рис.1.23.
Рис.1.23
ЗАВДАННЯ
1. Побудувати з використанням ФЕ (& ,Ú ,Ø )оптимальні в класі нормальних форм і абсолютно оптимальні ФС, що реалізують такі функції:
а) ( x® y)Å zy; б) ( xÅ y)|z, в) xy® yz;г) x|(yÚ z); д) x®( y® z) ;
е) (10011101) ;ж) (01101011) ;з) (11101011111111110) .
2. Побудувати з допомогою ФЕ (Ú,Ø )ФС функций 1.а) -ж).
3. Побудувати з використанням ФЕ (&,Ø)ФС функцій 1.а)-ж).
4. Побудувати ФС, що реалізує однорозрядний двійковий суматор (Приклад 2) за допомогою ФЕ наступного виду:
а)(& ,Ú ,Ø), б) (Ú ,Ø ) , в) (& ,Ø), г) ( x| y} .
5. За допомогою ФЕ (& ,Ú ,Ø )побудувати ФС наступних пристроїв:
а) перетворювача з двійковими входами ( х,у), і виходом f, який працює наступним чином: при подачі х= 0на виході f =у, а при подачі х = 1на вході f =`у;
б) виборчого пристрою з двійковими входами ( х,у)і виходами f 0 , f 1 , f 2 , f 3 , який приймає на вході комбінацію значень ( х у) як двійкове числоi, що лежить в інтервалі від 0 до 3. Значення виходів для кожного iнаступні: f i= 1, а решта f j= 0, (0 £ j£ 3 , j¹ i).
6. Чи можна як базис при побудові ФС прийняти такі набори функцій:
а) (1001), (10001110),
б) (0101), (1011), (1101),
в) (1010), (01110001)?
Відповідь обґрунтувати.
7. Навести приклади функцій, що управляють, ФС яких не можна побудувати тільки з одних ФЕ типу (®).
8. Навести приклади керуючих функцій, ФС яких не можна побудувати тільки з одних ФЕ типу (Å, º).
9. Дана ФС з ФЕ (&, Ú, Ø).
Рис.1.24
Чи можна з неї виключити шляхом еквівалентних перетворень:
а) усі елементи (Ø)?
б) усі елементи (&)?
в) усі елементи (Ú)?
10. Оптимізувати ФС з ФЕ (&, Ú, Ø), наведену на рис.1.25.
Рис.1.25
Побудувати ФС:
а) оптимальну в класі нормальних форм та
б) абсолютно оптимальну.