Klausur SS 07

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

Klausur SS 07

Beitrag von Kineese » 27. Aug 2011 18:02

Hi!
Ich hab gerade die Aufgabe 1 gemacht und da ist mir irgendwas komisch :D
\(\varphi := \neg[(p \wedge q) \vee (q \to r)]\)
\(\psi :=\neg p \wedge q \wedge \neg r\)

KNF von \(\varphi\) ist \((\neg p \vee \neg q ) \wedge q \wedge r\)
KNF von \(\neg\psi\) ist, nach benutzung der Wahrheitstabelle für \(\neg\psi\) wo \(\neg\psi = 0\) ist, \(\neg p \vee q \vee \neg r\)
Jetzt soll man mittels Resolutionskalkül \(\varphi \models \psi\) nachweisen, was also bedeutet
\([] \in Res^{*}(K(\varphi \wedge \neg\psi))\)

Ich bin mir ziemlich sicher, dass \(\varphi \models \psi\) gilt, da es bis jetzt immer so war^^, aber nach Benutzung des Kalküls hab ich am Ende nur \(\{ \neg p \}\)

Wenn wir jetzt bei der c) \(\varphi \vdash \psi\) ableiten sollen, dann fange ich mit \((\neg p \vee q ) \wedge q \wedge r \vdash \neg p \wedge q \wedge \neg r\) an.. dabei bekomme ich folgende Blätter

\(\frac{}{\neg p,q,r \vdash \neg p}Ax, \frac{}{q,r \vdash \neg p, q}Ax, \frac{}{\neg p \vee \neg q,q,r \vdash q}Ax, \frac{}{ \neg p,q,r \vdash} , \frac{}{q,r \vdash q}Ax\)
D.h. es ist nicht ableitbar... wobei es anscheinend doch so sein sollte :D

Hab ich da irgendwo einen Fehler gemacht?

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

Re: Klausur SS 07

Beitrag von fscheepy » 27. Aug 2011 18:09

Kineese hat geschrieben:Hi!
Ich hab gerade die Aufgabe 1 gemacht und da ist mir irgendwas komisch :D
\(\varphi := \neg[(p \wedge q) \vee (q \to r)]\)
\(\psi :=\neg p \wedge q \wedge \neg r\)

KNF von \(\varphi\) ist \((\neg p \vee \neg q ) \wedge q \wedge r\)
KNF von \(\neg\psi\) ist, nach benutzung der Wahrheitstabelle für \(\neg\psi\) wo \(\neg\psi = 0\) ist, \(\neg p \vee q \vee \neg r\)
Jetzt soll man mittels Resolutionskalkül \(\varphi \models \psi\) nachweisen, was also bedeutet
\([] \in Res^{*}(K(\varphi \wedge \neg\psi))\)

Ich bin mir ziemlich sicher, dass \(\varphi \models \psi\) gilt, da es bis jetzt immer so war^^, aber nach Benutzung des Kalküls hab ich am Ende nur \(\{ \neg p \}\)

Wenn wir jetzt bei der c) \(\varphi \vdash \psi\) ableiten sollen, dann fange ich mit \((\neg p \vee q ) \wedge q \wedge r \vdash \neg p \wedge q \wedge \neg r\) an.. dabei bekomme ich folgende Blätter

\(\frac{}{\neg p,q,r \vdash \neg p}Ax, \frac{}{q,r \vdash \neg p, q}Ax, \frac{}{\neg p \vee \neg q,q,r \vdash q}Ax, \frac{}{ \neg p,q,r \vdash} , \frac{}{q,r \vdash q}Ax\)
D.h. es ist nicht ableitbar... wobei es anscheinend doch so sein sollte :D

Hab ich da irgendwo einen Fehler gemacht?
Die KNF von \(\varphi\) ist doch \((\neg p \vee \neg q ) \wedge q \wedge \neg r\), oder nicht?

P.S.: check mal deine PMs

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

Re: Klausur SS 07

Beitrag von Kineese » 27. Aug 2011 18:25

Ja hatte da die negierung von Q in (notP or notQ) vergessen

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

Re: Klausur SS 07

Beitrag von Kineese » 28. Aug 2011 10:15

Habe eben nochmal die Squenz \(\neg[(p \wedge q) \vee (q \to r)] \vdash \neg p \wedge q \wedge \neg r\) abgeleitet.
Dieses mal habe ich jedoch die Linke seite etwas umgeformt:
\(\neg(p \wedge q) \wedge \neg(\neg q \vee r) \vdash \neg p\wedge q \wedge \neg r\)

Und habe es dann abgeleitet und kam zum Ergebnis dass das so stimmt!

Habe bei der 2 gemacht.
Für die (a) gilt: Überall 1 außer bei \(\neg p \wedge \neg q\wedge r\)
Bei der (b) hab ich mir etwas Hilfe aus TGdI verschafft indem ich die Wertetabelle in ein KV-Diagramm geändert habe und nachgesehen habe was ich alles zusammenfassen kann. Dabei sind zwei Lösungen erschienen: \(\neg r \vee (p\wedge r) \vee (q\wedge r\wedge \neg p)\) und \(p \vee (q\wedge \neg p) \vee (\neg p \wedge \neg q\wedge \neg r)\)
Lässt sich nicht weiter vereinfachen, sodass eine Variable rausfallen würde.

Wäre sowas in der Klausur als Lösung ausreichend?

Bei der (c) bin ich mir nicht ganz sicher wie ich die Formeln lesen soll. Soll es \((p \wedge q) \to r\) oder \(p \wedge (q \to r)\) gelesen werden?

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

Re: Klausur SS 07

Beitrag von Kineese » 28. Aug 2011 11:24

Die Aufgabe 3 habe ich mal ausgelassen, da die Skolemisierung eigentlich keine große Sache ist und der Rest nicht Klausurrelevant ist.

Aufgabe 4:
(a):
(i) Ist Falsch, da \(\varphi\) nicht allgemeingültig ist gibt es eine Belegung die \(\neg\varphi\) erfüllt
(ii) und (iii) verstehe ich nicht :oops:

(b):
\(\Gamma \models \varphi \to \psi \equiv \Gamma \models \neg\varphi\vee\psi => \Gamma \vdash \neg\varphi\vee\psi\) das ist nach Regelanwendung \(\neg R\) das gleiche wie \(\Gamma , \varphi \vdash \psi\), wobei \(\Gamma\) in KNF ist (Siehe AL-Skript Seite 17 Def. 6.1)

Aufgabe 5:
(a)
(i) \(\forall x \forall y [ Px \wedge Qy \wedge ( x < y \vee y < x)]\)
(ii) \(\forall x \forall y \exists z [Px \wedge Py \wedge Qz \wedge x < z \wedge z < y]\)
(iii) \(\forall x_{1} \forall x_{2} ... \forall x_{n} [ Px_{1} \wedge Px_{2} \wedge ... \wedge Px_{n} \wedge x_{1} < x_{2} \wedge ... \wedge x_{n-1} < x_{n}]\)

(b)
(i)\(\varphi\) sagt aus, dass wenn x,y und z weiß sind und x<y<z , dann muss es ein schwarzes w geben, mit x<w<z.
Das gilt bei B für den ersten Teil \(\bullet - \circ- \circ- \bullet\) , aber für den zweiten Teil \(\bullet - \circ - \circ - \circ - \circ - \circ - \bullet\) gilt es nicht: Angenommen x sei das erste \(\circ\), y das zweite \(\circ\) und z das letzte \(\circ\) in dieser Sequenz, so müsste es nach \(\varphi\) ein \(\bullet\) geben dazwischen geben.

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

Re: Klausur SS 07

Beitrag von fscheepy » 28. Aug 2011 12:08

Kineese hat geschrieben:Die Aufgabe 3 habe ich mal ausgelassen, da die Skolemisierung eigentlich keine große Sache ist und der Rest nicht Klausurrelevant ist.

Aufgabe 4:
(a):
(i) Ist Falsch, da \(\varphi\) nicht allgemeingültig ist gibt es eine Belegung die \(\neg\varphi\) erfüllt
(ii) und (iii) verstehe ich nicht :oops:

(b):
\(\Gamma \models \varphi \to \psi \equiv \Gamma \models \neg\varphi\vee\psi => \Gamma \vdash \neg\varphi\vee\psi\) das ist nach Regelanwendung \(\neg R\) das gleiche wie \(\Gamma , \varphi \vdash \psi\), wobei \(\Gamma\) in KNF ist (Siehe AL-Skript Seite 17 Def. 6.1)

Aufgabe 5:
(a)
(i) \(\forall x \forall y [ Px \wedge Qy \wedge ( x < y \vee y < x)]\)
(ii) \(\forall x \forall y \exists z [Px \wedge Py \wedge Qz \wedge x < z \wedge z < y]\)
(iii) \(\forall x_{1} \forall x_{2} ... \forall x_{n} [ Px_{1} \wedge Px_{2} \wedge ... \wedge Px_{n} \wedge x_{1} < x_{2} \wedge ... \wedge x_{n-1} < x_{n}]\)

(b)
(i)\(\varphi\) sagt aus, dass wenn x,y und z weiß sind und x<y<z , dann muss es ein schwarzes w geben, mit x<w<z.
Das gilt bei B für den ersten Teil \(\bullet - \circ- \circ- \bullet\) , aber für den zweiten Teil \(\bullet - \circ - \circ - \circ - \circ - \circ - \bullet\) gilt es nicht: Angenommen x sei das erste \(\circ\), y das zweite \(\circ\) und z das letzte \(\circ\) in dieser Sequenz, so müsste es nach \(\varphi\) ein \(\bullet\) geben dazwischen geben.
4a) stimme ich dir zu. (i) hab ich genau so, (ii) und (iii) bin ich ebenfalls nicht sicher, was gemeint ist. Ich nehme mal an, dass man darauf hinaus soll, dass es bei erfüllbaren Formeln ein x gibt, das
die Formel erfüllt (wo wird denn da das x eingesetzt?) aber die Formel nicht für alle x erfüllbar ist (?).
4b) Ja, bei (1) Implikation ersetzen, dann kommt man mit vL auf (2), dort mit \(\neg R\) auf (3)

5a) Hier hätte ich eher eine Implikation verwendet: (Px ^ Qy) -> ((x < y) v (y < x))
5b) Ebenfalls mit Implikation: (Px ^ Py ^ Qz ^ x < y) -> (x < z ^ z < y)
5c) Das habe ich formuliert mit: \(\forall x \exists y\) ((Px v Qx) ^ Py) -> (x < y)

mc_doa
Gast

Re: Klausur SS 07

Beitrag von mc_doa » 28. Aug 2011 19:22

allo ,

woher habt ihr die alten klausuren ??
Könntet ihr die hier vllt. hochladen so dass andere studenten sie auch durchrechnen könnten :)

Danke


mc_D.

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

Re: Klausur SS 07

Beitrag von eintopf » 28. Aug 2011 19:34


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

Re: Klausur SS 07

Beitrag von eintopf » 30. Aug 2011 11:14

Meine Ergebnisse / Antworten

Zur 4)
a)

i) Ist Falsch. Sei Phi eine erfüllbare, aber nicht allgemein gültige Formel. So gibt es Interpretationen, die Phi NICHT wahr machen, genau diese Interpretationen machen !Phi wahr.

ii) Richtig. Wenn x nicht aus den freien Variablen von Phi ist, gilt die Aussag eh, da Phi erfüllbar ist.
Wenn x aus den freien Variablen von Phi ist, dann "findet" der E-Quantor eine Belegung, die Phi wahr macht -> efüllbar.

ii) Falsch. Sei Phi erfüllbar aber nicht allgemein gültig und x aus den freien Variablen von Phi, so gibt es Belegungen von x, die Phi nicht wahr machen (da nicht allgemeingültig). \(\forall x\)Phi sagt aber genau, dass es für alle Belegungen von x gelten soll, was ein Widerspruch ist.

b)

(1) lässt sich umformen zu T |= !Phi v Psi.
(2) gilt laut Defi. genau dann wenn, T |= !Phi v Psi, somit (1) <=> (2)
(3) Lässt sich durch Regelanwendung !R auf (2) bekommen

Zur 5)
a)

i) \(\neg(\exists t Q(t) \land P(t))\)
ii) \(\neg (\exists x\exists y x < y \land \neg\exists z ( x < z \land z < y) \land P(x) \land P(y))\)
iii) \(\forall x \exists y (x < y \land P(y)\)
(das Heißt für jeden Zeitpunkt x gibt es einen späteren Zeitpunkt y, an dem Zustand P gilt => unendlich, da Trägermenge unendlich)

b)
i) (Semantikspiel) Mit der Belegung x = 5, y = 6, z = 7 lässt sich kein w finden, sodass die Aussage gilt.
ii) was haltet ihr von f(x,y,z)^A = y ?
iii) Fehlt mir :( Komme nur auf Formeln die mehr Quantoren brauchen :/

Antworten

Zurück zu „Archiv“