2. előadás

1. biz (Metszet kommutativitása)

\[ A \cap B = B \cap A \]

Definíció alapján: \(x \in A \cap B\), ha \(x \in A \land x \in B\)

Másik def: \(X = Y \iff \forall x:(x \in X \iff y \in Y)\)

Egyenlők \(\iff\) ugyanazok az elemeik

Tehát, a bizonyítás

\[ x \in A \cap B \iff x \in A \land x \in B \iff x \in B \land x \in A \iff x \in B \cap A \]

\(x \in A \land x \in B \iff x \in B \land x \in A\) bizonyítható igazságtáblával

1. állítás

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

Tehát \(\cap\) disztributív \(\cup\)-ra

2. állítás

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

Biz: igazságtábla

Halmaz műveletek

\(A \triangle B\)

szimmetrikus differencia, "szimdiff"

\[ x \in A \triangle B \iff x \in A \oplus x \in B \]

\(A \backslash B\)

\(A\) különbség \(B\)

\[ x \in A \backslash B \iff x \in A \land x \notin B \]

Állítás 3

\[ A \triangle B = (A \backslash B) \cup (B \backslash A) = (A \cup B) \backslash (A \cap B) \]

Állítás 4

\[ (A \triangle B) \triangle C = A \triangle (B \triangle C) \]

Halmazok halmaza (halmazrendszer)

Pl: \(\{\{1, 2\}, \{2, 3\}, \{3, 4\}\}\)

Def: \(X\) halmazrendszer:

\(\cup X := \{a | \exists A \in X: a \in A\}\)
\(\cap X := \{a | \forall A \in X: a \in A\}\)

Szótár

halmazok	logika
\(\cap\)	\(\land\)
\(\cup\)	\(\lor\)
\(\triangle\)	\(\oplus\)
\(\backslash\)	\(ANDNOT\)
\(\overline{A}\)	\(\lnot\)
\(\subseteq\)	\(\Rightarrow\)

Komplementer

Def: Ha van egy NAGY \(U\) (univerzum) nevű halmaz, melynek minden aktuálisan vizsgált eleme része, akkor \(A \subseteq U\)-nak az U-ra vonatkozó komplementere: \(U \backslash A\).

Állítás 5

\[ x \in U: x \notin A \iff x \in \overline{A} \]

Állítás 6

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

Halmaz műveletek

7., 8.: De Morgan szabályok

Hatványhalmaz

\[ P(A) = \{H | H \subseteq A\} \]

vagyis: \(x \in P(A) \iff x \subseteq A\)

Pl: \(A = \{1, 2, 3\} \rightarrow P(A) = \{\varnothing, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}\)

\(P(\varnothing) = \{\varnothing\}\)

\(P(\{\varnothing\}) = \{\varnothing, \{\varnothing\}\}\)

Rendezett pár

\((a, b) = \{a, \{a, b\}\}\)

Állítás: rendezett párok

\[ (a, b) = (c, d) \iff a = c \land b = d \]

Descartes szorzat

\[ A \times B \]

\(A\) kereszt \(B\)

\(A \times B := \{(a, b | a \in A, b \in B)\}\)

Pl: \(\{1, 2, 3\} \times \{x, y\} = \{(1, x), (1, y), (2, x), (2, y), (3, x), (3, y)\}\)

2. témakör: Relációk

Pl.:

\(((a < b) \land (b < c)) \Rightarrow a < c\)
\(((A \subseteq B) \land (B \subseteq C)) \Rightarrow A \subseteq C\)
\(\mathbb{Z}\): ((a osztója b-nek) \(\land\) (b osztója c-nek)) \(\Rightarrow\) a osztója c-nek
Geometria: \((e || f \land f || g) \Rightarrow e || g\)

a <, \(\subseteq\), osztója, \(||\) RELÁCIÓ TRANZITÍV.

DEF: \(R\) egy reláció (binér reláció), ha minden eleme rendezett pár

Pl.: \(\{(1, 10), (2, 20), (3, 30)\}\)

???

\(a\) osztója \(b\)-nek \(\iff\) \(b\) többszöröse \(a\)-nak

\(a < b \iff b > a\)

\(a\) szülője \(b\)-nek \(\iff\) \(b\) gyereke \(a\)-nak

\(e || f \iff f || e\)

R reláció inverze

R reláció inverze: \(R^{-1}\)

\(R^{-1} := \{(b, a) | (a, b) \in R\}\)

Kompozíció

\(R\), \(S\) relációk

\(R \circ S := \{(x, z) | \exists y: (x, y) \in S \land (y, z) \in R\}\) (\(R\) kör \(S\))

Kompozíció állítás

\((R \circ S)^{-1} = S^{-1} \circ R^{-1}\)

Bizonyítás

\((z, x) \in (R \circ S)^{-1} \iff (x, y) \in (R \circ S) \iff \exists y: (x, y) \in S \land (y, z) \in R \iff \exists y: (y, x) \in S^{-1} \land (z, y) \in R^{-1} \iff (z, x) \in S^{-1} \circ R^{-1}\)