Seite 1 von 1

Klausur WS 06/07

Verfasst: 25. Aug 2011 17:29
von bafnai
Hallo,
ein kleiner Ausschnitt aus der Klauser aus dem WS 06/07:

Aufgabe 5
\(( \mathbb N\ ,\)<\(,P,Q,R)\)
\(P, Q, R\) einstellige Relationen

(b) Beweisen Sie mit Hilfe des FO-Sequenzenkalküls, dass
\(\forall x \exists y(x\\)<\(\ y \wedge Py)\models \exists x Px\).

Hat jemand eine Idee, wie man auf den Ansatz für den Sequenzenkalkül kommt?

MfG bafnai

Re: Klausur WS 06/07

Verfasst: 25. Aug 2011 18:50
von dschneid
Die Folgerungsbeziehung gilt, wenn man die Sequenz \(\forall x \, \exists y \, (x < y \wedge Py) \vdash \exists x \, Px\) herleiten kann.

Man kann z.B. mit der Regel (Ax) die Sequenz \(c' < c, Pc \vdash Pc\) erzeugen. Mit der Regel (\(\wedge L\)) bekommt man \(c' < c \wedge Pc \vdash Pc\), mit der Regel (\(\exists R\)) dann \(c' < c \wedge Pc \vdash \exists x \, Px\), weiter mit der Regel (\(\exists L\)) die Sequenz \(\exists y \, (c' < y \wedge Py) \vdash \exists x \, Px\) und schließlich mit der Regel (\(\forall L\)) \(\forall x \, \exists y \, (x < y \wedge Py) \vdash \exists x \, Px\).

Re: Klausur WS 06/07

Verfasst: 29. Aug 2011 20:38
von eintopf
Hat jemand die anderen Aufgaben schon bearbeitet?

Hier meine Lösungsvorschläge:

1)
a) Wertetabelle => nicht allgemeingültig, aber erfüllbar (3 Belegungen gehen NICHT)

b) KNF: (p v !q v !r) ^ (!p v q v r) ^ (!p v !q v !r)

c) Nun ja ich find die Aufgabe sehr komisch formuliert, aber mein Versuch:
Phi1(x1, y1) = y1 v !x1
Phi2(x1, x2, y1, y2) = (y2 ^( (x1 ^ x2) v (!x1 ^ !x2) ) ) ^ Phi1
Phi n bzw. Phi n+1 bin ich nicht drauf gekommen - jemand einen Ratschlag?

2)
a) T(S) = {c}, R^H = T(S)xT(S) (= {(c,c)})

b) Auch hier bin ich mir nicht sicher, was ist mit Modell mit 3 Elementen gemeint? Trägermenge aus 3 Elementen?
T(S) = {c, fc, ffc)
R^H = {(f^n(c), f^n+1(c) : n elem N }

3) (Nur a) für Klausur relevant)
a) Phi1, Phi2, Phi3 sind in SNF

4)
a) Richtig. Beweis durch Sequenzenkalkül (\(1.\forall R 2.\forall L 3. \forall L 4. \forall L 5. \land R 6. Ax - Ax\)
b) Bin mir unsicher
c) Falsch, da O' |= Phi auch gilt, wenn beide nicht erfüllt werden. (O' |= Phi <=> I |= O' => I |= Phi <=> not(I |= O') v I |= Phi)
d) Richtig? Bin mir nicht sicher, aber ist es nicht eine Schlussfolgerung, die man aus dem Kompaktheitssatz ziehen kann?

5) Auch hier ist die Aufgabenstellung nicht eindeutig wie ich finde
a)
i) \(\forall x P(x)\) Zumindest ist die Aussage so erfüllt?
ii) \(\forall x ( Q(x) \rightarrow (\exists y x < y \land R(y)))\)
iii) \(\forall x ( \neg (Px \land Qx))\) Was heißt "direkter Wechsel"? Ist hier gemeint, dass man zum selben Zeitpunkt t keinen Wechsel erreichen kann, sondern frühstens im nächsten Zeitpunkt t+1?

:mrgreen:

Re: Klausur WS 06/07

Verfasst: 30. Aug 2011 17:48
von fscheepy
eintopf hat geschrieben:Hat jemand die anderen Aufgaben schon bearbeitet?

Hier meine Lösungsvorschläge:

1)
a) Wertetabelle => nicht allgemeingültig, aber erfüllbar (3 Belegungen gehen NICHT)

b) KNF: (p v !q v !r) ^ (!p v q v r) ^ (!p v !q v !r)

c) Nun ja ich find die Aufgabe sehr komisch formuliert, aber mein Versuch:
Phi1(x1, y1) = y1 v !x1
Phi2(x1, x2, y1, y2) = (y2 ^( (x1 ^ x2) v (!x1 ^ !x2) ) ) ^ Phi1
Phi n bzw. Phi n+1 bin ich nicht drauf gekommen - jemand einen Ratschlag?
Wertetabelle habe ich auch so, KNF ist bei mir
(!p v q v r) ^ p ^(!r v !q)

bei der c) habe ich nach längerem rumprobieren:
Phi1 := y1 <-> !x1
Phi2 := Phi1 ^ (y2 <-> ((!y1 ^ x2 ) v (y1 ^ !x2)))
Phin -> Phin+1 ist dann wohl:
Phin ^ (yn+1 <-> ((!yn ^ xn+1) v (yn ^ !xn+1)))
Also man nimmt immer Phin und hängt daran noch die Bedindung, dass yn+1 genau dann 1 ist, wenn yn = 0 war und xn+1 = 1 ist oder yn =1 und xn+1 = 0. Was haltet ihr davon?

Ist zwar keine super formale Lösung, aber eine Idee und ich denke so würd ichs auch in der Klausur hinschreiben :mrgreen:

So, ich mach dann mal die Klausur weiter und editiere meinen Beitrag später.


/Edit1:
Aufgabe 2:
gehört hier nicht T0(S) hin, welches {c, fc, ffc,...} ist? Ansonsten denke ich nicht, dass R = TxT ist, da (c, fc) nicht in R enthalten ist. Ich hab mir gedacht, man könnte für die Relation vielleicht {(f^n(x), f^n(c) : n aus N} wählen?

bei der b) ebenfalls keine Ahnung, was genau ein Modell mit 3 Elementen ist. Wenn es wirklich um eine dreielementige Trägermenge geht, scheint aber dein Modell korrekt zu sein (auch, wenn ich von Herbrandmodellen nicht sonderlich viel Ahnung habe, da das meiner Meinung nach sehr unzureichend erklärt wurde).

/Edit2:
3 habe ich genau so, Phi1-3 sind schon in SKNF, für !Psi habe ich:\(1.\forall y (Rcfy \land Rfyy)\)

Zur 4:
a) Richtig, Beweis hätte ich selbst formuliert ("es gilt für alle x und alle y, also lässt sich kein x finden, sodass blabla nicht gilt).
b) Auch unsicher, hätte aber mit dem Kompaktheitssatz argumentiert, dass es falsch ist.
c) Falsch, beispielsweise wenn Phi unerfüllbar ist.
d) Kann man da nicht ein Gegenbeispiel finden? Phi = {(p ^ q), r}; Psi = {r}? Oder denke ich mir das gerade zu einfach?

5a:
Hätte ich jeweils umformuliert (und dann formalisiert) zu:
i) Für alle x gibt es ein y, sodass gilt: ((x < y) ^ Py)
ii) Für alle x gibt es ein y, sodass gilt: (Qx -> (x < y) ^ Ry)
iii) Für alle x und alle y gibt es ein z, sodass gilt: ((x < y) ^ Px ^ Qy) -> ((x < z) ^ (z < y) ^ !Qz)

5b:
Hier bin ich mir nicht sicher, welche Schritte genau nötig sind. Durchgeführt habe ich, von unten nach oben gelesen:
\(\exists L\) -> \(\exists R\) -> habe da jeweils die Variable durch eine Konstante d ersetzt - muss ich jetzt noch weitermachen? Denn um die Konjunktion links aufzulösen, habe ich dann noch \(\forall L\) benutzt (hier kann man einen beliebigen Term einsetzen) -> \(\land L\) -> jetzt steht \(Pd\) links und rechts und man kann \(Ax\) benutzen. Geht das auch kürzer?

Re: Klausur WS 06/07

Verfasst: 31. Aug 2011 14:31
von MirkoK
Aufgabe 2 b) Auch hier bin ich mir nicht sicher, was ist mit Modell mit 3 Elementen gemeint? Trägermenge aus 3 Elementen?
T(S) = {c, fc, ffc)
R^H = {(f^n(c), f^n+1(c) : n elem N }
Ich bin mir auch nicht ganz sicher, aber ich habe mir das so gedacht, dass man nicht unbedingt ein Herbrandmodell angeben muss. Ich habe mir da folgendes überlegt:
Modell A = (N,R,f,0) mit den natürlichen Zahlen N als Trägermenge, der konstanten 0, der Nachfolgerfunktion f (also fx = x + 1) und der kleiner-als-Relation R (also R = {(a,b)| a,b sind Element aus N und a < b}
Zur 4:
d) Kann man da nicht ein Gegenbeispiel finden? Phi = {(p ^ q), r}; Psi = {r}? Oder denke ich mir das gerade zu einfach?
Das Gegenbeispiel ist falsch, da phi keine Teilmenge von psi ist (was per Definition gelten muss). Ich würde sagen die Aussage gilt, da jede Interpretation die alle Formeln in psi wahr macht auch insbesondere phi wahr macht. Denn es können nur Formeln in phi sein, die auch in psi sind.

Re: Klausur WS 06/07

Verfasst: 1. Sep 2011 10:58
von dimitrov89
MirkoK hat geschrieben:
Ich bin mir auch nicht ganz sicher, aber ich habe mir das so gedacht, dass man nicht unbedingt ein Herbrandmodell angeben muss. Ich habe mir da folgendes überlegt:
Modell A = (N,R,f,0) mit den natürlichen Zahlen N als Trägermenge, der konstanten 0, der Nachfolgerfunktion f (also fx = x + 1) und der kleiner-als-Relation R (also R = {(a,b)| a,b sind Element aus N und a < b}
Also, das ist falsch.
Es gilt wenn R ist "großer gleich" (≥)
fx = x+1
Dann:
1.) x≥x
2.) !(x≥x+1)
3.) x≥y+1 => x≥y

Re: Klausur WS 06/07

Verfasst: 1. Sep 2011 11:04
von dimitrov89
eintopf hat geschrieben:
b) Auch hier bin ich mir nicht sicher, was ist mit Modell mit 3 Elementen gemeint? Trägermenge aus 3 Elementen?
T(S) = {c, fc, ffc)
R^H = {(f^n(c), f^n+1(c) : n elem N }
Wir können das folgendes Modell betrachten:
Graph mit 3 Knoten (a,b,c) mit den folgenden Relationen:
aRb, bRc, cRa,
also ein Zyklus mit nur diese 3 Kanten.

Ich bin aber nicht sicher, ob wir das machen sollen oder was ganz anderes... :oops:

Re: Klausur WS 06/07

Verfasst: 1. Sep 2011 11:15
von eintopf
dimitrov89 hat geschrieben:
eintopf hat geschrieben:
b) Auch hier bin ich mir nicht sicher, was ist mit Modell mit 3 Elementen gemeint? Trägermenge aus 3 Elementen?
T(S) = {c, fc, ffc)
R^H = {(f^n(c), f^n+1(c) : n elem N }
Wir können das folgendes Modell betrachten:
Graph mit 3 Knoten (a,b,c) mit den folgenden Relationen:
aRb, bRc, cRa,
also ein Zyklus mit nur diese 3 Kanten.

Ich bin aber nicht sicher, ob wir das machen sollen oder was ganz anderes... :oops:
So ähnlich würde ich es auch in der Klausur machen und habe ich dann auch bei anderen Klausuren nun so gemacht, funktionierte recht gut :)

Re: Klausur WS 06/07

Verfasst: 1. Sep 2011 11:30
von fscheepy
MirkoK hat geschrieben:
Zur 4:
d) Kann man da nicht ein Gegenbeispiel finden? Phi = {(p ^ q), r}; Psi = {r}? Oder denke ich mir das gerade zu einfach?
Das Gegenbeispiel ist falsch, da phi keine Teilmenge von psi ist (was per Definition gelten muss). Ich würde sagen die Aussage gilt, da jede Interpretation die alle Formeln in psi wahr macht auch insbesondere phi wahr macht. Denn es können nur Formeln in phi sein, die auch in psi sind.
Ja, das stimmt natürlich, keine Ahnung, welcher Teufel mich da geritten hat :mrgreen: die Aussage ist meiner Meinung nach richtig.