Matematika közlek A1a 2013/2. gyakorlat

A MathWikiből
A lap korábbi változatát látod, amilyen Mozo (vitalap | szerkesztései) 2013. szeptember 15., 11:03-kor történt szerkesztése után volt.

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.

(\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

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


5. feladat. Egyszerűsítse az alábbi kifejezéseket!

    1. (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})=?
    2. (A\cap B)\cup C=?, ha A\subseteq C.

Mo. 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!

D=A\cap ((B\cap C)\cup (B\cap \overline{C})\cup(\overline{B}\cap C)\cup(\overline{B}\cap \overline{C}))=

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:

=A\cap ((B\cap (C\cup \overline{C}))\cup(\overline{B}\cap (C\cup\overline{C})))=

ekkor a halmaz és komplementere kiadja U-t, így:

=A\cap ((B\cap U)\cup(\overline{B}\cap U))=A\cap (B\cup\overline{B})=A \cap U=A

Tehát D = A.

Vagy Boole-algebrai formalizmusban:

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})=
 =a(1c+1\overline{c})=a(c+\overline{c})=a\cdot 1=a

1.2.

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

az elnyelési tulajdonság miatt és mert AC pontosan azt jelenti, hogy A U C = 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.

Halmazegyenletek

7. feladat. Oldja meg az alábbi halmazegyenleteket, X-re!

    1.  (A-X)\cup B=X\,
    2. A-X=X-A\,

Megoldás.

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 nem egy ekvivalens átalakítás, csak ritkán, melyenek fennállását külön meg kell gondolnunk):

\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}

ez utóbbi pontosan azt jelenti, hogy XB. Emellett a feltétel mellett B-vel a baloldalon "beuniózva":

 [\;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

amiből következik, hogy BX és AX. Ez azt jelenti, hogy ha van megoldás, akkor az egyértelmű éspedig

X=B\,

Most vizsgáljuk meg a megoldhatóság feltételét. Azt kaptuk, hogy ha van megoldás, akkor AX = B, vagyis

A\subseteq B\,

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:

 \quad\quad(A\cap \overline{B}) \cup B =\emptyset \cup B=B

2.

A-X=X-A\,

vagyis

A\cap\overline{X}=X\cap \overline{A}\,

Ha van megoldás és bemetszünk mindkét oldalon A-val (ez nem egy ekvivalens átalakítás, csak ritkán, melyenek fennállását külön meg kell gondolnunk), akkor

A\cap A\cap\overline{X}=X\cap \overline{A}\cap A\,
A\cap\overline{X}=\emptyset

azaz AX, de az egyenlet szimmetrikus az A és az X felcserélésére, ezért XA is teljesül, amiből X = A, ha van megoldás. Márpedig az egyenletet az X = A kielégíti.

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