Prüfung Ws 07/08 Sequenzenregeln beweisen

onbes
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 30. Jul 2011 18:43

Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von onbes » 17. Aug 2011 17:07

Moin Leute,

ich habe mich mal an der A3 a versucht und weiß aber nicht, ob das so richtig bzw. ausreichend ist.
Ist die Lösung richtig?

i) nicht gültig

Prämisse: Γ,¬φ |- Δ, ¬ψ
Konklusion: Γ,φ |- Δ, ψ

Begründung:
Sei I ein Modell der Prämisse. => I ist Modell von Γ und I ist Modell von ¬φ.
Nach Annahme ist I Modell von mindestens einem δ Є Δ U {¬ψ}. Wenn I Modell von Γ und ¬φ
und die Prämisse per Voraussetzung allgemeingültig ist kann das Modell I die Konklusion
Γ und φ garnicht mehr erfüllen, weil wenn ¬φ allgemeingültig, dann muss φ nicht erfüllbar sein -> Sequenzregel nicht korrekt.


ii) nicht gültig

Prämisse: Γ,¬ψ |- Δ, ¬φ
Konklusion: Γ,φ |- Δ, ψ

Begründung:
Angenommen Γ,¬ψ |- Δ, ¬φ ist allgemeingültig.
Sei I also ein Modell δ Є Δ U {¬φ}
Falls δ Є (¬φ) muss I(φ) = 0 sein. Somit ist I(Γ,φ) = 0 (also Konklusion nicht allgemeingültig)
Falls δ Є Δ ist I(Γ,φ) = 1 und daraus folgt, dass I(Δ,ψ) = 1.
Die Belegung I(ψ) = 1 widerspricht aber dem I(Γ,¬ψ) = 1

iii) gültig

Prämisse: Γ,∀xφ |- Δ
Konklusion: Γ |- Δ, ∃xφ

Begründung:
Angenommen Γ,∀xφ |- Δ ist allgemeingültig und I ein Modell von Δ.
Demnach ist die Konklusion auch gültig, weil I(Γ) = 1 und somit die Interpretation I das Δ mit 1 belegt.

Wobei ich mir bei iii) nicht ganz sicher bin, weil es unvollständig ausschaut (da ich nicht auf den All- und Existensquantor eingegangen bin)


Schönen Gruß 8)
onbes
Dateianhänge
Alte_Klausur_FGDI2_Ws_07_08.PDF
Prüfung FGdI2 WS 07/08
(664.17 KiB) 233-mal heruntergeladen

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von Domac » 17. Aug 2011 17:16

Servus onbes!
Wie hast du denn die 2 b) gelöst? Kann mich nicht daran erinnern, dass wir SKNF je in Klauselform gebracht haben.
Gruß domac

EDIT: Ich werde mich später auch nochmal an die Aufgabe 3 setzen und dann Bericht erstatten! :D
EDIT2: rotflshmsfoaidmt... danke dir onbes! Das ist mir jedoch neu :P
Zuletzt geändert von Domac am 17. Aug 2011 17:39, insgesamt 2-mal geändert.
Extend my dropbox space (here).
Thanks!

onbes
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 30. Jul 2011 18:43

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von onbes » 17. Aug 2011 17:36

Domac hat geschrieben:Servus onbes!
Wie hast du denn die 2 b) gelöst? Kann mich nicht daran erinnern, dass wir SKNF je in Klauselform gebracht haben.
Gruß domac

Moin Domac,

finde es gerade in dem Haufen Blätter nicht, sonst würd ich es posten.
Habe aber in Erinnerung, dass ich es 1 zu 1 wie im FGdI2 Script zur Logik 1. Stufe auf Seite 23 oben bei Beispiel 5.2 gemacht habe.

Gruß onbes

EDIT@Domac: Bin auch nur durch Zufall im Skript darauf gestoßen :lol:

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von Domac » 17. Aug 2011 18:53

Wie siehts eigentlich mit Reduktion von FO auf AL aus? Das haben wir doch auch nicht wirklich durchgesprochen...
Gruß domac

EDIT: Wenn ich das richtig verstanden habe:
a)
\(\varphi_1 = \forall x \forall y (Rxy \rightarrow (Pf(x,y) \wedge Rxf(x,y) \wedge Rf(x,y)y)\)
\(\varphi_2 = \forall x (Rxg(x))\)
\(\psi = Rcg(c) \wedge Pc \wedge Pg(c)\)

b)
\(\varphi_1 \wedge \varphi_2 \wedge \neg \psi \equiv
\forall x \forall y (Rxy \rightarrow (Pf(x,y) \wedge Rxf(x,y) \wedge Rf(x,y)y) \wedge
\forall x (Rxg(x)) \wedge
\neg (Rcg(c) \wedge Pc \wedge Pg(c))\)

\(\equiv (\neg (Rxy) \vee Pf(x,y) \wedge \neg (Rxy) \vee Rxf(x,y) \wedge \neg (Rxy) \vee Rf(x,y)y)) \wedge
Rxg(x) \wedge \neg (Rcg(c) \wedge Pc \wedge Pg(c))\)

Stimmt das so ungefähr? Wenn nein, wie genau verfahre ich bei SKNf -> Klauselform? Mir fällt das mit den Quantorenbeziehungen relativ schwer.
Resultierend hätte ich folgende Klauselmenge:
\(\{
\;\{ \neg Rxy , Pf(x,y) \}\;,
\;\{ \neg Rxy , Rxf(x,y) \}\;,
\;\{ \neg Rxy , Rf(x,y)y \}\;,
\;\{ Rxg(x) \}\;,
\;\{ \neg Rcg(c) , \neg Pc , \neg Pg(c) \}\;
\}\)
Zuletzt geändert von Domac am 17. Aug 2011 20:20, insgesamt 2-mal geändert.
Extend my dropbox space (here).
Thanks!

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von ez22 » 17. Aug 2011 19:57

wie geht man an solche beweise überhaupt dran? wie kann ich meine Wissenslücke beseitigen.

großen Dank!

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von Domac » 17. Aug 2011 20:00

ez22 hat geschrieben:wie geht man an solche beweise überhaupt dran? wie kann ich meine Wissenslücke beseitigen.

großen Dank!
Skript lesen und beten. Das mache ich im Moment auch. ;)
Wenn ich es verstanden habe kann ich es dir gerne nochmal erklären oder du liest einfach mit.
Gruß domac
Extend my dropbox space (here).
Thanks!

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von ez22 » 17. Aug 2011 20:15

oh ja.. das tue ich... ist bei mir so eine schleife, abbruchsbedienung ist der klausurtermin...

aber gibs Literatur dazu, außer des Skriptes?

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von Domac » 17. Aug 2011 20:47

*push*
Wenn ich das richtig verstanden habe:
a)
\(\varphi_1 = \forall x \forall y (Rxy \rightarrow (Pf(x,y) \wedge Rxf(x,y) \wedge Rf(x,y)y)\)
\(\varphi_2 = \forall x (Rxg(x))\)
\(\psi = Rcg(c) \wedge Pc \wedge Pg(c)\)

b)
\(\varphi_1 \wedge \varphi_2 \wedge \neg \psi \equiv
\forall x \forall y (Rxy \rightarrow (Pf(x,y) \wedge Rxf(x,y) \wedge Rf(x,y)y) \wedge
\forall x (Rxg(x)) \wedge
\neg (Rcg(c) \wedge Pc \wedge Pg(c))\)

\(\equiv (\neg (Rxy) \vee Pf(x,y) \wedge \neg (Rxy) \vee Rxf(x,y) \wedge \neg (Rxy) \vee Rf(x,y)y)) \wedge
Rxg(x) \wedge \neg (Rcg(c) \wedge Pc \wedge Pg(c))\)

Stimmt das so ungefähr? Wenn nein, wie genau verfahre ich bei SKNf -> Klauselform? Mir fällt das mit den Quantorenbeziehungen relativ schwer.
Resultierend hätte ich folgende Klauselmenge:
\(\{
\;\{ \neg Rxy , Pf(x,y) \}\;,
\;\{ \neg Rxy , Rxf(x,y) \}\;,
\;\{ \neg Rxy , Rf(x,y)y \}\;,
\;\{ Rxg(x) \}\;,
\;\{ \neg Rcg(c) , \neg Pc , \neg Pg(c) \}\;
\}\)
Extend my dropbox space (here).
Thanks!

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von ez22 » 17. Aug 2011 20:56

hab genau die gleiche ableitung

hast du dann Resolution darauf angewendet? also Aufgabe c)

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von ez22 » 17. Aug 2011 20:58

bzw auf phi1 und phi2 erfüllen psi

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von Domac » 17. Aug 2011 21:51

\(\varphi_1 \wedge \varphi_2 \models \psi \equiv \models (\varphi_1 \wedge \varphi_2 ) \rightarrow \psi \equiv \models (\neg \varphi_1 \vee \neg \varphi_2) \vee \psi\) ... also ...
\((\neg (\neg (Rxy) \vee Pf(x,y) \wedge \neg (Rxy) \vee Rxf(x,y) \wedge \neg (Rxy) \vee Rf(x,y)y)) \vee
\neg Rxg(x)) \vee \neg (Rcg(c) \wedge Pc \wedge Pg(c))\)

\(\equiv ((Rxy \wedge \neg Pf(x,y) \vee Rxy \wedge \neg Rxf(x,y) \vee Rxy \wedge \neg Rf(x,y)y)) \vee
\neg Rxg(x)) \vee \neg (Rcg(c) \wedge Pc \wedge Pg(c))\)


Resultierend hätte ich folgende Klauselmenge:
\(\{
\;\{ Rcc \}\;,
\;\{ \neg Pf(c,c), Rcc \}\;,
\;\{ \neg Rcf(c,c), Rcc \}\;,
\;\{ \neg Rf(c,c)c, \neg Rcg(c), \neg Pc, \neg Pg(c) \}\;
\}\)


Und dann überlege ich mir, dass all diese Formeln \(\models Rcc\) ... </latein>.
Weit komme ich damit nicht... :(
Gruß domac
Extend my dropbox space (here).
Thanks!

onbes
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 30. Jul 2011 18:43

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von onbes » 17. Aug 2011 23:03

BItte spammt meinen Thread, solange da es keine Antwort gibt, nicht mit einem anderen Thema zu :)

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von Domac » 18. Aug 2011 09:36

Servus onbes, ja klaro. ^^
3) a)
(i) Du hast hier völlig recht.
(ungültig)

(ii) Hier behaupte ich, dass das Ganze gültig ist, wenn man \((\neg L)\) und \((\neg R)\) anwendet und abschließend \((Ax)\). ;)
(gültig)

(iii)Sollte wohl auch gültig sein mit den Regeln: \((\neg R)\) und \((Ax)\).
(gültig)

Gruß domac

PS.: Hoffentlich irre ich mich nicht! ;) Werde damit nochmal einen Tutor ärgern... :P
Extend my dropbox space (here).
Thanks!

onbes
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 30. Jul 2011 18:43

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von onbes » 18. Aug 2011 11:24

Hey Domac,

deine Lösung wurde von einer höheren Instanz bestätigt. Jedoch muss man dafür a) ein Gegenbeispiel angeben. Wenn ich später darüber nachgedacht habe poste ich es.
Hm wüsste gerne meinen Denkfehler bei der b), falls jmd. drauf kommt.
Somit werden die spams, bezüglich der angehängten Prüfung, wieder für gültig erklärt. :)

Gruß onbes

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von Domac » 18. Aug 2011 11:45

Domac hat geschrieben:Servus onbes, ja klaro. ^^
(ii) Hier behaupte ich, dass das Ganze gültig ist, wenn man \((\neg L)\) und \((\neg R)\) anwendet und abschließend \((Ax)\). ;)
(gültig)
Schau hier bitte nochmal ins FO Skript auf Seite 30 mit dem Hintergedanken, dass man die Regeln dort auch vice versa anwenden kann und nicht nur in die dort genannte Richtung. Ist deine (i) nicht Gegenbeispiel genug? Man nimmt sich eine Interpretation her, welche in der Annahme der Allgemeingültigkeit der Prämisse eben diese mit Belegungen von \(I(\varphi)=0\) und \(I(\psi)=0\) erfüllt.

Wie siehts eigentlich mit meiner Klauselform aus? Habe ich das richtig verstanden, so wie es da steht?
Domac hat geschrieben: Resultierend hätte ich folgende Klauselmenge:
\(\{
\;\{ \neg Rxy , Pf(x,y) \}\;,
\;\{ \neg Rxy , Rxf(x,y) \}\;,
\;\{ \neg Rxy , Rf(x,y)y \}\;,
\;\{ Rxg(x) \}\;,
\;\{ \neg Rcg(c) , \neg Pc , \neg Pg(c) \}\;
\}\)
Gruß domac
Extend my dropbox space (here).
Thanks!

Antworten

Zurück zu „Archiv“