Logik-Basierte Sprachverarbeitung - Exam

Aufgabe 1)

Aussagenlogik und ihre PrinzipienAussagenlogik untersucht die formale Struktur von Aussagen mittels logischer Operatoren.

• Aussagen (propositionale Variable): entweder wahr (True) oder falsch (False)
• Logische Operatoren: und (AND: ∧), oder (OR: ∨), nicht (NOT: ¬), impliziert (Implikation: →), äquivalent (Äquivalenz: ↔)
• Wahrheitstafeln zur Bestimmung von Wahrheitswerten
• Gesetze der Aussagenlogik: Identitätsgesetz, Negationsgesetz, Idempotenzgesetz, Domination, Double Negation, Kommutativität, Assoziativität, Distributivität, De Morgan’sche Gesetze
• Beispiel: Wahrheitstabelle für A ∧ B

  A	B	A ∧ B
  Wahr	Wahr	Wahr
  Wahr	Falsch	Falsch
  Falsch	Wahr	Falsch
  Falsch	Falsch	Falsch

a)

Erstelle eine Wahrheitstafel für die logische Ausdruck \texttt{(A ∧ ¬B) ∨ (¬A ∧ B)}. Fülle jede Zeile der Tabelle aus und bestimme, wann der Ausdruck wahr oder falsch ist.

Lösung:

Wahrheitstafel für den logischen Ausdruck (A ∧ ¬B) ∨ (¬A ∧ B)Um die Wahrheitstafel für den gegebenen logischen Ausdruck zu erstellen, müssen wir alle möglichen Kombinationen von A und B betrachten und den Wahrheitswert des Ausdrucks in jeder dieser Kombinationen bestimmen.Hier ist die vollständige Wahrheitstafel:

A	B	¬A	¬B	A ∧ ¬B	¬A ∧ B	(A ∧ ¬B) ∨ (¬A ∧ B)
Wahr	Wahr	Falsch	Falsch	Falsch	Falsch	Falsch
Wahr	Falsch	Falsch	Wahr	Wahr	Falsch	Wahr
Falsch	Wahr	Wahr	Falsch	Falsch	Wahr	Wahr
Falsch	Falsch	Wahr	Wahr	Falsch	Falsch	Falsch

Erklärung der Spalten:

• A und B sind die Eingangsvariablen, die entweder Wahr oder Falsch sein können.
• ¬A und ¬B zeigen die Negation der Variablen A und B.
• A ∧ ¬B repräsentiert das Ergebnis der logischen UND-Operation zwischen A und der Negation von B.
• ¬A ∧ B repräsentiert das Ergebnis der logischen UND-Operation zwischen der Negation von A und B.
• (A ∧ ¬B) ∨ (¬A ∧ B) zeigt das Ergebnis der logischen ODER-Operation zwischen den beiden vorherigen Ergebnissen.

b)

Beweise mittels Wahrheitstafeln, dass die formulierte Aussage aus dem ersten Teil wirklich einer der De Morgan'schen Gesetze entspricht.

Lösung:

Wahrheitstafel und Beweis des De Morgan'schen Gesetzes

• De Morgan'sche Gesetze sind zwei Transformationsregeln der Aussagenlogik, die wie folgt lauten:Erstes Gesetz: ¬(A ∧ B) ≡ ¬A ∨ ¬BZweites Gesetz: ¬(A ∨ B) ≡ ¬A ∧ ¬B

Um zu beweisen, dass eine dieser Regeln durch Wahrheitstafeln gültig ist, vergleichen wir beide Seiten der Gleichung.Wir nehmen das erste Gesetz: ¬(A ∧ B) ≡ ¬A ∨ ¬BHier ist die erweiterte Wahrheitstafel für diese beiden Ausdrücke:

A	B	A ∧ B	¬(A ∧ B)	¬A	¬B	¬A ∨ ¬B
Wahr	Wahr	Wahr	Falsch	Falsch	Falsch	Falsch
Wahr	Falsch	Falsch	Wahr	Falsch	Wahr	Wahr
Falsch	Wahr	Falsch	Wahr	Wahr	Falsch	Wahr
Falsch	Falsch	Falsch	Wahr	Wahr	Wahr	Wahr

Erklärung der Spalten:

• A und B sind die Eingangsvariablen, die entweder Wahr oder Falsch sein können.
• A ∧ B stellt die logische UND-Verknüpfung der Variablen A und B dar.
• ¬(A ∧ B) stellt die Negation der logischen UND-Verknüpfung von A und B dar.
• ¬A und ¬B zeigen die Negation der Variablen A und B.
• ¬A ∨ ¬B stellt die logische ODER-Verknüpfung der Negationen von A und B dar.

Durch den Vergleich der Spalten für ¬(A ∧ B) und ¬A ∨ ¬B können wir sehen, dass sie für jede Kombination von A und B immer die gleichen Wahrheitswerte haben. Daher ist bewiesen, dass das erste De Morgan'sche Gesetz gültig ist: ¬(A ∧ B) ≡ ¬A ∨ ¬B.

Aufgabe 2)

Gegeben sei das Universum der Diskurs \textit{U}, welches aus allen natürlichen Zahlen besteht. Definiere die Prädikate \textit{E(x)} als 'x ist eine gerade Zahl' und \textit{P(x)} als 'x ist eine Primzahl'. Verwende die Prädikatenlogik und Quantoren, um die folgenden Aufgaben zu lösen.

a)

Formuliere schriftlich die folgenden Aussagen in Prädikatenlogik:

• Es gibt eine gerade Zahl, die eine Primzahl ist.
• Alle Primzahlen sind ungerade Zahlen.
• Jede gerade Zahl größer als 2 ist keine Primzahl.

Lösung:

Universum der Diskurs: U (alle natürlichen Zahlen)Prädikate:

• E(x): x ist eine gerade Zahl
• P(x): x ist eine Primzahl

Aufgaben:

• Es gibt eine gerade Zahl, die eine Primzahl ist.
• Alle Primzahlen sind ungerade Zahlen.
• Jede gerade Zahl größer als 2 ist keine Primzahl.

Lösungen in Prädikatenlogik:

• Es gibt eine gerade Zahl, die eine Primzahl ist:

  ∃x (E(x) ∧ P(x))

• Alle Primzahlen sind ungerade Zahlen:

  ∀x (P(x) → ¬E(x))

• Jede gerade Zahl größer als 2 ist keine Primzahl:

  ∀x [(E(x) ∧ x > 2) → ¬P(x)]

b)

Beweise formal die Aussage 'Es existiert eine Primzahl, die weder gerade noch ungerade ist' anhand einer Widerspruchsannahme und der Anwendung der Prädikatenlogik und Quantoren.Zeige dabei jeden Schritt im Detail.

Lösung:

Universum der Diskurs: U (alle natürlichen Zahlen)Prädikate:

• E(x): x ist eine gerade Zahl
• P(x): x ist eine Primzahl
• O(x): x ist eine ungerade Zahl

Aufgabe: Beweise formal die Aussage 'Es existiert eine Primzahl, die weder gerade noch ungerade ist' anhand einer Widerspruchsannahme und der Anwendung der Prädikatenlogik und Quantoren.Beweis durch Widerspruch:

• Annahme: Es gibt eine Primzahl, die weder gerade noch ungerade ist.
• Formulieren der Annahme in Prädikatenlogik:

  ∃x [P(x) ∧ ¬E(x) ∧ ¬O(x)]

• Erinnern, dass eine Zahl entweder gerade oder ungerade sein muss. Formal:

  ∀x [E(x) ∨ O(x)]

• Widerspruch annehmen: Angenommen, es gebe eine Zahl 'x', die weder gerade noch ungerade ist.

  ∃x [¬E(x) ∧ ¬O(x)]

• Da jede natürliche Zahl entweder gerade oder ungerade ist, folgt:

  ¬∃x [¬E(x) ∧ ¬O(x)]

• Kombiniere die Aussagen:

  1. ∃x [P(x) ∧ ¬E(x) ∧ ¬O(x)]

  2. ¬∃x [¬E(x) ∧ ¬O(x)]

• Die beiden Aussagen widersprechen sich gegenseitig, daher ist die ursprüngliche Annahme falsch.
• Schlussfolgerung: Es existiert keine Primzahl, die weder gerade noch ungerade ist.

Aufgabe 3)

Gegeben sei ein Prolog-Programm, das mit Fakten und Regeln Aussagen über Familienbeziehungen trifft. Folgende Fakten und Regeln sind gegeben:

vater(heinrich, fritz).vater(fritz, hans).mutter(maria, hans).elternteil(X, Y) :- vater(X, Y).elternteil(X, Y) :- mutter(X, Y).grossvater(X, Z) :- vater(X, Y), elternteil(Y, Z).

a)

Define die Bedeutung und Syntax von Fakten und Regeln in Prolog und erläutere, wie sie in obigem Programm verwendet werden.

Lösung:

Definition und Syntax von Fakten und Regeln in Prolog:

• Fakten: In Prolog werden Fakten verwendet, um grundlegende Aussagen über die Welt zu machen. Diese Aussagen sind immer wahr. Ein Fakt hat in der Regel das Format prädikat(argument1, argument2, ...). Anhand der Argumente können Beziehungen zwischen den Objekten beschrieben werden.
• vater(heinrich, fritz). Dieser Fakt besagt, dass Heinrich der Vater von Fritz ist.
• vater(fritz, hans). Dieser Fakt besagt, dass Fritz der Vater von Hans ist.
• mutter(maria, hans). Dieser Fakt besagt, dass Maria die Mutter von Hans ist.

• Regeln: In Prolog werden Regeln verwendet, um logisch abgeleitete Aussagen zu definieren. Eine Regel besteht aus einem Kopf und einem oder mehreren Körpern, die durch :- getrennt werden. Der Kopf ist die Aussage, die wahr ist, wenn die Körperbedingungen erfüllt sind. Die allgemeine Syntax einer Regel ist kopf :- bedingung1, bedingung2, ... .
• elternteil(X, Y) :- vater(X, Y). Diese Regel besagt, dass X ein Elternteil von Y ist, wenn X der Vater von Y ist.
• elternteil(X, Y) :- mutter(X, Y). Diese Regel besagt, dass X ein Elternteil von Y ist, wenn X die Mutter von Y ist.
• grossvater(X, Z) :- vater(X, Y), elternteil(Y, Z). Diese Regel besagt, dass X der Großvater von Z ist, wenn X der Vater von Y ist und Y ein Elternteil von Z ist.

Verwendung im obigen Programm:

• Das Prolog-Programm definiert spezifische Familienbeziehungen durch die Fakten vater(heinrich, fritz)., vater(fritz, hans). und mutter(maria, hans)..
• Zusätzlich verwendet das Programm Regeln, um allgemeine Konzepte wie Elternteil und Großvater zu definieren. Zum Beispiel zeigt elternteil(X, Y) :- vater(X, Y). und elternteil(X, Y) :- mutter(X, Y)., dass ein Elternteil entweder ein Vater oder eine Mutter sein kann.
• Die Regel grossvater(X, Z) :- vater(X, Y), elternteil(Y, Z). verwendet die bereits definierten Beziehungen, um die Beziehung eines Großvaters in der Familienstruktur zu erstellen und leitet ab, dass Heinrich der Großvater von Hans ist, weil Heinrich der Vater von Fritz und Fritz ein Elternteil von Hans ist.

b)

Formuliere eine Abfrage, um herauszufinden, wer der Großvater von Hans ist. Beschreibe den Ablauf der Suchstrategie (Tiefensuche) in Prolog, die verwendet wird, um die Antwort zu berechnen.

Lösung:

Abfrage:Um herauszufinden, wer der Großvater von Hans ist, formulieren wir folgende Abfrage in Prolog:

grossvater(X, hans).

Ablauf der Suchstrategie (Tiefensuche) in Prolog:Prolog verwendet eine Tiefensuche (Depth-First Search, DFS) Strategie, um Lösungen für die gestellte Abfrage zu finden. Im Detail läuft die Suchstrategie folgendermaßen ab:

• Prolog startet mit der Abfrage grossvater(X, hans). und sucht im Regel- und Faktenbestand nach einer passenden Regel für grossvater(X, Z).
• Die Regel grossvater(X, Z) :- vater(X, Y), elternteil(Y, Z). wird gefunden. Prolog versucht nun, eine Übereinstimmung herzustellen, indem es die Regelkörper prüft (vater(X, Y) und elternteil(Y, hans)).
• Zuerst prüft Prolog vater(X, Y). Es sucht im Faktenbestand nach Einträgen, die zu vater(X, Y) passen. Der Fakt vater(heinrich, fritz) passt, also wird X mit heinrich und Y mit fritz belegt.
• Nun prüft Prolog, ob elternteil(fritz, hans) wahr ist. Hier wird die Regel elternteil(X, Y) :- vater(X, Y). verwendet.
• Es gibt einen Fakt vater(fritz, hans), der erfüllt ist, somit ist elternteil(fritz, hans) wahr.
• Da beide Teilbedingungen (vater(heinrich, fritz) und elternteil(fritz, hans)) erfüllt sind, ist die ursprüngliche Abfrage grossvater(heinrich, hans) wahr.
• Prolog gibt dafür als Antwort X = heinrich zurück, das heißt, Heinrich ist der Großvater von Hans.

Zusammenfassung:Durch Anwendung der Tiefensuche und schrittweises Prüfen der Regeln und Fakten kommt Prolog zu der Antwort, dass Heinrich der Großvater von Hans ist.

c)

Erkläre das Konzept der Unifikation und zeige anhand eines Beispiels, wie Unifikation in der Regel

grossvater(X, Z) :- vater(X, Y), elternteil(Y, Z).

funktioniert.

Lösung:

Unifikation in Prolog:

• Das Konzept der Unifikation in Prolog bezieht sich auf den Prozess, bei dem Prolog versucht, Variablen mit Konstanten oder anderen Variablen zu binden, um eine Übereinstimmung zwischen einer Abfrage und einer Fakt oder Regel zu finden. Dies ist ein zentraler Mechanismus, der es Prolog ermöglicht, logische Schlussfolgerungen zu ziehen.

Beispiel zur Unifikation in der Regel:Betrachten wir die Regel:

grossvater(X, Z) :- vater(X, Y), elternteil(Y, Z).

Und nehmen wir an, wir stellen die Abfrage:

grossvater(heinrich, hans).

• Prolog versucht, die Regel grossvater(X, Z) :- vater(X, Y), elternteil(Y, Z). mit der Abfrage grossvater(heinrich, hans) zu unifizieren.
• Bei der Unifikation wird X mit heinrich und Z mit hans gebunden. Die Regel wird nun wie folgt interpretiert: vater(heinrich, Y), elternteil(Y, hans).
• Nun versucht Prolog, vater(heinrich, Y) zu erfüllen. Im Faktenbestand findet es den Fakt vater(heinrich, fritz). Somit wird Y mit fritz gebunden.
• Die Regel lautet jetzt: elternteil(fritz, hans).
• Prolog versucht nun, elternteil(fritz, hans) zu erfüllen. Es findet zwei Regeln für elternteil: elternteil(X, Y) :- vater(X, Y) und elternteil(X, Y) :- mutter(X, Y).
• Prolog prüft die erste Regel: elternteil(fritz, hans) :- vater(fritz, hans). Es findet den Fakt vater(fritz, hans), somit ist elternteil(fritz, hans) erfüllt.
• Da beide Teilbedingungen der ursprünglichen Regel erfüllt sind (vater(heinrich, fritz) und elternteil(fritz, hans)), gilt die Regel grossvater(heinrich, hans) als wahr.

• Durch diese Sequenz von Unifikationen kommen wir zu dem Schluss, dass Heinrich der Großvater von Hans ist.

Zusammenfassung:

• Die Unifikation ermöglicht es Prolog, Variablenwerte so zuzuweisen, dass Abfragen mit Regeln und Fakten übereinstimmen. In unserem Beispiel führte die Unifikation der Variablen in der Regel grossvater(X, Z) :- vater(X, Y), elternteil(Y, Z) zur Erkenntnis, dass Heinrich der Großvater von Hans ist.

d)

Diskutiere die Bedeutung des Herbrand-Universums und der Modelltheorie in der Semantik von Prolog-Programmen. Wie tragen diese Begriffe zur Interpretation des Programms bei?

Lösung:

Die Bedeutung des Herbrand-Universums und der Modelltheorie in der Semantik von Prolog-Programmen:

• Herbrand-Universum: Das Herbrand-Universum ist die Menge aller Grundterme (d.h. Terme ohne Variablen), die in einem gegebenen Prolog-Programm gebildet werden können. Dies umfasst alle Konstanten und Funktionssymbole, die in den Fakten und Regeln des Programms vorkommen. In unserem Beispiel umfassen die Konstanten heinrich, fritz, hans und maria das Herbrand-Universum.
• Das Herbrand-Universum stellt sicher, dass alle möglichen Kombinationen von Terme innerhalb des Programms berücksichtigt werden, wenn Prolog versucht, eine Abfrage zu lösen.
• Modelltheorie: In der Modelltheorie wird ein Modell als Interpretation einer Menge von Sätzen verstanden, das diese Sätze wahr macht. Für Prolog-Programme bedeutet dies, dass ein Modell eine Zuweisung von Wahrheitswerten zu den Atomen im Herbrand-Universum ist, die alle Regeln und Fakten des Programms erfüllt.
• Ein Prolog-Programm wird als eine Menge von logischen Sätzen (Fakten und Regeln) betrachtet. Ein Modell für ein Prolog-Programm ist eine Interpretation, die die Bedeutung dieser Sätze erfasst und festlegt, welche Kombinationen von Termen (oder Atomen) wahr sind.

Beitrag zur Interpretation des Programms:

• Das Herbrand-Universum gibt den Rahmen vor, innerhalb dessen Prolog-Abfragen interpretiert werden. Es bestimmt die Menge der möglichen Werte, die Variablen in diesen Abfragen und Regeln annehmen können.
• In unserem Beispiel beinhalten alle Terme des Herbrand-Universums mögliche Werte für X, Y und Z in den Fakten und Regeln, z.B. vater(X, Y) oder elternteil(X, Y).
• Die Modelltheorie stellt sicher, dass die Interpretation (Modell) die Fakten und Regeln des Programms reflektiert. Eine gültige Interpretation für unser Programm wäre eine Zuweisung von Wahrheitswerten zu jedem Atom, die die gegebenen Fakten (vater(heinrich, fritz), vater(fritz, hans), mutter(maria, hans)) und Regeln (elternteil(X, Y) :- vater(X, Y), elternteil(X, Y) :- mutter(X, Y), grossvater(X, Z) :- vater(X, Y), elternteil(Y, Z)) wahr macht.
• Ein Modell bestätigt beispielsweise, dass grossvater(heinrich, hans) wahr ist, weil Heinrich über Fritz (der Vater ist) und Fritz über Hans (sein Elternteil ist) in Beziehung steht.

• Zusammengefasst liefern das Herbrand-Universum und die Modelltheorie die strukturelle und semantische Grundlage für die Ausführung und Interpretation von Prolog-Programmen. Während das Herbrand-Universum den Bereich der möglichen Werte definiert, gewährleistet die Modelltheorie, dass die Interpretation der Beziehungen und Schlussfolgerungen des Programms logisch konsistent ist.

Aufgabe 4)

Angenommen Du hast ein simples Prolog-Programm:

 f(a). f(b). g(c). h(X, Y) :- f(X), g(Y). h(d, e).

Verwende dieses Programm, um die folgenden Aufgaben zu lösen:

a)

Betrachte das Ziel

h(X, Y)

. Demonstriere den Prozess der Unifikation, um die Werte von X und Y zu finden. Welche Schritte sind erforderlich, um eine mögliche Lösung für

h(X, Y)

zu finden? Beschreibe detailliert, wie die Substitutionen durchgeführt werden.

Lösung:

Betrachte das Ziel

h(X, Y)

. Der Prozess der Unifikation zur Bestimmung der Werte von X und Y kann in mehreren Schritten beschrieben werden:

• Zunächst suchen wir eine Regel oder Fakten in unserem Prolog-Programm, die mit dem Ziel

  h(X, Y)

  übereinstimmen.
• Die Regel

  h(X, Y) :- f(X), g(Y)

  könnte eine Übereinstimmung sein. Um diese Regel anzuwenden, müssen wir sicherstellen, dass die Prädikate

  f(X)

  und

  g(Y)

  für bestimmte Werte von X und Y wahr sind.
• Setze zuerst

  f(X)

  auf wahr. Im Programm sind

  f(a)

  und

  f(b)

  wahr. Daher könnten X = a oder X = b sein.
• Nun setze

  g(Y)

  auf wahr. Im Programm ist

  g(c)

  wahr. Daher ist Y = c.
• Da sowohl X = a als auch X = b zu wahren Aussagen führen können, haben wir zwei mögliche Substitutionen:
• X = a, Y = c
• X = b, Y = c
• Zusätzlich gibt es noch den Fakt

  h(d, e)

  , der direkt passt. Dies bedeutet, dass es auch die Lösung:
• X = d, Y = e

Zusammengefasst führen diese Schritte zu den möglichen Lösungen für

h(X, Y)

:

• X = a, Y = c
• X = b, Y = c
• X = d, Y = e

Substitutionen:

• Erste Substitution: X = a, Y = c
• Zweite Substitution: X = b, Y = c
• Dritte Substitution: X = d, Y = e

b)

Angenommen, die Unifikation scheitert im ersten Versuch, erkläre den Backtracking-Prozess mit diesem Prolog-Programm. Was passiert, wenn das erste Ziel

f(X)

in der Regel

h(X, Y) :- f(X), g(Y).

fehlschlägt und wie hilft der Backtracking-Mechanismus, alternative Lösungen zu finden?

Lösung:

Angenommen, die Unifikation scheitert im ersten Versuch, erkläre den Backtracking-Prozess mit diesem Prolog-Programm. Backtracking ist ein entscheidender Mechanismus in Prolog, der verwendet wird, um alternative Lösungen zu finden, wenn ein Ansatz fehlschlägt. Betrachten wir die Regel

h(X, Y) :- f(X), g(Y).

und analysieren diesen Prozess Schritt für Schritt:

• Erstes Ziel: Wir betrachten das Ziel

  h(X, Y)

  . Die Regel

  h(X, Y) :- f(X), g(Y).

  wird ausgewählt, um dieses Ziel zu lösen. Wir müssen dafür

  f(X)

  und

  g(Y)

  erfüllen.
• Unifikation von f(X): Der erste Schritt ist, zu prüfen, ob

  f(X)

  wahr ist. Wir suchen im Programm und finden:

  f(a)

  und

  f(b)

  . Der Unifikationsversuch beginnt mit

  X = a

  .
• Unifikation von g(Y): Dann prüfen wir, ob

  g(Y)

  wahr ist. Im Programm finden wir

  g(c)

  . Daher setzen wir

  Y = c

  . Somit haben wir die erste Lösung:
  • X = a, Y = c
• Backtracking: Angenommen, wir suchen weiter nach zusätzlichen Lösungen. Prolog verwendet Backtracking, um alternative Pfade zu erkunden. Im vorhergehenden Schritt haben wir

  X = a

  gewählt. Prolog wird jetzt versuchen,

  X = b

  zu setzen und prüfen, ob

  f(X)

  mit

  X = b

  erfolgreich ist.
• Alternative Lösung: Mit

  X = b

  und

  g(Y) wahr (d.h. Y = c)

  , erhalten wir die alternative Lösung:
  • X = b, Y = c
• Direkter Fakt: Zudem haben wir den Fakt

  h(d, e)

  , der direkt die Lösung:
  • X = d, Y = e
  liefert.

Zusammengefasst:

• Der Backtracking-Mechanismus überprüft alternative Pfade, wenn die erste Unifikation fehlschlägt oder mehr Lösungen benötigt werden.
• Erste Unifikation:

  X = a, Y = c

• Backtracking und alternative Lösung:

  X = b, Y = c

• Direkter Fakt als Lösung:

  X = d, Y = e