# Mengenlehre

In dieser Präsentation lernen Sie, wie man Mengenoperationen in mathGUIde darstellt und wie man die Gleichheit zweier Mengen durch eine Fallunterscheidung ermitteln kann.

## Mengenoperatoren in mathGUIde

    A = Set([1,2])
    B = Set([2,3])

    A + B        # Vereinigung
    A & B        # Durchschnitt
    A ^ B        # Symmetrische Differenz
    A * B        # Kartesisches Produkt
    A.powerset() # Potenzmenge
    A.card()     # Mächtigkeit (Kardinalzahl)

## Gleichheit zweier Mengen

Zwei Teilmengen A und B (einer Grundmenge M) sind gleich, wenn für alle möglichen Elemente x (aus M) gilt:

x \in A \Leftrightarrow x \in B

Um die Richtigkeit einer Mengengleichung wie z. B. des folgenden Distributivgesetzes

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

zu entscheiden, formen wird die Gleichung in eine logische Aussage um:

\def\blue{\bbox[#c0e0ff,2pt]} \def\green{\bbox[#d0ffd0,2pt]} x \in (A \green\cap (B \cup C)) \Leftrightarrow x \in ((A \cap B) \blue\cup (A \cap C))

Mit den Definitionen von Durchschnitt und Vereinigung ergibt sich daraus

x \in A \green\wedge x \in (B \cup C) \Leftrightarrow x \in (A \cap B) \blue\vee x \in (A \cap C)

Die verbleibenden Vereinigungs- und Durchschnittsoperatoren lassen sich ebenso ersetzen:

x \in A \wedge (x \in B \vee x \in C) \Leftrightarrow (x \in A \wedge x \in B) \vee (x \in A \vee x \in C)

Wenn wir jetzt die drei Aussagen durch Variablen ersetzen

\begin{eqnarray} & x \in A & \; \small\textrm{durch}\normalsize \; a \\ & x \in B & \; \small\textrm{durch}\normalsize \; b \\ & x \in C & \; \small\textrm{durch}\normalsize \; c \\ \end{eqnarray}

bekommen wir

a \wedge (b \vee c) \Leftrightarrow (a \wedge b) \vee (a \vee c)

Die Richtigkeit dieser Aquivalenz kann mathGUIde überprüfen:

    Logic.equivalent("a and (b or c)", "(a and b) or (a and c)")

Wie hat mathGUIde das entschieden? Ganz einfach, durch eine Fallunterscheidung. Wir nehmen diese Fallunterscheidung nun direkt vor: Dazu betrachten wir ein beliebiges Element x und fragen, in welchen der drei Mengen A, B und C es enthalten ist. Es gibt 23 = 8 Möglichkeiten, die wir in den rechten 8 Spalten der folgenden Tabelle unterscheiden (0 für nicht enthalten, 1 für enthalten):

In der ersten hellblauen Tabellenzeile stehen die Werte für die Vereinigung von B und C. Hier steht (nach Def. der Vereinigung) also genau dann eine Eins, wenn in der zweiten oder in der dritten Zeile eine Eins steht. In den beiden anderen hellblauen Tabellenzeilen sind die Bestandteile der rechten Seite der Mengengleichung ausgewertet.
Die linke Seite der Mengengleichung ergibt sich nun aus der ersten grauen und der ersten hellblauen Zeile (erste dunkelblaue Zeile). Die rechte Seite der Mengengleichung ergibt sich aus den beiden unteren hellblauen Zeilen (zweite dunkelblaue Zeile).

In allen acht Fällen stimmen die Ergebnisse überein (punktierte Linie!). Die beiden Mengen sind also gleich!

## Venn-Diagramme: Fallunterscheidung mit „repräsentativen“ Mengen

Die Fallunterscheidung lässt sich geometrisch darstellen:

- Wir wählen für die acht Fälle je ein Element.
  Dafür verwenden wir die acht dreistelligen Binärzahlen 000, 001, 010, ..., 111.
  Die drei Ziffern stehen für das Enthaltensein in den Mengen A, B, C.
- Diese acht Elemente packen wir so in drei Mengen, dass sich alle acht Fälle unterscheiden lassen.

Eine geometrische Darstellung dieser Mengen wird als „Venn-Diagramm“ bezeichnet.

Venn-Diagramme sind sehr praktisch für Mengengleichungen, in denen bis zu drei oder notfalls noch vier Mengen vorkommen. Für fünf und mehr Mengen wird es sehr aufwendig, die 25 und mehr Fälle übersichtlich abzugrenzen und zu überprüfen.

Wir beschränken uns auf die drei Mengen A, B, C. Wenn ein Element in A liegt, gibt es folgende Möglichkeiten (vgl. Abb.):

- Es liegt weder in B noch in C ("100")
- Es liegt in C, aber nicht in B ("101")
- Es liegt in B, aber nicht in C ("110")
- Es liegt B und in C ("111")

Mit den gleichen Überlegungen für B und C können wir die folgenden repräsentativen Mengen definieren:

    A = Set(["100", "101", "110", "111"])
    B = Set(["010", "011", "110", "111"])
    C = Set(["001", "011", "101", "111"])

### Überprüfung des Distributivgesetzes

Unser Ausgangsbeispiel

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

lässt sich jetzt ganz einfach überpüfen:

    # Ist A & (B+C) == (A & B) + (A & C) ?
    print(A & (B+C))
    print((A & B) + (A & C))

Die Ausgabe von mathGUIde zeigt die Gleichheit der beiden Mengen

Als Übung versuchen Sie es bitte einmal mit dem anderen Distributivgesetz:

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

### Assoziativität der symmetrischen Differenz:

Die symmetrische Differenz ist definiert durch

x \in A \bigtriangleup B \quad\Leftrightarrow\quad x \in A \quad \textrm{xor} \quad x \in B

Wir überprüfen die Assoziativität der symmetrischen Differenz:

(A \bigtriangleup B) \bigtriangleup C = A \bigtriangleup (B \bigtriangleup C)

    # Ist (A ^ B) ^ C == A ^ (B ^ C) ?
    print((A ^ B) ^ C)
    print(A ^ (B ^ C))

Wieder sehen Sie dass die beiden Mengen gleich sind.