Читать реферат по всему другому: "Мінімізація функцій алгебри логіки методом карт Карно. Мінімізація функцій алгебри логіки методом Квайна-Мак-Класкі" Страница 1

(Назад) (Cкачать работу)

Реферат на тему:

Мінімізація функцій алгебри логіки методом карт Карно. Мінімізація функцій алгебри логіки методом Квайна-Мак-Класкі

Під мінімізацією ФАЛ розуміють перетворення її алгебраїчного виразу з метою отримання найпростішого виду функції. В інженерній практиці для мінімізації найширше застосування отримали наступні методи:

метод послідовного спрощення, що базується на застосуванні основних законів і тотожностей алгебри логіки;

метод, який базується на застосуванні карт Карно;

метод Квайна-Мак-Класкі.

При застосуванні метода карт Карно проводиться накриття карти за допомогою правильних конфігурацій, що містять нулі або одиниці (див. рис. 8). Правильними конфігураціями на карті Карно для функції алгебри логіки з n-змінними є всі прямокутники (горизонтальні, вертикальні, квадрати), які мають площу 2n-i (i = 0, 1, 2 …, n).

При накриванні ФАЛ стараються, щоб кількість накриттів на карті була мінімальною, а площа, що накривається кожною з правильних конфігурацій була максимальною. Конфігурації можуть перекриватись, накладатись одна на одну. При виборі накриття можливе об’єднання крайніх полів, що розміщені на крайніх протилежних сторонах карти в горизонтальному або вертикальному напрямках. Принцип мінімізації полягає в об’єднанні сусідніх полів карти в межах правильних конфігурацій. При знаходженні мінімальної форми ФАЛ виписуються усі змінні, які не змінюють свого значення в межах правильної конфігурації.

При об’єднанні полів, в яких записані одиниці функція алгебри логіки пишеться в диз’юнктивній нормальній формі, тобто у виді диз’юнкцій добутків змінних, які незмінні в межах кожної конфігурації накриття. При об’єднанні полів, що містять нулі, ФАЛ записується в кон’юнктивній нормальній формі, тобто у виді добутків диз’юнкцій інверсних значень змінних, які не змінюються при переході з одного поля конфігурації на інше. Приклади мінімізації декількох ФАЛ методом карт Карно наведені на рис. 8.

Рисунок 8 Приклади мінімізації функцій алгебри логіки методом карт Карно

Мінімізація функцій алгебри логіки методом Квайна-Мак-Класкі.

Даний метод базується на задаванні функцій елементарних змінних, що входять в ДДНФ у виді двійкових чисел, які називаються номерами відповідних наборів. Крім номера кожному добуткові присвоюється визначений індекс, під яким розуміють кількість одиниць у двійковому поданні даного набору. Наприклад:

Набір , номер 010 (2), індекс 1(І)

Набір , номер 110 (6), індекс 2(ІІ)

В результаті реалізації даного методу функція алгебри логіки розкладається на прості імпліканти. Під простою імплікантою функції розуміють будь-який елементарний добуток, що приймає одиничне значення на всіх наборах аргументів, що і вхідна ФАЛ і при виключенні з якого хоча б одного аргументу, вже не виконуватиметься дана умова.

Алгоритм Квайна-Мак-Класкі формулюється наступним чином: для того, щоб два числа m та n були номерами двох наборів, що склеюються між собою, необхідно і достатньо, щоб індекси даних чисел відрізнялись на одиницю, самі числа відрізнялись на степінь числа два і число з більшим індексом було більше за число з меншим індексом.

Реалізацію алгоритму розглянемо на прикладі мінімізації ФАЛ:

На першому етапі мінімізації