Wissensrepräsentation und -verarbeitung - Exam

Aufgabe 3)

Du hast ein logisches System, in dem Du Fakten und Aussagen ableiten kannst. Die Ableitungsregeln (Schlussregeln) garantieren die Konsistenz und Gültigkeit der abgeleiteten Aussagen. Eine der grundlegendsten Schlussregeln ist der Modus Ponens, der besagt, dass aus den Aussagen If A, then B und A automatisch B folgt.

Ein weiteres Beispiel für eine Schlussregel ist der Modus Tollens. Diese Regel sagt aus, dass aus den Aussagen If A, then B und Not B die Aussage Not A folgt.

a)

Teilaufgabe 1: Wende die Schlussregel Modus Ponens in einem logischen Beweis an. Gegeben sind die Aussagen:

• If it rains, then the ground will be wet
• It is raining

A. Was kann aus diesen beiden Aussagen logisch abgeleitet werden? Begründe Deine Antwort unter Verwendung der Modus Ponens Regel.

Lösung:

Teilaufgabe 1: Wende die Schlussregel Modus Ponens in einem logischen Beweis an. Gegeben sind die Aussagen:

• If it rains, then the ground will be wet
• It is raining

A. Was kann aus diesen beiden Aussagen logisch abgeleitet werden? Begründe Deine Antwort unter Verwendung der Modus Ponens Regel.

Die Aussagen lauten:

• A: Wenn es regnet (A), wird der Boden nass (B).
• B: Es regnet (A).

Die Schlussregel Modus Ponens besagt, dass aus den Aussagen If A, then B und A die Aussage B folgt. Daher kannst Du aufgrund der gegebenen Aussagen logisch ableiten, dass der Boden nass wird.

Formell ausgedrückt:

• Prämisse 1: If A, then B (Wenn es regnet, wird der Boden nass)
• Prämisse 2: A (Es regnet)
• Schlussfolgerung: B (Der Boden wird nass)

Diese Ableitung ist logisch und konsistent gemäß der Modus Ponens Regel.

b)

Teilaufgabe 2: Nutze die Schlussregel Modus Tollens und bestimme die logische Konsequenz aus den folgenden Aussagen:

• If the security system detects an intruder, then the alarm will sound
• The alarm did not sound

A. Was kannst Du aus diesen Aussagen ableiten? Begründe Deine Antwort unter Verwendung der Modus Tollens Regel.

Lösung:

Teilaufgabe 2: Nutze die Schlussregel Modus Tollens und bestimme die logische Konsequenz aus den folgenden Aussagen:

• If the security system detects an intruder, then the alarm will sound
• The alarm did not sound

A. Was kannst Du aus diesen Aussagen ableiten? Begründe Deine Antwort unter Verwendung der Modus Tollens Regel.

Die Aussagen lauten:

• A: Wenn das Sicherheitssystem einen Eindringling erkennt (A), wird der Alarm ausgelöst (B).
• Not B: Der Alarm wurde nicht ausgelöst (¬B).

Die Schlussregel Modus Tollens besagt, dass aus den Aussagen If A, then B und Not B folgt, dass Not A gilt. Daher kannst Du aus den gegebenen Aussagen logisch ableiten, dass das Sicherheitssystem keinen Eindringling erkannt hat.

Formell ausgedrückt:

• Prämisse 1: If A, then B (Wenn das Sicherheitssystem einen Eindringling erkennt, wird der Alarm ausgelöst)
• Prämisse 2: Not B (Der Alarm wurde nicht ausgelöst)
• Schlussfolgerung: Not A (Das Sicherheitssystem hat keinen Eindringling erkannt)

Diese Ableitung ist logisch und konsistent gemäß der Modus Tollens Regel.

Aufgabe 4)

Logisches Schließen

Prozess der Ableitung neuer Fakten aus gegebenen Fakten und Aussagen mithilfe logischer Regeln.

• Aussagenlogik: Formale Sprache. Satzformen: Aussagen (A, B,...).
• Prädikatenlogik: Enthält zusätzlich Quantoren (\(\forall\), \(\exists\)) und Prädikate.
• Regeln: Modus Ponens, Resolution, Einheitsersetzung.
• Prozedures: Vorwärtsverkettung, Rückwärtsverkettung.
• Werkzeuge: SAT-Solver, Theorembeweiser.
• Komplexität: Entscheidend für Effizienz und Anwendbarkeit.
• Ziele: Verifikation, Wissensgewinn, Problemlösung.

a)

Gegeben seien die folgenden logischen Aussagen in der Aussagenlogik:

• A: Es regnet.
• B: Die Straße ist nass.

Angenommen, wir wissen, dass A wahr ist und die Aussage If it rains, then the street is wet (\(A \rightarrow B\)) ebenfalls wahr ist.

• a) Benutze den Modus Ponens, um zu zeigen, ob B wahr ist. Begründe Deine Antwort.
• b) Übersetze die obigen Aussagen in die Prädikatenlogik und formuliere die entsprechenden Quantoren und Prädikate. Verwende \(R(x)\) für 'x regnet' und \(P(x)\) für 'x ist nass'.

Lösung:

• Logisches Schließen

Prozess der Ableitung neuer Fakten aus gegebenen Fakten und Aussagen mithilfe logischer Regeln.

• Aussagenlogik: Formale Sprache. Satzformen: Aussagen (A, B,…).
• Prädikatenlogik: Enthält zusätzlich Quantoren (\(\forall\), \(\exists\)) und Prädikate.
• Regeln: Modus Ponens, Resolution, Einheitsersetzung.
• Prozeduren: Vorwärtsverkettung, Rückwärtsverkettung.
• Werkzeuge: SAT-Solver, Theorembeweiser.
• Komplexität: Entscheidend für Effizienz und Anwendbarkeit.
• Ziele: Verifikation, Wissensgewinn, Problemlösung.

---

Löse die folgende Teilaufgabe:

Gegeben seien die folgenden logischen Aussagen in der Aussagenlogik:

• A: Es regnet.
• B: Die Straße ist nass.

Angenommen, wir wissen, dass A wahr ist und die Aussage If it rains, then the street is wet (A \rightarrow B) ebenfalls wahr ist.

• a) Benutze den Modus Ponens, um zu zeigen, ob B wahr ist. Begründe Deine Antwort.
• b) Übersetze die obigen Aussagen in die Prädikatenlogik und formuliere die entsprechenden Quantoren und Prädikate. Verwende \(R(x)\) für 'x regnet' und \(P(x)\) für 'x ist nass'.

---

• Lösung:
• a) Benutze den Modus Ponens, um zu zeigen, ob B wahr ist. Begründe Deine Antwort.
• Der Modus Ponens besagt: Wenn folgende Aussagen gegeben sind:
• 1. A (Es regnet)
• 2. A → B (Wenn es regnet, ist die Straße nass)

Dann können wir folgern:

• 3. B (Die Straße ist nass)

Da A wahr ist und A → B wahr ist, muss B ebenfalls wahr sein gemäß der Regel des Modus Ponens.

• b) Übersetze die obigen Aussagen in die Prädikatenlogik und formuliere die entsprechenden Quantoren und Prädikate. Verwende \(R(x)\) für 'x regnet' und \(P(x)\) für 'x ist nass'.
• 1. \(\forall x (R(x) \rightarrow P(x))\): Für alle x, wenn x regnet, dann ist x nass.
• 2. \(R(x)\): x regnet.

Da \(R(x)\) wahr ist (es regnet) und \(\forall x (R(x) \rightarrow P(x))\) ebenfalls wahr ist, können wir folgern, dass \(P(x)\) wahr ist (x ist nass).

b)

Angenommen, Du arbeitest an einem Theorembeweiser und hast die folgenden Aussagen erhalten:

• \(\forall x (R(x) \rightarrow \exists y P(y))\)
• \(R(a)\)
• a) Bestimme mithilfe der Vorwärtsverkettung, ob es ein spezifisches \(y\) gibt, das nass ist. Erkläre jeden Schritt.
• b) Bezeichne die Komplexität des Resolutionverfahrens, das für den obigen Prozess einer Entscheidung verwendet wird. Diskutiere, warum die Komplexität eine Rolle spielt.

Lösung:

• Logisches Schließen

Prozess der Ableitung neuer Fakten aus gegebenen Fakten und Aussagen mithilfe logischer Regeln.

• Aussagenlogik: Formale Sprache. Satzformen: Aussagen (A, B,…).
• Prädikatenlogik: Enthält zusätzlich Quantoren (\(\forall\), \(\exists\)) und Prädikate.
• Regeln: Modus Ponens, Resolution, Einheitsersetzung.
• Prozeduren: Vorwärtsverkettung, Rückwärtsverkettung.
• Werkzeuge: SAT-Solver, Theorembeweiser.
• Komplexität: Entscheidend für Effizienz und Anwendbarkeit.
• Ziele: Verifikation, Wissensgewinn, Problemlösung.

---

Löse die folgende Teilaufgabe:

Angenommen, Du arbeitest an einem Theorembeweiser und hast die folgenden Aussagen erhalten:

• \(\forall x (R(x) \rightarrow \exists y P(y))\)
• \(R(a)\)
• a) Bestimme mithilfe der Vorwärtsverkettung, ob es ein spezifisches \(y\) gibt, das nass ist. Erkläre jeden Schritt.
• b) Bezeichne die Komplexität des Resolutionverfahrens, das für den obigen Prozess einer Entscheidung verwendet wird. Diskutiere, warum die Komplexität eine Rolle spielt.

---

• Lösung:
• a) Bestimme mithilfe der Vorwärtsverkettung, ob es ein spezifisches \(y\) gibt, das nass ist. Erkläre jeden Schritt.
• Schritt 1: Ausgangsaussagen identifizieren:
  • Aussage 1: \(\forall x (R(x) \rightarrow \exists y P(y))\)
  • Aussage 2: \(R(a)\)
• Schritt 2: Anwenden der Vorwärtsverkettung:
  • Aussage 2 sagt aus, dass \(R(a)\) wahr ist, also regnet es an Ort a.
  • Da \(\forall x (R(x) \rightarrow \exists y P(y))\) für alle x gilt, setzen wir x = a, das ergibt: \(R(a) \rightarrow \exists y P(y)\).
• Schritt 3: Folgern:
  • Da \(R(a)\) wahr ist, muss gemäß der Aussage \(R(a) \rightarrow \exists y P(y)\) \(\exists y P(y)\) ebenfalls wahr sein.
• Ergebnis: Es existiert ein spezifisches \(y\), sodass \(P(y)\) wahr ist, d.h., es gibt ein y, das nass ist.
• b) Bezeichne die Komplexität des Resolutionverfahrens, das für den obigen Prozess einer Entscheidung verwendet wird. Diskutiere, warum die Komplexität eine Rolle spielt.
• Komplexität des Resolutionverfahrens:Die Komplexität des Resolutionverfahrens in der Prädikatenlogik ist typischerweise unentscheidbar, was bedeutet, dass es keine allgemeine Methode gibt, um in endlicher Zeit zu entscheiden, ob eine gegebene Aussage aus einer Menge von Prämissen folgt. In der Aussagenlogik ist das Resolutionverfahren NP-vollständig.
• Bedeutung der Komplexität:Die Komplexität spielt eine entscheidende Rolle, weil sie die Effizienz und die praktische Anwendbarkeit des Verfahrens beeinflusst. Hohe Komplexität kann zu langen Berechnungszeiten und hohen Speicheranforderungen führen, was die Nutzbarkeit von Theorembeweisern in realen Anwendungen einschränken kann. Insbesondere bei sehr großen Mengen von Prämissen oder komplexen Aussagen kann die Komplexität ein erhebliches Hindernis darstellen.