МІНІСТЕРСТВО ОСВІТИ І НАУКИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" МЕТОДИ АНАЛІЗУ ТА СИНТЕЗУ КОМБІНАЦІЙНИХ СХЕМ. МІНІМІЗАЦІЯ МЕТОДОМ КВАЙНА МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи № 3 з курсу «Схемотехніка пристроїв технічного захисту інформації» для студентів базового напряму 6.170102 «Системи технічного захисту інформації» Затверджено на засіданні кафедри «Захист інформації» Протокол № 12 від 07.05.2015р. Львів – 2015  Мета роботи: вивчення методу Квайна мінімізації логічних функцій. 1. ОСНОВНІ ВІДОМОСТІ Метод Квайна мінімізації логічних функцій [1] може бути коротко описаний наступним алгоритмом: Записати задану логічну функцію n змінних в досконалій диз’юнктивній нормальній формі (ДДНФ), тобто як диз’юнкцію мінтермів (елементарних кон’юнкцій n – ого рангу), які відповідають всім одиничним значенням заданої функції. Здійснити всі можливі склеювання мінтермів ДДНФ заданої функції. Результатами склеювання будуть кон’юнкції-імпліканти (n-1) -ого рангу. Зформувати проміжну функцію Z як диз’юнкцію імплікант і тих мінтермів, які не мали пари для склеювання. Здійснити всі можливі склеювання імплікант (n-1) -ого рангу. Результатами склеювання будуть кон’юнкції-імпліканти (n-2) -ого рангу. Зформувати проміжну функцію Z як диз’юнкцію отриманих імплікант (n-2) -ого рангу, мінтермів і імплікант (n-1) -ого рангу, які не мали пари для склеювання. Повторювати пункт 3, поки у функції Z будуть існувати імпліканти, які можна склеїти. Всі імпліканти функції Z, отриманої в пункті 3, є простими, тобто не мають пари для склеювання. Для такої функції Z – скороченої форми заданої логічної функції - побудувати імплікантну таблицю Квайна. Стовпці таблиці відповідають мінтермам заданої логічної функції, а рядки – простим імплікантам функції Z. Таблиця 1 № набору 




 0 0 0 0 0 0  1 0 0 0 1 0  2 0 0 1 0 0  3 0 0 1 1 1  4 0 1 0 0 0  5 0 1 0 1 1  6 0 1 1 0 1  7 0 1 1 1 1  8 1 0 0 0 0  9 1 0 0 1 1  10 1 0 1 0 1  11 1 0 1 1 0  12 1 1 0 0 1  13 1 1 0 1 0  14 1 1 1 0 1  15 1 1 1 1 0  За допомогою імплікантної таблиці Квайна визначити тупикові і мінімальні форми заданої логічної функції. Розглянемо реалізацію описаного алгоритму на прикладі. Приклад. Виконати мінімізацію методом Квайна логічної функції, заданої таблицею істинності (Таблиця 1). Побудувати комбінаційну схему для реалізації мінімізованої функції, використовуючи елементи І, АБО, НЕ. Розв’язання. 1. Перший крок при реалізації даного методу мінімізації - запис заданої функції в ДДНФ, тобто у вигляді диз’юнкції мінтермів, що відповідають одиничним значенням логічної функції. Отже, спираючись на Таблицю 1, записуємо ДДНФ заданої логічної функції. При цьому мінтерми ДДНФ нумеруємо:
(1) Далі переходимо до знаходження простих імплікант за Квайном. Знаходження простих імплікант за Квайном зводиться до пошуку пар мінтермів та імплікант, що склеюються між собою. Для нашого прикладу цей процес буде виглядати так: 1-ий етап: на цьому етапі здійснюємо всі можливі склеювання мінтермів функції (1). Для цього перебираємо всі можливі пари мінтермів у функції (1):
не склеюються
не склеюються,

: :









Отже, ми виконали всі можливі склеювання мінтермів. Аналізуючи результати склеювання робимо висновок, що з восьми мінтермів функції (1) тільки п’ятий не мав пари для склеювання. На основі результатів склеювання записуємо новий варіант функції Z. Для цього спочатку записуємо диз’юнкцію імплікант, отриманих при склеюванні (в даному випадку імпліканти - це кон’юнкції трьох змінних). При цьому не допускаємо повторення однакових імплікант. Далі дописуємо диз’юнкцію мінтермів, що не мали пари для склеювання (в даному прикладі – п’ятий мінтерм функції (1)). Імпліканти нумеруємо. Отримаємо вираз (2).
(2) Далі перевіряємо всі імпліканти 3-го рангу з виразу (2) на можливість склеювання. В даному прикладі жодна імп...