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

'''Квајн–Макласкијев алгоритам''' ({{jez-eng|Quine–McCluskey algorithm}}, ''метод простих импликаната'') је метод који се користи за минимализацију логичких функција који су открили [[Вилард Ван Орман Квајн]] и [[Edward J. McCluskey|Едвард Џ. Макласки]] [[1956]]. године.<ref>{{cite journal |last=Quine |first=W. V. |date= 1952 |title=The Problem of Simplifying Truth Functions |url=https://archive.org/details/sim_american-mathematical-monthly_1952-10_59_8/page/521 |jstor=2308219 |journal=The American Mathematical Monthly |publisher= |volume=59 |issue=8 |pages=521–531 |doi= 10.2307/2308219}}</ref><ref>{{cite journal |last=Quine |first=W. V. |date= 1955 |title=A Way to Simplify Truth Functions |url=https://archive.org/details/sim_american-mathematical-monthly_1955-11_62_9/page/627 |jstor=2307285 |journal=The American Mathematical Monthly |publisher= |volume=62 |issue=9 |pages=627–631 |doi= 10.2307/2307285}}</ref><ref>{{cite journal |last=McCluskey |first=E.J., Jr. |date= 1956 |title=Minimization of Boolean Functions |url=https://archive.org/details/bstj35-6-1417 |journal=Bell System Technical Journal |publisher= |volume=35 |issue=6 |pages=1417–1444 |doi= 10.1002/j.1538-7305.1956.tb03835.x|accessdate = 24. 08. 2014}}</ref> Овај метод је врло функционалан, баш као и [[карноова карта|карноове карте]], али његова таблична форма га чини лакшим и практичнијим за програмирање, такође, даје и детерминистички пут проналажења минималне форме који управо гарантује да је добијена истинитосна функција минимална. Зову га још и ''таблични метод''.

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

== Комплексност ==
Иако практичнији од карнових карти, када као улаз функција добија више од четири променњиве, Квајн–Макласкијев алгоритам има такође ограничен спектар употребе, јер проблем спада у [[НП-тешки проблеми|НП-тешке проблеме]]: време извршавања Квајн–Макласкијевог алгоритма расте [[Експоненцијално време|експоненцијално]] са порастом променљивих. Може се показати да је за функцију од -{''n''}- променњивих горња граница броја примарних импликаната -{3<sup>''n''</sup>/''n''}-. За -{''n''}- = 32 може бити преко 6.5 * 10<sup>15</sup> простих импликаната. Функције са великим бројем променљивих морају бити минимализоване са неоптималним [[Хеуристички модел|хеуристичним]] методама, заправо алгоритам -{ESPRESSO}- је стандард.<ref>-{V.P. Nelson e.a., ''Digital Circuit Analysis and Design'', Prentice Hall, 1995, pag. 234}-</ref> 

== Пример ==
=== Корак 1: проналажење простих импликаната ===
Минимализоваћемо једну произвољну функцију:
:<math>f(A,B,C,D) =\sum m(4,8,10,11,12,15) + d(9,14).  \,</math>
Израз назначује да ће излазна вредност функције -{''f''}- бити 1 за улазне вредности 4,8,10,11,12 и 15 (означене са 'm'). Такође, говори да нам излазна вредност уколико улазни подаци одговарају децималним бројевима 9 и 14 нису битне. (-{'d'}- означава небитне вредности).
-{
{| class="wikitable"
|-
!   !! A !! B !! C !! D !! !! f
|-
| m0 || 0 || 0 || 0 || 0 || || 0
|-
| m1 || 0 || 0 || 0 || 1 || || 0
|-
| m2 || 0 || 0 || 1 || 0 || || 0
|-
| m3 || 0 || 0 || 1 || 1 || || 0
|-
| m4 || 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 || || x
|-
| 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 || || x
|-
| m15 || 1 || 1 || 1 || 1 || || 1
|}
}-
Лако се може формирати израз канонског збира производа из ове табеле, управо сумирајући колоне на којима се као излазна вредност добија 1 (без небитних вредности).
:<math>f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD,</math>

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

{| class="wikitable"
|-
! Број јединица !! Мин члан !! Бинарна репрезензација
|-
| rowspan="2" | 1
| -{m4}- || 0100
|-
| -{m8}- || 1000
|-
| rowspan="3" | 2
| -{m9}- || 1001
|-
| -{m10}- || 1010
|-
| -{m12}- || 1100
|-
| rowspan="2" | 3
| -{m11}- || 1011
|-
| -{m14}- || 1110
|-
|| 4
| -{m15}- || 1111
|}

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

{| class="wikitable"
|-
! Број јединица !! Мин члам !! 0-коцка !! величина 2 импликаната !! величина 4 импликаната
|-
| rowspan="2" | 1
| -{m4}- || 0100 || -{m}-(4,12)  -100* || -{m}-(8,9,10,11) 10--*
|-
| -{m8}- || 1000 || -{m}-(8,9) 100- || -{m}-(8,10,12,14)  1--0*
|-
| -- || -- || -- || -{m}-(8,10)  10-0 || --
|-
| rowspan="3" | 2
| -{m}-9 || 1001 || -{m}-(8,12)  1-00 || -{m}-(10,11,14,15)  1-1-*
|-
| -{m}-10 || 1010 || -- || --
|-
| -{m}-12 || 1100 || -{m}-(9,11)  10-1 || --
|-
| -- || -- || -- || -{m}-(10,11)  101- || --
|-
| rowspan="2" | 3
| -{m}-11 || 1011 || -{m}-(10,14)  1-10 || --
|-
| -{m}-14 || 1110 || -{m}-(12,14)  11-0 || --
|-
| rowspan="2" | 4
| -{m}-15 || 1111 || -{m}-(11,15)  1-11 || --
|-
| || || -{m}-(14,15)  111- ||
|}

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

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

{| class="wikitable"
|-
|                 || 4 || 8 || 10 || 11 || 12 || 15 ||      || => || A || B || C || D
|-
| m(4,12)*        || X ||   ||    ||    || X  ||    || -100 || => || - || 1 || 0 || 0
|-
| m(8,9,10,11)    ||   || X || X  || X  ||    ||    || 10-- || => || 1 || 0 || - || -
|-
| m(8,10,12,14)   ||   || X || X  ||    || X  ||    || 1--0 || => || 1 || - || - || 0
|-
| m(10,11,14,15)* ||   ||   || X  || X  ||    || X  || 1-1- || => || 1 || - || 1 || -
|}

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

:<math>f_{A,B,C,D} = BC'D' + AB' + AC\ </math>.
:<math>f_{A,B,C,D} = BC'D' + AD' + AC.\ </math>.

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

:<math>f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.\ </math>.

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

== Референце ==
{{reflist}}

== Спољашње везе ==
* [http://frederic.carpon.perso.sfr.fr/Quine-McCluskey_%28frederic_carpon_implementation%29.php -{Quine-McCluskey algorithm implementation with a search of all solutions] {{Wayback|url=http://frederic.carpon.perso.sfr.fr/Quine-McCluskey_%28frederic_carpon_implementation%29.php |date=20131103054056 }}, by Frédéric Carpon.}-
* [https://web.archive.org/web/20090107120802/http://www.embedded.com/columns/programmerstoolbox/29111968 -{All about Quine-McClusky], article by Jack Crenshaw comparing Quine-McClusky to Karnaugh maps}-
* [http://2b2.eu/fun/game.php?gid=14 -{Kmap minimizer] {{Wayback|url=http://2b2.eu/fun/game.php?gid=14 |date=20120303030651 }} Flash application based on Quine-McCluskey Algorithm.}-
* [http://www.inf.ufrgs.br/logics/ -{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 [http://www4.dei.isep.ipp.pt/acc/bfunc/ -{BFunc] {{Wayback|url=http://www4.dei.isep.ipp.pt/acc/bfunc/ |date=20150610204444 }}, QMC based boolean logic simplifiers supporting up to 64 inputs / 64 outputs (independently) or 32 outputs (simultaneously)}-

{{нормативна контрола}}

[[Категорија:Булова алгебра]]
[[Категорија:Математичка логика]]
[[Категорија:Алгебра]]
[[Категорија:Теоријско рачунарство]]