![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Форми зображення логічних функцій.
Будь-яку логічну функцію можна задати або зобразити у різних формах: словесне, таблично, числового запису, аналітичне і координатної карти чи діаграми. Розглдаємо кожну з цих форм окремо. Словесне зображення – це логічне висловлення, під яким розуміють довільне твердження, щодо якого можна сказати, істинне воно або хибне. Словесне зображення – це логічне висловлення, під яким розуміють довільне твердження, щодо якого можна сказати, істинне воно або хибне. Наприклад, функцію Табличне зображення характеризується таблицею істинності, яка має Кожний спосіб чи форма зображення має свою специфіку і тому буде зручною там, де даний спосіб є найбільш простим чи компактним. Таблична форма запису хоча й наочна і може бути застосована для довільного числа змінних, однак при аналізі властивостей функції такий запис не є компактним. Для випадку чотирьох і більше змінних табличне зображення логічної функції є суттєво складнішим та громіздким. Простішим буде числовий запис, коли логічна функція задається у вигляді послідовності десяткових чисел, що є еквівалентами тих вхідних наборів, на яких дана функція набував значення 1 або 0.
Таблиця 6
При аналітичному зображенні функція задається алгебраїчним виразом, який отримують при застосуванні логічних операцій до змінних бульової алгебри. Якщо попередні форми зображення логічної функції лише вказують значення функції на конкретних наборах змінних, то аналітичне зображення, крім того, ще дозволяв виконувати різні аналітичні перетворення, які необхідні як для аналізу, так і для синтезу цифрового пристрою, що реалізує або мав реалізувати дану логічну функцію. Нехай на фіксованому вхідному наборі { В інших випадках, наприклад, коли набір { Найбільш раціональним є зображення логічних функцій в так званих нормальних (канонічних) формах запису, зокрема, у вигляді диз’юнкції кон’юнкцій або кон’юнкції диз’юнкцій змінних, що взяті з інверсіями або без них. Окремі вирази функції змінних * Терм (від англ. term – вираз, член) – поняття алгебри логіки, що аналогічне поняттю іменника у граматиці. Кон’юнктивний терм (мінтерм або конституента одиниці)
Наприклад, або Диз’юнктивний терм (макстерм або конституента нуля)
Наприклад, або Ранг терма Згідно із законом дуальності будь-яку логічну функцію n-змінних можна зобразити як диз’юнкцію кон’юнкцій (мінтерм) або як кон’юнкцію диз’юнкцій (макстерм) змінних. Однозначне зображення логічних функцій одержують тільки при так-званих удосконалених нормальних формах (УНФ), тобто таких, при яких мінтерми або макстерми формуються з усіх аргументів логічної функції і в одного (причому максимального) рангу. Якщо логічна функція складається з набору диз’юнкцій елементарних кон’юнкцій одного рангу, її називають удосконаленою диз’юнктивно нормальною формою (УДНФ), а якщо– з набору кон’юнкцій елементарних диз’юнкцій – удосконаленою кон’юнктивно нормальною формою (УКНФ) зображення. Для n-змінних складається В загальному випадку алгебраїчний вираз логічної функції в УДНФ набуває вигляду
де В УКНФ загальний вираз логічної функції
де Застосовуючи закони алгебри логіки (див. табл.3), неважко довести еквівалентність обох форм зображення будь-якої логічної функції. Такі форми зображення логічних функцій необхідні при проектуванні цифрових пристроїв. Для згаданого прикладу (див. табл.6) можна записати два тотожних (дуальних) вирази логічної функції. Беручи лише до уваги конституенти 1, маємо
а для конституент 0
Отже, якщо логічну функцію задано таблично, то для переходу до її аналітичного зображення в УНФ роблять так: для зображення в УДНФ виписують ті набори змінних, для яких функція дорівнює одиниці, тобто для конституент 1; для кожного такого набору складають мінтерм, причому змінні для зображення в УКНФ виписують набори, для яких функція дорівнює нулю, тобто для конституент 1; для кожного набору складають макстерм, причому змінні Слід зауважити, що в даному прикладі вибір форми зображення логічної функції не має принципового значення, бо число мінтерм дорівнюз числу макстерм. Проте у випадках, коли число одних переважав над числом інших, наприклад, кількість Досить зручним і наглядним зображенням логічної функції є координатний спосіб, тобто у вигляді координатної карти (таблиці, діаграми) логічних станів. Одною з координатних форм зображення логічної функції, що знайшла найбільше поширення в інженерній практиці для досить незначного числа змінних Карта Карно будується так, щоб сусідні клітинки відрізнялися значенням тільки одної змінної. Сусідніми вважаються ті клітинки карти Карно, які дотикаються своїми сторонами, а також клітинки, що розташовані по краях карти (у верхньому і нижньому рядках та лівому і правому стовпцях). На рис.1.2, а-в, показані таблиці Карно для логічних функцій відповідно двох, трьох і чотирьох змінних. а) б) в) Рис. 1.2. Таблиці Карно.
Таблицю Карно для п’яти і більше змінних розглядають як складену з меншого числа змінних, тобто з двох або біпьше простих підкарт. Наприклад, карту для п’яти змінних будують як дві підкарти для чотирьох змінних. При цьому зручно під’єднати (склеїти) їх одну до одної зі сторони одно іменних стовпців. Сусідніми клітинками тоді будуть також клітинки стовпців, що симетрично розташовані відносно лінії з’єднання підкарт для чотирьох змінних одноіменних рядків. Для логічних функцій з числом змінних Зведення логічної функції до УНДФ або до УКНФ дає однозначне зображення Мінімізація – це процес зведення логічної функції до такого виду, який припускає більш просту і дешеву її фізичну реалізацію, тобто з меншим числом логічних елементів за рахунок зменшення числа логічних символів, кількості змінних та зв’язків між елементами. Відомо кілька методів мінімізації [2-4], серед яких найбільш поширеними в інженерній практиці є такі: · безпосередніх перетворень; · карт Карно; · Квайна. Знайти гарантовано мінімальний вираз для довільної логічної функції можна лише методом повного перебору в процесі мінімізації всіх можливих варіантів. Від руки (на папері) це реально здійснити для невеликої кількості змінних. Із збільшенням числа змінних складність розглянутих методів мінімізації зростає за геометричною прогресією і стає під силу лише автоматизованим методам, які призначені для ЕОМ. Розглянемо перераховані методи мінімізації логічних функцій. Метод безпосередніх перетворень – це аналітичний метод спрощення логічних функцій з допомогою аксіом та законів бульової алгебри. При набутті певних навичок цей метод є досить ефективним для малої кількості змінних (як правило, не більше трьох). Для мінімізації логічних функцій методом безпосередніх перетворень корисно використовувати такі формули бульової алгебри:
У деяких випадках ефективніше мінімізувати інверсію логічної функції для отримання простішого виразу в МДНФ. Це може бути тоді, коли логічна функція має переважаюче число одиниць, ніж кулів. Тоді, маючи МДНФ інверсної функції, при технічній реалізації цієї функції достатньо на виході побудованої схеми під’єднати інвертор для відновлення прямої функції. Метод таблиць (карт) Карно застосовують переважно для мінімізації логічних функцій невеликого числа змінних ( Суть мінімізації за допомогою карт Карно полягає в тому, що шукаються мінтерми (конституенти 1), які “склеюються” за законом склеювання для диз’юнкції. Склеєними вважаються сусідні одиниці, які розташовані як у вертикальних, так і у горизонтальних клітинках. Сусідніми вважаються також клітинки, які стають суміжними після згортання карти у горизонтальний і у вертикальний циліндр. Це бував тільки для випадку логічних функцій, що мають три або більше змінних. Оскільки дві сусідні клітинки карти Карно відрізняються лише на одну зміну, диз’юнкція цих двох мінтермів дає один кон’юнктивний член, з якого вилучена спільна змінна (згідно із законом склеювання для диз’юнкцїй). У карті Карно клітинки з одиницями графічно об’єднують обведенням контурів, що відповідає процедурі покриття. Це еквівалентно. виділенню спрощеного мінтерма, а саме – доповнення типу ( Зауважимо, що будувати карту Карно для логічної функції двох змінних недоцільно. В цьому випадку простіше функцію мінімізувати аналітичним методом. Таким чином, процес мінімізації за допомогою каpт Карно зводиться до знаходження найбільших за площею покриттів з Проілюструємо процес мінімізації методом карт Карно на прикладі для логічної функції:
Спочатку задану функцію зобразимо картою Карно, розміщуючи у відповідні клітинки конституенти 1 (рис.1.3). Далі об’єднуємо конституенти сусідніх клітинок (тобто виконуємо покриття), у даному випадку по дві одиниці (контур Рис. 1.3. Метод склеювання клітинок таблиць Карно.
|