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
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 
Juhul kui on antud funktsioon , pole DNK ja KNK võrdsed, sest 

Kasutusala
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
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 . 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
Tuleb leida funktsiooni  

      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 349px|TDNK|right 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
 Venni diagramm
 Kahendväärtus
 Quine'i–McCluskey algoritm

Välislingid
 Karnaugh' kaart. Minimeerimine kaardiga.

Kategooria:Matemaatika