Matematika A1a 2008/1. gyakorlat

A MathWikiből
(Változatok közti eltérés)
(Direkt következtetések)
(Boole-algebrai átalakítások)
110. sor: 110. sor:
  
 
==Boole-algebrai átalakítások==
 
==Boole-algebrai átalakítások==
Világos, hogy az unió is metszet definíciója miatt ugyanazok az azonosságok vonatkoznak rájuk, mint az "vagy"-ra és az "és"-re. A rájuk vonatkozó azonosságokat Boole-algebrai azonosságoknak nevezzük. Ahhoz, hogy teljes legyen a kép még egy fontos halmazműveletet kell felelevenítenünk:
+
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'' minusz ''B'' vagy ''A'' különbség ''B'':
 
Legyenek ''A'' és ''B'' halmazok. Ekkor ''A'' minusz ''B'' vagy ''A'' különbség ''B'':
 
:<math>A\setminus B=_\mathrm{def}\{x\mid x\in A \wedge x\notin B\}</math>
 
:<math>A\setminus B=_\mathrm{def}\{x\mid x\in A \wedge x\notin B\}</math>
 
azaz azon elemek halmaza, melyek az ''A''-nak elemei, de a ''B''-nek nem.
 
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ó komplementerrel:
+
Nagyon hasznos azonosság, hogy a különbség átírható komplementer és metszet segítségével:
 
:<math>A\setminus B=A\cap\overline{B}</math>
 
:<math>A\setminus B=A\cap\overline{B}</math>
ahol a kopmlementerkézés egy olyan halmazra vonatkozik, melyben minden szóbanforgó halmaz részhalmazként benne van, például jelem esetben ''H'' = ''A'' U ''B'' alkalmas.
+
ahol a komplementerkézés egy olyan halmazra vonatkoztatjuk, melyben minden szóbanforgó 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
 
'''4. Feladat.''' Igazoljuk, hogy tetszőleges ''A'', ''B'' és ''C'' halmazokra

A lap 2009. február 11., 22:17-kori változata

<Matematika A1a 2008

Ha A1, A2, ..., An, B mondatok, akkor azt mondjuk, hogy az

\frac{A_1,\;A_2,\;...\;,\;A_n}{B}

szimbólummal jelölt következtetés helyes, ha minden olyan esetben, amikor az A1, A2, ..., An mondatok (az úgy nevezett premisszák vagy feltételek) mindegyike igaz, akkor a B mondat, azaz a konkúzió (következmény) is igaz.

A helyes következtetések listája elég nagy, ám vannak bizonyos tekintetben alapvetőnek tekinthető kövekeztetések, melyeket könnyen lehet kategorizálni a bevezetési és kiküszöbölési szabályok szerint.

Tartalomjegyzék

Direkt következtetések

A legegyszerűbb eset az és (jelben \wedge) mondatoperátorral összekötött összetett mondatokra vonatkozó bevezetési és kiküszöbölési szabály. Egy mondatoperátor kiküszöbölési szabályának jelentése lényegében abban áll, hogy megadja, mire következtethetünk akkor, ha ismertnek tételezzük fel annak igazságát, jelen esetben például az A és B összetett mondat igaz voltát. Eszerint:

(\wedge\; \mathrm{ki})\quad\quad\frac{A\wedge B}{A},\quad\quad\frac{A\wedge B}{B}

Azaz, ha tudjuk, hogy A és B igaz, akkor jogos kijelentenünk, akár A, akár B igazságának fennállását. A bevezetési szabály azt adja meg, hogy miből következtethetünk az adott összetételre. Világos, hogy a helyes következtetés fenti értlemezése szerint minden olyan esetben amikor az {A, B} premisszapár minden tagja igaz, levonhatjuk az A és B következtetést:

(\wedge\; \mathrm{be})\quad\quad\frac{A,B}{A\wedge B}

A vagy (jelben: \vee) bevezetési szabálya szitén nyilvánvaló:

(\vee\; \mathrm{be})\quad\quad\frac{A}{A\vee B},\quad\quad\frac{B}{A\vee B}

Ezzel szemben a kiküszöbölési szabályának tárgyalásával máris belefutottunk a logikafilozófia ingoványába, ezt persze nem tárgyaljuk, csak magát a köetkeztetési szabályt. A vagy kiküszöbölési szabályát az esetszétválasztás szabályának nevezzük:

(\vee\; \mathrm{ki})\quad\quad\frac{\cfrac{\;A\;}{C},\;\cfrac{\;B\;}{C},\;A\vee B}{C} az esetszétválasztás szabálya

Azaz ha A-ból következik a C és a B-ből is következik a C, továbbá az A és a B közül legalább az egyik igaz (ez a klasszikus vagy: nem feltétlenül tudjuk, melyik igaz, csak azt, hogy az egyik), akkor a C biztos igaz.

Ezekkel analógak a ∀ és ∃, azaz "minden" és "létezik" szavakra vonatkozó szabályok is. A ∀ az ∧-sel rokonítható, az ∃ a ∨-gyal.

Példa

A fenti következtetésekre azonnal hozhatunk egy példát a halmazok témaköréből. A halmazműveletek megfeleltethetők logikai műveleteknek. A fentieknek megfelelők. 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 nem ismert jel esetleg itt a ∀, melyre a minden szó rövidítéseként gondolunk és a nyilak, amik 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ább is 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 felefelé.

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űveltek 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 ezt úgy tenénk, hogy egy A halmaz esetén az A komplementerébe azon elemek tartoznak, melyen 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ófi 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ó komplementre az

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

A fenti H halmazt alkalmasan nagynak gondoljuk és ezzel elkerüljük a logkai 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éldké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 baloldalba. 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 vontkozó 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 minusz 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ézés egy olyan halmazra vonatkoztatjuk, melyben minden szóbanforgó 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)

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

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.


6. Feladat. Legyen (an) és (bn) két tetszőleges sorozat. Melyik állítás következik a másikból és melyik nem?

  1. (an) korlátos vagy (bn) korlátos
  2. (an) korlátos és (bn) korlátos
  3. (an\cdotbn) korlátos

Megoldás.

1 --> 2 pusztán logikai okokból nem teljesül.

Ellenpélda: an\equiv1 és (bn)=(n).

Ugyanis, bár 1 korlátos, így legalább az egyik korlátos, de mindkettő nem.


2 --> 1 viszont logikai okokból igaz.

Bizonyítás: ha mindekettő korlátos, akkor világos, hogy legalább az egyik korlátos.


1 --> 3 valószínűleg nem igaz. Valóban:

ellenpélda az 1-->2-beli.

Ugyanis, bár legalább az egyik korlátos, de a szorzat (1\cdotn)=(n) nem az.

2 --> 3 igaz.

Bizonyítás. |an\cdotbn|=|an|\cdot|bn| < K\cdotL, ahol K az egyik, L, a másik sorozat abszolútértékét felül becslő szám.

3 --> 2 nem igaz

Ellenpélda. (n) és (1/n)

Ugyanis. bár a szorzat korlátos, az egyik sorozat nem az.

3 --> 1 becsapós.

Ellenpélda. an = n, ha n páros és an =1/n, ha n páratlan. bn a "fordítottja", azaz párosakra 1/n és páratlanokra n.

Ugyanis, an\cdotbn = 1 és korlátos, de egyik sem korlátos önmagában.

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