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

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

Складність

Незважаючи на більшу можливість практичного застосування ніж у карт Карно, коли мова йде про більше ніж чотири змінних, метод Куайна — Мак-Класкі теж має обмеження області застосування через експоненціальне зростання часу зі збільшенням кількості змінних. Можна показати, що для функції від n змінних верхня границя кількості основних імплікант 3ⁿ/n. Якщо n = 32 їх може бути більше ніж 6.5 * 10¹⁵. Функції з великою кількістю змінних мають бути мінімізовані з допомогою потенційно не оптимального евристичного алгоритму, на сьогодні евристичний алгоритм мінімізації є фактичним світовим стандартом.

Приклад

Крок 1: знаходимо основні імпліканти

Нехай функція задана за допомогою наступної таблиці істинності:

# ${\displaystyle {x}}$ ${\displaystyle {y}}$ ${\displaystyle {z}}$ ${\displaystyle {t}}$ ${\displaystyle f({x},{y},{z},{t})}$ 0 0 0 0 0 0 1 0 0 0 1 0 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 0 7 0 1 1 1 0

# ${\displaystyle {x}}$ ${\displaystyle {y}}$ ${\displaystyle {z}}$ ${\displaystyle {t}}$ ${\displaystyle f({x},{y},{z},{t})}$ 8 1 0 0 0 1 9 1 0 0 1 x 10 1 0 1 0 1 11 1 0 1 1 1 12 1 1 0 0 1 13 1 1 0 1 0 14 1 1 1 0 x 15 1 1 1 1 1

Можна легко записати ДДНФ, просто просумувавши мінтерми (не звертаючи увагу на ) де функція приймає значення 1.

${\displaystyle f=x'yz't'+xy'z't'+xy'zt'+xy'zt+xyz't'+xyzt.}$

Для оптимізації запишемо мінтрерми, включно із тими, що відповідають байдужим станам, в наступну таблицю:

Кількість 1	Мінтерм	Двійкове представлення
1	m4	0100
	m8	1000
2	m9	1001
	m10	1010
	m12	1100
3	m11	1011
	m14	1110
4	m15	1111

Тепер можна починати комбінувати між собою мінтерми (фактично проводити операцію склеювання). Якщо два мінтерми відрізняються лише символом, що стоїть в одній і тій самій позиції в обох, заміняємо цей символ на «-», це означає, що даний символ для нас не має значення. Терми, що не піддаються подальшому комбінуванню позначаються «*». При переході до імплікант другого рангу, трактуємо «-» як третє значення. Наприклад: -110 і -100 або -11- можуть бути скомбіновані, але не -110 і 011-. (Підказка: Спершу порівнюй «-».)

Кількість 1 Мінтерми | Імпліканти 1-го рівня | Імпліканти 2го рівня ------------------------------|-----------------------|---------------------- 1 m4 0100 | m(4,12) -100* | m(8,9,10,11) 10--* m8 1000 | m(8,9) 100- | m(8,10,12,14) 1--0* ------------------------------| m(8,10) 10-0 |---------------------- 2 m9 1001 | m(8,12) 1-00 | m(10,11,14,15) 1-1-* m10 1010 |-----------------------| m12 1100 | m(9,11) 10-1 | ------------------------------| m(10,11) 101- | 3 m11 1011 | m(10,14) 1-10 | m14 1110 | m(12,14) 11-0 | ------------------------------|-----------------------| 4 m15 1111 | m(11,15) 1-11 | | m(14,15) 111- | 

Крок 2: таблиця простих імплікант

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

	4	8	10	11	12	15
m(4,12)	X				X		-100
m(8,9,10,11)		X	X	X			10--
m(8,10,12,14)		X	X		X		1--0
m(10,11,14,15)			X	X		X	1-1-

Принцип вибору імплікант такий самий як і в методі Куайна. Прості імпліканти, що є ядрами виділені жирним шрифтом. В цьому прикладі, ядра не перекривають усі мінтерми, в такому випадку може бути виконана додаткова процедура спрощення таблиці (див. Метод Петрика). Маємо два варіанти:

${\displaystyle f_{A,B,C,D}=BC'D'+AB'+AC\ }$

${\displaystyle f_{A,B,C,D}=BC'D'+AD'+AC.\ }$

Обидві ці функції функціонально еквівалентні до:

${\displaystyle f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'C'D+AB'CD'+AB'CD+ABC'D'+ABCD'+ABCD.\ }$

Примітки

1. V.P. Nelson e.a., Digital Circuit Analysis and Design, Prentice Hall, 1995, pag. 234

Див. також

• Метод Куайна
• Карта Карно
• евристичний алгоритм мінімізації

Посилання

• Мінімізація ДНФ, Інтернет-ресурс для мінімізації ДНФ методом Куайна - Мак-Класкі.
• , стаття Джека Кренча з порівняння методів Куайна - Мак-Класкі та К-карт. (англ.)
• Kmap minimizer Флеш програма базована методі Куайна - Мак-Класкі. (англ.)
• Аплет, що мінімізує булеві функції методом Куайна - Мак-Класкі. (нім.)
• Karma (Karnaugh Map Viewer) – A CAD tool for Karnaugh map manipulation with didactic features in logic circuit synthesis. Uses Quine–McCluskey algorithm to generate a minimal sum of products.
• A. Costa BFunc, QMC based boolean logic simplifiers supporting up to 64 inputs / 64 outputs (independently) or 32 outputs (simultaneously)
• to display all the generated primes.
• Python Implementation by Robert Dick.
• Quinessence, an open source implementation written in Free Pascal by Marco Caminati.
• A literate program written in Java implementing the Quine-McCluskey algorithm.
• a MATLAB implementation by Andrey Popov.
• an open source, R based implementation used in the social sciences, by Adrian Duşa
• A series of two articles describing the algorithm(s) implemented in R: and . The R implementation is exhaustive and it offers complete and exact solutions. It processes up to 20 input variables.
• [1], an applet for a step by step analyze of the QMC- algorithm by Christian Roth
• [2] SourceForge.net C++ program implementing the algorithm.
• Perl Module by Darren M. Kulp.