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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:17, 7 марта 2016.

Метод Куайна — Мак-Класки (англ. Quine–McCluskey method) позволяет с помощью таблиц минимизировать булевы функции. Предложен Уиллардом Куайном и доработан Эдвардом Мак-Класки. Его разработка связана с попыткой избавиться от недостатков метода Куайна.

Уиллард Куайн

Уиллард Ван Орман Куайн (англ. Willard Van Orman Quine) — американский философ, логик и математик. Родился 25 июня 1908 года в Акроне, штат Огайо. Умер 25 декабря 2000 года в Бостоне, штат Массачусетс, в возрасте 92 лет.[1]

Краткая биография

Происходит из семьи предпринимателя и школьной учительницы. В 1930 году получил степень бакалавра в Оберлинском колледже. Следующие два года учился в Гарвардском университете под руководством Алфреда Норта Уайтхеда.

Поездка в Европу в 1932-1933 годах свела его с членами Венского кружка. Через год, уже вернувшись в Гарвард, занялся одной из основных проблем Венского кружка, а именно над вопросом о роли логики в обосновании математики.

В 1941 году Уиллард Куайн получил звание доцента. Год спустя принял участие во Второй Мировой войне, но не в качестве солдата, а в качестве шифровальщика в американском морском флоте. В его задачу входило разгадывать шифры немецких подводных лодок.

Спустя три года после окончания войны Куайн стал профессором Гарвардского университета и женился во второй раз. Два брака принесло ему четверых детей.[2]

В 1956 году Эдвард Мак-Класки доработал метод Куайна. Под конец жизни, в 1993 году, Уиллард Куайн получил премию Рольфа Шока в области логики и философии.

Философские взгляды

В философии Куайн придерживался позиций крайнего номинализма, испытывал влияние неопозитивизма, прагматизма и бихевиоризма. В 1951 году выпустил статью «Две догмы эмпиризма», где подверг критике ряд основополагающих идей неопозитивизма. В частности, он доказывает в статье, что высказывание «Всякий холостяк неженат» представляет собой догму эмпиризма, а не логического позитивизма[3]. Только опыт позволяет заявить подобное утверждение. «Две догмы эмпиризма» усилили интерес в США к аналитической философии, привнесло в неё элементы прагматизма.

Уиллард Куайн стремился к конкретике и находил философию мало отличающейся от естественных наук. Главное отличие, по его мнению, заключалось в общности положений и принципов. Собственную позицию философ обозначал как натурализм, или научный реализм.

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

Язык также был предметом внимания Уилларда Куайна. По нему, язык — важнейшая форма человеческого поведения, а наука — один из путей приспособления организма к окружающей среде. Отсюда выделяется и проблема переводимости языков, при этом «радикальный перевод» остаётся принципиально неопределённым.

Эдвард Мак-Класки

Эдвард Джозеф[4] Мак-Класки (англ. Edward Joseph McCluskey) — ныне покойный профессор Стэнфордского университета, пионер в области электротехники. Родился 16 октября 1929 года в Нью-Йорке, умер 13 февраля 2016 года в возрасте 86 лет.[5]

Краткая биография

Родился накануне Великой Депрессии. Закончил Боудин-колледж, штат Мэн, в 1953 году. Достигнув заметных успехов на поприще физики и математики, перешёл в Массачусетский технологический институт изучать электротехнику. Там же, в 1956 году, получил докторскую степень.

В Bell Labs он начал разрабатывать теорию переходов в логических сетях, чем продолжил заниматься и после перехода в Принстон в 1959 году. Данной теорией пользуются по сей день. В Принстонском университете Мак-Класки также сформулировал концепцию режимов работы последовательных схем.[6] Помимо научных изысканий, он преподавал электротехнику и основал в Принстоне компьютерный центр.[7]

Метод Куайна — Мак-Класки введён в диссертации «Алгебраическая минимизация и разработка контактных сетей двухполюсников» (1956 год)[8] под руководством Самюэля Х. Колдвелла. В те времена Эдвард Мак-Класки был аспирантом Массачусетского технологического института. Данный метод представляет собой алгоритм проектирования комбинационных схем, процедуру логической минимизации.

С 1966 года работал в Стэнфорде. Его исследования там посвящены логической проверке, синтезу, дизайну, тестируемости и отказоустойчивости вычислительной техники. Здесь он также оставил после себя исторический след, основав лабораторию цифровых систем. А в 1970 году Мак-Класки помог ввести Стэнфордскую компьютерно-инженерную программу и в тот же год стал первым президентом компьютерного сообщества IEEE (Институт инженеров электротехники и электроники).

Как и Уиллард Куайн, удостоился награды под конец жизни. Только получил не премию Рольфа Шока, а медаль Неймана (2012 год), в знак признания его заслуг при жизни.

Метод Куайна

Метод Куайна (англ. Quine’s method) — способ минимизации булевых функций с их представлением в виде ДНФ или КНФ. Предложен Уиллардом Куайном в 1950 году. Согласно этому алгоритму, преобразование функции производится в два этапа:

  1. Переход от канонической формы (СДНФ или СКНФ) к сокращённой;
  2. Переход от сокращённой формы к минимальной.[9]

Первый этап

Положим, что функция представлена в виде СДНФ. Тогда, чтобы привести её к сокращённой форме, необходимо совершить операции склеивания и поглощения. Операция склеивания осуществляется при наличии пар членов, соответствующих общей форме или , где может быть конъюнкцией любого числа переменных, отличающихся от . После того, как все такие пары будут найдены, производится собственно операция склеивания: . Результаты склеивания теперь играют роль дополнительных членов.

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

Рассмотрим пример: .

0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

СДНФ

После операции склеивания наша функция принимает вид:

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

Теперь действительно наступает этап поглощения:

В такой форме функция состоит из так называемых простых импликант функции. Это наиболее простое представление функции по сравнению с её СДНФ.

Второй этап (табличный)

Рассмотренный выше пример уже удовлетворяет определению минимальной формы, однако далеко не всегда после первого этапа сокращённая форма совпадает с минимальной. Ещё могут оставаться члены, чьё удаление не изменяет конечный результат. На данном этапе требуется удалить лишние переменные.

Приведём новый пример:

0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 1
1 1 1 1 1

СДНФ

После первого этапа функция принимает вид:

Мы вновь получили дизъюнкцию простых импликант, на этот раз в количестве пяти штук. Чтобы получить минимальную форму, воспользуемся импликантной матрицей. Столбцы в ней соответствуют членам СДНФ, а строки — членам сокращённой формы. Отмечаются столбцы членов СДНФ, которые поглощаются отдельными простыми импликантами:

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

Выбор остальных импликант, что войдут в минимальную форму, сводится к нахождению минимального набора неядровых импликант, которые покроют столбцы, не перекрываемые ядровыми. Применительно к рассматриваемому случаю это будут третий и четвёртый столбец. Выбрать можно разными способами. Мы возьмём импликанту . Итак, мы получили минимальную дизъюнктивную нормальную форму (МДНФ):

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

Для реализации метода Куайна через СКНФ нужно произвести вышеприведённые этапы с учётом двойственности конъюнкции и дизъюнкции.

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

  1. Нахождение первичных импликант;
  2. Эти импликанты разбиваются на группы, в каждую группу входят импликанты с равным количеством единиц (нулей);
  3. Производится попарное сравнение эквивалентов (термов) в соседних группах, с целью формирования термов более низких рангов;
  4. Составляется таблица, где строкам соответствуют первичные импликанты, а заголовкам столбцов — термы низких рангов;
  5. Расставляются метки, отражающие поглощение термов высших рангов (исходных термов).[10]
  6. Находятся существенные импликанты;
  7. Вычёркиваются лишние столбцы;
  8. Вычёркиваются лишние первичные импликанты;
  9. Выбирается минимальное покрытие максимальными интервалами.[11]

Особенности

По сравнению с методом Куайна, метод Куайна — Мак-Класки требует меньшего числа попарных сравнений на предмет склеивания. Сокращение становится возможным благодаря разбиению на равнодушные группы (см. п. 2 предыдущего раздела). Это позволяет исключить бессмысленные на предмет склеивания сравнения.

Пример

Первым делом необходимо найти первичные импликанты. Для этого определим вес каждого минтерма функции (элементарная конъюнкция ранга ). Сравниваем те минтермы, чьи веса отличаются на единицу. Получаем минтермы ранга , на месте разрядов с различающимися значениями пишем ~. Далее сравниваем новые минтермы с учётом тильда-разрядов, получаем минтермы ранга и так далее, пока это возможно. Отмечаем минтермы, на которых произошло склеивание. Оставшиеся — первичные, или простые, импликанты.

Положим, что вышеприведённая функция записана в виде СДНФ. Тогда первичными импликантами будут 010~, 0~11, 1~01, 111~, ~1~1. Теперь переходим к расставлению меток в описанной выше таблице. Если первичная импликанта входит в минтерм, ставим отметку:

0011 0100 0101 0111 1001 1101 1110 1111
010~
0~11
1~01
111~
~1~1

Существенными импликантами будут те, где в соответствующих столбцах стоит только одна метка. Без любой из них не будет полного покрытия исходных минтермов. Итого получается, что в данном примере существенные импликанты — 0~11, 010~, 1~01, 111~. Как видим, самая короткая конъюнкция в решение не вошла.

Уберём лишние строки (в данном случае только одну) и выберем такую совокупность первичных импликант, что включает метки во всех столбцах. Предпочтение отдаётся минимальной выборке. Получаем искомую МДНФ:

Достоинства и недостатки

К достоинствам метода Куайна — Мак-Класки можно отнести следующие положения:

  • Его можно применять на большом количестве переменных в САПР, с использованием ЭВМ для минимизации полностью или частично определённых функций;
  • Не принципиально, задана функция в СДНФ или СКНФ;
  • Удобно минимизировать системы булевых функций в связи с простым выделением общих частей реализуемой системы ФАЛ;
  • Данный метод — алгоритмически систематический, он легко формализуется и алгоритмизируется. Не зависит от навыков разработчика;
  • Позволяет последовательно осуществить все этапы минимизации (склеивание и выявление лишних импликант, получение минимальных покрытий).

Несмотря на приведённые достоинства, у рассматриваемого метода есть два сравнительно серьёзных недостатка:

  • Затруднительна ручная минимизация функций с шестью и более переменных;
  • Метод Куайна — Мак-Класки алгоритмически неинвариантен: время работы растёт экспоненциально с увеличением входных данных. Если функция зависит от чересчур большого числа переменных, используют эвристические алгоритмы.

Список источников