TU Wien:Einführung in wissensbasierte Systeme VU (Egly)/Prüfung 2014-03-28/Beispiel 1

Logikbasierte Wissensrepräsentation

Teilaufgabe a)

Die prädikatenlogische Sprache der Arithmetik besteht aus einem einstelligen Funktionsymbol $s$ (Nachfolger) zwei zweistelligen Funktionssymbolen $+$ und $\ast$, einem Konstanntensymbol $0$. Weiters ist die zweistellige Gleichheitsrelation $=$ vorhanden. Die Sprache der Arithmetik kann verwendet werden, um die Theorie der natürlichen Zahlen zu axiomatisieren. Dabei betrachten wir eine Zahl $n$ als den Term $s(s(\mathrm{...}s(0))\mathrm{...}))$ (n mal)

Drücken Sie jede der folgenden Aussagen in der Sprache der Arithmetik aus, oder erklären Sie kurz, warum dies nicht möglich ist.

Unterpunkt 1)

Eine Zahl $y$ teilt eine Zahl $x$, wenn es ein $y$ gibt mit $x=y\ast z$.

Lösungsvorschlag:

$\mathrm{\forall }x\mathrm{\exists }y(\text{divides}(x,y)<=>\mathrm{\exists }z(=(x,\ast (z,y))))$

Unterpunkt 2)

Keine Zahl hat Null als Nachfolger

Lösungsvorschlag:

$\mathrm{\forall }x\mathrm{\neg }(=(0,s(x))$

Unterpunkt 3)

Jede Zahl hat höchstens einen Nachfolger

Lösungsvorschlag:

$\mathrm{\forall }x,y,z((=(y,s(x))\wedge =(z,s(x)))⟹=(y,z))$

Unterpunkt 4)

Eine Zahl $x$ ist kleiner als eine Zahl $y$, wenn es ein $z\ne 0$ gibt, sodass $y=x+z$ (wir schreiben $x<y$)

Lösungsvorschlag:

$\mathrm{\forall }x\mathrm{\forall }y\mathrm{\exists }z((\mathrm{\neg }=(0,z)\wedge =(y,+(x,z)))⟹x<y)$

Unterpunkt 5)

Jede Menge von Zahlen hat ein kleinstes Element

Lösungsvorschlag:

Geht nicht, da zum Beispiel die Menge der natürlichen Zahlen kein kleinstes Element besitzt

Kommentar von --JasonLeroy (Diskussion) 20:41, 4. Mai 2014 (CEST): Diese Begründung hat einen Haken: Die natürlichen Zahlen haben je nach Definition als kleinstes Element 0 bzw. 1. Ich vermute, das Problem liegt darin, dass wir keine Menge von Zahlen beschreiben können. Wir müssten unsere verwendeten Variablen $x,y$ in $\mathrm{\forall }x\mathrm{\exists }y$ einschränken, vielleicht so: $x,y\in \varphi$ und $\varphi \subseteq \mathbb{N}$. Aber ich glaube nicht, dass das erwünscht ist.

Unterpunkt 6)

Jede von $0$ verschiedene Zahl hat einen Nachfolger. Der Nachfolger einer Zahl ist immer größer als die Zahl selbst.

Lösungsvorschlag:

Geht nicht da es kein Prädikat 'größer als' in der Arithmetik gibt.

Lösungsvorschlag unter Verwendung von Punkt 4, --JasonLeroy (Diskussion) 20:48, 4. Mai 2014 (CEST)

$\mathrm{\forall }x(\mathrm{\neg }=(x,0)⟹\mathrm{\exists }y(=(s(x),y)\wedge x<y))$

Unterpunkt 7)

Eine Zahl heißt gerade, wenn sie durch Zwei teilbar ist.

Lösungsvorschlag:

$\mathrm{\forall }x(\text{even}(x)<=>\mathrm{\exists }y(=(x,\ast (y,s(s(0))))))$

Lösungsvorschlag unter Verwendung von Punkt 1, --JasonLeroy (Diskussion) 20:51, 4. Mai 2014 (CEST)

$\mathrm{\forall }x(divides(x,2)\to even(x))$

Lösungsvorschlag unter Verwendung von Punkt 1, --MartinW (Diskussion) 10:50, 16. März 2017 (CEST)

$\mathrm{\forall }x(divides(x,s(s(0)))\to even(x))$

Unterpunkt 8)

Ein Zahl ist eine Primzahl, wenn sie nur sich selbst und Eins als Teilbar hat und überdies hinaus größer als Eins ist.

Lösungsvorschlag von Msio:

Geht nicht da es kein Prädikat zur Division gibt.

Lösungsvorschlag unter Verwendung von Punkt 1, --JasonLeroy (Diskussion) 20:56, 4. Mai 2014 (CEST)

Angepasst nach dem Kommentar von LigicRolli am 24. Jan 2015

$\mathrm{\forall }x((divides(x,1)\wedge divides(x,x)\wedge \mathrm{\neg }\mathrm{\exists }y(divides(x,y)\wedge \mathrm{\neg }=(x,y)))\to prim(x))$

Lösungsvorschlag von LogicRolli: Denke die Formel vom Jason ist falsch da er sagt es gibt überhaupt kein y was x teilt.

$\mathrm{\forall }x(prim(x)\leftrightarrow \mathrm{\exists }y(divides(x,y)\wedge \mathrm{\neg }(=(y,0))\wedge (=(y,s(0))\vee =(y,x))))$

Unterpunkt 9)

Zu jeder Zahl gibt es eine größere Zahl.

Lösungsvorschlag:

Kann man nicht definieren da es Mengen gibt die nur aus begrenzt vielen Zahlen besteht sodass es ein größtes Element gibt.

Lösungsvorschlag unter Verwendung von Punkt 4, --JasonLeroy (Diskussion) 20:58, 4. Mai 2014 (CEST)

(für die Menge der natürlichen Zahlen und keine Untermenge o.ä.)

$\mathrm{\forall }x\mathrm{\exists }y(x<y)$

Lösungsvorschlag von posthuman:

$\mathrm{\forall }x\mathrm{\exists }y\mathrm{\exists }z(=(+(x,z),y)\wedge \mathrm{\neg }=(z,0))$

Lösungsvorschlag von ree5:

$\mathrm{\forall }x\mathrm{\exists }y(=(y,s(x)));x,y\in \mathbb{N}$

Teilaufgabe b)

Man Zeige, dass aus $\psi \models \varphi$ und $\mathrm{\neg }\psi \models \varphi$ immer $\models \varphi$ folgt. Zeigen Sie ferner, dass aus $\models \psi$ und $\psi \models \varphi$ auch $\models \varphi$ folgt. Wenn Sie zusätzliche Theoreme aus Vorlesung verwenden, so müssen sie diese beweisen.

Lösungsvorschlag: --JasonLeroy (Diskussion) 21:30, 4. Mai 2014 (CEST)

Wir wollen zeigen, dass $(\psi \to \varphi )\wedge (\mathrm{\neg }\psi \to \varphi )\models \mathrm{\top }\to \varphi$ gültig ist. In diesem Fall können wir das TC1 für das Gegenbeispiel bilden. Wir vereinfachen erst:

$\begin{array}{c}\mathrm{\neg }[((\psi \to \varphi )\wedge (\mathrm{\neg }\psi \to \varphi ))\models \mathrm{\top }\to \varphi ]\\ \mathrm{\neg }[((\mathrm{\neg }\psi \vee \varphi )\wedge (\psi \vee \varphi ))\to (\mathrm{\neg }\mathrm{\top }\vee \varphi )]\\ ((\mathrm{\neg }\psi \vee \varphi )\wedge (\psi \vee \varphi ))\wedge \mathrm{\neg }(\mathrm{\neg }\mathrm{\top }\vee \varphi )\\ ((\mathrm{\neg }\psi \vee \varphi )\wedge (\psi \vee \varphi ))\wedge (\mathrm{\top }\wedge \mathrm{\neg }\varphi )\\ \end{array}$

Im Tableau:

$(\mathrm{\neg }\psi \vee \varphi )\wedge (\psi \vee \varphi )$ $\mathrm{\top }\wedge \mathrm{\neg }\varphi$
$\mathrm{\neg }\psi \vee \varphi$ $\psi \vee \varphi$ $\mathrm{\top }$ $\mathrm{\neg }\varphi$
$\mathrm{\neg }\psi$		$\varphi$ CLASH
$\psi$ CLASH	$\varphi$ CLASH

TODO Der zweite Teil fehlt noch. Vermutlich sollten aber beide Teile ohne TC1 gemacht werden, ich weiß aber nicht genau, wie man das dann aufschreiben soll.

Teilaufgabe c)

Kreuzen Sie Zutreffendes an:

1. Nur erfüllbare Formeln sind gültig wahr ☐ falsch ☐
2. $\text{Cn}:\text{Formulas}\to \text{Formulas}$ d.h. $\text{Cn}(\cdot )$ ist eine Funktion, welche Formeln aus Formeln abbildet. Dabei ist Formulas die Menge aller Formeln. wahr ☐ falsch ☐
3. TC1 terminiert, wenn die zu beweisende Formel erfüllbar ist. wahr ☐ falsch ☐
4. Falls $\phi$ erfüllbar ist, so $\mathrm{\neg }\phi$ ist unerfüllbar. wahr ☐ falsch ☐
5. $\models ̸\phi \Rightarrow \psi \iff \mathrm{\forall }I$: $I\models \phi$ und $I\models ̸\psi$ wahr ☐ falsch ☐
6. Falls $\models \psi$ und $\models ̸\psi \Rightarrow \phi$ , dann $\models ̸\phi$ wahr ☐ falsch ☐

Lösungsvorschlag:

1. wahr ☒ falsch ☐
2. wahr ☐ falsch ☒
3. wahr ☐ falsch ☒
4. wahr ☐ falsch ☒
5. wahr ☒ falsch ☐
6. wahr ☒ falsch ☐

Ann. MartinW (16.03.2017)

5 ist falsch, wegen des All-Quantors (stattdessen sollte hier ein Existenz-Quantor stehen). Das ist von der LVA-Leitung geprüft (schauen Sie Prüfung 2017-01-10: Datei:TU Wien-Einführung in wissensbasierte Systeme VU (Egly) - Prüfung 2017-01-10.pdf (Aufgabe 1)d)).

Teilaufgabe d)

Formulieren Sie und beweisen Sie das Deduktionstheorem