Matematika közlek A1a 2013/2. gyakorlat
Mozo (vitalap | szerkesztései) |
Mozo (vitalap | szerkesztései) (→Példák) |
||
138. sor: | 138. sor: | ||
''Ugyanis,'' ekkor <math>K=\emptyset</math>, <math>L\ne\emptyset</math>. | ''Ugyanis,'' ekkor <math>K=\emptyset</math>, <math>L\ne\emptyset</math>. | ||
+ | ===Halmazegyenletek=== | ||
+ | |||
+ | # '''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>. | ||
+ | # '''Oldja meg az alábbi halmazegyenleteket, ''X''-re!''' | ||
+ | ## <math> (A-X)\cup B=X\,</math> | ||
+ | ## <math>A-X=X-A\,</math> | ||
+ | |||
+ | ''Megoldás.'' | ||
+ | |||
+ | 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'' ⊆ ''C'' pontosan azt jelenti, hogy ''A'' U ''C'' = ''C''. | ||
+ | |||
+ | 2.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: | ||
+ | :<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'' ⊆ ''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'' ⊆ ''X'' és ''A'' ⊆ ''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'' ⊆ ''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.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, akkor | ||
+ | :<math>A\cap A\cap\overline{X}=X\cap \overline{A}\cap A\,</math> | ||
+ | :<math>A\cap\overline{X}=\emptyset</math> | ||
+ | azaz ''A'' ⊆ ''X'', de az egyenlet ''szimmetrikus'' az ''A'' és az ''X'' felcserélésére, ezért ''X'' ⊆ ''A'' is teljesül, amiből ''X'' = ''A'', ha van megoldás. Márpedig az egyenletet az ''X'' = ''A'' kielégíti. | ||
==Házi feladatok== | ==Házi feladatok== |
A lap 2013. szeptember 15., 11:59-kori változata
Tartalomjegyzék |
Halmatalgebra
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.
- tetszőleges t dologra.
- ahol x-re semmilyen plusz megszorítás nincs.
- valamilyen t dologra.
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 x ∈ H 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:
azaz azon elemek halmaza, mely az A illetve a B közül legalább az egyikben benne vannak;
A és B metszete:
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 nyilak a következtetés irányát jelzik. Az, hogy a "ha A akkor B" (jelben: A B) és az "A -ból következik B" (jelben: ) 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:
Bizonyítás. 1) Vegyünk egy tetszőleges x-et. Igazoljuk: "ha x ∈ baloldal, akkor x ∈ jobboldal".
Esetszétválasztás jön, mert innentől nem tudjuk, x a B-ben vagy a C'-ben van
-
- és (igaz állítást bármihez "hozzáéselhetünk": és be)
- vagy (bármi "hozzávagyolható" egy igaz kijelentéshez: vagy be)
-
- és (igaz állítást bármihez "hozzáéselhetünk": és be)
- vagy (bármi "hozzávagyolható" egy igaz kijelentéshez: vagy be)
- 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:
A bevezetési szabálya pedig az úgy nevezett redukció ad abszurdum.
Ezeknek a segítségével olyan fontos tételeket is levezethetünk, mint a De-Morgan azonosságok:
A fentiekben a , 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
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ó:
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:
Azaz az, hogy A = B az ugyanaz, mint hogy és is teljesül.
2. Feladat. Példaként nézzük csak a
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
-
- (indirekt feltevés), ezek után esetszétválasztáshoz kell folyamodnunk. Mindkét esetben ellentmondásra jutunk:
- ha , akkor a legfelső
- ha , akkor a legfelső alatti egyenlőség miatt jutunk ellentmondásra, így a
- (indirekt feltevés), ezek után esetszétválasztáshoz kell folyamodnunk. Mindkét esetben ellentmondásra jutunk:
- 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:
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
Az formulákban így néz ki:
Egy ilyen tagadása az, hogy a kvantort átírjuk a duálisára és a tulajdonságot tagadjuk:
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:
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:
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
Megoldás. Írjuk fel a baloldalt és alakítsuk addig, míg ki nem jön a jobboldal:
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.
Példák
5. Feladat. Legyen A, B és C tetszőleges halmaz, továbbá legyen
- és
Vizsgáljuk meg, hogy melyik tartalmazás áll fenn!
Megoldás. Az A U B-re vonatkozó komplementerképzésre áttérve:
Tehát biztosan igaz, azaz (1) igaz.
Ellenben (2) hamis, ellenpélda:
- ,
Ugyanis, ekkor , .
Halmazegyenletek
- Egyszerűsítse az alábbi kifejezéseket!
- , ha .
- Oldja meg az alábbi halmazegyenleteket, X-re!
Megoldás.
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!
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:
ekkor a halmaz és komplementere kiadja U-t, így:
Tehát D = A.
Vagy Boole-algebrai formalizmusban:
1.2.
az elnyelési tulajdonság miatt és mert A ⊆ C pontosan azt jelenti, hogy A U C = C.
2.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 utóbbi pontosan azt jelenti, hogy X ⊆ B. Emellett a feltétel mellett B-vel a baloldalon "beuniózva":
amiből következik, hogy B ⊆ X és A ⊆ X. Ez azt jelenti, hogy ha van megoldás, akkor az egyértelmű éspedig
Most vizsgáljuk meg a megoldhatóság feltételét. Azt kaptuk, hogy ha van megoldás, akkor A ⊆ X = B, vagyis
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:
2.2.
vagyis
Ha van megoldás és bemetszünk mindkét oldalon A-val, akkor
azaz A ⊆ X, de az egyenlet szimmetrikus az A és az X felcserélésére, ezért X ⊆ A is teljesül, amiből X = A, ha van megoldás. Márpedig az egyenletet az X = A kielégíti.
Házi feladatok
- K\(K\L) = L\(L\K)
- (K ∩ L) \ ( K\M ) = K ∩ L ∩ M
- (K\L)\M = (K\M)\(L\M)