Karnaugh' kaart
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 pole DNK ja KNK võrdsed, sest
[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 . 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
Peas luuakse funktsiooni kahendväärtuste tabel |
Joonis |
[redigeeri] Millal tasuks Karnaugh kaarti mitte kasutada
Kaart saab segipaisatud ja muutub raskeks kasutada, kui muutujaid on neljast rohkem. Kuid 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
- ^ Kõige võikeim, lühem ehk efektiivseim
- ^ Tuvastada
- ^ Eemaldada
- ^ võimalikud
- ^ Mainimisväärseks teeb selle asjaolu, et tavaline valemitega lihtsustamine sellega hakkama ei saa.
- ^ Lühidalt, inimesed kes pole matemaatilised geeniused, pole selleks võimelised ilma välisabita.
- ^ Kõige parima antud olukorras
- ^ 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.)