Szerkesztő:Mozo/A2 szigorlat 1

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.

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.

Igazoljuk a disztributív szabályt (egyik irány)

$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é.

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$

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

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.

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

esetet.

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 kvantorokra 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ú.

Az üres halmaz minden halmaznak része.

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.

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 .

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