Matematika közlek A1a 2013/2. gyakorlat

A MathWikiből
(Változatok közti eltérés)
(Hatványhalmaz)
 
(egy szerkesztő 6 közbeeső változata nincs mutatva)
1. sor: 1. sor:
==Halmatalgebra==
+
==Halmazalgebra==
 
===Megjegyzés===
 
===Megjegyzés===
 
Az és és a vagy logikai operátoraival analóg a ∀ és ∃, azaz "minden" és "létezik" szavakra vonatkozó szabályok is. A ∀ az ∧-sel rokonítható, az ∃ a ∨-gyal. Ezek az operátorok nem két mondatot kapcsolnak össze, hanem sok mondatra vonatkoznak egyszerre, abban az értelemben, hogy egy ''A(x)'' predikátumból (nyitott mondatból) készítenek egy új mondatot. Például az ''A(x)'' := ''x-nek van emelt szintű matematika érettségije'' nyitott mondatból a ∃ a (∃x)''A(x)'' := ''van akinek van emelt szintű matematika érettségije'' mondatot képezi, a ∀  a (∀x)''A(x)'' := ''mindenkinek van emelt szintű matematika érettségije'' mondatot képezi. Az előbbi azt jelenti, hogy a "jelenlévők" közül (az "alaphalmazból") valakinek azaz Pistinek, ''vagy'' Bélának, ''vagy'' Cilinek ill. valakinek van emelt érettségije matekból -- persze '''nem kell feltétlenül tudnunk''', hogy kinek; az utóbbi pedig, hogy Pistinek is ''és'' Bélának is ''és'' Cilinek is ''és'' Daniellának is ''és'' ... mindenkinek megvan az emelt matekja.   
 
Az és és a vagy logikai operátoraival analóg a ∀ és ∃, azaz "minden" és "létezik" szavakra vonatkozó szabályok is. A ∀ az ∧-sel rokonítható, az ∃ a ∨-gyal. Ezek az operátorok nem két mondatot kapcsolnak össze, hanem sok mondatra vonatkoznak egyszerre, abban az értelemben, hogy egy ''A(x)'' predikátumból (nyitott mondatból) készítenek egy új mondatot. Például az ''A(x)'' := ''x-nek van emelt szintű matematika érettségije'' nyitott mondatból a ∃ a (∃x)''A(x)'' := ''van akinek van emelt szintű matematika érettségije'' mondatot képezi, a ∀  a (∀x)''A(x)'' := ''mindenkinek van emelt szintű matematika érettségije'' mondatot képezi. Az előbbi azt jelenti, hogy a "jelenlévők" közül (az "alaphalmazból") valakinek azaz Pistinek, ''vagy'' Bélának, ''vagy'' Cilinek ill. valakinek van emelt érettségije matekból -- persze '''nem kell feltétlenül tudnunk''', hogy kinek; az utóbbi pedig, hogy Pistinek is ''és'' Bélának is ''és'' Cilinek is ''és'' Daniellának is ''és'' ... mindenkinek megvan az emelt matekja.   
113. sor: 113. sor:
 
:::<math>=(A\setminus B)\cup (A\cap C)</math>
 
:::<math>=(A\setminus B)\cup (A\cap C)</math>
  
==Cáfoló példák, cáfoló szituációk==
+
 
 +
'''5. feladat.''' Egyszerűsítse az alábbi kifejezéseket!
 +
## <math>(A\cap B\cap C)\cup (A\cap B\cap \overline{C})\cup(A\cap \overline{B}\cap C)\cup(A\cap \overline{B}\cap \overline{C})=?</math>
 +
## <math>(A\cap B)\cup C=?</math>, ha <math>A\subseteq C</math>.
 +
 
 +
''Mo.''
 +
1.1. Legyen ''D'' a feladatban szereplő halmaz és legyen ''U'' = ''A'' U ''B'' U ''C'' a komplementerképzés alaphalmaza! Emeljünk ki ''A''-t!
 +
:<math>D=A\cap ((B\cap C)\cup (B\cap \overline{C})\cup(\overline{B}\cap C)\cup(\overline{B}\cap \overline{C}))=</math>
 +
A második tényező első két tagjából kiemelhetünk ''B''-t a második két tagjából ''B'' komplementert:
 +
:<math>=A\cap ((B\cap (C\cup \overline{C}))\cup(\overline{B}\cap (C\cup\overline{C})))=</math>
 +
ekkor a halmaz és komplementere kiadja ''U''-t, így:
 +
:<math>=A\cap ((B\cap U)\cup(\overline{B}\cap U))=A\cap (B\cup\overline{B})=A \cap U=A</math>
 +
Tehát ''D'' = ''A''.
 +
 
 +
Vagy Boole-algebrai formalizmusban:
 +
:<math>d=abc+a\overline{b}c+ab\overline{c}+a\overline{bc}=a(bc+\overline{b}c+b\overline{c}+\overline{bc})=a((b+\overline{b})c+(b+\overline{b})\overline{c})=</math>
 +
:<math> =a(1c+1\overline{c})=a(c+\overline{c})=a\cdot 1=a</math>
 +
 
 +
1.2. 
 +
:<math>(A\cap B)\cup C=(A\cup C)\cap (B\cup C)= C\cap (B \cup C)= C</math>
 +
az elnyelési tulajdonság miatt és mert ''A'' &sube; ''C'' pontosan azt jelenti, hogy ''A'' U ''C'' = ''C''.
 +
===Cáfoló példák, cáfoló szituációk===
  
 
Azt, hogy egy kijelentés igaz, azt a matematikában ''bizonyítással'' látjuk be. Például egy "ha ''A'', akkor ''B''" állítás esetén az ''A''-ból levezetjük ''B''-t.  
 
Azt, hogy egy kijelentés igaz, azt a matematikában ''bizonyítással'' látjuk be. Például egy "ha ''A'', akkor ''B''" állítás esetén az ''A''-ból levezetjük ''B''-t.  
119. sor: 140. sor:
 
Azt, hogy egy kijelentés hamis, általában cáfoló ellenpélda vagy cáfoló szituációra való rámutatással. Például egy "ha ''A'', akkor ''B''" állítás cáfolása esetén meg kell mutatunk, hogy a megadott cáfoló szituációban ''A'' ugyan igaz, de ''B'' nem. Ez azt jelenti, hogy ellenpélda esetén is kell bizonyítanunk, éspedig az előző esetben azt, hogy "bár ''A'', de nem ''B''". A metódus tehát a következő: 1) adunk egy példát 2) belátjuk, hogy az adott példa ellenpélda.
 
Azt, hogy egy kijelentés hamis, általában cáfoló ellenpélda vagy cáfoló szituációra való rámutatással. Például egy "ha ''A'', akkor ''B''" állítás cáfolása esetén meg kell mutatunk, hogy a megadott cáfoló szituációban ''A'' ugyan igaz, de ''B'' nem. Ez azt jelenti, hogy ellenpélda esetén is kell bizonyítanunk, éspedig az előző esetben azt, hogy "bár ''A'', de nem ''B''". A metódus tehát a következő: 1) adunk egy példát 2) belátjuk, hogy az adott példa ellenpélda.
  
===Példák===
 
  
'''5. Feladat.''' Legyen ''A'', ''B'' és ''C'' tetszőleges halmaz, továbbá legyen  
+
 
 +
'''6. feladat.''' Legyen ''A'', ''B'' és ''C'' tetszőleges halmaz, továbbá legyen  
 
:<math>K=(A\setminus(B\setminus C))\setminus C</math> és  
 
:<math>K=(A\setminus(B\setminus C))\setminus C</math> és  
 
:<math> L=(A\setminus B)\cup(A\cap C)</math>
 
:<math> L=(A\setminus B)\cup(A\cap C)</math>
138. sor: 159. sor:
 
''Ugyanis,'' ekkor <math>K=\emptyset</math>, <math>L\ne\emptyset</math>.
 
''Ugyanis,'' ekkor <math>K=\emptyset</math>, <math>L\ne\emptyset</math>.
  
 +
===Halmazegyenletek===
 +
 +
'''7. feladat.''' Oldja meg az alábbi halmazegyenleteket, ''X''-re!
 +
## <math> (A-X)\cup B=X\,</math>
 +
##  <math>A-X=X-A\,</math>
 +
 +
''Megoldás.''
 +
 +
1. Legyen a komplementerképzés univerzuma U. Tegyük fel, hogy van megoldás. Eltünik az ''X'' komplementer a bal oldalról, ha mindkét oldalt elmetszük ''X''-szel (ez nem egy ekvivalens átalakítás, csak ritkán, melyenek fennállását külön meg kell gondolnunk):
 +
:<math>\begin{matrix}
 +
(A-X) \cup B & = & X \\
 +
(A\cap \overline{X}) \cup B & = & X \\
 +
((A\cap \overline{X}) \cup B)\cap X & = & X \cap X\\
 +
(A\cap \overline{X}\cap X) \cup (B\cap X) & = & X \\
 +
(A\cap \emptyset) \cup (B\cap X) & = & X \\
 +
B\cap X & = & X
 +
\end{matrix}</math>
 +
ez utóbbi pontosan azt jelenti, hogy ''X'' &sube; ''B''. Emellett a feltétel mellett B-vel a baloldalon "beuniózva":
 +
:<math> [\;X =\; ]\quad\quad(A\cap \overline{X}) \cup B =(A\cup B)\cap (\overline{X}\cup B)\supseteq (A\cup B)\cap (\overline{X}\cup X)=(A\cup B)\cap U =A\cup B</math>
 +
amiből következik, hogy ''B'' &sube; ''X'' és ''A'' &sube; ''X''. Ez azt jelenti, hogy ha van megoldás, akkor az egyértelmű éspedig
 +
:<math>X=B\,</math>
 +
 +
Most vizsgáljuk meg a megoldhatóság feltételét. Azt kaptuk, hogy ha van megoldás, akkor  ''A'' &sube; ''X'' = ''B'', vagyis
 +
:<math>A\subseteq B\,</math>
 +
De ez elégséges feltétele is a megoldhatóságnak, ugyanis ekkor az ''X'' = ''B'' helyettesítés kielégíti az egyenletet:
 +
:<math> \quad\quad(A\cap \overline{B}) \cup B =\emptyset \cup B=B</math>
 +
2.
 +
:<math>A-X=X-A\,</math>
 +
vagyis
 +
:<math>A\cap\overline{X}=X\cap \overline{A}\,</math>
 +
Ha van megoldás és bemetszünk mindkét oldalon ''A''-val (ez nem egy ekvivalens átalakítás, csak ritkán, melyenek fennállását külön meg kell gondolnunk), akkor
 +
:<math>A\cap A\cap\overline{X}=X\cap \overline{A}\cap A\,</math>
 +
:<math>A\cap\overline{X}=\emptyset</math>
 +
azaz ''A'' &sube; ''X'', de az egyenlet ''szimmetrikus'' az ''A'' és az ''X'' felcserélésére, ezért  ''X'' &sube; ''A'' is teljesül, amiből ''X'' = ''A'', ha van megoldás. Márpedig az egyenletet az ''X'' = ''A'' kielégíti.
 +
 +
==Hatványhalmaz==
 +
A ''H'' halmaz hatványhalmaza a ''P''(''H''):={ X | X&sube;H } halmazrendszer.
 +
 +
'''8.''' Igazoljuk, hogy ''P''(A&cap;B) = ''P''(A) &cap; ''P''(B).
 +
 +
'''9.''' Milyen tartalmazás teljesül ''P''(A&cup;B) és ''P''(A) &cup; ''P''(B) között?
 +
 +
Egy véges halmaz elemszáma mindig kisebb, mint a hatványhalmazáé, mert ha a halmaz elemszáma ''n'', akkor a hatványhalmazáé 2<sup>''n''</sup>.
 +
 +
Végtelen halmaz és hatványhalmaza sem lehet azonos számosságú. Ez az alábbi feladatból derül ki.
 +
 +
'''10.''' Egy végtelen sok embert tartamlazó univerzumban a lakók minden lehetséges módon bizottságokat alakítanak. Az összes ember is egy nagy bizottság, de van egyelemű és nulla elemű bizottság is. Egy jegyző úgy dönt számba veszi az összes bizottságot. Minden bizottságot egy emberről fog elnevezni, két különböző bizottságnak nem lehet azonos neve. Sikerrel fog-e járni?
 +
 +
''Útmutatás.'' Vegyük azt a bizottságot, mely azokat az embereket tartalmazza, akik nem tagjai a saját magukról elnevezett bizottságnak. Ezt nevezzük ideiglenesen a szerények bizottságának. Szerény-e a szerények bizottságának névadója?
  
 
==Házi feladatok==
 
==Házi feladatok==

A lap jelenlegi, 2013. szeptember 22., 19:24-kori változata

Tartalomjegyzék

Halmazalgebra

Megjegyzés

Az és és a vagy logikai operátoraival analóg a ∀ és ∃, azaz "minden" és "létezik" szavakra vonatkozó szabályok is. A ∀ az ∧-sel rokonítható, az ∃ a ∨-gyal. Ezek az operátorok nem két mondatot kapcsolnak össze, hanem sok mondatra vonatkoznak egyszerre, abban az értelemben, hogy egy A(x) predikátumból (nyitott mondatból) készítenek egy új mondatot. Például az A(x) := x-nek van emelt szintű matematika érettségije nyitott mondatból a ∃ a (∃x)A(x) := van akinek van emelt szintű matematika érettségije mondatot képezi, a ∀ a (∀x)A(x) := mindenkinek van emelt szintű matematika érettségije mondatot képezi. Az előbbi azt jelenti, hogy a "jelenlévők" közül (az "alaphalmazból") valakinek azaz Pistinek, vagy Bélának, vagy Cilinek ill. valakinek van emelt érettségije matekból -- persze nem kell feltétlenül tudnunk, hogy kinek; az utóbbi pedig, hogy Pistinek is és Bélának is és Cilinek is és Daniellának is és ... mindenkinek megvan az emelt matekja.

(\forall\; \mathrm{ki})\quad\quad\frac{(\forall x)A(x)}{A(t)} tetszőleges t dologra.
(\forall\; \mathrm{be})\quad\quad\frac{A(x)}{(\forall x)A(x)} ahol x-re semmilyen plusz megszorítás nincs.
(\exist\; \mathrm{be})\quad\quad\frac{A(t)}{(\exist x)A(x)} valamilyen t dologra.
(\exist\; \mathrm{ki})\quad\quad\frac{\cfrac{\;A(x)\;}{C},(\exist x)A(x)}{C}

Példa

Az és és a vagy-ra vonatkozó következtetésekre azonnal hozhatunk példát a halmazok témaköréből, ugyanis a halmazműveletek megfeleltethetők a logikai műveleteknek. A halmazoknál van egy kitüntetett nyitott mondat: ha H halmaz, akkor xH azt jelenti, hogy az alaphalmaz egy x-szel jelölt (esetleg közelebbről jobban meg nem határozott) eleme benne van a H halmazban. Legyenek A és B halmazok. Ekkor A és B uniója:

A\cup B=_\mathrm{def}\{x\mid x\in A \vee x\in B\}

azaz azon elemek halmaza, mely az A illetve a B közül legalább az egyikben benne vannak;

A és B metszete:

A\cap B=_\mathrm{def}\{x\mid x\in A \wedge x\in B\}

azaz azon elemek halmaza, mely az A-ban is és a B-ben is benne vannak.

Ha választ várnánk arra a kérdésre, hogy mi az a halmaz, akkor szintén a matematikafilozófia ingoványában találnánk magunkat, ezért intellektuálisan a legtisztességesebb, ha tárgyunk célját (az analízis elsajátítását) érdeklődésünk homlokterébe tartva, ezzel a kérdéssel nem foglalkozunk.

Tudjuk: két halmaz egyenlő, akkor és csak akkor, ha ugyanazok az elemeik. Formulákban:

A=B\quad\Leftrightarrow\quad(\forall x)(\;(x\in A \Rightarrow x\in B)\;\wedge\; (x\in A \Leftarrow x\in B )\;)

A nyilak a következtetés irányát jelzik. Az, hogy a "ha A akkor B" (jelben: A \Rightarrow B) és az "A -ból következik B" (jelben: \frac{A}{B}) ugyanazt jelenti, az egyáltalán nem nyilvánvaló és valójában az úgy nevezett dedukciótétel mondja ki, persze bizonyos itt nem részletezett feltételek mellett.

1. Feladat. Igazoljuk a disztributív szabályt, legalábbis az egyiket, az alábbit:

A\cap(B\cup C)=(A\cap B)\cup(A\cap C)

Bizonyítás. 1) Vegyünk egy tetszőleges x-et. Igazoljuk: "ha x ∈ baloldal, akkor x ∈ jobboldal".

x\in A\cap (B\cup C)
x\in A
x\in B\cup C

Esetszétválasztás jön, mert innentől nem tudjuk, x a B-ben vagy a C'-ben van

x\in B
x\in B és x\in A (igaz állítást bármihez "hozzáéselhetünk": és be)
x\in A\cap B
x\in (A\cap B) vagy x\in (A\cap C) (bármi "hozzávagyolható" egy igaz kijelentéshez: vagy be)
x\in (A\cap B)\cup(A\cap C)
x\in C
x\in C és x\in A (igaz állítást bármihez "hozzáéselhetünk": és be)
x\in A\cap C
x\in (A\cap C) vagy x\in (A\cap B) (bármi "hozzávagyolható" egy igaz kijelentéshez: vagy be)
x\in (A\cap B)\cup(A\cap C)
x\in (A\cap B)\cup(A\cap C) azaz mindkét esetben kijött a jobboldal.

2) Visszafelé ugyanígy, csak felfelé.

Negáció, indirekt bizonyítás

A tagadás (negáció) kiküszöbölési szabálya az úgy nevezett kettős tagadás törlésének szabálya:

(\neg\; \mathrm{ki})\quad\quad\frac{\neg\neg A}{A}

A bevezetési szabálya pedig az úgy nevezett redukció ad abszurdum.

(\neg\; \mathrm{be})\quad\quad\frac{\cfrac{\;A\;}{C},\;\cfrac{\;A\;}{\neg C}}{\neg A}

Ezeknek a segítségével olyan fontos tételeket is levezethetünk, mint a De-Morgan azonosságok:

\neg(A\vee B)\equiv \neg A\wedge \neg B
\neg(A\wedge B)\equiv \neg A\vee \neg B

A fentiekben a \equiv, hogy a két oldalon lévő kifejezés kölcsönösek következik egymásból.

Példák

Ami még hiányzik a logikai operációk és a halmazműveletek megfeleltetéséből, az negáció halmazműveletekkel történő átfogalmazása, mely nem titok, a komplementerképzés lesz. Sajnos komoly logikai problémát okozna, ha komplementeren egy A halmaz esetén azon elemeket értenénk, melyek nem az A-ban vannak. Ekkor ugyanis egy kisebb halmaz, mint mondjuk az {1,2,3} komplementere a világ összes ezektől különböző dolgából állna. Ezzel azonban világos, hogy megint a matematikafilozófia ingoványos talajára tévednénk, így ezt másként tesszük.

Ha H halmaz, akkor az A halmaznak a H-ra vonatkozó komplementere az

\overline{A}|_H=_\mathrm{def}\{x\in H\mid x\notin A\}

Ha a fenti H halmazt alkalmasan nagynak választjuk, akkor elkerüljük a logikai problémát.

Ezzel a De-Morgan-azonosságok halmazokkal megfogalmazott változata a következő alakban írható:

\overline{A\cup B}=\overline{A}\cap\overline{B}
\overline{A\cap B}=\overline{A}\cup\overline{B}

A fenti egyenlőségek középiskolából ismert relációval is kifejezhetők. Azt mondjuk, hogy A része B-nek, ha minden olyan esetben, amikor egy elem eleme A-nak, akkor B-nek is eleme, jelben:

A\subseteq B

Azaz az, hogy A = B az ugyanaz, mint hogy A\subseteq B és A\supseteq B is teljesül.


2. Feladat. Példaként nézzük csak a

\overline{A\cup B}\supseteq\overline{A}\cap\overline{B}

esetet.

Megoldás. Vegyünk egy elemet a jobboldalból és igazoljuk, hogy benne van a baloldalban. Tudjuk a metszet definíciója miatt, hogy ekkor

x\notin A
x\notin B
x\in A \vee B (indirekt feltevés), ezek után esetszétválasztáshoz kell folyamodnunk. Mindkét esetben ellentmondásra jutunk:
ha x\in A, akkor a legfelső
ha x\in B, akkor a legfelső alatti egyenlőség miatt jutunk ellentmondásra, így a
x\notin A \vee B konklúzióra jutottunk.

Egy másik jellegzetes példa a részhalmaz relációval kapcsolatos. Előtte azonban fel kell idéznünk a kvantrokra vonatkozó De-Morgan-azonosságot. A "létezik" szót (mely a "minden" duálisa) ∃-tel jelöljük:

\neg(\forall x)A(x)\equiv(\exists x)\neg A(x)
\neg(\exists x)A(x)\equiv(\forall x)\neg A(x)

A kijelentések világosak: ha nem minden dolog A, akkor van olyan dolog, ami nem A. Ha nem létezik A, akkor minden dolog nem A tulajdonságú.

3. Feladat. Igazoljuk, hogy az üres halmaz minden halmaznak része.

Megoldás. Legyen A tetszőleges halmaz. Indirekten tegyük fel, hogy

\emptyset \not\subseteq A

Az \emptyset \subseteq A formulákban így néz ki:

(\forall x)(x\in \emptyset \Rightarrow x\in A)

Egy ilyen tagadása az, hogy a kvantort átírjuk a duálisára és a tulajdonságot tagadjuk:

(\exists x)(x\in \emptyset \wedge x\notin A)

Ekkor azonban azt kaptuk, hogy létezik az üres halmaznak eleme, ami ellentmondás.

Boole-algebrai átalakítások

Világos, hogy az unióra és a metszetre a definíciójuk miatt ugyanazok az azonosságok vonatkoznak, mint a "vagy"-ra és az "és"-re. Ezeket a szabályokat Boole-algebrai azonosságoknak nevezzük. Ahhoz, hogy teljes legyen a kép még egy fontos halmazműveletet fel kell elevenítenünk: Legyenek A és B halmazok. Ekkor A mínusz B vagy A különbség B:

A\setminus B=_\mathrm{def}\{x\mid x\in A \wedge x\notin B\}

azaz azon elemek halmaza, melyek az A-nak elemei, de a B-nek nem.

Nagyon hasznos azonosság, hogy a különbség átírható komplementer és metszet segítségével:

A\setminus B=A\cap\overline{B}

ahol a komplementerképzés egy olyan halmazra vonatkoztatjuk, melyben minden szóban forgó halmaz részhalmazként benne van, például jelen esetben H = A U B alkalmas ilyen halmaz .

4. Feladat. Igazoljuk, hogy tetszőleges A, B és C halmazokra

A\setminus(B\setminus C)=(A\setminus B)\cup (A\cap C)

Megoldás. Írjuk fel a baloldalt és alakítsuk addig, míg ki nem jön a jobboldal:

A\setminus(B\setminus C)=A\cap \overline{B \cap \overline{C}}=A\cap (\overline{B}\cup \overline{\overline{C}})=(A\cap \overline{B}) \cup (A\cap C)=
=(A\setminus B)\cup (A\cap C)


5. feladat. Egyszerűsítse az alábbi kifejezéseket!

    1. (A\cap B\cap C)\cup (A\cap B\cap \overline{C})\cup(A\cap \overline{B}\cap C)\cup(A\cap \overline{B}\cap \overline{C})=?
    2. (A\cap B)\cup C=?, ha A\subseteq C.

Mo. 1.1. Legyen D a feladatban szereplő halmaz és legyen U = A U B U C a komplementerképzés alaphalmaza! Emeljünk ki A-t!

D=A\cap ((B\cap C)\cup (B\cap \overline{C})\cup(\overline{B}\cap C)\cup(\overline{B}\cap \overline{C}))=

A második tényező első két tagjából kiemelhetünk B-t a második két tagjából B komplementert:

=A\cap ((B\cap (C\cup \overline{C}))\cup(\overline{B}\cap (C\cup\overline{C})))=

ekkor a halmaz és komplementere kiadja U-t, így:

=A\cap ((B\cap U)\cup(\overline{B}\cap U))=A\cap (B\cup\overline{B})=A \cap U=A

Tehát D = A.

Vagy Boole-algebrai formalizmusban:

d=abc+a\overline{b}c+ab\overline{c}+a\overline{bc}=a(bc+\overline{b}c+b\overline{c}+\overline{bc})=a((b+\overline{b})c+(b+\overline{b})\overline{c})=
 =a(1c+1\overline{c})=a(c+\overline{c})=a\cdot 1=a

1.2.

(A\cap B)\cup C=(A\cup C)\cap (B\cup C)= C\cap (B \cup C)= C

az elnyelési tulajdonság miatt és mert AC pontosan azt jelenti, hogy A U C = C.

Cáfoló példák, cáfoló szituációk

Azt, hogy egy kijelentés igaz, azt a matematikában bizonyítással látjuk be. Például egy "ha A, akkor B" állítás esetén az A-ból levezetjük B-t.

Azt, hogy egy kijelentés hamis, általában cáfoló ellenpélda vagy cáfoló szituációra való rámutatással. Például egy "ha A, akkor B" állítás cáfolása esetén meg kell mutatunk, hogy a megadott cáfoló szituációban A ugyan igaz, de B nem. Ez azt jelenti, hogy ellenpélda esetén is kell bizonyítanunk, éspedig az előző esetben azt, hogy "bár A, de nem B". A metódus tehát a következő: 1) adunk egy példát 2) belátjuk, hogy az adott példa ellenpélda.


6. feladat. Legyen A, B és C tetszőleges halmaz, továbbá legyen

K=(A\setminus(B\setminus C))\setminus C és
 L=(A\setminus B)\cup(A\cap C)

Vizsgáljuk meg, hogy melyik tartalmazás áll fenn!

  1. K\subseteq L
  2.  K\supseteq L

Megoldás. Az A U B-re vonatkozó komplementerképzésre áttérve:

K=A\cap \overline{B\cap\overline{C}}\cap \overline{C}=A\cap (\overline{B}\cup C)\cap\overline{C}=((A\cap \overline{B})\cup (A\cap C))\cap\overline{C}=
=((A\setminus B)\cup (A\cap C))\cap\overline{C}=L\cap\overline{C}

Tehát K\subseteq L biztosan igaz, azaz (1) igaz.

Ellenben (2) hamis, ellenpélda:

A=C=\{1\}\ne\emptyset, B=\emptyset

Ugyanis, ekkor K=\emptyset, L\ne\emptyset.

Halmazegyenletek

7. feladat. Oldja meg az alábbi halmazegyenleteket, X-re!

    1.  (A-X)\cup B=X\,
    2. A-X=X-A\,

Megoldás.

1. Legyen a komplementerképzés univerzuma U. Tegyük fel, hogy van megoldás. Eltünik az X komplementer a bal oldalról, ha mindkét oldalt elmetszük X-szel (ez nem egy ekvivalens átalakítás, csak ritkán, melyenek fennállását külön meg kell gondolnunk):

\begin{matrix}
(A-X) \cup B & = & X \\
(A\cap \overline{X}) \cup B & = & X \\
((A\cap \overline{X}) \cup B)\cap X & = & X \cap X\\
(A\cap \overline{X}\cap X) \cup (B\cap X) & = & X \\
(A\cap \emptyset) \cup (B\cap X) & = & X \\
B\cap X & = & X 
\end{matrix}

ez utóbbi pontosan azt jelenti, hogy XB. Emellett a feltétel mellett B-vel a baloldalon "beuniózva":

 [\;X =\; ]\quad\quad(A\cap \overline{X}) \cup B =(A\cup B)\cap (\overline{X}\cup B)\supseteq (A\cup B)\cap (\overline{X}\cup X)=(A\cup B)\cap U =A\cup B

amiből következik, hogy BX és AX. Ez azt jelenti, hogy ha van megoldás, akkor az egyértelmű éspedig

X=B\,

Most vizsgáljuk meg a megoldhatóság feltételét. Azt kaptuk, hogy ha van megoldás, akkor AX = B, vagyis

A\subseteq B\,

De ez elégséges feltétele is a megoldhatóságnak, ugyanis ekkor az X = B helyettesítés kielégíti az egyenletet:

 \quad\quad(A\cap \overline{B}) \cup B =\emptyset \cup B=B

2.

A-X=X-A\,

vagyis

A\cap\overline{X}=X\cap \overline{A}\,

Ha van megoldás és bemetszünk mindkét oldalon A-val (ez nem egy ekvivalens átalakítás, csak ritkán, melyenek fennállását külön meg kell gondolnunk), akkor

A\cap A\cap\overline{X}=X\cap \overline{A}\cap A\,
A\cap\overline{X}=\emptyset

azaz AX, de az egyenlet szimmetrikus az A és az X felcserélésére, ezért XA is teljesül, amiből X = A, ha van megoldás. Márpedig az egyenletet az X = A kielégíti.

Hatványhalmaz

A H halmaz hatványhalmaza a P(H):={ X | X⊆H } halmazrendszer.

8. Igazoljuk, hogy P(A∩B) = P(A) ∩ P(B).

9. Milyen tartalmazás teljesül P(A∪B) és P(A) ∪ P(B) között?

Egy véges halmaz elemszáma mindig kisebb, mint a hatványhalmazáé, mert ha a halmaz elemszáma n, akkor a hatványhalmazáé 2n.

Végtelen halmaz és hatványhalmaza sem lehet azonos számosságú. Ez az alábbi feladatból derül ki.

10. Egy végtelen sok embert tartamlazó univerzumban a lakók minden lehetséges módon bizottságokat alakítanak. Az összes ember is egy nagy bizottság, de van egyelemű és nulla elemű bizottság is. Egy jegyző úgy dönt számba veszi az összes bizottságot. Minden bizottságot egy emberről fog elnevezni, két különböző bizottságnak nem lehet azonos neve. Sikerrel fog-e járni?

Útmutatás. Vegyük azt a bizottságot, mely azokat az embereket tartalmazza, akik nem tagjai a saját magukról elnevezett bizottságnak. Ezt nevezzük ideiglenesen a szerények bizottságának. Szerény-e a szerények bizottságának névadója?

Házi feladatok

  1. K\(K\L) = L\(L\K)
  2. (K ∩ L) \ ( K\M ) = K ∩ L ∩ M
  3. (K\L)\M = (K\M)\(L\M)
Személyes eszközök