Matematika A1a 2008/1. gyakorlat

A MathWikiből
(Változatok közti eltérés)
(Negáció, indirekt bizonyítás)
(Cáfolatok)
100. sor: 100. sor:
  
 
==Cáfolatok==
 
==Cáfolatok==
 +
 +
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''".
 +
 +
'''Feladat.''' Vizsgáljuk meg, hogy ha ''A'', ''B'' és ''C'' tetszőleges halmaz, akkor melyik tartalmazás áll fenn!
 +
 +
 +
'''Feladat.''' Legyen (''a''<sub>n</sub>) és (''b''<sub>n</sub>) két tetszőleges sorozat. Melyik állítás következik a másikból és melyik nem?
 +
 +
# (''a''<sub>n</sub>) korlátos vagy (''b''<sub>n</sub>) korlátos
 +
# (''a''<sub>n</sub>) korlátos és (''b''<sub>n</sub>) korlátos
 +
# (''a''<sub>n</sub><math>\cdot</math>''b''<sub>n</sub>) korlátos

A lap 2008. szeptember 4., 13:21-kori változata

Tartalomjegyzék

Következtetések

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.

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ó:

(\wedge\; \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.

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.)

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.

Ami még hiányzik a logikai operációk és a halmaz mű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}


Példként nézzük csak a

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

esetet.

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.

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: 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ó komplementerrel:

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

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.

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

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

í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áfolatok

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".

Feladat. Vizsgáljuk meg, hogy ha A, B és C tetszőleges halmaz, akkor melyik tartalmazás áll fenn!


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
Személyes eszközök