DHARMA Initiative Diszkrét Matematika 1. DHARMA INITIATIVE

DHARMA Initiative

Diszkrét Matematika 1.

DHARMA INITIATIVE

Diszkrét Matematika 1. – Definíciók (középszint) E dokumentum az ELTE IK Diszkrét Matematika 1. 2010/2011-es vizsgájára készült. Az elkészítéshez a korábbi évek kidolgozott listáit használtuk. Amennyiben hibát talált a definíciók között, azt kérjük, hogy jelezze a kurzusfórumon. Sikeres felkészülést kívánunk! DHARMA Initiative 1. Mondjon legalább három példát predikátumra. E(x): x egyenes P(x): x pont I(x, y): x illeszkedik y-ra. 2. Sorolja fel a logikai jeleket. ￢: negáció (tagadás) ∧: konjukció (és) ∨: diszjunkció (vagy) ⇒: implikáció (ha… akkor…) ⇔: ekvivalencia (akkor és csak akkor) ⊕: antivalencia (kizáró vagy)

∣: konnegáció (sem… sem…[A | B = ￢(A∨B)])

||:‖exklúzió (összeférhetetlen vagy: [A || B = ￢(A ∧ B)])

Belső terjesztésre!

DI 90M1654-21644

1

DHARMA Initiative


3. Milyen kvantorokat ismer? Mi a jelük? ∀ : univerzális kvantor (minden). ∃ : egzisztenciális kvantor (létezik).

4. Hogyan kapjuk a logikai formulákat? A logikai formulák az adott elmélet predikátumaiból épülnek fel a logikai jelek valamint a kvantorok segítségével. 5. Mikor van egy változó egy kvantor hatáskörében? Egy formula egy (∃x A) vagy (∀x A) típusú részformulája esetén az x változó minden, a két zárójel közötti előfordulására (a kvantor után vagy A-ban) a kvantor hatáskörében van. 6. Mik a nyitott és mik a zárt formulák? Ha egy formulában egy változó egy adott előfordulása egy kvantor hatáskörében van, akkor azt mondjuk, hogy az adott előfordulás kötött előfordulás, egyébként az adott előfordulás szabad előfordulás. Ha egy változónak egy formulában van szabad előfordulása, akkor azt mondjuk, hogy a változó szabad változó. Ha egy formulának nincs szabad változója, akkor a formulát zárt formulának, egyébként nyitott formulának mondjuk. 7. Mondjon két példát nyitott formulára. A(x,y) = ((P(x) ∧ P(y))∧￢x = y);

B(x) = ((E(x)∧P(y))∧I(x,y))

8. Mondjon egy példát zárt formulára. ∀x(E(x)⇒∃y(P(x)∧I(x,y)))

9. Definiálja a részhalmaz és a valódi részhalmaz fogalmát és adja meg jelöléseiket. Akkor mondjuk, hogy az A halmaz részhalmaza a B halmaznak, ha A minden eleme a B halmaznak is eleme. Jele: A⊂B vagy B⊃A. Ha A részhalmaza B-nek, de nem egyenlő vele, akkor azt mondjuk, hogy A valódi részhalmaza B-nek. Jele: A⊊B vagy B⊋A. 10. Milyen tulajdonságokkal rendelkezik a ,,részhalmaz” fogalom? Reflexivitás: A ⊂ A Trantitivitás: A ⊂ B ∧ B ⊂ C ⇒ A ⊂ C Antiszimmetria: A ⊂ B ∧ B ⊂ A ⇒ A = B (a meghatározottsági axióma szerint).

11. Milyen tulajdonságokkal rendelkezik a halmazok egyenlősége? Reflexivitás: A=A Tranzitivitás: A = B ∧ B = C ⇒ A =C Belső terjesztésre!

DI 90M1654-21644

2

DHARMA Initiative


Antiszimmetria: A=B ∧ B = A ⇒ A = B Szimmetria: A = B ⇒ B = A

12. Írja le a részhalmaz fogalmát. Milyen jelölést használunk részhalmazok megadására? Az A halmaz részhalmaza B halmaznak, ha A minden eleme a B halmaznak is eleme. (jele: A ⊂ B)

13. Írja le az üres halmaz fogalmát.

Az üres halmaz az a halmaz, amelynek nincsen eleme (jele: ∅).

14. Igaz-e, hogy csak egy üres halmaz van?

Igen. A meghatározottság axiómája miatt csak egy üres halmaz van. 15. Írja le két halmaz unióját és a megfelelő jelöléseket. Az A és B halmaz uniója az a halmaz, amelynek pontosan azokat a dolgokat tartalmazza, melyek elemei A-nak vagy B-nek ( vagy mindkettőnek). Jele: A ⋃ B

16. Írja le halmazrendszer unióját és a megfelelő jelöléseket.

Egy halmazrendszer uniója az a halmaz, amely pontosan azokat a dolgokat tartalmazza, amelyek a halmazrendszer legalább egy elemének elemei. Jelölései: ∪A, ∪{A:A∈A}∪A∈A A.

17. Fogalmazza meg a halmazok uniójának alaptulajdonságait. A∪∅=A Kommutativitás: A∪B = B∪A Asszociativitás: A∪(B ∪ C)=(A∪B)∪C Idempotencia: A∪A = A A⊂B ⇔ A∪B = B.

18. Definiálja halmazrendszer és két halmaz metszetét, és adja meg a jelöléseket. Egy halmazrendszer metszete az a halmaz, amely pontosan azokat a dolgokat tartalmazza, amely a halmazrendszer minden elemének elemei. Jelölései: ∩A, ∩{A: A∈A}∩A∈A A. Az A és B halmaz metszete az a halmaz, amelynek pontosan azok a dolgok az elemei, melyek elemei A-nak és B-nek is. Jele: A ∩ B 19. Definiálja a diszjunktság és páronként diszjunktság fogalmát. Ha A ∩ B =∅, akkor A és B halmazok diszjunktak. Ha egy halmazrendszer bármely két halmaza diszjunkt, akkor a halmazrendszer elemei páronként diszjunktak. 20. Fogalmazza meg a halmazok metszetének alaptulajdonságait. A ∩ ∅ =∅; Kommutativitás: A∩B=B∩A Belső terjesztésre!

DI 90M1654-21644

3

DHARMA Initiative


Asszociativitás: A∩(B∩C)=(A∩B)∩C Idempotencia: A∩A=A (idempotencia) A⊂B ⇔ A∩B=A.

21. Fogalmazza meg az unió és a metszet disztributivitását. Az unió és a metszet műveletek kölcsönösen disztributívak egymásra nézve. A metszet disztributivitása az unióra nézve: A∩(B∪C)=(A∩B)∪(A∩C) Az unió disztributivitása a metszetre nézve: A∪(B∩C)=(A∪B)∩(A∪C) 22. Definiálja halmazok különbségét, szimmetrikus differenciáját és komplementerét. Különbség: A\B:={x∈A : x∉B} Szimmetrikus differencia: A ▵ B:=(A\B)∪(B\A) Komplementer: CxA := X \ A (A’-val is jelöljük). 23. Fogalmazza meg a halmazok komplementerének alaptulajdonságait. • • • • • • • •

(A')'=A ∅'=X X'=∅ A∩A'=∅ A∪A'=X A⊂B⇔B'⊂A' (A∪B)'=A'∩B' (A∩B)'=A'∪B'

24. Írja le a hatványhalmaz fogalmát. Milyen jelölések kapcsolódnak hozzá? Minden A halmazhoz létezik egy olyan halmazrendszer, amelynek elemei pontosan A részhalmazai(Hatványhalmaz-axióma). Jele: ℘(A) vagy 2A .

25. Definiálja a rendezett pár fogalmát és koordinátáit.

Rendezett pár alatt az (a,b) szimbólumot értjük, ahol (a,b) = (c,d) ⇔ a = c ∧ b = d. A rendezett pár fogalmát ennek megfelelően halmazként definiáljuk: (a,b) = {{a},{a,b}}. Az (a,b) rendezett pár első koordinátája a, második b. 26. Definiálja két halmaz Descartes-szorzatát. Az X,Y halmazok Descartes-szorzatán az X⨯Y:={(x,y):x∈X,y∈Y} halmazt értjük. 27. Definiálja a binér reláció fogalmát és adja meg a kapcsolódó jelöléseket. Az R halmaz binér reláció, ha minden eleme rendezett pár. Ha (x,y) ∈ R, akkor xRy-ként is jelölhetjük, melynek jelentése: x és y között fenáll R reláció. 28. Adjon három példát binér relációra. kisebb reláció (a < b,) nagyobb reláció (a > b) egyenlőség (a = b) Belső terjesztésre!

DI 90M1654-21644

4

DHARMA Initiative


29. Mit jelent az, hogy R reláció X és Y között? Mit jelent az, hogy R egy X-beli reláció? Ha X és Y halmazokra R⊂X⨯Y, akkor azt mondjuk, hogy R reláció X és Y között. Ha X=Y, akkor azt mondjuk, hogy R egy X-beli binér reláció (homogén binér reláció). 30. Definiálja binér reláció értelmezési tartományát és értékkészletét, és adja meg a kapcsolódó jelöléseket. Az R binér reláció értelmezési tartománya az elemeinek első koordinátáiból álló halmaz. Jele: dmn(R). dmn(R):={x:∃(x,y)∈R} Az R binér reláció értékkészlete az elemeinek második koordinátáiból álló halmaz. Jele: rng(R). rng(R):={y:∃(x,y)∈R} 31. Definiálja binér reláció kiterjesztését, leszűkítését és leszűkítését egy halmazra és adja meg a kapcsolódó jelöléseket. Az R binér relációt az S binér reláció kiterjesztésének, illetve S-et az R leszűkítésének (vagy megszorításának) nevezzük, ha S⊂R. Ha X egy halmaz, az R reláció X-re való leszűkítésén (vagy megszorításán) az R|X:={(x,y)∈R:x∈X} relációt értjük. 32. Definiálja egy binér reláció inverzét és sorolja fel az inverz három egyszerű tulajdonságát. Egy binér reláció inverzét elemeinek két koordinátájának megcserélésével kapjuk (jele: R-1). Formálisan: R-1 := b(b,a)(a,b) ∈R} Az inverz három egyszerű tulajdonsága: • • •

(R-1)-1=R; ha R reláció X és Y között, akkor R-1 reláció Y és X között; dmn(R-1) = rng(R) és rng(R-1) = dmn(R).

33. Definiálja halmaz képét és inverz képét binér relációnál és adja meg a kapcsolódó jelöléseket. Legyen R egy binér reláció és A egy halmaz. Az A halmaz kepe az R(A):={y:∃x∈A:(x,y)∈R} halmaz. rng(A) pontosan akkor üres, ha A és dmn(R) diszjunktak. Az A halmaz inverz kepe az R relációnál R-1(A). Ha A={a}, akkor rng({a}) helyett rng(a)-t írunk. 34. Definiálja binér relációk kompozícióját. Lehet-e a kompozíció üres? Az R és S binér relációk összetételén (kompozícióján, szorzatán) az R∘S:={(x,y):∃z: (x,z)∈S ∧ (z,y)∈R} relációt értjük. Két reláció kompozíciója lehet üres: ez a helyzet, ha rng(S) és dmn(R) diszjunktak. 35. Fogalmazzon meg három, binér relációk kompozíciójára vonatkozó állítást. Legyenek R,S,T binér relációk. Ekkor (1) ha rng(S) ⊃ dmn(R), akkor rng(R∘S) = rng(R);


DI 90M1654-21644

5

DHARMA Initiative


(2) R∘(S∘T)=(R∘S)∘T (asszociativitás); (3) (R∘S)-1=S-1∘R-1.

36. Mit jelent az, hogy egy reláció tranzitív, szimmetrikus, illetve dichotóm? Ezek közül mi az, ami csak a reláción múlik? Az R legyen egy X halmazbeli reláció. Ekkor R: Tranzitív, ha minden x,y,z-re (x,y)∈R és (y,z)∈R eseten (x,z)∈R; Szimmetrikus, ha minden x,y-ra (x,y)∈R eseten (y,x)∈R; Dichotom, ha minden x,y ∈X eseten (x,y) ∈R vagy (y,x) ∈R

Ezek közül a tranzitivitás és a szimmetrikusság függ csak a relációtól. 37. Mit jelent az, hogy egy reláció antiszimmetrikus, illetve trichotóm? Ezek közül mi az, ami csak a reláción múlik? Az R legyen egy X halmazbeli reláció. Ekkor R: Intranzitív, ha minden x,y,z-re(x,y) ∈R és (y,z) ∈R eseten (x,z) ∉R; Antiszimmetrikus, ha minden x,y-ra (x,y)∈R és (y,x)∈R eseten x=y; Trichotóm, ha minden x,y ∈X eseten x=y, (x,y) ∈R és (y,x) ∈R közül pontosan egy teljesül. Ezek közül az intranzitivitás és az antiszimmetrikusság függ csak a relációtól. 38. Mit jelent az, hogy egy reláció szigorúan antiszimmetrikus, refexív illetve irreflexív? Ezek közül mi az, ami csak a reláción múlik? Az R legyen egy X halmazbeli reláció. Ekkor R: reflexív, ha minden x ∈X eseten (x,x) ∈R irreflexív, ha minden x∈X eseten (x,x) ∉R szigorúan antiszimmetrikus, ha minden x,y-ra (x,y) ∈R eseten (y,x) ∉R Ezek közül a szigorúan antiszimmetrikusság függ csak a relációtól. 39. Definiálja az ekvivalenciareláció, illetve az osztályozás fogalmát. Egy X halmazbeli binér reláció ekvivalenciareláció, ha reflexív, szimmetrikus és tranzitív. Az X részhalmazainak egy O rendszerét X osztalyozasanak nevezzuk, ha O páronként diszjunkt nem üres halmazokból álló halmazrendszer, amelyre ∪O=X.

40. Mi a kapcsolat az ekvivalenciarelációk és az osztályozások között?

Egy X halmazon értelmezett ekvivalenciareláció X-nek egy osztályfelbontását adja. Megfordítva, X minden osztályfelbontása egy ekvivalenciarelációt hoz létre. 41. Definiálja a részbenrendezés és a részbenrendezett halmaz fogalmát. Mit mondhatunk egy részbenrendezett halmaz egy részhalmazáról? Egy X halmazbeli binér reláció részbenrendezés, ha reflexív, antiszimmetrikus és tranzitív. Ekkor X halmaz részbenrendezett. Ha x,y ∈X: x≤y ∨ y≤x, akkor x és y elemek Belső terjesztésre!

DI 90M1654-21644

6

DHARMA Initiative


összehasonlíthatóak. Egy részbenrendezett halmaz minden részhalmaza is részbenrendezett, ha a ≤ relációt csak ennek elemei között tekintjük. 42. Definiálja a rendezés, a rendezett halmaz és a lánc fogalmát. A rendezett X halmaz olyan részbenrendezett halmaz, amely dichotóm, azaz bármely két eleme összehasonlítható. Tehát egy X halmazbeli binér reláció rendezés, ha reflexív, antiszimmetrikus, tranzitív és dichotóm. Láncnak nevezzük egy részbenrendezett halmaz részhalmazát, amely rendezett, ha a ≤ relációt csak ennek elemei között tekintjük. 43. Mondjon példát részbenrendezett de nem rendezett halmazra. A természetes számok körében az n|m reláció részbenrendezés, de nem rendezés. 44. Definiálja egy relációnak megfelelő szigorú illetve gyenge reláció fogalmát. Egy X-beli reláció R relációhoz definiálhatunk egy X-beli S relációt úgy, hogy xSy akkor álljon fenn, ha xRy de x≠y, ez az R-nek megfelelő szigorú reláció. Megfordítva, egy X-beli R relációhoz a megfelelő T gyenge relációt úgy definiáljuk, hogy legyen xTy, ha xRy vagy x=y. 45. Definiálja a szigorú részbenrendezést és fogalmazza meg kapcsolatát a részbenrendezéssel. Szigorú részbenrendezés az a részbenrendezés, amelyet szigorúan rendezünk. Ez tranzitív, irreflexív és szigorúan antiszimmetrikus (jele: <). Ha egy részbenrendezett relációt szigorúan, majd gyengén rendezünk, akkor a kiindulási részbenrendezést kapjuk vissza. 46. Mi az, hogy kisebb, nagyobb, megelőzi, követi? Adja meg a kapcsolódó jelöléseket. Ha x
DI 90M1654-21644

7

DHARMA Initiative


50. Definiálja a legkisebb és a legnagyobb elem fogalmát. Az X részbenrendezett halmaz legkisebb elemén egy olyan x∈X elemet értünk, amelyre x≤y minden y∈X-re. Nem biztos, hogy van ilyen elem, de ha van, akkor egyértelmű. Hasonlóan, X legnagyobb elemén egy olyan x elemet értünk, amelyre y≤x minden y∈X -re. Nem biztos, hogy van ilyen elem, de ha van, akkor egyértelmű. 51. Definiálja a minimális és a maximális elem fogalmát és adja meg a kapcsolódó jelöléseket. Legyen x∈X. Az x-et minimálisnak nevezzük, ha nincs nála kisebb elem, maximálisnak pedig akkor, ha nincs nála nagyobb elem. Maximális és minimális elem lehet több is. Jelölések: min X, max X. 52. Adjon meg olyan részbenrendezett halmazt, amelyben több minimális elem van. Az N := ℕ \{0,1} halmazon ∀n, m ∈N –re az n≤m : n|m reláció részbenrendezés, melyben minden prímszám minimális elem. Formálisan ≤:={(n,m) ∈ N ⨯ N: n|m}

53. Adjon meg olyan részbenrendezett halmazt, amelyben nincs maximális elem. A természetes számok halmaza ilyen a szokásos rendezéssel. 54. Igaz-e, hogy rendezett halmazban a legkisebb és a minimális elem fogalma egybeesik? Igen. Minimális és maximális elem több is lehet, és hogy ha X rendezett, akkor a legkisebb és a minimális elem fogalma egybeesik, de egyébként nem feltétlenül. 55. Definiálja az alsó és a felső korlát fogalmát. Egy X részbenrendezett halmaz egy x elemet az Y részhalmaz alsó korlátjának nevezzük, ha minden y∈Y-ra x≤y. Ha minden y∈Y-ra y≤x akkor x az Y felső korlátja. Ha letézik alsó illetve felső korlát, akkor azt mondjuk, hogy Y alulról illetve felülről korlátos. 56. Igaz-e, hogy ha egy részbenrendezett halmaz egy részhalmaza tartalmaz a részhalmaz alsó korlátjai közül elemeket, akkor csak egyet? Igen, ha az alsó korlátok között van olyan, mely eleme a részhalmaznak, úgy csak egy ilyen van. 57. Definiálja az alsó és a felső határ tulajdonságot. Ha az X részbenrendezett halmaz bármely nem üres, felülről korlátos részhalmazának van felső határa, akkor felső határ tulajdonságúnak nevezzük. 58. Igaz-e, hogy ha egy részbenrendezett halmaz egy részhalmaza tartalmazza a részhalmaz egy alsó korlátját, akkor az a részhalmaznak minimális eleme? Igen, ha az alsó korlátok között van olyan, mely eleme a részhalmaznak, úgy csak egy ilyen van. Belső terjesztésre!

DI 90M1654-21644

8

DHARMA Initiative


59. Definiálja az infimum és a szuprémum fogalmát. Amennyiben X halmaz Y részhalmaza alulról korlátos, akkor az alsó korlátok halmazában a legnagyobb elem az infimum (jele: infY). Hasonlóan, ha Y felülről korlátos, akkor a felső korlátok halmazában a legkisebb elem a szuprémum (jele: supY). 60. Definiálja a jólrendezés és a jólrendezett halmaz fogalmát. Az X részbenrendezett halmazt jólrendezett, részbenrendezése pedig jólrendezés, ha X bármely nem üres részhalmazának van legkisebb eleme. 61. Adjon meg olyan rendezett halmazt, amely nem jólrendezett. Az egész számok halmaza a szokásos rendezéssel. 62. Adjon példát jólrendezett halmazra. A természetes számok halmaza jólrendezett a szokásos rendezéssel. 63. Adjon meg két részbenrendezett halmaz Descartes-szorzatán a halmazok részbenrendezései segítségével két részbenrendezést. Az X és Y részbenrendezett halmazok Descartes-szorzatán értelmezzük az alábbi részbenrendezéseket: R1 := {((x,y) ∈ X × Y, (x’,y’) ∈ X × Y): x ≤ x’ ∧ y ≤ y’} R2 := {((x,y) ∈ X×Y, (x’ y’) ∈ X × Y): x ≤ x’ ∨ (x=x’ ∧ y ≤ y’)}

64. Két jólrendezett halmaz Descartes-szorzatán a lexikografikus részbenrendezést tekintjük. Mit állíthatunk erről? Ha X és Y rendezettek, illetve jólrendezettek, akkor X×Y is rendezett, illetve jólrendezett a lexikografikus részbenrendezéssel. 65. Definiálja a függvény fogalmát. Ismertesse a kapcsolódó jelöléseket. A függvény egy olyan f reláció, amelynél minden x-hez legfeljebb egy olyan y létezik, amelyre (x,y) ∈f. Az f függvény x helyen felvett y értékét szokás f(x) = y-ként illetve fx-szel is jelölni. A függvény hozzárendelési szabályát az f:x→y formulával szokás felírni, ahol a függvény jelölését olykor elhagyják és egyszerűen x → y-t írnak. 66. Mi a különbség a között, hogy f ∈ X → Y és hogy f : X → Y ?

Az f ∈ X → Y esetén dmn(f) ⊂X, míg a f: X→Y esetében dmn(f) = X

67. Mikor nevezünk egy függvényt kölcsönösen egyértelműnek?

Az f függvényt kölcsönösen egyértelműnek nevezzük, ha f(x)=y és f(x')=y eseten x=x'. Ez azzal ekvivalens, hogy az f-1 reláció függvény. Más néven injektívnek nevezzük a kölcsönösen egyértelmű függvényeket.


DI 90M1654-21644

9

DHARMA Initiative


68. Igaz-e, hogy az identikus leképezés mindig szürjektív? Igen, az identikus leképzés definíciójából következik, hogy dmn(𝕀x) = X és rng(𝕀x) = X, így a függvény szürjektív. 69. Definiálja a permutáció fogalmát. Egy halmaz permutációján a halmaznak önmagára való kölcsönösen egyértelmű leképezését értjük. 70. Igaz-e, hogy két függvény összetétele függvény? Igen. Ha f és g függvények, akkor f ∘ g is az. 71. Mikor állíthatjuk, hogy két függvény összetétele injektív, szürjektív illetve bijektív? Ha a két függvény injektív, szürjektív illetve bijektív, akkor és csak akkor lesz a két függvény összetétele is injektív, szürjektív valamint bijektív. 72. Mi a kapcsolat függvények és ekvivalenciarelációk között? Ha az X halmazon adott egy ekvivalenciareláció, akkor az x elemhez az ekvivalenciaosztályát rendelő leképezést kanonikus leképezésnek nevezzük. Megfordítva, ha f: X→Y egy függvény, akkor az x ∼ x', ha f(x)=f(x') reláció egy ekvivalenciareláció.

73. Mikor nevezünk egy függvényt monoton növekedőnek illetve monoton csökkenőnek?

Az f: X→Y függvény monoton növekedő, ha ∀x ∈X(∀y ∈X, x≤y): f(x)≤f(y) teljesül. Monoton csökkenő, ha ∀x ∈X(∀y ∈X, x≤y): f(x) ≥ f(y) teljesül. 74. Mikor nevezünk egy függvényt szigorúan monoton növekedőnek illetve szigorúan monoton csökkenőnek? Az f: X→Y függvény szigorúan monoton növekedő, ha ∀x ∈X(∀y ∈X, x f(y) teljesül. 75. Mi a kapcsolat a szigorúan monoton növekedő függvények és a kölcsönösen egyértelmű függvények között? Ha X,Y rendezettek, akkor szigorúan monoton növekedő (illetve csökkenő) függvény nyilván kölcsönösen egyértelmű. Megfordítva, ha X,Y rendezettek, akkor egy f:X→Y kölcsönösen egyértelmű monoton növekedő (illetve csökkenő) leképezés szigorúan monoton növekedő (illetve csökkenő) is, és az inverze is monoton növekedő (illetve csökkenő) f(X)-en. 76. Mit állíthatunk a monoton növekedő függvények inverz függvényéről? A monoton növekedő függvények inverz függvénye is monoton növekedő.


DI 90M1654-21644

10

DHARMA Initiative


77. Mit értünk indexhalmaz, indexelt halmaz és indexelt család alatt? Egy x függvény i helyen felvett értékét néha xi-vel jelöljük. Ilyenkor gyakran a függvény I értelmezési tartományát indexhalmaznak, az elemeit indexeknek, értékkészletét indexelt halmaznak, az x függvényt magát pedig családnak nevezzük. 78. Definiálja indexelt halmazcsaládok unióját és metszetét. Ha az értékkészlet elemei halmazok, akkor halmazcsaládról beszélünk. Egy Xi, i∈I halmazcsalád unióját a ∪i∈IXi:= ∪{Xi:i∈I} összefüggéssel értelmezzük. Rövidebb jelölése: ∪iXi. Ha I≠∅, akkor a halmazcsalád metszetét is definiáljuk a ∩i∈IXi:= ∩{Xi:i∈I}. 79. Fogalmazza meg az indexelt halmazcsaládokra vonatkozó De Morgan szabályokat. Ha Xi, i∈I az X halmaz részhalmazainak egy nem üres családja (azaz I≠∅), akkor az X-re vonatkozó komplementert vesszővel jelölve: (∪i∈IXi)'=∩i∈IXi'; (∩i∈IXi)'=∪i∈IXi'. 80. Definiálja véges sok halmaz Descartes-szorzatát és ismertesse a kapcsolódó jelöléseket. Véges sok, n darab halmaz Descartes – szorzatát formálisan így definiáljuk: X1 × X2 × … × Xn :={(x1,x2,...,xn):x1 ∈ X1, x2 ∈X2, … xn ∈ Xn} Ha X1 = X2 = … = Xn := X1 × X2 × … × Xn helyett egyszerűen Xn-t szokás írni. 81. Definiálja a (nem feltétlenül binér) reláció fogalmát és a kapcsolódó jelöléseket. Az R halmaz n-változós reláció, ha minden eleme rendezett n-es elemekből épül fel. 82. Definiálja tetszőleges indexelt halmazcsalád Descartes-szorzatát és ismertesse a kapcsolódó jelöléseket. Az Xi, i∈I halmazcsalád ×i∈IXi Descartes-szorzata a halmazcsaládhoz tartozó összes kiválasztási függvénynek halmaza. Jelölése: ×iXi. 83. Definiálja a binér, unér és nullér művelet fogalmát és ismertesse a kapcsolódó jelöléseket. Legyen X egy halmaz. Egy X-beli binér műveleten egy ∗:X×X→X leképezést értünk. Ha x,y∈X, akkor ∗(x,y) a művelet eredménye, x és y pedig az operandusai. Rendszerint a binér művelet jelét az operandusok közé írjuk: x∗y. Egy X-beli unér művelet egy ∗:X→X leképezés. Mivel X∅={∅}, egy nullér művelet egy ∗:{∅}→X leképezés, ami tulajdonképpen X egy elemének a kijelölését jelenti, operandusa nincs, csak eredménye.


DI 90M1654-21644

11

DHARMA Initiative


84. Adjon meg egy binér és egy unér műveletet táblázattal. ∧

↑

↓

↑

↑

↓

↓

↓

↓

┐

↑

↓

↓

↑

85. Hogyan definiálunk műveleteket függvények között? Ha X és Y halmazok. ∗ binér műveletet pedig Y halmaz elemei között értelmezzük, akkor f, g: X → Y függvények között is értelmezhetjük „pontonként” ∗’ binér műveletet az alábbi módón formálisan: ∀x ∈X: (f ∗ ’g)(x) = f(x) ∗ g(x)

A két műveletet általában ugyanazzal a jellel szokás jelölni. Analóg módon definiálhatók unér illetve nullér műveletek is függvények között. 86. Adjon példát műveletekre függvények között. Egy n-bites számítógépen rendszerint rendelkezésre állnak a logikai műveletek n-bites szavakon, azaz a {0,1,...,n-1} halmazt a {↑,↓} halmazba képező függvények halmazán. 87. Definiálja a művelettartó leképezés fogalmát. Legyenek ∗ és ∗’ binér műveletek rendre X és X’ halmazokon. Egy φ: X → X’ leképezés művelettartó, ha ∀x,y ∈X :(f ∗ ’g)(x) = f(x) ∗ g(x)

A két műveletet általában ugyanazzal a jellel szokás jelölni. Analóg módon definiálhatók unér illetve nullér műveletek is függvénytereken.

88. Adjon példát művelettartó leképezésre. Ha a>1, az x|→ax leképzés művelettartó és kölcsönösen egyértelmű leképzése az összeadással tekintett valós számoknak a szorzással tekintett pozitív valós számokra. 89. Fogalmazza meg a rekurziótételt. Legyen X egy halmaz, a∈X és f:X→X egy függvény. Ha a Peano-axiómák teljesülnek, akkor egy és csak egy olyan ℕ-et X-be képező g függvény létezik, amelyre g(0)=0 és g(n+)=f(g(n)) minden n∈ℕ-re.


DI 90M1654-21644

12

DHARMA Initiative


90. Definiálja a karakterisztikus függvény fogalmát és ismertesse a kapcsolódó jelöléseket. Az X és Y halmazokra, ha Y ⊂ X, akkor legyen 𝑋𝑌(x):=1, ha x ∈Y és 𝑋𝑌(x):=0, ha x ∈X\Y. A 𝑋𝑌 függvény az Y halmaz X-en értelmezett karakterisztikus függvénye. 1, ℎ𝑎 𝑥 ∈ Y Formalizálva 𝑋𝑌(x) : = � 0, ℎ𝑎 𝑥 ∈ X\Y

91. Definiálja a baloldali semleges elem, a jobboldali semleges elem és a semleges elem fogalmát. A (G,∗) grupoid esetén G halmaz egy s elemét bal, illetve jobb oldali semleges elemnek nevezzük, ha s ∗ g = g, illetve g ∗ s = g minden g ∈G-re. Ha s bal és jobb oldali semleges elem is, akkor semleges elemnek nevezzük. 92. Definiálja a félcsoport, a balinverz, a jobbinverz és az inverz fogalmát és ismertesse a kapcsolódó jelöléseket. Ha a ∗ binér művelet G halmazon asszociatív (azaz ∀x, y, z ∈G: (x∗y)∗z = x ∗ (y ∗ z)), akkor (G,∗) grupoid félcsoport.

Ha (G,∗) félcsoportban s semleges elem, akkor g, g∗ ∈ G-re g ∗ g∗ = s esetén g a g∗ balinverze, g∗ pedig a g jobbinverze. Ha g∗ a g-nek bal- és jobbinverze is, akkor g∗ a g inverze. 93. Igaz-e, hogy egy egységelemes multiplikatív félcsoportban ha h-nak és g-nek van inverze, akkor hg-nek is, és ha igen, mi? Igen. Ha g-nek g∗ az inverze, és h-nak h∗ az inverze, akkor a g∗h inverze h∗ ∗ g∗.

94. Definiálja a csoport és az Abel-csoport fogalmát. Ha egy semleges elemes félcsoport minden elemének van inverze, akkor csoport. Ha a ∗ binér műveletet a G halmazon és ∀g,h ∊ G: g ∗ h = h ∗ g teljesül, akkor g és h felcserélhetőek. Ha G bármely két eleme felcserélhető, akkor a ∗ művelet kommutatív. A kommutatív csoportok az Abel-csoportok. 95. Igaz-e, hogy ha X tetszőleges halmaz, akkor℘(X), ∩ egy egységelemes félcsoport? Igen, (℘(X), ∩) kommutatív egységelemes félcsoport. 96. Igaz-e, hogy ha X tetszőleges halmaz, akkor(℘(X), ∪)egy csoport? Nem igaz, (℘(X), ∪) kommutatív egységelemes félcsoport.

97. Igaz-e, hogy ha X tetszőleges halmaz, akkor (℘(X), Δ) egy félcsoport? Igaz, mivel (℘(X), Δ) Abel-csoprt.


DI 90M1654-21644

13

DHARMA Initiative


98. Igaz-e, hogy ha X tetszőleges halmaz, akkor az X-beli binér relációk a kompozícióval egységelemes félcsoportot alkotnak? Igen, mert a kompozíció művelet asszociatív, hiszen R, Q, S relációkra (R ∘ Q) ∘ S = R ∘ (Q ∘ S), az 𝕀x = {(x,x) ∈ X ⨯ X : x ∈ X} pedig egységelem, mivel ∀R ∈ X ⨯ X-re R ∘ 𝕀x = 𝕀x ∘ R = R. 99. Igaz-e, hogy ha X tetszőleges halmaz, akkor az X-et X-re képező bijektív leképezések a kompozícióval, mint művelettel csoportot alkotnak? Igaz. Ha csak az összes injektív, illetve az összes szürjektív leképezéseket tekintjük, akkor is egységelemes félcsoportot kapunk. Az összes bijektív leképezések csoportot alkotnak. 100. Fogalmazza meg a természetes számokra a ≤ reláció és a műveletek kapcsolatát leíró tételt. Ha k,m,n ∈ℕ, akkor:

(1) n+ közvetlenül követi n-et; (2) m≤n ⇔ m+k ≤ n+k; (3) k≠0 : m≤n ⇔ m·k ≤ n·k; (4) m
101. Definiálja a véges sorozatokat. Ha n∈ℕ, akkor a [0,n] ⊂ℕ vagy [1,n] ⊂ℕ+ halmazon értelmezett függvényeket véges sorozatnak nevezzük. Az x véges sorozatot úgy is jelöljük, hogy x0,x1,...,xn vagy xi, i = 0,1,2,...,n. 102. Fogalmazza meg az általános rekurziótételt. Legyen adott X halmaz és egy olyan f függvény, amelynek értékkészlete X részhalmaza, értelmezési tartománya pedig az összes olyan függvények halmaza, amelyek értékkészlete X részhalmaza, értelmezési tartománya pedig ℕ valamely kezdőszelete. Ekkor egyértelműen létezik egy g: ℕ → X függvény, amelyre ∀a ∈ℕ: g(a) = f(g|]←,a[) teljesül. 103. Hogyan használható az általános rekurziótétel a Fibonacci-számok definiálására? Legyen X = ℕ, és legyen az n|→n- leképezése ℕ+-nak ℕ-re az n|→n+ leképezés inverze, f(∅)=0, f({(0,k)}) :=1 bármely k∈ℕ-re, és ha n>1, h:] ←,n[→ ℕ egy függvény, akkor legyen f(h) := h(n-) + h(n- -). (n=min (ℕ\dmn(h))) 104. Definiálja véges sok elem szorzatát félcsoportban és egységelemes félcsoportban. Ha G egy félcsoport, x: ℕ+→G egy sorozat, akkor az általános rekurziótételt alkalmazva 𝑛 definiálhatjuk a ∏𝑛𝑘=1 𝑥𝑘 = 1 és ∏𝑛+1 𝑘=1 𝑥𝑘 = (∏𝑘=1 𝑥𝑘 ) · 𝑥(𝑛+1) szorzatokat úgy, hogy . Ha G egységelemes félcsoport e egységelemmel, akkor ∏0𝑘=0 𝑥𝑘 = 𝑒. Belső terjesztésre!

DI 90M1654-21644

14

DHARMA Initiative


105. Fogalmazza meg a hatványozás két tulajdonságát félcsoportban és egységelemes félcsoportban. Egy tetszőleges G multiplikatív félcsoportra minden g ∈G-re teljesülnek az alábbiak minden m, n ∈ℕ+-ra (egységelemes G félcsoport esetén minden m,n ∈ℕ-re): • •

gm+n = gm · gn (gm)n = gmn

106. Fogalmazza meg a hatványozásnak azt a tulajdonságát, amely csak felcserélhető elemekre érvényes. Ha g,h a G félcsoport felcserélhető elemei, akkor indukcióval (gh)n=gnhn minden n∈ℕ+-ra, ha G egységelemes félcsoport, akkor minden n∈ℕ-re.

107. Hogyan értelmeztük ∑(𝒂∈𝐀) 𝒙a jelölést? Ha G egy kommutatív félcsoport, x:A → G egy tetszőleges függvény és van olyan φ:{k ∈ℕ: 1 ≤ k ≤ n} → A kölcsönösen egyértelmű leképezés (n ∈ℕ+-ra, illetve nullelemes G félcsoport esetén n ∈ℕ-re}, amely A-ra képez, akkor minden ilyen leképezésre ∑𝑛𝑘=1 𝑥φ(k) ugyanaz – ez az általános kommutativitás tétele. Ezt a közös értéket ∑(𝑎∈A) 𝑥 a – val is jelölhetjük. 108. Mikor mondjuk, hogy egy binér művelet kompatibilis egy osztályozással? Adjon ekvivalens megfogalmazást, és Definiálja a műveletet az osztályok között.

109. Definiálja a nullgyűrű és a zérógyűrű fogalmát. A nullgyűrű olyan gyűrű, amelynek csak egyetlen eleme van, ez pedig szükségszerűen a 0 nullelem. (Különben a gyűrű R alaphalmaza nem alkotna az összeadással Abel-csoportot, de még csoportot se.) A zérógyűrűben bármely két elem szorzata 0 nullelem. 110. Definiálja a bal és jobb oldali nullosztó és a nullosztópár fogalmát. Ha x és y egy gyűrű nullától különböző elemei és x · y = 0, akkor x és y egy nullosztópár, ahol x a bal oldali, y pedig a jobb oldali nullosztó. 111. Definiálja az integritási tartomány fogalmát. Egy legalább kételemű gyűrű nullosztómentes, ha nincsenek benne nullosztópárok. A kommutatív nullosztómentes gyűrű az integritási tartomány.


DI 90M1654-21644

15

DHARMA Initiative


112. Definiálja a rendezett integritási tartomány fogalmát. R-et rendezett integritási tartománynak nevezzük, ha rendezett halmaz, integritási tartomány, és (1) ha x,y,z∈R és x≤y, akkor x+z≤y+z (az összeadás monoton); (2) ha x,y∈R és x,y≥0, akkor x·y≥0 (a szorzás monoton). 113. Fogalmazzon meg szükséges és elégséges feltételt arra vonatkozóan, hogy egy integritási tartomány rendezett integritási tartomány legyen. Egy R rendezett halmaz, amely integritási tartomány akkor és csak akkor rendezett integritási tartomány, ha az összeadás és szorzás is szigorúan monoton. Formálisan: ∀x,y,z ∈ℝ (x0): x·y>0 (a szorzás szigorúan monoton)

114. Fogalmazza meg a rendezett integritási tartományban az egyenlőtlenségekkel való számolás szabályait leíró tételt. Legyen R rendezett halmaz, amely integritási tartomány. Ekkor teljesül az alábbi 5 szabály ∀x,y,z ∈ ℝ-re: (1) ha x>0, akkor –x<0, és ha x<0, akkor –x>0; (2) ha x0, akkor xzyz; (4) ha x≠0, akkor x2>0; speciálisan, ha van egységelem, akkor az pozitív; 1 1 (5) ha 1 az egységelem, 0<x
115. Definiálja a test fogalmát és adjon három példát testre. Egy F gyűrűt ferdetestnek nevezünk, ha a nullelemet 0-val jelölve F\{0} a szorzással csoport. Ha a szorzás kommutatív, akkor a ferdetestet testnek nevezzük. Példák testre: ℚ, valós számok, komplex szamok.

𝑥

116. Definiálja a rendezett test fogalmát és adjon példát olyan testre, amely nem tehető rendezett testté. A rendezett test olyan test, amely rendezett integritási tartomány is. A {0,1} halmaz a 0 + 0 = 1 + 1 = 0, 0 + 1 = 1 + 0 = 1 összefüggésekkel megadott összeadással és a 0 · 0 = 0 · 1 = 1 · 0 = 0, 1 · 1 = 1 összefüggésekkel megadott szorzással kételemű test, de nincsen olyan rendezés, amellyel rendezett test lenne, mert a rendezett testben 1>0 és -1<0, de a fenti kételemű testben -1 = 1. 117. Fogalmazza meg az arkhimédeszi tulajdonságot. Az F rendezett test arkhimédeszi tulajdonságú, ha ∀x,y ∈F, x,y≥ 0 (∃y ∈ℕ): nx ≥y.

118. Mi a kapcsolata az arkhimédeszi tulajdonságnak a felső határ tulajdonsággal? Egy felső határ tulajdonságú test mindig arkhimédészi tulajdonságú is. 119. Fogalmazza meg a racionális számok felső határ tulajdonságára és az arkhimédeszi tulajdonságára vonatkozó tételt. A racionális számok rendezett teste arkhimédészi tulajdonságú, de nem felső határ tulajdonságú.


DI 90M1654-21644

16

DHARMA Initiative


120. Fogalmazza meg a valós számok egyértelműségét leíró tételt. Legyen ℝ’ és ℝ’’ két felső határ tulajdonságú test. Ekkor létezik egy φ kölcsönösen egyértelmű leképezése ℝ’-nek ℝ’’-re, amely monoton növekedő, összeadás- és szorzástartó. Egy felső határ tulajdonságú testet a valós számok testének nevezzük, az előbbiek értelmében legfeljebb egy ilyen van. 121. Definiálja a bővített valós számokat. A bővített valós számok halmaza: ℝ:= ℝ’( ’ = feslsővonal) ∪{+∞,-∞}.

122. Fogalmazza meg a valós számok létezését leíró tételt.

Létezik felső határ tulajdonságú test. Egy felső határ tulajdonságú testet a valós számok testének nevezzük. 123. Fogalmazza meg a valós számok körében a gyökvonásra vonatkozó tételt. Minden x≥0 valós számhoz és n∈ℕ+ természetes számhoz pontosan egy olyan y≥0 valós 𝑛 szám található, amelyre yn=x. Az y számot az x n-edik gyökének nevezzük és √𝑥 -el 1

jelöljük (n=2 esetén √𝑥-el is) vagy 𝑥 𝑛 -el jelöljük.

124. Fogalmazza meg a valós számok körében a szorzat gyökére vonatkozó állítást. 𝑛 𝑛 𝑛 Ha a és b nemnegatív számok és n∈ℕ+, akkor √𝑎𝑏 = √𝑎 √𝑏. 125. Definiálja a komplex számok halmazát a műveletekkel.

A komplex számok halmaza ℂ = ℝ⨯ℝ, a valós számpárok halmaza az (x,y)+(x',y')=(x+x',y+y') összeadással és az (x,y) · (x',y')=(xx'-y'y,y'x+yx') szorzással, mint műveletekkel. A ℂ test a fenti műveletekkel: a nullelem a (0,0) pár, az (x,y) pár additív inverze a (-x,-y) pár, egységelem az (1,0) pár, és a nullelemtől különböző (x,y) pár multiplikatív inverze az �

𝑥

𝑥 2 +𝑦 2

−

𝑦

𝑥 2 +𝑦 2

� pár.

126. Adja meg ℝ beágyazását ℂ -be. Ha x,x’ ∈ℝ, akkor (x,0) + (x’,0) = (x+x’,0) és (x,0) · (x’,0) = (x · x’,0), így az x →(x,0) leképezés injektív, összeadás- és szorzástartó leképezése ℝ-nek ℂ-be, ezért az összes (x,0) ∈ ℂ, x∈ ℝ alakú komplex számok halmazát azonosíthatjuk ℝ-rel.

127. Definiálja i-t, komplex szám valós és képzetes részét, konjugáltját és a képzetes számok fogalmát.


DI 90M1654-21644

17

DHARMA Initiative


128. Fogalmazza meg a komplex konjugálás tulajdonságait.

129. Definiálja komplex szám abszolút értékét. Milyen tételt használt? A komplex számokat a sík origóból kiinduló vektorainak tekintve a komplex számok abszolút értéke ennek a vektornak a hossza. Azaz az (x,y) ∈ ℂ szám abszolút értéke : |(x,y)| = �𝑥 2 + 𝑦 2 . Ehhez felhasználtuk azt az analízisbeli tételt, mely szerint x ∈ ℝ, x≥0, 𝑛 n n ∈ℕ+: ! ∃y ∈ℝ+ 0 (y = x). Ekkor az y szám n. gyöke, jele: y = √𝑥 .

130. Fogalmazza meg komplex számok abszolút értékének tulajdonságait.

131. Definiálja komplex számokra a sgn függvényt és fogalmazza meg tulajdonságait.

132. Definiálja komplex számok trigonometrikus alakját és argumentumát. Ha 0≠z ∈ℂ, akkor van olyan t valós szám, amelyre sgn(z) = cos t + i sin t. Ha ez az összefüggés fennáll t-re, akkor a t + 2k𝜋, k ∈ℤ számokra is, és csak ezekre. Ekkor z =|z| · (cos t + i sin t), ez a komplex szám trigonometrikus alakja. Ha z = 0, akkor akármilyen t ∈ ℝ szám választható. Ha z≠0 ∈ℂ, akkor z argumentuma (jele: arg(z)) az az egyetlen t valós szám, amelyre –𝜋
DI 90M1654-21644

18

DHARMA Initiative


133. Írja fel két komplex szám szorzatát és hányadosát trigonometrikus alakjuk segítségével. Legyen z,w ∈ ℂ trigonometrikus alakjukban z:=|z| · (cos t + i sin t) és w :=|w| · (cos s + i sin s), ahol t,s ∈ ℝ. Ekkor z és w szorzata valamint hányadosa a trigonometrikus alakjuk segítségével: • z · w = |z| · (cos t + i sin t) · |w| · (cos s + i sin s) = |zw| · (cos t cos s – sin t sin s + i(cos t sin s + cos s sin t)) = |zw| · (cos(t + s) + i sin(t + s)) 134. Ha n ∈ℕ+ és w ∈ ℂ, írja fel a z = w egyenlet összes megoldását. 𝑡+2𝑘𝜋

𝑛

zk = �|𝑤| · �𝑐𝑜𝑠 �

𝑛

𝑡+2𝑘𝜋

� + 𝑖 𝑠𝑖𝑛 �

𝑛

�� k = 0,1, … ,n – 1

135. Írja fel az n-edik komplex egységgyököket. Mit értünk primitív n-edik egységgyök alatt? A 𝜀n = 1 egyenlet megoldásai az n. komplex egységgyökök. Ekkor |𝜀| = 1 és t =0, így: 2𝑘𝜋

2𝑘𝜋

𝜀k = cos� � + i sin� �, k = 0,1,…, n -1 𝑛 𝑛 Azok az n. egységgyökök, amelyek hatványaként az összes többi előáll, az úgynevezett primitív n. komplex egységgyökök. (Például n≥2 esetén 𝜀1 és 𝜀n-1 mindig primitív egységgyökök.)

136. Ha n ∈ ℕ+ és w ∈ ℂ, írja fel a zn = w egyenlet összes megoldását az n-edik egységgyökök segítségével. zk = z · 𝜀k, k = 0,1,…,n – 1

137. Fogalmazza meg az algebra alaptételét. Ha n∈ℕ+, valamint c0,c1,...,cn komplex számok, cn≠0, akkor van olyan z komplex szám, amelyre ∑𝑛𝑘=0 ckzk = 0 .Másként fogalmazva, minden legalább elsőfokú komplex együtthatós algebrai egyenletnek van komplex gyöke. 138. Definiálja halmazok ekvivalenciáját és sorolja fel tulajdonságait. Az X és Y halmazok ekvivalensek, ha létezik X-et Y-ra leképező injektív leképezés. Jelölése: X ∼ Y. Amennyiben X, Y, és Z halmazok, akkor teljesülnek az alábbi tulajdonságok: • • •

Reflexivitás: X ∼ X Szimmetria: X ∼ Y ⇒ Y ∼ X Tranzitivitás: X ∼ Y ∧ Y ∼ Z ⇒ X ∼ Z

139. Ha az X és X’ illetve Y és Y’ halmazok ekvivalensek, milyen más halmazok ekvivalenciájára következtethetünk még ebből? Ha X ∼ X’ és Y ∼ Y’, akkor X⨯Y ∼ X’ ⨯ Y’ az (x,y) →(f(x),g(y)) leképzéssel. Belső terjesztésre!

DI 90M1654-21644

19

DHARMA Initiative


140. Definiálja a véges és a végtelen halmazok fogalmát. Egy X halmaz véges, ha valamely n számra ekvivalens {1,2,…,n} a halmazzal, egyébként végtelen. 141. Definiálja egy véges halmaz elemeinek számát. Hogyan jelöljük? Mit használt fel a definícióhoz? Az az egyértelműen meghatározott természetes szám, mely egy adott X véges halmaz ekvivalens {1,2,…,n}-nel, az X halmaz elemeinek száma, más néven számossága. Jelölése: #(X) vagy card(X). A definícióhoz felhasználtuk, hogy minden halmaz legfeljebb egy n-re ekvivalens {1,2,…,n} halmazzal. 142. Fogalmazza meg a véges halmazok és elemszámuk tulajdonságait leíró tételt. Legyenek X és Y halmazok. Ekkor teljesülnek rájuk a következő tulajdonságok: (1) (2) (3) (4) (5) (6) (7) (8)

Ha X véges és Y⊂ X, akkor Y is véges, és #(Y) ≤ #(X); Ha X véges és Y ⊊ X, akkor #(Y) < #(X); Ha X és Y végesek és diszjunktak, akkor X ∪ Y is véges, és #(X ∪ Y) = #(X) + #(Y); Ha X és Y végesek, akkor #(X ∪ Y) + (X ∩ Y) = #(X) + #(Y); Ha X és Y végesek, akkor X ⨯ Y is véges, és #(X ⨯ Y) = #(X) · #(Y); Ha X és Y végesek, akkor XY is véges, és #(XY) = #(X)#(Y); Ha X véges halmaz, akkor ℘(X) is véges, és #(℘(X)) = 2#(X); Ha X véges és f függvény X-et Y-ra képezi, akkor Y is véges, #(Y) ≤ #(X), és ha f nem injektív, akkor #(Y) < #(X).

143. Fogalmazza meg a skatulyaelvet. Ha X és Y véges halmazok, és #(X) > #(Y), akkor f: X → Y leképezés nem lehet injektív.

144. Mit mondhatunk véges halmazban minimális és maximális elem létezéséről?

Részbenrendezett halmaz bármely nem üres véges részhalmazának van maximális és minimális eleme. 145. Mit mondhatunk egy véges halmaz összes permutációinak számáról? Ha egy A halmaz ekvivalens {1,2,...,n}-nel, akkor permutációinak halmaza ekvivalens {1,2,...,n} permutációinak halmazával. Ha A={a1,a2,...,an} és p1,p2,...,pn az {1,2,...,n} egy permutációja, akkor az A megfelelő permutációja az ai|→api leképzés. Így A permutációinak száma csak n = #(A)-tól függ. Jelölje ezt a számot Pn. Pn=n!.


DI 90M1654-21644

20

DHARMA Initiative


146. Mit értünk egy véges halmaz variációin és mit mondhatunk az összes variációk számáról? Az A halmaz elemeiből készíthető, különböző tagokból álló a1,a2,…,an sorozatokat, azaz {1,2,…,n}-t A-ba képező kölcsönösen egyértelmű leképzéseket az A halmaz k-ad osztályú variációinak nevezzük. Ha A véges halmaz, #(A)=n, akkor ezek 𝑉𝑛𝑘 száma megegyezik az {1,2,..,k}-t {1,2,…,n}-be képező kölcsönösen egyértelmű leképezések számával. 𝑉𝑛𝑘 =

n! (n−k)!

= n(n − 1) … (n − k + 1), ha k ≤ n, egyébként 0.

147. Definiálja az ismétléses variációk fogalmát. Mit mondhatunk egy véges halmaz összes ismétléses variációinak számáról? Az A halmaz elemeiből készíthető a1,a2,…,ak sorozatokat, azaz {1,2,…,k}-t A-ba képező leképezéseket az A halmaz k-ad osztályú ismétléses variációinak nevezzük. Ha A véges halmaz, #(A) = n, akkor ezek i𝑉𝑛𝑘 számáról (a 𝑉𝑛𝑘,𝑖 jelölés is szokásos) már tudjuk, hogy nk. 148. Mit értünk egy véges halmaz kombinációin és mit mondhatunk az összes kombinációk számáról? Ha k ∈ℕ, akkor A halmaz k elemű részhalmazait az A halmaz k-ad osztályú kombinációinak nevezzük. Ha A véges halmaz, akkor #(A)=n, akkor ezek 𝐶𝑛𝑘 száma megegyezik a {1,2,…,n} 𝑛! halmaz k elemű részhalmazainak számával. 𝐶𝑛𝑘 = = �𝑛𝑘�, ha k≤n, egyébként 0. 𝑘!(𝑛−𝑘)!

149. Mit értünk egy véges halmaz ismétléses kombinációin és mit mondhatunk az összes ismétléses kombinációk számáról? Ha k ∈ℕ, akkor A halmazból k elemet kiválasztva, de ismétléseket is megengedve, nem tekintve a sorrendre, az A halmaz k-ad osztályú ismétléses kombinációit kapjuk. Pontosabban, tekintsük mindazokat az f:A→ℕ függvényeket, amelyek csak véges sok helyen vesznek fel nem nulla értéket, és ezen értékek összege k; ezek az A halmaz ismétléses kombinációi. Ha A véges halmaz, akkor #(A)=n, így feltehetjük, hogy A={1,2,..,n}. Minden g:{1,2,..,k}→{1,2,...,n} monoton növekedő hozzárendelve az f(j) = # (g-1(j)) függvényt, kölcsönösen egyértelmű megfeleltetést kapunk. A ismétléses kombinációi és az {1,2,...,k}-t {1,2,...,n}-be képező monoton növekedő függvények között, így ezek száma az A ismétléses kombinációinak i𝐶𝑛𝑘 száma. i𝐶𝑛𝑘 = �𝑛+𝑘−1 � 𝑘

150. Mit értünk egy véges halmaz ismétléses permutációin és mit mondhatunk az összes ismétléses permutációk számáról?

Ha r,i1,i2,...,ir ∈ℕ, akkor az a1,a2,...,ar (különböző) elemek i1,i2,...,ir ismétlődésű ismétléses permutációi az olyan n=i1+i2+...+ir-tagú sorozatok, amelyekben az aj elem ij-szer fordul elő. Az A={a1,a2,...,ar} jelöléssel ezek olyan {1,2,...,n}-et A-ba képező leképzések, amelyeknél aj teljes inverz kepe ij elemű.


DI 90M1654-21644

21

DHARMA Initiative


151. Fogalmazza meg a binomiális tételt. Legyenek x,y egy R kommutatív egységelemes gyűrű elemei, n∈ℕ Ekkor: 𝑛

𝑛 (𝑥 + 𝑦)𝑛 = � � � 𝑥 𝑘 𝑦 𝑛−𝑘 𝑘 𝑘=0

152. Írja fel a Pascal-háromszög első 8 sorát.

1

1

6

5

4

3

2 6

1 3

1 4

1

1

10 10 5 1 15 20 15 6 1 7 21 35 35 21 7 1 8 28 56 70 56 28 8 1

1

1

1

1

1

1

1

153. Mennyi a binomiális együtthatók összege, illetve váltakozó előjellel vett összege? n

𝑛

k=0

𝑘=0

n 𝑛 � � � =2n é𝑠 � � � (−1)𝑘 = 0 k 𝑘

154. Fogalmazza meg a polinomiális tételt.

155. Fogalmazza meg a logikai szita formulát.


DI 90M1654-21644

22

DHARMA Initiative


156. Definiálja a természetes számok körében az oszthatóságot és adja meg a jelölését. Az m természetes számot az n természetes szám osztójának, az n-et pedig m többszörösének nevezzük, illetve azt mondjuk, hogy n osztható m-el, ha van olyan k természetes szám, hogy n=mk. jelölése: m|n. 157. Sorolja fel a természetes számok körében az oszthatóság alaptulajdonságait. A természetes számok körében (1) ha m|n és m'|n', akkor mm'|nn'; (2) a nullának minden természetes szám osztója; (3) a nulla csak saját magának osztója; (4) az 1 minden természetes számnak az osztója; (5) ha m|n, akkor mk|nk minden k ∈ℕ-re; (6) ha k∈ℕ+ és mk|nk, akkor m|n; 𝑗 (7) ha m|ni és ki∈ℕ, (i=1,2,...,j), akkor m|∑𝑖=1 𝑘𝑖 𝑛𝑖 ; (8) bármely nem 0 természetes szám bármely osztója kisebb vagy egyenlő, mint a szám; (9) az | reláció reflexív, tranzitív és antiszimmetrikus, azaz részbenrendezés. 158. Definiálja a természetes számok körében a prímszám és a törzsszám fogalmát. Mi a kapcsolat a két fogalom között? Az n>1 természetes szám törzsszám, ha az 1-en és saját magán kívül nincs más osztója, azaz csak triviális módon, 1·n = n · 1 alakban írható fel természetes számok szorzataként. A p>1 természetes számot prímszámnak nevezzük, ha p|km (k,m∈ℕ) eseten p|k vagy p|m. A törzsszámok és prímszámok halmaza egyenlő. 159. Definiálja egységelemes integritási tartományban az oszthatóságot és adja meg a jelölését. Egy R egységelemes integritási tartományban, ha a,b∈R, akkor b az a osztója, vagy a a b többszöröse, azaz a osztható b-vel, ha van olyan c∈R, hogy a=bc. jelölése b|a. 160. Sorolja fel egységelemes integritási tartományban az oszthatóság alaptulajdonságait. Egy egységelemes integritási tartomány elemei körében (1) ha a|b és a'|b', akkor aa'|bb'; (2) a 0-nak minden természetes szám osztója; (3) a 0 csak saját magának osztója; (4) az 1 minden elemnek az osztója; (5) ha b|a, akkor bc|ac minden c ∈R -re; (6) ha bc|ac és c≠0, akkor b|a; 𝑗 (7) ha b|ai és ci∈R, (i=1,2,...,j), akkor b|∑𝑖=1 𝑐𝑖 𝑎𝑖 (8) az | reláció reflexív és tranzitív.


DI 90M1654-21644

23

DHARMA Initiative


161. Definiálja az asszociáltak fogalmát és sorolja fel ennek a kapcsolatnak a tulajdonságait. Ha egy R egységelemes integritási tartomány a és b elemére igaz, hogy a|b ∧ b|a, akkor a és b asszociáltak. Ez a reláció ekvivalenciareláció, továbbá kompatibilis a szorzással. A nullának (nullelem) mindig csak saját maga az asszociáltja. A | reláció kompatibilis ezzel az ekvivalenciarelációval, és az ekvivalenciaosztályokon tekintve részbenrendezést kapunk. 162. Definiálja az egységek fogalmát és sorolja fel az egységek halmazának tulajdonságait. Az egységek az 1 (egységelem) asszociáltjai. Egy elem asszociáltjait leírhatjuk az egységek segítségével, amelyek nem mások, mint 1 osztói, hiszen 1 bárminek osztója. Másképpen: az egységek R egységelemes integritási tartomány azon elemei, amelyeknek van a szorzásra nézve inverzük. Az egységek a szorzásra nézve Abel-csoportot alkotnak, a gyűrű egységcsoportját. Az egységek bármely a ∈R-nak osztói, mert 1a-nak osztói.

163. Mi a kapcsolat az egységek és az asszociáltak között?

Az a ∈R asszociáltjai az 𝜀a alakú elemek, ahol 𝜀 egység, R pedig egységelemes integritási tartomány. 164. Mi a kapcsolat a természetes számok és az egész számok körében vett oszthatóság között? Mivel ha k,m ∈ℤ, akkor |km| = |k| · |m|, az egész számok körében m|n pontosan akkor teljesül, ha |m|||n| az ℕ-ben.

165. Definiálja a Gauss-egészek gyűrűjét. Igaz-e, hogy két egység van?

A Gauss-egészek egységelemes gyűrűje: G = {n + im: n,m ∈ℤ} ⊂ ℂ. Négy egység van ±1 és ±i.

166. Definiálja egységelemes integritási tartományban a prímelem és az irreducibilis elem fogalmát. Mi a kapcsolat a két fogalom között? Az R egységelemes integritási tartomány egy a ≠ 0 eleme felbonthatatlan (más néven: irreducibilis), ha nem egység, és csak triviális módon írható fel szorzatként, tehát a =bc (b,c ∈R) esetén b vagy c egység. A 0≠p ∈R elem prímelem, ha nem egység, és p|ab (a,b ∈R) esetén p|a vagy p|b. A felbonthatatlan elemek és prímelemek halmaza egyenlő.

167. Mit értünk egységelemes integritási tartományban legnagyobb közös osztó alatt? Az R egységelemes integritási tartományban az a1,a2,…,an ∈ R elemeknek a b ∈R elem legnagyobb közös osztója, ha i = 1,2,…,n esetén b|ai és b’|ai, akkor b’|b.


DI 90M1654-21644

24

DHARMA Initiative


168. Mikor mondjuk egységelemes integritási tartomány elemeire, hogy relatív prímek? Az R egységelemes integritási tartományban az a1,a2,…,an ∈ R elemek legnagyobb közös osztói egységek, akkor a1,a2,…,an relatív prímek. 169. Mit értünk egységelemes integritási tartományban legkisebb közös többszörös alatt? Az R egységelemes integritási tartományban az a1,a2,…,an ∈ R elemeknek a b ∈R elem legkisebb közös többszöröse, ha i = 1,2,…,n esetén b’|ai, akkor b|b’. 170. Egyértelmű-e az egész számok körében a legnagyobb közös osztó? Ismertesse a kapcsolódó jelölést. Nem. Az a1,a2,…,an ∈ℤ számok legnagyobb közös osztói közül az egyik nemnegatív, ezt lnko(a1,a2,…,an)-nel jelöljük. (Használt jelölés még az gcd(a1,a2,…,an) és az (a1,a2,…,an) is.)

171. Egyértelmű-e az egész számok körében a legkisebb közös többszörös? Ismertesse a kapcsolódó jelölést.

Nem. A a1,a2,…,an ∈ℤ számok legkisebb közös többszörösei közül az egyik nemnegatív, ezt lkkt(a1,a2,…,an)-nel jelöljük. (Használt jelölés még az lcm(a1,a2,…,an) és az [a1,a2,…,an] is.)

172. Ismertesse a bővített euklideszi algoritmust.

173. Mely tétel alapján számolhatjuk ki véges sok egész szám legnagyobb közös osztóját prímfelbontás nélkül? Bármely a1,a2,…,an ∈ ℤ számoknak létezik legnagyobb közös osztója, és: lnko(a1,a2,…,an) = lnko(lnko(a1,a2),a3,a4,…,an). 174. Fogalmazza meg a számelmélet alaptételét. Minden pozitív természetes szám a sorrendtől eltekintve egyértelműen felbontható prímszámok szorzataként. 175. Definiálja prímtényezős felbontásnál a kanonikus alakot.


DI 90M1654-21644

25

DHARMA Initiative


A számelmélet alaptételében szereplő prímtényezős felbontást gyakran α α α α 𝑛 = 𝑝1 1 𝑝2 2 𝑝3 3 … 𝑝𝑘 k alakban írjuk, ahol p1,p2,...,pk különböző prímek, a kitevők pedig ℕ+ elemei. Ezt nevezzük a szám kanonikus alakjának. 176. Hogyan határozhatók meg természetes számok esetén az osztók, a legnagyobb közös osztó és a legkisebb közös többszörös a prímtényezős felbontás segítségével? Ha adott a szám kanonikus alakban, akkor azok a természetes számok osztják a-t, amelyek kanonikus alakjában csak a prímtényezői szerepelnek és egyik prímtényező sem szerepel nagyobb hatványon, mint a kanonikus alakjában. Formálisan: a kanonikus alakja legyen α α α α 𝑝1 1 𝑝2 2 𝑝3 3 … 𝑝𝑘 k , ekkor: α

α

α

α

∀b ∈ℕ (b|a) ⇔ b = 𝑝1 1 𝑝2 2 𝑝3 3 … 𝑝𝑘 k : 𝛽i ≤ 𝛼i, (i = 1,2,…k).

Bármely a1,a2,...,an ∈ ℕ számok legnagyobb közös osztóját és legkisebb közös többszörösét úgy kapjuk meg, hogy ha felírjuk mindegyik szám kanonikus alakját úgy kiegészítve, hogy mindegyikben ugyanazok a prímtényezők szerepeljenek (a feleslegesek a 0. hatványon), akkor: α

α

α

α

ai = 𝑝1 1 𝑝2 2 𝑝3 3 … 𝑝𝑘 k , (i = 1,2,…,k),

177. Mi a kapcsolat két egész szám legnagyobb közös osztója és legkisebb közös többszöröse között? lnko(a,b) · lkkt(a,b) = |ab| 178. Hogyan számolhatjuk ki véges sok egész szám legkisebb közös többszörösét prímfelbontás nélkül? Tetszőleges a1,a2,...,an ∈ℤ számoknak létezik legkisebb közös többszöröse, és lkkt(a1,a2,...,an)=lkkt(lkkt(a1,a2),...,an). 179. Ismertesse Eratoszthenész szitáját. Ha egy adott n-ig az összes prímet meg akarjuk tálalni, a következő egyszerű eljárás hatékony módszert ad: írjuk fel a számokat 2-től n-ig. Az első szám, a 2 prím, összes (valódi) többszöröse összetett, ezeket húzzuk ki. A megmaradó számok közül az első a 3, ez prím, ennek minden (valódi) többszöröse összetett, ezeket húzzuk ki stb. Az eljárás végén az n-nél nem nagyobb prímek maradnak meg. 180. Definiálja egész számok kongruenciáját és adja meg a kapcsolódó jelöléseket. Ha a,b,m ∈ℤ és m osztója a - b-nek, akkor azt mondjuk, hogy a és b kongruensek modulo m. Ezt úgy jelöljük, hogy a ≡ b(mod m). 181. Fogalmazza meg az egész számok kongruenciájának egyszerű tulajdonságait.


DI 90M1654-21644

26

DHARMA Initiative


Ha a ≡ b(mod m) és d|m, akkor a ≡ b(mod m) is teljesül. Ha 0≠d ∈ℤ, akkor a≡b(mod m) ekivalens azzal, hogy ad≡bd(mod md). Az oszthatóság tulajdonságaiból következik, hogy bármely adott m∈ℤ-re a kongruencia ekvivalenciareláció ℤ -ben. Az m és a -m szerinti kongruencia ugyanazt jelenti. 182. Definiálja a maradékosztály, redukált maradékosztály, teljes és redukált maradékrendszer fogalmát. Egy m∈ℤ modulus szerinti kongruencia ekvivalenciaosztályait maradékosztályoknak nevezzük. Ha egy maradékosztály valamelyik eleme relatív prím a modulushoz, akkor mindegyik, és ekkor a maradékosztály redukált maradékosztálynak nevezzük. Páronként inkongruens egészek egy rendszerét maradékrendszernek nevezzük. Ha egy maradékrendszer minden maradékosztályából tartalmaz elemet, akkor teljes maradékrendszernek nevezzük. Ha egy maradékrendszer pontosan a redukált maradékosztályokból tartalmaz elemet, akkor redukált maradékrendszernek nevezzük. 183. Definiálja ℤm-et. Milyen algebrai struktúra ℤm?

Egy m∈ ℤ modulus szerinti kongruencia ekvivalenciaosztályait maradékosztályoknak nevezzük. A kongruencia kompatibilis az összeadással és a szorzással. Az ekvivalenciaosztályok kommutatív egységelemes gyűrűt alkotnak az összeadással és a szorzással. Ezt a gyűrűt ℤm-el jelöljük.

184. Ismertesse a komplemens ábrázolásokat.

Negatív számok számítógépes ábrázolására elterjedt a komplemens ábrázolás. Csak bináris gépek esetével foglalkozunk. Egy n-bites számítógépen használt lehetőségek 0≤k<2n-1 eseten –k ábrázolására: 1. -k mod (2n-1) kettes számrendszerbeli alakját tároljuk. Ezt úgy kapjuk, hogy k kettes számrendszerbeli alakját levonjuk 2n-1 kettes számrendszerbeli alakjából. Mivel ez utóbbi csupa egyesből áll, a kivonás során nincs átvitel, k kettes számrendszerbeli alakját csak bitenként komplementáljuk. (egyesekre komplementálás) 2. Kettes komplementálás: k mod 2n kettes számrendszerbeli alakját tároljuk. Ezt úgy kapjuk, hogy k kettes számrendszerbeli alakjának vesszük a bitenkénti komplementerét, majd hozzáadunk 1-et. 185. Fogalmazza meg a ℤm gyűrű tulajdonságait leíró tételt.

Legyen m>1 egész. Ha 1
186. Ismertesse a diszkrét logaritmus problémát.

ℤm-ben nem nehéz hatványozni. Azonban a tapasztalat szerint még ha m prím is, ℤm invertálható elemeinek multiplikatív csoportjában egy a alap és egy ak hatvány ismeretében nehéz meghatározni a k kitevőt, legalábbis ha m-1-nek vannak nagy prímtényezői: ez a diszkrét logaritmus probléma. A probléma számos más csoport esetén is nehéznek tűnik. Belső terjesztésre!

DI 90M1654-21644

27

DHARMA Initiative


187. Ismertesse a Diffie–Hellmann–Merkle kulcscserét. A felhasználók megállapodnak egy nagy Sophie Germain prímben, azaz olyan p prímben, amelyre q=2p+1 is prím valamint egy 10 egész szám, és jelölje ϕ (m) a modulo m redukált maradékosztályok számát; ϕ az Euler-féle ϕ függvény. 189. Mit mondhatunk az aai + b számokról, ha ai egy maradékrendszer, illetve egy redukált maradékrendszer elemeit futja be? Legyen m>1 egész szám, a relatív prím m-hez. Ha a1,a2,...,am teljes maradékrendszer modulo m és b∈ℤ, akkor aa1+b, aa2+b,..., aam+b is teljes maradékrendszer modulo m. Ha a1,a2,...,a ϕ (m) redukált maradékrendszer modulo m, akkor aa1,aa2,...,aa ϕ (m) is redukált maradékrendszer modulo m. 190. Fogalmazza meg az Euler–Fermat-tételt. Legyen m>1 egész szám, a relatív prím m-hez. Ekkor a 𝜑(m) ≡1 (mod m). 191. Fogalmazza meg a Fermat-tételt. Legyen p prímszám. Ha a∈ℤ és p∤a akkor ap-1≡1 (mod p). Ha a∈ℤ tetszőleges, akkor ap≡1 (mod p). 192. Mit értünk diofantikus problémán? Ha egy egyenlet vagy egyenletrendszer egész megoldásait keressük, akkor diofantikus problémáról beszélünk. 193. Mondjon két példát diofantikus problémára. •

x2 + y2 = -4, nincs se egész, se valós megoldása.

•

x4 – 4y4 = 3, nincs egész megoldása, mivel x4 – 4y4 ≡ 0 ∨ 1 (mod 4), míg 3 ≡ 3 (mod 4).

194. Fogalmazza meg a kínai maradéktételt.

Legyenek m1,m2,...mn egynél nagyobb, páronként relatív prím természetes számok,


DI 90M1654-21644

28

DHARMA Initiative


c1,c2,...,cn∈ℤ. Az x∈cj (mod mj), j=1,2,...,n kongruenciarendszer megoldható, és bármely két megoldása kongruens modulo m1,m2,...mn.


DI 90M1654-21644

29

DHARMA Initiative Diszkrét Matematika 1. DHARMA INITIATIVE

Recommend Documents