2.3 Mengenoperationen

Mengen verknüpfen

Aus zwei Mengen lassen sich durch logische Bedingungen neue Mengen bilden. Die Junktoren aus Kapitel 1 erscheinen dabei direkt in den Definitionen.

Definition 2.6 (Mengenoperationen). Seien \(A\) und \(B\) Teilmengen einer Grundmenge \(E\).

\[ \begin{aligned} A\cap B &:=\{x\in E\mid x\in A\ \wedge\ x\in B\}, &&\text{Durchschnitt},\\ A\cup B &:=\{x\in E\mid x\in A\ \vee\ x\in B\}, &&\text{Vereinigung},\\ A\setminus B &:=\{x\in E\mid x\in A\ \wedge\ x\notin B\}, &&\text{Differenz},\\ \overline A &:=E\setminus A, &&\text{Komplement von }A\text{ in }E. \end{aligned} \]

Abbildung 2.1: Durchschnitt, Vereinigung, Differenz und Komplement als Venn-Diagramme.

In Abbildung 2.1 ist jeweils der Bereich markiert, dessen Elemente die zugehörige Bedingung erfüllen. Bei \(A\setminus B\) ist die Reihenfolge wichtig; im Allgemeinen gilt \(A\setminus B\ne B\setminus A\).

Ein Anwendungsbeispiel übersetzt die vier Operationen in eine typische Zugriffsverwaltung.

Beispiel: Zugriffsrechte auf Hochschuldienste

\(G\) sei die Menge der Studierenden mit GitLab-Zugang und \(J\) die Menge der Studierenden mit JupyterHub-Zugang. Dann beschreibt

  • \(G\cap J\) alle Personen mit Zugang zu beiden Diensten,
  • \(G\cup J\) alle Personen mit mindestens einem der beiden Zugänge,
  • \(G\setminus J\) alle Personen mit GitLab-, aber ohne JupyterHub-Zugang und
  • \(\overline G\) bezüglich der Grundmenge aller Kursteilnehmenden diejenigen ohne GitLab-Zugang.

Rechengesetze

Da Durchschnitt und Vereinigung über \(\wedge\) und \(\vee\) definiert sind, spiegeln ihre Rechengesetze die Gesetze der Aussagenlogik wider.

Satz 2.2 (Kommutativ-, Assoziativ- und Distributivgesetze). Für beliebige Teilmengen \(A,B,C\subseteq E\) gilt

\[ \begin{aligned} A\cup B&=B\cup A, &A\cap B&=B\cap A,\\ (A\cup B)\cup C&=A\cup(B\cup C), &(A\cap B)\cap C&=A\cap(B\cap C),\\ (A\cup B)\cap C&=(A\cap C)\cup(B\cap C),\\ (A\cap B)\cup C&=(A\cup C)\cap(B\cup C). \end{aligned} \]

Beim Übergang zum Komplement werden Vereinigung und Schnitt miteinander vertauscht.

Satz 2.3 (Komplement- und De-Morgan-Gesetze). Für \(A,B\subseteq E\) gilt

\[ \begin{aligned} A\cup\emptyset&=A, & A\cap E&=A,\\ A\cup\overline A&=E, & A\cap\overline A&=\emptyset,\\ \overline{\overline A}&=A. \end{aligned} \]

Außerdem gelten die De-Morgan-Gesetze

\[ \overline{A\cup B}=\overline A\cap\overline B, \qquad \overline{A\cap B}=\overline A\cup\overline B. \tag{2.1}\]

Gleichung 2.1 zeigt: Beim Komplementieren werden Vereinigung und Durchschnitt vertauscht.

Beispiel: Ein De-Morgan-Gesetz elementweise verstehen

Warum gilt \(\overline{A\cup B}=\overline A\cap\overline B\)?

Für jedes \(x\in E\) gilt

\[ \begin{aligned} x\in\overline{A\cup B} &\Longleftrightarrow x\notin A\cup B\\ &\Longleftrightarrow (x\notin A)\wedge(x\notin B)\\ &\Longleftrightarrow x\in\overline A\cap\overline B. \end{aligned} \]

Beide Mengen enthalten daher genau dieselben Elemente.

Zusammenfassung

  • Durchschnitt, Vereinigung, Differenz und Komplement werden über Bedingungen an die enthaltenen Elemente definiert.
  • Die Differenz ist nicht kommutativ; ihr Ergebnis hängt von der Reihenfolge ab.
  • Die Mengenoperationen erfüllen analoge Rechengesetze wie \(\wedge\), \(\vee\) und die Negation in der Aussagenlogik.
  • Mengenidentitäten lassen sich durch Umformen oder durch beidseitige Inklusion beweisen.