KARNAUGH' KAARDID (0)

KARNAUGH '   KAARDID
Karnaugh'  kaart  on  funktsiooni  tõeväärtustabeli  sihipärane
topoloogiline ümberpaigutus   tasandil  või  ruumis.
Tõeväärtustabeli igale reale vastab kaardil  üks ruut.
Karnaugh'   kaartide  topoloogia
2 muutuja  Karnaugh' kaart  on tabel mõõtmetega    2  2   (või  1  4)   ruutu ;
3muutuja  Karnaugh' kaart  on tabel mõõtmetega    2  4  =  8  ruutu ;
4muutuja  Karnaugh' kaart  on tabel mõõtmetega    4  4  =  16   ruutu ;
     TTÜ 
või
6 - muutuja
Karnaugh'  kaart
2 - muutuja
3 - muutuja
4 - muutuja
Karnaugh'  kaartide  põhiomadused
Karnaugh'  kaart
Karnaugh'  kaart
Karnaugh'  kaart
Karnaugh'  kaardil on  2  põhiomadust.
1. põhiomadus
2  3 ja   4muutuja  kaardid  on   2mõõtmelised  ehk  tasandilised.
5 ja   6muutuja  kaardid  on   3mõõtmelised  ehk   ruumilised .
kaardi iga ruudu  naaberruutude arv  võrdub  kaardi muutujate arvuga
5muutuja  Karnaugh' kaart  on tabel mõõtmetega    2  4  4  =  32   ruutu ;
Seega:
Arvutitehnika 
2muutuja  Karnaugh' kaardi igal ruudul on  2  naaberruutu ;
3muutuja  Karnaugh' kaardi igal ruudul on  3  naaberruutu ;
4muutuja  Karnaugh' kaardi igal ruudul on  4  naaberruutu ;
5muutuja  Karnaugh' kaardi igal ruudul on  5  naaberruutu ;
6muutuja  Karnaugh' kaardi igal ruudul on  6  naaberruutu ;
6muutuja kaart  on  suurim Karnaugh' kaart.    
5 - muutuja
Karnaugh'  kaart
7muutuja kaarti ei eksisteeri, sest 3 mõõtmelise ruumi võimalused on
6muutuja kaardiga ammendatud  ehk  ruudu 7ndat naabrit pole ruumis enam
   Instituut
6muutuja  Karnaugh' kaart  on tabel mõõtmetega   4  4  4  =  64   ruutu ;
kuhugi paigutada.
Argumentvektorite  paiknemine  kaardi  ruutudes
Kaardi  igale ruudule  vastab   loogikafunktsiooni  üks argumentvektor  
x  x
x  x
4   5
4   5
x  x
00
01
11
10
00
01
11
10
2   3
x  x
2   3
(milleks on mingi  njärguline  2ndvektor).
0
1
3
2
16
17
19
18
00
00
00000
00001
00011
00010
10000
10001
10011
10010
2. põhiomadus
4
5
7
6
20
21
23
22
01
01
suvalise kahe naaberruudu  argumentvektorid  on  teineteise  lähiskoodid
00100
00101
00111
00110
10100
10101
10111
10110
12
13
15
14
28
29
31
30
11
11
( meenutame et,  lähiskoodid  on kahendvektorid, mis erinevad teineteises
01100
01101
01111
01110
11100
11101
11111
11110
  ainult  ühes  oma kahendjärgus )
8
9
11
10
24
25
27
26
10
10
01000
01001
01011
01010
11000
11001
11011
11010
  x  x
 3      4
1
x    = 0
1
x    = 1
  x  x
  x  x
00
01
11
10
 2     3
 1     2
  x
00
01
11
10
1
0
1
3
2
x    = 0
00
1
5-muutuja  Karnaugh'  kaart
0
1
3
2
0000
0001
0011
0010
x    = 1
  0
1
( kolmemõõtmeline ! )
000
001
011
010
4
5
7
6
01
4
5
7
6
0100
0101
0111
0110
x  x
  1
5   6 00
01
11
10
00
01
11
10
00
01
11
10
00
01
11
10
100
101
111
110
x  x
3   4
11 12
13
15
14
     TTÜ 
0
1
3
2
16
17
19
18
48
49
51
50
32
33
35
34
1100
1101
1111
1110
00 000000 000001 000011 000010
010000 010001
110000
100000  100001
3-muutuja  Karnaugh'  kaart
8
9
11
10
01 4
5
7
6
20
21
23
22
52
53
55
54
36
37
39
38
10
000100 000101
1000
1001
1011
1010
11
12
13
15
14
28
29
31
30
60
61
63
62
44
45
47
46
4-muutuja  Karnaugh' kaart
001111 001110
011111 011110
111111 111110
101111 101110
10 8
9
11
10
24
25
27
26
56
57
59
58
40
41
43
42
001000
011000
111000
101000
10
/¯¯  näide:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
x  x   = 00
x  x   = 01
x  x   = 11
x  x   =
1     2
1     2
1     2
1     2
3-muutuja loogikafunktsiooni       f ( x1 x2 x3 )  =   x1 x
¯2      w      x3  
x  x
1   2
tõeväärtustabel :
     
 0 0
    
 0 1
Arvutitehnika 
   x
 1 1
6-muutuja  Karnaugh' kaart
1 x2 x3               x1 x
¯2   w  x3   
 1 0
———————————————————  ...
( kolmemõõtmeline )
 paikneb 3-muutuja Karnaugh'  kaardil:
     0  0  0                        0  
Kontuurid
     0  0  1                        1
  x  x
 2     300
01
11
10
     0  1  0                        0
  x 1
Karnaugh' kaardil valitakse välja  kindlate mõõtmetega ruutude gruppe, mida
     0  1  1                        1
  0
0
1
1
0
nimetatakse  kontuurideks.
     1  0  0                        1
Tasandilise  kaardi  kontuurid  on  ristkülikud   lubatud  küljepikkustega
     1  0  1                        1
  1
1
1
1
0
 2täisarv      ehk       2m 2n    ruutu.
     1  1  0                        0
     1  1  1                        1
2-mõõtmelise  Karnaugh' kaardi  kontuuride võimalikud suurused  on järgnevad :
   Instituut
|____________________________________________________________________________________ |
 
1  1   ruutu
1  2   ruutu
1  4   ruutu
  x  x
 3      4
  x  x
  x  x
00
01
11
10
2  2   ruutu
 2     3
 1     2
  x
00
01
11
10
2  4   ruutu
1
00
4  4   ruutu
  0
001
011
     ——————
      2m  2n
01
101
111
  1
<
3-mõõtmelise  Karnaugh' kaardi  kontuuride  võimalikud suurused :
11
1101
<
<
 
1  1  1     ruutu
10
1  1 2
1000
1001
1011
1010
     ruutu
<
1  1 4     ruutu
1  2  1
<
     ruutu
<
1  2  2    ruutu
1  2  4    ruutu
suvalised kontuurid  ja  nendele vastavad  intervallid
.  .  .  .  .  .
4  4  4    ruutu
Mistahes kontuuri koosseisu kuuluvatele ruutudele vastavad  
     TTÜ 
argumentvektorid  moodustavad  intervalli.
/¯¯¯¯¯   !    tüüpiline viga:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
kontuuri küljepikkus  pole kunagi  3 ruutu !
(s.t. kaardil ei tohi valida sellist kontuuri, mille mistahes küljepikkus on 3)
 x  x
 3      4
  x  x
  x  x
00
01
11
10
 2     3
 1     2
  x
00
01
11
10
1
00
1
1
1
  0
6 - muutuja
Karnaugh'  kaart
01
1
1
1
1
0
0
0
Arvutitehnika 
  1
Seega pole Karnaugh' kaardi kontuurideks ruutudegrupid küljepikkusega  3
11
1
1
1
1
ruutu.  Ülejäänud võimalikud küljepikkused  (mis mahuvad kaardile)  on  
kontuuridel lubatud.  Kontuuri küljepikkus   23 = 
1
1
 8  ruutu   ei mahu enam
10
füüsiliselt  isegi suurimale  Karnaugh' kaardile.  
valestivalitud "kontuurid"
Seega osutuvad kontuuride võimalikeks küljepikkusteks  1    2   ja   4   ruutu.
|____________________________________________________________________________________ |
Kontuuride  seos  intervallidega
Karnaugh'  kaardi  piirkonnad
n-muutuja kaardil on   2n  omavahel kattuvat  piirkonda  (ruutude gruppi): 
Meenutame, et  2ndvektorite  teatud  kindlate  tunnustega  hulka  nimetatakse  
intervalliks.
x1 = 0
    x1 = 1         x2 = 0         x2 = 1     . . . . .    xn = 0        xn = 1
   Instituut
Karnaugh' kaardi iga kontuur   vastab   kahendvektorite mingile  intervallile:
 
Kaardi piirkondi võib tähistada vastavalt:
  x
¯1             x1              x
¯2               x2   . . . . . . . . . .   x
¯n            xn 
Piirkondade suurus
Iga piirkond  on  täpselt  "pool kaarti"  suur  ehk  tema koosseisu kuuluvad
Leida  Karnaugh' kaardiga    MDNK    MKNK    4-muutuja funktsioonile:
(suvalise kaardi korral)  täpselt pooled  kaardi kõikidest ruutudest.
 f ( x
Piirkonnad kattuvad omavahel.
1 . . . x4 )   =    ( 1,  4,  5,  9,  11,  12, 13, 15 ) 0   ( 3, 14 ) —
Järgmisel joonisel  on näidatud  3-muutuja kaardi  kõik  6 piirkonda (igaühe
suurus  on  4 ruutu)   ja  
4-muutuja kaardi  kõik  8 piirkonda  (iga  piirkond  on  8-ruuduline):
x  x
x
x
3    4
x
x
4
x
4
x  x
1    2
00
01
11
10
3
x
3
4
3
  x  x
 3      4
  x  x
  x  x
00
01
11
10
00
0 1 3 2
 2     3
 1     2
  x
00
01
11
10
1
x
00
2
x
01
4 5 7 6
     TTÜ 
  0
1
x1
01
x
11 12 13 15 14
  1
1
x2
11
10
8 9 11 10
x
x
x
1
2
2
10
x2
x  x
3    4
x
x
x  x
1    2
00
01
11
10
3
3
Karnaugh'  kaardi
piirkonnad
00
1
0
1
Loogikafunktsioonide   minimeerimine
01
0
0
1
1
Arvutitehnika 
Loogikafunktsiooni  minimeerimine  on tema esitamine minimaalse
keerukusega normaalkujul — Minimaalsel Disjunktiivsel NormaalKujul
11
0
0
0
(MDNK)  või  Minimaalsel Konjunktiivsel NormaalKujul  (MKNK).
10
1
0
0
1
Loogikafunktsioone võib minimeerida nende avaldise teisendamisega
loogikaalgebra põhiseoseid   ja    loogikatehete asendusseoseid   kasutades.
MDNK  ja  MKNK  leidmised on teineteisest sõltumatud   ja nad võib leida  
Loogikafunktsiooni  minimeerimine  Karnaugh' kaardi  abil
ükskõik kumbas  järjekorras.
Loogikafunktsiooni minimeerimine on Karnaugh' kaardi põhiline
Leiame  esimesena  MDNK
rakendusvaldkond.
!  DNK  saadakse  alati  loogikafunktsiooni  1de   piirkonnast   !
Karnaugh' kaart on kõige eelistatum minimeerimisvahend, kuid ta on
   Instituut
rakendatav ainult kuni 6-muutuja loogikafunktsioonide korral.
Kontuuride valimise reeglid
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
1.   Katame  kaardil asuvad   1de ruudud   suurimate  kontuuridega, kasutades
x   x
3   4
x   x
x  x
00
01
11
10
3   4
 1   2
x  x
00
01
11
10
seejuures  võimalikult vähe  kontuure. ( 0-lle  ei tohi valida  1-de kontuuridesse )
 1   2
00
1
0
—
1
00
1
0
1
1
2.   Määramatuse ruute tohib seejuures kontuuridega katta , kuid  ei pea  katma .
x x
1
3
     Määramatusi  katame kontuuridega ainult siis,  kui  see  aitab  kasvatada
01
0
0
1
1
01
0
0
1
1
     veelgi suuremaks  mõnda  niikuinii vajalikku  kontuuri.
11
0
0
0
—
11
0
0
0
0
3.  Kontuurid   tohivad kattuda  —  peavad olema suurimad võimalikud.
10
1
0
0
1
10
1
0
0
1
parim  kontuuridevalik  selle funktsiooni   1-de piirkonna jaoks:
x  x
x x
2
4
3    4
1-de  kontuuridele vastavad
osaliselt määratud funktsiooni
x  x
1    2
00
01
11
10
elementaarkonjunktsioonid
MDNK-esituseks valitud
00
1
0
1
täielikult määratud funktsioon
MDNK :
01
0
0
1
1
     TTÜ 
 f ( x1 x2  x3 x4 )    =    x
¯1 x3     w   x
¯2 x
¯4
11
0
0
0
Osaliselt määratud  funktsioon  on sellega  "lõpuni määratud"
10
1
0
0
1
kontuuride äravalimine toob endaga koheselt kaasa  ka senise  osaliselt
määratud  loogikafunktsiooni  lõpunimääramise   täielikult määratud  
MDNK  väljakirjutamiseks  analüüsime ühekaupa   igat  valitud  kontuuri,
funktsiooniks  (ehk  määramatuspiirkond  saab ärajaotatud  1de  ja  0de  
( suvalises järjekorras, üks kontuur korraga )
x
piirkonna vahel).  
4
pole
x
x
=  1
=  1
konstantne
3
3
kui oleks valitud  1de katmiseks 4ruudulise asemel  ehk  2ruuduline kontuur ?
x   x
x   x
Arvutitehnika 
3   4
3   4
x  x
00
01
11
10
x  x
00
01
11
10
x   x
 1   2
 1   2
3   4
x   x
x  x
00
01
11
10
3   4
 1   2
x  x
00
01
11
10
 1   2
00
1
0
—
1
00
1
0
—
1
00
1
0
—
1
x
00
1
0
0
1
=  0
x x
1
1
3
01
01
0
0
1
1
0
0
1
1
01
0
0
1
1
01
0
0
1
1
x
11
11
0
0
0
—
0
0
0
—
2
x =  0
pole
1
11
0
0
0
—
11
0
0
0
0
konstantne
10
10
1
0
0
1
1
0
0
1
10
1
0
0
1
10
1
0
0
1
konstantsed muutujad
1-de  kontuurile vastav
vaadeldavas kontuuris
elementaarkonjunktsioon
ebaoptimaalsem kontuuridevalik
. . . selle kontuurivalikuga oleks
   Instituut
1de  katmiseks
esindajaks valitud   selline
täielikult määratud funktsioon
 f ( x1 x2  x3 x4 )    =    x
¯1 x2 x3     w   x
¯2 x
¯4
x  x
3    4
x  x
1    2
00
01
11
10
väiksemas kontuuris on  rohkem konstantseid muutujaid, mis põhjustab
00
1
0
1
enamate liikmetega  (ehk keerukamat)  loogikaavaldist/ normaalkuju .
01
0
0
1
1
 . . .  järelikult tasub valida  SUURIMAD  võimalikud kontuurid,  misjuhul
tuleb avaldisse VÄHIM arv  algterme    x
11
0
0
0
i    ehk  saame  minimaalseima
normaalkuju.
10
1
0
0
1
MDNK leitud ja analüüsitud  —  edasi leiame samale funtsioonile  MKNK
!  KNK  saadakse  alati  loogikafunktsiooni  0de  piirkonnast  !
teine  võimalik / sobiv
kontuuridevalik
MKNK leidmisel teeme kõik samad toimingud , kuid  duaalselt vastupidi :
katame suurimate võimalike kontuuridega  0-de piirkonna  ehk  0-de ruudud:
     TTÜ 
x  x
x  x
3    4
3    4
x  x
x  x
1    2
00
01
11
10
1    2
00
01
11
10
00
1
0
1
00
1
0
1
01
0
0
1
1
01
0
0
1
1
11
0
0
0
11
0
0
0
10
1
0
0
1
10
1
0
0
1
kolmas  võimalik / sobiv
Arvutitehnika 
x  x
3    4
x  x
kontuuridevalik
1    2
00
01
11
10
ükski  3st  sobivast kontuuridevalikust  pole ülejäänud kahe suhtes parem /
00
1
0
1
pole eelistatud,  kuna kõik nad kasutavad   3 tk  4-ruudulisi  kontuure  ehk  
kõik nad annavad  sama keerukusega  KNK
01
0
0
1
1
Kirjutame  MKNK välja  esimesest  kontuuridevalikust:
11
0
0
0
10
1
0
0
1
esimesena  märgatav
   Instituut
kontuuridevalik
x  x
x  x
3    4
3    4
x  x
x  x
1    2
00
01
11
10
1    2
00
01
11
10
00
1
0
1
00
1
0
1
01
0
0
1
1
01
0
0
1
1
11
0
0
0
11
0
0
0
10
1
0
0
1
10
1
0
0
1
esimesena  märgatav
kontuuridevalik
 f D (0011)    =   1
MKNK   keerukus on kontuuride arvust  ja  nende  suurusest   tulenevalt :
 f D (1110)    =   0
 f ( x
     TTÜ 
1 x2  x3 x4 )    =   ( x      w   x ) ( x      w   x ) ( x      w   x )
 f K    =   ( x
¯2    w   x3 ) ( x3      w   x
¯4 ) ( x
¯1     w   x
¯4 )
MKNK:
milleks arvutub  leitud   MKNK  funktsiooni  määramatuspiirkonnas  ?
 f ( x1 x2  x3 x4 )    =   ( x
¯2    w   x3 ) ( x3      w   x
¯4 ) ( x
¯1     w   x
¯4 )
 f K (0011)    =   ?
 f K (1110)    =   ?
tähistame leitud  MDNK  ja  MKNK:
 f 
x  x
K    =   ( x
¯2    w   x3 ) ( x3      w   x
¯4 ) ( x
¯1     w   x
¯4 )
3    4
x  x
1    2
00
01
11
10
Arvutitehnika 
 f D    =    x
¯1 x3     w   x
¯2 x
¯4
00
1
0
1
vaatleme , milleks arvutuvad  leitud normaalkujud   määramatuspiirkonnas.
01
0
0
1
1
Milleks arvutub  leitud  MDNK  funktsiooni  määramatuspiirkonnas  ?
11
0
0
0
 f D (0011)    =   ?
 f
10
1
0
0
1
 D (1110)    =   ?
MKNK  leidmise
kontuuridevalik
 f
   Instituut
 K (0011)    =   1
 f K (1110)    =   1
?  kas leitud  MDNK  ja  MKNK  on teineteisega  loogiliselt võrdsed  ?
x1 x2 x3
 f ( x1 x2  x3 )
?    f 
0  0  0
1
D     =    f K    ?
0  0  1
0
meenutame:  
0  1  0
1
loogikaavaldised on  võrdsed  kui  nende tõeväärtustabelid  on samasugused.
0  1  1
1
1  0  0
0
Osaliselt määratud funktsiooni esindajateks valitud  MDNK  ja  MKNK   
1  0  1
1
võrdsus oleneb sellest, milleks  nad arvutuvad  määramatuspiirkonnas.
1  1  0
1
1  1  1
1
Siin leitud  mõlemad normaalkujud    f D     f K    ei ole  teineteisega võrdsed:
 
    f D          f K              sest
kanname  tõeväärtustabeli  3-muutuja  kaardile:
 f D (1110)         f K (1110)
x  x
2    3
     TTÜ x10001 1110
0
f D (1110)    =   0
f 
1
K (1110)    =   1
x  x
3    4
x  x
0011 korral
1    2
00
01
11
10
x  x
väärtustuvad
2    3
x1
00
01
11
10
00
1
0
1
MDNK  ja  MKNK
samamoodi (1)
0
1
0
1
1
01
0
0
1
1
Arvutitehnika 
1
0
1
1
1
11
0
0
0
1110 korral
10
1
0
0
1
väärtustuvad
MDNK  ja  MKNK
0-de  ja  1-de  kontuurid
erinevalt
x  x
2    3
samal kaardil
x1
00
01
11
10
|______________________________________________________________________________|
0
1
0
1
1
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
1
0
1
1
1
   Instituut
Leia  Karnaugh' kaardi  abil   MDNK  samale funktsioonile, mille
TDNK  lihtsustasime  eelpool näites  MDNK-ks
MDNK :
 f ( x
x  x
x  x
1 x2 x3)      =      x2      w    x1 x3       w     x
¯1 x
¯3
4    5
4    5
x  x
2    3
00
01
11
10
x  x
2    3
00
01
11
10
MDNK-ks   saime sama tulemuse  nagu enne  TDNK  teisendamisel
00
00
—  kas Karnaugh' kaardilt  väljakirjutatud  DNK- avaldist võib olla võimalik
lihtsustada käsitsi edasi veelgi lihtsamaks  (loogikaalgebra põhiseoste abil )?
01
01
11
11
—  milline oleks olnud kaardilt loetav DNK- avaldis , kui oleksime mingi
kontuuri valinud väiksema  ?
10
10
x  x
2    3
x =  0
x =  1
x
1
1
1
00
01
11
10
x =  0
0
1
0
1
1
1
x =  1
1
1
0
1
1
1
x  x
x  x
     TTÜ 
4    5
4    5
x  x
2    3
00
01
11
10
x  x
2    3
00
01
11
10
00
1
0
1
00
0
0
 f ( x1 x2 x3)      =      x2      w    x1 x3       w     x
¯1 x
¯2 x
¯3
01
0
0
1
1
01
0
0
0
0
sellises avaldises  leidub   neeldumine  ,   mis ikkagi kaotab liiase     x
¯2 
|______________________________________________________________________________|
11
0
0
0
11
0
0
0
1
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
10
1
0
0
1
10
1
0
0
x =  0
x
1
1 =  1
Arvutitehnika 
x =  0
1
Leida  Karnaugh' kaardiga    MDNK    MKNK   5-muutuja funktsioonile:
x =  1
1
  f ( x1 . . . x5 )   =    ( 0 , 2 , 6 , 7 , 8 , 10 , 24 , 30 ) 1    ( 3, 14 , 16 , 18 , 26 ) —
MDNK :
kanname  tõeväärtustabeli  5-muutuja  kaardile:
   Instituut
x  x
x  x
x  x
x  x
4    5
4    5
4    5
4    5
x  x
x  x
2    3
00
01
11
10
x  x
2    3
00
01
11
10
x  x
2    3
00
01
11
10
2    3
00
01
11
10
00
1
1
00
00
1
1
00
01
1
1
01
01
1
1
01
11
11
1
11
11
1
10
1
1
10
1
10
1
1
10
1
x =  0
x =  1
x =  0
x =  1
1
1
1
1
x =  0
x =  0
1
1
x =  1
x =  1
1
1
     TTÜ 
MDNK :
MKNK :
 f ( x1 . . . . x5 )    =    x
¯3 x
¯5      w    x
¯1 x
¯2 x4      w    x2 x4 x
¯5
 f ( x1 . . . x5 )    =   ( x
¯3    w  x4 ) ( x
¯2    w  x
¯5 ) ( x4    w  x
¯5 ) ( x
¯1    w   x2 )
see on ainus  MDNK  sellel  (osaliselt määratud)  funktsioonil
siin leidub ka  teine, sama keerukusega  MKNK
MKNK :
|______________________________________________________________________________|
x  x
x  x
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
4    5
4    5
x  x
2    3
00
01
11
10
x  x
2    3
00
01
11
10
00
0
00
0
0
Arvutitehnika 
01
0
0
01
0
0
0
0
Kontrollida  Karnaugh' kaardiga   ühe varasema teisendusülesande  
tulemuseks saadud  DNK- avaldise  minimaalsust:
11
0
0
0
11
0
0
0
 f ( x

 
1 . . . x4 )    =
  x1 x
¯2 x
¯4      w    x1 x
¯2 x3     w   x3 x4   w   x2 x4      w     x
¯1 x4
10
0
0
10
0
0
Kas see  DNK  on  MDNK ?
x =  0
x
1
1 =  1
x =  0
1
x =  1
   Instituut
1
kanname 4-muutuja kaardile need 1-de kontuurid, millest tuleneks antud DNK  
 x

 
1 x
¯2 x
¯4      w    x1 x
¯2 x3     w   x3 x4   w   x2 x4      w     x
¯1 x4
elementaarkonjunktsioon     x
x  x
1 x
¯2 x
¯4    tuleneb   1-de  intervallist    1  0  —  0
3    4
x  x
1    2
00
01
11
10
elementaarkonjunktsioon     x1 x
¯2 x3    tuleneb   1-de  intervallist    1  0  1  — 
00
elementaarkonjunktsioon       x
1
1
3 x4       tuleneb   1-de  intervallist    —  —  1  1
elementaarkonjunktsioon       x2 x4       tuleneb   1-de  intervallist    —  1  —  1
01
1
1
elementaarkonjunktsioon       x
¯1 x4       tuleneb   1-de  intervallist    0  —  —  1
11
1
1
x  x
3    4
x  x
1    2
00
01
11
10
10
1
1
1
00
DNK   liikmetele vastavad
01
5  kontuuri
11
liiane  kontuur   vastab  DNK liikmele    x1 x
¯2 x3   
x

 
     TTÜ 
1 x
¯2 x
¯4      w    x1 x
¯2 x3     w   x3 x4   w   x2 x4      w     x
¯1 x4
10
Selle liikme ärajätmisel  DNK-st  jääb avaldise tõeväärtustabel muutumatuks.
Analüüsitava  DNK-avaldise   MDNK  on seega:
x  x
3    4
x  x
x

 
1 x
¯2 x
¯4      w   x3 x4   w   x2 x4      w     x
¯1 x4
1    2
00
01
11
10
mis põhjustab   punase kontuuri  liiasust  ?
00
1
1
Kaardi kontuuridest on näha, et liiasus sisaldub juba liiase avaldise  kolmes
01
1
1
esimeses liikmes :
11
 x
1
1
1 x
¯2 x
¯4      w    x1 x
¯2 x3     w    x3 x4      =      x1 x
¯2 x
¯4       w    x3 x4 
Arvutitehnika 
10
1
1
1
?   kas leidub ka avaldise teisendus , mis kaotaks liiase liikme ?
rakendades   kleepimisseadust      x   =   x y   w   x y
¯       teisendame avaldise
analüüsitava DNK  tõeväärtustabel  kaardil
korraks keerulisemaks, lisades liiasele liikmele  seal puuduva muutuja   x4  
mitme kontuuriga õnnestub katta kõik 1-de ruudud optimaalseimal viisil ?
Siis tekkivad avaldises  neeldumised  kujul     x   w   x y   =   x  
x1 x
¯2 x
¯4       w    x1 x
¯2 x3      w    x3 x4      = 
4  kontuuriga :
 =      x1 x
¯2 x
¯4       w    x1 x
¯2 x3 x4       w    x1 x
¯2 x3 x
¯4     w     x3 x4      = 
 =      x1 x
¯2 x
¯4       w    x1 x
¯2 x3 x4       w    x1 x
¯2 x3 x
¯4     w     x3 x4      = 
   Instituut
 =      x1 x
¯2 x
¯4                  w                  x1 x
¯2 x3 x
¯4     w     x3 x4      = 
 =      x1 x
¯2 x
¯4       w     x3 x4
 kleepimisjärgselt toimus kaks neeldumist  vastavalt  neeldumisseadusele 
x  x
5   6 00
01
11
10
00
01
11
10
00
01
11
10
00
01
11
10
x  x
3   4
1
1
1
1
1
1
—
—
sama võib esineda kodutöö  ülesandes,  kus MKNK sulud korrutatakse lahti :
00
ka kodutöös võib osutuda selline kleepimine vajalikuks, kui  
01
—
—
MDNK  =   MKNK ,    kuid   MKNK   lahtikorrutamisel  ei tekki   MDNK
11
1
1
—
1
kodutöös:
10
1
1
kui  MDNK  =   MKNK    siis   (     )(     )(     )   =    . . . . . . . . .   =   MDNK
x  x  =  00
x  x    =  01
x  x   =  11
    =  10
x  x
 1    2
 1    2
 1    2
 1    2
x  x
kui  MDNK     MKNK    siis   (     )(     )(     )   =    . . . . . . . . .   =   DNK
 1    2
 0 0
|______________________________________________________________________________|
 0 1
 1 1
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
 1 0
MDNK :
     TTÜ 
 f ( x1 . . . . x6 )    =    x
¯3 x
¯4 x
¯5      w    x1 x2 x3 x5     w    x1 x3 x4 x5 x
¯6
Leida  Karnaugh' kaardiga    MDNK       6-muutuja funktsioonile:
|______________________________________________________________________________|
  f ( x1 . . . x6 )   =   
=     ( 0
 , 1 , 16 , 17 , 46 , 48 , 49 , 58 , 59 , 62 , 63   1   ( 32, 33 , 36 , 39 , 44 ) —
  kanname  tõeväärtustabeli  6-muutuja  kaardile:
x  x
5   6 00
01
11
10
00
01
11
10
00
01
11
10
00
01
11
10
x  x
Arvutitehnika 
3   4
1
1
1
1
1
1
—
—
00
01
—
—
11
1
1
—
1
10
1
1
x  x  =  00
x  x    =  01
x  x   =  11
    =  10
x  x
 1    2
 1    2
 1    2
 1    2
 0 0
 0 1
 1 1
 1 0
   Instituut
x  x
 1    2