Novák Ágnes - Halmazok

Országok listájaHungaryMiskolci EgyetemGépészmérnöki és Informatikai KarProgramtervező informatikusDiszkrét MatematikaJegyzetekNovák Ágnes - Halmazok

PPKE ITK matematika Halmazok-eladás vázlat

Diszkrét

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: aA azt jelenti, hogy az a eleme az A halmaznak. (Az a az A halmazhoz tartozik.) Mit jelent aA? Azt követeljük meg, hogy a halmazt az elemei egyértelmen meghatározzák: Csak olyan halmazokkal foglalkozunk, amelyeknél aA állítás igazsága egyszersmind aA állítás hamis voltát vonja maga után, illetve az aA állítás igaz voltából az aA állítás hamissága következik. Az alábbi, ún. antinomiák (2. antinomia késbb) 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 nH igaz, vagy nH? Halmazok megadása, példák: felsorolás : A:={3, 4} valamely tulajdonság megadása (részhalmaz, ld. késbb): B:={x| xR, x megoldása az (x-3)(x-4)=0 egyenletnek}

Definíció: Az A és a B halmazok egyenlk, ha ugyanazok az elemeik.

1 © Bércesné Novák Ágnes

PPKE ITK matematika

Diszkrét

Nyilván a fenti példákban A=B. 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: AB. Ha AB és AB, 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: AA reflexív A részhalmaz definícióját átfogalmazhatjuk úgy is, hogy AB , ha A-nak nincsen olyan eleme, amely ne lenne B-nek is eleme. Ennélfogva A, hiszen nincsen eleme. Igaz-e, ha AB és BC, akkor AC ? (tranzitivitás) Igaz-e, ha AB, akkor BA? (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: AB tulajdonságai: reflexív: AA tranzitív: AB és BC, akkor AC NEM kommutatív 1. Állítás: A=B akkor és csak akkor, ha AB és BA. Ez az állítás használható halmazok azonosságának bizonyítására.

2 © Bércesné Novák Ágnes

PPKE ITK matematika Definíció: Az A halmaz P(A) hatványhalmazán az A részhalmazainak halmazát értjük. 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! Mveletek halmazok között

Diszkrét

Definíció: Az A és B halmazok egyesítése (uniója, összege) az az AB-vel jelölt halmaz, amelynek elemei vagy A-nak, vagy B-nek elemei. AB:={x|xA vagy xB } Definíció: Az A és B halmazok közös része (metszete,szorzata) az az AB-vel jelölt halmaz, amelynek elemei A-nak is és B-nek is elemei. AB:= {x|xA és xB } Ha az A és B halmazoknak nincsen közös része, vagyis AB=, 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,

3 © Bércesné Novák Ágnes

PPKE ITK matematika

Diszkrét

A\B = B A :=: {xxA és xB} 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: AU=U AA=A A=A A\=A AU=A AA=A A= \A=

4 © Bércesné Novák Ágnes

PPKE ITK matematika

Diszkrét

Mveleti azonosságok: 1. AB=BA AB=BA 2. (AB)C=A(BC) (AB)C=A(BC) 3. a.) A(BC)= (AB) (AC) b.) A(BC)= (AB) (AC) 3. a.) bizonyítása: A(BC)= (AB) (AC) kommutatív asszociatív disztributív disztributív X:= A(BC) Y:= (AB) (AC) bal oldal jobb oldal

Azt kell biz., hogy XY, és YX. a.) XY Legyen x tetszleges eleme X-nek. Tetszleges 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 xA és x BC. Az utóbbi miatt x B, vagy xC. Így vagy xA, és xB, ami azt jelenti, hogy xA B, vagy, hasonlóképpen: xAC ami éppen azt jelenti, hogy x(AB) (AC). Tehát minden X-beli elem Y-beli is, tehát XY. b.) YX. Legyen y tetszleges eleme Y-nak. Ekkor vagy yAB, vagy yAC. Az els esetben yA és yB. Utóbbi miatt yBC, tehát y A(BC). Ehhez hasonlóan második esetben yA és yC, így y BC, amibl következik, hogy yA(BC). Ezzel beláttuk, hogy minden Ybeli elem X-beli is, YX. Feladat: Igazolja a 3. b.) azonosságot!

5 © Bércesné Novák Ágnes

PPKE ITK matematika További azonosságok (De Morgan): 4. a.)
b.)

Diszkrét

A B = A B

A B = A B
A B = A B

Biz.: 4. a.) Legyen

H1= A B = A B =H2. Bármely x H1 xAB xA és xB x A B = H2, H1 H2 Bármely x H2 x A és x B xA és xB xAB , tehát x A B = H1 H2

Feladat: Igazolja a 4.b.) De Morgan azonosságot is! Venn-diagramm:

A

U A

U B

A

U B

A

AB

AB
6

© Bércesné Novák Ágnes

PPKE ITK matematika Feladat: Illusztrálja a mveleti azonosságokat és a De Morgan azonosságokat Venn-diagramm segítségével!

Diszkrét

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) |AB| = ? |ABC| = ? |ABCD| = ? 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)}

7 © Bércesné Novák Ágnes

PPKE ITK 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)| xR és yR}, 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 jellemzje: 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

8 © Bércesné Novák Ágnes

PPKE ITK matematika Feladatok: Döntsük el az alábbi relációkról, hogy a fenti jellemzk közül melyekkel rendelkeznek? 1. x, yN, (x,y) r, ha x osztója y-nak. 2. x, yR, (x,y) r, ha x kisebb (kisebb vagy egyenl) mint y. 3. x, yR, (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.

Diszkrét

Az 1 természetes szám. Minden természetes számnak van rákövetkezje. Nincsen olyan természetes szám, aminek az 1 rákövetkezje lenne. Csak egyenl természetes számoknak vannak egyenl rákövetkezik. 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övetkezje is eleme, akkor A azonos a természetes számok halmazával.

Az 5. axióma nem független a többitl, 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 elszö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ökldése fennáll, vagyis, ha a tulajdonság teljesül az n természetes számra, akkor teljesül a rákövetkezjére is.

9 © Bércesné Novák Ágnes

PPKE ITK 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

Diszkrét

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 haA=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.) aT=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

10 © Bércesné Novák Ágnes

PPKE ITK matematika

Diszkrét

Feladatok: Bizonyítsa teljes indukcióval az alábbi összefüggéseket: 1. n<2n 2. Bernoulli egyenltlensé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

11 © Bércesné Novák Ágnes



Hasonló témájú dokumentumok

Hozzászólások

01 10.16-2 18. század 2005 4.előadás áteresz család csehov dendrológia diffúzió elte építésszervezés 1 építésszervezés i. etnikai kisebbség eu logisztika fenntartható füvészkert gazdaságtörténet gazdmatek görögország gyakorló feladatok halász gábor hőtan innováció ipar jános kalkulus kántor anita kőzetek közgáz lemez máté eörs mechanika3 zh művészettörténet művtöri német felvilágosodás ökológia önköltség öregedés összefoglaló pénzpiac posztmodern sejt speech sounds szellemi tulajdon tanirodai természetvédelmi mérnök teszt vállalat gazdaságtan vetőmag