Matematika A1a 2008/1. gyakorlat

A MathWikiből
(Változatok közti eltérés)
(Negáció)
50. sor: 50. sor:
 
2) Visszafelé ugyanígy, csak felefelé.
 
2) Visszafelé ugyanígy, csak felefelé.
 
==Negáció, indirekt bizonyítás==
 
==Negáció, indirekt bizonyítás==
A tagadás kiküszöbölési szabálya az úgy nevezett ''kettős tagadás törlésének szabálya'':
+
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'':
 
:<math>(\neg\; \mathrm{ki})\quad\quad\frac{\neg\neg A}{A}</math>  
 
:<math>(\neg\; \mathrm{ki})\quad\quad\frac{\neg\neg A}{A}</math>  
 
A bevezetési szabálya pedig az úgy nevezett ''redukció ad abszurdum''.
 
A bevezetési szabálya pedig az úgy nevezett ''redukció ad abszurdum''.
59. sor: 59. sor:
 
A fentiekben a <math>\equiv</math>, hogy a két oldalon lévő kifejezés kölcsönösek következik egymásból.
 
A fentiekben a <math>\equiv</math>, hogy a két oldalon lévő kifejezés kölcsönösek következik egymásból.
  
Példként csak nézzük a  
+
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.
:<math>\frac{\neg A\wedge \neg B}{\neg(A\vee B)}</math>
+
 
 +
Ha ''H'' halmaz, akkor az ''A'' halmaznak a ''H''-ra vonatkozó komplementre az
 +
:<math>\overline{A}|_H=_\mathrm{def}\{x\in H\mid x\notin A\}</math>
 +
 
 +
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ó:
 +
:<math>\overline{A\cup B}=\overline{A}\cap\overline{B}</math>
 +
:<math>\overline{A\cap B}=\overline{A}\cup\overline{B}</math>
 +
 
 +
 
 +
Példként nézzük csak a
 +
:<math>\overline{A\cup B}\supseteq\overline{A}\cap\overline{B}</math>  
 
esetet.
 
esetet.
  
72. sor: 84. sor:
 
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.
  
Ennek a segítségével lehet definiálni egy ''H'' halmazra vonatkozó komplementert:
+
Nagyon hasznos azonosság, hogy a különbség átírható komplementerrel:
:<math>\overline{B}|_H=_\mathrm{def}H\setminus B</math>
+
és ami még ennél is hasznosabb, a különbség átírható komplementerre:
+
 
:<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 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.
 
Ezzel a De-Morgan azonosságok halmazokkal megfogalmazott változata a következő alakban írható:
 
:<math>\overline{A\cup B}=\overline{A}\cap\overline{B}</math>
 
:<math>\overline{A\cap B}=\overline{A}\cup\overline{B}</math>
 
  
 
'''Igazoljuk,''' hogy tetszőleges ''A'', ''B'' és ''C'' halmazokra
 
'''Igazoljuk,''' hogy tetszőleges ''A'', ''B'' és ''C'' halmazokra

A lap 2008. szeptember 4., 12:31-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.

Tudjuk:

\neg A
\neg B
A \vee B (indirekt feltevés)

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

Személyes eszközök