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

Answer Set

Beispiel A/a

Es sei $P$ ein logisches Programm und $I$ eine Interpretation. Man definiere die Begriffe klassiches Modell von $P$, Gelfond-Lifschitz reduct von $P$ und Answer Set von $P$.

Lösungsvorschlag --NomNomNom (Diskussion) 18:23, 10. Jun. 2014 (CEST):

klassiches Modell von $P$

$M$ ist ein klassiches Modell einer Regel, dann und nur dann, wenn gilt, dass wenn der Body, der Regel true ist, auch der Kopf true sein muss.

M ist ein klassisches Modell eines Programms wenn es für alle Regeln diese Eigenschaft erfüllt.

Gelfond-Lifschitz reduct von $P$

$P^{I}=\{a_{1}\lor \dots \lor a_{I}\vdash b_{1},\dots ,b_{k}\mid a_{1}\lor \dots \lor a_{I}\vdash b_{1},\dots ,b_{k},{\text{ not }}b_{k+1},\dots ,{\text{ not }}b_{n}\in P,\{b_{k+1},\dots ,b_{n}\}\cap I=\emptyset \}$

Answer Set von $P$

Ein Answer Set ist eine minimale Menge von Literalen eines Reducts.

Oder anders

Ein Answer Set ist eine minimale Menge von Literalen welches ein Model von $P^{M}$ ist.

Beispiel A/b

Beispiel A/b/1

Für jedes Horn Programm $P$ und jede Interpretation $M$ gilt $P=P^{M}$

Lösungsvorschlag --NomNomNom (Diskussion) 18:42, 10. Jun. 2014 (CEST):

Gegenbeispiel:

Programm

$P=\{{\text{ man }}\vdash ,{\text{ single }}\vdash {\text{ man }},{\text{ not husband }},{\text{ husband }}\vdash {\text{ man }},{\text{ not single }},{\text{ loved }}\vdash {\text{ man }},{\text{ husband }},{\text{ free }}\vdash {\text{ man }},{\text{ single }}\}$

Interpretationen

$M_{1}=\{{\text{ man }},{\text{ single }}\}$

und $M_{2}=\{{\text{ man }},{\text{ husband }}\}$

Redukt

$P^{M_{1}}=\{{\text{ man }}\vdash ,{\text{ single }}\vdash {\text{ man }},{\text{ free }}\vdash {\text{ man }},{\text{ single }}\}$

und $P^{M_{2}}=\{{\text{ man }}\vdash ,{\text{ husband }}\vdash {\text{ man }},{\text{ loved }}\vdash {\text{ man }},{\text{ husband }}\}$

minimale Modelle der Redukte

$P^{M_{1}}=\{{\text{ man }},{\text{ single }},{\text{ free }}\}$

und $P^{M_{2}}=\{{\text{ man }},{\text{ husband }},{\text{ loved }}\}$

Weder die Gleichheit $P=P^{M_{1}}$, noch $P=P^{M_{2}}$ ist gegeben.
[vik_xxxl: Anmerkung: gegebene P ist kein Horn Program]

Lösungsvorschlag 2 --Tyleet
Ich stimme dem Vorposter nicht zu, wie erwähnt ist sein P kein Horn Programm, Horn Programme haben weder Starke noch Schwache negationen. Mein Beweis für die Aussage wäre:
Alle Regeln eines Horn Programms haben die Form:
$a:-b_{1},....,b_{n}$
Darauß folgt, dass für ein Reduct eines Horn Programms gilt:
$P_{horn}^{M}=\{a:-b_{1},...,b_{n}|a:-b_{1},...,b_{n}\in P\}$
Also gilt für jede Regel $r$ für welche $r\in P$gilt, auch $r\in P^{M}$

[vik_xxxl] @Tyleet ich bin der selbe Meinung. Was genau stimmt nicht mit meine Aussage "gegebene P ist kein Horn Program" ????

Beispiel A/b/2

Jedes Horn Programm hat ein klassisches Model.

Lösung:

todo
[vik_xxxl:Vorschlag]
Every horn program must have one answer set. Every answer set of arbitrary program is classical model. So every horn programm must have one classical model :)

Beispiel A/c

Gegeben sei folgende Beschreibung eines Rechenelements $C$. Falls $C$ nicht defekt ist,am Eingang 1 von $C$ der Wert $V_{1}$ anliegt, und am Eingang 2 von $C$ der Wert $V_{2}$ anliegt, dann liegt am Ausgang von $C$ der Wert $V_{1}*V_{2}$ an vorausgesetzt $V_{1}>0$,ansonsten liegt am Ausgang von $C$ der Wert $V_{2}$ an. Repräsentieren Sie dies durch logische Programmregeln und verwenden Sie dafür folgende Prädikate:

$\mathop {\text{Calculator}} (C)$

$C$ ist Rechenelement

$\mathop {\text{ab}} (C)$

$C$ ist defekt

$\mathop {\text{in1}} (C,V_{1})$

am Eingang 1 von $C$ liegt der Wert $V_{1}$ an

$\mathop {\text{in2}} (C,V_{2})$

am Eingang 2 von $C$ liegt der Wert $V_{2}$ an

$\mathop {\text{out}} (C,V)$

am Ausgang von $C$ liegt der Wert $V$ an

Lösung:

Lösungsvorschlag: $out(C,V):-in1(C,V1),in2(C,V2),notab(C),Calculator(C),V=V1*V2,V1>0.$ $out(C,V2):-in1(C,V1),in2(C,V2),notab(C),Calculator(C),V1==0.$

Anmerkung:
Was ist wenn V1<0 ist? Meiner Meinung nach sollte die 2. Regel V1<=0 enthalten anstatt V1==0.

Beispiel A/d

wahr oder falsch

Gegeben seien folgende Programme ($a$ und $b$ sind Grundatome)

$P=\{a\lor b\leftarrow \}$ $Q=\{a\leftarrow \mathop {\text{not}} b,b\leftarrow \mathop {\text{not}} a,b\leftarrow a\}$

Für welche der folgenden Programme ist ${a}$ kein Answer Set?

Beispiel A/d/1

$P\cup \{a\leftarrow \}$

Lösung: falsch. Answer set: {a}

Beispiel A/d/2

$Q\cup \{a\leftarrow \}$

Lösung: wahr. Answer set: {a, b}

Beispiel A/d/3

$P\cup Q$

Lösung: wahr. Answer set: {b}