Алгоритм Куайна – Маккласки - Quine–McCluskey algorithm

Диаграмма Хассе графа поиска алгоритма по 3 переменным. Учитывая, например, подмножество ${\displaystyle S=\{abc,a{\overline {b}}c,{\overline {a}}bc,{\overline {a}}b{\overline {c}},{\overline {a}}{\overline {b}}c\}}$ узлов нижнего уровня (светло-зеленый) алгоритм вычисляет минимальный набор узлов (здесь: ${\displaystyle \{{\overline {a}}b,c\}}$, темно-зеленый), который точно покрывает ${\displaystyle S}$.

В Алгоритм Куайна – Маккласки (QMC), также известный как метод простых импликантов, это метод, используемый для минимизация из Логические функции это было разработано Уиллард В. Куайн в 1952 г.^[1][2] и продлен Эдвард Дж. Маккласки в 1956 г.^[3] В качестве общего принципа этот подход уже был продемонстрирован логиком. Хью МакКолл в 1878 г.,^[4][5][6] было доказано Арчи Блейком в 1937 году,^[7][8][9][6] и был заново открыт Эдвардом В. Самсоном и Бертоном Э. Миллсом в 1954 году.^[10][6] и Раймондом Дж. Нельсоном в 1955 году.^[11][6] Также в 1955 году Пол В. Абрахамс и Джон Г. Нордал^[12] а также Альберт А. Муллин и Уэйн Г. Келлнер^{[13][14][15][16]} предложен десятичный вариант метода.^{[17][14][15][16][18][19][20][21]}

Алгоритм Куайна – Маккласки функционально идентичен алгоритму Карно отображение, но табличная форма делает ее более эффективной для использования в компьютерных алгоритмах, а также дает детерминированный способ проверки достижения минимальной формы булевой функции. Иногда его называют методом табуляции.

Метод состоит из двух этапов:

1. Найти все основные импликанты функции.
2. Используйте эти основные импликанты в простая импликантная диаграмма чтобы найти основные простые импликанты функции, а также другие простые импликанты, необходимые для покрытия функции.

Сложность

Хотя более практично, чем Карно отображение при работе с более чем четырьмя переменными алгоритм Куайна – Маккласки также имеет ограниченный диапазон использования, поскольку проблема это решает НП-полный.^[22][23][24] В Продолжительность алгоритма Куайна – Маккласки растет экспоненциально с количеством переменных. Для функции п переменных число простых импликант может достигать 3^пln (п), например для 32 переменных может быть более 534 × 10¹² главные импликанты. Функции с большим количеством переменных должны быть минимизированы с потенциально неоптимальными эвристический методы, из которых Минимизатор эвристической логики эспрессо был стандартом де-факто в 1995 году.^{[нуждается в обновлении ][25]}

Второй шаг алгоритма сводится к решению установить проблему прикрытия;^[26] NP-жесткий на этом шаге алгоритма могут возникать экземпляры этой проблемы.^[27][28]

Пример

Вход

В этом примере входом является логическая функция с четырьмя переменными, ${\displaystyle f:\{0,1\}^{4}\to \{0,1\}}$ что оценивается как ${\displaystyle 1}$ о ценностях ${\displaystyle 4,8,10,11,12}$ и ${\displaystyle 15}$, принимает неизвестное значение на ${\displaystyle 9}$ и ${\displaystyle 14}$, и чтобы ${\displaystyle 0}$ везде (где эти целые числа интерпретируются в их двоичной форме для ввода в ${\displaystyle f}$ для краткости обозначений). Входы, которые оцениваются как ${\displaystyle 1}$ называются «минтермами». Мы кодируем всю эту информацию, записывая

${\displaystyle f(A,B,C,D)=\sum m(4,8,10,11,12,15)+d(9,14).\,}$

Это выражение говорит, что функция вывода f будет равна 1 для minterms ${\displaystyle 4,8,10,11,12}$ и ${\displaystyle 15}$ (обозначается термином 'm') и что нам не важен вывод для ${\displaystyle 9}$ и ${\displaystyle 14}$ комбинации (обозначаемые термином "d").

Шаг 1: поиск основных импликантов

Сначала мы записываем функцию в виде таблицы (где x означает безразлично):

	А	B	C	D	ж
m0	0	0	0	0	0
m1	0	0	0	1	0
m2	0	0	1	0	0
м3	0	0	1	1	0
м4	0	1	0	0	1
m5	0	1	0	1	0
m6	0	1	1	0	0
m7	0	1	1	1	0
m8	1	0	0	0	1
m9	1	0	0	1	Икс
m10	1	0	1	0	1
m11	1	0	1	1	1
m12	1	1	0	0	1
m13	1	1	0	1	0
m14	1	1	1	0	Икс
m15	1	1	1	1	1

Можно легко сформировать канонический сумма продуктов выражение из этой таблицы, просто суммируя минтермы (Покидать условия безразличия ), где функция равна единице:

ж_{А, Б, В, D} = A'BC'D '+ AB'C'D' + AB'CD '+ AB'CD + ABC'D' + ABCD.

что не минимально. Таким образом, для оптимизации все minterms, оценивающие один, сначала помещаются в таблицу minterm. В эту таблицу также добавляются безразличные термины (имена в скобках), поэтому их можно комбинировать с minterms:

Число из 1 с	Минтерм	Двоичный Представление
1	м4	0100
	m8	1000
2	(m9)	1001
	m10	1010
	m12	1100
3	m11	1011
	(m14)	1110
4	m15	1111

На этом этапе можно начинать комбинировать минтермы с другими минтермами. Если два термина отличаются только одной цифрой, эту цифру можно заменить дефисом, указывающим, что цифра не имеет значения. Термины, которые больше не могут быть объединены, отмечены звездочкой (*). Например 1000 и 1001 можно объединить, чтобы дать 100-, что указывает на то, что оба термина подразумевают, что первая цифра 1 и следующие два 0.

Число из 1 с	Минтерм	0-куб	Импликант размера 2
1	м4	0100	м (4,12)	-100*
	m8	1000	м (8,9)	100-
	—	—	м (8,10)	10-0
	—	—	м (8,12)	1-00
2	m9	1001	м (9,11)	10-1
	m10	1010	м (10,11)	101-
	—	—	м (10,14)	1-10
	m12	1100	м (12,14)	11-0
3	m11	1011	м (11,15)	1-11
	m14	1110	м (14,15)	111-
4	m15	1111	—

При переходе от размера 2 к размеру 4 угощайте - как третье битовое значение. Например, -110 и -100 можно объединить, чтобы дать -1-0, сканирование -110 и -11- давать -11-, но -110 и 011- не может, потому что -110 подразумевается 1110 пока 011- не является. (Уловка: сопоставьте - первый.)

Число из 1 с	Минтерм	0-куб	Импликант размера 2		Импликант размера 4
1	м4	0100	м (4,12)	-100*	м (8,9,10,11)	10--*
	m8	1000	м (8,9)	100-	м (8,10,12,14)	1--0*
	—	—	м (8,10)	10-0	—
	—	—	м (8,12)	1-00	—
2	m9	1001	м (9,11)	10-1	м (10,11,14,15)	1-1-*
	m10	1010	м (10,11)	101-	—
	—	—	м (10,14)	1-10	—
	m12	1100	м (12,14)	11-0	—
3	m11	1011	м (11,15)	1-11	—
	m14	1110	м (14,15)	111-	—
4	m15	1111		—	—

Примечание. В этом примере ни один из терминов в таблице импликантов размера 4 нельзя комбинировать дальше. Как правило, этот процесс следует продолжать (размеры 8, 16 и т. Д.) До тех пор, пока не перестанут быть объединены термины.

Шаг 2: диаграмма простых импликантов

Ни один из терминов не может быть скомбинирован дальше этого, поэтому на этом этапе мы строим существенную таблицу импликантов простых чисел. По бокам идут первичные импликанты, которые только что были сгенерированы, а сверху идут минтермы, указанные ранее. Термины безразличия не помещаются сверху - они опускаются в этом разделе, потому что они не являются необходимыми входными данными.

	4	8	10	11	12	15	⇒	А	B	C	D
м (4,12) *							⇒	—	1	0	0
м (8,9,10,11)							⇒	1	0	—	—
м (8,10,12,14)							⇒	1	—	—	0
м (10,11,14,15) *							⇒	1	—	1	—

Чтобы найти основные простые импликанты, мы пробегаемся по верхнему ряду. Мы должны искать столбцы только с одним «✓». Если в столбце есть только один «✓», это означает, что минтерм может быть покрыт только одним простым импликантом. Этот главный импликант существенный.

Например: в первом столбце с minterm 4 только одно «✓». Это означает, что m (4,12) существенно. Так что ставим рядом звезду. Minterm 15 также имеет только одно «✓», поэтому m (10,11,14,15) также имеет важное значение. Теперь все столбцы с одним «✓» закрыты.

Импликанты второго простого числа могут быть «покрыты» третьим и четвертым импликантами, а импликанты третьего простого числа могут быть «покрыты» вторыми и первыми, и поэтому ни один из них не является существенным. Если простая импликанта важна, то, как и следовало ожидать, необходимо включить ее в минимизированное булево уравнение. В некоторых случаях существенные простые импликанты не охватывают все минтермы, и в этом случае можно использовать дополнительные процедуры для сокращения диаграммы. Самая простая «дополнительная процедура» - метод проб и ошибок, но более систематический способ - Метод Петрика. В текущем примере существенные простые импликанты не обрабатывают все минтермы, поэтому в этом случае существенные импликанты могут быть объединены с одной из двух несущественных импликант, чтобы получить одно уравнение:

ж_{А, Б, В, D} = BC'D '+ AB' + AC^[29]

или же

ж_{А, Б, В, D} = BC'D '+ AD' + AC

Оба этих окончательных уравнения функционально эквивалентны исходному подробному уравнению:

ж_{А, Б, В, D} = A'BC'D '+ AB'C'D' + AB'C'D + AB'CD '+ AB'CD + ABC'D' + ABCD '+ ABCD.

Смотрите также

• Каноническая форма Блейка^[7][6]
• Алгоритм Бухбергера - аналогичный алгоритм для алгебраической геометрии
• Метод Петрика
• Качественный сравнительный анализ (QCA)

Рекомендации

1. Куайн, Уиллард Ван Орман (Октябрь 1952 г.). «Проблема упрощения функций истины». Американский математический ежемесячник. 59 (8): 521–531. Дои:10.2307/2308219. JSTOR  2308219.
2. Куайн, Уиллард Ван Орман (Ноябрь 1955 г.). «Способ упростить функции истины». Американский математический ежемесячник. 62 (9): 627–631. Дои:10.2307/2307285. HDL:10338.dmlcz / 142789. JSTOR  2307285.
3. Маккласки младший, Эдвард Джозеф (Ноябрь 1956 г.). «Минимизация булевых функций». Технический журнал Bell System. 35 (6): 1417–1444. Дои:10.1002 / j.1538-7305.1956.tb03835.x. HDL:10338.dmlcz / 102933. Получено 2014-08-24.
4. Макколл, Хью (1878-11-14). «Исчисление эквивалентных утверждений (третья статья)». Труды Лондонского математического общества. s1-10 (1): 16–28. Дои:10.1112 / плмс / с1-10.1.16.
5. Лэдд, Кристина (1883). «Об алгебре логики». В Пирс, Чарльз Сандерс (ред.). Исследования по логике. Бостон, США: Little, Brown & Company. С. 17–71, 23. […] Если приведение [выражения к простейшей форме] не очевидно, это можно облегчить, взяв отрицательное значение выражения, уменьшив его, а затем вернув его в положительную форму. […]
6. Браун, Фрэнк Маркхэм (ноябрь 2010 г.) [2010-10-27]. «Макколл и минимизация». История и философия логики. Тейлор и Фрэнсис. 31 (4): 337–348. Дои:10.1080/01445340.2010.517387. ISSN  1464-5149. В архиве из оригинала на 2020-04-15. Получено 2020-04-15.
7. Блейк, Арчи (1938) [1937]. Канонические выражения в булевой алгебре (Диссертация) (Lithographed ed.). Чикаго, Иллинойс, США: Библиотеки Чикагского университета. п. 36. […] Этот метод был известен Пирс и его учениками […] Он упоминается в нескольких местах в «Исследованиях по логике» членами Университет Джона Хопкинса, 1883 […] (ii + 60 страниц)
8. Блейк, Арчи (ноябрь 1932 г.). «Канонические выражения в булевой алгебре». Бюллетень Американского математического общества. Тезисов докладов: 805.
9. Блейк, Арчи (июнь 1938). "Исправления к Канонические выражения в булевой алгебре". Журнал символической логики. Ассоциация символической логики. 3 (2): 112–113. Дои:10.2307/2267595. ISSN  0022-4812. JSTOR  2267595.
10. Самсон, Эдвард Уолтер; Миллс, Бертон Э. (апрель 1954 г.). Минимизация схем: алгебра и алгоритмы для новых булевых канонических выражений. Бедфорд, Массачусетс, США: Кембриджский исследовательский центр ВВС США. Технический отчет AFCRC TR 54-21.
11. Нельсон, Раймонд Дж. (Июнь 1955 г.). «Простейшие функции нормальной истины». Журнал символической логики. Ассоциация символической логики. 20 (2): 105–108. Дои:10.2307/2266893. JSTOR  2266893. (4 страницы)
12. «Добро пожаловать на страницу памяти Джона« Джека »Дж. Нордала, 14 июня 1933 г. ~ 20 ноября 2017 г. (84 года)». Похоронное бюро Джеллисон и услуги кремации. В архиве из оригинала 2020-05-05. Получено 2020-05-05.
13. Маллин, Альберт Алкинс; Келлнер, Уэйн Г. (1958). Написано в Университете Иллинойса, Урбана, США, и на факультете электротехники, Массачусетский Институт Технологий, Массачусетс, США. «Проверка остатка для булевых функций» (PDF). Труды Академии наук штата Иллинойс (Учебный меморандум). Спрингфилд, Иллинойс, США. 51 (3–4): 14–19. S2CID  125171479. В архиве (PDF) из оригинала 2020-05-05. Получено 2020-05-05. [1] (6 страниц) (Примечание. В его книга Колдуэлл датирует это ноябрем 1955 года как учебный меморандум. Поскольку Маллин датирует их работу 1958 г. другая работа и Abrahams / Nordahl's меморандум класса также датируется ноябрем 1955 года, возможно, это ошибка копирования.)
14. Колдуэлл, Сэмюэл Хоукс (1958-12-01) [февраль 1958]. «5.8. Операции с использованием десятичных символов». Написано в Уотертауне, Массачусетс, США. Коммутационные схемы и логическая конструкция. 5 сентября 1963 г. (1-е изд.). Нью-Йорк, США: John Wiley & Sons Inc. С. 162–169 [166]. ISBN  0-47112969-0. LCCN  58-7896. […] Приятно отметить, что этот метод лечения основан на работе двух студентов, которые изучали схемы переключения в Массачусетском технологическом институте. Они обсудили метод самостоятельно, а затем вместе подготовили памятную записку: П. В. Абрахам и Дж. Г. Нордаль […] (xviii + 686 страниц) (NB. Что касается первого основного трактата о десятичном методе в этой книге, его иногда ошибочно называют «десятичной таблицей Колдуэлла».)
15. Маллин, Альберт Алкинс (1960-03-15) [1959-09-19]. Написано в Университете Иллинойса, Урбана, США. Фишер, Харви I .; Экбло, Джордж Э .; Green, F. O .; Джонс, Рис; Круиденье, Фрэнсис; МакГрегор, Джон; Сильва, Пол; Томпсон, Милтон (ред.). «Два приложения элементарной теории чисел» (PDF). Труды Академии наук штата Иллинойс. Спрингфилд, Иллинойс, США. 52 (3–4): 102–103. В архиве (PDF) из оригинала 2020-05-05. Получено 2020-05-05. [2][3][4] (2 страницы)
16. Маккласки младший, Эдвард Джозеф (Июнь 1960 г.). «Альберт А. Муллин и Уэйн Г. Келлнер. Проверка вычетов для булевых функций. Труды Академии наук штата Иллинойс, том 51, номера 3 и 4, (1958), стр. 14–19». Журнал символической логики (Рассмотрение). 25 (2): 185. Дои:10.2307/2964263. JSTOR  2964263. […] Результаты этой статьи представлены в более доступном книга С. Х. Колдуэлла […]. В этой книге автор отмечает Маллин и Келлнер для отработки манипуляций с десятичными числами. (1 стр.)
17. Абрахамс, Пол Уильям; Нордаль, Джон «Джек» Г. (ноябрь 1955 г.). Модифицированная процедура восстановления Куайна – Маккласки (Классный меморандум). Электротехнический отдел, Массачусетский Институт Технологий, Массачусетс, США. (4 страницы) (NB. В некоторых источниках авторов указаны как "П. В. Абрахам " и "И. Г. Нордаль ", название также цитируется как"Модифицированная процедура восстановления Маккласки – Куайна ".)
18. Филдер, Дэниел К. (декабрь 1966 г.). "Классная редукция булевых функций". IEEE Transactions по образованию. IEEE. 9 (4): 202–205. Bibcode:1966ITEdu ... 9..202F. Дои:10.1109 / TE.1966.4321989. eISSN  1557-9638. ISSN  0018-9359.
19. Каммерер, Вильгельм (Май 1969 г.). "I.12. Minimierung Boolescher Funktionen". Написано в Йене, Германия. В Фрюхауф, Ганс; Каммерер, Вильгельм; Шредер, Курц; Винклер, Гельмут (ред.). Digitale Automaten - Theorie, Struktur, Technik, Programmieren. Elektronisches Rechnen und Regeln (на немецком языке). 5 (1-е изд.). Берлин, Германия: Akademie-Verlag GmbH. С. 98, 103–104. Лицензия №. 202-100 / 416/69. № заказа. 4666 ES 20 K 3. с. 98: […] 1955 г. wurde das Verfahren auf die bequemere dezimale Schreibweise umgestellt (П. В. Абрахам и И. Г. Нордаль в [Колдуэлл ]). […] (NB. Существует также второе издание 1973 г.)
20. Холдсворт, Брайан; Вудс, Клайв (2002). «3.17. Десятичный подход к упрощению Куайна – Маккласки булевой алгебры». Цифровой логический дизайн (4-е изд.). Newnes Книги / Elsevier Science. С. 65–67. ISBN  0-7506-4588-2. Получено 2020-04-19. (519 страниц) [5]
21. Маджумдер, Алак; Чоудхури, Барнали; Mondal, Abir J .; Джайн, Кундж (30.01.2015) [09.01.2015]. Исследование метода Куайна МакКласки: новый подход к минимизации булевой функции, основанный на десятичной манипуляции. Международная конференция по электронному проектированию, компьютерным сетям и автоматизированной проверке (EDCAV), 2015 г., Шиллонг, Индия (доклад конференции). Департамент электроники и связи, Технический национальный технологический институт, Аруначал-Прадеш, Юпия, Индия. С. 18–22. Дои:10.1109 / EDCAV.2015.7060531. В архиве из оригинала на 2020-05-08. Получено 2020-05-08. [6] (NB. Эта работа не цитирует предшествующий уровень техники по десятичным методам.) (5 страниц)
22. Масек, Уильям Дж. (1979). Некоторая NP-комплектация, покрывающая проблемы. не опубликовано.
23. Чорт, Себастьян Лукас Арне (1999). Сложность минимизации формул дизъюнктивных нормальных формул (Дипломная работа). Орхусский университет.
24. Уманс, Кристофер; Вилла, Тициано; Санжиованни-Винчентелли, Альберто Луиджи (2006-06-05). «Сложность минимизации двухуровневой логики». IEEE Transactions по автоматизированному проектированию интегральных схем и систем. 25 (7): 1230–1246. Дои:10.1109 / TCAD.2005.855944. S2CID  10187481.
25. Нельсон, Виктор П .; Нэгл, Х. Трой; Кэрролл, Билл Д .; Ирвин, Дж. Дэвид (1995). Анализ и проектирование цифровых логических схем (2-е изд.). Prentice Hall. п. 234. ISBN  978-0-13463894-2. Получено 2014-08-26.
26. Фельдман, Виталий (2009). «Трудность приближенной двухуровневой минимизации логики и обучения PAC с запросами членства». Журнал компьютерных и системных наук. 75: 13–25 (13–14). Дои:10.1016 / j.jcss.2008.07.007.
27. Гимпель, Джеймс Ф. (1965). «Метод создания булевой функции, имеющей произвольно заданную простую импликантную таблицу». Транзакции IEEE на компьютерах. 14: 485–488. Дои:10.1109 / PGEC.1965.264175.
28. Пол, Вольфганг Якоб (1974). "Boolesche Minimalpolynome und Überdeckungsprobleme". Acta Informatica (на немецком). 4 (4): 321–336. Дои:10.1007 / BF00289615. S2CID  35973949.
29. Логическая пятница программа

дальнейшее чтение

• Кертис, Х. Аллен (1962). «Глава 2.3. Метод Маккласки». Новый подход к проектированию схем переключения. Серия Bell Laboratories. Принстон, Нью-Джерси, США: D. van Nostrand Company, Inc. С. 90–160.
• Кудерт, Оливье (октябрь 1994). «Минимизация двухуровневой логики: обзор» (PDF). Интеграция, Журнал СБИС. 17–2 (2): 97–140. Дои:10.1016/0167-9260(94)00007-7. ISSN  0167-9260. В архиве (PDF) из оригинала 2020-05-10. Получено 2020-05-10. (47 страниц)
• Джадхав, Виттал; Бухад, Амар (2012-03-08). «Модифицированный метод Куайна-Маккласки». arXiv:1203.2289 [cs.OH ]. (4 страницы)
• Креншоу, Джек (2004-08-19). "Все о Куайне-МакКласки". embedded.com. В архиве из оригинала 2020-05-10. Получено 2020-05-10.
• Томашевский, Себастьян П .; Челик, Ильгаз У .; Антониу, Джордж Э. (декабрь 2003 г.) [2003-03-05, 2002-04-09]. ""Минимизация булевой функции на основе WWW " (PDF). Международный журнал прикладной математики и информатики. 13 (4): 577–584. В архиве (PDF) из оригинала 2020-05-10. Получено 2020-05-10. [7][8] (7 страниц)
• Душа, Адриан (2008-10-01) [сентябрь 2007]. «Математический подход к задаче булевой минимизации». Качество и количество. 44: 99–113. Дои:10.1007 / s11135-008-9183-х. S2CID  123042755. Номер статьи: 99 (2010). [9] (22 страницы)
• Душа, Адриан (2007). "Улучшение Куайна-МакКласки" (PDF). Бухарестский университет. В архиве (PDF) из оригинала 12.05.2020. Получено 2020-05-12. (16 страниц) (NB. QCA, реализация на основе R с открытым исходным кодом, используемая в социальных науках.)

внешняя ссылка

• Реализация алгоритма Куайна-Маккласки с поиском всех решений, автор: Фредерик Карпон.
• Karċma 3, Набор инструментов логического синтеза, включая карты Карно, минимизацию Куайна-Маккласки, BDD, вероятности, обучающий модуль и многое другое. Лаборатория синтеза логических схем (LogiCS) - UFRGS, Бразилия.
• BFunc, Упростители логической логики на основе QMC, поддерживающие до 64 входов / 64 выходов (независимо) или 32 выхода (одновременно), Антонио Коста
• Python Выполнение Роберта Дика, с оптимизированная версия.
• Python Выполнение для символического сокращения логических выражений.
• Quinessence, реализация с открытым исходным кодом, написанная на Free Pascal Марко Каминати.
• minBool реализация Андрея Попова.
• Аплет QMC, апплет для пошагового анализа QMC-алгоритма Кристиана Рота
• Реализация на C ++ SourceForge.net C ++ программа, реализующая алгоритм.
• Модуль Perl Даррен М. Кулп.
• Руководство Учебное пособие по методу Куайна-Маккласки и Петрика.
• Петрик Реализация C ++ (включая Petrick) на основе приведенного выше руководства.
• Программа C Программа C на основе консоли Public Domain на SourceForge.net.
• Чтобы увидеть полностью проработанный пример, посетите: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm
• Логический бот: реализация JavaScript для Интернета: http://booleanbot.com/
• графический интерфейс с открытым исходным кодом QMC Minimizer
• Коды компьютерного моделирования для метода Куайна-МакКласки, пользователя Sourangsu Banerji.