Wenn $X_1 + X_2 = 10$ und $X_1 - X_2 = 4$,
was ist dann $X_1$?

Historisch war Logik bis 1990 das Hauptparadigma für künstliche Intelligenz.

• Problem: Deterministisch. Kann nicht mit Unsicherheit umgehen (anders: probabilistische Inferenz)
• Problem: Regel-basiert. Kein Fine-tuning aus Daten (anders: Machine Learning)
• Vorteil: Sehr ausdrucksstark

Beispiel:

• Ein Euro ist besser als ein Groschen.
• Ein Groschen ist besser als ein Cent.
• Also ist ein Euro besser als ein Cent.

Beispiel 2:

• Ein Cent ist besser als Nichts.
• Nichts ist besser als Weltfrieden.
• Also ist ein Cent besser als Weltfrieden.

Natürliche Sprache ist ungenau.

Sprachen sind ein Weg um Dinge auszudrücken

Natürliche Sprache (informell)

• Englisch: Two divides even numbers.
• German: Zwei teilt gerade Zahlen

Programmiersprachen (formal)

• Python: def even(x): return x % 2 == 0
• C++: bool even(int x) { return x % 2 == 0; }

Logische Sprachen (formal)

• First-order-logic: $\forall x.\ \text{Even}(x) \to \text{Divides}(x, 2)$

Ziele von logischen Sprachen:

• Wissen repräsentieren
• Aus dem Wissen schlussfolgern

Bausteine

• Syntax: definiert eine Menge valider Aussagen (Formeln / Klauseln)
  Beispiel: $\text{Regen} \wedge \text{Nass}$
• Semantik: für jede Aussage spezifiziere die Bedeutung einer Konfiguration
  Beispiel:

  $\text{Regen}$	$\text{Nass}$	$\text{Regen} \wedge \text{Nass}$
  0	0	0
  1	0	0
  0	1	0
  1	1	1

• Inferenzregeln: Gegeben $f$, welche Aussage $g$ kann ich daraus folgern ($\frac{f}{g}$)
  Beispiel: Aus $\text{Regen} \wedge \text{Nass}$ folgt $\text{Regen}$

Syntax vs Semantik

• Syntax: Was ist ein valider Ausdruck in der Sprache?
• Semantik: Was bedeutet ein solcher Ausdruck?

Unterschiedliche Syntax, gleiche Semantik:
$2 + 3 \Leftrightarrow 3 + 2$
(jeweils 5)

Gleiche Syntax, unterschiedliche Semantik:
3/2 (Python 2.7) $\not\Leftrightarrow$ 3/2 (Python 3)
(1 vs 1.5)

• Aussagenlogik (nur mit Horn-Klauseln)
• Aussagenlogik
• Modallogik
• Prädikatenlogik erster Stufe (nur mit Horn-Klauseln)
• Prädikatenlogik erster Stufe
• Prädikatenlogik zweiter Stufe
• ...

Tradeoff: Ausdrucksstärke vs (rechentechnische) Effizienz

Syntax

• Symbole (elementare Aussagen, Atome): $A, B, C$
• Logische Verknüpfungen: $\neg, \wedge, \vee, \to, \leftrightarrow$

Wenn $f$ und $g$ Aussagen sind, dann gibt es auch folgende Aussagen:

• Negation: $\neg f$
• Konjunktion: $f \wedge g$
• Disjunktion: $f \vee g$
• Implikation: $f \to g$
• Bikonditional: $f \leftrightarrow g$

Können rekursiv Aussagen aufbauen:
$\neg f \wedge g \to \neg f \vee \neg g$

• Aussage: $A$
• Aussage: $\neg A$
• Aussage: $\neg B \to C$
• Aussage: $\neg A \wedge (\neg B \to C) \vee (\neg B \vee D)$
• Aussage: $\neg \neg A$
• Keine Aussage: $A \neg B$
• Keine Aussage: $A + B$

Wichtig: Eine Aussage allein ist nur eine Menge Symbole
Ohne Semantik haben diese noch keine Bedeutung

Syntax

• Symbole $A$
• Aussagen $f$
• Verknüpfungen $\neg, \wedge, \ldots$

Eine Interpretation (oder model) $w$ in der Aussagenlogik ist eine Zuweisung von Wahrheitswerten zu den Symbolen.

Beispiel:

• 3 Symbole $A, B, C$
• $2^3 = 8$ mögliche Interpretationen $w$:

  $A$	$B$	$C$
  0	0	0
  0	0	1
  0	1	0
  0	1	1
  1	0	0
  1	0	1
  1	1	0
  1	1	1

Syntax

• Symbole $A$
• Aussagen $f$
• Verknüpfungen $\neg, \wedge, \ldots$

Semantik

• Interpretation $w$

Sei $f$ eine Aussage und $w$ eine Interpretation.

Eine Auswertefunktion (Interpretationsfunktion) $\mathcal{I}(f, w)$ gibt zurück:

• True (1): $w$ erfüllt $f$.
• False (0): $w$ erfüllt $f$ nicht.

Die Auswertefunktion definiert meine Semantik

Einfacher Fall:

Für ein atomares Symbol $p$ (z.B. $A, B, C$) gilt: \[ \mathcal{I}(p, w) = w(p) \]

$p = \text{Regen}$, $w = \{ \text{Regen}: 1 \}$,
$\mathcal{I}(p, w) = 1$

Rekursiver Fall:

Für zwei Aussagen $f$ und $g$ definiere:

Das ist die gesamte Semantik unserer Logik.

Aussage: $f = (\neg A \wedge B) \leftrightarrow C$

Interpretation: $w = \{A: 1, B: 1, C: 0\}$

Syntax

• Symbole $A$
• Aussagen $f$
• Verknüpfungen $\neg, \wedge, \ldots$

Semantik

• Interpretation $w$
• Auswertefunktion $\mathcal{I}$

Aussage: $f = \text{Regen} \vee \text{Nass}$

Interpretationen: \[ \mathcal{M}(f) = \{\\ \{\text{Regen}: 1, \text{Nass}: 0 \},\\ \{\text{Regen}: 0, \text{Nass}: 1 \},\\ \{\text{Regen}: 1, \text{Nass}: 1 \} \} \]

Syntax

• Symbole $A$
• Aussagen $f$
• Verknüpfungen $\neg, \wedge, \ldots$

Semantik

• Interpretation $w$
• Auswertefunktion $\mathcal{I}$
• Interpretationen $\mathcal{M}(f)$

Sei $\text{KB} = \{ \text{Regen} \vee \text{Schnee}, \text{Verkehr} \}$.

$\mathcal{M}(\text{Regen}) = \{\\ \{\text{Regen}: 1, \text{Nass}: 0\},\\ \{\text{Regen}: 1, \text{Nass}: 1\}\}$

$\mathcal{M}(\text{Regen} \to \text{Nass}) = \{\\ \{\text{Regen}: 0, \text{Nass}: 0\},\\ \{\text{Regen}: 0, \text{Nass}: 1\},\\ \{\text{Regen}: 1, \text{Nass}: 1\}\}$

$\mathcal{M}(\text{Regen}, \text{Regen} \to \text{Nass}) = \{\\ \{\text{Regen}: 1, \text{Nass}: 1\}\}$

Mit der Zeit fügen wir neue Aussagen zu unserer knowledge base hinzu: \[ \text{KB} \Rightarrow \text{KB} \cup \{ f \} \]

Damit schrumpft die Menge möglicher Interpretationen: \[ \mathcal{M}(\text{KB}) \Rightarrow \mathcal{M}(\text{KB}) \cap \mathcal{M}(f) \]

Wie stark schrumpft die Menge an Interpretationen?

Implikation (Entailment)

$f$ gibt uns keine neue Information (war bereits bekannt)

Beispiel: $$\text{Verkehr} \wedge \text{Schnee} \vDash \text{Schnee}$$

Widerspruch (Contradiction)

$f$ widerspricht unserem Wissen.

Beispiel:
$\text{Verkehr} \wedge \text{Schnee}$ widerspricht $\neg\text{Schnee}$

Kontingenz (Contingency)

$f$ gibt uns neue, nicht triviale Information zu $\text{KB}$.

$\emptyset \subsetneq \mathcal{M}(\text{KB}) \cap \mathcal{M}(f) \subsetneq \mathcal{M}(\text{KB})$

Beispiel:
$\text{Verkehr}$ und $\text{Schnee}$.

Unsere knowledge base soll eine Methode $\text{Tell}[f]$ bekommen mit der wir Fakten hinzufügen können.

$\text{Tell}[\text{Regen}]$
Tell: "Es regnet."

Mögliche Antworten:

• Weiß ich bereits: $\text{KB} \vDash f$
• Glaube ich nicht: $\text{KB} \vDash \neg f$
• Ich habe etwas gelernt: Update $\text{KB}$.

Wir wollen eine Methode haben, um der knowledge base Fragen zu stellen: $\text{Ask}[f]$

$\text{Ask}[\text{Regen}]$
Ask: "Regnet es?"

Mögliche Antworten:

• Ja: $\text{KB} \vDash f$
• Nein: $\text{KB} \vDash \neg f$
• Weiß ich nicht: Kontingenz

Bayesian Network als Generalisierung

Wir haben keine Menge von Interpretationen, sondern eine Verteilung über mögliche Assignments.

$w$ $P(W = w)$ $\{A : 0, B: 0, C: 0\}$ $0.3$ $\{A : 0, B: 0, C: 1\}$ $0.1$ ...

\[ P(f | \text{KB}) = \frac{\sum_{w \in \mathcal{M}(\text{KB} \cup \{f\})} P(W = w)}{\sum_{w \in \mathcal{M}(\text{KB})} P(W = w)} \]

\[ P(f | \text{KB}) = \frac{\sum_{w \in \mathcal{M}(\text{KB} \cup \{f\})} P(W = w)}{\sum_{w \in \mathcal{M}(\text{KB})} P(W = w)} \]

• $0$: Nein
• $1$: Ja
• $>0, < 1$: Weiß ich nicht

Können die Antwort für "Ask" und "Tell" reduzieren auf Erfüllbarkeit:

SAT können wir schon lösen (siehe CSPs)!

• Variable $\Leftarrow$ Symbol
• Contraint / Factor $\Leftarrow$ Aussage
• Assignment $\Rightarrow$ Interpretation

Beispiel: $\text{KB} = \{ A \vee B, B \leftrightarrow \neg C \}$

• Symbole / Variablen: $\{A, B, C\}$
• Factor Graph:
• Konsistentes Assignment: $\{A: 1, B: 0, C:1 \}$.

Die bisherigen Aussagen können immer für den SAT Solver in Conjunctive Normalform (CNF) überführt werden:

Können SAT solver nutzen um die Antworten zu generieren

Können wir noch mehr machen?

Konzept: Schlussfolgern (Inference)

Beispiel: Schlussfolgern

• Es regnet. ($\text{Regen}$)
• Wenn es regnet, dann ist es nass.
  ($\text{Regen} \to \text{Nass}$)
• Also ist es nass. ($\text{Nass}$)

$$\frac{\text{Regen}, \text{Regen} \to \text{Nass}}{\text{Nass}} \qquad \frac{\text{(Prämisse)}}{\text{(Konklusion)}}$$

Eine Schlussregel hat immer die Form $$ \frac{f_1, f_2, \ldots, f_k}{g} $$

Schlussregeln operieren nur auf der Syntax (und brauchen keine Semantik)

Eine knowledge base $\text{KB}$ beweist $f$ ($\text{KB} \vdash f$), wenn $f$ irgendwann zu $\text{KB}$ hinzugefügt wird.

• $\text{KB} = \{\text{Regen}, \text{Regen} \to \text{Nass}, \text{Nass} \to \text{Rutschig} \}$
• Modus ponens ($\text{Regen}$ und $\text{Regen} \to \text{Nass}$):
  $\text{KB} = \{\text{Regen}, \text{Regen} \to \text{Nass}, \text{Nass} \to \text{Rutschig}, {\color{red} \text{Nass}} \}$
• Modus ponens ($\text{Nass}$ und $\text{Nass} \to \text{Rutschig}$):
  $\text{KB} = \{\text{Regen}, \text{Regen} \to \text{Nass}, \text{Nass} \to \text{Rutschig}, {\color{red} \text{Nass}}, {\color{red} \text{Rutschig}} \}$

Semantik

Implikation / Entailment $\text{KB} \vDash f$ ist definiert durch die Interpretation.

Wie verhält sich $\{ f: \text{KB} \vDash f \}$ zu $\{ f: \text{KB} \vdash f \}$?

$\{ f: {\color{blue} \text{KB} \vDash f} \}$ ist die (semantische) Wahrheit

• Gültigkeit: Nichts als die Wahrheit
• Vollständigkeit: Die ganze Wahrheit

Idealerweise wollen wir: die ganze Wahrheit und nichts als die Wahrheit.

Ist $\frac{p, p \to q}{q}$ (Modus ponens) gültig?

Gültig!

Ist $\frac{q, p \to q}{p}$ gültig?

Ungültig!

Ist Modus ponens vollständig?

Wie kommen wir zur Vollständigkeit?

1. Restriktivere Menge an Aussagen
   (Aussagenlogik nur mit Horn-Formeln)
2. Stärkere Schlussregeln

Definite Klauseln:

• $(\text{Regen} \wedge \text{Schnee}) \to \text{Verkehr}$
• $\text{Verkehr}$

Nicht definite Klauseln:

• $\neg \text{Verkehr}$
• $(\text{Regen} \wedge \text{Schnee}) \to (\text{Verkehr} \vee \text{Homeoffice})$

Beispiele:

• $(\text{Regen} \wedge \text{Schnee}) \to \text{Verkehr}$
• $(\text{Verkehr} \wedge \text{Homeoffice}) \to \text{false}$
  äquivalent: $\neg(\text{Verkehr} \wedge \text{Homeoffice})$
  oder: $\neg \text{Verkehr} \vee \neg \text{Homeoffice}$

Beispiel:

Wenn $\text{KB}$ nur Horn-Klauseln enthält, dann ist
$\text{KB} \vDash p$ äquivalent zu $\text{KB} \vdash p$.

Frage: $\text{KB} \vDash \text{Verkehr} \quad\Leftrightarrow\quad \text{KB} \vdash \text{Verkehr}$

Durch die Einschränkung auf Horn-Klauseln wird Modus ponens vollständig.

Aber wir können einige Dinge (z.B. "entweder oder") nicht darstellen.

Bausteine für eine Logik

• Syntax: Was sind erlaubte Aussagen?
  $\text{Regen} \wedge \text{Nass}$
• Semantik: Welche Interpretationen $\mathcal{M}(f)$ lässt eine Aussage zu?
  

  		$\text{Regen}$
  		0	1
  $\text{Nass}$	0
  	1

• Schlussregeln: Welche neuen Aussagen können wir aus $\text{KB}$ schließen?
  Aus $\text{Regen} \wedge \text{Nass}$ schließe $\text{Regen}$

Inferenz Algorithmus:
Wende Schlussregeln immer wieder auf $\text{KB}$ an.

• Zulässige Regeln: Bewiesene Aussagen sind semantisch korrekt
• Volländige Regeln: Wir können alle korrekten Aussagen beweisen

Horn-Klauseln als Disjunktion

• Literal: Entweder $p$ oder $\neg p$ für ein Symbol $p$
• Klausel: Disjunktion von Literalen
• Horn-Klausel: Klausel mit maximal einem positiven Literal

Modus ponens für Disjunktionen

\[ \frac{A, \neg A \vee C}{C} \]

Intuition: $A$ und $\neg A$ heben sich auf.

Resolution (Robinson, 1965)

Beispiel: \[ \frac{\text{Regen} \vee {\color{red} \text{Schnee}}, \quad {\color{red} \neg \text{Schnee}} \vee \text{Verkehr}}{\text{Regen} \vee \text{Verkehr}} \]

Ist Resolution gültig?

$\frac{f \vee p, \quad \neg p \vee g}{f \vee g}$

Resolution ist gültig!

Resolution funktioniert nur auf Klauseln - aber das reicht uns

Beispiel: $(A \vee B \vee \neg C) \wedge (\neg B \vee D)$

Äquivalent zu einer knowledge base nur mit Klauseln.

• $(\text{Sommer} \to \text{Schnee}) \to \text{Merkwürdig}$
• $(\neg \text{Sommer} \vee \text{Schnee}) \to \text{Merkwürdig}$
  (Implikation ersetzen)
• $\neg (\neg \text{Sommer} \vee \text{Schnee}) \vee \text{Merkwürdig}$
  (Implikation ersetzen)
• $(\neg \neg \text{Sommer} \wedge \neg \text{Schnee}) \vee \text{Merkwürdig}$
  (de Morgan'sche Regel)
• $(\text{Sommer} \wedge \neg \text{Schnee}) \vee \text{Merkwürdig}$
  (Doppelte Negation entfernen)
• $(\text{Sommer} \vee \text{Merkwürdig}) \wedge (\neg \text{Schnee} \vee \text{Merkwürdig})$
  ($\vee$ in die Klammer ziehen)

Ersetzungsregeln

• Eliminiere $\leftrightarrow$: $\frac{f \leftrightarrow g}{(f \to g) \wedge (g \to f)}$
• Eliminiere $\to$: $\frac{f \to g}{(\neg f \vee g)}$
• $\neg$ in die Klammer ziehen (1): $\frac{\neg (f \wedge g)}{(\neg f \vee \neg g)}$
• $\neg$ in die Klammer ziehen (2): $\frac{\neg (f \vee g)}{(\neg f \wedge \neg g)}$
• Eliminiere doppelte Negation: $\frac{\neg \neg f}{f}$
• $\vee$ in die Klammer ziehen: $\frac{f \vee (g \wedge h)}{(f \vee g) \wedge (f \vee h)}$

Wir können nun Resolution verwenden um auf Entailment zu testen

$\text{KB} \vDash f \quad \Leftrightarrow \quad \text{KB} \cup \{ \neg f \}$ ist nicht erfüllbar.

"Beweis durch Widerspruch"

Beispiel

• $\text{KB} = \{A \to (B \vee C), A, \neg B \}, f = C$
• $\text{KB}' = \{A \to (B \vee C), A, \neg B, \neg C \}$
• $\text{KB}' = \{\neg A \vee B \vee C, A, \neg B, \neg C \}$

$\text{KB} \vDash C$

Jede Anwendung der Regel produziert Klausel mit einem Symbol.
Lineare Zeit

Jede Anwendung produziert Klausel mit mehreren Symbolen.
Exponentielle Zeit

Zusammenfassung (Aussagenlogik)

Grenzen der Aussagenlogik

• Alice und Bob verstehen Arithmetik
  $\text{AliceVerstehtArithmetik} \wedge \text{BobVerstehtArithmetik}$
• Alle Studierenden verstehen Arithmetik
  $\text{AliceStudiert} \to \text{AliceVerstehtArithmetik}$
  $\text{BobStudiert} \to \text{BobVerstehtArithmetik}$
  ...
• Jede gerade ganze Zahl größer 2 ist die Summe von zwei Primzahlen
  ???

Was fehlt uns?

• Objekte und Prädikate:
  Aussagen ($\text{AliceVerstehtArithmetik}$) haben mehr interne Struktur ($\text{alice}$, $\text{Versteht}$, $\text{arithmetik}$)
• Quantoren und Variablen:
  Wollen Aussagen über "alle" Dinge machen können ohne alle aufzuzählen.

Prädikatenlogik (erster Stufe)

• Alice und Bob verstehen Arithmetik
  $\text{Versteht}(\text{alice}, \text{arithmetik}) \wedge \text{Versteht}(\text{bob}, \text{arithmetik}) $
• Alle Studierenden verstehen Arithmetik
  $\forall x\; \text{Studiert}(x) \to \text{Versteht}(x, \text{arithmetik})$

Syntax

Terme

• Konstanten (z.B.: $\text{arithmetik}$)
• Variablen (z.B.: $x$)
• Funktionen von Termen (z.B.: $\text{Summe}(3, x)$)

Aussagen

• Atomare Ausdrücke: Prädikate angewendet auf Terme
  (z.B.: $\text{Versteht}(x, \text{arithmetik})$)
• Verknüpfungen von Ausdrücken
  (z.B.: $\text{Studiert}(x) \to \text{Versteht}(x, \text{arithmetik})$)
• Quantoren angewendet auf Ausdrücke
  (z.B.: $\forall x\; \text{Studiert}(x) \to \text{Versteht}(x, \text{arithmetik})$)

Quantoren

• Allquantor
  Konjunktion aller möglichen Werte:
  $\forall x\; P(x)$ entspricht $P(A) \wedge P(B) \wedge \ldots$
• Existenzquantor
  Disjunktion aller möglichen Werte:
  $\exists x\; P(x)$ enstpricht $P(A) \vee P(B) \vee \ldots$

de Morgan'sche Regel für Quantoren:
$\neg \forall x\; P(x)$ entspricht $\exists x\; \neg P(X)$

Achtung:
$\forall x\; \exists y\; P(x,y)$ ist nicht gleich $\exists y\; \forall x\; P(x,y)$.

• Es gibt eine Studierende, die Arithmetik versteht
  $\exists x\; \text{Studiert}(x) \wedge \text{Versteht}(x, \text{arithmetik})$
• Alle Studierenden verstehen Arithmetik
  
  $\forall x\; \text{Studiert}(x) \wedge \text{Versteht}(x, \text{arithmetik})$ $\forall x\; \text{Studiert}(x) \to \text{Versteht}(x, \text{arithmetik})$

Es gibt einen Kurs, den alle Studierenden belegt haben.

\[ \exists y\; \text{Kurs}(y) \wedge (\forall x\; \text{Studiert}(x) \to \text{Belegt}(x, y)) \]

Jede gerade ganze Zahl größer 2 ist die Summe zweier Primzahlen.

\[ \forall x\; (\text{GeradeGanzeZahl}(x) \wedge \text{Größer}(x, 2)) \to\\ ( \exists y\; \exists z\; \text{Gleich}(x, \text{Summe}(y,z)) \wedge \text{Prim}(y) \wedge \text{Prim}(z)) \]

Wenn ein Studierender einen Kurs belegt und der Kurs ein Konzept behandelt, dann versteht der Studierende das Konzept.

\[ \forall x\; \forall y\; \forall z\; (\text{Studiert}(x) \wedge \text{Belegt}(x, y) \wedge \text{Kurs}(y) \wedge\\ \text{Behandelt}(y, z)) \to \text{Versteht}(x,z) \]

Wie funktioniert die Semantik für Prädikatenlogik?

Aussagenlogik: Interpretation $w$ mappt Symbole auf Wahrheitswerte
$w = \{\text{AliceVerstehtArithmetik}: 1,\\ \text{BobVerstehtArithmetik}: 0\}$

Für Prädikatenlogik müssen wir die Beziehungen aus den Prädikaten abbilden

Graphische Variante einer Interpretation

Angenommen wir haben nur unäre und binäre Prädikate.

• Knoten sind Objekte, Label sind Konstanten.
• Unäre Prädikate sind zusätzliche Label.
• Binäre Prädikaten sind Kanten.

Alice und Bob sind Studierende
$\text{Studiert}(\text{alice}) \wedge \text{Studiert}(\text{bob})$

$w_1$

$w_2$

$w_3$

• Unique names: Jedes Objekt hat maximal eine Konstante (verbietet $w_2$)
• Domain closure: Jedes Objekt hat mindestens eine Konstante (verbietet $w_3$)

Mit dem 1:1 Mapping können wir Aussagen der Prädikatenlogik zu Aussagen der Aussagenlogik übersetzen

Wie kommen wir zu Schlussregeln für Prädikatenlogik?

Definite Klauseln

Aussagenlogik: $$ (p_1 \wedge \ldots \wedge p_k) \to q $$

Müssen Quantoren und Prädikate berücksichtigen: \[ \forall x\; \forall y\; \forall z\; (\text{Studiert}(x) \wedge \text{Belegt}(x, y) \wedge \text{Kurs}(y) \wedge\\ \text{Behandelt}(y, z)) \to \text{Versteht}(x,z) \]

• Gegeben: $P(\text{alice})$ und $\forall x\; P(x) \to Q(x)$.
• $P(x)$ und $P(\text{alice})$ matchen nicht - können also nicht $Q(\text{alice})$ schließen!
• Brauchen Konzept um Variablen und Konstanten zu matchen.

Substitution

Idee: Find & Replace

• $\text{Subst}[\{x / \text{alice}\}, P(x)] = P(\text{alice})$
• $\text{Subst}[\{x / \text{alice}, y / z\}, P(x) \wedge K(x, y)] =\\ P(\text{alice}) \wedge K(\text{alice}, z)$

Unification

Idee: Finde passende Substitution für zwei Aussagen

• $\text{Unify}[\text{Versteht}({\color{red}\text{alice}}, \text{arithmetik}), \text{Versteht}({\color{red} x}, \text{arithmetik})] = \{{\color{red} x / \text{alice}}\}$
• $\text{Unify}[\text{Versteht}({\color{red}\text{alice}}, {\color{blue} y}), \text{Versteht}({\color{red} x}, {\color{blue} z})] = \{{\color{red} x / \text{alice}}, {\color{blue} y / z}\}$
• $\text{Unify}[\text{Versteht}({\color{red}\text{alice}}, {\color{blue} y}), \text{Versteht}({\color{red} \text{bob}}, {\color{blue} z})] = \text{fail}$
• $\text{Unify}[\text{Versteht}({\color{red}\text{alice}}, {\color{blue} y}), \text{Versteht}({\color{red} x}, {\color{blue} F(x)})] = \{{\color{red} x / \text{alice}}, {\color{blue} y / F(\text{alice})}\}$

Die Substitution sollte "klein" sein (und keine unnötigen Ersetzungen machen).

Knowledge base

• $\text{Belegt}(\text{alice}, \text{kigru})$
• $\text{Behandelt}(\text{kigru}, \text{mdp})$
• $\forall x\; \forall y\; \forall z\; \text{Belegt}(x, y) \wedge \text{Behandelt}(y, z) \to \text{Versteht}(x, z)$

Schluss mit Modus ponens

• $\theta = \{x / \text{alice}, y / \text{kigru}, z / \text{mdp} \}$
• Schlussfolgere $\text{Versteht}(\text{alice}, \text{mdp})$

Laufzeit

• Jede Applikation von Modus ponens produziert eine atomare Aussage
• Ohne Funktionen ist die Anzahl an atomaren Aussagen maximal \[ \text{AnzahlKonstanterSymbole}^\text{MaximalePrädikatArity} \]

  $\forall x\; \forall y\; \forall z\; P(x,y,z)$, mit 100 Konstanten $\Rightarrow$ $100^3 = 1000000$ Möglichkeiten

Laufzeit

Mit Funktionen haben wir unendlich viele Möglichkeiten \[ Q(a),\quad Q(F(a)),\quad Q(F(F(a))), \ldots \]

Wie adaptieren wir Resolution?

$\forall x\; \text{Studiert}(x) \to \exists y\; \text{Versteht}(x, y)$

Ansatz (analog zur Aussagenlogik)

• Konvertiere alle Aussagen nach CNF.
• Wende Resolution Regel an.

Konversion nach CNF ist mechanisch möglich (mit zusätzlichen Schritten)

Beispiel: "Jeder, der alle Tiere mag, wird von jemandem gemocht"

• $\forall x\; (\forall y\; \text{Tier}(y) \to \text{Mag}(x, y)) \to \exists y\; \text{Mag}(y, x)$
• $\forall x\; \neg(\forall y\; \neg\text{Tier}(y) \vee \text{Mag}(x, y)) \vee \exists y\; \text{Mag}(y, x)$
  (Implikationen ersetzen)
• $\forall x\; (\exists y\; \text{Tier}(y) \wedge \neg \text{Mag}(x, y)) \vee \exists y\; \text{Mag}(y, x)$
  ($\neg$ nach innen ziehen)

• $\forall x\; (\exists y\; \text{Tier}(y) \wedge \neg \text{Mag}(x, y)) \vee \exists y\; \text{Mag}(y, x)$
  ($\neg$ nach innen ziehen)
• $\forall x\; (\exists y\; \text{Tier}(y) \wedge \neg \text{Mag}(x, y)) \vee \exists z\; \text{Mag}(z, x)$
  (Standardisiere Variablen)
• $\forall x\; (\text{Tier}(Y(x)) \wedge \neg \text{Mag}(x, Y(x))) \vee \text{Mag}(Z(x), x)$
  (Existenzquantor durch Skolem-Funktionen ersetzen)
• $\forall x\; (\text{Tier}(Y(x)) \vee \text{Mag}(Z(x), x)) \wedge (\neg \text{Mag}(x, Y(x)) \vee \text{Mag}(Z(x), x))$
  ($\vee$ nach innen ziehen)
• $(\text{Tier}(Y(x)) \vee \text{Mag}(Z(x), x)) \wedge (\neg \text{Mag}(x, Y(x)) \vee \text{Mag}(Z(x), x))$
  (Entferne Allquantor)

Beispiel

\[ \frac{\neg \text{Tier}(x) \vee \text{Mag}(Y(x), x), \quad \neg \text{Mag}(u, v) \vee \text{Füttert}(u, v)} {\neg \text{Tier}(x) \vee \text{Füttert}(Y(x), x)} \]

Substitution $\theta = \{ u / Y(x), v / x \}$

• Prädikatenlogik erlaubt kein Model Checking.
• Modus ponens und Resolution lassen sich adaptieren.
  • Substitution
  • Unification

• Prädikatenlogik erster Stufe erlaubt Quantoren über Objekte: $\exists x\; \text{Studiert}(x)$
• Prädikatenlogik zweiter Stufe erlaubt Quantoren über Prädikate (erster Stufe): $\exists P\; P(\text{alice})$
• Prädikatenlogik höherer Stufe erlauben analog Quantoren über Prädikate beliebiger Stufe