Matematika A1a 2008/1. gyakorlat

A MathWikiből
(Változatok közti eltérés)
(Direkt következtetések)
(Példák)
 
(egy szerkesztő 11 közbeeső változata nincs mutatva)
21. sor: 21. sor:
  
 
===Megjegyzés===
 
===Megjegyzés===
Ezekkel 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 vagy Pistinek, vagy Bélának, vagy Cilinek van emelt érettségije matekból -- persze '''nem kell feltétlenül tudnunk''', hogy kinek; az utóbbi pedig, hogy Pistinek is, Bélának is, Cilinek is, Daniellának is,... mindenkinek megvan az emelt matekja.   
+
Ezekkel 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.   
 +
:<math>(\forall\; \mathrm{ki})\quad\quad\frac{(\forall x)A(x)}{A(t)}</math> tetszőleges ''t'' dologra.
 +
:<math>(\forall\; \mathrm{be})\quad\quad\frac{A(x)}{(\forall x)A(x)}</math> ahol ''x''-re semmilyen plusz megszorítás nincs.
 +
:<math>(\exist\; \mathrm{be})\quad\quad\frac{A(t)}{(\exist x)A(x)}</math> valamilyen ''t'' dologra.
 +
:<math>(\exist\; \mathrm{ki})\quad\quad\frac{\cfrac{\;A(x)\;}{C},(\exist x)A(x)}{C}</math>
 +
 
 
===Példa===
 
===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 fenti 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'' &isin; ''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:
 
:<math>A\cup B=_\mathrm{def}\{x\mid x\in A \vee x\in B\}</math>
 
:<math>A\cup B=_\mathrm{def}\{x\mid x\in A \vee x\in B\}</math>
 
azaz azon elemek halmaza, mely az ''A'' illetve a ''B'' közül ''legalább az egyikben benne vannak'';
 
azaz azon elemek halmaza, mely az ''A'' illetve a ''B'' közül ''legalább az egyikben benne vannak'';
35. sor: 40. sor:
 
Tudjuk: két halmaz egyenlő, akkor és csak akkor, ha ugyanazok az elemeik. Formulákban:
 
Tudjuk: két halmaz egyenlő, akkor és csak akkor, ha ugyanazok az elemeik. Formulákban:
 
:<math>A=B\quad\Leftrightarrow\quad(\forall x)(\;(x\in A \Rightarrow x\in B)\;\wedge\; (x\in A \Leftarrow x\in B )\;)</math>
 
:<math>A=B\quad\Leftrightarrow\quad(\forall x)(\;(x\in A \Rightarrow x\in B)\;\wedge\; (x\in A \Leftarrow x\in B )\;)</math>
A nem ismert jel esetleg itt a &forall;, 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 <math>\Rightarrow</math> B'') és az "''A -ból következik B''" (jelben: <math>\frac{A}{B}</math>) 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.)
+
A nyilak a következtetés irányát jelzik. Az, hogy a "''ha A akkor B''" (jelben: ''A <math>\Rightarrow</math> B'') és az "''A -ból következik B''" (jelben: <math>\frac{A}{B}</math>) 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:  
+
'''1. Feladat. ''' Igazoljuk a disztributív szabályt, legalábbis az egyiket, az alábbit:  
 
:<math>A\cap(B\cup C)=(A\cap B)\cup(A\cap C)</math>
 
:<math>A\cap(B\cup C)=(A\cap B)\cup(A\cap C)</math>
 
''Bizonyítás.'' 1) Vegyünk egy tetszőleges ''x''-et. Igazoljuk: "ha ''x'' &isin; baloldal, akkor ''x'' &isin; jobboldal".  
 
''Bizonyítás.'' 1) Vegyünk egy tetszőleges ''x''-et. Igazoljuk: "ha ''x'' &isin; baloldal, akkor ''x'' &isin; jobboldal".  
55. sor: 60. sor:
 
::::<math>x\in (A\cap B)\cup(A\cap C)</math>
 
::::<math>x\in (A\cap B)\cup(A\cap C)</math>
 
:::<math>x\in (A\cap B)\cup(A\cap C)</math> azaz mindkét esetben kijött a jobboldal.
 
:::<math>x\in (A\cap B)\cup(A\cap C)</math> azaz mindkét esetben kijött a jobboldal.
2) Visszafelé ugyanígy, csak felefelé.
+
2) Visszafelé ugyanígy, csak felfelé.
  
 
==Negáció, indirekt bizonyítás==
 
==Negáció, indirekt bizonyítás==
68. sor: 73. sor:
  
 
===Példák===
 
===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.
+
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ó komplementre az
+
Ha ''H'' halmaz, akkor az ''A'' halmaznak a ''H''-ra vonatkozó komplementere az
 
:<math>\overline{A}|_H=_\mathrm{def}\{x\in H\mid x\notin A\}</math>
 
:<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.
+
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ó:
 
Ezzel a De-Morgan-azonosságok halmazokkal megfogalmazott változata a következő alakban írható:
84. sor: 89. sor:
  
  
'''2. Feladat.''' Példként nézzük csak a  
+
'''2. Feladat.''' Példaként nézzük csak a  
 
:<math>\overline{A\cup B}\supseteq\overline{A}\cap\overline{B}</math>  
 
:<math>\overline{A\cup B}\supseteq\overline{A}\cap\overline{B}</math>  
 
esetet.
 
esetet.
96. sor: 101. sor:
 
:<math>x\notin A \vee B</math> konklúzióra jutottunk.
 
:<math>x\notin A \vee B</math> 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) &exist;-tel jelöljük:
+
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) &exist;-tel jelöljük:
 
:<math>\neg(\forall x)A(x)\equiv(\exists x)\neg A(x)</math>
 
:<math>\neg(\forall x)A(x)\equiv(\exists x)\neg A(x)</math>
 
:<math>\neg(\exists x)A(x)\equiv(\forall x)\neg A(x)</math>
 
:<math>\neg(\exists x)A(x)\equiv(\forall x)\neg A(x)</math>
113. sor: 118. sor:
 
==Boole-algebrai átalakítások==
 
==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:
 
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'' mínusz ''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.
119. sor: 124. sor:
 
Nagyon hasznos azonosság, hogy a különbség átírható komplementer és metszet segítségével:
 
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 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 .
+
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
 
'''4. Feladat.''' Igazoljuk, hogy tetszőleges ''A'', ''B'' és ''C'' halmazokra
153. sor: 158. sor:
 
''Ugyanis,'' ekkor <math>K=\emptyset</math>, <math>L\ne\emptyset</math>.
 
''Ugyanis,'' ekkor <math>K=\emptyset</math>, <math>L\ne\emptyset</math>.
  
 +
<!--
  
 
'''6. 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?  
 
'''6. 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?  
162. sor: 168. sor:
 
''Megoldás.''  
 
''Megoldás.''  
  
1 --> 2 pusztán logikai okokból nem teljesül.
+
1 -- > 2 pusztán logikai okokból nem teljesül.
  
 
''Ellenpélda:'' ''a''<sub>n</sub><math>\equiv</math>1 és (''b''<sub>n</sub>)=(n).
 
''Ellenpélda:'' ''a''<sub>n</sub><math>\equiv</math>1 és (''b''<sub>n</sub>)=(n).
169. sor: 175. sor:
  
  
2 --> 1 viszont logikai okokból igaz.
+
2 -- > 1 viszont logikai okokból igaz.
  
'' Bizonyítás'': ha mindekettő korlátos, akkor világos, hogy legalább az egyik korlátos.
+
'' Bizonyítás'': ha mindkettő korlátos, akkor világos, hogy legalább az egyik korlátos.
  
  
1 --> 3 valószínűleg nem igaz. Valóban:  
+
1 -- > 3 valószínűleg nem igaz. Valóban:  
  
''ellenpélda'' az 1-->2-beli.
+
''ellenpélda'' az 1-- >2-beli.
  
 
''Ugyanis,'' bár legalább az egyik korlátos, de a szorzat (1<math>\cdot</math>n)=(n) nem az.
 
''Ugyanis,'' bár legalább az egyik korlátos, de a szorzat (1<math>\cdot</math>n)=(n) nem az.
  
2 --> 3 igaz.
+
2 -- > 3 igaz.
  
 
''Bizonyítás.'' |''a''<sub>n</sub><math>\cdot</math>''b''<sub>n</sub>|=|''a''<sub>n</sub>|<math>\cdot</math>|''b''<sub>n</sub>| < ''K''<math>\cdot</math>''L'', ahol ''K'' az egyik, ''L'', a másik sorozat abszolútértékét felül becslő szám.
 
''Bizonyítás.'' |''a''<sub>n</sub><math>\cdot</math>''b''<sub>n</sub>|=|''a''<sub>n</sub>|<math>\cdot</math>|''b''<sub>n</sub>| < ''K''<math>\cdot</math>''L'', ahol ''K'' az egyik, ''L'', a másik sorozat abszolútértékét felül becslő szám.
  
3 --> 2 nem igaz
+
3 -- > 2 nem igaz
  
 
''Ellenpélda.'' (n) és (1/n)
 
''Ellenpélda.'' (n) és (1/n)
190. sor: 196. sor:
 
''Ugyanis.'' bár a szorzat korlátos, az egyik sorozat nem az.
 
''Ugyanis.'' bár a szorzat korlátos, az egyik sorozat nem az.
  
3 --> 1 becsapós.
+
3 -- > 1 becsapós.
  
 
''Ellenpélda.'' ''a''<sub>n</sub> = ''n'', ha ''n'' páros és ''a''<sub>n</sub> =1/''n'', ha ''n'' páratlan. ''b''<sub>n</sub> a "fordítottja", azaz párosakra 1/''n'' és páratlanokra ''n''.  
 
''Ellenpélda.'' ''a''<sub>n</sub> = ''n'', ha ''n'' páros és ''a''<sub>n</sub> =1/''n'', ha ''n'' páratlan. ''b''<sub>n</sub> a "fordítottja", azaz párosakra 1/''n'' és páratlanokra ''n''.  
  
''Ugyanis,'' ''a''<sub>n</sub><math>\cdot</math>''b''<sub>n</sub> = 1 és korlátos, de egyik sem korlátos önmagában.
+
''Ugyanis,'' ''a''<sub>n</sub><math>\cdot</math>''b''<sub>n</sub> = 1 és korlátos, de egyik sem korlátos önmagában.-->
  
 
==Házi feladatok==
 
==Házi feladatok==

A lap jelenlegi, 2016. szeptember 6., 09:16-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 módszere 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álya lényegében az, hogy megadja, mire következtethetünk az adott operátorral összekötött mondatokból, jelen esetben például A és B összetett mondatból. 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 értelemezése szerint minden olyan esetben, amikor az {A, B} premisszapár minden tagja igaz, levonhatjuk az A és B konklúziót:

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

A vagy (jelben: \vee) bevezetési szabálya szinté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övetkezteté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.

Megjegyzés

Ezekkel 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

A fenti 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)

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.


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