Cwa(t)

[kuetsch]

Hallo zusammen,
ich dachte mir, ich nehm mir mal ein paar alte Prüfungsbeispiele vor. Konkret gehts um Bsp 3 aus der Prüfung vom 11.3.2011 (https://vowi.fsinf.at/images/7/73/TU...2011-03-11.pdf)

Hier mal meine Ergebnisse, vl. hilfts ja wem... Um Ergänzungen, Berichtigungen etc. wär ich natürlich dankbar!!! (Sorry, dass der Post etw. länger geworden ist)

lg kuetsch

ad a)
Grundsätzlich haben wir mal T gegeben und wissen dass es Prädikate P u Q gibt, und Konstanten a,b,c.

Danach soll Tasm angegeben werden. Mein Verständnis war bis jetzt immer zuerst mal alles mögliche aus T herleiten, das was fehlt negiert in Tasm schmeißen:
-Q(b) schon gegeben -> über die Allquantor-Formel -P(b) herleitbar
P(a) schon gegeben -> über die Allq.-F. Q(a) herleitbar
somit hätten wir alle Prädikate mit a u. b, es fehlt nur noch c, von dem wir gar nix wissen, außer dass die Formel mit Existenzqantor für irgendeine Var gelten muss, und dies definitiv nicht für a u. b tut, daher muss es für c gehn: Q(c) und -P(c) damit herleitbar.
==> Ergo haben wir alles hergeleitet was es gibt, und es gibts nichts, was wir nicht definiert hätten.

Ich würde deshalb sagen, dass Tasm leer wäre, da das "asm" ja für Assumption steht. Wir müssen hier nichts annehmen, sondern können alles herleiten, daher hätte ich Tasm = {} gesagt.

Im After Test Thread (http://www.informatik-forum.at/showt...Test-11-3-2011) gibts allerdings einige Kommentare, die die mehrfache Benotungsänderung dokumentieren, wonach:

• Tasm nicht nur assumptions, sondern auch alle negativen Fakten beinhalten soll. M.e. irgendwie widersprüchlich, weil ja genau für assumptions gedacht, aber Tasm ist immerhin definiert als Tasm = {-P | P ground atom; T |≠ P}, also müsste eigentlich alles, was nicht herleitbar ist negiert rein und alles was als negativer Fakt schon in T ist auch noch mal (wozu?). Irgendwie bringt es ja nichts, wenn das doppelt definiert ist? Weiters steht 1 Folie vor dieser Definition, dass die Idee ist, nur positive Fakten zu speichern, was ja ausschließen würde, dass in T sowas wie -Q(b) enthalten ist?
• Anscheinend wurde argumentiert, dass man mit -Q(b) und der Allquantor-Formel nicht auf -P(b) schließen kann, was ich nicht ganz verstehen kann. Auch wenn das vor dem Implikations-Pfeil steht ist es nur eine simple logische Formel, die man nach belieben auswerten kann und dann genau auf dieses Ergebnis kommt?

Danach sollte CWA(T) angegeben werden.

• Ist hier irgendetwas außer der Standard-Definition CWA(T) = {phi | T u Tasm |= phi, phi closed} anzugeben?

• Gibts eigentlich in dem Zusammenhang irgendeinen Unterschied, wann ich die Closure-Fkt Cn verwende und wann ich es mit den Mengen wie oben schreibe?
• Gibt es einen Unterschied zwischen "Ground" term (= variable free) und "Closed" term (anscheinend auch variable free)?

In a2) gibts dann 3 t/f Fragen:

• Tasm vollständig? Das hängt natürlich davon ab, was drin ist :-/ Üblicherweise stellt sich diese Frage doch eher im Zusammenhang mit CWA(T) oder? Wie auch immer, vollständig ist, wenn für jede Kombi aus Präd. P u Var. x ein P(x) oder -P(x) drin ist. Das ist bei Tasm sicher nicht der Fall. Bei CWA(T) wäre es m.E. zutreffend.
• CWA(T) konsistent? Würde ich sagen.
• T deduktiv abgeschlossen? Hätte ich mit nein beantwortet. Es ist zwar alles in T enthalten um den deduktiven Abschluss durchführen zu können, aber T ist doch nicht gleich Cn(T) oder? Cn(T) wäre deduktiv abgeschlossen und da Tasm={} wäre Cn(T) = CWA(T)

ad b) Klar, dass Default Logik nicht monoton ist.
Gegenbsp:
W = {a}; delta = {a:b/b}
E = {a,b}
W' = {a,-b} -> E' = {a,-b} (wenn ich das richtig verstanden habe)
==> Neue Fakten können alte "Annahmen" widerlegen, was der Monotonie widerspricht.
Wäre das ein passendes Gegenbeispiel?

ad c) Hab ich noch nicht, werd ich wenn mögl. noch nachreichen.

[rtbam]

seh ich auch so die t/f fragen sind tlw fangfragen glaub ich (das mit Tasm z.b.)

[_gerald_]

Tasm ist nicht leer. Fuer die Konstruktion von Tasm werden immer Grundatome betrachtet. Diese sind unterschiedlich zu Literalen:

Tasm = {-P | P ground, T |/= P}

Du pruefst jetzt mal fuer die verschiedenen Grundatome:

1.) P(a) ist herleitbar, daher kann -P(a) nicht enthalten sein
2.) Q(a) ist herleitbar (MP auf Allquantor), -Q(a) kann daher nicht enthalten sein
3.) P(b) ist nicht herleitbar, da -P(b) herleitbar ist und die Wissensbasis nicht inkonsistent ist; folglich kommt -P(b) in Tasm (hier musst du aufpassen: -P(b) ist ein Literal, P(b) das Atom)
4.) Q(b) ist nicht herleitbar, da ja -Q(b) direkt enthalten ist; folglich kommt -Q(b) auch in Tasm
5.) Aus T ist -P(b), -Q(b), P(a), Q(a) enthalten, daher kann nur -P(c) und Q(c) gelten. Folglich kommt -P(c) auch in Tasm (wieder das gleiche argument wie bei 3: P(c) ist nicht herleitbar, da -P(c) selbst herleitbar ist)

zu den Theoriefragen:

1.) Tasm ist nicht vollstaendig
2.) Konsistenz ist gegeben
3.) Die Theorie ist nicht deduktiv abgeschlossen. Ansonsten muesste auch zb. P(a) & -Q(b) drin sein (und noch unendlich viele Formeln mehr)

[Mobe]

Gibt es einen Unterschied zwischen "Ground" term (= variable free) und "Closed" term (anscheinend auch variable free)?

Ein "ground term" ist ein Term ohne Variablen, während ein "closed term" ein Term ohne freie Variablen ist.

[Mobe]

ad c)

Bin mir ein ziemlich unsicher bei meiner Lösung (vor allem bei Punkt 3).

1. E1=Cn({R(a),S(a),Q(a)}) extension, da gammaT(E1)=E1
E2=Cn({R(a), S(a), -Q(a)}) extension, da gammaT(E2)=E2

2. E1=Cn({-R(a), S(a)}) keine Defaults anwendbar; extension, da gammaT(E1)=E1

3. E1=Cn({R(a), Q(a), -S(a)}) keine extension, da gammaT(E1)=Cn({R(a), Q(a)}) != E1

[Mobe]

Hat sich eigentlich schon jemand den von kuetsch verlinkten After Test Thread durchgelesen? ^^ Ist ja total krank was da abgeht.
Laut Tompits ist die Lösung zu 1a nämlich Tasm={-P(b), -P(c), -Q(c), -Q(b)}. Und er hat davor anscheinend schon zweimal seine Meinung geändert was die Lösung angeht. Hat wer einen Schimmer wie diese "Lösung" zustande kommt??

[_gerald_]

Ja, wuesste schon wie sie zustande kommt, muss einen kleinen Teil meiner vorigen Loesung revidieren:

5.) Aus T ist -P(b), -Q(b), P(a), Q(a) enthalten, jedoch kann ueber P(c) und Q(c) keine Aussage gemacht werden, daher musst du beide (-P(c) und -Q(c)) in Tasm aufnehmen. Erklaerung dafuer:

T = {...} wie gegeben.
Frage: T |= Q(c)?

Widerlegen kannst das Ganze, indem du ein Modell von T angibst, das kein Modell von Q(c) ist, sprich Q(c) falsch macht. Im Endeffekt hast du bei dieser Interpretation den Freiheitsgrad, dass du zu a, b, c _beliebige_ Objekte aus der Domaene zuweisen kannst, daher kannst du u.a. zu a und c das gleiche zuweisen. Trotzdem kann die erste Formel der Theorie (exists...) erfuellt sein, da es halt nur die Konstanten a, b, c gibt, aber u.a. mehr Domaenenobjekte. Somit hast du fuer die restlichen Domaenenobjekte keinen "Namen" in der syntaktischen Darstellung. Nichtsdestotrotz kann die Theorie T erfuellt werden, ohne dass Q(c) erfuellt wird.

Aber das kann auch anders sein, sodass man sich _nur_ auf die geg. Konstanten beschraenken muss. Leider findet man dazu in den Folien nichts.

[kuetsch]

Ok, vielen Dank für die hilfreichen Posts!

Dh, wenn in T Literale vorkommen, die nur negierte Grundatome sind, so kommen diese auch in Tasm rein.
Das mit der Konstanten c ist m.E. noch nicht ausdiskutiert:

Meine Interpretation war ja, dass c als einziges übrig bleibt und deshalb die Formel mit Existenzquantor darauf angewendet werden muss. _gerald_ schreibt nun, es könnte ja auch ein anderes x geben, und deshalb kann man für c nichts daraus ableiten.
Andererseits sagt die Angabe ja "... mit den einzigen Konstantensymbolen a, b, und c, dem Variablensymbol x..."
Würde das nicht bedeuten, dass ich für x zwar beliebige Konstanten wählen kann, aber eben nur a, b, und c zur Verfügung habe? Ich dürfte ja auch nicht das x beliebig durch d, e, oder f ersetzen? Und wenn, dann müsste von den Konstantensymbolen ein großer Haufen in Tasm drin sein?

Zu den Theoriefragen/Antworten:
Tasm ist nicht vollständig. Stimmt meine Interpretation dazu (mal abgesehen davon, dass die Ergebnisse für Tasm bei mir falsch waren), wäre es ja nur vollständig, wenn für alle Präd. u Konstanten jede Kombination dort drin vorkommt.
CWA(T) konstistent, sind wir einer Meinung
T deduktiv abgeschlossen: Ebenfalls gleich... Nur als Gegencheck: CWA(T) wäre deduktiv abgeschlossen, oder?


@Mobe: Es gibt ja 2 Schreibweisen, freie Variablen oder Quantoren... Heißt das, dass für Closed Terms weder Freie var, noch über Quantoren gebundene Var drin sein dürfen?

lg kuetsch

[_gerald_]

Auf c kannst du nicht schliessen. Wie bereits gesagt, ich kann meine Sprache so reduzieren, dass ich nur a, b und c als Objektkonstanten verwenden darf. Jedoch sagt das nichts ueber die Interpretationsfunktion I aus. Ich kann eine Domaene waehlen, wo unendlich viele Objekte drin sind, und trotzdem I(a) = I(b) = I(c) setzen. Damit die Theorie erfuellt ist, muessen nur die Einschraenkungen fuer a und b gelten.

Ein Beispiel:

Domane D = {1, 2, 3, 4}

I(a) = 1
I(b) = {2}
I(P) = {1, 3} (=> P(a) und -P(b))
I(Q) = {1} (=> -Q(b), jedoch Q(a))

I(c) = 1 (=> P(c) und Q(c))

Die erste Formel der Theorie ist trotzdem erfuellt, denn es gibt ein x, sodass P(x) aber -Q(x) wahr werden (x entspricht dem Objekt '3' aus der Domaene).

Somit gibt es ein Modell von T, welches nicht Modell von Q(c) ist.

[kuetsch]

Um ehrlich zu sein, kann ich deinem Bsp nicht so ganz folgen (v.a. was die Nummern hier bedeuten...)

Ich versuchs mal allgemeiner zu formulieren:
Bedeutet das, dass ich zwar nur a,b und c berücksichtige in meiner CWA, es allerdings anzunehmen ist, dass es unendlich viele andere Konstanten gibt, die ich hier gar nicht berücksichtige? Das würde m.E. die Begründung erklären, aber:

Dann müsste Tasm doch immer unendlich sein?

Warum steht dann "die einzigen Konstantensymbole" in der Angabe? Wenn man's schon so genau nimmt müsste das doch "die einzigen berücksichtigten Konstantensymbole" heißen.

Warum kommt dann in der Theorie überhaupt irgendwo ein Existenzquantor vor? Wenn das die Definition ist, dann kann ich ja mit dem Exist.Q. NIE irgendwas aussagen und das Zeug wäre ausschließlich dem Fehler-Machen in EWBS Prüfungen vorbehalten ;-)

lg kuetsch

[_gerald_]

a, b und c sind Bestandteil deiner Signatur. Genauer genommen sind sie die Funktionen mit Aritaet 0. Das was du kennst mit neuen Konstanten einfuehren wird bei so manchen Kalkuelen gebraucht (Stichwort: Skolemisierung). Jedoch kannst du davon unabhaengig ja eine Interpretation angeben, die die Konstanten so belegt, dass die obige Theorie mit deinen Ueberlegungen fuer c keine Aussage treffen kann.

Wenn du (so wie du argumentierst) auf c schliessen willst durch das Ausschlussprinzip, so wuerdest du ein domain closure Axiom brauchen:



Lass dir den Unterschied zwischen einer Theorie T' = T + dieses Axiom und von T selbst durch den Kopf gehen.

[Mobe]

Es gibt ja 2 Schreibweisen, freie Variablen oder Quantoren... Heißt das, dass für Closed Terms weder Freie var, noch über Quantoren gebundene Var drin sein dürfen?

Was genau meinst du mit 2 Schreibweisen? Es gibt freie und (durch Quantoren) gebundene Variable. In Closed Terms dürfen nur gebundene Variablen vorkommen, in Ground Terms dürfen gar keine Variablen vorkommen.

[kuetsch]

Was genau meinst du mit 2 Schreibweisen? Es gibt freie und (durch Quantoren) gebundene Variable. In Closed Terms dürfen nur gebundene Variablen vorkommen, in Ground Terms dürfen gar keine Variablen vorkommen.

Dh. wenn "füralle x (...)" steht, ist das auch ein closed term, da x durch den quantor nicht mehr frei ist, oder?

lg kuetsch

[kuetsch]

Jedoch kannst du davon unabhaengig ja eine Interpretation angeben, die die Konstanten so belegt, dass die obige Theorie mit deinen Ueberlegungen fuer c keine Aussage treffen kann.

Ich dachte immer, dafür müsste ich dann eine Domain haben, die z.B. weitere Konstantensymbole enthält? Die "Preisfrage" an der Geschichte ist m.E. ob es nun mehr als a,b,c gibt oder nicht. Dem x als Variable muss ich ja immer irgendeinen Wert (bzw. Konstante) zuweisen...

Wenn du (so wie du argumentierst) auf c schliessen willst durch das Ausschlussprinzip, so wuerdest du ein domain closure Axiom brauchen:



Lass dir den Unterschied zwischen einer Theorie T' = T + dieses Axiom und von T selbst durch den Kopf gehen.

Schon klar, mit dem Axiom sagst du, dass x nur a,b oder c werden kann. Ich frag mich halt nur die ganze Zeit schon, ob es auch was anderes werden kann, und wenn ja, wie?

M.e. heißt das, ohne diesem Axiom sind die Formeln mit Existenzquantor nicht geeignet, irgendeine Ableitung zu bilden.

[_gerald_]

Die Konstantensymbole haben nichts mit der Domain zu tun. Ich kann fuer eine Formel, die in der Signatur nur a, b, c hat auch die natuerlichen Zahlen als Domain nehmen. An diesem Beispiel sollte es schon klar werden, dass es nicht fuer jedes Objekt aus der Domaene ein Konstantensymbol geben muss bzw. geben kann. Denk nur mal an ueberabzaehlbare Domaenen: hier kannst du gar nicht genug Konstantensymbole haben.

[kuetsch]

ad c)

Bin mir ein ziemlich unsicher bei meiner Lösung (vor allem bei Punkt 3).

1. E1=Cn({R(a),S(a),Q(a)}) extension, da gammaT(E1)=E1
E2=Cn({R(a), S(a), -Q(a)}) extension, da gammaT(E2)=E2

2. E1=Cn({-R(a), S(a)}) keine Defaults anwendbar; extension, da gammaT(E1)=E1

3. E1=Cn({R(a), Q(a), -S(a)}) keine extension, da gammaT(E1)=Cn({R(a), Q(a)}) != E1

Würde auf dieselben Lösungen kommen, hab allerdings eine Frage zu 3.

So wie ich das Verstanden habe, bilde ich das Redukt, indem ich alle anwendbaren Regeln mit rein nehme, nur ohne psi diesesmal. Offensichtlich darf der Default aus D2 nicht ins Redukt. Aber bis dahin haben wir ja noch keinen Widerspruch; -S(a) ist ja noch nicht in unserer Menge, sondern erst nach Anwendung der Regel. Mit welcher Begründung darf der dann trotzdem nicht rein? (Dass das Ding ein Widerspruch in sich selbst ist, ist eh klar...)

ad2) Hier haben wir eigentlich eine Extension, die kein neues Wissen ableitet. Ich kann formal jetzt keinen Hinweis darauf finden, dass das nicht passen würde, frag mich aber intuitiv, ob das dann eigentlich eine Extension ist??? ;-) Trotzdem glaub ich, dass das so stimmen wird...

lg kuetsch

[kuetsch]

Hab mir von der Prüfung am 10.12.09 (https://vowi.fsinf.at/images/8/81/TU...2009-12-10.pdf), das Bsp 3 zum selben Thema angesehen, hier meine Ergebnisse u. aufgeworfene Fragen:

a)
Ich glaube hier darf man das Q(x) -> P(x) nicht so verwenden, wie die üblichen Formeln mit Allquantor, dh. eigentlich ist die nutzlos.
Weiters sind keine negierten Prädikate in T, dh. wir müssen nicht aufpassen, dass wir die in Tasm vergessen zu erwähnen.

Ich würde sagen, dass wir hier nichts ableiten können, alles, was nicht in T gegeben ist, muss in Tasm rein.
Tasm = {-Q(a), -P(b), -Q(c), -P(c)}
CWA(T) = Cn(T u Tasm) (wobei in der Antabe statt Tasm {____} zum ausfüllen steht...

b)
Residuum des Defaults ist: A/C

c)
Ich weiß nicht, ob ich hier richtig liege, aber m.E. müsste
W = {..., Person(S) ^ -LikesCoffee(S)} äquivalent zu
W = {..., Person(S), -LikesCoffee(S)} sein, oder?

Mal angenommen, es ist so, dann wäre
1. keine Extension, weil LikesCoffe(S) nicht passt (-LikesCoffee(S) ist ja schon in W)
2. eine Extension
3. keine Extension, wieder weil LikesCoffee(S) widerspricht
4. keine Extension, LikesCoffee(S) passt nicht, außerdem fehlen die Student(...) Prädikate, die sollten sich ja mit nichts sonst in die Quere kommen und m.E. immer enthalten sein, wenn's denn eine Extension gibt...

was haltet ihr davon?

lg kuetsch

[_gerald_]

zu a) ja, da hat sich wohl jemand bei der Pruefungsangabe irgendwie vertan, insofern als T immer als geschlossen angenommen ist. Tatsaechlich gibt es zwei verschiedene Auffassungen entailment ueber offenen Theorien: die eine verwendet den Allabschluss, die andere laesst einfach bel. Variablen-assignments zu. Wenn ich mir die Def. vom Egly auf den Folien anschau, so wuerde Zweiteres zutreffen, dh. Q(x) -> P(x) zusammen mit Q(b) ergibt nicht notwendigerweise P(b), da du eine Interpretation angeben kannst, wo das Variablen-assignment fuer x so gelegt ist, dass Q(x) wahr ist und P(x) wahr ist, jedoch fuer b nur Q(b) wahr machen kannst und P(b) falsch machst. Generell ist das 1. von mir genannte Konzept schwaecher als das Zweite, dh. falls T |=(2) phi dann auch T |=(1) phi.

Falls sowas bei der Pruefung auftaucht, so wuerde ich die Aufsicht darauf hinweisen, dass das nicht den Annahmen in den Folien entspricht. Dann werden sie es (vielleicht, man weiss ja nie) festlegen und vll sogar sagen, dass der Allabschluss genommen wird.

However zu (b): passt

c) Mit der Aequivalenz hast du recht, mit den MC Fragen stimm ich dir auch ueberein. nur 2. ist eine Extension.

[_gerald_]

Eins noch: dasselbe mit "nicht klar definiert" trifft bei dieser Pruefung uebrigens auf das ganz erste Bsp auch zu: W -> neg phi ist nicht wohldefiniert, es is einfach nur ein syntaktischer Fehler: W ist keine Formel, sondern eine Menge von Formeln, daher kann W -> neg phi unmoeglich bestandteil meiner Sprache sein. Also lieber aufpassen bei solchen Sachen und nachfragen.

[kuetsch]

Also, du meinst, dass hier sinnvollerweise ein Allquantor in der Angabe sein sollte...
Das bedeutet, dass dann Q(a) und P(b) herleitbar sind und Tasm um -Q(a) und P(b) erleichtert wird.

T wäre dann weiterhin nicht vollständig (weil Prädikate für c nicht herleitbar sind) und CWA(T) wäre weiterhin inkonsistent, weil die Präd. für c aus Tasm der Theorie widersprechen...

[_gerald_]

Wie gesagt, ob der Allquantor gemeint ist, haengt von der Def. der Herleitungsrelation ab^^ aber ich denke, dass sie damit nicht den Allquantor meinen, lt. Egly's Definition geb ich dir mal ein Gegenbeispiel:

Wir haben geg. T = {Q(b), Q(x) -> P(x)}. Wir zeigen nun, dass T |/= P(b).

Dh. es gibt eine Interpretation , welche alle Formeln aus T wahr macht, und P(b) falsch macht. Die Interpretation und eine Domaene geben wir wie folgt an:



Nun ist eine Interpretation, welche offensichtlich Q(b) falsch macht, jedoch alle Formeln aus T wahr macht. Man sieht dass der Modellbegriff sowohl von I und D als auch von alpha abhaengt. Im Falle von geschlossenen Theorien hast du kein Problem, da das alpha immer leer ist.

[kuetsch]

Ich wollte schon Bsp 1 hier anreißen, jetzt hab ich eine Überleitung ;-) Dh. bei der 2. t/f Frage passt die Syntax nicht... hmmm

a)
1. richtig. Im Prinzip das Deduction Theorem anders rum aufgeschrieben. Das sollte ja passen, weil "genau dann" bzw. "iff" ja eine 1:1 Relation ist die ich auch umkehren kann, oder?
2. Grundsätzlich weiß ich ja trotz der falschen Syntax, worauf sie hinauswollen, näml. dass sich aus einer Theorie, die -phi ableiten lässt nie selbst phi enthalten kann... Wie müsste das sauber geschrieben werden? So wie das Contradition Theorem?
3. puh... Im Prinzip wird hier gefragt, ob sich phi noch ableiten lässt, wenn die Theorie um psi verringert wird... Ich sag mal falsch, es könnte nat. sein, dass ich psi nicht brauch, aber das kann ich ja nicht garantieren.
4. Oh, hier haben wir genau das Deduction Theorem, und das stimmt natürlich... Somit wäre Frage 2 dann ja wohl redundant???

b)
So, das sieht zuerst mal einfach aus, aber ich glaub irgendwo hab ich einen Fehler drin:

1. als Entailmentproblem darstellen:

(-b -> a) |= -(a v c) -> b

2. Erfüllbarkeitsproblem

Das Entailment gilt, wenn die Implikation auch gilt: |= ((-b -> a)) -> (-(a v c) -> b)
Verwendete Gesetze/Theoreme: Deduction Theorem

3. NNF
((-b -> a)) -> (-(a v c) -> b) gilt, wenn
-((-b -> a)) ^ (-(a v c) -> b) unerfüllbar

-((-b -> a) = -(b v a) = -b ^ -a

-(a v c) -> b = (a v c) v b = a v c v b

NNF(F) = (-b ^ -a) v a v b v c

4. die gilts jetzt mit TC0 zu widerlegen

-b
-a
a v b v c
-------------
a | b | c
clash | clash | kein clash

Gegenmodell:
I |= c
I |≠ b
I |≠ a

Wenn ich nun aber in die ursprüngliche Formel einsetze wird die nicht false:
(-b -> a) |= -(a v c ) -> b
(t -> f) |= -(f v t) -> f
f |= f -> f
f |= f
aus falschem folgt beliebiges, dh. das entailment müsste eigentlich gelten u ich weiß nicht warum (???). wo hab ich den fehler versteckt? dass die linke seite des entailments false ergibt wird doch nicht schon ausreichen? es müsste doch ein fall t |= f rauskommen oder täusche ich mich da?

Interpretation: Wenn ich die wüsste?
Gegenbeispiel: haut irgendwie ja nicht ganz hin...

lg kuetsch

[kuetsch]

Wie gesagt, ob der Allquantor gemeint ist, haengt von der Def. der Herleitungsrelation ab^^ aber ich denke, dass sie damit nicht den Allquantor meinen, lt. Egly's Definition geb ich dir mal ein Gegenbeispiel:

Wir haben geg. T = {Q(b), Q(x) -> P(x)}. Wir zeigen nun, dass T |/= P(b).

Dh. es gibt eine Interpretation , welche alle Formeln aus T wahr macht, und P(b) falsch macht. Die Interpretation und eine Domaene geben wir wie folgt an:



Nun ist eine Interpretation, welche offensichtlich Q(b) falsch macht, jedoch alle Formeln aus T wahr macht. Man sieht dass der Modellbegriff sowohl von I und D als auch von alpha abhaengt. Im Falle von geschlossenen Theorien hast du kein Problem, da das alpha immer leer ist.

Pfff... mit den Zahlen dazu krieg ich einen Knopf im Hirn ^^

Was bedeutet das nun genau?
alhpa(x) = {2} Heißt das, x kann den Wert 2 annehmen?
I(Q) = {1,2} Hier auch? Was bedeutet das ganze dann für die logischen Operaionen, wenn ich hier mit Zahlen rechne?

[_gerald_]

Deine Ueberlegungen bei den MC Fragen stimmen. Das mit den Syntax ist beim Test als richtig angekreuzt, darum meine ich, dass sie die Konjunktion ueber alle Formeln in W meinen (dafuer muss W nat. endlich sein, aber das is wieder was anderes ). Zu meinem Beispiel:

Eine Interpretation ist eine Funktion, die jeder Objektvariable ein Objekt aus der Domaene zuordnet. Sprich, in meiner Interpretation nimmt x den Wert '2' der Domaene an. Ferner ordnet die Funktion I jedem n-stelligen Relationssymbol eine n-stellige Relation ueber D zu. Eine einstellige Relation ist dabei einfach eine Teilmenge von D -> da P und Q einstellig sind, sind I(Q) und I(P) einfach Teilmengen von D.

Nun gilt:

Die Formel P(b) wird in I genau dann wahr, wenn . Das sind genau die Def. aus den Folien (hab hier eine kuerzere Darstellung genommen, das Ganze ist nat. induktiv definiert, aber ich glaub mit meinem Beispiel soll klar sein worauf ich hinaus will). Letzten Endes ist also eine Formel genau dann gueltig, wenn sie in jeder Interpretation wahr ist. (also in jedem I und in jeder Domaene wahr wird: Achtung, beim Durchschaun von Egly's Folien ist mir aufgefallen, dass er das nur mit "fuer jedes I_alpha..." definiert. Fuer normal wird aber fuer jede Domain und jedes I_alpha gefordert, bzw. fuer Allgemeingueltigkeit; glaub das ist einfach ein kleiner Fehler vom Egly. Waere dem nicht so, so koenntest du fuer eine vorgegebene Domain mit TC1 entscheiden, ob eine Formel in dieser Domain gueltig ist, was aber nat. nicht moeglich ist.)

Edit: ok, in den Folien ist es immer modulo von Sigma, dh. das passt scho

[kuetsch]

So, mittlerweile bin ich auch auf den Fehler im TC0 oben gekommen:

phi -> psi gilt, wenn
phi ^ -psi unerfüllbar. habs oben geschafft -phi ^ psi zu schreiben und der fehler zieht sich nat. durch

so, hier nun der beweis wo alles clashed

phi = -b -> a
psi = -(a v c) -> b

phi |= psi gilt, wenn
phi ^ -psi unerfüllbar

umformen in NNF

(-b -> a) ^ -(-(a v c) -> b)
(b v a) ^ - (a v b v c)
(b v a) ^ -a ^ -b ^ -c

TC0
----------------------------
-a
-b
-c
b v a
----------------------------
b              | a       
clash mit 2 | clash mit 1

Interpretation des Ergebnisses bzgl. Entailmentproblems?
Hmm... naja, dass offensichtlich die Gegenannahme (phi ^ -psi) falsch war und das der Beweis ist, dass das Entailment gilt... Aber das ist doch eigentlich nur Umformen der Fragestellung in eine Feststellung ;-)

Gegenbsp. gibts jetzt natürlich keins

lg kuetsch

[kuetsch]

Ich muss hier mal kurz meinen eigenen Thread kapern, mit einer Frage, die nicht direkt zu den Bsp gehört. Es ist nur eine Kleinigkeit und würd keinen neuen Thread rechtfertigen:

ISF (Immediate Subformula) in pl1.pdf (page 18)

phi(x)sigma is isf of forall_x(phi(x)) and existists_x(phi(x)) (where sigma is {x/t} for any term t)

was ist das sigma hier und warum ist die subformula mehr als das, was der quantor bindet? und wie ist die definition dahinter von sigma zu verstehen? normalerweise kenn ich die schreibweise für alles was parameter hat mit {name/arity}...

[_gerald_]

Das sigma ist als Substutition zu verstehen. Wenn du eine Formel mit einem Quantor hast (zb. ), dann sind alle Instantiierungen von P(x) durch einen bel. Term imm. subformulas.

[tass2]

kurze frage: prüfung 2011-03-11, aufgabe 1:

1. phi |= psi
2. |= (phi) -> (psi), deduktionstheorem angewandt
3. nnf(phi) = (not exists x P(x)) ^ for each y (P(a) v Q(y)) nnf(not psi) = Q(b) ^ (not Q(a))
4.

Das not exists x P(x) wird bei mir zu: not P(c)

das for all wird zu: P(a) v Q(a)

Q(a) ergibt einen Clash, P(a) bleibt offen

Die gegenteilige Annahme kann nicht widerlegt werden. Von Phi kann nicht auf Psi geschlossen werden.


Ein Gegenmodell wäre z.B: I(P(a)) = true, rest beliebig? Kann man das so sagen?

[kuetsch]

Also ich krieg Clashes:

not exists_x(P(x)) kannst du substituieren mit forall_x(-P(x))
damit brauchst du dann kein neues c einführen, sondern kannst im TC ein -P(a) draus machen, das dir dann den Clash verursacht.

lg kuetsch

[tass2]

Also ich krieg Clashes:

not exists_x(P(x)) kannst du substituieren mit forall_x(-P(x))
damit brauchst du dann kein neues c einführen, sondern kannst im TC ein -P(a) draus machen, das dir dann den Clash verursacht.

lg kuetsch

Danke! Habs auch grad in den Folien gesehen. Danke auch.

[tass2]

Hi! Noch 2 Fragen:

W={q} ; Delta1 = {q : not p / p}

1. T = W, Delta = Delta1

Extensions? Ich hätte gesagt Cn(q)?

2. T = W u {p}, Delta = Delta1

Extensions? Ich hätte gesagt cn(q,p)?

Oder gibts hier jeweils gar keine Extension?


----------------------------------------

EDIT:

Hab jetzt versucht, mit diesem Semirekursiven Ding zu schauen, obs Extension ist oder nicht:

E0 = W = {q}
E1 = Cn(E0) u {p} /* aus dem default */

fertig?

Cn(E1) != Cn(E) bzw
Cn(p,q) != Cn(q) ?? Daher keine Extension?

[kuetsch]

Habs jetzt nicht durchgerechnet, aber rein von dem was ich grad seh:

1. Hat m.e. keine Extension, denn mit q kann ich p ableiten. Wenn ich dann aber das Redukt bilde, dann fliegt die Regel raus (weil das ": not p" der extension widerspricht), damit wird das Gamma = {q} und ist nicht gleich der erhofften extension

2. Hat m.e. eine Extension und zwar E = Cn(T)... Hier haben wir in T schon p und q, kein Default ist anwendbar, das Redukt ist leer und das Gamma wird dasselbe sein wie die Extension, dh. die Closure von der Wissensbasis...

[tass2]

hey kuetsch. könntest du mir das mit dem Redukt erklären? Ich verstehe es nicht zu 100%

Gehe ich da so vor?

Ich will überprüfen ob E eine Extension ist.
Jetzt schaue ich, welche Defaults anwendbar sind, und wenn irgend ein Default sich widerspricht, ist es keine Extension. Wenn die Defaults anwendbar sind, aber dadurch keine Unstimmigkeit zustandekommt, passts. Ist kein Default anwendbar, ist alles OK.

Und ist das dann dieses Gamma T?


zB in den Folien steht folgendes, was ich nicht richtig zusammenbekomme (nmr seite 18 /letzte seite)
Gamma T (E′) = Cn({water creature}) != E′!

Das liegt bei mir vermutlich daran, dass ich im PDF den Punkt 3 (Seite 16) Definition von Gamma T nicht verstehe.



EDIT:

und noch was: prüfung 2011-03-11, aufgabe 1b: Wie zeigt man "formal korrekt", dass jedes Modell von Phi auch ein Modell von Psi ist?
Ein gegenbeispiel konstruieren kann ich mir noch vorstellen mit einer Interpretation. Aber ersteres?

[kuetsch]

Hallo,
ich versuch's mal grob zu beschreiben, die formal Korrekte Version findest du Ende nmr2.pdf u. gleich zu Beginn von nmr3.pdf

Hier nochmal die Angabe

W={q} ; Delta1 = {q : not p / p}

1. T = W, Delta = Delta1

2. T = W u {p}, Delta = Delta1

Grundsätzlich (also naiver Algorithmus) könnte alles mögliche eine Extension sein, aber wir können ja schon das meiste mit ein wenig Denken und Ableiten ausschließen, darum beschränken wir uns i.d.R. auch auf diese wenigen Lösungsmöglichkeiten. Vor allem hier, wo wir nur p und q haben ;-)

1.
Also wir versuchen uns mal eine Extension zu basteln. q haben wir schon, und nachdem der einzige Default nur q fordert, passt das... Außerdem nehmen wir "not p" an (weil ja noch nichts dagegenspricht) und leiten uns aus dem Default p ab.
Unsere vorgeschlagene Extension ist somit E = Cn(W u {p}) = Cn({q, p})

So, nun bilden wir das Redukt der Defaults, dh. wir nehmen alle Regeln von Delta in unser Delta_E auf, wo die Bedingungen und Justifications nicht der Extension widersprechen. Unser Redukt hat dann nur mehr Residuen (also die Defaults ohne Justifications) drin.
In unserem Fall widerspricht die Justification "not p" der Extension und wir können den Default nicht ins Redukt mitnehmen, dh. Delta_E = {}

Gamma ist nun die Überprüfung der Extension. In den Folien siehst du mal Gamma_T(E) = Cn^(Delta_E)(W). (hoffentl. kann man das ohne latex lesen...) Dh. dass das Gamma_T der Extension gleich ist der Closure über W, wenn du Delta_E (also unser Redukt) anwendest.
Gamma(E) = {q}, weil q ist schon in W und Defaults zum ableiten haben wir keine.

Nachdem Gamma(E) ≠ E --> keine Extension


2.
Hier funktioniert's genauso: Wir sehen uns mal W an, und was wir mit Delta alles ableiten können. Nachdem der einzige Default drin mit der Justification unseren Fakten widerspricht, kann ich ihn nicht anwenden. Die Extension liefert somit nichts neues, es gibt sie aber...
E = Cn(W)

Redukt siehe oben Delta_E={}

Gamma, siehe oben: Wir können nichts neues herleiten aus W und dem Delta_E, somit wird Gamma(E) = Cn({p,q}) sein.

Nun ist Gamma(E) = E --> Extension!!!


Hoffe, das hilft, und bitte korrigiert mich, falls ich einen Blödsinn schreib hier ;-) Alle Angaben ohne Gewähr ^^

Hab selbst noch eine Frage zur Closure Operation Cn(...). Wenn hier z.B. Cn(W) steht, ist dann die Standard-Annahme, dass die Closure über Delta aus T=(W,Delta) gemacht wird? Bei den Operationen mit dem Redukt schreib ich ja das Redukt extra zur Closure Op. dazu, normalerweise aber nicht...

lg kuetsch

[tass2]

Danke für die riesen mühe kuetsch. Zu deiner Frage: Ich glaube auch, es müsste korrekt Cn(T) heißen...würde irgendwie mehr Sinn machen.

Kann das noch jemand klären?

und noch was: prüfung 2011-03-11, aufgabe 1b: Wie zeigt man "formal korrekt", dass jedes Modell von Phi auch ein Modell von Psi ist?
Ein gegenbeispiel konstruieren kann ich mir noch vorstellen mit einer Interpretation. Aber ersteres?

[kuetsch]

Ich hab nie ganz verstanden, warum sie so auf eine "semantische" Lösung abfahren, m.E. ist das genau das, was du beim TC machst, nur halt nicht als Tableau angeschrieben

Ich würde es halt einfach textuell nochmal hinklatschen, also:

damit phi |= psi gilt muss phi -> psi gelten. das gilt, wenn phi ^ -psi nicht gilt.
jetzt halt die formel hinschreiben und sagen, was die einzelnen klammern sein müssten, um einen gegenbeweis konstruieren zu können...
so lange umformen, bis wir "semantisch" auf die clashes kommen und draufkommen, das, z.b. ein Atom true und false sein müsste, damit es einen geegenbeweis gäbe.
-> da der gegenbeweis unerfüllbar ist, gilt das zeugs...

bzw. halt ein gegenbeispiel finden und das zeug damit widerlegen...

[tass2]

Ja klingt gut! Habe noch was ausgegraben:

http://www.informatik-forum.at/showt...9&daysprune=-1

Bin mir bei allen 4 Punkten nicht sicher!

1) Wenn ich es in ein Tautologieproblem umforme, muss ich es noch negieren oder? Denn wenn das NEGAT überall clasht, hab ich Tautologie gezeigt
2) Keine Ahnung ob das Sinn macht. Muss ich da nicht die verschiedenen x (das mit Exists und das mit for all getrennt) substituieren und dann belegen oder so?
3) Verstehe den Sinn von U \ {1} nicht. Das fehlt ja dann auf beiden Seiten oder?
4) reicht TC?

[_gerald_]

Das Beispiel hat wohl nichts mit TC zu tun. Zur Klarstellung

Gegeben ist eine Konsequenzbehauptung A |= B

1.) Das entsprechende Tautologieproblem ist |= A -> B, weil A |= B genau dann gilt, wenn A -> B gueltig ist
2.) Das Erfuellbarkeitsproblem ist A & -B unsat., da A |= B genau dann, wenn A & -B unerfuellbar ist

ad 3.) U \ {1} bezeichnet die Domaene U ohne die {1}; sprich alle nat. Zahlen ausser 1
ad 4.) Da uns da etwas von der Angabe verheimlicht wird, hab ich keine Ahnung was bei Punkt 4 gefragt ist

[kuetsch]

Hmmm... das ist ja nett das Beispiel ;-)

ad1) Das was BSM17 schreibt, sieht aus als wäre es dasselbe wie das Erfüllbarkeitproblem? Aber irgendwo hakts da bei meinem Verständnis auch, weil ich nie verstanden hab, warum das nur Erfüllbarkeitsprob heißt, wenn ich die negation widerlege, dann hab ich ja die gültigkeit bewiesen, und nicht nur die erfüllbarkeit....

ad2) wenn ich das richtig verstehe, dann definiert er U als Nat. Zahlen und der Rückgabewert von P ist in der Interpretation auch immer in U. Dh. auf beiden seiten des entailments kann eigentlich nur immer eine natürliche zahl stehen und die verstehen wir als gültig... dh. wenn es eine ein x gibt, bei dem P(x) eine nat. zahl zurückliefert, dann gilt für alle x, dass P(x) eine nat. zahl zurückgibt.

ad3) hier versteh ich's dann nicht... wenn die interpretation von P die natürlichen zahlen ohne 1 ist, dann wirds links vom entailment "true", da dort eine beliebige zahl aus N \ {1) steht... rechts davon aber ebenfalls... warum gilt das dann nicht???

Die Interpretation von Arcticwolf drunter geht schon eher in mein Hirn... allerdings (und das verständnisproblem hatte ich auch schon bei _gerald_'s hilfreichen posts weiter oben) fällt mir schwer, warum I(P(b)) = 0 sein kann im allquantor... aber es scheint so, als wär mir gerade der knopf aufgegangen:
der allquantor ist ja im psi drin... eigentlich muss ich ja auf das psi keine rücksicht nehmen wenn ich mein U und mein I festlege... lediglich phi muss stimmen, oder?

kann bitte wer meine gedankengänge im letzten absatz hier bestätigen/widerlegen/korrigieren? der denkfehler nervt mich schon das ganze wochenende und es wär sehr hilfreich, wenn ich ihn bis zur prüfung morgen los werd ;-)

[tass2]

Gerald: Ich weiß, was U \ {1} bedeutet. Aber: Ichverstehe absolut nicht, warum Punkt 3 so funktionieren soll. Denn beide x haben ja dann die selbe Zahl, nur dass 1 nicht möglich ist.
zu dem 3:

Ex P(x) |= Vx P(x)
Wie lege ich fest, dass ich beim Existenzquantor das a verwende, und beim Allquantor das b? Streng formal?

Ich kann ja nicht einfach sagen I(P(a)) = 1, I(P(b)) = 0

Punkt 3: Bitte aufklären!

[kuetsch]

naja, das mit {a,b} ist nicht so schwer zu verstehen:

nimm an, du hast {a,b} und in deiner Interpretation ist P(a) true und P(b) false.
Jetzt gilt für die Wissensbasis, dass es ein x gibt, wo P(x) true wird. Dh. die Wissensbasis hat keinen widerspruch in sich.
Wenn ich jetzt aber die Query Vx(P(x)) daraus ableiten will, dann geht das nicht, weil dafür müsste auch P(b) true werden.
Das ist ein typisches "vom Einzelfall auf die Gesamtheit schließen" ála "Es gibt ein Tier (z.B. Hund in der Wissensbasis) das 4 Beine hat, daher haben alle Tiere 4 Beine"...

Wenn ich alle Tiere nehm und sag, es gibt ein Tier mit 4 Beinen dann stimmts (also ohne Query)
Wenn ich nur Hunde nehm und die Query "alle haben 4 Beine" davon ableite, stimmts auch

Aber wenn ich alle Tiere nehm und behaupte, weil eines existiert (z.b. Hund) das 4 Beine hat, haben alle Tiere 4 Beine, dann stimmts nicht mehr...

Die Interpretation über nat. Zahlen versteh ich auch nicht...

lg kuetsch

EDIT: 2 zeigt, dass es erfüllbar ist, und 3 zeigt, dass es widerlegbar ist, somit ist es "nur" erfüllbar... es kommt ganz einfach auf die Interpretation drauf an... die "nur-hund-interpretation für mit P(x) als "x-hat-4-beine"" ist der beweis für die erfüllbarkeit... der erweiterte mit allen tieren ist der beweis für die widerlegbarkeit

[tass2]

Stimmt, das so anzugeben dürfte klar sein. Frage nur, ob das "formal genug" ist...

[kuetsch]

Formal wäre:

2) Domäne U = {a}
I(P(a)) = 1
dann gilt das entailment

3) Domäne U = {a,b}
I(P(a)) = 1
I(P(b)) = 0
dann gilt das entailment nicht

Ist das ok, kann ma als Domäne einfach eine Menge von Bezeichnern angeben, oder muss ich dann noch weitere sachen definieren? Weil imho macht man bei Domäne U = N auch nichts anderes oder?

(man könnte auch I |= P(a) und I |≠ P(b) schreiben soweit ich weiß, die notationen sollten äquivalent sein)

lg kuetsch

[ag01]

W={q} ; Delta1 = {q : not p / p}

Bei einem solchen Default (wenn du ihn Anwenden kannst) kannst dir den Rest sparen da es keine Extension geben kann. (Anwendung des Defaults führt zu dessen nicht Anwendbarkeit.)

[kuetsch]

Bei einem solchen Default (wenn du ihn Anwenden kannst) kannst dir den Rest sparen da es keine Extension geben kann. (Anwendung des Defaults führt zu dessen nicht Anwendbarkeit.)

schon klar... wollt nur beschreiben, wie man allgemein vorgeht mit der default logik...