Prüfung WS 07 08

Kineese
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 14. Feb 2008 18:33

Prüfung WS 07 08

Beitrag von Kineese » 19. Aug 2011 14:28

Hi!
Ich bin gerade dabei die alte Klausur zu machen
Link zu klausur findet ihr hier: http://d120.de/forum/download/file.php?id=1001

Bin mittlerweile bei Aufgabe 2 a:
Bei der \(\neg\psi =\neg(\exists x \exists y (R_{xy} \land P_{x} \land P_{y}))\) habe ich als Ergebnis
\(\neg \psi = \forall x \forall y (\neg R_{xy} \vee \neg P_{x} \vee \neg P_{y})\)

Bin mir aber nicht sicher ob das so richtig ist, da ich irgendwo mal gelesen habe dass die Negation von Quantoren nur auf einen einzigen bezieht.

ez22
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 28. Mär 2011 14:52

Re: Prüfung WS 07 08

Beitrag von ez22 » 19. Aug 2011 18:46

eine gute frage,

in buch vom schöning aufgabe 63, dort bezieht sich die negation auf zwei terme. so wie du auch gemacht hast. bin übrigens bei der aufgabe genauso vorgegangen, hab das gleiche ergebnis

*eine gute frage für die sprechstunde am montag

Benutzeravatar
Domac
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 160
Registriert: 4. Okt 2010 16:11

Re: Prüfung WS 07 08

Beitrag von Domac » 20. Aug 2011 01:36

Kineese hat geschrieben: Bei der \(\neg\psi =\neg(\exists x \exists y (R_{xy} \land P_{x} \land P_{y}))\) habe ich als Ergebnis
\(\neg \psi = \forall x \forall y (\neg R_{xy} \vee \neg P_{x} \vee \neg P_{y})\)

Bin mir aber nicht sicher ob das so richtig ist, da ich irgendwo mal gelesen habe dass die Negation von Quantoren nur auf einen einzigen bezieht.
Servus!
Ich bestätige deine Lösung... ;)
\(\neg\psi =\neg(\exists x \exists y (R_{xy} \land P_{x} \land P_{y})) \equiv \neg \exists x \neg \exists y \neg(R_{xy} \land P_{x} \land P_{y})) \equiv \forall x \forall y (\neg R_{xy} \vee \neg P_{x} \vee \neg P_{y})\) ... die Negation wird ja praktisch mit den einzelnen Quantoren und Termen "ausmultipliziert", wobei man das hier nicht all zu laut sagen darf. ;-)
Gruß domac
Extend my dropbox space (here).
Thanks!

Kineese
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 14. Feb 2008 18:33

Re: Prüfung WS 07 08

Beitrag von Kineese » 20. Aug 2011 12:00

Habe jetzt auch mal eine Frage zu der Aufgabe 1 a.

Ich hab phi auf zwei unterschiedlichen wegen mal vereinfacht, sprich die implikation raus gekommen und ich bekomme bei einer Variante das Ergebnis dass phi allg.gültig ist und beim anderen halt nicht....
Habs versucht mit Wolfram-Alpha anzeigen zu lassen nur kennt er da die implikation nicht :(

Hat da jemand da was gescheites?

Benutzeravatar
Domac
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 160
Registriert: 4. Okt 2010 16:11

Re: Prüfung WS 07 08

Beitrag von Domac » 20. Aug 2011 12:21

\(\varphi := [\neg(p \rightarrow q) \wedge (r \rightarrow \neg (p \vee r))] \rightarrow (p \vee \neg (q \rightarrow r ))\)

\(p | q | r | \neg ( p \rightarrow q) | r \rightarrow \neg (p \wedge r) | p \vee \neg (q \rightarrow r) | \varphi\) ... fülle diese Wahrheitstabelle aus, dann hast du die 1a) erledigt.

Gruß domac

PS.: Das Teil ist allgemeingültig. ;)
Extend my dropbox space (here).
Thanks!

Benutzeravatar
nine
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 13. Okt 2010 20:35

Re: Prüfung WS 07 08

Beitrag von nine » 26. Aug 2011 14:17

Hey,
habt ihr euch schon mit der 4b) beschäftigt? Hat jemand da eine Lösungsidee?
lg

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

Re: Prüfung WS 07 08

Beitrag von fscheepy » 27. Aug 2011 16:08

nine hat geschrieben:Hey,
habt ihr euch schon mit der 4b) beschäftigt? Hat jemand da eine Lösungsidee?
lg
Was sind denn die Lösungen zur 4a)? Meine Ideen wären:
(i) Wahr, man kann bei endlicher Variablenanzahl alle Belegungen durchprobieren. Ist die Anzahl Variablen unendlich, hängt laut Kompaktheitssatz die Folgerungsbeziehung nur von einer endlichen Anzahl Variablen ab. (muss man bei diesen Aufgaben auch unendliche Formelmengen bzw. Formeln mit unendlich vielen Variablen in die Lösung mit einbeziehen oder habe ich da etwas falsch verstanden?)
(ii) Falsch, da es eine unendliche Anzahl an möglichen einsetzbaren Termen gibt und somit nicht immer in endlicher Zeit entschieden werden kann, ob die Beziehung gilt. (?)
(iii) Es gibt also keine Belegung, die beide Formeln gleichzeitig wahr macht, aber eine der Formeln ist immer wahr. Somit ist die andere Formel immer falsch und die Äquivalenz gilt. (oder?)
(iv) Falsch, nehmen wir an es gäbe 8 verschiedene Belegungen für die Formeln und 4 davon machten phi wahr und die anderen 4 machten psi wahr. Des weiteren machten alle dieser Belegungen psi v phi wahr (da es ja allgemeingültig ist). Somit ist keine der Formeln ansich allgemeingültig, ihre Disjunktion aber schon.

Inwiefern sind meine Lösungen (insbesondere formal gesehen) richtig/falsch?

Bei der b) habe ich keine Ahnung. Kann man da irgendwie argumentieren, dass man hierbei eine Formalisierung über die Trägermenge von E machen müsste, was in FO nicht möglich ist?

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

Re: Prüfung WS 07 08

Beitrag von eintopf » 28. Aug 2011 17:24

Habe die selben Wahr / Falsch Zuordnungen ... mit Formalisierung nun ja :mrgreen:
Lediglich bei der (i) weiß ich, dass man dafür ja das Resolutionsverfahren nutzen kann.

Hat jemand schon die 5) gemacht?

Meine Ergebnisse für die 5. Aufgabe:

a)
i) \(\exists x \exists y \exists z (Px \land Py \land Pz \land \neg x=y \land \neg x=z \land \neg y=z )\)
ii) \(\forall x \forall y (Exy \rightarrow ((Px \land Qy) \lor (Py \land Qx)))\)
iii) \(\forall x (Qx \rightarrow (\exists y Exy \land Py))\)

b)

- H = {T0(S), R^H, f^H}
- f wie üblich
- T0(S) = {c, fc, ffc, ffc, ...}
- R^H = { (f^n(c), f^(n-1)(c)) : n > 0}

Was sagt ihr dazu?
Zuletzt geändert von eintopf am 28. Aug 2011 18:51, insgesamt 1-mal geändert.

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

Re: Prüfung WS 07 08

Beitrag von fscheepy » 28. Aug 2011 17:48

eintopf hat geschrieben: a)
i) \(\exists x \exists y \exists z (Px \land Py \land Pz \land \neg x=y \land \neg x=z \land \neg y=z )\)
ii) \(\forall x \forall y (Exy \rightarrow ((Px \land Qy) \lor (Py \land Qx)))\)
iii) \(\forall x (Qx \rightarrow (\exists y Rxy \land Py))\)
Bei der (i) auf richtige Klammerung achten, bei der (ii) würde ich den hinteren Teil weglassen, da ich nicht davon ausgehe, dass die Kantenrelation hier kommutativ ist, bei der (iii) meinst du sicherlich Exy statt Rxy? Ansonsten hab ich es genau so.

Bei der b) hatte ich die gleiche Idee, hätte es aber anders formuliert: R^H = {(f(t), t) : t element von T0(S)}

keine Ahnung, wie man sowas richtig formalisiert :(

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

Re: Prüfung WS 07 08

Beitrag von eintopf » 28. Aug 2011 18:51

Bei der (i), was meinst du mit korrekter Klammerung? Würde das schon so hinschreiben wie ich es hier hingeschrieben habe :D

bei der (ii) glaub ich hast du recht, was hälst du von:
\(\forall x \forall y (Exy \rightarrow (Px \land Qy))\)
D.h. wenn eine Kante Exy existiert, dann hat Startknoten x die Eigentschaft P und Endknoten y die Eigentschaft Q.

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

Re: Prüfung WS 07 08

Beitrag von fscheepy » 28. Aug 2011 20:08

eintopf hat geschrieben:Bei der (i), was meinst du mit korrekter Klammerung? Würde das schon so hinschreiben wie ich es hier hingeschrieben habe :D

bei der (ii) glaub ich hast du recht, was hälst du von:
\(\forall x \forall y (Exy \rightarrow (Px \land Qy))\)
D.h. wenn eine Kante Exy existiert, dann hat Startknoten x die Eigentschaft P und Endknoten y die Eigentschaft Q.
Sorry, da hab ich mich missverständlich ausgedrückt - es geht darum, dass man meiner Meinung nach schreibt "~(x = y)" statt "~x = y", da sich die Negation auf den Vergleich und nicht das x bezieht (würde ja auch sonst keinen Sinn machen). Und ja, so würde ich die (ii) auch formalisieren.

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

Re: Prüfung WS 07 08

Beitrag von eintopf » 28. Aug 2011 20:28

Stimmt, du hast recht, danke!

Ankou
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 15. Mai 2011 18:23

Re: Prüfung WS 07 08

Beitrag von Ankou » 29. Aug 2011 13:43

meine Lösung zur 4b) (eine ähnliche Aufgabe gab es in einer älteren Klausur, da gabs aber irgendwie noch eine kurze hinführung insofern, dass man zuerst Formeln angeben sollte, die unendlich viele Äquivalenzklassen sicherstellen). Die Art der Notation von \(\varphi_n\) habe ich der Lösung zur Übung 14 entnommen, den inhalt allerdings nicht, müsste das ausdrücken was ich geschrieben habe, wenn ihr anderer Meinung seid schreit hier ma laut auf :p -

Angenommen \(\psi\) ist eine FO Formelmenge, die genau dann erfüllt ist, wenn E endlichen Index hat.
Sei \(\varphi_n, n \in \mathbb{N}\) eine FO Formel, die genau dann wahr ist, wenn E mindestens n Äquivalenzklassen hat, \(\varphi_n\) lässt sich definieren als:
\(\varphi_n := \exists x_1...x_n \bigwedge_i (\bigwedge_{j \neq i} \neg (Ex_i x_j))\)
Dann sei \(\phi\) die vereinigung aller \(\varphi_n\) \(\phi := \bigcup_n \varphi_n\) die unendliche Formelmenge, die genau dann wahr ist, wenn der Index von E größer als jedes \(n \in \mathbb{N}\) sprich unendlich ist.
Sei \(\phi' := \phi \cup \psi\), dann gilt:
-\(\phi'\) ist genau dann wahr, wenn E gleichzeitig unendlich und endlich viele Äquivalenzklassen hat, sprich unerfüllbar
-jede endliche Teilmenge \(\phi''\) von \(\phi'\) ist erfüllbar durch ein E mit endlich vielen Äquivalenzklassen mindestens jedoch n für das in \(\phi''\) enthaltene \(\varphi_n\) mit dem höchsten n, nach Kompaktheitssatz ist also \(\phi'\) ebenfalls erfüllbar.
\(\phi'\) ist also sowohl erfüllbar als auch unerfüllbar und stellt somit einen widerspruch dar, ein solches \(\psi\) kann es also nicht geben.

es geht darum, dass man meiner Meinung nach schreibt "~(x = y)" statt "~x = y"
Gleichheit ist in FO sowieso für Terme zulässig, daher ist es eindeutig und somit denke ich, dass es auch wayne ist ob nun geklammert oder nicht.

Antworten

Zurück zu „Archiv“