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

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

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

Пример

Корак 1: проналажење простих импликаната 
Минимализоваћемо једну произвољну функцију:

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

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

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

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

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

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

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

.
.

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

.

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

Референце

Спољашње везе 
 -{Quine-McCluskey algorithm implementation with a search of all solutions , by Frédéric Carpon.}-
 -{All about Quine-McClusky, article by Jack Crenshaw comparing Quine-McClusky to Karnaugh maps}-
 -{Kmap minimizer  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 , QMC based boolean logic simplifiers supporting up to 64 inputs / 64 outputs (independently) or 32 outputs (simultaneously)}-

Булова алгебра
Математичка логика
Алгебра
Теоријско рачунарство
Квајн–Макласкијев алгоритам ( , метод простих импликаната ) је метод који се користи за минимализацију логичких функција који су открили Вилард Ван Орман Квајн и Едвард Џ. Макласки године . Овај метод је врло функционалан , баш као и карноове карте , али његова таблична форма га чини лакшим и практичнијим за програмирање , такође , даје и детерминистички пут проналажења минималне форме који управо гарантује да је добијена истинитосна функција минимална . Зову га још и таблични метод . Метод чине два корака : Проналажење простих инпликаната функције . Користи те просте импликанте у табели простих импликаната да пронађе само битне просте импликанте функције , као и друге просте импликанте који су потребни да покрију целу функцију . Комплексност Иако практичнији од карнових карти , када као улаз функција добија више од четири променњиве , Квајн–Макласкијев алгоритам има такође ограничен спектар употребе , јер проблем спада у НП-тешке проблеме : време извршавања Квајн–Макласкијевог алгоритма расте експоненцијално са порастом променљивих . Може се показати да је за функцију од -{ n }- променњивих горња граница броја примарних импликаната -{ 3n /n }- . За -{ n }- =може бити преко5 *простих импликаната . Функције са великим бројем променљивих морају бити минимализоване са неоптималним хеуристичним методама , заправо алгоритам -{ ESPRESSO }- је стандард . Пример Корак проналажење простих импликаната Минимализоваћемо једну произвољну функцију : Израз назначује да ће излазна вредност функције -{ f }- битиза улазне вредности8,10 ,11,12 и( означене са 'm ' ) . Такође , говори да нам излазна вредност уколико улазни подаци одговарају децималним бројевимаинису битне. ( -{ 'd ' }- означава небитне вредности ). - { }- Лако се може формирати израз канонског збира производа из ове табеле , управо сумирајући колоне на којима се као излазна вредност добија( без небитних вредности ) . Ова функција није минимална . Да би је оптимизовали , потребно је груписати све чланове Функције , тако да сви чланови једне групе имају исти број цифара " 1 " у својој бинарној представи . Небитне вредности су такође убачене у таблу тако да се могу комбиновати са члановима функције . У овом тренутку можемо почети са комбиновањем чланова функције са другим члановима . Уколико се два члана разликују на тачно једном месту( у бинарном облику ) та цифра бива замењена цртицом '- ' , што имплицира да она није битна . Чланови који више не могу бити комбиноване су означене са ' * ' . Када се прелази са комбинација величине два , на комбинације величине четири , сматрати '- ' као трећу вредност битова . Пример:иили могу бити комбиноване , међутим ,и не могу . ( Напомена : места на којима се налазе '- ' морају да се поклапају . ) Напомена : У овом примеру , ни један члан величинесе не може комбиновати у наставку . Ово имплицира да је крај првог корака алгоритма , уколико би била могућа даља комбиновања алгоритам би требало наставити ( чланови величине ) . Корак табела простих импликаната Ни један од чланова не може бити даље комбинован , дакле можемо приступити проналажењу битних примарних импликаната . Редове таблице представљају импликанти који су настали , док колоне чине чланови функције . Небитне вредности нису постављене као засебне колоне - оне су сувишне за овај део алгоритма јер их не морамо имплементирати( нису обавезни као улази ) . Овде , сваки од битних простих импликаната је означен * - други прост импликант може бити покривен трећим и четвртим , и трећи прост импликант може бити покривен другим и првим , међутим то није ни битно . Ако је прост импликант од суштинског значаја , као што је и очекивано , потребно га је укључити у минималну форму . У неким случајевима , битни прости импликатори не покривају све чланове функције , у том случају додатна процедура алгоритма мора бити упошљена . Једноставна " додатна процедура " је пресуђивање и грешка , али више систематичнији начин је Патриков метод . У овом примеру , битни прости импликатори не покривају све чланове , дакле , у овом случају могу се комбиновати битни импликанти са једним од два небитна па се тако добија једно од два могућа решења : . . Оба решења су еквивалентна оригиналном , не минималном решењу : . Види још Булова алгебра Де Морганови закони Карноова карта Минимализација кола Референце Спољашње везе -{ Quine-McCluskey algorithm implementation with a search of all solutions , by Frédéric Carpon . }- -{ All about Quine-McClusky , article by Jack Crenshaw comparing Quine-McClusky to Karnaugh maps }- -{ Kmap minimizer Flash application based on Quine-McCluskey Algorithm . }- -{ Karma 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 , QMC based boolean logic simplifiers supporting up toinputs / outputs ( independently ) oroutputs ( simultaneously ) }- Булова алгебра Математичка логика Алгебра Теоријско рачунарство