Loogikafunktsioonide minimeerimine

Allikas: Teadmusbaas

Loogikafunktsioonide minimeerimine (lihtsustamine)

Loogikafunktsioonide minimeerimine on funktsiooni esitamine minimaalse keerukusega normaalkujul – minimaalsel disjunktiivsel normaalkujul (MDNK) või minimaalsel konjunktiivsel normaalkujul (MKNK). Tavaliselt tehakse seda loogikaalgebra põhiseoste (põhiomadused) ja asendusseoste abil, mis on küllaltki keeruline ja nõuab teatud kogemust. Kõige kiirem viis minimeerimiseks on Karnaugh’ kaardi kasutamine, kuid see on kasutatav ainult kuni 6 muutujaga loogikafunktsiooni korral.

Karnauh’ kaardiga minimeerimise sammud:


  1. Funktsiooni tõeväärtustabeli paigutamine Karnaugh’ kaardile;
  2. Kõikide 1-de piirkondade (MDNK) ja 0-de piirkondade (MKNK) katmine võimalikult väikese arvu võimalikult suurte kontuuridega;
  3. Iga valitud kontuuri jaoks tema ulatuses konstantsete muutujate xi leidmine;
  4. Kontuuri konstantsete muutujate järgi MDNK elementaarkonjunktsioonide või MKNK elementaardisjunktsioonide välja kirjutamine.

Iga kontuur annab ühe elementaarkonjunktsiooni või ühe elementaardisjunktsiooni! Kontuurid võivad osaliselt kattuda!

Näitena kasutame suvalist 3-muutuja funktsiooni, kanname funktsiooni väärtused kaardile, moodustame kontuurid.

Tabel 1. Suvalise loogikafunktsiooni tõeväärtustabel
x1x2x3f(x1,x2,x3)
0000
0011
0100
0111
1001
1011
1100
1111

Ühtede piirkond vt sele 1 on esitatud kahe kontuuriga – 2x2 ja 1x2, neljases kontuuris (2x2) on konstantne ainult x3, kaheses kontuuris on konstantsed x1=1 ja x2=0, iga ühtede kontuur määrab DNK-s ühe elementaarkonjunktsiooni.

MDNK: f(x1,x2,x3)=x1¬x2Vx3

1-de kontuuri ulatuses konstantne xi=1 annab otsevääruse xi ja xi=0 annab inversiooni NOT(xi)

Naide1.png Naide2.png

Sele 1. Ühtede piirkond                                                    Sele 2. Nullide piirkond

Nullide piirkond vt sele 2 on esitatud kahe 1x2 kontuuriga, ühes kontuuris on konstantsed x1=0 ja x3=0, teises on konstantsed x2=1 ja x3=0, iga nullide kontuur määrab KNK-s ühe elementaardisjunktsiooni.

MKNK: f(x1,x2,x3)=(x1Vx3)(¬x2Vx3)

Nullide kontuuri ulatuses konstantne xi=0 annab otsevääruse xi ja xi=1 annab inversiooni NOT(xi)

Sobivate kontuuride valikuks parimat algoritmi pole olemas, tuleb jälgida ainult valikukriteeriumit:

Vajalikud ruudud Karnaugh’ kaardil tuleb katta võimalikult väikese arvu võimalikult suurte kontuuridega

KONTROLL:

Tabel 2. Suvalise loogikafunktsiooni väärtuste kontrolltabel
x1x2x3f(x1,x2,x3) x1¬x2Vx3A=x1Vx3B=¬x2Vx3AB
00000010
00111111
01000000
01111111
10011111
10111111
11000100
11111111

On näha, et mõlemad, nii MDNK, kui KMNK annavad kõikide argumentide korral samad väärtused, järelikult sobib funktsiooni lihtsustatud avaldiseks nii avaldis f(x1,x2,x3)=x1¬x2Vx3 kui ka f(x1,x2,x3)=(x1Vx3)(¬x2Vx3). Kuna ühest avaldisest piisab funktsiooni kirjeldamiseks siis võiks oletada, et saadud avaldised on samaväärsed.

Näide 2. Koostame Karnaugh’ kaardi implikatsioon tehtele:
Tabel 3. IMP tehte tõeväärtuste tabel
x1x2IMP(x1,x2)
001
011
100
111

Implikatsioon.png

Sele 3. Implikatsiooni Karnaugh' kaart

MDNK: sinine piirkond konstantne x1=0, pruun piirkond konstantne x2=1, f(x1, x2)=NOT(x1) V x2

MKNK: 1x1 piirkond, kus f(x1, x2)= NOT(x1) V x2

Nagu näha annavad MDNK ja MKNK täpselt samasuguse tulemuse, mis ongi implikatsiooni definitsioon ja ühtlasi lühim kuju IMP(x1, x2)= NOT(x1) OR x2

Tagasi Karnaugh' kaardile

Väino Liimann