Метод Куайна — Мак-Класкі (метод простих імплікант) - табличний метод мінімізації булевих функцій розроблений Уілардом Куайном і Едвардом Мак-Класкі. Функціонально ідентичний карті Карно, але таблична форма робить його ефективнішим для використання в комп'ютерних алгоритмах.
Складність
Незважаючи на більшу можливість практичного застосування ніж у карт Карно, коли мова йде про більше ніж чотири змінних, метод Куайна — Мак-Класкі теж має обмеження області застосування через експоненціальне зростання часу зі збільшенням кількості змінних. Можна показати, що для функції від n змінних верхня границя кількості основних імплікант 3n/n. Якщо n = 32 їх може бути більше ніж 6.5 * 1015. Функції з великою кількістю змінних мають бути мінімізовані з допомогою потенційно не оптимального евристичного алгоритму, на сьогодні евристичний алгоритм мінімізації Еспресо є фактичним світовим стандартомV.P. Nelson e.a., Digital Circuit Analysis and Design, Prentice Hall, 1995, pag. 234.
Приклад
Крок 1: знаходимо основні імпліканти
Нехай функція задана за допомогою наступної таблиці істинності: # 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 # 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.
Для оптимізації запишемо мінтрерми, включно із тими, що відповідають байдужим станам, в наступну таблицю: Кількість 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-
Принцип вибору імплікант такий самий як і в методі Куайна. Прості імпліканти, що є ядрами виділені жирним шрифтом. В цьому прикладі, ядра не перекривають усі мінтерми, в такому випадку може бути виконана додаткова процедура спрощення таблиці (див. Метод Петрика). Маємо два варіанти:
Обидві ці функції функціонально еквівалентні до:
Примітки
Див. також
Метод Куайна Карта Карно Еспресо евристичний алгоритм мінімізації
Посилання
Мінімізація ДНФ, Інтернет-ресурс для мінімізації ДНФ методом Куайна - Мак-Класкі. All about Quine-McClusky, стаття Джека Кренча з порівняння методів Куайна - Мак-Класкі та К-карт. Kmap minimizer Флеш програма базована методі Куайна - Мак-Класкі. Java-Applet Аплет, що мінімізує булеві функції методом Куайна - Мак-Класкі. 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. , an applet for a step by step analyze of the QMC- algorithm by Christian Roth SourceForge.net C++ program implementing the algorithm. Perl Module by Darren M. Kulp.