Contents

СТОРІНКИ |  |

3.1. Мета мінімізації логічних пристроїв

3.2. Метод безпосередніх перетворень

3.3. Метод Карно-Вейча

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

Лабораторний практикум

Висновки

Тестування

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

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

Алгоритм пошуку МДНФ цим методом такий.

1. Знаходять покриття П(z) заданої функції. Для цього формують кубічний комплекс логічної функції й у кожному i-му кубічному комплексі відзначають куби (імпліканти), що не утворили i+1-й кубічний комплекс. Відзначені імпліканти, які називають простими, утворять покриття заданої логічної функції.

2. Будують таблицю покриттів матриці Квайна. Рядки зазначеної таблиці відповідають простим імплікантам, а стовпчики – 0-кубам (конституентам одиниці) функції. На перетинанні i-го рядка і j-го стовпчика ставлять позначку, якщо імпліканта i покриває конституенту j. Зазначимо, що імпліканта i покриває конституенту j у разі, якщо вона відрізняється від неї незалежними аргументами.

3. Визначають покриття мінімальної вартості. Для цього:

– виділяють ядро Квайна. Якщо 0-куб заданої логічної функції покривається тільки однією простою імплікантою, то остання є істотною і входить у ядро Квайна і, отже, у покриття мінімальної вартості;

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

– стискують таблицю по стовпчиках, для чого з неї викреслюють стовпчики, в які цілком входить будь-який із стовпчиків, що залишився;