Halmazok-előadás vázlat

Diszkrét matematika Halmazok-előadás vázlat Naiv halmazelmélet:. Mi a halmaz? Mit jelent, hogy ”valami” eleme a halmaznak? Igaz-e, hogy a halmaz elemei valamilyen kapcsolatban állnak egymással? Jelölés: a∈A azt jelenti, hogy az a eleme az A halmaznak. (Az a az A halmazhoz tartozik.) Mit jelent a∉A? Azt követeljük meg, hogy a halmazt az elemei egyértelműen meghatározzák: Csak olyan halmazokkal foglalkozunk, amelyeknél a∈A állítás igazsága egyszersmind a∉A állítás hamis voltát vonja maga után, illetve az a∉A állítás igaz voltából az a∈A állítás hamissága következik. Az alábbi, ún. antinomiák (2. antinomia később) indokolják, miért szükséges a fenti furcsa kikötés: 1. Antinomia: Tekintsük a magyar nyelven legfeljebb 100 karakterrel definiálható egész számok halmazát, jelöljük ezt H-val. Legyen az n egész szám definíciója az alábbi: A legkisebb, magyar nyelven száz írásjellel (a szóközt beleértve) nem definiálható természetes szám. (A fenti mondat pontosan 100 karakter) Vajon n∈H igaz, vagy n∉H? Halmazok megadása, példák: -

felsorolás : A:={3, 4} valamely tulajdonság megadása (részhalmaz, ld. később): B:={x| x∈R, x megoldása az (x-3)(x-4)=0 egyenletnek}

Definíció: Az A és a B halmazok egyenlők, ha ugyanazok az elemeik. Nyilván a fenti példákban A=B.

1 © Bércesné Novák Ágnes

Diszkrét matematika Definíció: Üres halmaznak nevezzük azt a halmazt, amely egy elemet sem tartalmaz. Jele:∅. Definíció: Az A halmaz részhalmaza a B halmaznak, ha A minden eleme B-nek is eleme. Jelölés: A⊆B. Ha A⊆B és A≠B, akkor azt mondjuk, hogy A valódi részhalmaza B-nek. Jelölés: A ⊂B. A definíció szerint minden halmaz részhalmaza önmagának: A⊆A reflexív A részhalmaz definícióját átfogalmazhatjuk úgy is, hogy A⊆B , ha A-nak nincsen olyan eleme, amely ne lenne B-nek is eleme. Ennélfogva ∅ ⊆ A, hiszen nincsen eleme. Igaz-e, ha A⊆B és B⊆C, akkor A⊆C ? (tranzitivitás) Igaz-e, ha A⊆B, akkor B⊆A? (kommutativitás) 2. Antinomia (Russel): Elképzelhető, hogy vannak olyan halmazok, amelyek önmagukat tartalmazzák. Ugyanígy, vannak olyan halmazok, amelyek önmagukat nem tartalmazzák. Legyen a H halmaz azon halmazok halmaza, amelyek önmagukat nem tartalmazzák. Vajon H eleme-e önmagának? Mondjunk példát olyan halmazra, amelyik tartalmazza önmagát! Példa: ∅ ⊆∅ A⊆B tulajdonságai: reflexív: A⊆A tranzitív: A⊆B és B⊆C, akkor A⊆C NEM kommutatív 1. Állítás: A=B akkor és csak akkor, ha A⊆B és B⊆A. Ez az állítás használható halmazok azonosságának bizonyítására. Definíció: Az A halmaz P(A) hatványhalmazán az A részhalmazainak halmazát értjük.


Diszkrét matematika Példák: A:= {1, 2}, P(A)={∅,{1},{2},{1,2}} P(∅)={∅} P({∅})={∅,{∅}} Feladatok: -

Adja meg a B:= {∅,{1}} halmaz hatványhalmazát! Adja meg a C:= {{1}, C} halmaz hatványhalmazát! Műveletek halmazok között

Definíció: Az A és B halmazok egyesítése (uniója, összege) az az A∪B-vel jelölt halmaz, amelynek elemei vagy A-nak, vagy B-nek elemei. A∪B:={x|x∈A vagy x∈B } Definíció: Az A és B halmazok közös része (metszete,szorzata) az az A∩B-vel jelölt halmaz, amelynek elemei A-nak is és B-nek is elemei. A∩B:= {x|x∈A és x∈B } Ha az A és B halmazoknak nincsen közös része, vagyis A∩B=∅, akkor azt mondjuk, hogy az A és B halmazok diszjunktak. Definíció: Az A és a B halmazok különbsége, A\B vagy a B halmaz A halmazra vonatkozó komplementere, amelyek nincsenek B-ben.

A azon elemeinek halmaza,

A\B = B A :=: {xx∈A és x∉B}


Diszkrét matematika Tulajdonságai: A\∅=? ∅\A=? Szokás az ún. univerzális halmaz, vagy univerzum bevezetése, ez a feladattal kapcsolatos összes lehetséges objektumok összessége, jelölés: U. A B halmaz univerzumra vonatkozó komplementerének jele: B . Szokásos univerzumok: - valós számok, R - pozitív valós számok, R+ - nem negatív egészek, N - egészek, Z Feladatok: Mi a pozitív egész számok halmazára vonatkozó komplementere a páros pozitív egészek halmazának? Mi a valós számok halmazára vonatkozó komplementere a racionális számok halmazának? A definíciók egyszerű következményei: A∪U=U A∪A=A A∪∅=A A\∅=A

A∩U=A A∩A=A A∩∅=∅ ∅\A=∅

Műveleti azonosságok:


Diszkrét matematika 1. A∪B=B∪A A∩B=B∩A 2. (A∪B)∪C=A∪(B∪C) (A∩B)∩C=A∩(B∩C)

kommutatív asszociatív

3. a.) A∩(B∪C)= (A∩B) ∪(A∩C) b.) A∪(B∩C)= (A∪B) ∩ (A∪C)

disztributív disztributív

3. a.) bizonyítása: A∩(B∪C)= (A∩B) ∪(A∩C)

X:= A∩(B∪C) Y:= (A∩B) ∪(A∩C)

bal oldal jobb oldal

Azt kell biz., hogy X⊆Y, és Y⊆X. a.) X⊆Y Legyen x tetszőleges eleme X-nek. Tetszőleges azt jelenti, hogy bármely (más) X-beli elemre az alábbiak elmondhatók, igy tehát valójában X minden elemére bizonyítunk. Ekkor x∈A és x∈ B∪C. Az utóbbi miatt x∈ B, vagy x∈C. Így vagy x∈A, és x∈B, ami azt jelenti, hogy x∈A ∩ B, vagy, hasonlóképpen: x∈A∩C ami éppen azt jelenti, hogy x∈(A∩B) ∪(A∩C). Tehát minden X-beli elem Y-beli is, tehát X⊆Y. b.) Y⊆X. Legyen y tetszőleges eleme Y-nak. Ekkor vagy y∈A∩B, vagy y∈A∩C. Az első esetben y∈A és y∈B. Utóbbi miatt y∈B∪C, tehát y∈ A∩(B∪C). Ehhez hasonlóan második esetben y∈A és y∈C, így y∈ B∪C, amiből következik, hogy y∈A∩(B∪C). Ezzel beláttuk, hogy minden Ybeli elem X-beli is, Y⊆X. Feladat: Igazolja a 3. b.) azonosságot!


Diszkrét matematika További azonosságok (De Morgan): 4. a.)

A∪ B = A∩ B

b.)

A∩ B = A∪ B

Biz.: 4. a.) Legyen

A∪ B = A∩ B

H1= A ∪ B = A ∩ B =H2. Bármely x∈ H1 ⇒ x∉A∪B ⇒ x∉A és x∉B ⇒ x∈ A ∩ B = H2, H1⊆ H2 Bármely x∈ H2 ⇒ x∈ A és x∈ B ⇒ x∉A és x∉B ⇒ x∉A∪B , tehát x∈ A ∪ B = H1⊆ H2 Feladat: Igazolja a 4.b.) De Morgan azonosságot is! Venn-diagramm:

A

U A

A

U B

A∩B

A

U B

A∪B


Diszkrét matematika Feladat: Illusztrálja a műveleti azonosságokat és a De Morgan azonosságokat Venn-diagramm segítségével! Definíció: Halmaz számosságán a halmaz elemeinek számát értjük. Jelölés: |A|. Ha ez véges szám, akkor azt mondjuk, hogy az A halmaz véges, ellenkező esetben az A halmaz végtelen. |{3, 4}|=2 Feladatok: (Logikai szita) |A∪B| = ? |A∪B∪C| = ? |A∪B∪C∪D| = ? Definíció: Legyenek D1, D2, …Dn adott halmazok. E halmazok Descartes (direkt) szorzata: D1 x D2 x … x Dn : = {( d1, d2, …dn) | dk ∈Dk 1 ≤ k ≤n } A direkt szorzat tehát olyan rendezett érték n-eseket tartalmaz, amelynek k. eleme a k. halmazból való. Példák: 1. A={1,2} és B={7,8,9} akkor A×B={(1,7),(1,8),(1,9),(2,7),(2,8),(2,9)}


Diszkrét matematika 2. Adatok:= Nevek x Városok x Utcanevek x Házszámok= {(Nagy Janka, Budapest, Fő u., 1),… (Nagy Janka, Budapest, Fő u., 16), (Nagy Janka, Budapest, Fő u., 17),….. (Nagy Janka, Budapest, Kossuth L. u., 1), …. (Nagy János, Budapest, Fő u. 1.), ….} Alkalmazás: adatbáziskezelés - relációs algebra 3. R x R={(x,y)| x∈R és y∈R}, Descartes koordináta-rendszer Definíció: Relációnak nevezzük a D1 x D2 x … x Dn direkt szorzat bármely részhalmazát: r ⊆ D1 x D2 x … x Dn Példa: { (Nagy Janka, Budapest, Kossuth L. u., 1), (Nagy János, Budapest, Fő u., 1)} ⊆ Adatok Definíció: Bináris reláció, ha n=2: r ⊆ D1 x D2 Bináris relációk néhány jellemzője: Reflexív: (a, a) ∈r Kommutatív: ha (a, b) ∈r, akkor (b, a) ∈r Anti-kommutatív (nem kommutatív): ha (a, b) ∈r, akkor (b, a) ∉r Tranzitív: ha (a, b) ∈r, és (b, c) ∈r, akkor (a, c) ∈r


Diszkrét matematika Feladatok: Döntsük el az alábbi relációkról, hogy a fenti jellemzők közül melyekkel rendelkeznek? 1. x, y∈N, (x,y) ∈r, ha x osztója y-nak. 2. x, y∈R, (x,y) ∈r, ha x kisebb (kisebb vagy egyenlő) mint y. 3. x, y∈R, (x,y) ∈r, ha x = y. A természetes számok halmaza (Az 1 számból az 1 ismételt hozzáadásával keletkező számok axiomatikus megadása.) Peano axiómák: 1. 2. 3. 4. 5.

Az 1 természetes szám. Minden természetes számnak van rákövetkezője. Nincsen olyan természetes szám, aminek az 1 rákövetkezője lenne. Csak egyenlő természetes számoknak vannak egyenlő rákövetkezőik. Ha a természetes számok valamely A részhalmazára igaz az, hogy az 1 természetes számot tartalmazza, továbbá, ha az n természetes szám eleme, akkor ennek rákövetkezője is eleme, akkor A azonos a természetes számok halmazával.

Az 5. axióma nem független a többitől, az első 4 és a halmazelmélet segítségével. Az 5. axióma az alapja az ún. teljes indukciós bizonyításnak. Ha azt akarjuk bizonyítani, hogy egy állítás teljesül az összes természetes számra, akkor először bizonyítani kell, hogy 1-re igaz az állítás. Második lépésként pedig azt kell bizonyítani, hogy a tulajdonság öröklődése fennáll, vagyis, ha a tulajdonság teljesül az n természetes számra, akkor teljesül a rákövetkezőjére is.


Diszkrét matematika Példa: 1. Páratlan számok összege: 1=1 1+3=4 1+3+5=9 1+3+5+7=16 ⇒Állítás: 1+3+… +(2k-1)=k2 Bizonyítás (teljes indukcióval): 1.Megvizsgáljuk, k=1-re igaz-e: 1=1 tehát igaz. 2.Tegyük fel hogy k=n-ra igaz: 1+3+ … (2n-1)=n2 3.Bizonyítjuk, hogyha k=n-ra igaz, akkor hogy k= n+1-re is: 1+3+ … +(2k-1)+(2k+1) ?= (k+1)2 1+3+…+(2k-1) = k2 , k2+(2k+1)=k2+2k+1= (k+1)2 ⇒ az állítás igaz. 2. n elemű halmaz hatványhalmazának számossága: P(A) =2n, ha A=n Bizonyítás (teljes indukcióval): 1. n=1-re igaz, mert egyelemű halmaz részhalmazai az üreshalmaz és és az egyetlen elemet tartalmazó halmaz, vagyis száma 2. 2. Tfh. P(A)= 2n haA=n 3. Azt akarjuk bizonyítani, hogyha A=n P(A)= 2n AKKOR T=n+1 P(T)=2n+1. Az általánosság megszorítása nélkül feltehető, hogy T=A∪{a}.(„a” az az elem, ami az „n” elemű halmazban nem volt benne.) a∈T=A∪{a} és T\{a}=S=A P(S)= 2n az indukciós feltétel miatt. P(S):={∅,S1, S2, … , Sk} (összesen 2n darab) P(T):={ {a},{S1∪{a}},{S2∪{a}}, … , {Sk∪{a}}}∪ P(S) Könnyen látható, hogy egyértelmű megfeleltetés van T-nek a-t tartalmazó és a-t nem tartalmazó részhalmazai között. P(T)= 2n +2n =2·2n =2n+1


Diszkrét matematika

Feladatok: Bizonyítsa teljes indukcióval az alábbi összefüggéseket: 1. n<2n 2. Bernoulli egyenlőtlenség Természetes számok és halmazok A természetes számok halmaza felépíthető csak halmazelméleti fogalmakkal. Ekkor a halmaz számossága azonosítható a természetes számmal. 0:=∅ 1:={0}={∅} 2:={0, 1}={∅, {∅}}=1∪{1} 3:= {0, 1, 2}= {∅, {∅}, {∅, {∅}}}=2∪{2} . . n:={0, 1, 2, 3, …n}=..= n ∪{n}

|0|=0 |1|=1 |2|=2 |3|=3 |n|=n


Halmazok-előadás vázlat

Recommend Documents