Метод Квайна

Метод отримання скороченої диз’юктивної нормальної форми логічної функції називається методом Квайна.

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

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

Fxi Fxi = F

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

Метод Квайна виконується в декілька етапів:

1. В таблиці станів виділяються рядки, в яких вихідна зміна має значення 1.

2. Для кожного рядка, в якому У=1 складають кон’юнкцію всіх вихідних змінних цієї строчки, причому записують Х, якщо зміна приймає значення 1, в іншому випадку записують «не Х». Таким чином, встановлюється стільки складових, скільки є рядків У=1.

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

Приклад 1.7 Скласти комбінаційну схему для наступної умови. Є два вимикача. При включені одного з них загорається лампа (світлодіод). Скласти таблицю роботи.

Рішення:

1. Складаємо таблицю 1.1 роботи:

Таблиця 1.1 – Таблиця роботи схеми

Х1	Х2	У

2. У відповідності з таблицею 1.1 знайдемо функцію:

3. Комбінаційна схема має вигляд:

Приклад 1.8 Скласти комбінаційну схему для наступної таблиці станів:

Таблиця 1.2 – Таблиця станів

Строчка	Х1	Х2	Х3	У

Рішення:

Для третього рядка кон’юнкція:

Для п’ятого рядка кон’юнкція:

Для сьомого рядка кон’юнкція:

Вихідна функція:

Використовуючи закони Булевої алгебри, отримуємо:

Дата добавления: 2015-09-01