Mathematik: Diskrete Mathematik: Mengenlehre

Hoch zu Diskrete Mathematik Inhaltsverzeichnis

Definition

Eine Menge ist eine Sammlung von verschiedenen Dingen, wie z.B.

• Zahlen
• Buchstaben
• Farbe
• Figuren
• Namen

Mengen werden mit Großbuchstaben benannt.

Darstellungen

Es gibt verschiedene Möglichkeiten eine Menge darzustellen:

• graphisch mit Hilfe von Mengenbildern

• in aufzählender Form:

$B=\{1;2;3;4;5\}$
$\mathbb {N} _{0}=\{0;1;2;3;4;5;6;...\}$

• in beschreibender Form:

$P=\{x\mid x\ \mathrm {ist\ Primzahl} \}$
$C=\{x\in N\mid x<5\}$

Elemente

Die in der Menge beinhalteten Objekte nennt man Elemente.
$x\in A$ (lies "x ist Element von A") bedeutet, dass x ein Element der Menge A ist, also in dieser Menge liegt.

$x\notin A$ (lies "x ist nicht Element von A") bedeutet, dass x kein Element der Menge A ist, also nicht in A liegt.

Beispiel:
$A=\{1;2;3\}\Rightarrow$ $1\in A,2\in A,5\notin A$

Besitzt eine Menge keine Elemente, so ist sie die leere Menge.
$\{\}=\phi$
Eine Menge kann jedoch eine leere Menge enthalten !
$M=\{\phi \}$

Gleichheit

Zwei Mengen sind gleich, wenn sie genau die gleichen Elemente beinhalten. Beim Aufzählen von Mengen zählt weder die Reihenfolge der einzelnen Elemente, noch die Anzahl der gleichen Elemente.
$A=\{1;2;3\}$ $=\{3;1;2;2\}$ $=B$

Mächtigkeit

Die Mächtigkeit einer endlichen Menge ist die Anzahl ihrer Elemente. Beispiele:

$|\{1;2;3\}|=3$

$|\{\}|=0$

Bei unendlichen Mengen hat wird der Anzahlbegriff problematisch; die Mächtigkeit wird durch ein Symbol ausgedrückt, das ausdrücklich keine Zahl im arithmetischen Sinne ist. Für die Mächtigkeit der natürlichen Zahlen schreibt man

$|\mathbb {N} |=\aleph _{0}$

(gesprochen aleph null).

Aus Mengen gebildete Mengen

• Die Teilmenge: Die Teilmenge ist eine Menge die in der Ausgangsmenge enthalten ist, und so alle Elemente dieser beinhaltet.$B\subseteq A\Leftrightarrow (x\in B\Rightarrow x\in A)$
  Datei:Teilmenge.png
• Die Potenzmengen: Die Potenzmenge beinhaltet alle möglichen Teilmengen.

$P(A)=\{\phi ;\{1\};\{2\};\{3\};\{1;2\};\{1;3\};\{2;3\};\{1;2;3\}\}$
Die Mächtigkeit der Potenzmenge beträgt immer die Potenz von 2 mit der Mächtigkeit der Ausgangsmenge: $|P(A)|=2^{|A|}$
Datei:Menge aller teilmengen.png

• Die Schnittmenge: Die Schnittmenge beinhaltet alle Elemente, die gleichzeitig in der Menge A und B enthalten ist.
  

$A\cap B=\{x\in A\wedge x\in B\}$

• Die Vereinigungsmenge: Die Vereinigungsmenge beinhaltet alle Elemente, die entweder in A oder in B enthalten sind.
  

$A\cup B=\{x\in A\vee x\in B\}$
Datei:Vereinigungsmenge.png

• Die Differenzmenge: Die Differenzmenge beinhaltet alle Elemente, die in A aber nicht in B enthalten sind.
  

$A\setminus B=\{x\in A\wedge x\notin B\}$

Rechenregeln für Mengenoperationen

Für beliebige Mengen $A,B,C$ gelten die folgenden Rechenregeln

• Kommutativgesetze

$A\cup B=B\cup A$

$A\cap B=B\cap A$

• Assoziativgesetze

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

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

• Distributivgesetze

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

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

• Absorptionsgesetze

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

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

• Idempotenzgesetze

$A\cap A=A$

$A\cup A=A$

• De Morgansche Regel

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

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

Relationen

Definition

Sind die Mengen $A$ und $B$ endliche, nicht leere Mengen, so heißt $R\subseteq A\times B$ (binäre) Relation zwischen A und B.