Квајн–Макласкијев алгоритам

Квајн–Макласкијев алгоритам (енгл. Quine–McCluskey algorithm, метод простих импликаната) је метод који се користи за минимализацију логичких функција који су открили Вилард Ван Орман Квајн и Едвард Џ. Макласки 1956. године.^[1][2][3] Овај метод је врло функционалан, баш као и карноове карте, али његова таблична форма га чини лакшим и практичнијим за програмирање, такође, даје и детерминистички пут проналажења минималне форме који управо гарантује да је добијена истинитосна функција минимална. Зову га још и таблични метод.

Метод чине два корака:

1. Проналажење простих инпликаната функције.
2. Користи те просте импликанте у табели простих импликаната да пронађе само битне просте импликанте функције, као и друге просте импликанте који су потребни да покрију целу функцију.

Иако практичнији од карнових карти, када као улаз функција добија више од четири променњиве, Квајн–Макласкијев алгоритам има такође ограничен спектар употребе, јер проблем спада у НП-тешке проблеме: време извршавања Квајн–Макласкијевог алгоритма расте експоненцијално са порастом променљивих. Може се показати да је за функцију од n променњивих горња граница броја примарних импликаната 3ⁿ/n. За n = 32 може бити преко 6.5 * 10¹⁵ простих импликаната. Функције са великим бројем променљивих морају бити минимализоване са неоптималним хеуристичним методама, заправо алгоритам ESPRESSO је стандард.^[4]

Минимализоваћемо једну произвољну функцију:

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

Израз назначује да ће излазна вредност функције f бити 1 за улазне вредности 4,8,10,11,12 и 15 (означене са 'm'). Такође, говори да нам излазна вредност уколико улазни подаци одговарају децималним бројевима 9 и 14 нису битне. ('d' означава небитне вредности).

Лако се може формирати израз канонског збира производа из ове табеле, управо сумирајући колоне на којима се као излазна вредност добија 1 (без небитних вредности).

${\displaystyle f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'CD'+AB'CD+ABC'D'+ABCD,}$

Ова функција није минимална. Да би је оптимизовали, потребно је груписати све чланове Функције, тако да сви чланови једне групе имају исти број цифара "1" у својој бинарној представи. Небитне вредности су такође убачене у таблу тако да се могу комбиновати са члановима функције.

У овом тренутку можемо почети са комбиновањем чланова функције са другим члановима. Уколико се два члана разликују на тачно једном месту(у бинарном облику) та цифра бива замењена цртицом '-', што имплицира да она није битна. Чланови који више не могу бити комбиноване су означене са '*'. Када се прелази са комбинација величине два, на комбинације величине четири, сматрати '-' као трећу вредност битова. Пример: -110 и -100 или -11- могу бити комбиноване, међутим, -110 и 011- не могу. (Напомена: места на којима се налазе '-' морају да се поклапају.)

Напомена: У овом примеру, ни један члан величине 4 се не може комбиновати у наставку. Ово имплицира да је крај првог корака алгоритма, уколико би била могућа даља комбиновања алгоритам би требало наставити (чланови величине 8 ).

Ни један од чланова не може бити даље комбинован, дакле можемо приступити проналажењу битних примарних импликаната. Редове таблице представљају импликанти који су настали, док колоне чине чланови функције. Небитне вредности нису постављене као засебне колоне - оне су сувишне за овај део алгоритма јер их не морамо имплементирати(нису обавезни као улази).

Овде, сваки од битних простих импликаната је означен * - други прост импликант може бити покривен трећим и четвртим, и трећи прост импликант може бити покривен другим и првим, међутим то није ни битно. Ако је прост импликант од суштинског значаја, као што је и очекивано, потребно га је укључити у минималну форму. У неким случајевима, битни прости импликатори не покривају све чланове функције, у том случају додатна процедура алгоритма мора бити упошљена. Једноставна "додатна процедура" је пресуђивање и грешка, али више систематичнији начин је Патриков метод. У овом примеру, битни прости импликатори не покривају све чланове, дакле, у овом случају могу се комбиновати битни импликанти са једним од два небитна па се тако добија једно од два могућа решења:

${\displaystyle f_{A,B,C,D}=BC'D'+AB'+AC\ }$.

${\displaystyle f_{A,B,C,D}=BC'D'+AD'+AC.\ }$.

Оба решења су еквивалентна оригиналном , не минималном решењу:

${\displaystyle f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'C'D+AB'CD'+AB'CD+ABC'D'+ABCD'+ABCD.\ }$.

• Булова алгебра
• Де Морганови закони
• Карноова карта
• Минимализација кола

• Quine-McCluskey algorithm implementation with a search of all solutions Архивирано на веб-сајту Wayback Machine (3. новембар 2013), by Frédéric Carpon.
• All about Quine-McClusky, article by Jack Crenshaw comparing Quine-McClusky to Karnaugh maps
• Kmap minimizer Архивирано на веб-сајту Wayback Machine (3. март 2012) Flash application based on Quine-McCluskey Algorithm.
• Karma 3, A set of logic synthesis tools including Karnaugh maps, Quine-McCluskey minimization, BDDs, probabilities, teaching module and more. Logic Circuits Synthesis Labs (LogiCS), Brazil.
• A. Costa BFunc Архивирано на веб-сајту Wayback Machine (10. јун 2015), QMC based boolean logic simplifiers supporting up to 64 inputs / 64 outputs (independently) or 32 outputs (simultaneously)