Diskrete Mathematik - Exam.pdf

Aufgabe 1)

Betrachte einen Graphen, bei dem die Knoten die Städte eines Landes und die Kanten die Straßen zwischen diesen Städten darstellen. Je nach Typ der Verbindung kann der Graph entweder gerichtet oder ungerichtet sein. Ein ungerichteter Graph bedeutet, dass die Straße in beide Richtungen befahrbar ist, während ein gerichteter Graph zeigt, dass die Straße nur in einer Richtung befahrbar ist.

a)

Modelliere dieses Straßennetzwerk als Adjazenzmatrix sowohl für die ungerichtete als auch für die gerichtete Version des Graphen. Angenommen, es gibt vier Städte A, B, C und D mit den folgenden Verbindungen:

• Von A nach B und B nach A (bidirektional)
• Von A nach C
• Von C nach D und D nach C (bidirektional)

Lösung:

Adjazenzmatrix für das Straßennetzwerk

Betrachte die Städte A, B, C und D in einem Netzwerk von Straßenverbindungen. Wir erstellen sowohl die ungerichtete als auch die gerichtete Adjazenzmatrix für die gegebenen Verbindungen.

Ungerichteter Graph

In einem ungerichteten Graphen sind die Verbindungen bidirektional. Die Adjazenzmatrix ist symmetrisch entlang der Diagonale.

Hier sind die gegebenen Verbindungen für den ungerichteten Graphen:

• Von A nach B und B nach A (bidirektional)
• Von A nach C
• Von C nach D und D nach C (bidirektional)

Die Adjazenzmatrix für den ungerichteten Graphen ist wie folgt:

  A B C DA 0 1 1 0B 1 0 0 0C 1 0 0 1D 0 0 1 0

Gerichteter Graph

In einem gerichteten Graphen sind die Verbindungen nur in einer Richtung möglich. Die Adjazenzmatrix ist nicht unbedingt symmetrisch.

Hier sind die gegebenen Verbindungen für den gerichteten Graphen:

• Von A nach B und B nach A
• Von A nach C
• Von C nach D und D nach C

Die Adjazenzmatrix für den gerichteten Graphen ist wie folgt:

  A B C DA 0 1 1 0B 1 0 0 0C 0 0 0 1D 0 0 1 0

Bitte beachte, dass die Einträge in den Matrizen entweder 1 (wenn eine Verbindung zwischen den Städten existiert) oder 0 (wenn keine Verbindung existiert) sind.

b)

Bestimme den Grad jedes Knotens sowohl im gerichteten als auch im ungerichteten Graphen. Erläutere den Unterschied zwischen dem Grad eines Knotens in einem gerichteten und einem ungerichteten Graphen. Nutze die Adjazenzmatrix, die Du im ersten Teil der Aufgabe erstellt hast.

Lösung:

Berechnung des Knotengrades

Der Grad eines Knotens in einem Graphen gibt die Anzahl der Kanten an, die zu diesem Knoten führen. Im gerichteten Graphen unterscheidet man zwischen dem Eingangsgrad (Anzahl der einwärts gerichteten Kanten) und dem Ausgangsgrad (Anzahl der auswärts gerichteten Kanten).

Ungerichteter Graph

Im ungerichteten Graphen ist der Grad eines Knotens einfach die Anzahl der Verbindungen, die der Knoten zu anderen Knoten hat.

Adjazenzmatrix für den ungerichteten Graphen:

  A B C DA 0 1 1 0B 1 0 0 0C 1 0 0 1D 0 0 1 0

Grad der Knoten im ungerichteten Graphen:

• Grad von A: 2 (Verbindungen mit B und C)
• Grad von B: 1 (Verbindung mit A)
• Grad von C: 2 (Verbindungen mit A und D)
• Grad von D: 1 (Verbindung mit C)

Gerichteter Graph

Im gerichteten Graphen betrachtet man sowohl den Eingangsgrad als auch den Ausgangsgrad:

• Eingangsgrad: Anzahl der Kanten, die in den Knoten hineingehen.
• Ausgangsgrad: Anzahl der Kanten, die aus dem Knoten herausgehen.

Adjazenzmatrix für den gerichteten Graphen:

  A B C DA 0 1 1 0B 1 0 0 0C 0 0 0 1D 0 0 1 0

Eingangs- und Ausgangsgrad der Knoten im gerichteten Graphen:

• Knoten A:
  • Eingangsgrad: 1 (von B)
  • Ausgangsgrad: 2 (zu B und C)
• Knoten B:
  • Eingangsgrad: 1 (von A)
  • Ausgangsgrad: 1 (zu A)
• Knoten C:
  • Eingangsgrad: 1 (von A)
  • Ausgangsgrad: 1 (zu D)
• Knoten D:
  • Eingangsgrad: 1 (von C)
  • Ausgangsgrad: 1 (zu C)

Insgesamt zeigt sich, dass der Unterschied zwischen dem Grad eines Knotens im gerichteten und ungerichteten Graphen darin besteht, dass im gerichteten Graphen der Grad in zwei Teile (Eingangs- und Ausgangsgrad) aufgeteilt wird, während im ungerichteten Graphen der Grad die Gesamtanzahl der Verbindungen darstellt.

Aufgabe 2)

Betrachte einen Universitätscampus, auf dem drei verschiedene Clubs existieren: Der Mathematik-Club (M), der Informatik-Club (I) und der Physik-Club (P). Die Mitgliederzahlen sind wie folgt gegeben:

• |M| = 50
• |I| = 60
• |P| = 40

• |M ∩ I| = 20
• |M ∩ P| = 10
• |I ∩ P| = 15
• |M ∩ I ∩ P| = 5

a)

Berechne alle einzelnen Zweifach- und Dreifachschnittmengen von M, I und P, die im Kontext angegeben sind.

Lösung:

Um die Gesamtzahl der Studenten zu berechnen, die in mindestens einem der drei Clubs Mitglied sind, nutzen wir das Inklusions-Exklusions-Prinzip. Zuerst listen wir die gegebenen Einzelmengen und ihre Schnittmengen auf:

• Die Anzahl der Mitglieder im Mathematik-Club \( (M) \) ist \( |M| = 50 \).
• Die Anzahl der Mitglieder im Informatik-Club \( (I) \) ist \( |I| = 60 \).
• Die Anzahl der Mitglieder im Physik-Club \( (P) \) ist \( |P| = 40 \).

Die gegebenen Schnittmengen sind:

• Die Mitglieder sowohl im Mathematik-Club als auch im Informatik-Club: \( |M \cap I| = 20 \).
• Die Mitglieder sowohl im Mathematik-Club als auch im Physik-Club: \( |M \cap P| = 10 \).
• Die Mitglieder sowohl im Informatik-Club als auch im Physik-Club: \( |I \cap P| = 15 \).
• Die Mitglieder in allen drei Clubs: \( |M \cap I \cap P| = 5 \).

Diese Schnittmengen sind korrekt und helfen uns dabei, die Gesamtzahl der Studenten, die in mindestens einem der Clubs Mitglied sind, zu berechnen.

b)

Benutze das Inklusions-Exklusions-Prinzip, um die Gesamtzahl der Studenten zu berechnen, die in mindestens einem der drei Clubs Mitglied sind.

Lösung:

Um die Gesamtzahl der Studenten zu berechnen, die in mindestens einem der drei Clubs Mitglied sind, verwenden wir das Inklusions-Exklusions-Prinzip. Die Formel dafür lautet:

• \[|M \cup I \cup P| = |M| + |I| + |P| - |M \cap I| - |M \cap P| - |I \cap P| + |M \cap I \cap P|\]

Nun setzen wir die gegebenen Werte ein:

• \[|M| = 50\]
• \[|I| = 60\]
• \[|P| = 40\]
• \[|M \cap I| = 20\]
• \[|M \cap P| = 10\]
• \[|I \cap P| = 15\]
• \[|M \cap I \cap P| = 5\]

Wir wenden die Werte in der Formel an:

• \[|M \cup I \cup P| = 50 + 60 + 40 - 20 - 10 - 15 + 5\]

Nach der Berechnung erhalten wir:

• \[|M \cup I \cup P| = 50 + 60 + 40 - 20 - 10 - 15 + 5 = 110\]

Also, die Gesamtzahl der Studenten, die in mindestens einem der drei Clubs Mitglied sind, beträgt 110.

Aufgabe 3)

Gegeben sei die boolesche Funktion f mit den Variablen A, B und C:

'f(A, B, C) = (A \land eg B) \lor (eg A \land B \land C)'

Bearbeite die folgenden Teilaufgaben:

Aufgabe 4)

Betrachte die folgenden Mengen:

• Menge A: \(\{1, 2, 3, 4, 5\}\)
• Menge B: \(\{ x \, | \, x \in \mathbb{N} \text{ und } x \text{ ist gerade} \}\)
• Menge C: \(\{ x \, | \, x = k^2 \text{ für } k \in \mathbb{N} \}\)
• Menge D: \(\mathbb{Z}\)

b)

• Für die Mengen A und C: Bestimme die Mächtigkeit der Mengen.

Lösung:

• Menge A: Menge A ist \(\{1, 2, 3, 4, 5\}\).Die Mächtigkeit (Kardinalität) dieser Menge ist die Anzahl der Elemente in der Menge. Da Menge A genau fünf Elemente enthält, ist die Mächtigkeit von Menge A gleich 5.
• Menge C: Menge C ist \(\{ x \, | \, x = k^2 \text{ für } k \in \mathbb{N} \}\).Die Mächtigkeit dieser Menge ist unendlich, da es unendlich viele natürliche Zahlen \((k)\) gibt und somit unendlich viele Quadratzahlen \((k^2)\).Da es kein Ende für die Menge der natürlichen Zahlen gibt, wird auch die Menge der Quadratzahlen unendlich sein. Deshalb hat Menge C die Mächtigkeit des unendlichen Kardinals \((\aleph_0)\).

c)

• Überprüfe, ob die Menge B abzählbar unendlich oder überabzählbar ist. Begründe Deine Antwort mit geeigneten Argumenten und Beispielen.

Lösung:

• Menge B: Menge B ist \(\{ x \, | \, x \in \mathbb{N} \text{ und } x \text{ ist gerade} \}\).Um zu überprüfen, ob diese Menge abzählbar unendlich oder überabzählbar ist, müssen wir untersuchen, ob sie in eine bijektive Beziehung mit den natürlichen Zahlen \((\mathbb{N})\) gebracht werden kann.

• Eine Menge ist abzählbar unendlich, wenn ihre Elemente in einer eineindeutigen Beziehung zu den natürlichen Zahlen stehen. Mit anderen Worten, es muss eine Funktion existieren, die jedem Element der Menge eine eindeutige natürliche Zahl zuordnet und umgekehrt.

• Betrachten wir die Menge der geraden natürlichen Zahlen:

• \(B = \{ 2, 4, 6, 8, 10, \ldots \}\)

• Wir können diese Menge einfach so mit den natürlichen Zahlen paaren:

• \(1 \leftrightarrow 2\)
• \(2 \leftrightarrow 4\)
• \(3 \leftrightarrow 6\)
• \(4 \leftrightarrow 8\)
• \(5 \leftrightarrow 10\)

• Die allgemeine Form dieser Paarung wäre \(n \leftrightarrow 2n\), wobei \(n\) eine natürliche Zahl ist. Diese Funktion ist bijektiv, da:

• Für jede natürliche Zahl \(n\) gibt es eine eindeutige gerade Zahl \(2n\).
• Für jede gerade Zahl \(2n\) gibt es eine eindeutige natürliche Zahl \(n\).

• Da eine bijektive Zuordnung zwischen den natürlichen Zahlen \((\mathbb{N})\) und den geraden natürlichen Zahlen existiert, ist Menge B abzählbar unendlich.

• Daher ist die Menge B abzählbar unendlich und nicht überabzählbar.

d)

• Definiere eine neue Menge E als Vereinigung der Mengen A und B. Ist diese Menge E endlich oder unendlich? Begründe Deine Antwort unter Berücksichtigung der Eigenschaften der ursprünglichen Mengen.

Lösung:

• Definiere Menge E als Vereinigung der Mengen A und B:

• Menge A: \(\{1, 2, 3, 4, 5\}\)
• Menge B: \(\{ x \, | \, x \in \mathbb{N} \text{ und } x \text{ ist gerade} \}\)

• Die Vereinigung der beiden Mengen ist:

• Menge E: \(A \cup B = \{1, 2, 3, 4, 5\} \cup \{ x \in \mathbb{N} \text{ und } x \text{ ist gerade} \}\)

• Untersuchen wir die Eigenschaften der einzelnen Mengen:

• Eigenschaften von Menge A: Menge A ist endlich und enthält die Elemente {1, 2, 3, 4, 5}.
• Eigenschaften von Menge B: Menge B ist unendlich und enthält alle geraden natürlichen Zahlen {2, 4, 6, 8, ...}.

• Wenn wir die Vereinigung der beiden Mengen bilden, erhalten wir eine Menge, die alle Elemente von A und alle Elemente von B enthält:

• Menge E: \(\{1, 2, 3, 4, 5\} \cup \{2, 4, 6, 8, ...\}\)

• Da Menge B unendlich viele Elemente enthält, wird die Vereinigung einer endlichen Menge (Menge A) mit einer unendlichen Menge (Menge B) auch unendlich viele Elemente enthalten.

• Das bedeutet, dass Menge E unendlich viele Elemente enthält.

• Schlussfolgerung: Menge E ist unendlich, weil sie die Vereinigung einer endlichen Menge (Menge A) mit einer unendlichen Menge (Menge B) ist.