ŠĻą”±į > ž’ ŗ ¼ ž’’’ ¶ · ø ¹ ž ū w ’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’ģ„Į 7 ųæ ÕĖ bjbjUU (Z 7| 7| »Ē ’’ ’’ ’’ l ć ć ć 8 Ąć D ę ģ Ø ¶ üķ n jł " ł ł ł Ō Ö Ö Ö C !Ø $ V© v« EØ Ż ¤ EØ \ ł ł Q ZØ \ \ \ \J ł ł Ō \ Ō \ ¤ \ ©_ R e õ @i ł šķ pŌøDÅ tß ć Ż[ i @i . pØ 0 Ø "i ¬ Ż[ ( ¬ @i \ Ł IAY0010 Diskreetne matemaatika
Lühikonspekt
Käesolev lühikonspekt katab suure osa aines IAY3310 (endiste koodidega IAY3310 ja LIY3310) loetavast. Samal ajal ei saa seda materjali vaadelda kui antud aine täiskonspekti, mille läbitöötamine garanteeriks hea eksamiresultaadi.
Loengutes ja harjutustundides käsitletakse mitmeid probleeme tunduvalt põhjalikumalt.
Sellest hoolimata usun, et antud kirjutisest on paljudele tudengitest lugejatele kasu valmistumisel kontrolltööks ja eksamiks.
Margus Kruus
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 ( B = { x ( ( x ( A ) V ( x ( B ) }
Hulkade ühisosa (lõige)
A ( B = { x ( ( x ( A ) & ( x ( B )
Hulga täiend
EMBED Equation.2 = { x ( ( x ( I ) & ( x ( A ) }, kus I on nn. universaalhulk.
Hulkade vahe
A \ B = { x ( ( x ( A ) & ( x ( B ) }
Hulkade sümmeetriline vahe
A ( B = { x ( (( x ( A ) & ( x ( B )) V (( x ( A ) & ( x ( B )) }
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
EMBED Equation.2
EMBED Equation.2
Idempotentsusseadus
( ( A = A ( A = A
Välistatud kolmanda seadused
A ( EMBED Equation.2 = I
A ( EMBED Equation.2 = (
Topelttäiendi seadus
EMBED Equation.2 = A
( ( ( = ( A ( I = A A ( ( = A A ( I = I
Neeldumisseadused
A ( ( A ( B ) = A A ( ( EMBED Equation.2 ( B ) = A ( B
A ( ( A ( B ) = A A ( ( EMBED Equation.2 ( B ) = A ( B
Kleepimisseadused
( A ( B ) ( (A ( EMBED Equation.2 ) = A
( A ( B ) ( (A ( EMBED Equation.2 ) = A
A \ B = A ( EMBED Equation.2
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 = EMBED Equation.2
EMBED Equation.2
EMBED Equation.2
Leida hulk X, mis rahuldab järgmisi tingimusi:
EMBED Equation.2
Tõestada, et järgmised võrdused kehtivad:
EMBED Equation.2
Lihtsustada hulgateoreetilised avaldised, esitada Cantori normaalkujul:
EMBED Equation.2
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(() = { a ( EQ EMBED Equation.2 b ( ( () }
Vastavuse muutumispiirkond (range):
R(() = { b ( EQ EMBED Equation.2 a ( ( () }
Vastavuse täiend:
EMBED Equation.2 = { | ( v } | EMBED Equation.2 | = |AxB| - |(|
Pöördvastavus:
EMBED Equation.2 = { | (( } ( BxA | EMBED Equation.2 | = |(|
Vastavuste ühend ja ühisosa:
(1 ( (2 = { | ( (1 & ( (2 }
(1 ( (2 = { | ( (1 V ( (2 }
Vastavuste kompositsioonitehe:
(1 ( (2 = { | ( b ( ( (1 & ( (2 ) } ,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 ( ( ( { | b (B }.
Vastavus ( ( AxB on üks-ühene, kui (-1 ( ( ( { | b (B } ja
( ( (-1 ( { | a (A }
Ü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 (B={0,1,2,3,4,5}). 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.
Hulga A={a,b,c,d,e} 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.
abcdea11110b01111R=c11111d01111e00101
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 - EMBED Equation.2 = ( A x A ) \ R
Pöördsuhe - EMBED Equation.2
Suhte R transitiivseks sulundiks nimetatakse minimaalset transitiivset suhet EMBED Equation.2 , mis sisaldab suhet R.
Osaline mitterange järjestussuhe ( ( ) on refleksiivne, antisümmeetriline ja transitiivne.
Osaline range järjestussuhe ( < ) on antirefleksiivne, antisümmeetriline ja transitiivne.
Lineaarne järjestussuhe - (( a,b(A) [ (a ( R }
Ekvivalentsisuhe genereerib tükelduse P hulgal A.
Tükeldus P koosneb ekvivalentsiklassidest Ki , i=1,...,n.
P = { K1, K2, ..., Kn }, kus Ki ( (, i=1,...,n;
Ki ( Kj = (, i,j=1,...,n, i ( j;
( Ki = A.
0-tükeldus (nulltükeldus) koosneb 1-elemendilistest ekvivalentsi klassidest, 1-tükelduses (ühiktükelduses) on ainult üks ekvivalentsiklass.
Operatsioonid tükeldustega:
P1 ( P2 : (a1 ( a2 (P1 ( P2 )) ( (a1 ( a2 (P1 )& a1 ( a2 (P2 ))
P1 + P2 : (a1 ( a2 (P1 + P2 )) ( (a1 ( a2 (P1 )V a1 ( a2 (P2 ))
P1 ( P2 ( P1 ( P2 = P1 ( [ ( Ki ( P1 ( ( Kj ( P2 [ Ki ( Kj ])]
Ülesandeid vastavuste ja suhete temaatikal
A = { a,b,c,d,e } B = { x,y,z,w } C = { 1,2,3,4 }
(1 ( A x B (1 = { ,,,, }
(2 ( B x C (2 = { ,,,,, }
Leida D( (1 ), R( (1 ), EMBED Equation.2 . Esitada (1 graafiliselt.
Leida EMBED Equation.2
Klassifitseerida saadud vastavused.
A = { 1,2,3,4,5 }. Koostada suhe R, mis sisaldab mitte vähem kui 10 seost ja mis on:
1) refleksiivne, sümmeetriline ja mittetransitiivne;
mitterefleksiivne, antisümmeetriline ja transitiivne.
A = { 1,2,3,4,5 } R ( A x A
12345111010210010R=300000411001500010
Leida suhte R, tema täiendi ja pöördsuhte omadused (refleksiivsus, sümmeetria, transitiivsus, antirefleksiivsus, antisümmeetria, antitransitiivsus). Juhul kui mõnel suhtel teatav omadus puudub, leida kaugus selle omaduseni.
A = { 1,2,3,4,5 } B = {2,4,6,8 }
( ( A x B ( = { < a,b > ( a ( b }
Leida ja klassifitseerida vastavus (. Leida EMBED Equation.2 .
R ( N x N R = { < a,b> ( a jagub b-ga ( a(mod b)=0)}
Näidata, kas R on osalise järjestuse suhe.
A = { 1,2,3,4,5 } R ( A x A
R = { <1,2>,<1,3>,<1,4>,<2,2>,<3,5>,<4,3>,<4,4<,<5,3> }
Leida suhte R transitiivne sulund.
Antud suhte R ( A x A naabrusmaatriks. A = { 1,2,3,4,5,6,7,8 }
12345678110100000201001001310100000R=400010110501001001600010110700010110801001001
Näidata, et suhe R on ekvivalentsisuhe. Moodustada vastav tükeldus P1 .
Olgu tükeldus P2 = { { 1,4,6}, { 3 }, { 7 }, { 2,8 }, { 5 } }
Leida P1 ( P2 ja P1 + P2
Hulga A võimsus on n. Leida kõikvõimalike antirefleksiivsete suhete arv; kõikvõimalike sümmeetriliste suhete arv.
Antud kõigi sõnade hulk S tähestikus A. Sõna v on sõna w prefiks, kui eksisteerib sõna u(S nii, et w = vu. Näidata, et suhe sõna v on sõna w prefiks on osalise järjestuse suhe hulgal S.
ALGEBRAD JA ALGEBRALISED SÜSTEEMID.
Algebra on süsteem A = < M,S >, kus M on algebra alushulk (objektide hulk) ja S on algebra signatuur (operatsioonide hulk).
Näiteks < EMBED Equation.2 ) on algebra, mille alushulgaks on hulga A astmehulk ning signatuuriks tuntud hulgateoreetilised tehted (täiend, ühend ja ühisosa).
Vastavalt tehetes osalevate operandide arvule määratakse signatuuri tüüp, mis on antud näites määratud vektoriga (1,2,2).
Põhimõisted
Grupoid - lihtsaim algebra < M, ( >, kus ( on 2-kohaline operatsioon.
Parempoolne ühikelement e : (m(M (m ( e = m).
Vasakpoolne ühikelement e : (m(M (e ( m = m).
Ühikelement e : (m(M (m ( e=e ( m = m).
Igas grupoidis pole rohkem kui üks ühikelement.
Grupoid on idempotentne, kui (m(M (m ( m = m).
Grupoid on kommutatiivne, kui (m1 , m2 ( M (m1 ( m2 = m2 ( m1 ).
Grupoid on assotsiatiivne (nimetatakse poolrühmaks), kui kehtib assotsiatiivsusseadus.
Monoid on poolrühm, kus on olemas ühikelement.
Rühm on monoid, kus igal elemendil on olemas pöördelement
[(m(M (m-1(M ( m ( m-1 = m-1 ( m = e ) ].
Algebralise süsteemi moodustab algebra koos suhete hulgaga.
Olgu antud järjestussuhe (.
Elementide m1 ja m2 ülemrajaks on element m3 , kui m1 ( m3 ja m2 ( m3 .
Elementide m1 ja m2 alamrajaks on element m4 , kui m4 ( m1 ja m4 ( m2 .
Ülemraja on vähim, kui ta on väiksem suvalisest teisest ülemrajast.
Alamraja on suurim, kui ta on suurem suvalisest teisest alamrajast.
Võreks nimetatakse algebralist süsteemi < M, (, ( , ( >, kus ( on osalise järjestuse suhe hulgal M ning 2 suvalist elementi hulgast M omavad vähimat ülemraja ja suurimat alamraja.
Seejuures ( ja ( on üldistatud operatsioonid rajade leidmiseks, milliste lahtimõtestus on tunduvalt laiem kui lihtsalt hulgateoreetilised operatsioonid.
Näited.
1. Naturaalarvude hulk N; a ( b = min (a,b); a ( b = max (a,b), a ( b.
2. Hulk N; a ( b - SÜT; a ( b - VÜK; a ( b - b jagub a-ga.
3. Kahendvektorite hulk; (x1 ,x2 ,....,xn ) ( (y1 ,y2 ,....,yn) ( (xi ( yi );
X ( Y - X&Y (konjunktsioon) ; X ( Y - XVY (disjunktsioon).
4. Kõikvõimalike tükelduste hulk; P1 ( P2 - P1 ( P2 ; P1 ( P2 - P1 +P2 ;
P1 ( P2 - P1 ( P2 = P1 .
Boolei algebraks nimetatakse algebrat, mille signatuur koosneb 2 binaarsest operatsioonist + ja ( ning ühest unaarsest operatsioonist EMBED Equation.2 , kusjuures + ja ( on kommutatiivsed, assotsiatiivsed, idempotentsed ning teineteise suhtes distributiivsed ning eksisteerivad elemendid 0 ja 1, nii et x ( x = 0 ning x + x = 1.
Näited. {2A ,(,(, EMBED Equation.2 } - Cantori algebra.
{ (0,1)n ,&,V, EMBED Equation.2 } - loogikaalgebra.
Kaks algebrat on isomorfsed ( A1 = < M1 ,S1 > ( A2 = < M2 ,S2 > ), 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.
A={0,1,...,p-1}. Operatsioonid : +(mod p) ja x(mod p) (s.o. liitmine ja korrutamine mooduliga p). Kas selliselt kirjeldatud algabra on rühm?
A={1,2,3,4}. Ehitada kõikvõimalike tükelduste võre.
MATEMAATILINE LOOGIKA
Vaatleme loogikafunktsioone f(x1 ,x2 ,...xn), kus nii argumendid kui funktsiooni väärtus kuuluvad hulka {0,1}.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.
x1x2x3f(x1, x2, x3 )00000010010001111000101111011111
f(x1 , x2 , x3 )= EMBED Equation.2 x2x3 ( x1 EMBED Equation.2 x3 ( x1x2 EMBED Equation.2 ( x1x2x3
Erinevate loogikafunktsioonide f(x1 ,x2 ,...xn) arv K on EMBED Equation.2 .
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 ).
x1x2f0f1f2f3f4f5f6f7f8f9f10f11f12f13f14f15000000000011111111010000111100001111100011001100110011110101010101010101
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 EMBED Equation.2
f3 - argumendi x1 väärtus
f4 - pöördimplikatsiooni eitus EMBED Equation.2
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, EMBED Equation.2 ehk EMBED Equation.2 f9 - ekvivalentsi- ehk samaväärsusfunktsioon, x1 ( x2 ehk x1 ( x2
f10 - argumendi inversioon EMBED Equation.2
f11 - pöördimplikatsioon x2 ( x1
f12 - argumendi inversioon EMBED Equation.2
f13 - implikatsioon x1 ( x2
f14 - Shefferi kriips, Shefferi funktsioon, EMBED Equation.2 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 EMBED Equation.2
De Morgani seadused
EMBED Equation.2
Kleepimisseadused
EMBED Equation.2
Neeldumisseadused
EMBED Equation.2
Tehted konstantidega
EMBED Equation.2 EMBED Equation.2
x & 0 = 0 x ( 0 = x
x & 1 = x x ( 1 = 1
Lisateisendused
EMBED Equation.2
Näiteid (näidetes on antud algavaldis ja lõppresultaat pärast lihtsustamist)
EMBED Equation.2
Loogikafunktsiooni konstituent: EMBED Equation.2 , kus EMBED Equation.2
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 EMBED Equation.2 .
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:
EMBED Equation.2
Leida tõeväärtustabel alg- ja lõppavaldise jaoks. Veenduda lihtsustuse õigsuses.
Lihtsustada järgmised avaldised:
EMBED Equation.2
Tõestada DeMorgani seadused 3 muutuja jaoks nii tõeväärtustabeliga kui ka valemiliselt.
Antud kolme muutuja nn. mazhoritaarfunktsioon: EMBED Equation.2 . Tõestada, et kehtivad järgmised võrdused:
EMBED Equation.2
Loogikafunktsioonide normaalkujud
Loogikafunktsioon f(x1 , x2 ,..., xn ) võib olla esitatud erinevate valemite abil.
Näiteks EMBED Equation.2
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
EMBED Equation.2
Parempoolne valem on funktsiooni täielik DNK.
EMBED Equation.2
Parempoolne valem on funktsiooni täielik KNK.
EMBED Equation.2
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: EMBED Equation.2
Kasutatud näitefunktsiooni tõeväärtustabel on toodud järgnevas:
Nr.x1x2x3f(x1 ,x2 ,x3) EMBED Equation.2 000001100101201010301110410001510110611001711101
Minimaalse keerukusega DNK-d (KNK-d) nimetatakse minimaalseks DNK-ks (KNK-ks). Lühenditena vastvalt MDNK ja MKNK.
Ülesanne
EMBED Equation.2
Leida antud loogikafunktsiooni MDNK, MKNK, TDNK, TKNK.
Minimeerimine normaalkujude klassis
Boole'i ruum {0,1}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-üheselt ruumi {0,1}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 intervallid: {0},{1},{2},{3},{7},{0,1},{0,2},{1,3},{2,3},{3,7},{0,1,2,3}.
Maksimaalsed ühtede intevallid: {3,7},{0,1,2,3}.
Intervalle võime esitada baasis {0,1,-}
Näiteks: {1} ( 001 ( EMBED Equation.2
{0,1,2,3} ( 0-- ( EMBED Equation.2
{3,7} ( -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
Lihtimplikandid: {1,3} ( 0-1
{3,7} ( -11
{6,7} ( 11-
Taandatud DNK: EMBED Equation.2
Taandatud DNK võib sisaldada liiaseid liikmeid.
Eelmises näites esitatud funktsiooni MDNK on järgnev: EMBED Equation.2 .
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.
Vaatleme summaatorit, mis realiseerib liitmistehet F=A+B. A ja B kuuluvad hulka {0,1,2,3} ja on kodeeritud vastavalt kahendkujule {00,01,10,11} argumentidena a1 a2 ja b1 b2 . F({0,1,2,3,4,5,6} ja on kodeeritud {000,001,010,011,100,101,110} 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 )= EMBED Equation.2
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
1f(x1 ,x2 ,x3)= EMBED Equation.2 - minimaalne DNK
f(x1 ,x2 ,x3)= EMBED Equation.2 - 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)= EMBED Equation.2 - minimaalne DNK
f(x1 ,x2 ,x3)= EMBED Equation.2 - 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)= EMBED Equation.2 - minimaalne DNK
f(x1 ,x2 ,x3, x4)= EMBED Equation.2 - 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)= EMBED Equation.2 - 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)= EMBED Equation.2 - minimaalne DNK
f(x1 ,x2 ,x3, x4)= EMBED Equation.2 - 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)= EMBED Equation.2 - minimaalne DNK
f(x1 ,x2 ,x3, x4, x5)= EMBED Equation.2 - 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)= EMBED Equation.2
Leida Karnaugh' kaardiga MDNK ja MKNK.
Kontrollvastus: f(x1 ,x2 ,x3, x4)= EMBED Equation.2
Antud nelja muutuja loogikafunktsioon:
f(x1 ,x2 ,x3, x4)= EMBED Equation.2
Leida Karnaugh' kaardiga MDNK ja MKNK.
Kontrollvastus: f(x1 ,x2 ,x3, x4)= EMBED Equation.2
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)= EMBED Equation.2
f1(x1 ,x2 ,x3, x4)= EMBED Equation.2
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)= EMBED Equation.2
f1(x1 ,x2 ,x3, x4)= EMBED Equation.2
Leida minimaalse DNK-ga f2(x1 ,x2 ,x3, x4).
Antud nelja muutuja funktsioon F(x1 ,x2 ,x3, x4)= EMBED Equation.2 . 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 ) = EMBED Equation.2
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
IndeksIntervallMärgeIndeksIntervallMärgeIndeksIntervallMärge00000x0-1000-x0-1-1-2-00-A410001x00-0x-0-0A50010x-000x1-2-2-3--10A61000x1-20-01A120101x-001x0110x0-10x1001x-010x1010x100-x30111x10-0x1110x2-301-1A2011-A3-110x1-10x
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.012567891014A1xxA2xxA3xxA4xxx(A5xxxxA6xxx(
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 = EMBED Equation.2
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ärgeInd.Nr.-dVaheMärgeInd.Nr.-dVaheMärge00x0-10-11x0-1-1-20-1-8-91,8A411x0-22x0-2-8-102,8A52x0-88x1-2-2-32-6-10-144,8A68x1-21-54A125x1-98x6x2-64x9x2-108x10x8-91x37x8-102x14x2-35-72A26-71A36-148x10-144x
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.
LihtimplikantVahedx1x2x3x4KonjunktsioonA2201-1 EMBED Equation.2 A41,8-00- EMBED Equation.2 A64,8--10 EMBED Equation.2
f(x1 ,x2 ,x3, x4 ) = A4 ( A6 ( A2 = EMBED Equation.2
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 EMBED Equation.2 .
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ärgeInd.Nr.-dVaheMärgeInd.Nr.-dVaheMärge12x1-22-64x1-2-2-32-6-10-144,8A425x2-108x6x2-35-78A110x6-74A237x6-148x11x10-114A314x10-148x
2.etapp - lihtimplikantide hulga minimeerimine
Impl.2567101114A1(xA2xxA3x(A4(xx(
Kohustuslikud intervallid A1(vektor 5), A3 (vektor 11) ja A4 (vektorid 2 ja 14) katavad kogu nullide piirkonna. Elementaarkonjunktsioonide leidmine toimub analoogiliselt eelpool tooduga
LihtimplikantVahedx1x2x3x4DisjunktsioonA1201-1 EMBED Equation.2 A31101- EMBED Equation.2 A44,8--10 EMBED Equation.2
f(x1 ,x2 ,x3, x4 ) = EMBED Equation.2 EMBED Equation.2 EMBED Equation.2
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ärgeInd.Nr.-dVaheMärgeInd.Nr.-dVaheMärge00x0-10-22x0-1-1-20-2-8-102,8A112x0-44x0-4-8-124,8A24x0-88x1-2-2-34-5-12-131,8A38x1-22-108x25*x4-51x10x4-128x12x8-102x313*x8-124x415*x2-35-13*8x12-131x3-413-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.02481012A1x(x(A2xxxxA3xx
Kohustuslik on intervall A1(vektorid 4 ja 10). Katmata jäänud punktide 4 ja 12 jaoks sobib kas implikant A2 või implikant A3.
LihtimplikantVahedx1x2x3x4KonjunktsioonA12,8-0-0 EMBED Equation.2 A24,8--00 EMBED Equation.2 A31,8-10- EMBED Equation.2
Antud funktsiooni jaoks eksisteerib kaks keerukuselt võrdväärset lahendit:
f 1(x1 ,x2 ,x3, x4 ) = A1 ( A2 = EMBED Equation.2 ( EMBED Equation.2
f 2(x1 ,x2 ,x3, x4 ) = A1 ( A3 = EMBED Equation.2 ( EMBED Equation.2
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 | << | V- |;
funktsiooni argumentide arv on suur;
V1 ja V0 on esitatud intervallide kujul.
Selliste omadustega ja selliselt esitatud funktsioonide minimeerimiseks ei sobi ei Karnaugh' kaart ega McCluskey meetod.
Nõrgalt määratud funktsioonide minimeerimisel (DNK klassis) on võimalik kasutada heuristilist meetodit, mille puhul laiendatakse funktsiooni ühtede intervalle (argumentide vabastamise teel) nii, et ükski ühtede intervall ei omaks ühisosa ühegi nullide intervalliga.
Sellisel laiendusel võib abivahendina kasutada nn. ortogonaalsusfunktsiooni #, mis on kirjeldatud järgnevalt:
#01-00101100-000
Rakendatuna intervallide paarile näitab funktsioon #, milliste argumentide järgi on intervallid ortogonaalsed (s.o. teatud argument on ühes intrvallis 0, teises 1). Kahte intervalli nimetame mittekattuvateks, kui nad on ortogonaalsed vähemalt ühe argumendi järgi. Kui intervallid on ortogonaalsed mitme argumendi järgi, võib osa argumente vabastada (s.o intervalli suurendada ehk vastavat konjunktsiooni lühendada).
Näide 1
f(x1 ,x2 ,x3, x4 ) = EMBED Equation.2
Analüüsime kõikide intervallipaaride ortogonaalsust.
Nullide int.
Ühtede int.-
1
0
01
0
1
10
0
0
-0
1
0
01
0
1
00
-
0
10
0
0
11
0
1
0
Intervallid 000- ja -100 on ortogonaalsed argumendi x2 järgi. Järelikult intervalli 000- laiendamisel peab x2 säilitama oma väärtuse (x2 =0). Intervall 000- on ortogonaalne intervalliga 1011 argumentide x1 ja x3 järgi. Järelikult peab säilitama oma väärtuse kas x1 =0 või x3 =0 ning intervalli 000- laienduseks võivad olla intervallid 00-- või -00-. Analoogselt laiendame intevalli 0-01. Võimalikud laiendused on 0--1 või --01. Valime lahendisse esimesena märgitud laiendused:
f(x1 ,x2 ,x3, x4 ) = EMBED Equation.2
ehk
f(x1 ,x2 ,x3, x4 ) = EMBED Equation.2
Ülesanne
Proovige sama funktsiooni minimeerida teiste Teile tuntud minimeerimismeetoditega. Selgitage endale kirjeldatud heuristilise meetodi olemus.
Näide 2
f(x1 ,x2 ,x3, x4 ,x5) = EMBED Equation.2
Minimeerige funktsioon kõigi tuntud meetoditega. Hinnake, milline meetod sobib kõige paremini.
Kontrolllahendus: funktsioon jääb sõltuma kolmest argumendist f(x1 ,x2 ,x3) = EMBED Equation.2 .
Näide 3
f(x1 ,x2 ,x3, x4 ,x5 ,x6 )= EMBED Equation.2
Leida minimaalne DNK (kontrolllahend: EMBED Equation.2 ) ja minimaalne KNK. Seejuures märgime, et KNK leidmine toimub samade ideede alusel, kusjuures laiendatakse maksimaalselt nullide intervalle, garanteerides seejuures mittekattuvus ühtede intervallidega.
Loogikafunktsioonide täielik süsteem
Eelnevast on teada, et suvaline loogikafunktsioon on esitatav DNK ja KNK kujul. Järelikult on suvaline funktsioon kujutatav läbi funktsioonide &, V ja EMBED Equation.2 .
Loogikafunktsioonide süsteemi, mille abil on võimalik kujutada suvalise keerukusega loogikafunktsiooni, nimetatakse täielikuks süsteemiks.
Olgu antud loogikafunktsioonide süsteem S:
S={ f1(x1 ,x2 ,..... ,xn1 ), f2(x1 ,x2 ,..... ,xn2 ),...., fm(x1 ,x2 ,..... ,xnm )}
Süsteemi S superpositsiooniks nimetatakse funktsiooni f, mis on saadud süsteemi S funktsioonidest järgnevalt:
funktsiooni fi ( S muutujate ümbernimetamisega;
funktsiooni fj ( S mõne muutuja asendamisega funktsiooniga fk ( S ;
eelneva kahe tegevuse korduval rakendamisel.
Süsteemi S nimetatakse täielikuks, kui suvaline funktsioon f(x1 ,x2 ,..... ,xn ) on esitatav läbi süsteemi S superpositsiooni.
Täielik süsteem S on baassüsteem, kui tema täielikkus kaob suvalise funktsiooni fi ( S eemaldamisel süsteemist S.
Süsteemi S täielikkuse analüüs nõuab järgneva viie funktsioonide klassi defineerimist. Kasutame iga klassi illustreerimisel eelpööl kirjeldatud kahe muutuja funktsioonide
hulka { f0, f1, f2, ... , f15 }
Klass K0 - nulli säilitavate loogikafunktsioonide klass.
K0 ={ fi(x1 ,x2 ,..... ,xn ) | fi(0,0,...,0 ) = 0}
{ f0, f1, f2, f3, f4, f5, f6, f7 } ( K0
Klass K1 - ühte säilitavate loogikafunktsioonide klass.
K1 ={ fi(x1 ,x2 ,..... ,xn ) | fi(1,1,....,1 ) = 1}
{ f1, f3, f5, f7, f9, f11, f13, f15 } ( K1
Klass Klin - lineaarsete loogikafunktsioonide klass.
Klin ={ fi(x1 ,x2 ,..... ,xn ) | fi(x1 ,x2 ,..... ,xn )= c0 ( c1x1 ( c2x2 ( .... ( cnxn }, kus ci( {0,1}
Seega iga lineaarse funktsiooni jaoks eksisteerib selline kahendvektor {c0 ,c1, c2, ...., cn }, et funktsioon on esitatav definitsioonis toodud lineaarpolünoomina. Kõikvõimalikest
n-argumendi loogikafunktsioonidest on lineaarseid funktsioone 2n+1 .
{ f0, f3, f5, f6, f9, f10, f12, f15 } ( Klin
Klass Kd - iseendaga duaalsete funktsioonide klass
Kaks loogikafunktsioonid fi(x1 ,x2 ,..... ,xn ) ja fj(x1 ,x2 ,..... ,xn ) on omavahel duaalsed, kui
fi(x1 ,x2 ,..... ,xn )= EMBED Equation.2
Kd = { fi(x1 ,x2 ,..... ,xn ) ( fi(x1 ,x2 ,..... ,xn )= EMBED Equation.2 }
{ f3, f5, f10, f12 } ( Kd
Klass Kmon - monotoonsete loogikafunktsioonide klass
Kmon = { fi(x1 ,x2 ,..... ,xn ) ( EMBED Equation.2 }
Iga loogikafunktsioon, mis ei sisalda DNK kujus inversioone, on monotoonne ning vastupidi, iga monotoonne loogikafunktsioon on esitatav DNK-na, mis ei sisalda inversioone.
{ f0, f1, f3, f5, f7, f15 } ( Kmon
Loogikafunktsioonide klass S on suletud, kui suvaline selle klassi funktsioonide superpositsioon kuulub samuti klassi S.
Klassid Klin ja Kmon on suletud klassid.
Süsteem S on nõrgalt täielik, kui ta võimaldab pärast konstantfunktsioonide f0=0 ja f15=1 lisamist esitada suvalist funktsiooni fi(x1 ,x2 ,..... ,xn ) läbi süsteemi {S, f0, f15} superpositsiooni.
Selleks, et süsteem S oleks nõrgalt täielik, on piisav ja tarvilik, et ta sisaldaks ühte mittemonotoonset ja ühte mittelineaarset funktsiooni.
Näiteks süsteem {&,(} on nõrgalt täielik, kuna & on mittelineaarne ja ( mittemonotoonne.
Selleks, et süsteem S oleks tugevalt täielik (edasises täielik), on piisav ja tarvilik, et ta sisaldaks nulli mittesäilitavat funktsiooni, ühte mittesäilitavat funktsiooni, mittelineaarset funktsiooni, mittemonotoonset funktsiooni ja iseendaga mitteduaalset funktsiooni.
Märgime, et kuna f0 on ühte mittesäilitav, f15 nulli mittesäilitav ning mõlemad funktsioonid on iseendaga mitteduaalsed, siis muutub nõrgalt täielik süsteem (sisaldab mittelineaarset ja mittemonotoonset funktsiooni) täielikuks f0 ja f15 lisamisel.
Baassüsteemid
Vaatleme kõigi kahe muutuja funktsioonide hulga alamhulka:
{ f0, f1, f6, f7, f8, f12, f13, f14, f15 } .
Toodud alamhulgas on esindatud kõik tähtsamad funktsioonid. Järgnevas toome välja kõik baassüsteemid, mis on võimalik moodustada nimetatud alamhulga funktsioonidest.
Funktsioonid f8 (Pierce'i funktsioon) ja f14 (Shefferi funktsioon) ei kuulu ühtegi eelpool vaadeldud viiest funktsioonide klassist. Järelikult on võimalik moodustada kaks ühe funktsioonilist baassüsteemi:
Pierce'i baas B1 ={ f8 }
Shefferi baas B2 ={ f14 }
Ülejäänud funktsioonide baasil on võimalik klassidesse mittekuuluvuse alusel moodustada veel seitse baassüsteemi.
Konjunktiivne baas B3 ={ f1 , f12 }
Disjunktiivne baas B4 ={ f7 , f12 }
Implikatiivsed baasid B5 ={ f12 , f13 }, B6 ={ f0 , f13 }, B7 ={ f6 , f13 }
Read-Mülleri baas (Zhegalkini baas) B8 ={ f1 , f6 , f15 }
B9 ={ f6 , f7 , f15 }
Baaside leidmiseks võib kasutada katteülesande modifikatsiooni, kus veergudeks on vastavasse klassi mittekuuluvus, ridadeks aga vaadeldav funktsioonide alamhulk. Baassüsteemi moodustavad funktsioonid (read), mis katavad mittekuuluvuse kõigisse viide klassi.
Loogikafunktsiooni esitamine baassüsteemides
Olgu antud funktsioon DNK kujul (või KNK kujul):
EMBED Equation.2
Esitame funktsiooni f(x1, x2, x3) baassüsteemides B1 kuni B9 .
B1 ={ f8 }
Teisenduseks on sobivaim lähtuda KNK-st, inverteerida funktsiooni kahekordselt ning rakendada De Morgani seadust.
Resultaat: f(x1, x2, x3) = EMBED Equation.2
B2 ={ f14 }
Teisenduseks sobib funktsiooni DNK-d inverteerida kahekordselt ja rakendada De Morgani seadust.
Resultaat: f(x1, x2, x3) = EMBED Equation.2
B3 ={ f1 , f12 }
Lähtuda võib suvalisest normaalkujust, ellimineerides mittelubatud disjunktsiooni. Erinevus baasist B2 seisneb selles, et baas B3 lubab kasutada "puhast" konjunktsiooni (ilma inversioonita).
Resultaat: f(x1, x2, x3) = EMBED Equation.2
B4 ={ f7 , f12 }
Teisendus analoogiline teisendusega baassüsteemi B3 . Erinevusena baasist B1 märgime "puhta" disjunktsiooni kasutamise võimalust.
Resultaat: f(x1, x2, x3) = EMBED Equation.2
B5 ={ f12 , f13 }
Teisenduseks kasutame järgmisi abivalemeid:
EMBED Equation.2
Resultaat: f(x1, x2, x3) = EMBED Equation.2
Märgime, et resultaadi minimaalsus sõltub DNK liikmete paigutusest ja asenduste sooritamise järjekorrast.
B6 ={ f0 , f13 }
Kasulikud on järgmised abivalemid:
EMBED Equation.2
Resultaat: f(x1, x2, x3) = EMBED Equation.2 EMBED Equation.2
B7 ={ f6 , f13 }
Teisendus sellesse baassüsteemi on eelneva põhjal iseseisvaks tööks.
B8 ={ f1 , f6 , f15 }
Read-Mülleri ehk Zhegalkini baasile vastab algebra, kus kehtivad järgnevad seosed:
Kommutatiivsus: x1( x2 = x2 ( x1
Distributiivsus: x1 & (x2 ( x3 )= x1 x2 ( x1 x3
x1 ( (x2 ( x2 ) = x1
Teisendusel kasulikud abivalemid:
EMBED Equation.2
Resultaat: f(x1, x2, x3) = x1 x2 x3 ( x1 x3 ( x2 x3 ( x1 ( x3
Kui vaadeldavas algebras analoogiliselt eelmise näitega avada sulud, saame normaalkuju sarnase avaldise, kus disjunktsiooni asemel kasutatakse funktsiooni ( ja puuduvad argumentide inversioonid. See on loogikafunktsiooni Read-Mülleri polünoom.
Iga loogikafunktsiooni jaoks eksisteerib täpselt 1 Read-Mülleri polünoom (analoogiliselt täielike DNK ja KNK-ga).
Märgime, et kui fi & fj = 0, siis fi ( fj = fi ( fj . See seos annab võimaluse meile tuntud meetoditega tuletada Read-Mülleri polünoom näiteks Karnaugh' kaardilt. Selleks on vaja kontuuride moodustamisel mitte lubada nende kattumist (kattumine tähendaks seda, et eksisteerib sisendvektor, mis muudab "1"-ks mõlemale kontuurile vastavad konjunktsioonid). Mittekattuvad kontuurid esitavad Read-Mülleri polünoomiks sobivaid konjunktsioone, millistes aga on osa argumente inverteeritud. Korrektse Read-Mülleri polünoomi saamiseks peame inversioonid abivalemiga asendama ning sulud lõplikult avama.
Näide
EMBED Equation.2
B9 ={ f6 , f7 , f15 }
Teisendus jääb eelneva põhjal iseseisvaks tööks.
Ülesanded
Esitada funktsioon f(x1 ,x2 ,x3, x4 ) = ((0,1,4,5,6,12,14)1 baassüsteemides B1 kuni B9 .
Kontrollida, kas järgmised loogikafunktsiooide süsteemid on täielikud. Kas nad kujutavad baassüsteeme? Kui mõni süsteem pole täielik, näidata mitte täielikkuse põhjus.
{ f0 , f1 , f9 }
{ f9 , f12 , f13 }
{ f6 , f7}
{ f1 , f7 , f13 }
{ f0 , f6 , f12 , f15 }
{ f(x1 ,x2 ,x3, x4 ) = ((0,3,7,11,13)1 }
EMBED Equation.2
Tuua näiteks kolme muutuja loogikafunktsioon, mis on:
- monotoonne ja lineaarne;
- iseendaga duaalne ja lineaarne.
Antud nelja muutuja loogikafunktsioon :
f(x1 ,x2 ,x3, x4 ) = EMBED Equation.2
Leida funktsiooni f(x1 ,x2 ,x3, x4 ) minimaalsed DNK ja KNK ning kümnendesitusvorm.
Esitada funktsioon f(x1 ,x2 ,x3, x4 ) baassüsteemides B1 , B5 ja B9 .
Loogikafunktsioonide Shannoni arendus
Loogikafunktsiooni täielik arendus annab resultaadina täieliku DNK (või KNK).
Arendusvalemid:
Täielik disjunktiivne arendus
EMBED Equation.2
2. Täielik konjunktiivne arendus
EMBED Equation.2
Näide
Antud loogikafunktsioon f(x1, x2, x3)= EMBED Equation.2
Täielik disjunktiivne arendus:
f(x1, x2, x3) = EMBED Equation.2 EMBED Equation.2 EMBED Equation.2 EMBED Equation.2
EMBED Equation.2 EMBED Equation.2 EMBED Equation.2 EMBED Equation.2 =
= EMBED Equation.2
Täielik konjunktiivne arendus:
f(x1, x2, x3)= EMBED Equation.2
Osaline disjunktiivne arendus argumentide (x1, x2,..., xk ) järgi:
EMBED Equation.2
4. Osaline konjunktiivne arendus argumentide (x1, x2,..., xk ) järgi:
EMBED Equation.2
Näide
Antud loogikafunktsioon f(x1, x2, x3, x4)= EMBED Equation.2
Disjunktiivne arendus argumendi x1 järgi: EMBED Equation.2
Disjunktiivne arendus argumendi x2 järgi: EMBED Equation.2
Disjunktiivne arendus argumendipaari (x1 x2 )järgi: EMBED Equation.2
Konjunktiivne arendus argumendi x1 järgi: EMBED Equation.2
Sulgudes arendusargumentide järel on nn. jääkfunktsioonid. Jääkfunktsioon näitab, milliseks muutub vaadeldav funktsioon, kui arendusargumentidele on omistatud konstantsed väärtused.
Loogikafunktsiooni tuletis
Loogikafunktsiooni f(x1, x2,..., xn) tuletis argumendi xi on määratud järgmise valemiga:
EMBED Equation.2
Näide
Antud loogikafunktsioon f(x1, x2, x3, x4) = ( (3,4,5,6,7,8,10,12,14)1
EMBED Equation.2
Loogikafunktsiooni tuletis argumendi xi järgi määrab loogikatingimused, milliste puhul funktsiooni väärtus on tundlik argumendi xi muutuste suhtes (kas otse- või vastandfaasis).
Ülesanded
Antud loogikafunktsioon f(x1, x2, x3, x4) = EMBED Equation.2
Leida Shannoni osaline disjunktiivne arendus argumendipaari (x1,x4) järgi ja konjunktiivne arendus argumendipaari (x2,x3) järgi.
Antud loogikafunktsioon f(x1, x2, x3, x4) = ( (0,1,2,4,7,8,11,15)1
Leida funktsiooni tuletis EMBED Equation.2
PAGE
PAGE 1
. õ : J K U V [ \ h i Ø © ½ ¾ Ń Ņ Ó Ō Ż Ž ć ä š ń 0 1 6 7 C D h i s t z { ¢ £ Ā Ä ó 6 7 9 : A B C D G H O P Q l ś÷ń ķ é å į į Ż å į į Ų ČæŲ å į » å į » · å į » » į µ ķ ³ é é Æ Ż ŻÆ j Aš 5H* j Dš j Ļš jP¬×6
EHü’U jP¬×6
CJ UVmH nH u j U j Ēš j Īš j |š j Čš 5>*
5>*CJ CJ
5>*CJ$ E - . i č é ö ÷ ų V 9 : H p ° ½ # K ż ż ż ż ų ų ų ų ų ż ż ż ż ż ż ż ż ż ż ż ó ż ó ż ó ż ó ż
&