Karnaugh' kaart

Allikas: Vikipeedia
Karnaugh' kaart

Karnaugh' kaart, tuntud ka kui Veitchi diagramm, on abivahend kahendväärtusi sisaldava avaldise lihtsustamiseks. Karnaugh' kaardi leiutas 1953. aastal Bell Labsi instituudi telekommunikatsiooni insener Maurice Karnaugh.

Tõeväärtustabelist võetud väärtused paigutatakse kaardile ja järjestatakse Gray koodi printsiibi kohaselt, s.o kõrvutiasetsevate tulpade või ridade puhul erineb vaid ühe muutuja väärtus. Seejärel moodustatakse tabelis olevatest tõestest väärtustest võimalikult suured grupid (kontuurid) suurusega 2n (1, 2, 4, 8, ...). Kontuuride põhjal leitakse avaldise lihtsustatud kuju.

Mõisted[muuda | redigeeri lähteteksti]

Loogikafunktsiooni normaalkujude leidmisel kasutatakse mõisteid: disjunktiivne normaalkuju (DNK) (funktsiooni 1-de piirkond) ja konjunktiivne normaalkuju (KNK) (funktsiooni 0-de piirkond). Nendest on tuletatud täielik DNK (TDNK) ja täielik KNK (TKNK). DNK ja KNK on üksteisest sõltumatud. Kui tuleb leida, kas DNK ja KNK on võrdsed, siis võetakse kasutusele funktsioon ja lisatakse vastavad indeksid d, j ja k.

Karnaugh' kaardil valitakse välja kindlate suurustega maksimaalsed piirkonnad, mida kutsutakse kontuurideks.

Näide DNK ja KNK võrdlemisest[muuda | redigeeri lähteteksti]

Juhul kui on antud funktsioon \begin{matrix}f(x_1,x_2,x_3,x_4)=\Pi(1,4,5,9,11,12,13,15)_0(3,14)\end{matrix}, pole DNK ja KNK võrdsed, sest \begin{matrix}F_d(1110)\ne F_k(1110)\end{matrix}

Kasutusala[muuda | redigeeri lähteteksti]

Tavaliselt kasutatakse täiendavaid arvutusi leidmaks kahendväärtusliku funktsiooni valemi minimeeritud, s.o lühimat ja efektiivseimat kuju, aga selleks võib kasutada ka Karnaugh' kaarti.

  • Karnaugh' kaart kasutab ära inimese tähelepanuväärset mustrisobitusoskust otsustamaks tingimusi, mille järgi kombineerida lihtsaim valem.
  • Karnaugh' kaart võimaldab tuvastada ja elimineerida potentsiaalsed valikuvõimalused, millega tavaline valemitega lihtsustamine hakkama ei saa.
  • Karnaugh' kaart on suurepärane abivahend kuni kuue muutujaga valemites, kuid kui muutujaid on rohkem, muutub mustri sobitamine nõnda keeruliseks, et inimesel tekib raskusi optimaalse valemi leidmisel.

Karnaugh' kaarti kasutatakse ka loogikafunktsioonide ja nende minimeerimise õpetamiseks.

Omadused[muuda | redigeeri lähteteksti]

Karnaugh' kaardil võib olla palju muutujaid, kuid tavaliselt leiab ta kasutust, kui muutujaid on vähe (2–6). Iga uus muutuja kahekordistab valemi võimaluste arvu, võimaluste arvu saab kirja panna ka kui \begin{matrix}2^{muutujaid}\end{matrix}. Karnaugh' kaardil on muutujad on paigutatud nõnda, et need erineksid kõrvutiasetsevate tulpade või ridade vahel vaid ühe kahendväärtuse võrra. Ainult nõnda on võimalik leida valemi minimaalkuju.

Näide[muuda | redigeeri lähteteksti]

Tuleb leida funktsiooni \begin{matrix}f(x_1,...,x_4)=\sum (2,3,6,7,9,10,11,14)_1\end{matrix}

     X1X2X3X4   f 
 0.  0 0 0 0   1
 1.  0 0 0 1   1
 2.  0 0 1 0   0
 3.  0 0 1 1   1
 4.  0 1 0 0   0
 5.  0 1 0 1   0
 6.  0 1 1 0   0 
 7.  0 1 1 1   1
 8.  1 0 0 0   1
 9.  1 0 0 1   1
10.  1 0 1 0   0
11.  1 0 1 1   1 
12.  1 1 0 0   1
13.  1 1 0 1   1
14.  1 1 1 0   0
15.  1 1 1 1   1

Peas luuakse funktsiooni kahendväärtuste tabel

TDNK

Joonis

Karnaugh' kaardi kasutamine ei ole otstarbekas, kui muutujaid on rohkem kui neli. Kaart muutub matemaatiliseks ristsõnaks, kui muutujaid on rohkem kui kuus. Sellistel juhtudel tuleks kasutada Quine-McCluskey algoritmi. Selle abil on võimalik leida suurem osa optimaalilähedasi lahendeid, kuid valimaks optimaalseimat, võib siiski olla vaja valemile läheneda jõumeetodiga. (See on siiski üldiselt palju lihtsam, kui jõumeetodil lahendada kogu probleemi.).

Vaata ka[muuda | redigeeri lähteteksti]

Välislingid[muuda | redigeeri lähteteksti]