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

Teilaufgabe a)

Punkt 1

Geben Sie einen Satz der Prädikatenlogik an, der besagt, dass ein Ball der Kategorie Football einen Durchmesser von 22 cm hat. Verwenden Sie dazu die folgenden Prädikate: $IsA(x,y)$ bedeutet, dass ein Objekt $x$ der Kategorie $y$ angehört. $Size(x,y)$ bedeutet, dass das Objekt $x$ einen Durchmesser von $y$ cm hat. (2 Punkte)

Lösungsvorschlag: JasonLeroy (Diskussion) 14:54, 22. Jan. 2014 (CET)

$\mathrm{\forall }x(IsA(x,Football)\to Size(x,22))$

Punkt 2

Geben Sie einen Satz der Form $\mathrm{\forall }{x}_1\mathrm{...}\mathrm{\forall }{x}_n\varphi (x_1,\mathrm{...},x_n)$ an, der besagt, dass zwei Objekte der selben Kategorie den selben Durchmesser haben. Dabei ist $\varphi (x_1,\mathrm{...},x_n)$ eine definite Horn-Klausel mit freien Variablen $x_1,\mathrm{...},x_n$. (Eine Horn Klausel ist eine Disjunktion von Literalen - Atomformeln und negierten Atomformeln - von denen exakt eines eine nicht negierte Atomformel ist.) (2 Punkte)

Lösungsvorschlag: JasonLeroy (Diskussion) 14:54, 22. Jan. 2014 (CET)

$\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }w\mathrm{\forall }z((IsA(x,w)\wedge IsA(y,w)\wedge Size(x,z))\to Size(y,z))$

In Worten: Sind x und y von der Kategorie w und x hat die Größe z, dann hat y auch die Größe z.

Diese Lösung lässt sich noch zu einer Horner-Klausel umformen:

$\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }w\mathrm{\forall }z(\mathrm{\neg }(IsA(x,w)\wedge IsA(y,w)\wedge Size(x,z))\vee Size(y,z))$
$\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }w\mathrm{\forall }z(\mathrm{\neg }IsA(x,w)\vee \mathrm{\neg }IsA(y,w)\vee \mathrm{\neg }Size(x,z)\vee Size(y,z))$

Punkt 3

Betrachten Sie die Wissensbasis bestehend aus dem Satz aus 2. sowie den Sätzen $IsA(Bal{l}_2,Football)$, $IsA(Bal{l}_1,Football)$, $Size(Bal{l}_1,22)$. Zeigen Sie mittels TC1, dass daraus auch $Size(Bal{l}_2,22)$ folgt. (8 Punkte)

Lösungsvorschlag: JasonLeroy (Diskussion) 14:54, 22. Jan. 2014 (CET)

$\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }w\mathrm{\forall }z(\mathrm{\neg }IsA(x,w)\vee \mathrm{\neg }IsA(y,w)\vee \mathrm{\neg }Size(x,z)\vee Size(y,z))$ $IsA(Bal{l}_1,Football)$ $IsA(Bal{l}_2,Football)$ $Size(Bal{l}_1,22)$ $\mathrm{\neg }Size(Bal{l}_2,22)$
$\mathrm{\neg }IsA(Bal{l}_1,Football)\vee \mathrm{\neg }IsA(Bal{l}_2,Football)\vee \mathrm{\neg }Size(Bal{l}_1,22)\vee Size(Bal{l}_2,22)$
$\mathrm{\neg }IsA(Bal{l}_1,Football)$	$\mathrm{\neg }IsA(Bal{l}_2,Football)$	$\mathrm{\neg }Size(Bal{l}_1,22)$	$Size(Bal{l}_2,22)$
✘ clash	✘ clash	✘ clash	✘ clash

Diese lösung ist blödsinn. siehe: hier und hier

Danke! Hab's ausgebessert. --JasonLeroy (Diskussion) 09:45, 14. Jun. 2014 (CEST)

Teilaufgabe b)

Kreuzen Sie die zutreffende Antwort an:

1. Seien $\alpha$, $\beta$ und $\gamma$ aussagenlogische Sätze. Falls $\alpha \models \gamma$ oder $\beta \models \gamma$ gilt, so gilt auch $\alpha \wedge \beta \models \gamma$.

richtig ☐ falsch ☐

2. Seien $\alpha$, $\beta$ und $\gamma$ aussagenlogische Sätze. Falls $\alpha \wedge \beta \models \gamma$ gilt, so gilt $\alpha \models \gamma$ oder $\beta \models \gamma$ oder es gelten beide.

richtig ☐ falsch ☐

3. Aus $\mathrm{\neg }A\vee \mathrm{\neg }B\vee C$ folgt $\mathrm{\neg }A\vee \mathrm{\neg }B$.

richtig ☐ falsch ☐

4. Eine aussagenlogische Klausel ist genau dann gültig, wenn sie die Literale $A$ und $\mathrm{\neg }A$ für eine aussagenlogische Variable $A$ enthält.

richtig ☐ falsch ☐

(6 Punkte)

Lösungsvorschlag: JasonLeroy (Diskussion) 14:54, 22. Jan. 2014 (CET)

1. richtig ☒ falsch ☐
2. richtig ☐ falsch ☒
3. richtig ☐ falsch ☒
4. richtig ☒ falsch ☐

Teilaufgabe c)

Ist die folgende Aussage korrekt? Wenn ja, begründen Sie Ihre Antwort; wenn nein, geben Sie ein Gegenbeispiel an.

Seien $\alpha$ und $\beta$ beliebige aussagenlogische Sätze in konjunktiver Normalform, die dieselben $n$ aussagenlogischen Variablen enthalten. Dann gilt entweder $\alpha \models \beta$ oder $\alpha \models \mathrm{\neg }\beta$. (4 Punkte)

Was verändert sich, wenn alle Klausen von $\alpha$ einzelne Literale sind ($A$ oder $\mathrm{\neg }A$)? (3 Punkte)

Lösungsvorschlag 1:

Gegenbeispiel:

$\alpha$ und $\beta$ können frei gewählt werden, daher wählen wir:

$\alpha$ = $(\mathrm{\neg }a\vee a\vee \mathrm{\neg }b\vee b)$
$\beta$ = $(a\vee b)$

Eine Interpretation in der $\alpha \models \beta$ nicht gilt (die also $\alpha$ wahr und $\beta$ falsch macht):
$I(a)=0$ und $I(b)=0$

Eine Interpretation in der $\alpha \models \mathrm{\neg }\beta$ nicht gilt (die also $\alpha$ wahr und $\mathrm{\neg }\beta$ falsch macht):
$I(a)=0$ und $I(b)=1$

Es gilt also weder $\alpha \models \beta$ noch $\alpha \models \mathrm{\neg }\beta$.

TODO 2. Punkt

Lösungsvorschlag 2: JasonLeroy (Diskussion) 16:47, 22. Jan. 2014 (CET)

Nein. Gegenbeispiel:

$\alpha =(a\vee b)$
$\beta =(a)\wedge (b)$

In diesem Fall lassen sich Interpretationen finden, sodass sowohl $\alpha \models \beta$ als auch $\alpha \models \mathrm{\neg }\beta$ nicht gelten:

• Die Interpretation $I(a)=0,I(b)=1$ zeigt: aus $\alpha$ kann nicht auf $\beta$ geschlossen werden.
• Die Interpretation $I(a)=1,I(b)=1$ zeigt: aus $\alpha$ kann nicht auf $\mathrm{\neg }\beta$ geschlossen werden.

Beschränkt man sich bei $\alpha$ allerdings auf reine Konjunktionen (d.h. alle Disjunktionen der Normalform bestehen aus einem einzigen Literal), so gilt die Aussage. Der Grund ist, dass sich die aussagenlogischen Sätze aus $\alpha$ nicht weiter einschränken lassen (gilt $a\wedge b$ so gilt auch $a\vee b$).

Links

• Datei:TU Wien-Einführung in wissensbasierte Systeme VU (Egly) - Prüfung 2013-03-22.pdf
• Diskussion im Informatik-Forum