Klausur WS 06/07

bafnai
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 126
Registriert: 13. Apr 2011 06:36

Klausur WS 06/07

Beitrag von bafnai » 25. Aug 2011 17:29

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

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: Klausur WS 06/07

Beitrag von dschneid » 25. Aug 2011 18:50

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\).

eintopf
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 25. Aug 2011 17:41

Re: Klausur WS 06/07

Beitrag von eintopf » 29. Aug 2011 20:38

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:

fscheepy
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 153
Registriert: 14. Dez 2009 21:17

Re: Klausur WS 06/07

Beitrag von fscheepy » 30. Aug 2011 17:48

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?

MirkoK
Erstie
Erstie
Beiträge: 12
Registriert: 28. Sep 2010 17:00

Re: Klausur WS 06/07

Beitrag von MirkoK » 31. Aug 2011 14:31

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.

dimitrov89
Windoof-User
Windoof-User
Beiträge: 32
Registriert: 2. Mai 2011 10:43

Re: Klausur WS 06/07

Beitrag von dimitrov89 » 1. Sep 2011 10:58

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

dimitrov89
Windoof-User
Windoof-User
Beiträge: 32
Registriert: 2. Mai 2011 10:43

Re: Klausur WS 06/07

Beitrag von dimitrov89 » 1. Sep 2011 11:04

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:

eintopf
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 25. Aug 2011 17:41

Re: Klausur WS 06/07

Beitrag von eintopf » 1. Sep 2011 11:15

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 :)

fscheepy
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 153
Registriert: 14. Dez 2009 21:17

Re: Klausur WS 06/07

Beitrag von fscheepy » 1. Sep 2011 11:30

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.

Antworten

Zurück zu „Archiv“