Реферат на тему:
Мінімізація функцій алгебри логіки методом карт Карно. Мінімізація
функцій алгебри логіки методом Квайна-Мак-Класкі
Під мінімізацією ФАЛ розуміють перетворення її алгебраїчного виразу з
метою отримання найпростішого виду функції. В інженерній практиці для
мінімізації найширше застосування отримали наступні методи:
метод послідовного спрощення, що базується на застосуванні основних
законів і тотожностей алгебри логіки;
метод, який базується на застосуванні карт Карно;
метод Квайна-Мак-Класкі.
При застосуванні метода карт Карно проводиться накриття карти за
допомогою правильних конфігурацій, що містять нулі або одиниці
(див. рис. 8). Правильними конфігураціями на карті Карно для функції
алгебри логіки з n-змінними є всі прямокутники (горизонтальні,
вертикальні, квадрати), які мають площу 2n-i (i = 0, 1, 2 …, n).
При накриванні ФАЛ стараються, щоб кількість накриттів на карті була
мінімальною, а площа, що накривається кожною з правильних конфігурацій
була максимальною. Конфігурації можуть перекриватись, накладатись одна
на одну. При виборі накриття можливе об’єднання крайніх полів, що
розміщені на крайніх протилежних сторонах карти в горизонтальному або
вертикальному напрямках. Принцип мінімізації полягає в об’єднанні
сусідніх полів карти в межах правильних конфігурацій. При знаходженні
мінімальної форми ФАЛ виписуються усі змінні, які не змінюють свого
значення в межах правильної конфігурації.
При об’єднанні полів, в яких записані одиниці функція алгебри логіки
пишеться в диз’юнктивній нормальній формі, тобто у виді диз’юнкцій
добутків змінних, які незмінні в межах кожної конфігурації накриття. При
об’єднанні полів, що містять нулі, ФАЛ записується в кон’юнктивній
нормальній формі, тобто у виді добутків диз’юнкцій інверсних значень
змінних, які не змінюються при переході з одного поля конфігурації на
інше. Приклади мінімізації декількох ФАЛ методом карт Карно наведені на
рис. 8.
Рисунок 8 Приклади мінімізації функцій алгебри логіки методом карт Карно
Мінімізація функцій алгебри логіки методом Квайна-Мак-Класкі.
Даний метод базується на задаванні функцій елементарних змінних, що
входять в ДДНФ у виді двійкових чисел, які називаються номерами
відповідних наборів. Крім номера кожному добуткові присвоюється
визначений індекс, під яким розуміють кількість одиниць у двійковому
поданні даного набору. Наприклад:
, номер 010 (2), індекс 1(І)
, номер 110 (6), індекс 2(ІІ)
В результаті реалізації даного методу функція алгебри логіки
розкладається на прості імпліканти. Під простою імплікантою функції
розуміють будь-який елементарний добуток, що приймає одиничне значення
на всіх наборах аргументів, що і вхідна ФАЛ і при виключенні з якого
хоча б одного аргументу, вже не виконуватиметься дана умова.
†
e
а і число з більшим індексом було більше за число з меншим індексом.
Реалізацію алгоритму розглянемо на прикладі мінімізації ФАЛ:
На першому етапі мінімізації визначаємо номери та індекси кожного
набору, записуючи ФАЛ у виді:
1I 5II 10II 7III 11III 3II
Групуємо набори і розміщуємо їх в порядку зростання індексів
(див.табл. 4).
На наступному етапі поводимо склеювання різних наборів, керуючись
наведеним формулюванням алгоритму. При склеюванні розряди чисел, що не
співпадають відмічаються почерками. Наприклад, склеювання чисел 0001 та
0011 дає число 00-1. Результат склеювання виписується в наступний
стовпець таблиці, який так само розділюється на стрічки з індексами, які
відрізняються на одиницю. Після склеювання всіх груп першого стовпця
таблиці переходять до другого, переписуючи результат склеювання в третій
стовпець. При об’єднанні наборів третього і наступних стовпців таблиці
можна склеювати тільки сила, що містять прочерки в однойменних розрядах.
Склеювання продовжується до тих пір, поки неможливо буде створити новий
стовпець.
Таблиця 4 Мінімізація функцій алгебри логіки методом Квайна-Мак-Класкі.
Індекси Номери Результат склеювання
І 0001 (1) 00-1 (1, 3)
0–01 (1, 5) 0–1 (1, 3, 5, 7)
0–1 (1, 5, 3, 7)
ІІ 0011 (3)
0101 (5)
1010 (10) 0–11 (3, 7)
-011 (3, 11)
01–1 (5, 7)
101- (10, 11)
ІІІ 0111 (7)
1011 (11)
Після завершення склеювання приступають до побудови імплікантної
таблиці (див.табл. 5), записуючи в неї в якості простих імплікант
набори, що містяться в останньому стовпці табл.4. В якості простих
імплікант в табл.5 також вписуються набори з тих стовпців табл.4, котрі
не приймали участі у склеюванні. Якщо імпліканта, яка міститься в і-й
лінійці таблиці складає деяку частину конституанти і-го стовпця на
перетині і-тої лінійки та і-го стовпця ставиться символ “*”. З метою
отримання мінімальної форми ФАЛ із табл.5 необхідно вибрати мінімальну
кількість лінійок, щоб для кожного стовпця серед вибраних лінійок
знайшлася хоча б одна, що містить в цьому стовпці символ “*”.
Таблиця 5 Імплікантна таблиця мінімізованої ФАЛ
Набори 1 5 10 7 11 3
Імпліканти
* * * *
* *
* *
Отримана після мінімізації ФАЛ (приклад мінімізованої ФАЛ подано для
розглянутого варіанту) записується в наступному виді:
.
Використана література:
Основы промышленной электроники/ Под ред. В.Г. Герасимова. -М.: Высшая
школа, 1978.
Изъюрова Г.И., Кауфман М.С. Приборы и устройства промышленной
электроники. -М.: Высшая школа, 1975.
Миклашевский С.П. Промышленная электроника. -М.: Высшая школа, 1973.
Горбачев Г.Н., Чаплыгин Е.Е. Промышленная электроника. – М.: Высшая
школа, 1988.
Основы промышленной электроники/Под ред. В.Г. Герасимова. – М.: высшая
школа, 1982.
Гершунский В.С. Основы электроники. – К.: Вища школа, головн. из-во,
1982.
Жеребцов И.П. Основы электроники. – Л.:Энергоатомиздат, 1985.
Нагорский В.Д. Электроника и электрооборудование. – М.: Высшая школа,
1986.
Нашли опечатку? Выделите и нажмите CTRL+Enter
