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

Answer Set Programming (ASP)

Teilaufgabe a)

Sei M eine Interpretation und P ein grundiertes Programm.

1. Definieren Sie den Begriff des Reduktes $P^M$.

2. Wann ist M ein Answer Set von P?

(8 Punkte)

Lösungsvorschlag: JasonLeroy (Diskussion) 11:09, 25. Jan. 2014 (CET)

1. $P^M=\{a_1,\mathrm{...},a_n:-b_1,\mathrm{...},b_k|a_1,\mathrm{...},a_n:-b_1,\mathrm{...},b_k,not{b}_{k+1},\mathrm{...},not{b}_m\in P\{b_{k+1},\mathrm{...},b_m\}\cap M=\mathrm{\varnothing }\}$

2. M is an answer set of a ground program $P$ iff it is a minimal set of literals (w.r.t. set inclusion) which is a model of $P^M$.

Quelle: Seite 23, asp1.pdf, WS2013/14

Teilaufgabe b)

In welcher Weise kann ein grundiertes, normales Programm P als Default Theorie T übersetzt werden, sodass die Answer Sets von P zu den Extensionen von T korrespondieren?

(6 Punkte)

r ... Regel der Form $a:-b_1,\mathrm{...},b_k,not{b}_{k+1},\mathrm{...},not{b}_n$

$\delta (r)=\frac{b_1,\mathrm{...},b_k:\mathrm{\neg }{b}_{k+1},\mathrm{...},\mathrm{\neg }{b}_n}{a}$

$\Delta =\{\delta (r)|r\in P\}$

$T=(0,\Delta )$

Teilaufgabe c)

Betrachten Sie folgendes Programm (a, b, c sind Grundatome):

$P=\{\mathrm{\neg }c\vee \mathrm{\neg }d:-,a\vee b:-notc\}$

Geben Sie eine Menge $Q$ von Constraints an, sodass $P\cup Q$ zwei Answer Sets, $\{\mathrm{\neg }c,a\}$ und $\{\mathrm{\neg }c,b\}$ besitzt.

(6 Punkte)

Lösungsvorschlag:

$AS(P)=\{(\mathrm{\neg }c,a),(\mathrm{\neg }c,b),(\mathrm{\neg }d,a),(\mathrm{\neg }d,b)\}$

Die Answer Sets mit d müssen eliminiert werden:

$Q=\{:-\mathrm{\neg }d\}$

Teilaufgabe d)

Welche der folgenden Aussagen treffen zu:

1. Es gibt ein disjunktives logisches Programm $P$ sodass $P$ Answer Sets von $X_1,X_2$ besitzt, welche die Bedingung $X_1\subset X_2$ erfüllen, d.h. sodass $X_1$ eine echte Teilmenge von $X_2$ ist.

2. Es gibt ein normales logisches Programm welches ein inkonsistentes Answer Set besitzt.

(5 Punkte)

Lösungsvorschlag: von Stampi

Korrigiert am 28.01.2015 von jasonLeroy. Grund ist das Ergebnis der Diskussion weiter unten.

1) FALSCH, weil ein Answer Set immer minimal sein muss.

2) FALSCH, weil ein Answer Set niemals inkonsistent ist.

Ursprüngliche Lösung welche zu folgender Diskussion geführt hat: 2) RICHTIG, $P=\{a:-,\mathrm{\neg }a:-\}$

Kommentar: 2) ist falsch gelöst, weil ein normales Programm keine Regel besitzen darf die disunktiv ist oder strong-negation enthält (siehe asp1.pdf Seite 18)

Mein Vorschlag wäre: $P=\{a:-nota\}$

Vorschlag von --Stampi (Diskussion) 14:25, 27. Jan. 2014 (CET)

mMn ist 2) auch FALSCH, weil wenn $P=\{a:-nota\}$ dann gibt es keine Answer Sets für das Programm P und es kann deshalb auch nicht inkonsistent sein. D.h. AS(P) = {}

Siehe asp1.pdf Seite 26

Vorschlag von --me.name 19. Jan. 2015 (CET)

laut asp1.pdf Seite 28 hat $P=\{a:-,\mathrm{\neg }a:-\}$ kein Model daher auch kein Answer Set. ich denke das 2 ebenfalls falsch ist denn so etwas wäre ja nur möglich mit einem konstrukt wie:

a.

b :- a, not c.

-b :- a, not c.

aber das ganze hat ja gar kein Answerset. Habe auch nirgends gefunden das es inkonsitente Answersets überhapt gibt.

[vik_xxxl] d2: Nicht nur für normale Programme, sondern es gibt gar kein Programm das inkonsistente Answer Set besitzt.
Beweis: answer set => classical model. classical model => interpretation. interpretation <=> consistent set.
Oder in wort: Jede answer set ist klasische model. Jede klasische model ist interpretation. Jede interpretation ist konsistente menge.
Also es gibt keine Menge die inkonsistent ist und gleichzeitig answer set ist und egal ob normal, basic oder horn Programm.

Links

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