![]()
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів
Контакти
Тлумачний словник Авто Автоматизація Архітектура Астрономія Аудит Біологія Будівництво Бухгалтерія Винахідництво Виробництво Військова справа Генетика Географія Геологія Господарство Держава Дім Екологія Економетрика Економіка Електроніка Журналістика та ЗМІ Зв'язок Іноземні мови Інформатика Історія Комп'ютери Креслення Кулінарія Культура Лексикологія Література Логіка Маркетинг Математика Машинобудування Медицина Менеджмент Метали і Зварювання Механіка Мистецтво Музика Населення Освіта Охорона безпеки життя Охорона Праці Педагогіка Політика Право Програмування Промисловість Психологія Радіо Регилия Соціологія Спорт Стандартизація Технології Торгівля Туризм Фізика Фізіологія Філософія Фінанси Хімія Юриспунденкция |
|
|||||||
Тема 9. Методи мінімізації булівських функцій9.1. Принципи спрощення ДНФ 9.2. Метод карт Карно 9.3. Метод Квайна - Мак-Класски 9.4. Евристичні методи мінімізації 9.5. Основні алгоритми евристичної мінімізації
9.1. Принципи спрощення ДНФ Будь-якому аналітичному вираженню булевої функції відповідає логічна схема, побудована у вигляді мережі з елементів НЕ. І та АБО. Ця схема є ще однією формою завдання булевої функції. Наприклад, логічна схема, показана на Рис. 9.1, відповідає булевої функції Рис. 9.1. Реалізація функції У цій схемі кожному терму Одна і та ж функція може бути представлена різними аналітичними виразами, яким відповідають різні схеми. Ці схеми можуть мати різну кількість елементів і з'єднань між ними, що визначає їх різну вартість. Для оцінки складності реалізації j-го аналітичні вирази функції fi, на практиці використовують ціну схеми по Квайну Так, для схеми на рис. 3.1 маємо
Аналіз функції
Рис. 9.2. Реалізація, функції асоціативності (б) Застосування асоціативного закону до булевої функції Таким чином, застосування законів булевої алгебри дозволило зменшити початкову вартість схеми в чотири рази. Очевидно, чим менша ціна за Квайну, тим менше і вартість схеми в грошовому обчисленні. Таким чином, правильне застосування законів булевої алгебри дозволяє зменшити вартість схем, якщо це можливо. Отже, одна і та ж булева функція може бути представлена різними ДНФ. Ці форми називаються еквівалентними ДНФ. Це приводить до задачі знаходження оптимальної в якомусь сенсі ДНФ серед безлічі еквівалентних ДНФ. Ця задача називається задачею мінімізації булевої функції (у класі ДНФ) і має складний комбінаторний характер. Якщо критерієм оптимальності є мінімальне число букв (літералів) у кінцевій формулою, то мова йде про знаходження мінімальної ДНФ. Якщо мінімізується кількість кон'юнкцій у формулі, то говорять про пошук найкоротшої ДНФ. Іноді на практиці досить знайти лише так звану без надлишкову ДНФ, тобто формулу, з якої не можна видалити жодного терма (кон'юнкції) і жодного літерала. Найпростіші методи спрощення ДНФ носять локальний характер, тобто їх застосування дозволяє спростити тільки окремі частини ДНФ. Так, при розгляді пар термів використовуються три наступні операції: 1. Поглинання, визначається формулою
Вираз (9.2) відображає той факт, що терм ab поглинається змінною а. Формула (9.2) доводиться наступним чином: Цю формулу можна поширити на випадок довільних кон'юнкція F1 і F2:
У виразі (9.3) терми F1 і F2 можуть складатися з довільного числа змінних. Нехай, наприклад, 2. Склеювання, визначається формулою
При цьому говорять, що терми Ця формула також може бути поширена на довільні терми F1 і F2:
Наприклад, нехай 3. Видалення літерала, визначається за формулою
Формулу (9.6) можна довести таким чином: Ця формула може бути розповсюджена на випадок будь-яких термів
Для попереднього прикладу маємо: При розгляді трьох термів може застосовуватися операція узагальненого склеювання:
Формула (9.8) може бути доведена наступним чином: Для спрощення ДНФ часто застосовують два наступних прийоми: 1. Дублювання термів (елементарних кон'юнкцій) функції, тобто використання закону 2. Диз'юнктивні розкладання термів функції з відсутньою змінною. Наприклад, терм ab може бути розкладений на змінні с, що дає Обидва прийоми використовуються для подальшого склеювання отриманих термів з деякими з вже існуючих термів ДНФ.
9.2. Метод карт Карно Природно, що безпосереднє застосування законів булевої алгебри для спрощення функцій є досить складним процесом. Тому на практиці використовуються методи, засновані на застосуванні карт Карно або деяких формальних методик. Мета спрощення булевих функцій - отримання схеми з мінімальною ціною по Квайну, що відповідає аналогічному вираженню функції з мінімальним числом літер. Назвемо ДНФ з мінімальним числом літер мінімальної ДНФ (МДНФ), а процес побудови МДНФ по С ДНФ - мінімізацією булевої функції. Розглянемо функцію
Рис. 9.3. Карта Карно для функції Знайдемо підфункцію Отриманий результат відповідає 3-кубу, який об'єднує вершини 0, 1, 4. 5, 8, 9, 12 і 13. З розглянутих прикладів можна зробити висновок про те, що будь-яким сусіднім Процес мінімізації по карті Карно може бути представлений наступним чином: 1. Знайти всі пари клітин, що містять одиниці і відповідних 1-кубів. Якщо деякі клітини не можна об'єднати з іншими, то відповідні їм терми з L літерами увійдуть до мінімальну ДНФ. 2. Знайти всі четвірки, що отримуються як комбінації пар першого етапу і відповідні 2-кубів. Якщо деякі пари не можна об'єднати з іншими, то відповідні їм терми з L-1 літерами увійдуть до мінімальну ДНФ. 3. Процес продовжується до тих пір, поки на черговому етапі ніяка пара з (n-1) - кубів не об'єднується в n- куб (n = 0,1 ,..., L-1). Кожен з отриманих кубів відповідає межам, що входить до МДНФ. Розглянемо процес мінімізації функції З розглянутого нами методу отримання булевих функцій 1. Якщо l-я компонента наборів, що входять у межі покриття, змінюється, то відповідна їй буква не входить в результуючий терм (l= 1 ,...,L). 2. Якщо 1-а літера входить в результуючий терм, то при рівності одиниці l-я компоненти l-я літера входить в терм без інверсії. Отже, результуючий терм Fc, який відповідає покриттю, визначається формулою
де Використовуючи формулу (9.9), отримаємо такі підсумкові терми, які входять до ДНФ: Таким чином, МДНФ функції Ціна по Квайну C( Для ефективної мінімізації булевої функції по картах Карно студентам необхідно придбати деякі практичні навички, після чого мінімізація буде виконуватися автоматично. Аналогічним чином формується і мінімальна КНФ (МКНФ). Відмінність від попереднього полягає в тому, що n- куби формуються з сусідніх клітин карти, що містять нулі. Мінімізація тепер заснована на використанні закону склеювання де А - довільна булева функція. У цьому випадку результуючий терм Фc визначається виразом
де Розглянемо карту Карно (мал. 9.4) і знайдемо мінімальну КНФ функції
Рис. 9.4. Карта Карно для функції Після знаходження покриттів I - IV очевидно, що результуюча МКНФ Отже, Розглянуті раніше функції відносяться до повністю певних функцій булевої алгебри, значення яких визначені на всіх можливих наборах змінних. Однак через фізичні особливості роботи пристрою, частина наборів можуть бути забороненими. Фізично це означає, що подібне поєднання параметрів є неможливим. Якщо функція Розглянемо деякі приклади, що ілюструють появу невизначених (заборонених) наборів. Приклад 9.1. У приміщенні необхідно підтримувати рівень температури в межах Система стабілізації температури може бути представлена наступною схемою: (рис. 9.5.) Рис. 9.5. Структурна схема системи стабілізації рівня температури Ця система включає крім кондиціонера та обігрівача два датчики Закон функціонування системи управління задається таблицею істинності (табл. 9.1). Тут набір Приклад 9.2. Поставити таблицю істинності функції уз, де уз = 1, якщо і тільки якщо А Рис. 9.6. Фізичний сенс сигналів датчиків і системи управління
Таблиця 9.1 Очевидно, для представлення десяткових чисел А і В необхідно по два двійкових розряди Таблиця 9.2 У табл. 9.2 стовпці А і В використані в якості коментарів, а також для спрощення порівняння А і В. На рис. 9.7 наведена карта Карло, відповідна табл. 9.2. Рис. 9.7. Карта Карло функції уз При синтезі логічної схеми знаки * повинні бути замінені нулями або одиницями. Очевидно, кожен знак * може бути замінений па 0 або 1. Таким чином, якщо функція у має n невизначених наборів, то їй відповідає Розглянемо ряд прикладів. Нехай всі знаки * в карті Карно (рис. 9.7) замінені нулями, що буде відповідати функції Тепер замінимо всі знаки * одиницями (рис. 9.8) і отримаємо МДНФ
З порівняння МДНФ з ціною по Квайну С (
Рис. 9.8. Поліостью певні функції, відповідні часткової функції уз При формуванні МКНФ необхідно керуватися такими самими правилами. Карта Карно (рис. 9.8г) дозволяє отримати МКНФ з ціною по Квайну Оптимальна заміна вимагає практичних навичок, які, однак, досить швидко отримуються при відповідних тренуваннях. Відзначимо, що при використанні формули (9.1), маємо
де Тепер, згідно (9.11) для функції
9.3. Метод Квайна - Мак-Класски Метод Квайна - Мак-Класски є формалізованим методом мінімізації булевих функцій, що використовують практично той же алгоритм, який ми розглядали при використанні карт Карно. Проілюструємо цей метод на прикладі мінімізації функції Ідея методу Квайна - Мак-Класски полягає в послідовному знаходженні l-кубів по 0-кубах, 2-кубів по l- кубів і так далі. Цей процес виконується максимум за L кроків, де L - число вхідних змінних функції. На останньому етапі шукається мінімальне покриття, тобто покриття функції кубами, породжує мінімальну ДНФ. Рис. 9.9. Карта Карно функції На першому етапі будується таблиця розмірності Таблиця 9.3 Таблиця 0-кубів функції З таблиці. 9.3 випливає, що терм 2. Будується таблиця 1-кубів розмірності 3. Будується таблиця 2-кубів розмірності Як випливає з табл. 9.5 2-куби функції Таблиця 9.4 Таблиця 1-кубів функції Таблиця 9.5 Таблиця 2-кубів функції
4. Знаходиться покриття вихідної функції отриманими кубами, для чого може бути використаний, наприклад, метод Петрика. Цей метод заснований на побудові таблиці покриття, рядки якої відзначаються отриманими кубами, зазначеними знаком "+", а стовпці - вихідними 0-кубами. На перетині і-го рядка і j-го стовпця таблиці покриття ставиться знак Для функції Таблиця 9.6 Таблиця покриття функції За цією таблицею будуються формули для покриття стовпців: Далі формується формула функції покриття, що має наступний вигляд: Таким чином, для функції Відзначимо, що цей же варіант виходить і по карті Карно (рис. 9.9). Вид функції Так, з табл. 9.6 виключається рядок А, так як тільки вона покриває терм f, рядок В - h (що дозволяє видалити і стовпець g), рядок С - b і d "(що дозволяє видалити і стовпці а, с), рядок D - е і g (що дозволяє видалити стовпці а, с). Таким чином, Якщо застосувати розглянутий метод Квайна - Мак-Класски до функції Рис. 9.10. Карта Карно функції Побудуємо таблицю покриття для функції Як видно з цього прикладу, терм В є надлишковим і не входить в остаточний результат. Проблема пошуку надлишкових термів дуже важлива. Як показано далі, для її вирішення використовуються складні формальні методи, засновані на евристика. Таблиця 9.7 Таблиця покриття функції Якщо вихідна функція є частковою, то для її мінімізації використовується наступний підхід: 1. Всі невизначеності (відмічені знаком *) в карті Карпо або таблиці істинності замінюються одиницями. 2. Знаходяться терми, відповідні рядкам таблиці покриття. Терми, відповідні кубах, які включають тільки невизначені набори, виключаються з таблиці покриття. 3. Знаходиться мінімальна ДНФ вихідної функції. Розглянемо як приклад булеву функцію Рис. 9.11. Функція Замінивши всі знаки * одиницями, можна отримати наступні терми Таблиця 9.8 Таблиця покриття функції З аналізу табл. 9.8 випливає, що терм А повинен бути включений у ДНФ, що виключає стовпці а, d, g, h. Аналогічно, терм С також повинен бути включений в мінімальну ДНФ, що виключає стовпці b, с, е, f. Таким чином, маємо формулу Метод Квайна - Мак-Класски застосуємо також для формування мінімальної КНФ. У цьому випадку вихідна таблиця будується для 0-кубів, відповідних наборів, на яких функція дорівнює нулю. Щоб звести задачу до вихідної, досить в усіх таблицях замість мінтермів розглядати відповідні їм куби. Наприклад, одержимо мінімальну КНФ функції Рис. 9.12. Карта Карно функції
1. Побудуємо таблицю 0-кубів (Табл. 9.9). З аналізу табл. 9.9 випливає, що терм Таблиця 9.9 Таблиця 0-кубів функції
2. Побудуємо таблицю 1-кубів функції Таблиця 9.10 Таблиця 1-кубів функції
З таблиці. 9.10 випливає, що терм 3. Побудуємо таблицю 2-кубів функції Таблиця 9.11 Таблиця 2-кубів функції 4. Побудуємо таблицю покриття функції Таблиця 9.12 Таблиця покриття функції Аналіз табл. 9.12 показує, що терм А входить до МКНФ, так як тільки він включає стовпець f; терм B входить у МКНФ, так як тільки він включає стовпець h; терм С входить до МКНФ, так як тільки він включає стовпець d; терм D входить до МКНФ, так як тільки він включає стовпець e. Отже, немає потреби в побудові функції покриття, і мінімальна КНФ функції Якщо порівнювати МДНФ Пошук МКНФ для часткової функції проводиться аналогічно пошуку МДНФ. Природно, що при цьому враховується той факт, що необхідно аналізувати нулі функції. Метод має наступний вигляд: 1. Всі невизначеності замінюються нулями і знаходяться всі куби вищого порядку. 2. Якщо пошук кубів завершений, то куби, що покривають тільки невизначені набори, виключаються з подальшого розгляду. Відмітимо, що на практиці часто доводиться мінімізувати системи булевих функцій, однак ці методи досить трудомісткі і виходять за рамки цієї книги. 9.4. Евристичні методи мінімізації Розглянутий метод Квайна - Мак-Класски відноситься до точних методів мінімізації булевих функцій, що дозволяє знайти мінімальну ДНФ. Однак, як було вже зазначено, блоки ЕОМ задаються функціями, які мають десятки і сотні аргументів і тисячі термів. Такі функції, звичайно, можуть бути мінімізовані з використанням методу Квайна - Мак-Класски, однак час мінімізації буде неприйнятно великим (дні і тижні). Відзначимо, що така мінімізація може виконуватися тільки ЕОМ, а за тиждень роботи цілком може статися збій. Це означає, що процес мінімізації треба буде починати спочатку. У зв'язку з цим для вирішення практичних задач великої розмірності використовуються евристичні методи, що дозволяють знайти безнадлишкові ДНФ за прийнятний час. При цьому важливим є те, що евристичні методи не вимагають стільки пам'яті ЕОМ, як точні методи. Практичні методи використовують принцип ітераційного поліпшення рішення, крім того вони не вимагають отримання всіх первинних імплікант. Терм Рис. 9.11 Карта Карно для функції Ця карта містить чотири первинних імпліканти, відповідних обведеним областям. Це імпліканти У евристичних методах мінімізація починається з первинного покриття, яке включає всі мінтерми (набори, відповідні одиницям в карті Карно) і несуттєві набори (відмічені знаком *). Для отримання рішення використовуються чотири основних операції: 1. Розширення (Expand). При цьому кожен не первинний імплікант замінюється своїм первинним імплікантом. Потім з функції видаляються всі імпліканти, що покриваються первинними імілікантами. 2. Винятки (Reduce). Ця операція використовується для видалення з покриття надлишкових первинних імплікантів. При цьому таке видалення неможливо, якщо імплікант є істотним. Для перевірки можливості видалення імпліканта виконується перевірка, яка має показати чи є импликант істотним чи ні. 3. Переформатування (Reshape). Ця операція розглядає пари імплікантів і якщо один з імплікантів покривається іншим, то той що покриваються видаляється. 4. Безнадлишковий (Irredundant). З покриття функції видаляються несуттєві імпліканти зі збереженням покриття всіх вихідних мінттермів. Відомий ряд практичних методів, які використовують ці операції. Так, програма PRESTO використовує тільки операцію Expand. При цьому отримують рішення швидко, але воно може бути далеким від оптимального результату. Програма MINI використовує перші три з розглянутих вище операцій. При цьому операції Reduce і Reshape використовуються для поліпшення первісного покриття, яке виходить після процедури Expand. Проте покриття може бути надмірним. Наприклад, для функції Розглянемо основні ідеї, які використовуються в методі ESPRESSO, на прикладі функції Рис. 9.14. Карта Карно функції
Отже, функція Таблиця 9.13 Таблиця покриття функції
З таблиці. 9.13 можна отримати чотири мінімальних покриття, що визначається рівнянням: Запишемо імпліканти функції Застосуємо до цього покриття операцію Reduce. Нехай вона застосовується в порядку номерів i в Fi. Первинний імплікант F1 може бути зведений до порожнього імпліканту, тому що всі його мінтерми покриті іншими імплікантами покриття а. Первинний импликант F2 може бути зведений до Застосувавши операцію Reshape до пари
9.5. Основні алгоритми евристичної мінімізації Метою операції Expand є збільшення розміру кожного імпліканта (збільшення числа позицій, позначених знаком *) деякого покриття а. Це дозволяє видалити з покриття імпліканти меншого розміру, що покриваються отриманими первинними імплікантами. Нехай - знаходження перетину отриманого куба з кубами з множини - знаходження того, що новий куб покриває тільки мінтерм з множин Результат мінімізації (як і її час) залежить від порядку вибору як розширюваних імплікант, так і позицій, в яких 1 замінюються *. У програмах MINI і ESPRESSO використовують наступний підхід для вирішення цього завдання. Кожному набору з L вхідних змінних відповідає набір, що має 2L розрядів. Формується матриця Приклад 9.3. Застосувати процедуру Expand до функції Рис. 9.15. Карта Карно для функції З цієї карти можна отримати три матриці кубів для множини Рис. 9.16. Матричне подання функції Підсумовуючи всі одиниці в колонках матриці Нехай 1 міняються на * зліва направо (з метою спрощення процедури). Змінивши цифру 0 в першій колонці імпликанта Тепер обробляється останній імплікант. При зміні другої колонки отримуємо вектор Цей результат відповідає мінімальній ДНФ Метою операції Reduce є зменшення розмірності кожного імпліканта в початковому покритті для подальшого застосування операції Expand. Після застосування операції Reduce отримують імпліканти. Імплікант називається значущим (valid) імнлікантом, якщо він покриває вихідну функцію разом з рештою імплікантами. При цьому, операція Reduce не зменшує число імплікантів в покритті. Таким чином, покриття може залишатися надмірним. У нашому попередньому прикладі зменшення розмірності імпліканта Операція Irredundant використовується для отримання покриття, яке відрізняється від вихідного максимального можливим числом віддалених надлишкових імплікант. Ця операція була вперше застосована в алгоритмі ESPRESSO і виконується після операції Expand, коли всі імпліканти в покритті є первинними. Таке покриття F ділиться на 3 класи: - клас - клас - клас Для визначення класу Приклад 9.4. Визначити множин Рис. 9.17. Карта Карно для функції Області, обведені на карті, відповідають покриттю F, матрична форма якого наведена на рис. 9.18. Рис. 9.18. Матрична форма покриття F функції З карти Карно на рис. 9.17 можна знайти, що
Тепер необхідно вибрати з безлічі Процедура Essential дозволяє вибрати істотні імпліканти, що необхідно для алгоритмів точної і евристичної мінімізації. Ці імпліканти виключаються з подальшого розгляду і додаються в кінці процесу мінімізації до отриманого програмою покриття. Наприклад, перевіримо суттєвість для імпліканта Всі ці операції використовуються в програмі ESPRESSO, яка дозволяє досить швидко знайти безнадлишкові покриття. В якості оцінки використовується процедура Cost (F), що дозволяє знайти кількість термів в покритті F. Алгоритм виконується до тих пір, поки ціна кожного чергового покриття буде менше, ніж попереднього. Якщо поліпшення не досягнуто, то робиться остання спроба поліпшення рішення, виконувана процедурою last.gasp. У цій процедурі використовуються більш складні евристичні правила, ніж для основного циклу. У зв'язку з цим час процедури last.gasp значно перевищує час ітерації в основному циклі. У спрощеній формі алгоритм ESPRESSO представлений на рис. 9.19. Рис. 9.19 Спрощена блок-схема алгоритму ESPRESSO Читайте також:
|
||||||||
|