Véges és végtelen halmazok, részhalmazok száma, logikai szitafórmula módszere
A kombinatorika és halmazelmélet metszéspontjában található a számosság és a logikai szita (szitafórmula) fogalomköre. Ezen az oldalon megismerkedhetsz a véges és végtelen halmazok alapjaival, a részhalmazok számának meghatározásával (hatványhalmaz), valamint a 2 és 3 halmazra vonatkozó logikai szita (szita-elv) alkalmazásával. Ez a módszer elengedhetetlen a bonyolultabb, halmazok uniójának elemszámát vizsgáló emelt szintű érettségi feladatok megoldásához!
Adott az \( A = \{1, 2, 3, 4, 5, 6\} \) halmaz. Hány részhalmaza van az \( A \) halmaznak?
Egy \( n \) elemű halmaz részhalmazainak száma \( 2^n \).
Mivel a halmaznak 6 eleme van (\( n = 6 \)), így a részhalmazok száma: \[ 2^6 = 64 \]
Egy véges halmaznak pontosan 2048 részhalmaza van. Hány elemű a halmaz?
Tudjuk, hogy az \( n \) elemű halmaz részhalmazainak száma \( 2^n \).
A feladat szerint \( 2^n = 2048 \).
Mivel \( 2^{10} = 1024 \) és \( 2^{11} = 2048 \), ezért a halmaz 11 elemű.
Legyen \( B = \{a, b, c, d, e\} \). Hány olyan részhalmaza van a \( B \) halmaznak, amely tartalmazza az \( a \) elemet?
Ha egy részhalmaznak mindenképpen tartalmaznia kell az \( a \) elemet, akkor az \( a \) sorsa eldőlt (benne van).
A maradék 4 elem (\( b, c, d, e \)) mindegyikénél két lehetőségünk van: vagy beletesszük a részhalmazba, vagy nem.
Ezért a megfelelő részhalmazok száma a maradék elemekből képzett részhalmazok számával egyenlő: \[ 2^4 = 16 \]
Adott az \( \{1, 2, 3, 4, 5, 6, 7\} \) halmaz. Hány olyan részhalmaza van, amely tartalmazza a 2-t, de nem tartalmazza a 3-at?
A 2-es elem benne kell legyen (1 lehetőség), a 3-as elem nem lehet benne (1 lehetőség).
A maradék 5 elem (\( 1, 4, 5, 6, 7 \)) mindegyike vagy benne van, vagy nincs (elemenként 2 lehetőség).
Így a keresett részhalmazok száma: \[ 2^5 = 32 \]
Hány 3 elemű részhalmaza van egy 8 elemű halmaznak?
Egy \( n \) elemű halmaz \( k \) elemű részhalmazainak számát a binomiális együttható adja meg: \( \binom{n}{k} \).
Jelen esetben: \[ \binom{8}{3} = \frac{8!}{3!(8-3)!} = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 56 \]
Egy 5 elemű halmaz esetén számítsa ki a 0, 1, 2, 3, 4 és 5 elemű részhalmazok számát, majd igazolja, hogy összegük megegyezik a halmaz összes részhalmazának számával!
A binomiális együtthatók kiszámítása:
Ezek összege: \( 1 + 5 + 10 + 10 + 5 + 1 = 32 \).
Az összes részhalmaz száma képlettel: \( 2^5 = 32 \). A két érték megegyezik.
Döntse el, hogy az alábbi állítás igaz vagy hamis, és indokolja válaszát: 'A természetes számok halmaza (\( \mathbb{N} \)) és az egész számok halmaza (\( \mathbb{Z} \)) egyenlő számosságú.'
Igaz.
Két halmaz pontosan akkor egyenlő számosságú, ha létesíthető köztük kölcsönösen egyértelmű megfeleltetés (bijekció).
Az egész számokat sorba lehet rendezni úgy, hogy megszámlálhatóak legyenek: \( 0, 1, -1, 2, -2, 3, -3, \dots \)
Így minden egész számhoz egyértelműen hozzárendelhető egy természetes szám (pl. \( f(n) = 2n \) ha \( n \ge 0 \), és \( f(n) = -2n - 1 \) ha \( n < 0 \)), tehát számosságuk megegyezik (mindkettő megszámlálhatóan végtelen, azaz \( \aleph_0 \) számosságú).
Legyen \( |A| = 25 \), \( |B| = 15 \) és az unió számossága \( |A \cup B| = 32 \). Határozza meg a metszet (\( |A \cap B| \)) számosságát!
A logikai szita (szita-formula) két halmaz esetén: \[ |A \cup B| = |A| + |B| - |A \cap B| \]
Behelyettesítve az ismert értékeket: \[ 32 = 25 + 15 - |A \cap B| \]
\[ 32 = 40 - |A \cap B| \]
\[ |A \cap B| = 8 \]
Egy 40 fős osztályban mindenki tanul angolul vagy németül. 28-an tanulnak angolul, 22-en németül. Hányan tanulják mindkét nyelvet?
Jelölje \( A \) az angolul, \( N \) a németül tanulók halmazát.
Mivel mindenki tanul legalább egy nyelvet, az unió kiadja az egész osztályt: \( |A \cup N| = 40 \).
A formula alapján: \[ |A \cup N| = |A| + |N| - |A \cap N| \]
\[ 40 = 28 + 22 - |A \cap N| \]
\[ 40 = 50 - |A \cap N| \]
\[ |A \cap N| = 10 \]
Tehát 10 diák tanulja mindkét nyelvet.
Egy felmérés során 100 embert kérdeztek meg. Kiderült, hogy 60 ember szereti a kávét, 50 ember szereti a teát, és 15 ember egyiket sem szereti. Hány ember szereti a kávét is és a teát is?
Jelölje az alaphalmazt \( U \) (\( |U| = 100 \)). A kávét szeretők halmaza \( K \) (\( |K|=60 \)), a teát szeretők halmaza \( T \) (\( |T|=50 \)).
Akik egyiket sem szeretik, azok halmaza az unió komplementere, számosságuk 15. Ebből az unió számossága: \[ |K \cup T| = |U| - 15 = 100 - 15 = 85 \]
A logikai szita formulával: \[ |K \cup T| = |K| + |T| - |K \cap T| \]
\[ 85 = 60 + 50 - |K \cap T| \]
\[ 85 = 110 - |K \cap T| \implies |K \cap T| = 25 \]
25 ember szereti mindkét italt.
Hány olyan egész szám van 1 és 100 között (a határokat is beleértve), amely osztható 2-vel vagy 3-mal?
Legyen \( A \) a 2-vel, \( B \) a 3-mal osztható számok halmaza 1 és 100 között.
\( |A| = \lfloor 100 / 2 \rfloor = 50 \)
\( |B| = \lfloor 100 / 3 \rfloor = 33 \)
A metszet (\( A \cap B \)) a 2-vel és 3-mal is, azaz 6-tal osztható számok halmaza:
\( |A \cap B| = \lfloor 100 / 6 \rfloor = 16 \)
A keresett unió számossága: \[ |A \cup B| = |A| + |B| - |A \cap B| = 50 + 33 - 16 = 67 \]
Hány olyan egész szám van 1 és 200 között, amely osztható 2-vel, de nem osztható 5-tel?
Jelölje \( A \) a 2-vel osztható számok halmazát, \( B \) az 5-tel osztható számok halmazát.
A keresett halmaz az \( A \setminus B \) halmaz (a 2-vel oszthatók, mínusz amik 5-tel is, vagyis 10-zel). Képlete: \[ |A \setminus B| = |A| - |A \cap B| \]
\( |A| = \lfloor 200 / 2 \rfloor = 100 \)
\( A \cap B \) a 10-zel osztható számok halmaza: \( |A \cap B| = \lfloor 200 / 10 \rfloor = 20 \)
A megoldás: \[ 100 - 20 = 80 \]
Egy 50 fős társaságban 25-en tudnak angolul, 20-an németül, 15-en franciául. 10-en tudnak angolul és németül, 8-an angolul és franciául, 5-en németül és franciául. 3-an mindhárom nyelven tudnak. Hányan nem beszélnek egyet sem a három nyelv közül?
A 3 halmazra vonatkozó logikai szita-formula:
\[ |A \cup N \cup F| = |A| + |N| + |F| - |A \cap N| - |A \cap F| - |N \cap F| + |A \cap N \cap F| \]
Behelyettesítve: \[ |A \cup N \cup F| = 25 + 20 + 15 - 10 - 8 - 5 + 3 \]
\[ |A \cup N \cup F| = 60 - 23 + 3 = 40 \]
Tehát 40-en beszélnek legalább egy nyelvet. Akik egyet sem beszélnek: \[ 50 - 40 = 10 \]
Egy 100 fős évfolyamon 60-an szeretik a matekot, 55-en a fizikát és 40-en az informatikát. Aki szereti az informatikát, az szereti a matekot is. A fizikát és matekot is szeretők száma 30, a fizikát és informatikát is szeretők száma 15. Hány diák szereti mindhárom tárgyat?
Mivel mindenki, aki szereti az informatikát (\( I \)), szereti a matekot is (\( M \)), ez azt jelenti, hogy \( I \subset M \).
Ebből következik, hogy aki szereti a fizikát (\( F \)) és az informatikát (\( I \)), az automatikusan szereti a matekot (\( M \)) is!
Tehát a mindhárom tárgyat szeretők halmaza (\( M \cap F \cap I \)) megegyezik a fizikát és informatikát szeretők halmazával (\( F \cap I \)).
A feladat szövege szerint \( |F \cap I| = 15 \).
Tehát 15 diák szereti mindhárom tárgyat.
A 13. feladat adatait felhasználva (50 fő, 25 A, 20 N, 15 F; metszetek: 10 AN, 8 AF, 5 NF; 3 mind), számítsa ki, hányan beszélnek pontosan egy nyelvet!
A pontosan egy halmazba tartozók számának képlete:
\( |Csak A| = |A| - |A \cap N| - |A \cap F| + |A \cap N \cap F| \)
Összesen pontosan egy nyelvet beszélnek: \[ 10 + 8 + 5 = 23 \]
Legyenek \( A \) és \( B \) halmazok. Tudjuk, hogy \( |A \setminus B| = 12 \), \( |B \setminus A| = 18 \) és \( |A \cup B| = 40 \). Mennyi \( |A| \), \( |B| \) és \( |A \cap B| \) értéke?
Az uniót felbonthatjuk három diszjunkt részre:
\( |A \cup B| = |A \setminus B| + |A \cap B| + |B \setminus A| \)
Behelyettesítve a megadott értékeket: \[ 40 = 12 + |A \cap B| + 18 \] \[ 40 = 30 + |A \cap B| \implies |A \cap B| = 10 \]
Most már kiszámolhatjuk az \( A \) és \( B \) számosságát:
Egy 7 elemű halmaznak hány legalább 2 elemű részhalmaza van?
Ahelyett, hogy összeadnánk a 2, 3, 4, 5, 6, 7 elemű részhalmazokat, érdemes a komplementer módszert választani.
Az összes részhalmaz száma: \( 2^7 = 128 \).
A legfeljebb 1 elemű (azaz 0 vagy 1 elemű) részhalmazok száma:
Ezek összege \( 1 + 7 = 8 \).
A legalább 2 elemű részhalmazok száma tehát: \[ 128 - 8 = 120 \]
Adott a \( C = \{1, 2, 3\} \) és a \( D = \{a, b, c, d\} \) halmaz. Hány eleme van a \( C \times D \times C \) halmaznak?
Egy Descartes-szorzat elemszáma a tényezők elemszámának szorzata:
\[ |C \times D \times C| = |C| \cdot |D| \cdot |C| \]
A feladat alapján \( |C| = 3 \) és \( |D| = 4 \).
A szorzat elemszáma: \[ 3 \cdot 4 \cdot 3 = 36 \]
Legyen az értelmezési tartomány \( X = \{1, 2, 3, 4\} \) és az értékkészlet egy része \( Y = \{A, B, C\} \). Hány különböző \( f: X \to Y \) függvény adható meg?
Minden \( x \in X \) elemhez az \( Y \) halmaz bármelyik elemét hozzárendelhetjük.
Mivel az \( X \) halmaznak 4 eleme van, és mindegyikhez 3 lehetséges értékből választhatunk a \( Y \) halmazból, a variáció ismétléssel szabálya alapján a függvények száma:
\[ |Y|^{|X|} = 3^4 = 81 \]
Az előző feladat (19) halmazai esetén (\( |X| = 4, |Y| = 3 \)) létezik-e injektív (kölcsönösen egyértelmű) függvény \( X \)-ből \( Y \)-ba? Válaszát indokolja (skatulya-elv)!
Nem létezik.
Egy függvény pontosan akkor injektív, ha az értelmezési tartomány különböző elemeihez a képhalmaz különböző elemeit rendeli.
Mivel \( |X| = 4 \) elemünk van, de csak \( |Y| = 3 \) különböző értéket tudunk felvenni, a skatulya-elv (skatulya-elv / Dirichlet-elv) alapján legalább két \( X \)-beli elemhez ugyanazt az \( Y \)-beli értéket kell rendelnünk.
Általánosan: injektív függvény \( A \to B \) csak akkor létezik, ha \( |A| \le |B| \).