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

Алгоритм минимизации булевых функций

Диаграмма Хассе поискового графа алгоритма для 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]}

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

Алгоритм Куайна-Маккласки работает следующим образом:

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

Сложность

Хотя алгоритм Куайна–Маккласки более практичен, чем отображение Карно , при работе с более чем четырьмя переменными, он также имеет ограниченный диапазон использования, поскольку решаемая им задача является NP-полной . ^{[22] [23] [24]} Время выполнения алгоритма Куайна–Маккласки растет экспоненциально с числом переменных. Для функции от n переменных число простых импликантов может быть таким большим, как , ^[25] например, для 32 переменных может быть более 534 × 10 ¹² простых импликантов. Функции с большим количеством переменных должны быть минимизированы с помощью потенциально неоптимальных эвристических методов, из которых эвристический логический минимизатор Espresso был фактическим стандартом в 1995 году. ^{[ требуется обновление ] [26]} Для одного естественного класса функций точная сложность нахождения всех простых импликант понятна лучше: Милан Моссе, Гарри Ша и Ли-Ян Тан открыли близкий к оптимальному алгоритм для нахождения всех простых импликант формулы в конъюнктивной нормальной форме . ^[27] ${\displaystyle 3^{n}/{\sqrt {n}}}$ ${\displaystyle f}$

Второй шаг алгоритма заключается в решении задачи покрытия множества ; ^{[28] На этом шаге алгоритма могут возникнуть} NP-трудные случаи этой задачи. ^{[29] [30]}

Пример

Вход

В этом примере входные данные — это булева функция с четырьмя переменными, которая вычисляется как для значений и , вычисляется как неизвестное значение для и , и как везде в остальном (где эти целые числа интерпретируются в их двоичной форме для входных данных для краткости записи). Входные данные, вычисляемые как , называются «минтермами». Мы кодируем всю эту информацию, записывая ${\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 для минтермов и (обозначенных термином «m») и что нас не волнует выход для комбинаций и (обозначенных термином «d»). Символ суммирования обозначает логическую сумму (логическое ИЛИ или дизъюнкция) всех суммируемых терминов. ${\displaystyle 4,8,10,11,12}$ ${\displaystyle 15}$ ${\displaystyle 9}$ ${\displaystyle 14}$ ${\displaystyle \sum }$

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

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

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

f _A,B,C,D = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD.

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

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

При переходе от размера 2 к размеру 4 рассматривать -как третье битовое значение. Сначала сопоставьте -' s. Термины представляют продукты, и для объединения двух терминов продуктов они должны иметь одинаковые переменные. Одна из переменных должна быть дополнена в одном термине и не дополнена в другом. Остальные присутствующие переменные должны согласовываться. Таким образом, для сопоставления двух терминов -' s должны быть выровнены, и все, кроме одной, цифры должны быть одинаковыми. Например, -110и -100можно объединить, чтобы получить -1-0, как можно -110и , -010чтобы получить --10, но -110и 011-нельзя, так как -' s не выровнены. -110соответствует BCD', в то время как 011-соответствует A'BC, а BCD' + A'BC не эквивалентно термину продукта.

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

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

Ни один из терминов не может быть объединен дальше этого, поэтому на этом этапе мы строим таблицу основных первичных импликантов. Вдоль стороны идут первичные импликанты, которые только что были сгенерированы (это те, которые были отмечены знаком " * " на предыдущем шаге), а вдоль верха идут минтермы, указанные ранее. Неважные термины не помещаются сверху — они опущены в этом разделе, поскольку они не являются необходимыми входными данными.

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

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

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

f _A,B,C,D = BC'D' + AB' + AC ^[31]

или

f _A,B,C,D = BC'D' + AD' + AC

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

f _A,B,C,D = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.

Алгоритм

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

Псевдокод ниже рекурсивно вычисляет основные импликанты, учитывая список минтермов булевой функции. Он делает это, пытаясь объединить все возможные минтермы и отфильтровывая минтермы, которые были объединены, пока больше не будет возможности выполнить слияния минтермов и, следовательно, основные импликанты функции не будут найдены.

// Вычисляет основные импликанты из списка минтермов.// каждый минтерм имеет форму «1001», «1010» и т. д. и может быть представлен строкой.Функция getPrimeImplicants(список minterms) — это  primeImplicants ← пустой список merges ← новый логический массив длины, равной количеству минтермов, каждый из которых установлен в false числоОбъединений ← 0 mergedMinterm, minterm1, minterm2 ← пустые строки для i = 0 до длины (minterms) сделать  для c = i + 1 до длины (minterms) сделать minterm1 ← minterms[i] minterm2 ← minterms[c] // Проверка возможности объединения двух минтермов если CheckDashesAlign(minterm1, minterm2) && CheckMintermDifference(minterm1, minterm2) тогда mergedMinterm ← MergeMinterms(minterm1, minterm2) если primeImplicants не содержит mergedMinterm, то primeImplicants.Add(mergedMinterm) числоСлияний ← числоСлияний + 1 объединяет[i] ← верно объединяет[c] ← верно // Фильтрация всех минтермов, которые не были объединены, поскольку они являются первичными импликантами. Также удаляются дубликаты для j = 0 до length(minterms) сделать  если merges[j] == false && primeImplicants не содержит minterms[j] тогда primeImplicants.Добавить(minterms[j]) // если слияний не произошло, то все основные импликанты найдены, поэтому возвращаем, в противном случае // продолжаем объединять минтермы. если numberOfmerges == 0, то  вернуть primeImplicants , иначе  вернуть getPrimeImplicants(primeImplicants)

В этом примере функции CheckDashesAlignи CheckMintermDifferenceвыполняют необходимые проверки для определения возможности объединения двух минтермов. Функция MergeMintermsобъединяет минтермы и добавляет тире, где это необходимо. Вспомогательные функции ниже предполагают, что каждый минтерм будет представлен с использованием строк.

Функция MergeMinterms(minterm1, minterm2) — это mergedMinterm ← пустая строка для i = 0 до длины (minterm1) сделать  //Если биты различаются, то замените их на тире, в противном случае бит останется в объединенном минтерме. если минтерм[i] != минтерм2[i] тогда объединенныйMinterm ← объединенныйMinterm + '-' еще объединенныйMinterm ← объединенныйMinterm + minterm1[i] вернуться объединенныйMintermФункция CheckDashesAlign(minterm1, minterm2) для  i = 0 до length(minterm1) делает  // Если в одном минтерме есть дефисы, а в другом — нет, то минтермы не могут быть объединены. если minterm1[i] != '-' && minterm2[i] == '-' тогда  вернуть false вернуть trueФункция CheckMintermDifference(minterm1, minterm2) — это  // minterm1 и minterm2 — это строки, представляющие все найденные в данный момент простые импликанты и объединенные // minterms. Примеры включают '01--' и '10-0' m1, m2 ← целочисленное представление minterm1 и minterm2 с удаленными дефисами, они заменены на 0 // ^ здесь побитовое XOR рез ← m1 ^ m2 вернуть рез != 0 && (рез & рез - 1) == 0

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

Приведенный ниже псевдокод можно разделить на две части:

1. Создание первичной импликантной диаграммы с использованием первичных импликант
2. Чтение таблицы первичных импликантов для нахождения основных первичных импликантов.

Создание первичной импликантной диаграммы

Диаграмма первичной импликации может быть представлена ​​словарем, где каждый ключ является первичной импликацией, а соответствующее значение является пустой строкой, которая будет хранить двоичную строку после завершения этого шага. Каждый бит в двоичной строке используется для представления отметок в диаграмме первичной импликации. Диаграмма первичной импликации может быть создана с помощью следующих шагов:

1. Пройдитесь по каждому ключу (первичный импликант словаря).
2. Замените каждое тире в первичном импликанте кодом \dсимвола. Это создает регулярное выражение, которое можно проверить по каждому из минтермов, ища совпадения.
3. Пройтись по каждому минтерму, сравнивая регулярное выражение с двоичным представлением минтерма, если есть совпадение, добавить "1"к соответствующей строке в словаре. В противном случае добавить "0".
4. Повторите эти действия для всех основных импликантов, чтобы создать полную таблицу основных импликантов.

Описанный выше алгоритм, записанный в псевдокоде, выглядит следующим образом:

функция CreatePrimeImplicantChart(список основных импликантов, список основных импликантов) primeImplicantChart ← новый словарь с ключом типа string и значением типа string // Создание пустой диаграммы с основными импликантами в качестве ключа и пустыми строками в качестве значения. для i = 0 до длины (primeImplicants) сделать // Добавляем новый первичный импликант в диаграмму. primeImplicantChart.Add(primeImplicants[i], "")  для i = 0 до length(primeImplicantChart.Keys) сделать primeImplicant ← primeImplicantChart.Keys[i] // Преобразуем «-» в «\d», который можно использовать для поиска строки отметок выше. regularExpression ← Преобразовать в регулярное выражение (primeImplicant) для j = 0 до длины (минтермс) сделать // Если есть совпадение между регулярным выражением и минтермом, то добавляем 1, в противном случае 0. если regularExpression.соответствует(primeImplicant), то primeImplicantChart[primeImplicant] += "1" еще  primeImplicantChart[primeImplicant] += "0" // Основная импликантная диаграмма завершена, поэтому возвращаем завершенную диаграмму. вернуть primeImplicantChart

Функция полезности, ConvertToRegularExpression, используется для преобразования первичной импликанты в регулярное выражение для проверки совпадений между импликантой и минтермами.

функция ConvertToRegularExpression(строка primeImplicant) regularExpression ← новая строка для i = 0 до length(primeImplicant) сделать  если primeImplicant[i] == "-" тогда // Добавьте буквенный символ "\d". регулярноеВыражение += @"\d"; вернуть регулярное выражение

Нахождение основных первичных импликантов

Используя функцию, CreatePrimeImplicantChartопределенную выше, мы можем найти существенные простые импликанты, просто перебирая столбец за столбцом значения в словаре, и если "1"найдено одно число, то найден существенный простой импликант.

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

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

Ссылки

1. Куайн, Уиллард Ван Орман (октябрь 1952 г.). «Проблема упрощения функций истинности». The American Mathematical Monthly . 59 (8): 521–531. doi :10.2307/2308219. JSTOR  2308219.
2. Куайн, Уиллард Ван Орман (ноябрь 1955 г.). «Способ упрощения функций истинности». The American Mathematical Monthly . 62 (9): 627–631. doi :10.2307/2307285. hdl :10338.dmlcz/142789. JSTOR  2307285.
3. МакКласки, Эдвард Джозеф-младший (ноябрь 1956 г.). «Минимизация булевых функций». Bell System Technical Journal . 35 (6): 1417–1444. doi :10.1002/j.1538-7305.1956.tb03835.x. hdl :10338.dmlcz/102933 . Получено 24.08.2014 .
4. Макколл, Хью (1878-11-14). «Исчисление эквивалентных утверждений (третья статья)». Труды Лондонского математического общества . s1-10 (1): 16–28. doi :10.1112/plms/s1-10.1.16.
5. Лэдд, Кристин (1883). «Об алгебре логики». В Peirce, Charles Sanders (ред.). Studies in Logic . Бостон, США: Little, Brown & Company . стр. 17–71. стр. 23: [...] Если сведение [выражения к простейшей форме] не очевидно, его можно облегчить, взяв отрицательное выражение, сократив его, а затем восстановив его в положительной форме. [...]
6. Brown, Frank Markham (ноябрь 2010 г.) [2010-10-27]. "McColl and Minimization". History and Philosophy of Logic . 31 (4). Taylor & Francis : 337–348. doi :10.1080/01445340.2010.517387. ISSN  1464-5149. S2CID  216590641. Архивировано из оригинала 2020-04-15 . Получено 2020-04-15 .
7. Блейк, Арчи (1938) [1937]. Канонические выражения в булевой алгебре (диссертация) (литографированное издание). Чикаго, Иллинойс, США: Библиотеки Чикагского университета . стр. 36. стр. 36: [...] этот метод был известен Пирсу и его ученикам [...] Он упоминается в нескольких местах в «Исследованиях по логике» членов Университета Джонса Хопкинса , 1883 [...](ii+60 страниц)
8. Блейк, Арчи (ноябрь 1932 г.). «Канонические выражения в булевой алгебре». Бюллетень Американского математического общества . Рефераты статей: 805.
9. Блейк, Арчи (июнь 1938 г.). «Исправления канонических выражений в булевой алгебре». Журнал символической логики . 3 (2). Ассоциация символической логики : 112–113. doi : 10.2307/2267595. ISSN  0022-4812. JSTOR  2267595. S2CID  5810863.
10. Сэмсон, Эдвард Уолтер; Миллс, Бертон Э. (апрель 1954 г.). Минимизация цепей: алгебра и алгоритмы для новых канонических булевых выражений . Бедфорд, Массачусетс, США: Исследовательский центр ВВС в Кембридже . Технический отчет AFCRC TR 54-21.
11. Nelson, Raymond J. (июнь 1955 г.). «Простейшие нормальные функции истинности». Журнал символической логики . 20 (2). Ассоциация символической логики : 105–108. doi : 10.2307/2266893. JSTOR  2266893. S2CID  32920372.(4 страницы)
12. "Добро пожаловать на страницу памяти Джона "Джека" Г. Нордаля 14 июня 1933 г. ~ 20 ноября 2017 г. (84 года)". Jellison Funeral Home and Cremation Services. Архивировано из оригинала 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 годом, а учебный меморандум Абрахамса/Нордаля также датирован ноябрем 1955 года, это может быть ошибкой копирования.)
14. Caldwell, Samuel Hawks (1958-12-01) [февраль 1958]. "5.8. Операции с использованием десятичных символов". Написано в Уотертауне, Массачусетс, США. Switching Circuits and Logical Design . 5-е издание, сентябрь 1963 г. (1-е изд.). Нью-Йорк, США: John Wiley & Sons Inc., стр. 162–169. ISBN 0-47112969-0. LCCN  58-7896. стр. 166: [...] С удовольствием отмечаем, что эта обработка основана на работе двух студентов в период изучения коммутационных схем в Массачусетском технологическом институте. Они независимо друг от друга обсудили метод, а затем совместно подготовили классный меморандум: PW Abraham и JG Nordahl [...](xviii+686 страниц) (Примечание. Первый крупный трактат по десятичному методу в этой книге иногда ошибочно называют «десятичной табуляцией Колдуэлла».)
15. Mullin, Albert Alkins (1960-03-15) [1959-09-19]. Написано в Университете Иллинойса, Урбана, США. Fisher, Harvey I.; Ekblaw, George E.; Green, FO; Jones, Reece; Kruidenier, Francis; McGregor, John; Silva, Paul; Thompson, Milton (ред.). "Два приложения элементарной теории чисел" (PDF) . Transactions of the Illinois State Academy of Science . 52 (3–4). Springfield, Illinois, USA: 102–103. Архивировано (PDF) из оригинала 2020-05-05 . Получено 2020-05-05 .[2][3][4] (2 страницы)
16. McCluskey, Edward Joseph Jr. (июнь 1960 г.). "Albert A. Mullin and Wayne G. Kellner. A residual test for Boolean functions. Transactions of the Illinois State Academy of Science, vol. 51 nos. 3 and 4, (1958), pp. 14–19". The Journal of Symbolic Logic (Review). 25 (2): 185. doi :10.2307/2964263. JSTOR  2964263. S2CID  123530443. p. 185: [...] Результаты этой статьи представлены в более доступной книге SH Caldwell [...]. В этой книге автор отдает должное Маллину и Келлнеру за разработку манипуляций с десятичными числами.(1 страница)
17. Абрахамс, Пол Уильям; Нордаль, Джон «Джек» Г. (ноябрь 1955 г.). Модифицированная процедура редукции Куайна–Маккласки (Памятная записка класса). Кафедра электротехники, Массачусетский технологический институт , Массачусетс, США.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )(4 страницы) (Примечание. В некоторых источниках авторами указаны «П. У. Абрахам» и «И. Г. Нордаль», а название также упоминается как «Модифицированная процедура редукции Маккласки–Куайна».)
18. Филдер, Дэниел К. (декабрь 1966 г.). «Сокращение булевых функций в классе». Труды IEEE по образованию . 9 (4). IEEE : 202–205. Bibcode :1966ITEdu...9..202F. doi :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 К 3. с. 98: [...] 1955 wurde das Verfahren auf die bequemere dezimale Schreibweise umgestellt (PW Авраам и И. Г. Нордаль в [Колдуэлле]). [...](Примечание. Существует также второе издание 1973 года.)
20. Холдсворт, Брайан; Вудс, Клайв (2002). "3.17 Десятичный подход к упрощению булевой алгебры по Куайну–Маккласки". Digital Logic Design (4-е изд.). Newnes Books / Elsevier Science . стр. 65–67. ISBN 0-7506-4588-2. Получено 19.04.2020 .{{cite book}}: CS1 maint: проигнорированы ошибки ISBN ( ссылка )(519 страниц) [5]
21. Majumder, Alak; Chowdhury, Barnali; Mondal, Abir J.; Jain, Kunj (2015-01-30) [2015-01-09]. Исследование метода Куайна-МакКласки: новый подход на основе десятичных манипуляций для минимизации булевой функции. Международная конференция по электронному проектированию, компьютерным сетям и автоматизированной проверке 2015 г. (EDCAV), Шиллонг, Индия (Доклад конференции). Кафедра электроники и связи, Инженерный национальный технологический институт, Аруначал-Прадеш, Юпия, Индия. стр. 18–22. doi :10.1109/EDCAV.2015.7060531. Архивировано из оригинала 2020-05-08 . Получено 2020-05-08 .[6] (Примечание. В этой работе не упоминается предшествующий уровень техники по десятичным методам.) (5 страниц)
22. Масек, Уильям Дж. (1979). Некоторые NP-полные множества, покрывающие проблемы . неопубликовано.
23. Чорт, Себастьян Лукас Арне (1999). Сложность минимизации дизъюнктивных нормальных форм формул (магистерская диссертация). Университет Орхуса.
24. Umans, Christopher ; Villa, Tiziano; Sangiovanni-Vincentelli, Alberto Luigi (2006-06-05). «Сложность минимизации двухуровневой логики». IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 25 (7): 1230–1246. doi :10.1109/TCAD.2005.855944. S2CID  10187481.
25. Чандра, Ашок К.; Марковски, Джордж (1978). «О числе простых импликантов». Дискретная математика . 24 (1): 7–11. doi : 10.1016/0012-365X(78)90168-1 .
26. Нельсон, Виктор П.; Нэгл, Х. Трой; Кэрролл, Билл Д.; Ирвин, Дж. Дэвид (1995). Анализ и проектирование цифровых логических схем (2-е изд.). Prentice Hall . стр. 234. ISBN 978-0-13463894-2. Получено 2014-08-26 .
27. Моссе, Милан; Ша, Гарри; Тан, Ли-Ян (2022). «Обобщение леммы о выполнимости кодирования и ее применения». DROPS-IDN/V2/Document/10.4230/LIPIcs.SAT.2022.9 . Замок Дагштуль – Центр информатики им. Лейбница. doi : 10.4230/LIPIcs.SAT.2022.9 .
28. Фельдман, Виталий (2009). «Трудность приближенной двухуровневой логической минимизации и обучения PAC с запросами на членство». Журнал компьютерных и системных наук . 75 : 13–25 [13–14]. doi : 10.1016/j.jcss.2008.07.007 .
29. Gimpel, James F. (1965). «Метод создания булевой функции, имеющей произвольную предписанную таблицу простых импликант». IEEE Transactions on Computers . 14 : 485–488. doi :10.1109/PGEC.1965.264175.
30. Пол, Вольфганг Якоб [на немецком языке] (1974). «Булеш-минимальный полином и проблема Überdeckungs». Acta Informatica (на немецком языке). 4 (4): 321–336. дои : 10.1007/BF00289615. S2CID  35973949.
31. Логическая пятничная программа

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

• Кертис, Герберт Аллен (1962). "Глава 2.3. Метод МакКласки". Новый подход к проектированию коммутационных схем . Серия Bell Laboratories (1-е изд.). Принстон, Нью-Джерси, США: D. van Nostrand Company, Inc. стр. 90–160. ISBN 0-44201794-4. OCLC  1036797958. S2CID  57068910. ISBN 978-0-44201794-1 . ark:/13960/t56d6st0q. (viii+635 страниц) (Примечание. Эта книга была переиздана Чин Джи в 1969 году.)
• Coudert, Olivier (октябрь 1994 г.). "Two-level logic minimization: an overview" (PDF) . Integration, the VLSI Journal . 17–2 (2): 97–140. doi :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. doi :10.1007/s11135-008-9183-x. S2CID  123042755. Номер статьи: 99 (2010).[9] (22 страницы)
• Душа, Адриан (2007). "Улучшение Куайна-Маккласки" (PDF) . Бухарестский университет . Архивировано (PDF) из оригинала 2020-05-12 . Получено 2020-05-12 .(16 страниц) (Примечание.

Внешние ссылки

• Учебное пособие по методу Куайна-Маккласки и Петрика.
• Для полностью проработанного примера посетите: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm