Hulgateooria põhimõisted (0)

Hulgateooria põhimõisted
Hulk on baasterminiks nii matemaatikas kui ka arvutiteaduses.
Järgnevalt tuvume hulgateooria põhikontseptsioonidega ja hulkadele rakendatavate operatsioonidega.
Paradoks:

Habemeajaja puzle- kapten käsib rühma habemeajajale ajada habet kõikidel kompanii liikmetel, eeldusel et rühma liikmed ei tohi ise habet ajada. Olles kõigi teiste habemed ajanud, kasvab talle endale habe. Enda habet ei saa ta ajada, sest nii rikuks ta kapteni käsku. Kui ta aga enda habet ei aja, siis ta peaks ühtpidi kapteni käsu järgi enda habet ajama (kõikidel liikmetel).
Def: Hulk A on kollektsioon korrektselt defineeritud objektidest , nii et iga objekti korral kehtib üks järgevast kahest võimalusest

• x kuulub hulka A , kirjutame x A
  
• x ei kuulu hulka A , kirjutame x A
  

Hulki tähistame suurte tähtedega ja nende elemente väikeste tähtedega.
Tühihulk Ø
Näited hulkada defineerimisest ja kasutamisest
N1. Antud hulgad
a)
-1 ja 1
b)
tühihulk
Millised on nende hulkade elemendid ( loetleda ).
N2. Antud on hulkade elemendid
a)
b)
defineerida vastavad hulgad
Vaatleme kahte hulka A ja B.
Def. Hulka A nimetame hulga B alamhulgaks (), siis ja ainult siis kui iga hulga A element on ka hulga B element.
tähendab, et
järeldub
Proper subset-alamhulk mis ei ühti hulgaga kuhu ta kuulub.
ehk tähendab et
ja AB.
N3. Antud on hulgad ,
ja
Millesed antud hulkadest on mingi teise alamhulgad.
Def. Juhul kui hulgad A ja B on kujutatud piirkonnana tasandil nimetatakse nendevahelist seost Venni diagrammiks.

A
B
Kaks hulka A ja B on võrdsed kui ja
N4: Kas järgmised hulgad on võrdsed (põhjendada miks)

<
<}}
N- naturaalarvud
Z-täisarvud
R- reaalarvud
Q-ratsionaalarvud
C-kompleksarvud
Kehtib:
Lõplik hulk- kindel arv elemente (on alati ka loenduv )
Lõpmatu hulk-piiramata arv elemente
Loenduv hulk- kui tema elementidele saab seada vastavusse naturaalarvude hulga
Def. Olgu U universaalhulk, A ja B tema alamhulgad. Hulga A täiendiks ehk absoluutseks täiendiks nimetatakse hulka
N5: Antud on universaalhulk
ja hulk .
Leida hulga A täiend. (E,T,K,N,R)

Def. Kahe hulga X ja Y ühisosa
Def. Kahe hulga X ja Y ühend
N6: Antud on hulgad ,
ja
a)Leida
ja , millised on neist hulkadest võrdsed?<<=A<<{a,b,c,e}=A
b)Leida
ja , millised on neist hulkadest võrdsed?
Def. Hulkade B ja A vaheks nimetatakse hulka
kirjanduses tähistatakse vahet ka B\A
N7: Leida A-(B-C) ja (A-B)-C. Kas need hulgad on võrdsed?
Def. Hulkade A ja B sümmeetriline vahe AB on hulk<
B\<
Def. n-korteež on objektide lõplik jada
Korteeži erinevused hulgast:

• üks ja seesama objekt saab esineda korteezis mitu korda
  
• objektid esinevad korteezis kindlas järjekorras
  

Kahte korteezi () ja () on võrdsed siis ja ainult siis kui
, ,....,.
Def. Antud n hulga
Cartesiuse korrutiseks ehk ristkorrutiseks
nimetame hulka, otsekorrutis
N9: Antud on hulgad ,
ja
Leida
ja .<<
Def. Tähestikuks ehk alfabeediks nimetame lõplikku mittetühja hulka , mille liikmeteks on tähed. Täpsustame, et tähestik ei pruugi koosned sugugi mitte ainult (või üldse) tähtedest. Tähestiku liikmeteks võivad olla suvalised sümbolid (ühikud), lihtsuse mõttes kutsume neid edaspidi siiski tähtedeks. (seega tähed on ka 0, 7 # jne.).
Def. Sõna on lõplik string tähestiku
tähtedest.
Kogu tähestiku
tähtedest moodustatud sõnade hulka tähistame
Def. Sõnade hulga
iga alamhulk on keel (formaalne keel).
N10: Tähestikus on ainult üks täht
Keel koosneb kõikvõimalikest mittetühjadest tähestiku abil moodustatud stringidest:
Keele saame ka teisiti esitada:
Def. Sõna pikkuseks nimetame tähestiku tähtede arvu sõnas ja tähistame
N11: Olgu
Loetleda kõik hulga A elemendid kui
(sõnapikkus on kaks)
aa,ab,ba,bb
Nimetatakse formaalseks keeleks , nendel puudub keeleline tähendus nagu inglise eesti jne keeled
Hulkadega teostatavate 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 ) esimeseks märgiks tuleb esimene märk
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 )
  

Def. Hulga A mittetü nimetatakse hulga A partitsiooniks siis ja ainult siis kui
Ø kõigi
korral.
N12: Antud on hulgad ,
ja
Nä on hulga A partitsioon .
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 
N13: leida järgmiste hulkade elementide arv ehk võimsus (cardinality)

Ø

<
<}}

| Ø |=0

|{Ø}|=1 kui hulga sees on tühihulk, siis selle võimsust loetakse 1

|{}}|=3
.................................
Def: Hulga A astmehulgaks
nimetatakse selle hulga kõiki alamhulki koos tühja hulgaga.
N14: Leida hulga
astmehulk
................P(A)}.........
N15: Tõestada indukstiooni meetodil, et kui
siis astmehulgas on elemente ).
n=0 siis A= Ø ja P(A) |P(A)|=1=20
eeldame et kehtib n=k korral: < |P(Ak)|= 2k
Tõestame, et kehtin n=k+1 korral
lisasime d<
Hulgale Ak+1 vastava astmehulga saamiseks võtame hulgale Ak vastava astmehulga ja lisame sellele paarid mis saame Ak astmehulga hulkade ja lisatava uue elemendi abil moodustada
Seega : |P(Ak+1)|= |P(Ak)|+ |P(Ak)|= 2k+2k=2*2k=2k+1
tõestatud
Booli algebra
Booli algebraks nimetame mittetühja hulka S koos kahe operatsiooniga
ja סּ mis rahuldavad järgmisi tingimusi :
Et järgnev liiga abstraktne ja keeruline ei tunduks võite esialgu kujutada ette
Hulga S rollis reaalarvude hulka ja tehete rollis liitmise ning korrutamise tehet.
Viimasel juhul on tegemist küll Booli algebra ühe erijuhuga, kuid kõik omadused on sel juhul väga lihtsad ja selged.
kui a,bS, siis abS ja aסּbS
Iga a,bS, korral kehtib(kommutatiivsus):
ab= ba ja aסּb= bסּa
Iga a,b,cS, korral kehtib (assotsiatiivsus):
a(bc)= (ab)c ja aסּ (bסּc)= (aסּb) סּc
Iga a,b,cS, korral kehtib (distributiivsus):
a(bסּc)= (ab) סּ(ac) ja aסּ (bc)= (aסּb) (a סּc)
Eksisteerivad elemendid 0 ja 1 nii et iga aS, korral kehtib:
a0=a ja aסּ1=a
Iga aS jaoks eksisteerib selline (a täiend või eitus), et kehtib
a=1 ja aסּ=0
Booli algebrat tähistatakse (S, ,סּ).
Leida ühisosa, hulkade liitmine lahutamine,