KARNAUGH' KAARDID (0)

/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
1.   Katame  kaardil asuvad   1de ruudud   suurimate  kontuuridega, kasutades
seejuures  võimalikult vähe  kontuure. ( 0-lle  ei tohi valida  1-de kontuuridesse )
2.   Määramatuse ruute tohib seejuures kontuuridega katta , kuid  ei pea  katma .
     Määramatusi  katame kontuuridega ainult siis,  kui  see  aitab  kasvatada
Leida   Karnaugh ' kaardiga    MDNK    MKNK    4- muutuja funktsioonile:
     veelgi suuremaks  mõnda  niikuinii vajalikku  kontuuri.
 f ( x1 . . . x4 )   =    ( 1,  4,  5,  9,  11,  12, 13, 15 ) 0   ( 3, 14 ) —
3.  Kontuurid   tohivad kattuda  —  peavad olema suurimad võimalikud.
parim  kontuuridevalik  selle funktsiooni   1-de piirkonna jaoks:
x  x
3    4
x  x
x  x
3    4
1    2
00
01
11
10
x  x
1    2
00
01
11
10
00
1
0
1
00
0 1 3 2
01
0
0
1
1
     TTÜ 
01
4 5 7 6
11
0
0
0
11 12 13 15 14
10
1
0
0
1
10
8 9 11 10
MDNK  väljakirjutamiseks  analüüsime ühekaupa   igat  valitud  kontuuri,
x  x
( suvalises järjekorras, üks kontuur korraga )
3    4
x  x
1    2
00
01
11
10
x4
pole
x
x
=  1
=  1
00
1
0
1
konstantne
3
3
x   x
x   x
Arvutitehnika 
3   4
3   4
x  x
00
01
11
10
x  x
00
01
11
10
 1   2
 1   2
01
0
0
1
1
00
1
0
—
1
00
1
0
—
1
x =  0
x x
11
0
0
0
1
1
3
01
01
0
0
1
1
0
0
1
1
10
1
0
0
1
x
11
11
0
0
0
—
0
0
0
—
2
x =  0
pole
1
konstantne
MDNK  ja  MKNK  leidmised on teineteisest sõltumatud   ja nad võib leida  
10
10
1
0
0
1
1
0
0
1
ükskõik kumbas  järjekorras.
Leiame  esimesena  MDNK
konstantsed muutujad
1-de  kontuurile vastav
!  DNK  saadakse  alati   loogikafunktsiooni  1de   piirkonnast   !
vaadeldavas kontuuris
elementaarkonjunktsioon
   Instituut
Kontuuride valimise reeglid
x   x
3   4
x   x
 f
x  x
00
01
11
10
3   4
 ( x1 x2  x3 x4 )    =    x
¯1 x2 x3     w   x
¯2 x
¯4
 1   2
x  x
00
01
11
10
 1   2
00
1
0
—
1
00
1
0
1
1
x x
väiksemas kontuuris on  rohkem konstantseid muutujaid, mis põhjustab
1
3
01
0
0
1
1
01
0
0
1
1
enamate liikmetega  (ehk keerukamat)  loogikaavaldist/ normaalkuju .
11
0
0
0
—
 . . .  järelikult tasub valida  SUURIMAD  võimalikud kontuurid,  misjuhul
11
0
0
0
0
tuleb avaldisse VÄHIM arv  algterme    xi    ehk  saame  minimaalseima
10
1
0
0
1
10
1
0
0
1
normaalkuju.
MDNK leitud ja analüüsitud  —  edasi leiame samale funtsioonile  MKNK
x x
1-de  kontuuridele vastavad
2
4
osaliselt määratud funktsiooni
!  KNK  saadakse  alati  loogikafunktsiooni  0de  piirkonnast  !
elementaarkonjunktsioonid
MDNK-esituseks valitud
täielikult määratud funktsioon
MKNK leidmisel teeme kõik samad toimingud, kuid  duaalselt vastupidi :
MDNK :
katame suurimate võimalike kontuuridega  0-de piirkonna  ehk  0-de ruudud:
     TTÜ 
 f ( x
x  x
1 x2  x3 x4 )    =    x
¯1 x3     w   x
¯2 x
¯4
3    4
x  x
1    2
00
01
11
10
Osaliselt määratud  funktsioon  on sellega  "lõpuni määratud"
00
1
0
1
kontuuride äravalimine toob endaga koheselt kaasa  ka senise  osaliselt
01
0
0
1
1
määratud  loogikafunktsiooni  lõpunimääramise   täielikult määratud  
funktsiooniks  (ehk  määramatuspiirkond  saab ärajaotatud  1de  ja  0de  
11
0
0
0
piirkonna vahel).  
10
1
0
0
1
kui oleks valitud  1de katmiseks 4ruudulise asemel  ehk  2ruuduline kontuur ?
Arvutitehnika 
x   x
3   4
x   x
x  x
00
01
11
10
3   4
x  x
 1   2
x  x
00
01
11
10
3    4
 1   2
x  x
1    2
00
01
11
10
00
1
0
—
1
00
1
0
0
1
00
1
0
1
01
0
0
1
1
01
0
0
1
1
01
0
0
1
1
11
0
0
0
—
11
0
0
0
0
11
0
0
0
10
1
0
0
1
10
1
0
0
1
10
1
0
0
1
ebaoptimaalsem kontuuridevalik
. . . selle kontuurivalikuga oleks
esimesena  märgatav
   Instituut
1de  katmiseks
esindajaks valitud   selline
kontuuridevalik
täielikult määratud funktsioon
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
teine  võimalik / sobiv
kontuuridevalik
kontuuridevalik
MKNK   keerukus on kontuuride arvust  ja  nende  suurusest   tulenevalt :
     TTÜ 
x  x
 f ( x1 x2  x3 x4 )    =   ( x      w   x ) ( x      w   x ) ( x      w   x )
3    4
x  x
1    2
00
01
11
10
MKNK:
00
1
0
1
 f ( x1 x2  x3 x4 )    =   ( x
¯2    w   x3 ) ( x3      w   x
¯4 ) ( x
¯1     w   x
¯4 )
01
0
0
1
1
11
0
0
0
tähistame leitud  MDNK  ja  MKNK:
10
1
0
0
1
 f K    =   ( x
¯2    w   x3 ) ( x3      w   x
¯4 ) ( x
¯1     w   x
¯4 )
kolmas  võimalik / sobiv
Arvutitehnika 
 f 
kontuuridevalik
D    =    x
¯1 x3     w   x
¯2 x
¯4
ükski  3st  sobivast kontuuridevalikust  pole ülejäänud kahe suhtes parem /
vaatleme , milleks arvutuvad  leitud normaalkujud   määramatuspiirkonnas.
pole eelistatud,  kuna kõik nad kasutavad   3 tk  4-ruudulisi  kontuure  ehk  
Milleks arvutub  leitud  MDNK  funktsiooni  määramatuspiirkonnas  ?
kõik nad annavad  sama keerukusega  KNK
Kirjutame  MKNK välja  esimesest  kontuuridevalikust:
 f D (0011)    =   ?
 f D (1110)    =   ?
   Instituut
x  x
?  kas leitud  MDNK  ja  MKNK  on teineteisega  loogiliselt võrdsed  ?
3    4
x  x
1    2
00
01
11
10
?    f D     =    f K    ?
00
1
0
1
meenutame:  
loogikaavaldised on  võrdsed  kui  nende tõeväärtustabelid  on samasugused.
01
0
0
1
1
11
0
0
0
Osaliselt määratud funktsiooni esindajateks valitud  MDNK  ja  MKNK   
võrdsus oleneb sellest, milleks  nad arvutuvad  määramatuspiirkonnas.
10
1
0
0
1
Siin leitud  mõlemad normaalkujud    f D     f K    ei ole  teineteisega võrdsed:
 f D (0011)    =   1
 f
 
    f
 
 
D (1110)    =   0
D          f K              sest
 f D (1110)         f K (1110)
     TTÜ 
 f K    =   ( x
¯2    w   x3 ) ( x3      w   x
¯4 ) ( x
¯1     w   x
¯4 )
milleks arvutub  leitud   MKNK  funktsiooni  määramatuspiirkonnas  ?
f D (1110)    =   0
 f
f
 
 K (1110)    =   1
K (0011)    =   ?
 f 
x  x
K (1110)    =   ?
3    4
x  x
0011 korral
1    2
00
01
11
10
väärtustuvad
00
1
0
1
MDNK  ja  MKNK
x  x
samamoodi (1)
3    4
x  x
01
0
0
1
1
1    2
00
01
11
10
Arvutitehnika 
00
1
0
1
11
0
0
0
1110 korral
01
0
0
1
1
10
1
0
0
1
väärtustuvad
MDNK  ja  MKNK
11
0
0
0
0-de  ja  1-de  kontuurid
erinevalt
samal kaardil
10
1
0
0
1
|______________________________________________________________________________|
MKNK  leidmise
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
kontuuridevalik
 f
   Instituut
 K (0011)    =   1
Leia  Karnaugh' kaardi  abil   MDNK  samale funktsioonile, mille
 f K (1110)    =   1
TDNK  lihtsustasime  eelpool näites  MDNK-ks
x1 x2 x3
 f ( x1 x2  x3 )
 f ( x1 x2 x3)      =      x2      w    x1 x3       w     x
¯1 x
¯3
0  0  0
1
0  0  1
0
MDNK-ks   saime sama tulemuse  nagu enne  TDNK  teisendamisel
0  1  0
1
—  kas Karnaugh' kaardilt  väljakirjutatud  DNK- avaldist võib olla võimalik
0  1  1
1
lihtsustada käsitsi edasi veelgi lihtsamaks  ( loogikaalgebra põhiseoste abil )?
1  0  0
0
1  0  1
1
—  milline oleks olnud kaardilt loetav DNK- avaldis , kui oleksime mingi
1  1  0
1
kontuuri valinud väiksema  ?
1  1  1
1
x  x
2    3
x1
00
01
11
10
kanname  tõeväärtustabeli  3-muutuja  kaardile:
0
1
0
1
1
x  x
0
1
1
1
2    3
1
     TTÜ 
x1
00
01
11
10
0
 f ( x1 x2 x3)      =      x2      w    x1 x3       w     x
¯1 x
¯2 x
¯3
1
sellises avaldises  leidub   neeldumine  ,   mis ikkagi kaotab liiase     x
¯2 
x  x
|______________________________________________________________________________|
2    3
x1
00
01
11
10
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
0
1
0
1
1
Arvutitehnika 
1
0
1
1
1
Leida  Karnaugh' kaardiga    MDNK    MKNK   5-muutuja funktsioonile:
  f ( x1 . . . x5 )   =    ( 0 , 2 , 6 , 7 , 8 , 10 , 24 , 30 ) 1    ( 3, 14 , 16 , 18 , 26 ) —
x  x
2    3
x1
00
01
11
10
0
1
0
1
1
kanname  tõeväärtustabeli  5-muutuja  kaardile:
1
0
1
1
1
   Instituut
MDNK :
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
00
00
1
1
00
01
01
01
1
1
01
11
11
11
11
1
10
10
10
1
1
10
1
x =  0
x =  1
x =  0
x =  1
1
1
1
1
x =  0
1
x =  0
x =  1
1
1
x =  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
MDNK :
00
1
0
1
00
0
0
 f ( x1 . . . . x5 )    =    x
¯3 x
¯5      w    x
¯1 x
¯2 x4      w    x2 x4 x
¯5
01
0
0
1
1
01
0
0
0
0
see on ainus  MDNK  sellel  (osaliselt määratud)  funktsioonil
11
0
0
0
11
0
0
0
1
MKNK :
10
1
0
0
1
10
1
0
0
x  x
x  x
4    5
4    5
x  x
2    3
00
01
11
10
x  x
2    3
00
01
11
10
x =  0
x
1
1 =  1
00
0
00
0
0
Arvutitehnika 
x =  0
1
x =  1
1
01
0
0
01
0
0
0
0
11
0
0
0
11
0
0
0
MDNK :
10
0
0
10
0
0
x =  0
x
1
1 =  1
x =  0
1
x =  1
   Instituut
1
x  x
x  x
4    5
4    5
x  x
elementaarkonjunktsioon     x1 x
¯2 x
¯4    tuleneb   1-de  intervallist    1  0  —  0
2    3
00
01
11
10
x  x
2    3
00
01
11
10
elementaarkonjunktsioon     x1 x
¯2 x3    tuleneb   1-de  intervallist    1  0  1  — 
00
1
1
00
elementaarkonjunktsioon       x3 x4       tuleneb   1-de  intervallist    —  —  1  1
01
1
1
01
elementaarkonjunktsioon       x2 x4       tuleneb   1-de  intervallist    —  1  —  1
elementaarkonjunktsioon       x
¯1 x4       tuleneb   1-de  intervallist    0  —  —  1
11
11
1
x  x
3    4
10
1
1
10
1
x  x
1    2
00
01
11
10
x =  0
x =  1
00
1
1
x =  0
01
1
x =  1
1
11
     TTÜ 10
MKNK :
 f ( x1 . . . x5 )    =   ( x
¯3    w  x4 ) ( x
¯2    w  x
¯5 ) ( x4    w  x
¯5 ) ( x
¯1    w   x2 )
x  x
3    4
x  x
1    2
00
01
11
10
siin leidub ka  teine, sama keerukusega  MKNK
00
1
1
|______________________________________________________________________________|
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
01
1
1
11
1
1
Arvutitehnika 
10
1
1
1
Kontrollida  Karnaugh' kaardiga   ühe varasema teisendusülesande  
tulemuseks saadud  DNK- avaldise  minimaalsust:
analüüsitava DNK   tõeväärtustabel  kaardil
 f ( x

 
1 . . . x4 )    =
  x1 x
¯2 x
¯4      w    x1 x
¯2 x3     w   x3 x4   w   x2 x4      w     x
¯1 x4
mitme kontuuriga õnnestub katta kõik 1-de ruudud optimaalseimal viisil ?
Kas see  DNK  on  MDNK ?
   Instituut
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
x  x
 kleepimisjärgselt toimus kaks neeldumist  vastavalt  neeldumisseadusele 
3    4
x  x
1    2
00
01
11
10
sama võib esineda kodutöö  ülesandes,  kus MKNK sulud korrutatakse lahti :
00
1
1
ka kodutöös võib osutuda selline kleepimine vajalikuks, kui  
01
1
1
MDNK  =   MKNK ,    kuid   MKNK   lahtikorrutamisel  ei tekki   MDNK
11
kodutöös:
1
1
kui  MDNK  =   MKNK    siis   (     )(     )(     )   =    . . . . . . . . .   =   MDNK
10
1
1
1
kui  MDNK     MKNK    siis   (     )(     )(     )   =    . . . . . . . . .   =   DNK
DNK   liikmetele vastavad
|______________________________________________________________________________|
5  kontuuri
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
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
Selle liikme ärajätmisel  DNK-st  jääb avaldise tõeväärtustabel muutumatuks.
Leida  Karnaugh' kaardiga    MDNK       6-muutuja funktsioonile:
Analüüsitava  DNK-avaldise   MDNK  on seega:
  f ( x1 . . . x6 )   =   
x

 
1 x
¯2 x
¯4      w   x3 x4   w   x2 x4      w     x
¯1 x4
=
mis põhjustab   punase kontuuri  liiasust  ?
     ( 0 , 1 , 16 , 17 , 46 , 48 , 49 , 58 , 59 , 62 , 63   1   ( 32, 33 , 36 , 39 , 44 ) —
Kaardi kontuuridest on näha, et liiasus sisaldub juba liiase avaldise  kolmes
esimeses liikmes :
  kanname  tõeväärtustabeli  6-muutuja  kaardile:
 x1 x
¯2 x
¯4      w    x1 x
¯2 x3     w    x3 x4      =      x1 x
¯2 x
¯4       w    x3 x4 
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
?   kas leidub ka avaldise teisendus , mis kaotaks liiase liikme ?
1
1
1
1
1
1
—
—
00
rakendades   kleepimisseadust      x   =   x y   w   x y
¯       teisendame avaldise
01
—
—
korraks keerulisemaks, lisades liiasele liikmele  seal puuduva muutuja   x4  
11
1
1
—
1
Siis tekkivad avaldises  neeldumised  kujul     x   w   x y   =   x  
10
1
1
x1 x
¯2 x
¯4       w    x1 x
¯2 x3      w    x3 x4      = 
x  x  =  00
x  x    =  01
x  x   =  11
    =  10
x  x
 1    2
 1    2
 1    2
 1    2
 =      x
 0 0
1 x
¯2 x
¯4       w    x1 x
¯2 x3 x4       w    x1 x
¯2 x3 x
¯4     w     x3 x4      = 
 0 1
 =      x
 1 1
1 x
¯2 x
¯4       w    x1 x
¯2 x3 x4       w    x1 x
¯2 x3 x
¯4     w     x3 x4      = 
 1 0
   Instituut
 =      x
x  x
1 x
¯2 x
¯4                  w                  x1 x
¯2 x3 x
¯4     w     x3 x4      = 
 1    2
 =      x1 x
¯2 x
¯4       w     x3 x4
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
—
—
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
x  x
 1    2
 0 0
 0 1
 1 1
 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
|______________________________________________________________________________|
Arvutitehnika 
   Instituut