Diskreetne matemaatika - konspekt (11)

AIY3310 Diskreetne matemaatika
Lühikonspekt
Käesolev lühikonspekt katab suure osa aines AIY3310 (endise koodiga 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 È

• Hulkade ühisosa (lõige)
  

A Ç, kus I on nn. universaalhulk .

• Hulkade vahe
  

A \

• Hulkade sümmeetriline vahe
  

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

• Kommutatiivsusseadused
  

A È B = B È A
A Ç B = B ÇA

• 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 = A

• Välistatud kolmanda seadused
  

A È
= I
A Ç
= Æ

• Topelttäiendi seadus
  

= A

• 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 D 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 D 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 j hulga B elementidega.
j Ì A x B j : A ® B
Vastavuse määramispiirkond ( domain ):
D(j)
Vastavuse muutumispiirkond (range):
R(j)
Vastavuse täiend:
= Pöördvastavus: < Ì BxA | | = |j|
Vastavuste ühend ja ühisosa:
j1 Ç
j1 È
Vastavuste kompositsioonitehe:< ,kus
j1 Ì AxB ja j2 Ì BxC.
Kompositsioonitehe on assotsiatiivse iseloomuga .
Vastavuste klassifikatsioon
Vastavus j Ì AxB on kõikjal määratud, kui D(j) = A.
Vastavus j Ì AxB on kõikjale määratud, kui R(j)=B.
Vastavus j Ì AxB on ühene, kui j-1 o j Ì.
Vastavus j Ì AxB on üks-ühene, kui j-1 o j Ì ja
j o j-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 j - eksamil tudengi poolt saadud hinne. Millistel tingimustel on j osaliselt määratud funktsioon; täielikult määratud funktsioon; sürjektsioon; injektsioon; bijektsioon?
BINAARSUHTED
Meie poolt vaadeldavad binaarsuhteid võib käsitleda kui vastavuse j erijuhtu, kus lähte- ja sihthulk langavad kokku (D(j)=R(j)=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 (a1 ) - ( "aÎA [ÎR] ).
  
• Antirefleksiivsus (a2 ) - ( "aÎA [ÏR]).
  

Suhe, mis ei täida nõudeid a1 ega a2 , on mitterefleksiivne.

• Sümmeetria (a3 ) - ( "a,bÎA [ÎR ® ÎR]), kus a ¹ b.
  
• Antisümmeetria (a4 ) - ( "a,bÎA [ÎR ® ÏR]), kus a ¹ b.
  

Suhe, mis ei täida nõudeid a3 ega a4 , on mittesümmeetriline.

• Transitiivsus (a5 ) - ("a,b,cÎA [(ÎR & ÎR) ® ÎR]), kus a¹b, b¹c, a¹c.
  
• Antitransitiivsus (a6 ) - ("a,b,cÎA [(ÎR & ÎR) ® ÏR]), kus a¹b,b¹c,a¹c.
  

Suhe, mis ei täida nõudeid a5 ega a6 , on mittetransitiivne.

• d(R,ai ) - suhte R kaugus omaduseni ai , s.o. seoste arv, mis tuleb minimaalselt lisada suhtesse R (või eemaldada suhtest R), et saavatada omadust ai.
  
• 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