#!/usr/bin/env python
# coding: utf-8
# # Mengenoperationen
# ## Was sind denn überhaupt Operationen?
#
# Operationen ordnen einer festgelegten Anzahl von Argumenten ein Ergebnis zu.
# Zum Beispiel ist die Addition eine arithmetische Operation mit 2 Argumenten: $5+3=8$.
# Die beiden Argumente sind $5$ und $3$, das Ergebnis ist $8$.
# Weil die Addition 2 Argumente nimmt, nennt man sie eine *binäre* Operation.
#
# Es gibt auch einige wichtige Operationen in der Mengenlehre. Diese Mengenoperationen werden wir uns hier ansehen.
# ## Die Potenzmengenoperation
# Die Definition der Potenzmengenoperation läuft in 2 Schritten ab.
# Erst wird definiert, was die Potenzmenge überhaupt ist, dann wird die entsprechende Operation festgelegt.
#
#
# Die Potenzmenge einer Menge $M$ ist die Menge aller möglichen Teilmengen von $M$.
# Die Potenzmenge ist also eine Menge von Mengen.
# Zur Erinnerung: Eine Menge N ist eine Teilmenge von M, wenn alle Elemente aus N auch in M sind.
# Jede Menge hat genau eine Potenzmenge.
#
# Die Potenzmengenoperation ist die Operation, die jeder Menge ihre Potenzmenge zuordnet.
# Man braucht diese Operation, damit man ein Symbol hat, mit dem man sich immer auf die Potenzmenge einer Menge beziehen kann. Wir verwenden die Notation $\mathcal{POT}(M)$.
# Ein paar Beispiele:
#
# 1. $\mathcal{POT}(\{1\})=\{\emptyset,\{1\}\}$
# 2. $\mathcal{POT}(\{1,2\})=\{\emptyset,\{1\},\{2\},\{1,2\}\}$
# 3. $\mathcal{POT}(\{1,2,3\})=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$
#
# Wichtig dabei: Die leere Menge $\emptyset$ ist Teilmenge jeder Menge.
# Alle Elemente der leeren Menge (nämlich gar keine) sind in jeder anderen Menge enthalten.
# Deshalb ist die leere Menge Element jeder Potenzmenge.
#
# ## Die Mächtigkeit der Potenzmenge
#
# Die Mächtigkeit einer Menge ist die Anzahl der Elemente der Potenzmenge (siehe das Ende des Skripts zu Mengen).
#
# Jetzt können wir für die Mächtigkeit der Potenzmenge eine Beobachtung machen: Wenn eine Menge M n Elemente hat, hat die Potenzmenge von M $2^n$ Elemente:
#
# $$|\mathcal{POT}(M)|=2^{|M|}$$
#
# Im Video wird dieser Zusammenhang näher erläutert. Es empfiehlt sich, das einmal an einem kleinen Beispiel selbst nachzurechnen.
# Wenn man weiß, wie viele Elemente die Potenzmenge haben muss, kann man einfach nachrechnen, ob man sie richtig gebildet hat.
#
#
#
# ## Schnitt, Vereinigung, Differenz, Komplement
# 
# In den folgenden Beispielen betrachten wir zwei Mengen $A=\{5,7,8\}$ und $B=\{5,6\}$
#
# Der **Schnitt** von zwei Mengen A und B ist die Menge, die alle Elemente enthält, die sowohl in A als auch in B sind. Beispiel:
#
# $$A \cap B = \{5\}$$
#
# Eine Vokabel taucht später immer wieder auf: Zwei Mengen sind *disjunkt*, wenn der Schnitt der beiden Mengen leer ist. Beispiel:
#
# $$A \cap \{12\}= \emptyset$$
#
# Die **Vereingung** von zwei Mengen A und B ist die Menge, in der alle Elemente aus A und B "zusammengeworfen" werden:
#
# $$A \cup B = \{5,6,7,8\}$$
#
# Dabei ist wichtig: Die $5$ ist sowohl in $A$ als auch in $B$ enthalten. In der Vereinigung der beiden Mengen taucht sie aber nur ein mal auf. Mengen können schließlich nicht dasselbe Element mehrfach enthalten.
# Die **Differenz** zweier Mengen A und B enthält alle Elemente, die in A, aber nicht in B sind.
#
# $$A-B=A\setminus B = \{7,8\}$$
#
# Hier kommt es auf die Reihenfolge an, denn die Differenz von A und B muss nicht die Differenz von B und A sein:
#
# $$B-A = B \setminus A = \{6\}$$
# Das **Komplement** einer Menge A ist eine besondere Form der Differenz. Oft gibt es bei Anwendungen der Mengenlehre ein *Universum* $U$. $U$ enthält alle Elemente, die in Betracht gezogen werden. Das Komplement von A in U ist dann die Menge aller Elemente aus U, die nicht in A sind.
#
# Sei in unserem Fall $U=\{3,4,5,6,7,8,9\}$. Dann ist
#
# $$C_U(A)= \overline{A} = U-A=U\setminus A=\{3,4,6,9\}$$ und
# $$C_U(B)= \overline{B} = U-B=U\setminus B=\{3,4,7,8,9\}$$
# ## Notation binärer Mengenoperationen
#
# 
#
# Die Notationen auf Folie 17 werden im Video erläutert.
#
#
# ## Gesetze zu Schnitt und Vereinigung
# 
# Oben haben wir bestimmte Operationen *definiert*: Die Vereinigung, den Schnitt, das Komplement. Aus diesen Definitionen lassen sich bestimmte *Gesetze* ableiten.
#
# Wir verwenden drei Beispielmengen: $A=\{5,7,8\}, B=\{5,6\}$ und $C=\{5,9\}$.
# ### Kommutativgesetze
# *commutare* lateinisch, italienisch: pendeln, vertauschen.
# Bei Schnitt und Vereinigung kommt es nicht auf die Reihenfolge der Argumente an. Die beiden Mengen können vertauscht werden, ohne dass das Ergebnis beeinflusst wird.
#
# $$A \cap B = B \cap A\\
# \Leftrightarrow \{5,7,8\} \cap \{5,6\} = \{5,6\} \cap \{5,7,8\}\\
# \Leftrightarrow \{5\}$$
#
# $$A \cup B = B \cup A\\
# \Leftrightarrow \{5,7,8\} \cup \{5,6\} = \{5,6\} \cup \{5,7,8\}\\
# \Leftrightarrow \{5,6,7,8\}$$
# ### Assoziativgesetze
# *assoziieren*: mit etwas verknüpfen. Werden mehr als ein Schnitt/eine Vereinigung hintereinander ausgeführt, kommt es nicht auf die Reihenfolge der Ausführung an. Es kommt also nicht auf die Art an, wie die Operationen miteinander verknüpft sind. Vergleichbar mit dem Assoziativgesetz in der Arithmetik, wo z.B. gilt: $(18+5)+3=18+(5+3)=26$
#
# $$(A \cap B) \cap C = A \cap (B \cap C)\\
# \Leftrightarrow (\{5,7,8\} \cap \{5,6\} ) \cap \{5,9\}= \{5,7,8\} \cap (\{5,6\} \cap \{5,9\})\\
# \Leftrightarrow \{5\} \cap \{5,9\}= \{5,7,8\} \cap \{5\}\\
# \Leftrightarrow \{5\} = \{5\}$$
#
# $$(A \cup B) \cup C = A \cup (B \cup C)\\
# \Leftrightarrow (\{5,7,8\} \cup \{5,6\} ) \cup \{5,9\}= \{5,7,8\} \cup (\{5,6\} \cup \{5,9\})\\
# \Leftrightarrow \{5,6,7,8\} \cup \{5,9\}= \{5,7,8\} \cup \{5,6,9\}\\
# \Leftrightarrow \{5,6,7,8,9\} = \{5,6,7,8,9\}$$
# ### Distributivgesetze
#
# engl. *distribute*: verteilen. Die Distributivgesetze beschreiben, wie sich Verknüpfungen aus Schnitt und Vereinigung bei der Auflösung von Klammern verhalten. Beim Auflösen der Klammern *verteilen* sich die Mengen. Auch hier kann ein Beispiel zum Distributivgesetz in der Arithmetik helfen:
#
# $$(3+4)*6=3*6+4*6=7*6=42$$
#
# In der Mengenlehre sieht das folgendermaßen aus:
#
# $$(A \cap B) \cup C = (A \cup C) \cap (B \cup C) \\
# \Leftrightarrow (\{5,7,8\} \cap \{5,6\}) \cup \{5,9\} = (\{5,7,8\} \cup \{5,9\}) \cap (\{5,6\} \cup \{5,9\}) \\
# \Leftrightarrow \{5\} \cup \{5,9\} = \{5,7,8,9\} \cap \{5,6,9\} \\
# \Leftrightarrow \{5,9\} = \{5,9\}$$
# $$(A \cup B) \cap C = (A \cap C) \cup (B \cap C) \\
# \Leftrightarrow (\{5,7,8\} \cup \{5,6\}) \cap \{5,9\} = (\{5,7,8\} \cap \{5,9\}) \cup (\{5,6\} \cap \{5,9\}) \\
# \Leftrightarrow \{5,6,7,8\} \cap \{5,9\} = \{5\} \cup \{5\} \\
# \Leftrightarrow \{5\} = \{5\} $$
# ### Idempotenzgesetze
# *Idemptenz* bedeutet in diesem Fall, dass eine Menge verknüpft mit sich selbst die Menge selbst ergibt. Beispiel:
#
# $$A \cap A = A\\
# \Leftrightarrow \{5,7,8\} \cap \{5,7,8\} = \{5,7,8\}$$
#
# $$A \cup A = A\\
# \Leftrightarrow \{5,7,8\} \cup \{5,7,8\} = \{5,7,8\}$$
# ### Neutrale Elemente
# Das neutrale Element einer binären Operation ist das Element, welches zusammen mit einem beliebigen anderen Argument X die Argumente der Operation bildet, und X kommt bei dieser Operation heraus. Beispiel aus der Arithmetik: 0 addieren oder mit 1 multiplizieren:
#
# $$4+0=4\\23*1=23$$
#
# Das neutrale Element der Vereinigung ist die Menge, mit der man eine andere Menge A vereinigt, und das Ergebnis der Vereinigung ist A:
#
# $$\{5,7,8\} \cup \emptyset = \{5,7,8\}$$
#
# Das neutrale Element des Schnitts ist die Menge, mit der man eine andere Menge A schneidet, und das Ergebnis des Schnitts ist A.
# Das neutrale Element des Schnitts ist $U$, das Universum. In unserem Beispiel ist $U=\mathbb{N}$
#
# $$A \cap U = \{5,7,8\} \cap \mathbb{N} = \{5,7,8\}$$
# ## weitere Gesetze
# 
# Die de-Morgan'schen Gesetze sind wichtige Gesetze der Mengenlehre (und haben Entsprechungen in der Logik). Die Videos betrachten den Beweis der Gesetze auf zwei Arten: Graphisch mittels Venn-Diagrammen, und in ausformulierter Form.
#
# Einige Vokabeln sind hilfreich zum Verständnis der Videos. Man wird diese immer wieder sehen, da viele Texte in der Computerlinguistik auf Englisch sind.
#
# - Menge - set
# - Vereinigung - union
# - Schnitt - intersection
# ### De-Morgan's Gesetze mit Venn-Diagrammen
#
# ### De-Morgan's Gesetze ausformuliert
#
# Hier nimmt man ein beliebiges $x$ und zeigt die de Morgan'schen Gesetze durch Aussagen darüber, ob $x$ Element bestimmter Mengen ist.
# An die Experten: Ist der Beweis vollständig? Was fehlt?
# In[ ]: