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)

$\forall x(IsA(x,Football)\rightarrow Size(x,22))$

Punkt 2

Geben Sie einen Satz der Form $\forall x_{1}...\forall x_{n}\phi (x_{1},...,x_{n})$ an, der besagt, dass zwei Objekte der selben Kategorie den selben Durchmesser haben. Dabei ist $\phi (x_{1},...,x_{n})$ eine definite Horn-Klausel mit freien Variablen $x_{1},...,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)

$\forall x\forall y\forall w\forall z((IsA(x,w)\land IsA(y,w)\land Size(x,z))\rightarrow 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:

$\forall x\forall y\forall w\forall z(\neg (IsA(x,w)\land IsA(y,w)\land Size(x,z))\lor Size(y,z))$
$\forall x\forall y\forall w\forall z(\neg IsA(x,w)\lor \neg IsA(y,w)\lor \neg Size(x,z)\lor Size(y,z))$

Punkt 3

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

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

$\forall x\forall y\forall w\forall z(\neg IsA(x,w)\lor \neg IsA(y,w)\lor \neg Size(x,z)\lor Size(y,z))$ $IsA(Ball_{1},Football)$ $IsA(Ball_{2},Football)$ $Size(Ball_{1},22)$ $\neg Size(Ball_{2},22)$
$\neg IsA(Ball_{1},Football)\lor \neg IsA(Ball_{2},Football)\lor \neg Size(Ball_{1},22)\lor Size(Ball_{2},22)$
$\neg IsA(Ball_{1},Football)$	$\neg IsA(Ball_{2},Football)$	$\neg Size(Ball_{1},22)$	$Size(Ball_{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 \land \beta \models \gamma$.

richtig ☐ falsch ☐

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

richtig ☐ falsch ☐

3. Aus $\neg A\lor \neg B\lor C$ folgt $\neg A\lor \neg B$.

richtig ☐ falsch ☐

4. Eine aussagenlogische Klausel ist genau dann gültig, wenn sie die Literale $A$ und $\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 \neg \beta$. (4 Punkte)

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

Lösungsvorschlag 1:

Gegenbeispiel:

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

$\alpha$ = $(\neg a\vee a\vee \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 \neg \beta$ nicht gilt (die also $\alpha$ wahr und $\neg \beta$ falsch macht):
$I(a)=0$ und $I(b)=1$

Es gilt also weder $\alpha \models \beta$ noch $\alpha \models \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 \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 $\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