TU Wien:Einführung in wissensbasierte Systeme VU (Egly)/Prüfung 2014-05-05/Beispiel 3

Answer Set Programming

Teilaufgabe a)

Welche der folgenden Aussagen treffen zu?

1. Jedes klassische Modell eines Programms P ist auch Answer Set von P. ☐ wahr ☐ falsch
2. Das Programm $P=\{a\vee b:-,a\vee c:-\}$ hat die Answer Sets $\{a\},\{b,c\},\{a,b\},\text{ und }\{a,c\}$.
3. Ein Answer Set eines normalen Programms P kann nicht-grundierte Atome enthalten.
4. Regeln in einem Programm zur abduktiven Diagnose dürfen disjunktiv sein.
5. Für jedes $n\ge 1$ gibt ein disjunktives logisches Programm, in welchem $\Theta (n)$ Atome vorkommen, welches jedoch mindestens $2^n$ Answer Sets besitzt.

(5 Punkte)

Lösungsvorschlag von --JasonLeroy (Diskussion) 21:29, 26. Jan. 2015 (CET)

(Laut Prüfungskorrektur)

1. ☐ wahr ☒ falsch
2. ☐ wahr ☒ falsch Answer Sets sind Minimal.
3. ☐ wahr ☒ falsch Answer Sets besitzen keine Variablen.
4. ☐ wahr ☒ falsch
5. ☒ wahr ☐ falsch

Teilaufgabe b)

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$?

(4 Punkte)

Teilaufgabe c)

Man gebe ein Horn Programm $P$ und Mengen $M_1,M_2$ an sodass $M_1$ und $M_2$ Answer Sets von $P$ sind, jedoch $M_1\cup M_2$ kein Answer Set von $P$ ist.

(1.5 Punkte)

Teilaufgabe d)

Es sei $⊢$ die skeptische Inferenzrelation definiert wie folgt: für jedes disjunktive logische Programm $P$ und jedes grundierte Literal $q$ gelte $P⊢q$ genau dann wenn $q$ in jedem Answer Set von $P$ enthalten ist.

Welche der folgenden Aussagen treffen zu?

1. $⊢$ erfüllt das Monotonieprinzip.
2. Es gibt ein Programm $P$ sodass $P⊢q$ für ein Atom $q$ das nicht in $P$ vorkommt.

(2 Punkte)

Lösungsvorschlag von --JasonLeroy (Diskussion) 21:29, 26. Jan. 2015 (CET)

(Laut Prüfungskorrektur)

1. ☐ wahr ☒ falsch
2. ☒ wahr ☐ falsch (so wurde es korrigiert, ich würde trotzdem immer noch "falsch" kreuzen; EDIT: bei einer älteren Prüfung wurde "falsch" als richtig gewertet, siehe: https://web.archive.org/web/*/www.informatik-forum.at/attachment.php?attachmentid=24584&d=1429963526)

[vik_xxxl] d2) EDIT: zB: P={q(a), p(X):-q(X)}

Anmerkung von --Tyleet
2) kann nicht wahr sein. Alles was in einem Answer Set von P vorkommt, muss auch im Head einer Regel in P vorgekommen sein, ansonsten wäre das Modell M nicht minimal und damit auch kein AS
[vik_xxxl] @Tyleet) Genau!