Методичні вказівки до лабораторних занять з дисципліни «прикладна теорія цифрових автоматів», страница 12

Такими канонічними формами є: досконала диз’юнктивна нормальна форма (ДДНФ) та досконала кон’юнктивна нормальна форма (ДКНФ).

Термін «диз‘юнктивна» вказує на те, що зовнішньою функцією розкладу є диз’юнкция, а внутрішньою – кон’юнкція, бо для обчислення значень функцій треба визначити значення всіх кон’юнкцій, а після цього обчислити їх диз’юнкцію.

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

Синтез комбінаційної схеми проводять, виходячи з таблиці істинності, що описує роботу комбінаційної схеми, що синтезується. Застосовуючи різні методи мінімізації, знаходять мінімальну диз’юнктивну форму (МДНФ) функції.

З великого числа різних методів мінімізації найбільш розроблені три методи:

·  розрахунковий метод (метод безпосередніх перетворень);

·  розрахунково-табличний метод (метод Квайна Мак-Класкі);

·  табличний метод (метод карт Карно).

Розглянемо більш докладно останній метод мінімізації за допомогою карт (діаграм) Карно, як один із найбільш зручних методів спрощення логічних функцій при невеликому числі змінних, розроблений у 1953 р. Морісом Карно. Карта Карно є певною таблицею істинності для двох, трьох та чотирьох аргументів. Різні види карт Карно зображені на рис. 2.1, 2.2, 2.3, 2.4.

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

Для мінімізації БФ із допомогою методу Карно необхідно по таблиці істинності заповнити карту, після чого провести прямокутні або квадратні контури за наступним правилам:

1. Всередині контура мають бути клітки, що містять тільки одиниці (первісна форма ДДНФ).