Основні положення методу квайна

Нехай вихідна функція зображена у ДДНФ.

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

Будь-який кон’юнктивний терм або група термів, з’єднаних знаками диз’юнкції, що входять у ДДНФ, є імплікантами вихідної функції.

Визначення 15.2. Первинна імпліканта функції – це імпліканта типу елементарної кон’юнкції, ніяка частина якої вже не є імплікантою.

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

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

Метод Квайна включає такі етапи:

– визначення первинних імплікант;

– розміщення міток;

– знаходження істотних імплікант;

– визначення й видалення зайвих стовпців;

– визначення й видалення зайвих первинних імплікант;

– вибір мінімального покриття;

– складання мінімальної форми вихідної функції.