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

Answer Set Programming

Teilaufgabe a)

Welche der folgenden Aussagen treffen zu?

1. Jedes Horn Programm hat ein klassisches Modell. ☐ wahr ☐ falsch
2. Das Programm $P=\{a\vee b:-,a\vee c:-,:-a\vee b\}$ ist ein disjunktives logisches Programm.
3. Falls ein Programm ein klassisches Modell hat, so besitzt es auch ein Answer Set. Jeodch sind nicht notwendigerweise alle klassischen Modelle Answer Sets.
4. Constraints fügen keine Ausdrucksstärke hinzu, sie können auf normale Regeln reduziert werden.
5. Sei $P$ ein Programm mit starker Negation und $P'$ ein Programm, welches aus $P$ entsteht, indem wir alle Literale der Form $\neg p$ uniform durch ein neues Atom $q_{\neg p}$ ersetzen. Falls $P$ kein Answer Set besitzt, so auch $P'$.

(5 Punkte)

Lösungsvorschlag von --JasonLeroy (Diskussion) 15:11, 27. Jan. 2015 (CET)

1. ☒ wahr ☐ falsch
2. ☐ wahr ☒ falsch Begründung: $:-a\vee b$ ist nicht einmal eine Regel.
3. ☐ wahr ☒ falsch
4. ☒ wahr ☐ falsch
5. ☒ wahr ☐ falsch

vik_xxxl Anmerkung zu 5): wenn P kein answer set besitzt, dann kann(vielleicht auch MUSS) unseres P' ein answer set besitzen.
Wenn P kein answer set besitzt dann sind alle "mögliche" answer-set-kandidaten inconsistent.
Also alle kandidaten sind in diese form
Candidat1 = [a, -a, ...]
Candidat2 = [a, -a, ...]
...
CandidatX = [a, -a, ...]

Nun, unseres P' hat selbe kandidaten, nur die sind auf einmal consistent und daher answer sets:
AS(P')1 = [a, minus_a, ...]
AS(P')2 = [a, minus_a, ...]
...
AS(P')X = [a, minus_a, ...]

Als Beispiel nehmen wir P={a,-a}, P'={a,minus_a}. P hat kein answer set aber P' schon. Und zwar {a,minus_a} :)
Sorry falls ich angabe falsch verstanden habe, aber antwort ist glaube ich falsch.

Teilaufgabe b)

Was ist ein Diagnoseproblem? Was ist eine konsistenzbasierte Diagnose gegeben solch ein Problem?

(1.5 Punkte)

Lösungsvorschlag mit ausführlicher Beschreibung von --JasonLeroy (Diskussion) 19:00, 27. Jan. 2015 (CET)

Ein Diagnoseproblem besteht aus

• einer Menge von Hypothesen, also Annahmen (hypotheses, H)
• einer Theorie (theory, T)
• einer Menge von Beobachtungen (observations, O)

In DLV ist

• H eine Menge von grundierten Atomen
• T ein Logik-Programm
• O eine Menge von grundierten Literalen

Bei der konsistenzbasierten Diagnose wird untersucht, welche Teile eines Systems defekt (abnormal) sind. Dafür ist H in diesem Fall eine Menge von grundierten Atomen mit Prädikatnamen $ab(.)$, zum Beispiel bei der Hausübung:

ab(x1).
ab(x2).
ab(a1).
ab(a2).
ab(o1).

Alle Regeln der Theorie enthalten not ab(X). (für X wird das jeweilige Atom eingesetzt), zum Beispiel:

c_out(0) :- and1(1), not ab(o1).

Die Beobachtungen werden in DLV als einfache Fakten aufgelistet, also Werte, die gelten, wie z.B.:

a_in(1).
b_in(1).

Nun wird eine Teilmenge von H gesucht, sodass

$T\cup O\cup S\cup \{\neg h|h\in H\backslash S\}$

konsistent ist, also ein Answer Set besitzt. $S$ ist also die Menge der defekten Komponenten, während $H\backslash S$ die nicht-defekten Kompoenenten enthält.

Arbeitet man mit DLV erhält man als Diagnose-Ergebnisse Mengen von ab(.), also verschiedene Möglichkeiten, welcher Teil des Systems bei der aktuellen Hypothese defekt ist.

Teilaufgabe c)

Sei $M$ eine Interpretation und $P$ ein grundiertes erweitertes logisches Programm. Betrachten Sie die beiden Definitionen von einem Answer Set:

(i) $M$ ist ein Answer Set genau dann, wenn $M$ ein minimales Modell (bzgl. $\subseteq$) von $P^{M}$ ist.

(ii) $M$ ist ein Answer Set genau dann wenn $M$ das kleinste Modell (bzgl. $\subseteq$ von $P^{M}$ ist.

Zeigen oder widerlegen Sie, dass die Definitionen übereinstimmen. Falls die Definitionen nicht übereinstimmen, untersuchen Sie ob jedes Answer Set gemäß (i) auch eines gemäß (ii) ist und umgekehrt.

(4 Punkte)

Informatik-Forum

Teilaufgabe d)

Es sei $\vdash$ die skeptische Inferenzrelation definiert wie folgt: für jedes disjunktive logische Programm $P$ und jedes grundierte Literal $q$ gelte $P\vdash q$ genau dann wenn $q$ in einem klassichen Modell von $P$ enthalten ist.

Welche der folgenden Aussagen treffen zu?

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

(2 Punkte)

Lösungsvorschlag --Tailorian (Diskussion) 01:10, 28. Mai 2015 (CEST)

(Laut Prüfungskorrektur)

1. ☐ wahr ☒ falsch
2. ☐ wahr ☒ falsch

siehe Prüfung vom Datei:TU Wien-Einführung in wissensbasierte Systeme VU (Egly) - Prüfung 28-01-2015.pdf

Also ich wäre bei 2. für richtig weil hier in der Frage (im Gegensatz zum verlinkten PDF) von klassischen Modellen und nicht von Answersets die Rede ist.