Метод Куайна

Метод Куайна — спосіб мінімізації функцій алгебри логіки. Представляє функції у вигляді ДНФ або КНФ з мінімальною кількістю членів і з мінімальним набором змінних.

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

Сам метод проходить в два етапи:

• Перехід від канонічної форми (ДДНФ або ДКНФ) до скороченої форми.
• Перехід від скороченої до мінімальної форми.

Перший етап (перехід до скороченої форми)[ред. | ред. код]

Здійснюється перехід від канонічної форми запису (ДДНФ) до скороченої на основі формули склеювання ${\displaystyle {w}\cdot {x}\lor {w}\cdot {\overline {x}}={w}\cdot ({x}\lor {\overline {x}})={w}}$, де ${\displaystyle {w}}$ однакова частина обох кон'юнкцій, ${\displaystyle {x}}$ — змінна, яка має протилежне значення.

Якщо потрібно отримати мінімальну КНФ, тоді правило склеювання має такий вигляд: ${\displaystyle ({w}\lor {x})\cdot ({w}\lor {\overline {x}})={w}}$.

Другий етап (отримання мінімальної форми)[ред. | ред. код]

Здійснюється перехід від скороченої форми до мінімальної шляхом поглинання ${\displaystyle {w}\lor {w}\cdot {z}={w}\cdot (1\lor {z})={w}}$ (член ${\displaystyle \mathbf {w} }$ поглинає вираз ${\displaystyle {w}\cdot {z}}$).

У випадку необхідності отримати отримання мінімальної КНФ операція поглинання має такий вигляд: ${\displaystyle {z}\cdot ({z}\vee {y})={z}\vee {z}\cdot {y}={z}\cdot (1\vee {y})={z}}$.

Приклад отримання мінімальної ДНФ[ред. | ред. код]

Нехай ми маємо функцію, задану за допомогою таблиці істинності.

# ${\displaystyle {x_{1}}}$ ${\displaystyle {x_{2}}}$ ${\displaystyle {x_{3}}}$ ${\displaystyle {x_{4}}}$ ${\displaystyle f({x_{1}},{x_{2}},{x_{3}},{x_{4}})}$ 0 0 0 0 0 1 1 0 0 0 1 1 2 0 0 1 0 0 3 0 0 1 1 0 4 0 1 0 0 1 5 0 1 0 1 0 6 0 1 1 0 1 7 0 1 1 1 1

# ${\displaystyle {x_{1}}}$ ${\displaystyle {x_{2}}}$ ${\displaystyle {x_{3}}}$ ${\displaystyle {x_{4}}}$ ${\displaystyle f({x_{1}},{x_{2}},{x_{3}},{x_{4}})}$ 8 1 0 0 0 1 9 1 0 0 1 1 10 1 0 1 0 0 11 1 0 1 1 0 12 1 1 0 0 0 13 1 1 0 1 0 14 1 1 1 0 1 15 1 1 1 1 1

Запишемо ДДНФ функції, заданої ТІ. В формулі кожну кон'юнкцію пронумеруємо відповідно до її порядкового номера в ТІ. Нумерація потрібна для відслідкування попарного перебору всіх кон'юнкцій на предмет застосування правила склеювання.

${\displaystyle f=}$	${\displaystyle ({\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}\cdot {\overline {x_{4}}})_{0}\lor ({\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}\cdot {x_{4}})_{1}\lor ({\overline {x_{1}}}\cdot {x_{2}}\cdot {\overline {x_{3}}}\cdot {\overline {x_{4}}})_{4}\lor ({\overline {x_{1}}}\cdot {x_{2}}\cdot {x_{3}}\cdot {\overline {x_{4}}})_{6}\lor }$
	${\displaystyle \lor ({\overline {x_{1}}}\cdot {x_{2}}\cdot {x_{3}}\cdot {x_{4}})_{7}\lor ({x_{1}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}\cdot {\overline {x_{4}}})_{8}\lor ({x_{1}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}\cdot {x_{4}})_{9}\lor ({x_{1}}\cdot {x_{2}}\cdot {x_{3}}\cdot {\overline {x_{4}}})_{14}\lor ({x_{1}}\cdot {x_{2}}\cdot {x_{3}}\cdot {x_{4}})_{15}}$

На першому етапі порівнюємо попарно всі кон'юнкції (мінітерми четвертого рангу). Склеюванню підлягають лише ті, що відрізняються інверсією лише однієї змінної. Це 0 і 1, 0 і 4, 0 і 8, 1 і 9, 4 і 6, 6 і 7, 6 і 14, 7 і 15, 8 і 9, 14 і 15 кон'юнкції.

${\displaystyle f=}$

${\displaystyle ({\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}})_{0-1}\lor ({\overline {x_{1}}}\cdot {\overline {x_{3}}}\cdot {\overline {x_{4}}})_{0-4}\lor ({\overline {x_{2}}}\cdot {\overline {x_{3}}}\cdot {\overline {x_{4}}})_{0-8}\lor ({\overline {x_{2}}}\cdot {\overline {x_{3}}}\cdot {x_{4}})_{1-9}\lor ({\overline {x_{1}}}\cdot {x_{2}}\cdot {\overline {x_{4}}})_{4-6}\lor }$

${\displaystyle \lor ({\overline {x_{1}}}\cdot {x_{2}}\cdot {x_{3}})_{6-7}\lor ({x_{2}}\cdot {x_{3}}\cdot {\overline {x_{4}}})_{6-14}\lor ({x_{2}}\cdot {x_{3}}\cdot {x_{4}})_{7-15}\lor ({x_{1}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}})_{8-9}\lor ({x_{1}}\cdot {x_{2}}\cdot {x_{3}})_{14-15}}$

За номерами мінітермів перевіряємо чи всі початкові мінітерми четвертого рангу склеїлися. В отриманій формулі присутні номери всіх початкових кон'юнкцій, що всі вони піддалися первинному склеюванню. У випадку, якщо номер якоїсь кон'юнкції відсутній в отриманій формулі, вона має бути введена в неї через знак диз'юнкції, для уникнення викривлення результату. Далі, за можливості, до мінітермів одного рангу знов застосовуємо правило склеювання. В отриманій функції склеюванню піддаються наступні мінітерми третього рангу 0-1 і 8-9, 0-8 і 1-9, 6-7 і 14-15, 6-14 і 7-15. В результаті утворюються мінітерми другого рангу. При цьому мінітерми 0-4 і 4-6 не піддаються склеюванню і через це присутні в скороченій формі функції.

${\displaystyle f=({\overline {x_{2}}}\cdot {\overline {x_{3}}})_{0-1/8-9}\lor ({\overline {x_{2}}}\cdot {\overline {x_{3}}})_{0-8/1-9}\lor ({\overline {x_{1}}}\cdot {\overline {x_{3}}}\cdot {\overline {x_{4}}})_{0-4}\lor ({\overline {x_{1}}}\cdot {x_{2}}\cdot {\overline {x_{4}}})_{4-6}\lor ({x_{2}}\cdot {x_{3}})_{6-7/14-15}\lor ({x_{2}}\cdot {x_{3}})_{6-14/7-15}}$

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

На другому етапі складається імплікантна таблиця, або таблиця поглинань (перекриттів). Ця таблиця дозволяє спростити застосування правило поглинання і одночасно відслідкувати, чи всі початкові кон'юнкції (імпліканти) враховані в спрощеній функції.

#	Спрощені імпліканти	Початкові імпліканти
		${\displaystyle {\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}\cdot {\overline {x_{4}}}}$	${\displaystyle {\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}\cdot {x_{4}}}$	${\displaystyle {\overline {x_{1}}}\cdot {x_{2}}\cdot {\overline {x_{3}}}\cdot {\overline {x_{4}}}}$	${\displaystyle {\overline {x_{1}}}\cdot {x_{2}}\cdot {x_{3}}\cdot {\overline {x_{4}}}}$	${\displaystyle {\overline {x_{1}}}\cdot {x_{2}}\cdot {x_{3}}\cdot {x_{4}}}$	${\displaystyle {x_{1}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}\cdot {\overline {x_{4}}}}$	${\displaystyle {x_{1}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}\cdot {x_{4}}}$	${\displaystyle {x_{1}}\cdot {x_{2}}\cdot {x_{3}}\cdot {\overline {x_{4}}}}$	${\displaystyle {x_{1}}\cdot {x_{2}}\cdot {x_{3}}\cdot {x_{4}}}$
1	${\displaystyle {\overline {\mathbf {x} _{2}}}\cdot {\overline {\mathbf {x} _{3}}}}$	V	V				V	V
2	${\displaystyle {\overline {x_{1}}}\cdot {\overline {x_{3}}}\cdot {\overline {x_{4}}}}$	V		V
3	${\displaystyle {\overline {x_{1}}}\cdot {x_{2}}\cdot {\overline {x_{4}}}}$			V	V
4	${\displaystyle {\mathbf {x} _{2}}\cdot {\mathbf {x} _{3}}}$				V	V			V	V
рядок перекриттів		V	V	V	V	V	V	V	V	V
Примітки: 1. Жирним виділені ті спрощені імпліканти, що складають ядро функції. 2. Червоним виділені ті комірки, що увійдуть у рядок перекриттів через "ядерність" відповідних імплікантів. 3. Зеленим виділені дві комірки з яких можемо вибирати будь-яку. 4. Позначки першого ядра показані жирним, косим шрифтом, другого просто жирним, а позначки додатків - звичайним шрифтом.

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

Ядро функції — скорочена імпліканта, яка одноосібно перекриває які-небудь стовпці таблиці (тобто в цих стовпцях стоїть лише одна позначка).

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

Додаток — скорочена імпліканта, яка дозволяє оптимальним чином заповнити комірки рядка перекриттів, що залишилися. Додаток необхідно обирати таким чином, щоб вони були як найпростіші (мали меншу кількість змінних, інверсій) і одночасно перекривали якомога більше незаповнених комірок рядка перекриттів. При цьому формула спрощеної функції буде складатися з ядер і додатків.

В нашому варіанті вибір додатків такий: ${\displaystyle {\overline {x_{1}}}\cdot {\overline {x_{3}}}\cdot {\overline {x_{4}}}}$ і ${\displaystyle {\overline {x_{1}}}\cdot {x_{2}}\cdot {\overline {x_{4}}}}$. В даному випадку обираємо другий варіант через меншу кількість інверсій.

Тож отримуємо мінімізований методом Куайна варіант функції: ${\displaystyle f={\overline {x_{2}}}\cdot {\overline {x_{3}}}\lor {\overline {x_{1}}}\cdot {x_{2}}\cdot {\overline {x_{4}}}\lor {x_{2}}\cdot {x_{3}}}$

Недоліки[ред. | ред. код]

Метод Куайна має один істотний недолік, який пов'язаний з необхідністю повного попарного порівняння членів ДДНФ (ДКНФ). При цьому з ростом числа членів зростає і кількість порівнянь у факторіальній залежності. В 1956 Мак-Класкі модернізував метод Куайна, це дозволило зменшити кількість порівнянь.

Див. також[ред. | ред. код]

• Метод Куайна — Мак-Класкі
• Карта Карно

Література[ред. | ред. код]

• «Прикладна теорія цифрових автоматів», Київ «Вища Школа» 1987, К. Г. Самофалов, А. М. Романкевич, В. Н. Валуйский, Ю. С. Каневский, М. М. Пиневич.
• Порубльов, І. М. (2018). Дискретна математика. Навчальний посiбник для студентiв 1-го курсу бакалаврату галузi знань «Iнформацiйнi технологiї» та спорiднених (PDF). ФОП Гордієнко Є. І. с. 23. ISBN 9789669730483. {{cite book}}: Перевірте значення |isbn=: контрольна сума (довідка)

Посилання[ред. | ред. код]

• Мінімізація ДНФ, Інтернет-ресурс для мінімізації ДНФ методом Куайна - Мак-Класкі.