Diskrete Strukturen - Exam.pdf

Aufgabe 1)

Teilweise und totale Ordnungen:Teilweise und totale Ordnungen beschreiben Beziehungen zwischen Elementen einer Menge, wobei teilweise Ordnungen nicht notwendigerweise jedes Paar von Elementen vergleichen können, während totale Ordnungen dies tun.

• Teilordnung: Eine Relation \( \leq \) auf einer Menge \( M \) ist eine Teilordnung, wenn sie reflexiv, antisymmetrisch und transitiv ist.
• Totale Ordnung: Eine Relation \( \leq \) auf einer Menge \( M \) ist eine totale Ordnung, wenn sie eine Teilordnung ist und zusätzlich für alle \( a, b \in M \) gilt: \( a \leq b \) oder \( b \leq a \).
• Beispiel: \( (\mathbb{N}, \leq) \) ist eine totale Ordnung.

a)

Gegeben sei die Menge \(A = \{1, 2, 3\}\) mit der Relation \(R = \{(1,1), (2,2), (3,3), (1,2), (2,3)\}\). Zeige durch Prüfung der definierenden Eigenschaften, ob \(R\) eine Teilordnung auf \(A\) ist. Gehe dabei systematisch vor und überprüfe Reflexivität, Antisymmetrie und Transitivität.

Lösung:

Gegeben sei die Menge A = \( \{1, 2, 3\} \) mit der Relation R = \( \{(1,1), (2,2), (3,3), (1,2), (2,3)\} \). Zeige durch Prüfung der definierenden Eigenschaften, ob R eine Teilordnung auf A ist. Um dies zu überprüfen, müssen wir die drei Eigenschaften Reflexivität, Antisymmetrie und Transitivität systematisch prüfen:

• Reflexivität: Eine Relation R ist reflexiv, wenn für alle a in A gilt: \( aRa \). Das bedeutet, dass jedes Element der Menge mit sich selbst in Relation stehen muss.In R sehen wir, dass (1,1), (2,2) und (3,3) enthalten sind. Somit ist R reflexiv, da jedes Element in A mit sich selbst in Relation steht.
• Antisymmetrie: Eine Relation R ist antisymmetrisch, wenn für alle a, b in A gilt: Wenn \( aRb \) und \( bRa \), dann muss \( a = b \) sein.In R sehen wir keine Paare der Form \( (a,b) \) und \( (b,a) \), außer den Reflexivitätspaaren \( (1,1) \), \( (2,2) \), und \( (3,3) \). Somit ist R antisymmetrisch.
• Transitivität: Eine Relation R ist transitiv, wenn für alle a, b, c in A gilt: Wenn \( aRb \) und \( bRc \) , dann muss auch \( aRc \) sein.In R haben wir folgende Paare zu prüfen:
  • \( (1,2) \) und \( (2,3) \) führen zu \( (1,3) \). Aber \( (1,3) \) ist nicht in R, daher ist R nicht transitiv.
  Somit ist R nicht transitiv, und daher ist die Relation R keine Teilordnung auf A.

Fazit: Die Relation R erfüllt die Eigenschaften der Reflexivität und Antisymmetrie, jedoch nicht die Transitivität. Daher ist R keine Teilordnung auf A.

b)

Sei \(B = \{a, b, c\}\). Definiere eine totale Ordnung \(\leq\) auf der Menge \(B\). Begründe, warum Deine Definition eine totale Ordnung ist.

Lösung:

Sei B = \( \{a, b, c\} \). Definiere eine totale Ordnung \( \leq \) auf der Menge B.

• Um eine totale Ordnung zu definieren, müssen wir eine Relation \( \leq \) finden, die reflexiv, antisymmetrisch, transitiv ist und zusätzlich für jedes Paar \(a, b\) in \(B\) gilt: \(a \leq b\) oder \(b \leq a\). Ein möglicher Weg ist eine lineare Ordnung, z.B.
• Definiere die Relation \( \leq \) folgendermaßen: \( a \leq b \leq c \).

Nun begründen wir, warum diese Definition eine totale Ordnung ist:

• Reflexivität: Jedes Element in \(B\) steht in Relation zu sich selbst. Das heißt, \(a \leq a\), \(b \leq b\), und \(c \leq c\).
• Antisymmetrie: Wenn \(a \leq b\) und \(b \leq a\), dann muss \(a = b\). Da unsere Relation linear ist, können wir keine zwei verschiedenen Elemente \(x\) und \(y\) haben, für die beide \(x \leq y\) und \(y \leq x \) zutreffen, es sei denn \(x = y \).
• Transitivität: Wenn \(a \leq b\) und \(b \leq c\), dann muss \(a \leq c\). In unserer Relation gilt dies für Schritte wie \(a \leq b\) und \(b \leq c\), daher auch \(a \leq c\).
• Totale Ordnung: Für jedes Paar \(a,b\) in \(B\) gilt entweder \(a \leq b\) oder \(b \leq a \). In unserem Beispiel ist das offensichtlich, da wir eine lineare Reihenfolge haben: \(a \leq b \leq c\).

Fazit: Die Definition \(a \leq b \leq c\) erfüllt alle Bedingungen einer totalen Ordnung. Daher ist \( \leq \) eine totale Ordnung auf der Menge \(B\).

Aufgabe 2)

Gegeben ist ein ungerichteter, ungewichteter Graph G mit den Knoten V = {A, B, C, D, E, F, G} und den Kanten E = {(A,B), (A,D), (B,C), (B,E), (C,F), (D,E), (E,G)}.

a)

Führe eine Tiefensuche (DFS) auf dem gegebenen Graphen G durch, startend von Knoten A. Gib die Reihenfolge der Knoten an, wie sie besucht werden.

Lösung:

Um eine Tiefensuche (DFS) durchzuführen, können wir iterative oder rekursive Methoden verwenden. Hier werden wir die rekursive Methode einsetzen. Wir beginnen mit dem Startknoten A und folgen systematisch allen Verzweigungen, bevor wir zu einem vorherigen Punkt zurückkehren.

• 1. Starte bei Knoten A
• 2. Gehe zu Knoten B von A aus
• 3. Von B gehe zu Knoten C
• 4. Von C gehe zu Knoten F (da dies der nächste unbesuchte Knoten ist)
• 5. Da F keine weiteren unbesuchten Nachbarn hat, kehre zu C und dann zu B zurück
• 6. Von B gehe zu Knoten E
• 7. Von E gehe zu G (da dies der nächste unbesuchte Knoten ist)
• 8. Da G keine weiteren unbesuchten Nachbarn hat, kehre zu E und dann zu B und dann zu A zurück
• 9. Von A gehe zu Knoten D (da dies der nächste unbesuchte Knoten ist, wenn wieder bei A angekommen)
• 10. Von D gehe zu Knoten E, aber E wurde bereits besucht, also höre auf

Die Reihenfolge der besuchten Knoten bei der Tiefensuche (DFS) ist somit:

• A
• B
• C
• F
• E
• G
• D

b)

Führe eine Breitensuche (BFS) auf dem gegebenen Graphen G durch, startend von Knoten A. Gib die Reihenfolge der Knoten an, wie sie besucht werden.

Lösung:

Um eine Breitensuche (BFS) durchzuführen, verwenden wir eine Warteschlange. Wir beginnen mit dem Startknoten A und besuchen dann schrittweise alle benachbarten Knoten. Danach besuchen wir die Nachbarn dieser Knoten und fahren so fort.

• 1. Starte bei Knoten A und füge A zur Warteschlange hinzu
• 2. Besuche Knoten A und markiere ihn als besucht
• 3. Füge alle unbesuchten Nachbarn von A zur Warteschlange hinzu (B, D)
• 4. Besuche den nächsten Knoten in der Warteschlange, B, und markiere ihn als besucht
• 5. Füge alle unbesuchten Nachbarn von B zur Warteschlange hinzu (C, E)
• 6. Besuche den nächsten Knoten in der Warteschlange, D, und markiere ihn als besucht
• 7. Füge alle unbesuchten Nachbarn von D zur Warteschlange hinzu (E, aber E ist schon in der Warteschlange)
• 8. Besuche den nächsten Knoten in der Warteschlange, C, und markiere ihn als besucht
• 9. Füge alle unbesuchten Nachbarn von C zur Warteschlange hinzu (F)
• 10. Besuche den nächsten Knoten in der Warteschlange, E, und markiere ihn als besucht
• 11. Füge alle unbesuchten Nachbarn von E zur Warteschlange hinzu (G)
• 12. Besuche den nächsten Knoten in der Warteschlange, F, und markiere ihn als besucht
• 13. Füge alle unbesuchten Nachbarn von F zur Warteschlange hinzu (Aber F hat keine unbesuchten Nachbarn)
• 14. Besuche den letzten Knoten in der Warteschlange, G, und markiere ihn als besucht
• 15. Füge alle unbesuchten Nachbarn von G zur Warteschlange hinzu (Aber G hat keine unbesuchten Nachbarn)

Die Reihenfolge der besuchten Knoten bei der Breitensuche (BFS) ist somit:

• A
• B
• D
• C
• E
• F
• G

c)

Gib die Adjazenzmatrix und die Adjazenzliste des Graphen G an. Wie ändert sich die Komplexität der DFS und BFS bezogen auf die Darstellungsform (Adjazenzmatrix vs. Adjazenzliste)?

Lösung:

Um die Adjazenzmatrix und die Adjazenzliste des gegebenen Graphen zu erstellen, fangen wir mit der Adjazenzmatrix an:

Adjazenzmatrix

In der Adjazenzmatrix wird eine 1 gesetzt, wenn eine Kante zwischen den Knoten existiert, und eine 0, wenn keine Kante vorhanden ist.

    A B C D E F G  A 0 1 0 1 0 0 0  B 1 0 1 0 1 0 0  C 0 1 0 0 0 1 0  D 1 0 0 0 1 0 0  E 0 1 0 1 0 0 1  F 0 0 1 0 0 0 0  G 0 0 0 0 1 0 0   

Adjazenzliste

Die Adjazenzliste listet für jeden Knoten alle direkt verbundenen Nachbarn auf.

  A: B, D  B: A, C, E  C: B, F  D: A, E  E: B, D, G  F: C  G: E   

Komplexität der DFS und BFS

DFS (Tiefensuche)

• Adjazenzmatrix: Die Komplexität der Tiefensuche beträgt O(V^2), da jeder Knoten und jede Kante berücksichtigt wird.
• Adjazenzliste: Die Komplexität der Tiefensuche beträgt O(V + E), da jeder Knoten und jede Kante einmal besucht wird.

BFS (Breitensuche)

• Adjazenzmatrix: Die Komplexität der Breitensuche beträgt O(V^2) aus den gleichen Gründen wie bei der Tiefensuche.
• Adjazenzliste: Die Komplexität der Breitensuche beträgt O(V + E), ebenfalls aus den gleichen Gründen wie bei der Tiefensuche.

d)

Nutze die Tiefensuche (DFS), um zu bestimmen, ob der Graph G Zyklen enthält. Falls ja, gib einen gefundenen Zyklus an.

Lösung:

Um zu bestimmen, ob der Graph G Zyklen enthält, können wir die Tiefensuche (DFS) verwenden. Dabei behalten wir die besuchten Knoten im Blick und prüfen bei jedem Schritt, ob wir auf einen Knoten stoßen, der bereits auf dem aktuellen Pfad liegt. Falls ja, haben wir einen Zyklus gefunden. Hier ist der Algorithmus in Schritten:

Algorithmus für Zyklensuche mittels DFS:

• Definiere einen Stack oder eine rekursive Funktion, um die Knoten zu besuchen.
• Verwende ein Array oder eine Liste, um besuchte Knoten zu markieren.
• Habe zusätzlich ein Array oder eine Liste, um Knoten zu markieren, die Teil des aktuellen Pfades sind.
• Bei Besuch eines Knotens, füge ihn zum aktuellen Pfad hinzu und markiere ihn als besucht.
• Für jeden Nachbarn dieses Knotens:
• Wenn der Nachbar noch nicht besucht wurde, rufe die DFS-Funktion rekursiv für diesen Nachbarn auf.
• Wenn der Nachbar bereits auf dem aktuellen Pfad ist, wurde ein Zyklus gefunden.
• Wenn alle Nachbarn besucht wurden und kein Zyklus gefunden wurde, entferne den Knoten vom aktuellen Pfad.

Anwendung auf den gegebenen Graphen G:

• Starte bei Knoten A und beginne die Tiefensuche.
• Besuche Knoten B von A aus. Markiere A und B als besucht und Teil des aktuellen Pfads.
• Von B aus gehe zu C, markiere C als besucht und Teil des aktuellen Pfads.
• Von C aus gehe zu F, markiere F als besucht und Teil des aktuellen Pfads.
• F hat keine weiteren Nachbarn, also kehre zu C, dann zu B zurück.
• Von B gehe zu E, markiere E als besucht und Teil des aktuellen Pfads.
• Von E aus gehe zu G, markiere G als besucht und Teil des aktuellen Pfads.
• G hat keine weiteren Nachbarn, also kehre zu E, dann zu B, dann zu A zurück.
• Von A gehe zu D, markiere D als besucht und Teil des aktuellen Pfads.
• Von D gehe zu E. Da E bereits besucht und ein Teil des aktuellen Pfades ist, haben wir einen Zyklus gefunden.

Ein gefundener Zyklus ist daher: A -> B -> E -> D -> A

Aufgabe 3)

Betrachte die folgende Behauptung: Für jede natürliche Zahl n gilt, dass die Summe der ersten n geraden Zahlen gleich n(n + 1) ist.

b)

Beweise die Behauptung durch den Widerspruchsbeweis, indem Du davon ausgehst, dass die Behauptung falsch ist.

Lösung:

Widerspruchsbeweis der Behauptung:

Wir wollen die Behauptung beweisen, dass für jede natürliche Zahl n die Summe der ersten n geraden Zahlen gleich n(n + 1) ist, indem wir annehmen, dass diese Behauptung falsch ist und daraus einen Widerspruch ableiten.

• Angenommen, die Behauptung ist falsch. Das bedeutet, dass die Summe der ersten n geraden Zahlen nicht gleich n(n + 1) ist.

Es existiert also mindestens eine natürliche Zahl n, für die gilt:

2 + 4 + 6 + ... + 2n ≠ n(n + 1)

• Betrachten wir die Summe der ersten n geraden Zahlen:

S = 2 + 4 + 6 + ... + 2n

• Diese Summe kann man umschreiben als:

S = 2(1 + 2 + 3 + ... + n)

• Es ist bekannt, dass die Summe der ersten n natürlichen Zahlen gleich \(\frac{n(n + 1)}{2}\) ist.

Setzen wir dies in unsere Summe ein, erhalten wir:

S = 2 \times \frac{n(n + 1)}{2}

S = n(n + 1)

• Damit haben wir gezeigt, dass die Summe der ersten n geraden Zahlen tatsächlich gleich n(n + 1) ist. Dies steht im Widerspruch zu unserer Annahme, dass die Behauptung falsch ist.
• Da unsere Annahme zu einem Widerspruch geführt hat, muss die ursprüngliche Behauptung richtig sein.

Somit haben wir durch Widerspruch gezeigt, dass die Summe der ersten n geraden Zahlen tatsächlich n(n + 1) ist.

c)

Formuliere zunächst die Basisbehauptung und führe dann den Induktionsbeweis zur Bestätigung der Behauptung.

Lösung:

Induktionsbeweis der Behauptung:

Wir wollen die Behauptung beweisen, dass für jede natürliche Zahl n die Summe der ersten n geraden Zahlen gleich n(n + 1) ist, mittels eines vollständigen Induktionsbeweises.

Hier sind die Schritte, die wir dazu benötigen:

• Basisbehauptung: Für n = 1 gilt, dass die Summe der ersten n geraden Zahlen gleich n(n + 1) ist.
  • Die erste gerade Zahl ist 2.
  • Die Summe der ersten 1 geraden Zahl ist also 2.
  • Der Ausdruck n(n + 1) ergibt für n = 1:

    1(1 + 1) = 1 * 2 = 2

  Also ist die Basisbehauptung wahr.

• Induktionsschritt: Angenommen, die Behauptung sei für eine natürliche Zahl k wahr, also gilt:

  2 + 4 + 6 + ... + 2k = k(k + 1)

  Wir müssen nun zeigen, dass die Behauptung auch für k + 1 wahr ist, d.h.:

  2 + 4 + 6 + ... + 2k + 2(k + 1) = (k + 1)((k + 1) + 1)

  Setzen wir die Induktionsannahme ein und fügen wir den nächsten Summanden hinzu:
  • Nach der Induktionsannahme ist die Summe der ersten k geraden Zahlen:

    2 + 4 + 6 + ... + 2k = k(k + 1)

  • Nun addieren wir die nächste gerade Zahl, 2(k + 1), zur Summe hinzu:

    k(k + 1) + 2(k + 1)

  • Faktorisieren wir diesen Ausdruck:

    (k + 1)(k + 2)

    Nach dem Distributivgesetz ergibt sich dies als:

    k(k + 1) + 2(k + 1) = (k + 1)(k + 2)

  Also stimmt unsere summierte Formel ebenfalls für k + 1:

Damit ist die Behauptung auch für k + 1 wahr, wenn sie für k wahr ist.

• Schlussfolgerung: Da die Basisbehauptung wahr ist und die Induktionsannahme für k zur Wahrheitsdefinition der Formel für k + 1 führt, haben wir durch vollständige Induktion gezeigt, dass:

Für jede natürliche Zahl n die Summe der ersten n geraden Zahlen gleich n(n + 1) ist.

d)

Erkläre anhand des zuvor durchgeführten Induktionsbeweises das Prinzip der vollständigen Induktion und beschreibe, warum es einen ausreichenden Beweis für die gegebene Behauptung liefert.

Lösung:

Das Prinzip der vollständigen Induktion:

Die vollständige Induktion ist ein mächtiges Beweisverfahren in der Mathematik, das insbesondere bei Behauptungen über natürliche Zahlen eingesetzt wird. Das Verfahren besteht aus zwei Hauptschritten: der Basisbehauptung und dem Induktionsschritt.

• Basisbehauptung: Zunächst wird gezeigt, dass die Behauptung für eine Anfangswert (meistens n = 1) wahr ist. In unserem Fall haben wir gezeigt, dass für n = 1 die Summe der ersten geraden Zahlen gleich n(n + 1) ist:

2 = 1 * (1 + 1) = 2

• Da dies wahr ist, ist die Basisbehauptung erfüllt.

• Induktionsschritt: Nun nehmen wir an, dass die Behauptung für eine natürliche Zahl k wahr ist. Diese Annahme nennt man Induktionsannahme. Für unser Beispiel bedeutet das:

2 + 4 + 6 + ... + 2k = k(k + 1)

• Im nächsten Schritt zeigen wir, dass die Behauptung auch für k + 1 gilt. Das bedeutet:

2 + 4 + 6 + ... + 2k + 2(k + 1) = (k + 1)((k + 1) + 1)

• Durch Umformen und Faktorisieren der Induktionsannahme haben wir gezeigt, dass dies tatsächlich so ist:

k(k + 1) + 2(k + 1) = (k + 1)(k + 2)

Damit haben wir gezeigt, dass die Behauptung auch für k + 1 wahr ist, wenn sie für k wahr ist.

Warum ist dies ein ausreichender Beweis?

• Das Prinzip der vollständigen Induktion liefert einen lückenlosen Beweis, weil es alle natürlichen Zahlen abdeckt. Indem wir die Basisbehauptung zeigen, haben wir einen Startpunkt. Der Induktionsschritt zeigt dann, dass jede Zahl, für die die Behauptung gilt, die Behauptung auch für die nächste Zahl mitzieht.
• Da wir beide Schritte erfolgreich durchgeführt haben, ist die Behauptung für alle natürlichen Zahlen n bewiesen.

Im vorliegenden Beispiel haben wir bewiesen, dass die Summe der ersten n geraden Zahlen gleich n(n + 1) ist. Dies zeigt das Prinzip der vollständigen Induktion klar und effektiv.

Aufgabe 4)

• Kartesisches Produkt: Für Mengen A und B ist das Kartesische Produkt definiert als: \[ A \times B = \{ (a, b) | a \in A, b \in B \} \]
• Potenzmenge: Die Potenzmenge einer Menge A ist die Menge aller Teilmengen von A: \[ \mathcal{P}(A) = \{ B | B \subseteq A \} \]

a)

Gegeben seien die Mengen \(A = \{1, 2\}\) und \(B = \{x, y\}\). Berechne das kartesische Produkt \(A \times B\).

Lösung:

• Kartesisches Produkt: Für Mengen A und B ist das Kartesische Produkt definiert als: \( A \times B = \{ (a, b) \ | \ a \in A, \ b \in B \} \)
• Potenzmenge: Die Potenzmenge einer Menge A ist die Menge aller Teilmengen von A: \( \mathcal{P}(A) = \{ B \ | \ B \subseteq A \} \)

Berechne das kartesische Produkt \(A \times B\) für die Mengen \(A = \{1, 2\}\) und \(B = \{ x, y \}\).

• Um das kartesische Produkt \(A \times B\) zu berechnen, nehmen wir jedes Element aus Menge A und kombinieren es mit jedem Element aus Menge B.
• Die Menge A hat die Elemente: \( 1 \) und \( 2 \).
• Die Menge B hat die Elemente: \( x \) und \( y \).

Dies führt zu den folgenden Paaren:

• \( (1, x) \)
• \( (1, y) \)
• \( (2, x) \)
• \( (2, y) \)

Daher ist das kartesische Produkt \( A \times B \) gegeben durch: \( A \times B = \{ (1, x), (1, y), (2, x), (2, y) \} \)

b)

Bestimme die Potenzmenge von \(B\) und berechne anschließend das kartesische Produkt \(P(A) \times P(B)\), wobei \(P\) die Potenzmenge einer Menge darstellt.

Lösung:

• Kartesisches Produkt: Für Mengen A und B ist das Kartesische Produkt definiert als: \( A \times B = \{ (a, b) \ | \ a \in A, \ b \in B \} \)
• Potenzmenge: Die Potenzmenge einer Menge A ist die Menge aller Teilmengen von A: \( \mathcal{P}(A) = \{ B \ | \ B \subseteq A \} \)

Bestimme die Potenzmenge von \( B \) und berechne anschließend das kartesische Produkt \( \mathcal{P}(A) \times \mathcal{P}(B) \), wobei \( \mathcal{P} \) die Potenzmenge einer Menge darstellt.

• Gegeben sei die Menge \( B = \{ x, y \} \).

1. Bestimme die Potenzmenge von \( B \): Die Potenzmenge von \( B \) umfasst alle Teilmengen von \( B \). Folgende Teilmengen gehören dazu:

• Leere Menge: \( \emptyset \)
• Ein-Element-Mengen: \( \{ x \} \), \( \{ y \} \)
• Zwei-Element-Menge: \( \{ x, y \} \)

Somit ist die Potenzmenge von \( B \), also \( \mathcal{P}(B) \), gegeben durch: \( \mathcal{P}(B) = \{ \emptyset, \{ x \}, \{ y \}, \{ x, y \} \} \)

• Gegeben sei die Menge \( A = \{ 1, 2 \} \).

2. Bestimme die Potenzmenge von \( A \): Die Potenzmenge von \( A \) umfasst alle Teilmengen von \( A \). Folgende Teilmengen gehören dazu:

• Leere Menge: \( \emptyset \)
• Ein-Element-Mengen: \( \{ 1 \} \), \( \{ 2 \} \)
• Zwei-Element-Menge: \( \{ 1, 2 \} \)

Somit ist die Potenzmenge von \( A \), also \( \mathcal{P}(A) \), gegeben durch: \( \mathcal{P}(A) = \{ \emptyset, \{ 1 \}, \{ 2 \}, \{ 1, 2 \} \} \) 3. Berechne das kartesische Produkt \( \mathcal{P}(A) \times \mathcal{P}(B) \): Das kartesische Produkt \( \mathcal{P}(A) \times \mathcal{P}(B) \) umfasst alle möglichen geordneten Paare, wobei das erste Element aus der Potenzmenge von \( A \) und das zweite Element aus der Potenzmenge von \( B \) stammt. Dies führt zu den folgenden Paaren:

• \( (\emptyset, \emptyset) \)
• \( (\emptyset, \{ x \}) \)
• \( (\emptyset, \{ y \}) \)
• \( (\emptyset, \{ x, y \}) \)
• \( (\{ 1 \}, \emptyset) \)
• \( (\{ 1 \}, \{ x \}) \)
• \( (\{ 1 \}, \{ y \}) \)
• \( (\{ 1 \}, \{ x, y \}) \)
• \( (\{ 2 \}, \emptyset) \)
• \( (\{ 2 \}, \{ x \}) \)
• \( (\{ 2 \}, \{ y \}) \)
• \( (\{ 2 \}, \{ x, y \}) \)
• \( (\{ 1, 2 \}, \emptyset) \)
• \( (\{ 1, 2 \}, \{ x \}) \)
• \( (\{ 1, 2 \}, \{ y \}) \)
• \( (\{ 1, 2 \}, \{ x, y \}) \)

Daher ist das kartesische Produkt \( \mathcal{P}(A) \times \mathcal{P}(B) \) gegeben durch: \( \mathcal{P}(A) \times \mathcal{P}(B) = \{ (\emptyset, \emptyset), (\emptyset, \{ x \}), (\emptyset, \{ y \}), (\emptyset, \{ x, y \}), (\{ 1 \}, \emptyset), (\{ 1 \}, \{ x \}), (\{ 1 \}, \{ y \}), (\{ 1 \}, \{ x, y \}), (\{ 2 \}, \emptyset), (\{ 2 \}, \{ x \}), (\{ 2 \}, \{ y \}), (\{ 2 \}, \{ x, y \}), (\{ 1, 2 \}, \emptyset), (\{ 1, 2 \}, \{ x \}), (\{ 1, 2 \}, \{ y \}), (\{ 1, 2 \}, \{ x, y \}) \} \)