Matemaatiline analüüs I kollokvium (0)

HULGATEOORIA PÕHIMÕISTEID
HULK - algmõiste, intuitiivse definitsiooni järgi objektide kogum.
George Cantor (1845-1918) - saksa matemaatik , hulgateooria rajaja.
Hulgad jaotuvad lõpmatuteks ja lõplikeks. Meie kursuses käsitletakse lõplikke hulki, mõnikord ka lõpmatuid loenduvaid hulki.
Hulgateoreetilised operatsioonid

• Hulkade ühend
  

A 

• Hulkade ühisosa (lõige)
  

A , kus I on nn. universaalhulk .

• Hulkade vahe
  

A \

• Hulkade sümmeetriline vahe
  

A 
Hulga A astmehulgaks 2A nimetatakse hulga A kõigi alamhulkade hulka.
Hulgateoreetiliste operatsioonide omadused

• Kommutatiivsusseadused
  

A  B = B  
A  B = B 

• Assotsiatiivsusseadused
  

A  ( B  C ) = ( A  B )  C
A  ( B  C ) = ( A  B )  C

• Distributiivsusseadused
  

A  ( B  C ) = ( A  B )  ( A  C )
A  ( B  C ) = ( A  B )  ( A  C )

• De Morgani seadus seadused
  

• Idempotentsusseadus
  

  A = A  A = A

• Välistatud kolmanda seadused
  

A 
= I
A 
= 

• Topelttäiendi seadus
  

= A

•    =  A  I = A A   = A A  I = I
  
• Neeldumisseadused
  

A  ( A  B ) = A A  (
 B ) = A  B
A  ( A  B ) = A A  (
 B ) = A  B

• Kleepimisseadused
  

( A  B )  (A  ) = A
( A  B )  (A  ) = A

• A \ B = A 
  
• A  B = ( A \ B )  ( B \ A ) = ( A  B ) \ ( A  B )
  

Hulkade võimsus ja Grassmani valemid
Lõpliku hulga A võimsuseks nimetame selle hulga elementide arvu (tähistame  A  ).
Grassmani valemid võimaldavad arvutada hulkade ühendi võimsust:
 A  B  =  A  +  B  -  A  B 
 A  B  C  =  A  +  B  +  C  -  A  B  -  A  C  -  B  C  +  A  B  C 
Ülesandeid

• Kas kehtivad järgmised hulgateoreetilised võrdused:
  

B =

• Leida hulk X, mis rahuldab järgmisi tingimusi:
  

• Tõestada, et järgmised võrdused kehtivad:
  

• Lihtsustada hulgateoreetilised avaldised , esitada Cantori normaalkujul:
  

• Millistel lisatingimustel kehtivad järgmised võrdused?
  

A \ B = B \ A
A  B = B \ A

• Viidi läbi küsitlus 100 tudengi hulgas (huvialade jaotus). Vastuste analüüs näitas: 28 tudengit pidasid oma huvialaks kunsti, 30 tudengit - muusikat ja 42 tudengit - sporti. 10 tudengit tundis huvi nii kunsti kui spordi, 5 tudengit - kunsti ja muusika ning 8 tudengit spordi ja muusika vastu. Nende hulgast 3 tudengit ütles ennast huvi tundvat kõigi kolme ala vastu. Kui palju tudengeid tunneb huvi ainult spordi vastu? ainult muusika vastu? mitte ühegi vastu nimetatud kolmest alast.
  
• Tudengirühmas on 25 inimest. Eksamieelduseks on saada kahe kontrolltöö arvestused. Esimesel kontrolltööl sai arvestuse 20 tudengit, teisel 21 tudengit. Kui palju tudengeid (minimaalselt ja maksimaalselt) pääseb eksamile?
  
• Vanal ajal toimunud lahingus sai palju sõdalasi kannatada. 70% lahingust osavõtjatest kaotas lahingus silma, 75% - kõrva, 80% - käe ja 85% - jala. Kui palju sõdalastest (minimaalselt ja maksimaalselt) jäi ilma nii silmast, kõrvast, käest kui ka jalast ?
  
• Füüsika- matemaatika teaduskonna iga tudeng tunneb huvi kas füüsika või matemaatika vastu. Kui palju tudengitest tunneb huvi mõlema ala vastu, kui on teada, et matemaatikahuvilisi on 84% ja füüsikahuvilisi - 64%?
  
• Hulk A koosneb naturaalarvudest 1 kuni 1000. Leida, mitu hulga A elementi ei jagu ei kolmega ega viiega .
  

VASTAVUSED
Antud 2 hulka A ja B ning reegel, kuidas hulga A elemendid on vastavuses  hulga B elementidega.
  A x B  : A  B
Vastavuse määramispiirkond ( domain ):
D()
Vastavuse muutumispiirkond (range):
R()
Vastavuse täiend:
= Pöördvastavus: <  BxA | | = ||
Vastavuste ühend ja ühisosa:
1  
1  
Vastavuste kompositsioonitehe:
1   ,kus
1  AxB ja 2  BxC.
Kompositsioonitehe on assotsiatiivse iseloomuga .
Vastavuste klassifikatsioon
Vastavus   AxB on kõikjal määratud, kui D() = A.
Vastavus   AxB on kõikjale määratud, kui R()=B.
Vastavus   AxB on ühene, kui -1   .
Vastavus   AxB on üks-ühene, kui -1    ja
  -1 
Ühene vastavus, mis pole kõikjal määratud - osaliselt määratud funktsioon.
Ühene vastavus, mis on kõikjal määratud, kuid pole kõikjale määratud - täielikult määratud funktsioon.
Ühene kõikjal ja kõikjale määratud vastavus - sürjektsioon .
Üks-ühene kõikjal määratud vastavus - injektsioon .
Üks-ühene kõikjal ja kõikjale määratud vastavus - bijektsioon .
Näide: Hulk A - õpperühma tudengite hulk. Hulk B - hinnete hulk (). Vastavus  - eksamil tudengi poolt saadud hinne. Millistel tingimustel on  osaliselt määratud funktsioon; täielikult määratud funktsioon; sürjektsioon; injektsioon; bijektsioon?
BINAARSUHTED
Meie poolt vaadeldavad binaarsuhteid võib käsitleda kui vastavuse  erijuhtu, kus lähte- ja sihthulk langavad kokku (D()=R()=A). Tähistame järgnevas binaarsuhet tähega R  AxA. Binaarsuhet on mugav interpreteerida suhte graafiga - s.o. orienteeritud graaf , kus hulga A elemendid vastavad tippudele ja seosed elementide vahel - kaartele. Suhte võime esitada binaarmaatriksina (naabrusmaatriksina).
Näide.< elementideks on arvutikomponendid: a-sisendseade, b- aritmeetika-loogikaseade, c-juhtseade, d-mälu, e-väljundseade. Binaarsuhe R seob kahte elementi, kui esimene seade annab teisele infot arvuti töö käigus.
a
b
c
d
e
a
1
1
1
1
0
b
0
1
1
1
1
R=
c
1
1
1
1
1
d
0
1
1
1
1
e
0
0
1
0
1
Binaarsuhete R omadused

• Refleksiivsus (1 ) - ( aA [R] ).
  
• Antirefleksiivsus (2 ) - ( aA [R]).
  

Suhe, mis ei täida nõudeid 1 ega 2 , on mitterefleksiivne.

• Sümmeetria (3 ) - ( a,bA [R  R]), kus a  b.
  
• Antisümmeetria (4 ) - ( a,bA [R  R]), kus a  b.
  

Suhe, mis ei täida nõudeid 3 ega 4 , on mittesümmeetriline.

• Transitiivsus (5 ) - (a,b,cA (R & R)  R]), kus ab, bc, ac.
  
• Antitransitiivsus (6 ) - (a,b,cA (R & R)  R]), kus ab,bc,ac.
  

Suhe, mis ei täida nõudeid 5 ega 6 , on mittetransitiivne.

• d(R,i ) - suhte R kaugus omaduseni i , s.o. seoste arv, mis tuleb minimaalselt lisada suhtesse R (või eemaldada suhtest R), et saavatada omadust i.
  
• Suhte täiend - = ( A x A ) \ R
  
• Pöördsuhe -
  
• Suhte R transitiivseks sulundiks nimetatakse minimaalset transitiivset suhet , mis sisaldab suhet R.
  

• Osaline mitterange järjestussuhe (  ) on refleksiivne, antisümmeetriline ja transitiivne.
  
• Osaline range järjestussuhe (
• Lineaarne järjestussuhe - ( a,bA) [ (a  a  b }
  Leida ja klassifitseerida vastavus . Leida .
  
  • R 
    
  
  Näidata, kas R on osalise järjestuse suhe.
  
  < R  A x A
  
  < - Cantori algebra.< - loogikaalgebra .
  
  • Kaks algebrat on isomorfsed ( A1 =  A2 = ), kui eksisteerib üksühene vastavus  nii, et : (M1  S1 )  ( M2  S2 ), kus
    
  
  fi (mj1 ,....,mjk-1)=mjk  (fi )((mj1 ),....,((mjk-1 )) = (mjk),
  mjl  M1 , (mjl)  M2 , fi  S1 , (fi )  S2 .
  Cantori algebra ja loogikaalgebra on isomorfsed.
  Ülesanded.
  
  <. Operatsioonid : +(mod p) ja x(mod p) (s.o. liitmine ja korrutamine mooduliga p). Kas selliselt kirjeldatud algabra on rühm?
  
  
  
  <. Ehitada kõikvõimalike tükelduste võre.
  
  
  MATEMAATILINE LOOGIKA
  Vaatleme loogikafunktsioone f(x1 ,x2 ,...xn), kus nii argumendid kui funktsiooni vää.Iga loogikafunktsiooni võib esitada tõeväärtustabelina.
  Näide Hääletusseade. Komisjon , mis koosneb 3 inimesest, hääletab teatava otsuse vastuvõtmise küsimuses. Otsus võetakse vastu lihthäälteenamusega.
  x1
  x2
  x3
  f(x1, x2, x3 )
  0
  0
  0
  0
  0
  0
  1
  0
  0
  1
  0
  0
  0
  1
  1
  1
  1
  0
  0
  0
  1
  0
  1
  1
  1
  1
  0
  1
  1
  1
  1
  1
  f(x1 , x2 , x3 )= x2x3  x1x3  x1x2  x1x2x3
  Erinevate loogikafunktsioonide f(x1 ,x2 ,...xn) arv K on .
  n=1  K=4
  n=2  K=16
  n=3  K=256
  n=4  K=65536
  n=5  K=4,3  109
  Järgnevalt tutvume kõikvõimalike kahe muutuja funktsioonidega f(x1 , x2 ).
  x1
  x2
  f0
  f1
  f2
  f3
  f4
  f5
  f6
  f7
  f8
  f9
  f10
  f11
  f12
  f13
  f14
  f15
  0
  0
  0
  0
  0
  0
  0
  0
  0
  0
  1
  1
  1
  1
  1
  1
  1
  1
  0
  1
  0
  0
  0
  0
  1
  1
  1
  1
  0
  0
  0
  0
  1
  1
  1
  1
  1
  0
  0
  0
  1
  1
  0
  0
  1
  1
  0
  0
  1
  1
  0
  0
  1
  1
  1
  1
  0
  1
  0
  1
  0
  1
  0
  1
  0
  1
  0
  1
  0
  1
  0
  1
  Tabelis on kirjeldatud järgnevad funktsioonid:
  
  • f0 - konstant "0"
    
  • f1 - konjunktsioon, loogiline korrutamine, "ja"-funktsioon, x1& x2 ehk x1 x2 ehk x1x2
    
  • f2 - implikatsiooni eitus
    
  • f3 - argumendi x1 väärtus
    
  • f4 - pöördimplikatsiooni eitus
    
  • f5 - argumendi x2 väärtus
    
  • f6 - argumentide summa mooduliga 2, (x1 + x2 )mod2 ehk x1  x2
    
  • f7 - disjunktsioon, loogiline liitmine, "või"-funktsioon, x1  x2 ehk x1 + x2
    
  • f8 - Pierce 'i nool, Pierce'i funktsioon, "või-ei"-funktsioon, ehk f9 - ekvivalentsi- ehk samaväärsusfunktsioon, x1  x2 ehk x1  x2
    
  • f10 - argumendi inversioon
    
  • f11 - pöördimplikatsioon x2  x1
    
  • f12 - argumendi inversioon
    
  • f13 - implikatsioon x1  x2
    
  • f14 - Shefferi kriips, Shefferi funktsioon, ehk x1 | x2
    
  • 
    
  • f15 - konstant 1
    
  
  Enamkasutatavate tehete prioriteet (tähtsus), mis määrab sulgude kasutamise vajaduse loogikaavaldistes:  , & ,  ,  , 
  Loogika põhiseadused
  
  • Idempotentsusseadused
    
  
  x&x=x xx=x
  
  • Kommutatiivsusseadused
    
  
  x1 & x2 = x2 & x1
  x1  x2 = x2  x1
  
  • Assotsiatiivsusseadused
    
  
  (x1 & x2 ) & x3 = x1 & (x2 & x3 )
  (x1  x2 )  x3 = x1  (x2  x3 )
  
  • Distributiivsusseadused
    
  
  x1 & ( x2  x3 ) = x1 & x2  x1 & x3
  x1  ( x2 & x3 ) = ( x1  x2 ) & ( x1  x3 )
  
  • Topelteituse seadus
    
  • De Morgani seadused
    
  
  
  • Kleepimisseadused
    
  
  
  • Neeldumisseadused
    
  
  
  • Tehted konstantidega
    
  
  x & 0 = 0 x  0 = x
  x & 1 = x x  1 = 1
  
  • Lisateisendused
    
  
  Näiteid (näidetes on antud algavaldis ja lõppresultaat pärast lihtsustamist)
  
  • Loogikafunktsiooni konstituent: , kus
    
  
  Iga loogikafunktsioon on esitatav oma konstituentide disjunktsioonina. Loogikafunktsiooni esitamiseks kasutame loogikavalemeid.
  
  • Loogikavalem on samaselt tõene, kui iga argumentide vektori ( x1 , x2 ,..., xn ) puhul
    
  
  f(x1 , x2 ,..., xn )=1.
  Samaselt tõene valem - tautoloogia.
  
  • Loogikavalem on samaselt väär, kui iga argumentide vektori ( x1 , x2 ,..., xn ) puhul
    
  
  f(x1 , x2 ,..., xn )=0.
  
  • Loogikavalemid f1 ja f2 samaväärsed, kui iga argumentide vektori ( x1 , x2 ,..., xn ) puhul
    
  
  f1(x1 , x2 ,..., xn )= f2(x1 , x2 ,..., xn )=.
  
  • Algtermiks nimetame argumenti xi või tema inversiooni .
    
  • Loogikavalemi keerukus on tema koosseisus olevate algtermide arv.
    
  • Loogikavalemi sügavuse määrame järgnevalt:
    
  
  
• argumendi xi sügavus on 0;
  
• F(f1 , f2 ,..., fn ) sügavus on k+1, kui f1 , f2 ,..., fn maksimaalne sügavus on k.
  Ülesandeid
  
  • Lihtsustada järgmine avaldis:
    
  
  Leida tõeväärtustabel alg- ja lõppavaldise jaoks. Veenduda lihtsustuse õigsuses.
  
  • Lihtsustada järgmised avaldised:
    
  
  
  • Tõestada DeMorgani seadused 3 muutuja jaoks nii tõeväärtustabeliga kui ka valemiliselt.
    
  • Antud kolme muutuja nn. mazhoritaarfunktsioon: . Tõestada, et kehtivad järgmised võrdused:
    
  
  Loogikafunktsioonide normaalkujud
  Loogikafunktsioon f(x1 , x2 ,..., xn ) võib olla esitatud erinevate valemite abil.
  Näiteks
  
  • Loogikafunktsiooni kanoonilisi standardseid esitusvalemeid nimetatakse funktsiooni normaalkujudeks.
    
  • Disjunktiivne normaalkuju (DNK) on valem, mis koosneb elemantaarkonjunktsioonide disjunktsioonist.
    
  • Elemantaarkonjunktsioon koosneb argumentide ja/või nende inversioonide konjunktsioonist.
    
  • Konjunktiivne normaalkuju (KNK) on valem, mis koosneb elemantaardisjunktsioonide konjunktsioonist.
    
  • Elemantaardisjunktsioon koosneb argumentide ja/või nende inversioonide disjunktsioonist.
    
  • Iga funktsioon on esitatav DNK ja KNK kujul, kuid mitte üheselt.
    
  
  
  • Täielik DNK (TDNK) on selline DNK, kus iga elemantaarkonjunktsiooni pikkus on n (s.o. iga elementaarkonjunktsioon sisaldab funktsiooni kõiki argumente).
    
  • Täielik KNK (TKNK) on selline KNK, kus iga elemantaardisjunktsiooni pikkus on n (s.o. iga elementaardisjunktsioon sisaldab funktsiooni kõiki argumente).
    
  • Igal funktsioonil on täpselt üks TDNK ja üks TKNK.
    
  
  Näiteid
  
  • 
    
  
  Parempoolne valem on funktsiooni täielik DNK.
  
  • 
    
  
  Parempoolne valem on funktsiooni täielik KNK.
  
  • 
    
  
  Parempoolne valem on antud funktsiooni DNK, KNK, TKNK.
  Loogikafunktsiooni võib esitada ka nn. numbrilises ehk kümnendesitusvormis. Sel juhul esitatakse funktsiooni ühtede või nullide piirkond vastavate argumendivektorite kümnendekvivalentide abil.
  Näiteks vaatleme funktsiooni eelnevast näitekomplektist:
  Kasutatud näitefunktsiooni tõeväärtustabel on toodud järgnevas:
  Nr.
  x1
  x2
  x3
  f(x1 ,x2 ,x3)
  0
  0
  0
  0
  0
  1
  1
  0
  0
  1
  0
  1
  2
  0
  1
  0
  1
  0
  3
  0
  1
  1
  1
  0
  4
  1
  0
  0
  0
  1
  5
  1
  0
  1
  1
  0
  6
  1
  1
  0
  0
  1
  7
  1
  1
  1
  0
  1
  
  • Minimaalse keerukusega DNK-d (KNK-d) nimetatakse minimaalseks DNK-ks (KNK-ks). Lühenditena vastvalt MDNK ja MKNK.
    
  
  Ülesanne
  Leida antud loogikafunktsiooni MDNK, MKNK, TDNK, TKNK.
  Minimeerimine normaalkujude klassis
  Boole'n all mõistame järgnevas kõikvõimalike kahendvektorite (x1 ,x2 ,...,xn ) hulka. Hüperkuupi (n-mõõtmelist kuupi) esitame kui graafi , mille iga tipp vastab üks-ün ühele vektorile ja 2 tippu on omavahel seotud, kui vastavad vektorid on ortogonaalsed (s.o. erinevad) täpselt ühe argumendi järgi ja langevad kokku ülejäänud (n-1)-s argumendis.
  
  • Intervall on vektorite (x1 ,x2 ,...,xn ) hulk, mis moodustavad teatava suurusega hüperkuubi.
    
  • Antud funktsiooni ühtede intervall on intervall, mille koosseisus olevate vektorite jaoks f(x1 ,x2 ,...,xn )=1.
    
  • Maksimaalne ühtede intervall on ühtede intervall, mis ei sisaldu üheski teises ühtede intervallis.
    
  
  Näide
  f(x1 ,x2 ,x3 )=(0,1,2,3,7)1
  Ühtede intervallidMaksimaalsed ü.
  Intervalle võ
  Nä  001  <  0--  <  -11  x2x3
  
  • Konjunktsiooni, mis vastab ühtede intervallile nimetatakse funktsiooni implikandiks.
    
  • Konjunktsiooni, mis vastab maksimaalsele ühtede intervallile nimetatakse funktsiooni lihtimplikandiks.
    
  • Kõigi lihtimplikantide disjunktsioon esiatb funktsiooni taandatud DNK.
    
  
  Näit. f(x1 ,x2 ,x3 ) = (1,3,6,7)1 <  0-1 <  -11<  11-
  Taandatud DNK:
  
  • Taandatud DNK võib sisaldada liiaseid liikmeid.
    
  
  Eelmises näites esitatud funktsiooni MDNK on järgnev: .
  Kõik eelpool esitatu võib olla interpreteeritud nullide piirkonna ja vastavalt KNK jaoks (maksimaalne nullide intervall, taandatud KNK jne.)
  Ülesanded
  
  • Antud funktsioon f(x1 ,x2 ,x3 ) = x1  x2  x3
    
  
  Esitada funktsioon TDNK, MDNK ja taandatud DNK kujul.
  
  < argumentidena a1 a2 ja b1 b2 . F{0,1,2,3,4,5,6} funktsioonidena f1 f2 f3 , kusjuures fi =f(a1 ,a2 ,b1 ,b2 ). Esitada f1 MDNK-s; f2 MKNK-s; f3 TDNK-s.
  
  
  Loogikafunktsioonide minimeerimine Karnaugh ’ kaardiga
  Antud teemat on eestikeelses versioonis põhjalikult käsitletud A. Ariste „Loogikalülituste koostamise metoodikas “ (TPI, 1978). Seetõttu piirdun siin vaid mõingate näidetaga.
  
  • Täielikult määratud loogikafunktsioonid .
    
  
  1. Kahe muutuja loogikafunktsioonid.
  Näide 1 f(x1 ,x2 )=(0,1,3)1
  x2
  x1
  0
  1
  0
  1
  1
  1
  0
  1
  f(x1 ,x2 )=
  Näide 2 f(x1 ,x2 )=(1,2,3)1
  x2
  x1
  0
  1
  0
  0
  1
  1
  1
  1
  f(x1 ,x2 )= x1  x2
  2.Kolme muutuja loogikafunktsioonid
  Näide 3
  f(x1 ,x2 ,x3)=(1,3,6,7)1
  x2x3
  x1
  00
  01
  11
  10
  0
  0
  1
  1
  0
  1
  0
  0
  1
  1
  f(x1 ,x2 ,x3)= - minimaalne DNK
  f(x1 ,x2 ,x3)= - minimaalne KNK
  Märkus : Karnough’ kaardil on punktiiriga näidatud liiasetele lihtimplikantidele vastavad kontuurid.
  Näide 4
  f(x1 ,x2 ,x3)=(1,4,5,6,7)1
  x2x3
  x1
  00
  01
  11
  10
  0
  0
  1
  0
  0
  1
  1
  1
  1
  1
  f(x1 ,x2 ,x3)= - minimaalne DNK
  f(x1 ,x2 ,x3)= - minimaalne KNK
  3. Nelja muutuja loogikafunktsioonid
  Näide 5
  f(x1 ,x2 ,x3, x4 )=(0,1,6,8,9,12,14)1
  x3x4
  x1x2
  00
  01
  11
  10
  00
  1
  1
  0
  0
  01
  0
  0
  0
  1
  11
  1
  0
  0
  1
  10
  1
  1
  0
  0
  f(x1 ,x2 ,x3, x4)= - minimaalne DNK
  f(x1 ,x2 ,x3, x4)= - minimaalne KNK
  
  • Osaliselt määratud loogikafunktsioonid
    
  
  Näide 6
  f(x1 ,x2 ,x3)=(0,2,7)1(1,3,5)-
  x2x3
  x1
  00
  01
  11
  10
  0
  1
  1
  1
  0
  1
  0
  f(x1 ,x2 ,x3)= - avaldis on ühtlasi nii minimaalne DNK kui ka minimaalne KNK.
  Näide 7
  f(x1 ,x2 ,x3, x4 )=(2,3,5,6,7,11,15)1(0,10,14)-
  x3x4
  x1x2
  00
  01
  11
  10
  00
  0
  1
  1
  01
  0
  1
  1
  1
  11
  0
  0
  1
  10
  0
  0
  1
  f(x1 ,x2 ,x3, x4)= - minimaalne DNK
  f(x1 ,x2 ,x3, x4)= - minimaalne KNK
  
  • Viie muutuja loogikafunktsioonid.
    
  
  Näide 8
  f(x1 ,x2 ,x3, x4, x5)=(2,3,5,5,7,11,15,16,17,18,19,21,22,23,26,27,30,31)1(0,10,14)-
  x4x5
  x2x3
  00
  01
  11
  10
  00
  0
  1
  1
  01
  0
  1
  1
  1
  11
  0
  0
  1
  10
  0
  0
  1
  x1=0
  x4x5
  x2x3
  00
  01
  11
  10
  00
  1
  1
  1
  1
  01
  0
  1
  1
  1
  11
  0
  0
  1
  1
  10
  0
  0
  1
  1
  x1=1
  f(x1 ,x2 ,x3, x4, x5)= - minimaalne DNK
  f(x1 ,x2 ,x3, x4, x5)= - minimaalne KNK
  Ülesanded
  
  • Ruumi temperatuuri reguleerivad 2 konditsioneeri F1 ja F2. Neid juhitakse 3 kahendanduri X1, X2 ja X3 abil. Kui temperatuur on alla 18 kraadi, on X1=X2=X3=0 ja konditsioneerid välja lülitatud (F1=F2=0). Kui temperatuur on 18 ja 21 kraadi vahel, siis X1=1 ning X2=X3=0. Sisse lülitatakse konditsioneer F1 (F1=1, F2=0). Kui temperatuur on 21 ja 24 kraadi vahel, siis X1=X2=1 ja X3=0. Sisse lülitatakse võimsam konditsioneer F2 (F1=0, F2=1). Temperatuuril üle 24 kraadi (X1=X2=X3=1) lülitatakse sisse mõlemad konditsioneerid (F1=F2=1). Avaldada osaliselt määratud funktsioonid F1 ja F2 sõltuvalt anduritest X1, X2 ja X3.
    
  
  
  • Antud nelja muutuja loogikafunktsioon:
    
  
  f(x1 ,x2 ,x3, x4)=
  Leida Karnaugh' kaardiga MDNK ja MKNK.
  Kontrollvastus: f(x1 ,x2 ,x3, x4)=
  
  • Antud nelja muutuja loogikafunktsioon:
    
  
  f(x1 ,x2 ,x3, x4)=
  Leida Karnaugh' kaardiga MDNK ja MKNK.
  Kontrollvastus: f(x1 ,x2 ,x3, x4)=
  
  • Nelja muutuja funktsioon F(x1 ,x2 ,x3, x4) on esitatud konjunktsioonina kahest funktsioonist:
    
  
  F(x1 ,x2 ,x3, x4)= f1(x1 ,x2 ,x3, x4)& f2(x1 ,x2 ,x3, x4)
  F(x1 ,x2 ,x3, x4)=
  f1(x1 ,x2 ,x3, x4)=
  Leida minimaalse DNK-ga f2(x1 ,x2 ,x3, x4).
  
  • Nelja muutuja funktsioon F(x1 ,x2 ,x3, x4) on esitatud disjunktsioonina kahest funktsioonist:
    
  
  F(x1 ,x2 ,x3, x4)= f1(x1 ,x2 ,x3, x4) f2(x1 ,x2 ,x3, x4)
  F(x1 ,x2 ,x3, x4)=
  f1(x1 ,x2 ,x3, x4)=
  Leida minimaalse DNK-ga f2(x1 ,x2 ,x3, x4).
  
  • Antud nelja muutuja funktsioon F(x1 ,x2 ,x3, x4)=. Leida funktsiooni F(x1 ,x2 ,x3, x4) inversiooni minimaalne DNK.
    
  
  
  • Minimeerida järgnevad funktsioonid Karnough’ kaardiga. Leida MDNK ja MKNK.
    
  
  f(x1 ,x2 ,x3, x4 )=(1,4,5,9,11,12,13,15)1(3,14)-
  f(x1 ,x2 ,x3, x4, x5)=(0,2,6,7,8,10,24,30)1(3,14,16,18,26)-
  f(x1 ,x2 ,x3, x4 ) =
  Viimases ülesandes tuleb argumendipaari xixj vaadelda kui tavalisi kahekohalisi kahendarve ning +-operatsiooni kui aritmeetilist liitmist.
  Loogikafunktsioonide minimeerimine McCluskey' meetodil
  Karnaugh' kaart võimaldab effektiivselt minimeerida funktsioone, mille muutujate arv on suhteliselt väike. Samuti on kaart eelkõige visuaalne minimeerimisvahend ning kasutatav meetod on tülikas algoritmiseerimiseks (seega mittesobiv masinrealisatsiooniks). McCluskey minimeerimismeetod on süstemaatiline ja kergesti viidav algoritmilisele kujule . Samuti puuduvad piirangud funktsiooni muutujate arvule (reaalsed piirangud tekkivad sõltuvalt arvuti võimsusest).
  
  • McCluskey meetod koosneb kahest põhietapist:
    
  
  
• Loogikafunktsiooni kõigi lihtimplikantide leidmine, kasutades süstemaatiliselt kleepimisseadusi;
  
• Lihtimplikantide hulga minimeerimine (katteülesanne).
  Kaks enamlevinud varianti antud meetodist erinevad algandmete esituselt. Need on niinimetatud intervallmeetod, mille puhul implikantide kirjeldamiseks kasutatakse intervallesitust ja numbriline meetod, mis on orienteeritud funktsiooni kümnendesitusele.
  
  • Intervallmeetod
    
  
  Kuna McCluskey meetod põhineb kleepimisseaduse kõikvõimalikele rakendustele antud funktsiooni ühtede piirkonnas, on otstarbekas esmalt sektsioneerida kogu funktsiooni ühtede piirkond vastavate kahendvektorite nn. indeksite järgi. Sellega minimeeritakse läbiviidavate võrdluste arvu. Boole'i vektori indeks on ühtede arv selles vektoris. Ilmselt on omavahel kleebitavad vaid need kahendvektorid, mille indeksid erinevad täpselt ühe võrra (seejuures langevad (n-1) argumendi väärtused kokku ja ühe argumendi väärtus on kleebitavates vektorites erinev).
  Pärast indeksite määramist toimub kleepmisseaduse alusel intervallide tabelite koostamine (vt. näide). Esimese etapi lõpuks saadakse kõigi antud funktsiooni lihtimplikantide loetelu . Teise etapi käigus seda loetelu minimeeritakse s.t. valitakse minimaalne alamhulk lihtimplikantidest, mis võimaldavad katta antud funktsiooni ühtede piirkonna (s.o. tüüpiline katteülesanne).
  Näide
  f(x1 ,x2 ,x3, x4 ) = (0,1,2,5,6,7,8,9,10,14)1
  
  • 1.etapp - lihtimplikantide hulga leidmine
    
  
  Indeks
  Intervall
  Märge
  Indeks
  Intervall
  Märge
  Indeks
  Intervall
  Märge
  0
  0000
  x
  0-1
  000-
  x
  0-1-1-2
  -00-
  A4
  1
  0001
  x
  00-0
  x
  -0-0
  A5
  0010
  x
  -000
  x
  1-2-2-3
  --10
  A6
  1000
  x
  1-2
  0-01
  A1
  2
  0101
  x
  -001
  x
  0110
  x
  0-10
  x
  1001
  x
  -010
  x
  1010
  x
  100-
  x
  3
  0111
  x
  10-0
  x
  1110
  x
  2-3
  01-1
  A2
  011-
  A3
  -110
  x
  1-10
  x
  Tabelite kolmandas veerus olev märge x näitab, et antud intervall on osalenud kleepimisprotsessis ja kuulub järelikult mõne suurema intervalli koosseisu. Märke x puudumine näitab, et intervall on lihtimplikandiks (tähistused A1 kuni A6).
  
  • 2.etapp - lihtimplikantide hulga minimeerimine
    
  
  Impl.
  0
  1
  2
  5
  6
  7
  8
  9
  10
  14
  A1
  x
  x
  A2
  x
  x
  A3
  x
  x
  A4
  x
  x
  x
  
  A5
  x
  x
  x
  x
  A6
  x
  x
  x
  
  Lahendis osalevad lihtimplikandid peavad katma funktsiooni ühtede piirkonna. Lihtimplikandid A4 ja A6 on igal juhul vajalikud, kuna nad võimaldavad ainsatena katta vektoreid 9 ja 14 (tabelis ). Implikantide A4 ja A6 lülitamine lahendisse katab ühtlasi ka vektorid 0,1,8 (A4) ja 2,6,10 (A6). Seega jäävad katmata vektorid 5 ja 7, mis omakorda kaetakse implikandiga A2.
  f(x1 ,x2 ,x3, x4 ) = A6  A4  A2 =
  
  • Numbriline meetod
    
  
  Implikantide kujutamine kolmendintervallide kujul võib olla küllalt tülikas, kui funktsiooni argumentide arv on küllalt suur. Pikkade intervallidega suureneb vigade tõenäosus (seda küll käsitsi lahendamisel). Meetodi 2. etapil tekitab probleeme kattetabeli täitmine, kus paratamatult läheme intervallidelt tagasi kümnendesitusele. McCluskey numbriline meetod säilitab andmete esituse kümnendkujul praktiliselt kuni lahendi väljakirjutamiseni. Kleepimisseaduste rakendus numbrilisel kujul nõuab teatavaid lisareegleid, mida järgnevas kirjeldatame. Kümnendnumbri indeksi mõiste on endiselt seotud numbrile vastava kahendvektori ühtede arvuga. Numbrid on omavahel kleebitavad, kui:
  
• numbrite vahe on võrdne 2k , kus k=0,1,2...;
  
• suurema numbriga seostub suurem indeks.
  Igal kleepimisel fikseeritakse numbrite vahe, mis hilisemas on vajalik kleepimisel väljalangeva argumendi määramiseks . Vahede fikseerimiseks on vaja alates lihtimplikantide leidmise etapi teisest tabelist lisaveergu „vahe“
  Kasutades uuesti sama näidet, leiame lihtimplikantide hulga numbrilisel meetodiga.
  
  • 1.etapp - lihtimplikantide hulga leidmine
    
  
  Ind.
  Nr.
  Märge
  Ind.
  Nr.-d
  Vahe
  Märge
  Ind.
  Nr.-d
  Vahe
  Märge
  0
  0
  x
  0-1
  0-1
  1
  x
  0-1-1-2
  0-1-8-9
  1,8
  A4
  1
  1
  x
  0-2
  2
  x
  0-2-8-10
  2,8
  A5
  2
  x
  0-8
  8
  x
  1-2-2-3
  2-6-10-14
  4,8
  A6
  8
  x
  1-2
  1-5
  4
  A1
  2
  5
  x
  1-9
  8
  x
  6
  x
  2-6
  4
  x
  9
  x
  2-10
  8
  x
  10
  x
  8-9
  1
  x
  3
  7
  x
  8-10
  2
  x
  14
  x
  2-3
  5-7
  2
  A2
  6-7
  1
  A3
  6-14
  8
  x
  10-14
  4
  x
  Leitud lihtimplikantide hulga minimeerimine toimub täpselt samuti, kui intervallmeetodi puhul. Lahendisse satuvad lihtimplikandid A2, A4 ja A6. Märgime, et siiani oleme kogu info esitanud eranditult kümnendkujul. Minimaalse DNK väljakirjutamisel võib lähtuda järgnevas tabelis kirjeldatud mõttekäigust.
  Lihtimplikant
  Vahed
  x1
  x2
  x3
  x4
  Konjunktsioon
  A2
  2
  0
  1
  1
  A4
  1,8
  0
  0
  A6
  4,8
  1
  0
  f(x1 ,x2 ,x3, x4 ) = A4  A6  A2 =
  Kommentaarid:
  
• Muutujate kaalud (antud juhul 8-4-2-1) ja vahede väärtused määravad konjunktsioonides mitteosalevad argumendid. Näiteks vahedest 1,8 ( implikant A4) tulenevalt ei osale nimetatud konjunktsioonis argumendid x1 ja x4 .
  
• Ülejäänud argumentide märgid tulenevad suvalisest implikandi kirjeldusse kuuluva kümnendnumbri kahendkoodist (s.o. vastavast kahendvektorist). Näiteks implikandi A4 koosseisus olevate kõigi numbrite 0,1,8 ja 9 kahendkoodides on x2 = 0 ja x3 = 0. Seega konjunktsiooniks tuleb .
  Edasises kirjelduses põhineme McCluskey numbrilisele meetodile . McCluskey meetodiga on võimalik analoogiliselt tuletada ka minimaalne KNK, samuti minimeerima osaliselt määratud loogikafunktsioone. Peatume järgnevalt nendel probleemidel.
  
  • Minimaalse KNK tuletamine
    
  
  Toome välja olulisemad erinevused võrreldes DNK tuletamisega ( orientatsioon järgnevas tehtud numbrilisele meetodile).
  
• Lähtume loogikafunktsiooni nullide piirkonnast .
  
• Kogu lahendusprotsess on analoogiline eelpool kirjeldatuga kuni funktsiooni väljakirjutamiseni (leitakse maksimaalsed nullide intervallid (etapp 1) ja minimeeritakse nende hulk (kaetakse kõik nullide piirkonna punktid minimaalse arvu intervallidega - s.o. lahendatakse katteülesanne (etapp 2)).
  
• Iga lahendisse lülitatav maksimaalne nullide intervall vastab minimaalse KNK elementaardisjunktsioonile, seega argumentide märgid tuleb väljakirjutamisel inverteerida.
  
  • Näide
    
  
  f(x1 ,x2 ,x3, x4 ) = (2,5,6,7,10,11,14)0
  
  • 1.etapp - lihtimplikantide hulga leidmine
    
  
  Ind.
  Nr.
  Märge
  Ind.
  Nr.-d
  Vahe
  Märge
  Ind.
  Nr.-d
  Vahe
  Märge
  1
  2
  x
  1-2
  2-6
  4
  x
  1-2-2-3
  2-6-10-14
  4,8
  A4
  2
  5
  x
  2-10
  8
  x
  6
  x
  2-3
  5-7
  8
  A1
  10
  x
  6-7
  4
  A2
  3
  7
  x
  6-14
  8
  x
  11
  x
  10-11
  4
  A3
  14
  x
  10-14
  8
  x
  
  • 2.etapp - lihtimplikantide hulga minimeerimine
    
  
  Impl.
  2
  5
  6
  7
  10
  11
  14
  A1
  
  x
  A2
  x
  x
  A3
  x
  
  A4
  
  x
  x
  
  Kohustuslikud intervallid A1( vektor 5), A3 (vektor 11) ja A4 (vektorid 2 ja 14) katavad kogu nullide piirkonna. Elementaarkonjunktsioonide leidmine toimub analoogiliselt eelpool tooduga
  Lihtimplikant
  Vahed
  x1
  x2
  x3
  x4
  Disjunktsioon
  A1
  2
  0
  1
  1
  A3
  1
  1
  0
  1
  A4
  4,8
  1
  0
  f(x1 ,x2 ,x3, x4 ) =
  
  • Osaliselt määratud funktsioonide minimeerimine (DNK näite baasil).
    
  
  Erinevused võrreldes eelnevaga :
  
• Esimesel tapil ühendatakse funktsiooni ühtede ja määramatuspiirkonnad eesmärgiga kasutada määramatuspiirkonda implikantide laiendamiseks. Seejuures lihtimplikandid, mis on moodustatud ainult määramatuspiirkonna baasil märgistatakse eraldi (järgnevas näites tärniga *) eristamaks neid ülejäänutest ja vältimaks nende sattumist lõpplahendisse.
  
• Teisel etapil on vaja katta vaid ühtede piirkonna punktid. Katmiseks kasutatakse lihtimplikante, mis kasvõi osaliselt katavad ühtede piirkonda.
  Näide
  Antud osaliselt määratud funktsioon:
  f(x1 ,x2 ,x3, x4 ) = (0,2,4,8,10,12)1 (5,13,15)-
  
  • 1.etapp - lihtimplikantide hulga leidmine
    
  
  Ind.
  Nr.
  Märge
  Ind.
  Nr.-d
  Vahe
  Märge
  Ind.
  Nr.-d
  Vahe
  Märge
  0
  0
  x
  0-1
  0-2
  2
  x
  0-1-1-2
  0-2-8-10
  2,8
  A1
  1
  2
  x
  0-4
  4
  x
  0-4-8-12
  4,8
  A2
  4
  x
  0-8
  8
  x
  1-2-2-3
  4-5-12-13
  1,8
  A3
  8
  x
  1-2
  2-10
  8
  x
  2
  5*
  x
  4-5
  1
  x
  10
  x
  4-12
  8
  x
  12
  x
  8-10
  2
  x
  3
  13*
  x
  8-12
  4
  x
  4
  15*
  x
  2-3
  5-13*
  8
  x
  12-13
  1
  x
  3-4
  13-15*
  2
  Teise tabeli viimane intevall (märgistatud #) ei moodusta funktsiooni lihtimplikanti, kuna on moodustatud määramatuspiirkonna arvel. Seega leidsime kolm lihtimplikanti, milliste alusel moodustatakse minimaalne DNK.
  
  • 2.etapp
    
  
  Impl.
  0
  2
  4
  8
  10
  12
  A1
  x
  
  x
  
  A2
  x
  x
  x
  x
  A3
  x
  x
  Kohustuslik on intervall A1(vektorid 4 ja 10). Katmata jäänud punktide 4 ja 12 jaoks sobib kas implikant A2 või implikant A3.
  Lihtimplikant
  Vahed
  x1
  x2
  x3
  x4
  Konjunktsioon
  A1
  2,8
  0
  0
  A2
  4,8
  0
  0
  A3
  1,8
  1
  0
  Antud funktsiooni jaoks eksisteerib kaks keerukuselt võrdväärset lahendit:
  f 1(x1 ,x2 ,x3, x4 ) = A1  A2 = 
  f 2(x1 ,x2 ,x3, x4 ) = A1  A3 = 
  McCluskey meetodiga tutvumiseks sobib samuti juba eelpool mainitud :
  
  • A.Ariste "Loogikalülituste koostamise metoodika"
    
  
  Ülesanded
  
  • Leida McCluskey meetodiga järgmiste funktsioonide minimaalsed DNK ja KNK.
    
  
  f(x1 ,x2 ,x3, x4 ) = (2,3,5,7)1
  f(x1 ,x2 ,x3, x4 ) = (0,1,4,9,14)1 (2,3,8,11,12,15)-
  f(x1 ,x2 ,x3, x4 ) = (0,1,3,4,8,9,12,13,15)1
  f(x1 ,x2 ,x3, x4 ) = (0,1,2,3,4,5,6,7,8,9,10,11,27,28,29,30)1
  Nõrgalt määratud loogikafunktsioonide minimeerimine
  Olgu tegemist osaliselt määratud loogikafunktsiooniga, mille määramispiirkond jaguneb kolmeks:
  -piirkond, kus f(x1 ,x2 ,..., xn ) =1 (piirkond V1 );
  -piirkond, kus f(x1 ,x2 ,..., xn ) =0 (piirkond V0 );
  -piirkond, kus f(x1 ,x2 ,..., xn )väärtus pole määratud (piirkond V- );
  Vaatleme nn. nõrgalt määratud loogikafunktsioone f(x1 ,x2 ,..., xn ), millistel on järgmised omadused:
  
  • | V1 | + | V0 |