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

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

Складність

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

Приклад

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

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

# $x$ $y$ $z$ $t$ $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

# $x$ $y$ $z$ $t$ $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.

$f=x^{\prime }y{z}^{\prime }{t}^{\prime }+x{y}^{\prime }{z}^{\prime }{t}^{\prime }+x{y}^{\prime }z{t}^{\prime }+x{y}^{\prime }zt+xy{z}^{\prime }{t}^{\prime }+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-

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

$f_{A,B,C,D}=B{C}^{\prime }{D}^{\prime }+A{B}^{\prime }+AC$

$f_{A,B,C,D}=B{C}^{\prime }{D}^{\prime }+A{D}^{\prime }+AC.$

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

$f_{A,B,C,D}=A^{\prime }B{C}^{\prime }{D}^{\prime }+A{B}^{\prime }{C}^{\prime }{D}^{\prime }+A{B}^{\prime }{C}^{\prime }D+A{B}^{\prime }C{D}^{\prime }+A{B}^{\prime }CD+AB{C}^{\prime }{D}^{\prime }+ABC{D}^{\prime }+ABCD.$

Див. також

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

Посилання

• Мінімізація ДНФ, Інтернет-ресурс для мінімізації ДНФ методом Куайна - Мак-Класкі.
• All about Quine-McClusky, стаття Джека Кренча з порівняння методів Куайна - Мак-Класкі та К-карт. Шаблон:Ref-en
• Kmap minimizer Флеш програма базована методі Куайна - Мак-Класкі. Шаблон:Ref-en
• Java-Applet Аплет, що мінімізує булеві функції методом Куайна - Мак-Класкі. Шаблон:Ref-de
• 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.
• Lecture on the Quine–McCluskey algorithm
• A. Costa BFunc, QMC based boolean logic simplifiers supporting up to 64 inputs / 64 outputs (independently) or 32 outputs (simultaneously)
• Java applet 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.
• minBool a MATLAB implementation by Andrey Popov.
• QCA 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: first article and second article. 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.