Überfachliche Grundlagen - Exam.pdf

Aufgabe 1)

Stellen Sie sich vor, Sie sind verantwortlich für die Validierung von Aussagen in einem Programm, das automatisierte Entscheidungen trifft. Ihre Aufgabe besteht darin, die grundlegenden logischen Operationen wie Konjunktionen, Disjunktionen und Implikationen korrekt zu verstehen und anzuwenden.

a)

Teil 1: Gegeben seien die Aussagen:

• p: „Der Sensor ist aktiv.“
• q: „Das Signal wird gesendet.“

Formulieren Sie die folgenden logischen Aussagen in Worten und bestimmen Sie ihre Wahrheitstafeln:

• Konjunktion: p ∧ q
• Disjunktion: p ∨ q
• Implikation: p → q

Lösung:

Teil 1: Gegeben seien die Aussagen:

• p: „Der Sensor ist aktiv.“
• q: „Das Signal wird gesendet.“

Formulieren Sie die folgenden logischen Aussagen in Worten und bestimmen Sie ihre Wahrheitstafeln:

• Konjunktion: p ∧ q
• Disjunktion: p ∨ q
• Implikation: p → q

• Konjunktion (p ∧ q): Dies bedeutet „Der Sensor ist aktiv und das Signal wird gesendet.“Die Wahrheitstafel für die Konjunktion sieht wie folgt aus:

• Disjunktion (p ∨ q): Dies bedeutet „Der Sensor ist aktiv oder das Signal wird gesendet.“Die Wahrheitstafel für die Disjunktion sieht wie folgt aus:

• Implikation (p → q): Dies bedeutet „Wenn der Sensor aktiv ist, dann wird das Signal gesendet.“Die Wahrheitstafel für die Implikation sieht wie folgt aus:

b)

Teil 2: Angenommen, die Aussagen p und q haben die folgenden Wahrheitswerte:

• p ist wahr.
• q ist falsch.

Ermitteln Sie die Wahrheitswerte der folgenden zusammengesetzten Aussagen:

• (p ∧ q) → q
• (p ∨ q) ∧ (¬q)
• ¬(p ∧ q) ∨ (p ∧ ¬q)

Lösung:

Teil 2: Angenommen, die Aussagen p und q haben die folgenden Wahrheitswerte:

• p ist wahr.
• q ist falsch.

Ermitteln Sie die Wahrheitswerte der folgenden zusammengesetzten Aussagen:

• (p ∧ q) → q
• (p ∨ q) ∧ (¬q)
• ¬(p ∧ q) ∨ (p ∧ ¬q)

• 1. (p ∧ q) → q: Zuerst berechnen wir p ∧ q: - p ist wahr. - q ist falsch. - Also ist p ∧ q falsch.Nun müssen wir die Implikation (p ∧ q) → q auswerten: - p ∧ q ist falsch. - q ist falsch. - Eine Implikation ist wahr, wenn der Vordersatz (Antezedens) falsch ist. Daher ist (p ∧ q) → q wahr. Der Wahrheitswert von (p ∧ q) → q ist daher: wahr.
• 2. (p ∨ q) ∧ (¬q): Zuerst berechnen wir p ∨ q: - p ist wahr. - q ist falsch. - Also ist p ∨ q wahr.Nun berechnen wir ¬q: - q ist falsch. - Also ist ¬q wahr.Nun müssen wir die Konjunktion (p ∨ q) ∧ (¬q) auswerten: - p ∨ q ist wahr. - ¬q ist wahr. - Eine Konjunktion ist nur dann wahr, wenn beide Teilaussagen wahr sind. Daher ist (p ∨ q) ∧ (¬q) wahr.Der Wahrheitswert von (p ∨ q) ∧ (¬q) ist daher: wahr.
• 3. ¬(p ∧ q) ∨ (p ∧ ¬q): Zuerst berechnen wir p ∧ q: - p ist wahr. - q ist falsch. - Also ist p ∧ q falsch.Nun berechnen wir ¬(p ∧ q): - p ∧ q ist falsch. - Also ist ¬(p ∧ q) wahr.Nun berechnen wir p ∧ ¬q: - p ist wahr. - ¬q ist wahr. - Also ist p ∧ ¬q wahr.Nun müssen wir die Disjunktion ¬(p ∧ q) ∨ (p ∧ ¬q) auswerten: - ¬(p ∧ q) ist wahr. - p ∧ ¬q ist wahr. - Eine Disjunktion ist wahr, wenn mindestens eine der Teilaussagen wahr ist. Daher ist ¬(p ∧ q) ∨ (p ∧ ¬q) wahr.Der Wahrheitswert von ¬(p ∧ q) ∨ (p ∧ ¬q) ist daher: wahr.

c)

Teil 3: In einem komplexen Entscheidungsprozess ist es wichtig, die Reihenfolge und Gruppierung logischer Operationen korrekt zu verstehen. Analysieren Sie die folgende Aussage und beantworten Sie die Fragen:

((p ∨ ¬q) ∧ (r → s)) → (¬p ∨ s), wobei r und s zusätzliche Aussagen sind.

• Erstellen Sie die Wahrheitstafel für die gegebenen Aussagen p, q, r und s.

• Geben Sie ein Beispiel an, bei dem die gesamte Aussage wahr ist, und eines, bei dem sie falsch ist.

Lösung:

Teil 3: In einem komplexen Entscheidungsprozess ist es wichtig, die Reihenfolge und Gruppierung logischer Operationen korrekt zu verstehen. Analysieren Sie die folgende Aussage und beantworten Sie die Fragen:

((p ∨ ¬q) ∧ (r → s)) → (¬p ∨ s), wobei r und s zusätzliche Aussagen sind.

• Erstellen Sie die Wahrheitstafel für die gegebenen Aussagen p, q, r und s.

• Geben Sie ein Beispiel an, bei dem die gesamte Aussage wahr ist, und eines, bei dem sie falsch ist.

• 1. Wahrheitstafel:

  Die Wahrheitstafel für die gegebenen Aussagen p, q, r und s wird wie folgt erstellt. Jede Zeile repräsentiert eine mögliche Kombination der Wahrheitswerte von p, q, r und s, und die resultierende Wahrheit der gesamten Aussage ((p ∨ ¬q) ∧ (r → s)) → (¬p ∨ s).

  p	q	r	s	p ∨ ¬q	r → s	(p ∨ ¬q) ∧ (r → s)	¬p ∨ s	((p ∨ ¬q) ∧ (r → s)) → (¬p ∨ s)
  wahr (True)	wahr (True)	wahr (True)	wahr (True)	wahr (True)	wahr (True)	wahr (True)	wahr (True)	wahr (True)
  wahr (True)	wahr (True)	wahr (True)	falsch (False)	wahr (True)	falsch (False)	falsch (False)	falsch (False)	wahr (True)
  wahr (True)	wahr (True)	falsch (False)	wahr (True)	wahr (True)	wahr (True)	wahr (True)	wahr (True)	wahr (True)
  wahr (True)	wahr (True)	falsch (False)	falsch (False)	wahr (True)	wahr (True)	wahr (True)	falsch (False)	falsch (False)
  wahr (True)	falsch (False)	wahr (True)	wahr (True)	wahr (True)	wahr (True)	wahr (True)	wahr (True)	wahr (True)
  wahr (True)	falsch (False)	wahr (True)	falsch (False)	wahr (True)	falsch (False)	falsch (False)	falsch (False)	wahr (True)
  wahr (True)	falsch (False)	falsch (False)	wahr (True)	wahr (True)	wahr (True)	wahr (True)	wahr (True)	wahr (True)
  wahr (True)	falsch (False)	falsch (False)	falsch (False)	wahr (True)	wahr (True)	wahr (True)	falsch (False)	falsch (False)
  falsch (False)	wahr (True)	wahr (True)	wahr (True)	falsch (False)	wahr (True)	falsch (False)	wahr (True)	wahr (True)
  falsch (False)	wahr (True)	wahr (True)	falsch (False)	falsch (False)	falsch (False)	falsch (False)	falsch (False)	wahr (True)
  falsch (False)	wahr (True)	falsch (False)	wahr (True)	falsch (False)	wahr (True)	falsch (False)	wahr (True)	wahr (True)
  falsch (False)	wahr (True)	falsch (False)	falsch (False)	falsch (False)	wahr (True)	falsch (False)	falsch (False)	wahr (True)
  falsch (False)	falsch (False)	wahr (True)	wahr (True)	falsch (False)	wahr (True)	falsch (False)	wahr (True)	wahr (True)
  falsch (False)	falsch (False)	wahr (True)	falsch (False)	falsch (False)	falsch (False)	falsch (False)	falsch (False)	wahr (True)
  falsch (False)	falsch (False)	falsch (False)	wahr (True)	falsch (False)	wahr (True)	falsch (False)	wahr (True)	wahr (True)
  falsch (False)	falsch (False)	falsch (False)	falsch (False)	falsch (False)	wahr (True)	falsch (False)	falsch (False)	wahr (True)

• 2. Beispiele:

  • Ein Beispiel, bei dem die gesamte Aussage wahr ist: - p ist wahr. - q ist falsch. - r ist wahr. - s ist wahr. - In diesem Fall sind alle Teilaussagen und somit die gesamte Aussage ((p ∨ ¬q) ∧ (r → s)) → (¬p ∨ s) wahr.
  • Ein Beispiel, bei dem die gesamte Aussage falsch ist: - p ist wahr. - q ist wahr. - r ist falsch. - s ist falsch. - In diesem Fall sind die Teilaussagen (r → s) und (¬p ∨ s) falsch, was die gesamte Aussage ((p ∨ ¬q) ∧ (r → s)) → (¬p ∨ s) ebenfalls falsch macht.

Aufgabe 2)

Betrachte die folgenden Aussagen in der Prädikatenlogik über eine Menge von Objekten:

• Die Menge ist geprägt durch eine Relation 'R' und eine Funktion 'F'.
• Für alle Objekte 'x' gilt, dass wenn 'x' in Relation zu einem anderen Objekt 'y' steht, 'y' ebenfalls in Relation zu 'x' steht (Symmetrie von 'R').
• Es existiert mindestens ein Objekt 'z', das für alle Objekte 'w', die in Relation 'R' zu ihm stehen, auch eine bestimmte Bedingung erfüllt.
• Die Funktion 'F' ist so definiert, dass sie jedes Objekt 'x' aus der Menge auf ein anderes Objekt 'F(x)' abbildet.

a)

Formuliere in der Prädikatenlogik: Die Relation 'R' ist symmetrisch. Verwende dazu notwendige Variablen, Terme und Formeln.

Lösung:

Um die Symmetrie der Relation 'R' in der Prädikatenlogik zu beschreiben, kannst Du die folgende Formel verwenden:

• Gegebene Elemente: x, y (beliebige Objekte aus der Menge)
• Gegebene Relation: R(x, y) (x steht in Relation zu y)

Die Symmetrie von 'R' bedeutet, dass wenn 'x' in Relation zu 'y' steht, dann steht auch 'y' in Relation zu 'x'. Das lässt sich wie folgt formalisieren:

• Formel: \[\forall x \forall y (R(x, y) \rightarrow R(y, x))\]

Das bedeutet:

• Für alle Objekte x und y gilt: Wenn x in Relation zu y steht, dann steht auch y in Relation zu x.

b)

Drücke folgendes in der Prädikatenlogik aus: Ein Objekt 'z' existiert, das für alle Objekte 'w', die in Relation 'R' zu ihm stehen, auch die Bedingung 'P(w)' erfüllt. Verwende dabei die Formel (Q(z, w)) und berücksichtige die Tatsache, dass dies für alle 'w' gilt.

Lösung:

Um die Aussage in der Prädikatenlogik auszudrücken, dass es ein Objekt 'z' gibt, das für alle Objekte 'w', die in Relation 'R' zu ihm stehen, auch die Bedingung 'P(w)' erfüllt, können wir die folgenden Variablen, Terme und Formeln verwenden:

• Gegebene Objekte: z, w (beliebige Objekte aus der Menge)
• Gegebene Relation: R(z, w) (z steht in Relation zu w)
• Gegebene Bedingung: P(w) (w erfüllt die Bedingung P)

Wir wollen ausdrücken, dass:

• Es existiert mindestens ein Objekt 'z', sodass für alle Objekte 'w', die in Relation 'R' zu 'z' stehen, auch 'P(w)' gilt.

Formalisiert in Prädikatenlogik lautet dies:

• Formel: \[\text{\exists} z (\forall w (R(z, w) \rightarrow P(w)))\]

Das bedeutet:

• Es gibt ein Objekt 'z', für das es gilt, dass alle Objekte 'w', die in Relation 'R' zu 'z' stehen, auch die Bedingung 'P(w)' erfüllen.

Aufgabe 3)

Kontext: Du sollst unterschiedliche Beweistechniken anwenden, um mathematische Aussagen zu verifizieren. Dazu stehen Dir der direkte Beweis, der indirekte Beweis und der Widerspruchsbeweis zur Verfügung.

a)

Beweise die Aussage durch direkten Beweis. Sei n eine gerade natürliche Zahl. Zeige, dass n² eine gerade Zahl ist.

• Definiere, was es bedeutet, dass eine Zahl n gerade ist.
• Zeige schrittweise, dass aus der Definition die Behauptung folgt.

Lösung:

Beweis durch direkten Beweis:

• Definition: Eine Zahl n ist gerade, wenn es eine ganze Zahl k gibt, so dass n = 2k. Das bedeutet, dass n ohne Rest durch 2 teilbar ist.
• Behauptung: Wenn n eine gerade natürliche Zahl ist, dann ist auch n² eine gerade Zahl.

• Schritt 1: Sei n eine gerade Zahl. Nach der Definition gibt es eine ganze Zahl k, für die gilt: n = 2k.
• Schritt 2: Berechne n² unter Verwendung der Definition: n² = (2k)² = 4k²
• Schritt 3: 4k² kann als 2 \times (2k²) geschrieben werden, was beweist, dass n² durch 2 teilbar ist.
• Schlussfolgerung: Da 4k² = 2m für eine ganze Zahl m geschrieben werden kann, ist n² eine gerade Zahl. Dies zeigt, dass wenn n eine gerade natürliche Zahl ist, dann ist auch n² eine gerade Zahl.

b)

Beweise die Aussage durch indirekten Beweis. Zeige, dass für jede natürliche Zahl n, wenn n² ungerade ist, dann muss n auch ungerade sein.

• Formuliere die Aussage in ihrer Negation.
• Zeige, dass die Negation zu einem Widerspruch führt.

Lösung:

Beweis durch indirekten Beweis:

• Aussage: Für jede natürliche Zahl n, wenn n² ungerade ist, dann muss n auch ungerade sein.

• Negation der Aussage: Es existiert eine natürliche Zahl n, so dass n² ungerade ist und n gerade ist.

• Schritt 1: Angenommen, n ist gerade. Das bedeutet, es existiert eine ganze Zahl k, so dass n = 2k.
• Schritt 2: Berechne n² unter Verwendung der Definition: n² = (2k)² = 4k²
• Schritt 3: Da 4k² offensichtlich durch 2 teilbar ist, ist n² gerade.
• Widerspruch: Wir haben angenommen, dass n² ungerade ist, aber aus den obigen Schritten folgt, dass n² gerade ist. Das ist ein Widerspruch.
• Schlussfolgerung: Die Annahme, dass n gerade sein kann wenn n² ungerade ist, führt zu einem Widerspruch. Daher muss n ungerade sein, wenn n² ungerade ist.

Aufgabe 4)

Gegeben sei eine Gruppe \( (G, \times) \) mit den folgenden Eigenschaften:

• \( G \) ist eine endliche Menge.
• Die Verknüpfung \( \times \) ist assoziativ und erfüllt die Gruppenaxiome.

Im Folgenden betrachten wir die Teilmengen von \( G \) und Abbildungen zwischen Gruppen.

a)

Teilaufgabe 1: Zeigen Sie, dass die Menge \( H = \{e, a, a^2\} \) mit der Verknüpfung \( \times \) eine Untergruppe von \( G \) ist, wobei \( e \) das neutrale Element von \( G \) und \( a \in G \) ist. Es wird vorausgesetzt, dass \( a^3 = e \). Verifizieren Sie, dass die angegebenen Elemente die Gruppenaxiome erfüllen und deshalb tatsächlich eine Untergruppe bilden.

Lösung:

Um zu zeigen, dass die Menge H = \{e, a, a^2\} mit der Verknüpfung \( \times \) eine Untergruppe von G ist, müssen wir die Untergruppenaxiome überprüfen:

• 1. H enthält das neutrale Element e von G.
• 2. H ist abgeschlossen bezüglich der Verknüpfung \( \times \).
• 3. Jedes Element von H besitzt ein Inverses in H.

Gehen wir Schritt für Schritt vor:

1. Neutrales Element: In der Menge H ist tatsächlich das neutrale Element e von G enthalten, da \(e \in H\).
2. Abgeschlossenheit: Wir müssen zeigen, dass für alle Elemente in H die Verknüpfung \( \times \) in H bleibt.
   • e \( \times \) e = e (liegt in H)
   • e \( \times \) a = a (liegt in H)
   • e \( \times \) a^2 = a^2 (liegt in H)
   • a \( \times \) e = a (liegt in H)
   • a \( \times \) a = a^2 (liegt in H)
   • a \( \times \) a^2 = a^3 = e (liegt in H, da \(a^3 = e\))
   • a^2 \( \times \) e = a^2 (liegt in H)
   • a^2 \( \times \) a = a^3 = e (liegt in H)
   • a^2 \( \times \) a^2 = a^4 = a \( \times \) a^3 = a \( \times \) e = a (liegt in H)
3. Inverses Element: Jedes Element in H muss ein Inverses in H besitzen.
   • Das Inverse von e ist e selbst, da \(e \( \times \) e = e\).
   • Das Inverse von a ist a^2, da \(a \( \times \) a^2 = e\).
   • Das Inverse von a^2 ist a, da \(a^2 \( \times \) a = e\).

Da alle drei Untergruppenaxiome erfüllt sind,müssen wir schließen, dass H = \{e, a, a^2\} wirklich eine Untergruppe von G ist.

c)

Teilaufgabe 3: Betrachten Sie zwei Gruppen \( (G, \times) \) und \( (G', \times') \). Seien \( \theta: G \rightarrow G' \) und \( \theta' : G' \rightarrow G \) zwei Homomorphismen. Zeigen Sie, dass eine Komposition \( \theta \theta' : G' \rightarrow G' \) wiederum ein Homomorphismus ist. Verifizieren Sie insbesondere die Homomorphieeigenschaft \( \theta \theta'(a' \times' b') = \theta \theta'(a') \times' \theta \theta'(b') \) für alle \( a', b' \in G' \).

Lösung:

Um zu zeigen, dass die Komposition \( \theta \theta' : G' \rightarrow G' \) ein Homomorphismus ist, müssen wir die Eigenschaft der Homomorphie für die zusammengesetzte Abbildung nachweisen. Insbesondere müssen wir zeigen, dass für alle \( a', b' \in G' \) die Gleichung \( \theta \theta'(a' \times' b') = \theta \theta'(a') \times' \theta \theta'(b') \) gilt.

Hier sind die einzelnen Schritte:

1. Definition von Homomorphismen: Ein Homomorphismus \( \theta : G \rightarrow G' \) ist eine Abbildung zwischen zwei Gruppen, die die Gruppenoperation respektiert, d.h. für alle \( g_1, g_2 \in G \) gilt: \[\theta(g_1 \times g_2) = \theta(g_1) \times' \theta(g_2)\]
2. Komposition der Homomorphismen: Gegeben \( \theta : G \rightarrow G' \) und \( \theta' : G' \rightarrow G \), ist die Komposition \( \theta \theta' \) definiert als: \[\theta \theta'(x) = \theta(\theta'(x)) \quad \text{für alle} \quad x \in G' \]
3. Homomorphieeigenschaft der Komposition:Nun zeigen wir, dass \( \theta \theta' \) ebenfalls ein Homomorphismus ist. Das bedeutet, wir müssen nachweisen, dass für alle \( a', b' \in G' \) gilt: \[\theta \theta'(a' \times' b') = \theta \theta'(a') \times' \theta \theta'(b')\]
4. Beweis:
   • Starten wir mit dem linken Ausdruck:
   • \[\theta \theta'(a' \times' b') = \theta(\theta'(a' \times' b'))\]
   • Da \( \theta' \) ein Homomorphismus ist, gilt:
   • \[\theta'(a' \times' b') = \theta'(a') \times \theta'(b')\]
   • Setzen wir dies in die vorherige Gleichung ein:
   • \[\theta(\theta'(a' \times' b')) = \theta(\theta'(a') \times \theta'(b'))\]
   • Da \( \theta \) ebenfalls ein Homomorphismus ist, gilt:
   • \[\theta(\theta'(a') \times \theta'(b')) = \theta(\theta'(a')) \times' \theta(\theta'(b'))\]
   • Daraus folgt:
   • \[\theta \theta'(a' \times' b') = \theta \theta'(a') \times' \theta \theta'(b')\]

Da die Homomorphieeigenschaft erfüllt ist, können wir schließen, dass die Komposition \( \theta \theta' : G' \rightarrow G' \) ein Homomorphismus ist.