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\vee \dots \vee a_I⊢b_1,\dots ,b_k\mid a_1\vee \dots \vee a_I⊢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=\mathrm{\varnothing }\}$

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 }⊢,\text{ single }⊢\text{ man },\text{ not husband },\text{ husband }⊢\text{ man },\text{ not single },\text{ loved }⊢\text{ man },\text{ husband },\text{ free }⊢\text{ man },\text{ single }\}$

Interpretationen

$M_1=\{\text{ man },\text{ single }\}$

und $M_2=\{\text{ man },\text{ husband }\}$

Redukt

$P^{M_1}=\{\text{ man }⊢,\text{ single }⊢\text{ man },\text{ free }⊢\text{ man },\text{ single }\}$

und $P^{M_2}=\{\text{ man }⊢,\text{ husband }⊢\text{ man },\text{ loved }⊢\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,\mathrm{....},b_n$
Darauß folgt, dass für ein Reduct eines Horn Programms gilt:
$P_{horn}^M=\{a:-b_1,\mathrm{...},b_n|a:-b_1,\mathrm{...},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\ast 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:

$\text{Calculator}(C)$

$C$ ist Rechenelement

$\text{ab}(C)$

$C$ ist defekt

$\text{in1}(C,V_1)$

am Eingang 1 von $C$ liegt der Wert $V_1$ an

$\text{in2}(C,V_2)$

am Eingang 2 von $C$ liegt der Wert $V_2$ an

$\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\ast 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\vee b\leftarrow \}$ $Q=\{a\leftarrow \text{not}b,b\leftarrow \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}