FHNW: mgli

Gegeben: \(R \subset M \times M\)

\(S \circ R := \{ (x,z) | \exists y \in M : (x,y) \in R \wedge (y,z) \in S \}\)

Tipp: Am besten von rechts nach links lesen

Sei \(R \subset A \times B\)

Die Relation \(R\) heisst total, wenn für alle Elemente \(x \in A\) mindestens ein Element \(y \in B\) existriert, dass gilt \((x,y) \in R\)

Sei \(R \subset A \times B\)

\(\forall x \in A , \forall y,z \in B : (x,y),(x,z) \in R \rightarrow y = z\)

Die Relation \(R\) heisst funktional, wenn für alle Elemente \(x \in A\) und alle Elemente \(y,z \in B\), für die \((x,y) \in R \) und \((x,z) \in R\), folgt, dass \(y = z\)

Eine Relation \(R \subset A \times B\)  heisst eine Funktion oder eine Abbildung genau dann, wenn \(R\) total und funktional ist.

\(f : A \longrightarrow B\)

       \(x \longrightarrow f(x)\)

Gegeben seien zwei Halbordnungen: \((M, \sqsubseteq) , (M^*,\sqsubseteq^*)\)

\(h : M \longrightarrow M^*\)

\(\forall x,y \in M : ( x \sqsubseteq y \rightarrow h(x) \sqsubseteq ^{*} h(y))\)

Eine binäre Relation \(R \subset M \times M\) heisst eine Äquivalenzrelation auf \(M\) wenn \(R\) als Relation reflexiv, symmetrisch und transitiv ist.

Sei \(R\) eine Äquivalenzrelation auf \(M\) und \(a \in M\). Dann nennen wir die Menge \([a] := \{x | (x,a) \in R \}\) die Äquivalenzklasse von \(a\).

Sei \(R\) eine Äquivalenzrelation auf \(M\).

Die Menge \(\pi := \{ [a] \text{ }|\text{ } a \in M \}\)ist eine Parition von \(M\)

Geg eine endliche Menge \(M\)

Eine Teilmenge \(U\) von \(P(M)\) (\(U\) ist also eine Menge von Teilmengen von \(M\)), heisst ein Teilmengensystem der Menge \(M\), wenn folgende Bedinungen erfüllt sind:

1. \(\emptyset \in U\)
2. Falls \(B \in U\) und \(A \subset B\), dann folgt \(A \in U\)

Ein Paar \((M, U)\) bestehend aus einer Menge \(M\) und einem Teilmengensystem \(U\) heisst ein Matroid, wenn die folgende Bedingung erfüllt ist:

Für alle Mengen \(A,B\) aus \(U\) mit \( |A| < |B|\) gilt, dass ein Element \(x \in B − A\) existiert, so dass die Menge \(A \cup \{x\} \)ebenfalls in \(U\) liegt.

Eine Relation \(R \subset A \times B\) heisst eine Funktion oder eine Abbildung genau dann, wenn \(R\)  total und funktional ist.

Sei \(f : A \longrightarrow B \leftrightarrow f \subset A \times B \) total und funktional (Funktion)

\(f \) ist surjektiv (auf) \(\leftrightarrow \forall y \in B : \exists x \in A : f(x) = y\)

Sei \(f : A \longrightarrow B \leftrightarrow f \subset A \times B \) total und funktional (Funktion)

\(f \) ist injektiv \(\leftrightarrow \forall x_1 , x_2 \in A : f(x_1) = f(x_2) \Rightarrow x_1 = x_2\)

Eine Funktion ist bijektiv, wenn sie injektiv und surjektiv ist.

\(f: A \longrightarrow B\)

\(g: B \longrightarrow C\)

\(g \circ f(x) = g(f(x))\)

Eine endliche Menge von Zeichen nennen wir ein Alphabet und bezeichnen es häufig mit \(\Sigma\). Die Elemente von \(\Sigma\) heissen Buchstaben.

• Eine endliche Folge von Buchstaben aus dem Alphabet \(\Sigma\)  nennen wir ein Wort über \(\Sigma\)
• Menge aller endlicher Wörter über \(\Sigma\) bezeichnen wir mit \(\Sigma^*\) 
• Menge aller nicht leeren endlichen Wörter über \(\Sigma\)mit \(\Sigma^+ := \Sigma^* - \{\epsilon\}\)

Das leere Wort: \(\epsilon\)

\(G:= (N, T,R,S)\)

• Nichtterminalsymbole: \(N\)
• Terminalsymbole / Variablen: \(T\)
• Eine endliche Menge von Regeln: \(R \subset (N \cup T)^+ \times(N\cup T)^*\)
• Startsymbol: \(S \in N\)

Die Menge der Regeln ist eine binäre Relation zwischen \(R \subset (N \cup T)^+\)  und \((N\cup T)^*\).

Regeln \((u,v)\) werden häufig durch die Bezeichnung \(u \longrightarrow v\) dargestellt.

Die leere Menge beinhaltet keine Elemente.

Die Notation lautet \(\{ \}\) oder \(\emptyset\)

Elemente in der Teilmenge T sind auch in der Menge M entahlten: 
\(x \in T\) und \(x \in M\)

Notation für Teilmenge:

\(T \subset M\)

Die Potenzmenge \(P(M)\) von \(M\) ist die Menge aller Teilmengen von \(M\)

Beispiel:

\(M:= \{1,2\}\)

\(P(M) = \{\emptyset, \{1\},\{2\},\{1,2\}\}\)

Ein geordnetes Paar, auch 2-Tupel genannt, ist in der Mathematik eine wichtige Art und Weise, zwei mathematische Objekte zu einer Einheit zusammenzufassen. Die beiden Objekte müssen dabei nicht notwendigerweise voneinander verschieden sein und ihre Reihenfolge spielt eine Rolle.

\(a \in A\) und \(b \in B\)

Notation: \((a,b)\)

Das geordnete Paar von a und b.

Zwei geordnete Paare sind gleich \((a,b) = (c,d)\) wenn \(a = c\) und \(b = d \) gilt.

Das kartesische Produkt zweier Mengen ist die Menge aller geordneten Paare von Elementen der beiden Mengen, wobei die erste Komponente ein Element der ersten Menge und die zweite Komponente ein Element der zweiten Menge ist.

Die Ergebnismenge wird oft auch Produktmenge oder Kreuzmenge genannt.

Definition: \(A \times B := \left\{ (a, b) \mid a \in A, b \in B \right\}\)

Beispiel zum Bild:

\(A := \{x,y,z\}\) und \(B:= \{1,2,3\}\)

\(A \times B\)

Die Reihenfolge der Mengen spielt eine Rolle. Es entstehen unterschiedliche Mengen!

Beispiel:

\(A=\{ a, b, c \}\) und \(B=\{ x, y \} \)

\(A \times B = \left\{ (a,x), (a,y), (b,x), (b,y), (c,x), (c,y) \right\}.\)

\(B \times A = \left\{ (x,a), (x,b), (x,c), (y,a), (y,b), (y,c) \right\},\)

Eine zweistellige Relation \(R\) zwischen zwei Mengen \(A\) und \(B\) ist eine Teilmenge des kartesischen Produkts\( A \times B = \{(a,b) \mid a \in A, b \in B\}\)

Beispiel:

\(A := \{1,2\} , B:= \{3,4\}\)

\(\{(1,3)\} \subset A \times B = \{(1,3),(1,4),(2,3),(2,4)\}\)

In der Mengenlehre ist eine Partition (auch Zerlegung oder Klasseneinteilung) einer Menge M eine Menge P, deren Elemente nichtleere Teilmengen von M sind, sodass jedes Element von M in genau einem Element von P enthalten ist.

Beispiel:

\(P = \left\{\left\{3,5\right\},\left\{2,4,6\right\},\left\{7,8,9\right\}\right\}\)ist eine Partition der Menge \(M=\left\{2,3,4,5,6,7,8,9\right\}\). Die Elemente von \(P\) sind dabei paarweise disjunkte Teilmengen von \(M\). (Teilmengen sind die Mengen innerhalb von P)

\(P\) ist jedoch keine Partition der Menge \(N=\left\{1,2,3,4,5,6,7,8,9\right\}\), weil 1 zwar in \(N\), aber in keinem Element von \(P\) enthalten ist.

Die Anzahl \(B_n\)  der Partitionen einer \(n\)-elementigen Menge nennt man Bellsche Zahl(nach Eric Temple Bell). Die ersten Bellzahlen sind:

\( B_0 = 1, \quad B_1 = 1, \quad B_2 = 2, \quad B_3 = 5, \quad B_4 = 15, \quad B_5 = 52, \quad B_6 = 203, \quad\ldots\)

Gegeben sei eine Menge \(M\)

Eine Menge \(P\) bestehend aus Teilmengen \(A_1,A_2,...\) der Menge \(M\) heisst eine Partition von \(M\), wenn gilt:

1. Sie ist eine Teilmenge von \(M\): \(A_i \subset M\)
2. Die Teilmengen \(A_i\) sind nicht leer.
3. Je zwei verschiedene Teilmengen sind disjunkt: \(A_i \cap A_j = \emptyset\) wenn \(i \neq j\)
4. Die Vereinigung aller Mengen \(A_i\) ist \(M\): 
   \(M = A_1 \cup A_2 \cup \dots\)

Notation:\(A \cup B\)

Definition: \(A \cup B := \{x | x \in A \text{ or } x \in B \}\)

Notation: \(A \cap B\)

Definition: \(A \cap B := \{x | x \in A \text{ and }x \in B \}\)

Notation: \(A \backslash B \text{ or } A - B\)

Definition: \(A \backslash B := \{ x \in A |x \notin B\}\)

Notation: \(A' \text{ or } \bar{A}\)

Definition: \(\bar{A} := \{x \in G | x \notin A\}\)

Notation: \(B \subset A\)

Definition: \(B \subset A \Leftrightarrow \forall x\in G : x \in B \Rightarrow x \in A\)

\(A \cup \emptyset = A\)

\(A \cup \bar{A}= G\)

\(A \cup B = B \cup A\) (kommutativ)

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

\(A \cap G =A\)

\(A \cap \bar{A} = \emptyset\)

\(A \cap B = B \cap A\) (kommutativ)

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

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

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