В сучасної технікикеруючих і обчислювальних пристроїв важливе місце займають дискретні перетворювачі, тобто пристрої, які мають деяке число входів і виходів. Набори сигналів, що надходять на входи і на виходах, належать відомим кінцевим множин.
Поділіться роботою у соціальних мережах
Якщо ця робота Вам не підійшла внизу сторінки, є список схожих робіт. Також Ви можете скористатися кнопкою пошук
Аранов Віктор Павлович. Дискретна математика. Розділ 5. ДНФ та схеми з ФЕ.
Лекція 28. Схеми із функціональних елементів. Завдання аналізу та синтезу
лекція 28. СХЕМИ З ФУНКЦІОНАЛЬНИХ ЕЛЕМЕНТІВ.
ЗАДАЧІ АНАЛІЗУ І СИНТЕЗУ
План лекції:
1. Поняття схеми із функціональних елементів(ФЕ).
2. Завдання аналізу та синтезу схем з ФЕ.
- Поняття схеми з ФЕ
У сучасній техніці керуючих та обчислювальних пристроїв важливе місце займаютьдискретні перетворювачі, тобто пристрої, які мають деяке число входів і виходів. Набори сигналів, що надходять на входи і на виходах, належать відомим кінцевим множин. Пристрої здійснюють перетворення вхідних наборів сигналів у вихідні. Математичною моделлю таких пристроїв є так званісхеми із функціональних елементів(СФЕ).
Як приклад розглянемо електричну схему з трьох діодів та опору, показану на рис. 1.
Рис. 1. Електрична схема та її умовне позначення
У точках схеми, зображених кружком, у різні моменти часу можлива поява або високого рівня, приблизно рівного 5, або низького рівня, приблизно рівного нулю. У точці схеми, зазначеної рисою, підтримується постійно низький рівень напруги.
Крапки, зазначені, інтерпретуватимемо як входи, а крапку – як вихід. Роботу схеми можна описати так: якщо на всіх входах низький рівень напруги, то на виході теж низький, якщо хоча б на одному з входів високий рівень напруги, то на виході – високий. Якщо позначити стан з високим рівнемнапруги одиницею, і з низьким – нулем, залежність виходу від входів можна поставити з допомогою булевої функції.
З цього наведену схему називають логічним елементом «АБО».
Подібні схеми можна побудувати з електронних ламп, електромеханічних перемикачів, пневмоелементів та ін. Залежність виходу від входів може описуватися не тільки як диз'юнкція, але також за допомогою кон'юнкції, заперечення та складніших булевих функцій.
Розглянемо логічні елементи з різною залежністю виходу від входів. Ці елементи можна з'єднувати один з одним, подаючи виходи деяких елементів на інші входи. В результаті отримуємо СФЕ.
Визначення поняття СФЕ можна розбити на два етапи. У першому етапі розкривається структурна частина цього поняття, другою – функціональна.
I етап. Розіб'ємо цей етап на ряд пунктів.
1 . Є кінцева множина об'єктів (), званихлогічними елементами.Кожен елемент має входи та один вихід. Елемент графічно зображується так, як зазначено на рис. 2.
2 . За індукцією визначаємо поняттялогічної мережі як об'єкта, в якому є деяка кількість входів та деяка кількість виходів (рис. 3).
а) Базис індукції. Ізольована вершина називається тривіальною логічною мережею. За визначенням, вона є одночасно входом та виходом (рис. 4).
… …
…
Рис. 2 Мал. 3 Мал. 4
б) індуктивний перехід. Ця частина полягає в використанні трьох операцій.
I . Операція об'єднання мереж, що не перетинаються. Нехай і – дві мережі, що не перетинаються (без загальних елементів, входів і виходів), що мають відповідно і входів, і виходів. Теоретико-множинне об'єднання мереж і є логічна мережа, яка має входи та виходи.
II . Операція приєднання елемента. Нехай мережа та елемент такі, що й у вибрано різних виходів з номерами. Тоді постать називається логічною мережею, що є результатом підключення елемента до мережі. Вхідами є всі входи, виходи – всі виходи мережі, крім виходів із номерами, а також вихід елемента. Мережа має входи та виходи (рис. 5).
… …
Рис. 6.
Рис. 5
III . Операція розщеплення виходу. Нехай у мережі виділено вихід із номером. Тоді постать називається логічною мережею, отриманою шляхом розщеплення виходу. Входами є всі входи, виходами – всі виходи мережі з номерами 1, …, …, та ще два виходи, що виникли з виходу з номером мережі (рис. 6). Отже, має входи та виходи.
3 . Нехай задані алфавіти та.
Схема з функціональних елементівназивається логічна мережа з входами з алфавіту та виходами з алфавіту, яка позначається
. (1)
Наведемо приклади схем.
1. Нехай безліч складається з трьох елементів І (кон'юнктора), АБО (диз'юнктора) та НЕ (інвертора).
Тоді фігура (рис. 6) буде схемою, оскільки вона може бути збудована з використанням операцій I – III .
Рис. 6 Мал. 7
2. Фігура, зображена на рис. 7 буде також схемою.
II етап. Визначення функціонування схеми.
4 . Порівняємо СФЕ (1) систему функцій логіки алгебри
(2)
звану такожпровідністю даної схеми.
приклад. а) Для схеми маємо систему, що складається з одного рівняння
Або.
б) Для схеми аналогічно отримуємо
- Реалізація булевих функцій схемами з ФЕ. Завдання аналізу та синтезу
схем із ФЕ
Завдання аналізу: для цієї СФЕ (1) отримати систему булевих рівнянь (2).
Алгоритм розв'язання задачі: слідуючи операціям побудови мережі I – III послідовно обчислюємо функції на виходах елементів мережі.
Завдання синтезу: для даного базису функціональних елементів та довільної системи булевих рівнянь (2) побудувати схему (1) із заданих ФЕ, що реалізує цю систему рівнянь.
Існування рішення задачі синтезу визначається теоремою Посту, згідно з якою система функцій, що реалізують базисні ФЕ, має бути повною. Функції можна у вигляді суперпозиції функцій, а кожному кроці суперпозиції відповідає певне з'єднання елементів.
приклад. Для функції
(3)
Схема, що відповідає суперпозиції у правій частині формули (3), показана на рис. 8.
Рис. 8
Проблема синтезу у тому, що з даної системи булевих рівнянь можна побудувати багато схем з ФЕ, які реалізують цю систему. У зв'язку з цим постає завдання оптимального синтезу: зі всіляких схем, що реалізують цю функцію, вибрати найкращу за тією чи іншою ознакою, наприклад, із найменшою кількістю елементів. Такі схеми називатимемомінімальними.
Справедливим є наступне твердження.
Теорема. Існує алгоритм, який кожної системи булевих функцій будує мінімальну схему.
Цей алгоритмпобудови мінімальних схем належить до класу алгоритмів типу «повного перебору», оскільки він заснований перегляд всіх схем до певної складності. Алгоритми повного перебору, як правило, мають велику трудомісткість і непридатні для практичних цілей. Тому розглянемо далі просте завдання, на яку вихідна система рівнянь містить одне рівняння
і, отже, шукана схема має вихід.
Складність мінімальної схеми позначимо через. Розглянемо завдання синтезу задля окремої функції, а всього класу функцій від змінних. Якість алгоритмів синтезу порівнюється шляхом зіставлення про функцій Шеннона. Нехай
- Мінімальна складність схем, що реалізують, які виходять за допомогою алгоритму.
Функції називаються функціями Шеннона, причому очевидно, що
Завдання синтезу полягає в тому, щоб знайти алгоритм, для якого була б можлива ближче, і щоб трудомісткість алгоритму була б істотно меншою, ніж трудомісткість алгоритму повного перебору. При такій постановці задачі не потрібно, щоб алгоритм кожної функції знаходив мінімальну схему, необхідно тільки, щоб найпростіша схема, що отримується за допомогою, мала складність, що сильно не перевищує.
Інші схожі роботи, які можуть вас зацікавити. |
|||
| 9013. | МЕТОДИ СИНТЕЗУ СХЕМ З ФЕ. СХЕМИ ДЕШИФРАТОРУ ТА ДВОЙКОВОГО СУМАТОРУ | 153.07 KB | |
| Загальна теорія синтезу СФЕ призводить до висновку, що більшість булевих функцій при великих значеннях має складні мінімальні схеми. Це означає, що практичну цінність з погляду синтезу є дуже вузьким класом булевих функцій. | |||
| 5321. | Види та значення параметрів автоматичних захистів для різних елементів заданої розрахункової схеми | 526.7 KB | |
| Для забезпечення нормальної роботи енергетичної системи та споживачів електроенергії необхідно якнайшвидше виявляти та відокремлювати місце пошкодження від непошкодженої мережі, відновлюючи нормальні умови роботи енергосистеми та споживачів. | |||
| 5384. | Розробка електричної схеми стенду для аналізу роботи тактованого декодера на 4 входи та 16 виходів | 626.63 KB | |
| Для покращення експлуатації рухомого складу АТП розроблена організаційна структура системи обслуговування та ремонту рухомого складу АТП а також запропоновано комплект обладнання для діагностування та технічне обслуговування. Основне завдання функціонування ремонтного господарства підприємства є забезпечення безперебійної експлуатації устаткування. До її складу входять: ремонтно-відновлювальна база підприємства склади цехи та загальнозаводські відділи ремонтного господарства технологічного обладнання диспетчерський. Організація... | |||
| 1886. | Етапи системного аналізу, їх основні цілі, завдання | 27.44 KB | |
| Теорія оптимальних систем дозволяє оцінити ту межу, яка може бути досягнута в оптимальній системі порівняти її з показниками діючої не оптимальної системи і з'ясувати, чи доцільно в даному випадку займатися розробкою оптимальної системи. Для автоматично керованого процесу автоматично керованої системи розрізняють дві стадії оптимізації: статичну та динамічну. Статична оптимізація вирішує питання створення та реалізації оптимальної моделі процесу а динамічна... | |||
| 5123. | Розробка функціональних стратегій | 35.44 KB | |
| Стратегія керування персоналом. Функції та структура управління. Функції управління та його роль формуванні структур управління. Ієрархічний тип структури управління. | |||
| 20368. | Вплив складу рецептурних компонентів та технологій на споживчі властивості функціональних продуктів | 742.05 KB | |
| Сучасною медичною наукою прийнято концепцію оптимального харчування. Це означає, що здійснено перехід від концепції адекватного харчування, коли в основному регламентувалися та нормувалися макронутрієнти – джерела жиру, джерела енергії, пластичного матеріалу (ліпіди, білки, жири) до концепції оптимального харчування, коли спектр необхідних для життєдіяльності організму харчових речовин та інших мінорних компонентів, на які раніше не звертали уваги, значно розширено. | |||
| 4706. | Методи синтезу карбоксилатів Ме | 9.26 MB | |
| Суть методу полягає у розчиненні оксиду, гідроксиду або карбонату металу у водному розчині відповідної кислоти. Продукт виділяють упарюванням розчину до початку кристалізації або фільтруванням осаду, якщо карбоксилат не розчинний або обмежено розчинний у воді. | |||
| 15923. | Основні методи синтезу піразалодіазепінів | 263.39 KB | |
| Нові методи синтезу похідних піразолодіазепінів. Розробка нових стратегій синтезу становить значний інтерес. Систематичні та узагальнюючі дослідження синтезу похідних піразолодіазепінів не проводилися; деякі питання залишаються незачепленими спірними або до кінця невирішеними. | |||
| 11978. | Енерготехнологічні установки на основі гідротермального окиснення алюмінію для виробництва електроенергії, тепла, водню та функціональних наноматеріалів | 49.89 KB | |
| В основі розробки лежить реакція гідротермального окиснення алюмінію, в ході якої виділяється велика кількість теплової енергії та утворюються оксиди алюмінію та водень: l2H2O→lOOH бемит15H2415. Як вихідні реагенти використовуються дистильована вода і мікронні порошки алюмінію. Установка КЭУ10 Установка ЭТК100 Технічні характеристикиустановки ЕТК100: Параметр Значення Витрата алюмінію кг год 101 Витрата води на вході у водопідготовчий пристрій кг год 484 Продуктивність водню нм3 110 Теплова потужність... | |||
| 6605. | Експертні системи. Проектування ТП методом синтезу | 11.67 KB | |
| Подання накопичення знань та підтримання їх у актуальному стані – складне завдання досліджуване у розділі інформатики, що називається інженерією знань. Інженер зі знань бере участь у створенні основи знань – ядра систем званих інтелектуальними. Найчастіше інтелектуальні системи застосовуються для вирішення складних завдань, де основна складність рішення... | |||
Подання булевих функцій формулами можна надати наступний "інженерно-конструктивний" сенс. Розглянемо формулу над якимось довільно фіксованим безліччю як "чорний ящик", якийсь пристрій, на вхід якого подаються всілякі набори значень змінних, а на виході з'являються відповідні цим наборам значення функції, що представляється формулою (рис. 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, а сигнал перенесення старшого розряду є старший розряд суми, яка в загальному випадку буде чотирирозрядним числом.
Розмір: px
Починати показ зі сторінки:
Транскрипт
1 Лекція 2. Схеми з функціональних елементів (СФЕ) у певному базисі. Складність та глибина схеми. приклади. Метод синтезу СФЕ з ДНФ. Лектор – доцент Селезньова Світлана Миколаївна Лекції з Дискретної математики 2. 1-й курс, група 141, факультет ВМК МДУ імені М.В. Ломоносова Лекції на сайті
2 Схеми із функціональних елементів Визначимо схеми із функціональних елементів у деякому базисі. Нехай нам задано деяку множину булевих функцій B = (g 1 (x 1,..., x n1),..., g s (x 1,..., x ns)) P 2, де n 1,. ., ns 0. Назвемо це безліч базисом. Зауважимо, що це поняття базису не пов'язане з поняттям базису P 2, яке розглядалося в алгебрі логіки. Як правило, ми розглядатимемо стандартний базис B 0 = (x&y, x y, x).
3 Визначення схеми з функціональних елементів Схема з функціональних елементів (СФЕ) у базисі B 0 = (x&y, x y, x) це 1) орієнтований ациклічний граф G = (V, E), кожна вершина v V якого має півступінь заходу d (v ), що не перевищує двох (d (v) 2); 2) кожна вершина v з напівступенем заходу, що дорівнює 0 (d (v) = 0), називається вхідний (або входом схеми) і їй приписується деяка булева змінна x i; 3) усі інші вершини (крім входів) називаються внутрішніми вершинами схеми;
4 Визначення схеми з функціональних елементів (продовження) 4) кожній вершині v з півступенем заходу, що дорівнює 1 (d (v) = 1) приписується (функціональний) елемент заперечення; усі такі вершини називаються інверторами; 5) кожній вершині v з півступенем заходу, що дорівнює 2 (d (v) = 2) приписується або (функціональний) елемент кон'юнкції &, або (функціональний) елемент диз'юнкції; всі вершини, яким приписані елементи кон'юнкції, називаються кон'юнкторами; всі вершини, яким приписані елементи диз'юнкції, називаються диз'юнкторами;
5 Визначення схеми з функціональних елементів (продовження) 6) крім того, деяким з вершин приписані різні вихідні змінні y 1,..., y m. Якщо задана СФЕ S, входам якої приписані тільки змінні x 1,..., x n, і з вихідними змінними y 1,..., y m, то позначатимемо цю СФЕ через S(x 1,..., x n ; y 1,..., y m).
6 Приклад СФЕ Приклад 1. СФЕ S(x 1, x 2, x 3 ; y 1, y 2, y 3):
7 Приклад СФЕ Приклад 1. Як правило, СФЕ зображуються наступним чином S(x 1, x 2, x 3 ; y 1, y 2, y 3):
8 Визначення складності СФЕ Складністю L(S) СФЕ S називається числом внутрішніх вершин цієї СФЕ, тобто. число функціональних елементів у СФЕ S.
9 Складність СФЕ Приклад 2. Складність СФЕ S:
10 Визначення глибини вершини СФЕ По індукції визначимо глибину d(v) вершини v СФЕ S. 1. Базис індукції. Кожен вхід v СФЕ S має глибину, що дорівнює 0: d(v) = Індуктивний перехід. 1) Якщо в інвертор v СФЕ S веде дуга з вершини v 1, то d(v) = d(v 1)) Якщо кон'юнктор або диз'юнктор v СФЕ S ведуть дуги з вершин v 1 і v 2, то d(v) = max(d(v 1), d(v 2)) + 1. Глибиною D(S) СФЕ S називається максимальна із глибин її вершин.
11 Глибина СФЕ Приклад 3. Глибина вершин СФЕ S та глибина СФЕ S:
12 Визначення функціонування СФЕ У кожному вершині СФЭ реалізується (чи обчислюється) деяка булева функція. По індукції визначимо булеву функцію, що реалізується у вершині v СФЕ S. 1) Якщо v вхідна вершина, і їй приписана змінна x i, то вершині v реалізується функція f v = x i. 2) Якщо інвертор v веде дуга з вершини v 1, і у вершині v 1 реалізується функція f v1, то вершині v реалізується функція f v = f v1. 3) Якщо кон'юнктор (або диз'юнктор) v ведуть дуги з вершин v 1 і v 2, і у вершинах v 1 і v 2 реалізуються функції f v1 і f v2 відповідно, то у вершині v реалізується функція f v = f v1 & f v2 ( відповідно f v = f v1 f v2).
13 Функціонування СФЕ Вважається, що СФЕ S(x 1,..., x n ; y 1,..., y m) реалізує систему булевих функцій F S = (f 1,..., f m ), що реалізуються у її вихідних вершинах y 1,..., y m.
14 Функціонування СФЕ Приклад 4. Булеві функції, що реалізуються у вершинах СФЕ S: F S = (x 3, x 1 x 2, x 1 x 2 x 3).
15 Лінійна програма Лінійною програмою з входами x 1,..., x n над базисом B 0 = (x&y, x y, x) називається послідовність z 1, z 2,..., z t, в якій для кожного номера j, j = 1,..., t, виконується, що 1) або z j = x i; 2) або z j = z k при k< j; 3) либо z j = z k &z l при k, l < j; 4) либо z j = z k z l при k, l < j. Линейная программа последовательно вычисляет значения z 1,..., z t как функции булевых переменных x 1,..., x n.
16 СФЕ та лінійні програми Зрозуміло, що обчислення у СФЕ можна переписати у вигляді лінійної програми. І навпаки, кожну лінійну програму можна у вигляді деякої СФЕ.
17 СФЕ та лінійні програми Приклад 5. СФЕ S відповідає лінійна програма z 1 = x 1 & x 2, z 2 = x 3, z 3 = z 1 z 2.
18 СФЕ та його характеристики Схеми з функціональних елементів є обчислювальною моделлю. Введені нами показники СФЕ демонструють різні аспекти ефективності обчислень. Складність СФЕ відповідає часу послідовного обчислення. Глибина СФЕ відповідає часу паралельного обчислення. Максимальне число вершин з однаковою глибиною в СФЕ відповідає кількості процесорів при паралельному обчисленні.
19 Приклад: сума двох бітів Приклад 6. Побудувати СФЕ у стандартному базисі, що реалізує (обчислює) суму двох бітів x та y. Рішення. Запишемо таблицю суми двох бітів x та y. Ця сума може бути числом із двома двійковими розрядами, тому введемо дві булеві змінні z 0, z 1, такі, що x + y = 2z 1 + z 0: x y z 1 z
20 Приклад: сума двох біт Рішення (продовження). Тоді z0 = xy, z1 = xy. Враховуючи, що x y = (x y) (x y), отримуємо CФЕ: Зрозуміло, що L(S 1) = 3 і D(S 1) = 3.
21 СФЕ у довільному базисі Аналогічно вводиться поняття СФЕ у довільному базисі B P 2.
22 Приклад: сума трьох бітів Приклад 7. Побудувати СФЕ в базисі P2 2 (тобто з усіх булевих функцій, що залежать від двох змінних), що реалізує (обчислює) суму трьох бітів x, y та z.
23 Приклад: сума трьох бітів Рішення. Аналогічно прикладу 6 запишемо таблицю суми трьох бітів x, y та z. Ця сума може бути числом також із двома двійковими розрядами, тому введемо дві булеві змінні u 0, u 1, такі, що x + y + z = 2u 1 + u 0: x y z u 1 u
24 Приклад: сума трьох бітів Рішення (продовження). Тоді u0 = xyz, u1 = xyxz yz. Враховуючи, що xy xz yz = xy z(x y), отримуємо CФЕ: Бачимо, що L(S) = 5, та D(S) = 3.
25 Реалізація булевої функції СФЕ Чи можна довільну булеву функцію (або систему булевих функцій) реалізувати СФЕ в базисі B 0 = (x&y, x y, x)? Можна, можливо. Як це можна довести? Наприклад, так. Т.к. (x&y, x y, x) повна в P 2 система, довільну булеву функцію f можна представити формулою тільки через кон'юнкцію, диз'юнкцію та заперечення. Наприклад, у вигляді досконалої ДНФ, якщо f 0 і у вигляді x& x, якщо f = 0. А потім по цій ДНФ (формулі) побудувати відповідну СФЕ. Такий метод побудови СФЕ для булевих функцій називається методом синтезу ДНФ.
26 Синтез СФЕ щодо ДНФ А якої складності вийде СФЕ S щодо ДНФ для булевої функції f (x 1,..., x n), яка залежить від n змінних? Досконала ДНФ для функції f міститиме не більше 2 n елементарних кон'юнкцій. Кожна елементарна кон'юнкція це кон'юнкція n змінних чи його заперечень.
27 Синтез СФЕ з ДНФ Тому у схемі будуть: n інверторів для реалізації всіх заперечень змінних x 1,..., x n; по (n 1) кон'юнктор для реалізації кожної з не більше 2 n елементарних кон'юнкцій в досконалої ДНФ; не більше (2 n 1) диз'юнктора для реалізації диз'юнкції елементарних кон'юнкцій ДНФ. Отримуємо, що L(S) n + (n 1) 2 n + (2 n 1) n 2 n + n.
28 Складність булевої функції Складністю L(f) бульової функції f (x 1,..., x n) у класі СФЕ називається мінімальна складність серед усіх СФЕ, що реалізують функцію f. Отже, довели теорему: Теорема 1. Для довільної функції f (x 1,..., x n) P 2 вірно L(f) n 2 n + n.
29 Завдання для самостійного вирішення 1. Для булевої функції f (x 1, x 2, x 3) = () побудувати СФЕ у стандартному базисі складності Для булевої функції f (x 1, x 2, x 3) = () побудувати СФЕ в стандартному базисі складності Для булевої функції f (x 1, x 2, x 3, x 4) = x 1 x 2 x 3 x 4 побудувати СФЕ у стандартному базисі глибини Довести, що у стандартному базисі L(x y) = 4.
30 Література для лекції 4 1. Яблонський С.В. Введення у дискретну математику. М: Вища школа, Ч. V, гол. 2, з Гаврилов Г.П., Сапоженко О.О. Завдання та вправи з дискретної математики. М: Фізматліт, Гол. X 1.1, 1.5, 1.7, 1.17, 1.18.
31 Кінець лекції 4
Лекція: Схеми із функціональних елементів із затримками (СФЕЗ), автоматність здійснюваних ними відображень. Подання КАВ СФЕЗ. Спрощення КАВ. Відмінність та невідмінність станів КАВ. Теорема Мура
Лекція: Теорема Анселя про розбиття n-мірного куба на ланцюзі. Теорема про кількість монотонних функцій логіки алгебри. Теорема про розшифрування монотонних функцій логіки алгебри. Лектор – доцент Селезньова Світлана
Лекція: Кінцеві автомати із виходом (КАВ). Автоматні функції, способи їхнього завдання. Теорема про перетворення періодичних послідовностей автоматними функціями. Лектор – доцент Селезньова Світлана Миколаївна
Лекція: Частково впорядковані множини (ЧУМ). Діаграма ЧУМ. Максимальні, мінімальні, найбільші та найменші елементи. Ланцюги та антиланцюги, довжина та ширина кінцевих ЧУМ. Теорема про розбиття ЧУМ на антицепи.
Лекція 2. Властивості біномних коефіцієнтів. Підрахунок сум та метод виробляючих функцій (кінцевий випадок). Поліноміальні коефіцієнти. Оцінки біномних та поліноміальних коефіцієнтів. Оцінки сум
Лекція: Алгоритм розпізнавання повноти P k. Замкнені класи. Класи функцій, що зберігають безліч і зберігають розбиття, їх замкнутість. Теорема Кузнєцова про функціональну повноту. Передповні класи.
лекція 2. Комбінаторика. Властивості біномних коефіцієнтів. Підрахунок сум та метод виробляючих функцій. Поліноміальні коефіцієнти. Оцінки біномних та поліноміальних коефіцієнтів. Асимптотичні
Лекція: Звичайнозначні функції. Елементарні k-значні функції. Способи завдання k-значних функцій: таблиці, формули, 1-а та 2-а форми, поліноми. Повнота. Теорема про повноту Постової системи. Функція Інтернету.
Лекція 3. Послідовності, що визначаються рекурентними співвідношеннями. Однорідні та неоднорідні лінійні рекурентні рівняння (ЛОРУ та ЛНРУ). Загальні рішення ЛОРУ та ЛНРУ. Лектор – доцент Селезньова Світлана
Лекція 15. Функції кінцевих логік. Елементарні функції k-значна логіка. Способи завдання функцій k-значної логіки: таблиці, формули, I-я та II-я форми, поліноми. Повнота. Лектор – доцент Селезньова
Лекція: Функції кінцевих логік. Елементарні функції значної логіки. Способи завдання функцій k-значної логіки: таблиці, формули, I-я та II-я форми, поліноми. Повнота. Лектор – доцент Селезньова Світлана
Лекція: Функція Мебіуса на ЧУМ. Функція Мебіуса на n-мірному кубі. Формула звернення Мебіуса. Принцип включень-виключень. Завдання про підрахунок кількості перестановок-заворушень. Лектор – доцент Селезньова Світлана
Лекція 2. Властивості біномних коефіцієнтів. Метод виробляючих функцій, підрахунок сум та підтвердження тотожностей. Поліноміальні коефіцієнти. Принцип включень-виключень. Лектор – доцент Селезньова Світлана
Лекція: Істотні функції. Три леми про суттєві функції. Критерій повноти Яблонської. Критерій повноти Слупецького. Шефферові функції. Лектор доцент Селезньова Світлана Миколаївна [email protected]
Основні комбінаторні числа. Оцінки та асимптотики для комбінаторних чисел. Лектор – доцент Селезньова Світлана Миколаївна факультет ВМК МДУ імені М.В. Ломоносова Лекції на сайті http://mk.cs.msu.su
Властивості біномних коефіцієнтів. Підрахунок сум та метод виробляючих функцій (кінцевий випадок). Поліноміальні коефіцієнти. Оцінки біномних та поліноміальних коефіцієнтів. Оцінки сум біномних
Лекція: Кінцеві автомати із виходом. Перетворення періодичних послідовностей кінцевими автоматами із виходом. Відмінність станів кінцевих автоматах з виходом. Спрощення автоматів. Лектор Селезньова
Лекція: Покриття множини та покриття матриці. Градієнтне покриття. Лемма про градієнтне покриття. Оцінки потужності затіняючої множини n-мірного куба. Оцінки довжини поліноміальних нормальних форм функцій
Лекція 5. Покриття множини та покриття матриці. Градієнтне покриття. Лемма про градієнтне покриття. Оцінки потужності затіняє безліч булева куба. Оцінки довжини поліноміальних нормальних форм булевих
Лекція 3. Послідовності, що визначаються рекурентними співвідношеннями. Однорідні та неоднорідні лінійні рекурентні рівняння (ЛОРУ та ЛНРУ). Загальні рішення ЛОРУ та ЛНРУ. Приклади Лектор – доцент Селезньова
Лекція 3. Відносини на множинах. Властивості. Формула включень-виключень. Відношення еквівалентності. Відношення часткового порядку. Лектор – доцент Селезньова Світлана Миколаївна Лекції з Дискретних моделей.
лекція 4. Особливості багатозначних логік. Замкнений клас, базис замкненого класу. Теореми Янова та Мучника про існування у багатозначних логіках замкнутих класів без базису та замкнутих класів з рахунковим
лекція. Функції натурального аргументу (послідовності). Однорідні та неоднорідні лінійні рекурентні рівняння (ЛОРУ та ЛНРУ). Загальні рішення ЛОРУ та ЛНРУ. Приклади Лектор – доцент Селезньова Світлана
Лекція: Хроматична кількість графа. Критерій двоколірності графа. Теореми про верхні та нижні оцінки хроматичного числа графа. Лектор – доцент Селезньова Світлана Миколаївна Лекції з Дискретних моделей.
Лекція: Графи та мережі. Оцінка числа псевдографів з ребрами q. Оцінка числа дерев з ребрами q. Планарні графіки. Формула Ейлер для планарних графів. Найбільше ребер у планарних графах. Непланарність
лекція 1. Комбінаторика. Розміщення, перестановки, розміщення із повтореннями, поєднання, поєднання із повтореннями. Їхнє число. Лектор – доцент Селезньова Світлана Миколаївна Кафедра математичної кібернернетики
Лекція: Послідовності. Однорідні та неоднорідні лінійні рекурентні рівняння. Загальні рішення лінійних рекурентних однорідних та неоднорідних рівнянь. Лектор – доцент Селезньова Світлана Миколаївна
Лекція 8. Розмальовки. Еквівалентність розмальовок щодо групи. Виробляють функції. Перелічує ряд для фігур і ряд для функцій. Теорема Пойя. Лектор Селезньова Світлана Миколаївна
Лекція: Розмальовки. Еквівалентність забарвлень щодо групи перестановок. Теорема Пойа (приватний випадок). Виробляють функції. Перелічує ряд для фігур і ряд для функцій. Теорема
Лекція 2. Кон'юнктивні нормальні форми. Імпліцент, проста імпліцент функції. Скорочені КНФ функції алгебри логіки. Способи побудови скороченої КНФ. Лектор Селезньова Світлана Миколаївна [email protected]
Математичні моделіта методи логічного синтезу НВІС Осінь 2015 Лекція 4 План лекції Логічна оптимізація комбінаційних логічних схем Різні способипредставлення функцій алгебри логіки (ФАЛ)
Лекція: Недетерміновані кінцеві автомати без виходу. Теорема про збіг класів множин слів, що допускаються кінцевими детермінованими та кінцевими недетермінованими автоматами. Процедура
Лекція 1. Вибірки. Розміщення, перестановки, розміщення з повтореннями, поєднання, поєднання із повтореннями, їх число. приклади. Лектор – доцент Селезньова Світлана Миколаївна Лекції з курсу Дискретна
Лекція 1. Комбінаторні об'єкти: вибірки, розміщення, перестановки, розміщення з повтореннями, поєднання, поєднання із повтореннями, їх число. Комбінаторні числа: факторіал, спадний факторіал, біноміальні
ЛЕКЦІЯ 4 СХЕМИ З ФУНКЦІОНАЛЬНИХ ЕЛЕМЕНТІВ 1. Основні визначення Насамперед необхідно розглянути композицію. Функцію можна представити у вигляді «чорної скриньки», яка має вхід і вихід. Нехай
Лекція 2. Алгоритм розпізнавання повноти P k. Теорема Кузнєцова. Замкнені класи. Класи функцій, що зберігають безліч. Класи функцій, що зберігають розбиття. Передповні класи. Лектор д.ф.-м.н. Селезньова
Лекція 3. Поліном Жегалкіна. Способи побудови полінома Жегалкіна функції. Лінійний імпліцент функції. Лінійна кон'юнктивна нормальна форма (ЛКНФ). Знаходження всіх лінійних імпліцентних функцій. Перевірка
Лекція 2. Виробляючі функції: підрахунок комбінаторних сум та підтвердження тотожностей, перерахування комбінаторних об'єктів. Принцип включень-виключень. Підрахунок числа перестановок-заворушень. Лектор -
лекція 5. Графи. Забарвлення графів. хроматичне число графа. Критерій двоколірності графа. Верхня оцінка хроматичного числа графа. Лектор д.ф.-м.н. Селезньова Світлана Миколаївна [email protected]Лекції
Лекція: Кінцеві автомати (КА) без виходу (кінцеві автомати-розпізнавачі). діаграми переходів. Автоматні множини (мови). Лемма про властивості автоматних множин. Приклад неавтоматної множини. Лектор
Лекція 1. Звичайнозначні функції. Елементарні k-значні функції. Способи завдання k-значних функцій: таблиці, формули, 1-а та 2-а форми, поліноми. Повнота. Теорема про повноту Постової системи. Функція Інтернету.
Лекція 7. Завдання вибору маршрутів та її окремий випадок – завдання розподілу рейсів по днях. Графові моделі для завдання розподілу рейсів. хроматичне число графа. Критерій дворозмальовування графа.
Курс «Основи кібернетики» для студентів спеціалізації 01.02.09.01 (математичне та програмне забезпеченняобчислювальних машин) 1. Загальна інформація(навчальне навантаження, форми контролю та ін.). Курс є
6. Графи. Спадкові властивості графів. Оцінка числа ребер у графах із спадковою властивістю. Екстремальні графіки. Найбільше ребер у планарних графах і графах без трикутників із заданим
Math-Net.Ru Загальноросійський математичний портал Д. С. Романов, Метод синтезу схем, що легко тестуються, що допускають поодинокі перевіряючі тести константної довжини, Дискрет. матем., 2014, том 26, випуск 2,
Лекція: Кінцеві автомати без виходу, детерміновані та недетерміновані. Теорема про збіг класів множин слів, що допускаються кінцевими детермінованими та недетермінованими автоматами. Процедура
Практична робота 2 Побудова нормальних форм логічної функції Мета роботи: Навчитися будувати кон'юктивні, диз'юнктивні, досконалі нормальні форми логічної функції Зміст роботи: Основні
Семінар за складністю булевих функцій Лекція 1: Введення А. Куликов Computer Science клуб при ПОМИ
Практична робота 1 Аналіз та синтез логічних та релейних систем управління ВСТУП Пристрої дискретної дії, виконані на елементах гідро-, пневмо- та електроавтоматики, та керуючі мікропроцесори
Лекція: Регулярні вирази та регулярні множини. Теорема Кліні про збіг класів автоматних множин і регулярних множин. Лектор – доцент Селезньова Світлана Миколаївна Лекції з Дискретної математики
Лекція 3 Булеві алгебри та булеві функції Булеві алгебри Поняття про алгебраїчні системи Алгебраїчна система або алгебраїчна структура безліч символів деякого алфавіту (носій) із заданим
лекція 5. Графи. Приклади застосування графів. Транспортне завдання. Потік у мережі, теорема Форда та Фалкерсона про величину максимального потоку у мережі. Алгоритм побудови максимального потоку у мережі. Лектор
Лекція: Графи. Приклади застосування графів. Транспортне завдання. Потік у мережі, теорема Форда та Фалкерсона про величину максимального потоку у мережі. Алгоритм побудови максимального потоку у мережі. Лектор -
Заняття 8 Нагадаємо, що для довільних множин A і B існують множини A B = (x x A і x B); (перетин A і B) A B = (x x A або x B); (об'єднання A та B) A \ B = (x x A та x/B) (різниця A та B).
Лекція 7. Числа Рамсея. Верхня оцінка числа Рамсея. Нижня оцінка числа Рамсея. Лектор Селезньова Світлана Миколаївна [email protected]факультет ВМК МДУ імені М.В. Ломоносова Лекції на сайті http://mk.cs.msu.ru
Лекція: Графи. Основні поняття. Зв'язкові графи. Дерева. Основне дерево. Число висячих вершин в остовне дерево. Лектор – доцент Селезньова Світлана Миколаївна Лекції з Дискретних моделей. Майстер,
Лекція 11. Бульові схеми. Дискретна математика, ВШЕ, факультет комп'ютерних наук (Осінь 2014 весна 2015)
ЗАТВЕРДЖУЮ Проректор з навчальної роботи Ю. А. Самарський 10 червня 2008 р. ПРОГРАМА І ЗАВДАННЯ за курсом ДИСКРЕТНІ СТРУКТУРИ за напрямом 010600 факультет ФІВТ кафедра аналізу даних курс II семестр 4 Два
Московський державний університет імені М. В. Ломоносова Факультет обчислювальної математики та кібернетики С. А. Ложкін
Лекція: Спадкові характеристики графів. Екстремальні графіки. Числа Рамсея. Лектор – доцент Селезньова Світлана Миколаївна факультет ВМК МДУ імені М.В. Ломоносова Лекції на сайті http://mk.cs.msu.su Спадкове
Лекція: Операції над звичайно-автоматними множинами. Доповнення, об'єднання, перетин, твір та ітерація автоматних множин, їхня автоматність. Лектор – доцент Селезньова Світлана Миколаївна Лекції
Міністерство Російської Федераціїз зв'язку та інформатизації Поволзька державна академія телекомунікацій та інформатики Кафедра вищої математики Схвалено Методичною радою ПДАТІ 29 березня 2002
Лекція 5. Розмальовки ребер графів. хроматичний індекс графа. Хроматичний індекс дводольних графів Верхня та нижня оцінки хроматичного індексу графа. Лектор Селезньова Світлана Миколаївна [email protected]
Math-Net.Ru Загальноросійський математичний портал Н. П. Редькін, Про схеми, що допускають короткі одиничні діагностичні тести, Дискрет. матем., 1989, том 1, випуск 3, 71 76 Використання Загальноросійського
МАТЕМАТИЧНА ЛОГІКА(1) Завдання до практичних занять 1. Алгебра висловлювань Висловлювання - величина, яка може набувати два значення: істина та брехня. Висловлювання позначають великими латинськими
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.
СФЕ Приклади Синтез СФЕ з ДНФ
Завантаження...