Karnaugh' kaart

Allikas: Vikipeedia

Karnaugh kaart, tuntud ka kui Veitchi diagramm, on abivahend käitlemaks kahendväärtuseid ja leidmaks valemi minimaalse kuju. Kaardil olevate numbrite väärtuste paigutused on erilised, kuna paiknevad Gray koodi prinsiibi kohaselt - erinevad vaid ühe kahendväärtuse võrra.

Sisukord

[redigeeri] Ajalugu ja nomenklatuur

Karnaugh kaardi leiutas 1953 aastal, Bell Labsi instituudi telekommunikatsiooni insener Maurice Karnaugh.

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 üksteiselt sõltumatud. Kuid kui tuleb leida kas juhuslikult on DNK ja KNK võrdsed, siis võetakse kasutusele funktsioon ja lisatakse vastavad indeksid d j k.

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

[redigeeri] Näide DNK ja KNK võrdlemisest

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}

[redigeeri] Kasutusala

Tavaliselt kasutatakse täiendavaid arvutusi leidmaks kahendväärtusliku funktsiooni valemi minimeeritud[1] kuju, aga selleks võib kasutada ka Karnaugh kaarti.

Probleemi lahendamisena kasutatakse, kui:

  • Karnaugh kaart kasutab ära inimese tähelepanuväärset mustri sobitavus oskust otsustamaks tingimused mille järgi tuleks kombineerida lihtsaim valem.
  • Karnaugh kaart võimaldab idenfitseerida[2] ja elimineerida[3] potensiaalsed[4] valikuvõimalused[5].
  • Karnaugh kaart on suurepärane abivahend kuni kuue muutujaga valemites, kuid kui muutujaid on rohkem, muutub mustri sobitamine nõnda keeruliseks, et inimesel tekib raskuseid[6] optimaalse[7] valemi leidmisel.

Karnaugh kaarti kasutatakse ka õpetamaks kahendväärtuse funktsioone ja minimeerimist.

[redigeeri] Omadused

Karnaugh kaardil võib olla palju muutujaid, kuid tavaliselt leiab ta kasutust, kui muutujaid on vähe, 2 kuni 6. Iga uus muutuja 2 kordistab valemi võimaluste arvu, võimaluste arvu saab kirjapanna ka kui \begin{matrix}2^{muutujaid}\end{matrix}. Karnaugh kaardi väärtuste asukohad on organiseeritud, nõnda et nende väärtused erineksid vaid ühe kahendväärtuse võrra. Ainult nõnda on võimalik leida valemi minimaalkuju.

[redigeeri] Näide

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

[redigeeri] Millal tasuks Karnaugh kaarti mitte kasutada

Kaart saab segipaisatud ja muutub raskeks kasutada, kui muutujaid on neljast rohkem. Kaart muutub matemaatiliseks ristsõnaks, kui muutujaid on rohkem kui kuus. Sellistel juhtudel tuleks kasutada Quine-McCluskey algoritmi[8].

[redigeeri] Vaata ka

  • Karnaugh' kaardid
  • Venni diagramm
  • Kahendväärtus
  • Quine–McCluskey algoritm

[redigeeri] Allmärkused

  1. ^ Kõige võikeim, lühem ehk efektiivseim
  2. ^ Tuvastada
  3. ^ Eemaldada
  4. ^ võimalikud
  5. ^ Mainimisväärseks teeb selle asjaolu, et tavaline valemitega lihtsustamine sellega hakkama ei saa.
  6. ^ Lühidalt, inimesed kes pole matemaatilised geeniused, pole selleks võimelised ilma välisabita.
  7. ^ Kõige parima antud olukorras
  8. ^ Algoritmi abil on võimalik leida suurem osa optimaali lähedaseid lahendeid, kuid valimaks optimaalsimat, võib siiski vajada valemile jõumeetodi põhist lähenemis. (See on siiski üldiselt palju lihtsam, kui jõumeetodil lahendada kogu probleemi.)