Prüfung Ws 07/08 Sequenzenregeln beweisen

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von onbes » 19. Aug 2011 13:21

Moin Moin,

ich habe vorhin es nochmal nachgerechnet und die gleiche Klauselmenge als Lösung rausbekommen. Hm ich finde schon, dass es als Gegenbeispiel reicht. Werde wenn ich später wieder zuhause bin mal überlegen und das Gegenbeispiel (falls ich eins finde) posten, mal schaun wer eher drauf kommt ;)

Habe noch eine Frage bezüglich deiner angegebenen Ableitungsregeln:

Bei ii) habe ich die Regeln angewendet ¬L und ¬R angewendet und dann habe ich wieder meine Konklusion der Ausgangsregel raus. Das würde ja dann heissen, dass die Konklusion aus der Prämisse der zu zeigenden Formel ii) folgt (?!). Aber ich verstehe nicht genau, wieso man an diesem Schritt noch Ax anwenden kann (bzw. habe ich es bisher richtig gemacht? (siehe unten))

Γ, ¬φ |- Δ,¬ψ
----------------(¬R)
Γ |- Δ, ¬φ,¬ψ
----------------(¬L)

Γ,¬ψ |- Δ, ¬φ
----------------
Γ,φ |- Δ, ψ


iii) kann ich die Anwendung der Regeln auch nicht nachvollziehen

Könntest du dies bezüglich noch ein paar Worte verlieren bitte? :)

Geschmeidigen Gruß

onbes 8)

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von Domac » 19. Aug 2011 14:29

Servus,
so wie du die b) aufgezeigt hast stimmt sie. Am Ende lässt sich deine Konklusion aus der Prämisse über die Sequenzregeln bilden und ist damit allgemeingültig. Also kannst du abschließend die (Ax) Regel darauf anwenden und das Ganze ist gültig in dem Sinne.
Zur c) werde ich heute abend ein paar Worte verlieren, bin gerade nicht in LaTeX-Stimmung. ^^ Danke dir bzgl. der Klauselform-geschichte.
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 » 19. Aug 2011 19:11

bei der Anwendung der -L und -R Regeln, fällt dann die Negation bei der Umstellung der Variablen auf die andere Seite nicht weg?
Das lese ich aus dem Skriptregeln auf der 30-ten Seite. So wäre die Prämisse (nach der Anwedung der beiden Regeln) äquivalent zu der Konklusion

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von Domac » 20. Aug 2011 01:30

So...also zur 3 a)

ii) \(\frac{\Gamma, \neg \psi \vdash \Delta, \neg \varphi}{\Gamma, \varphi \vdash \Delta, \psi}\)

\(\frac{\Gamma, \varphi \vdash \Delta, \psi}{\Gamma, \neg \psi, \varphi \vdash \Delta} (\neg L)\)

...und dann...

\(\frac{\Gamma, \neg \psi, \varphi \vdash \Delta}{\Gamma, \neg \psi \vdash \Delta, \neg \varphi} (\neg R)\)

...und dann...

\(\frac{\Gamma, \neg \psi \vdash \Delta, \neg \varphi}{}(Ax)\)

...fertig! Achja... ich kann hier die (Ax) Regel drauf werfen, weil ich meine Prämisse aus der Konklusion hergeleitet habe und das Teil somit allgemeingültig ist.

Bei der iii) verfährst du analog mit den von mir genannten Regeln.
Gruß domac
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 Sequenzenregeln beweisen

Beitrag von nine » 26. Aug 2011 13:50

Hallo :)

Der Weg bei der 3a) (ii) ist einleuchtend.
Aber wenn man bei der (iii) ebenfalls (¬R) drauf wirft, dann verschwindet zwar der Allquantor und taucht auf der anderen Seite als Existenzquantor wieder auf, allerdings muss dann doch ¬Phi hinter dem Existenzquantor auftauchen.

Denn schließlich ist:

nicht (für alle x gilt Phi) gleichbedeutend zu
es existiert ein x, so dass ¬Phi gilt und nicht unbedingt gleichbedeutend mit
es existiert ein x, so dass Phi gilt!

Oder?
Und so hast du es doch gemeint domac, oder?

Lg

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von bafnai » 26. Aug 2011 19:37

Hallo,
zur Aufgabe3 (a) (i)
Wahrscheinlich habe ich wieder einmal etwas falsch verstanden, aber so würde ich die Aufgabe lösen:

\(\underline {\Gamma , \neg \varphi \vdash \Delta , \neg \psi }\)
\(\Gamma , \varphi \vdash \Delta , \psi\)

Als Belegung wähle ich \(\Gamma\) wahr und \(\Delta , \varphi , \psi\) falsch.

Es würde also folgendermaßen aussehen:

\(\underline {1, \neg 0 \vdash 0, \neg 0}\)
\(1, 0 \vdash 0, 0\)

\(\underline {1, 1 \vdash 0, 1}\)
\(1, 0 \vdash 0, 0\)

\(\underline {1 \wedge 1 \vdash 0 \vee 1}\)
\(1 \wedge 0 \vdash 0 \vee 0\)

\(\underline {1 \vdash 1}\)
\(0 \vdash 0\)

Mit der Belegung wären also Prämisse und Konklusion beide allgemeingültig und die Sequenzenregel somit korrekt.


MfG bafnai

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von fscheepy » 27. Aug 2011 16:00

bafnai hat geschrieben:Hallo,
zur Aufgabe3 (a) (i)
Wahrscheinlich habe ich wieder einmal etwas falsch verstanden, aber so würde ich die Aufgabe lösen:

\(\underline {\Gamma , \neg \varphi \vdash \Delta , \neg \psi }\)
\(\Gamma , \varphi \vdash \Delta , \psi\)

Als Belegung wähle ich \(\Gamma\) wahr und \(\Delta , \varphi , \psi\) falsch.

Es würde also folgendermaßen aussehen:

\(\underline {1, \neg 0 \vdash 0, \neg 0}\)
\(1, 0 \vdash 0, 0\)

\(\underline {1, 1 \vdash 0, 1}\)
\(1, 0 \vdash 0, 0\)

\(\underline {1 \wedge 1 \vdash 0 \vee 1}\)
\(1 \wedge 0 \vdash 0 \vee 0\)

\(\underline {1 \vdash 1}\)
\(0 \vdash 0\)

Mit der Belegung wären also Prämisse und Konklusion beide allgemeingültig und die Sequenzenregel somit korrekt.


MfG bafnai
Ich denke dein Problem ist, dass du EINE Belegung gefunden hast, mit der die Regel korrekt ist. Sie muss aber immer korrekt sein.
Kann man da nicht argumentieren mit gamma = leer, delta = leer, phi = p und psi = ¬p? Dann wäre in der Prämisse die linke Seite immer 0, also ist die Prämisse allgemeingültig. In der Konklusion wäre aber die linke Seite 1 und die rechte Seite 0, somit nicht mehr allgemeingültig, also ist die Regel falsch...

/edit: eine weitere Frage noch: darf man im Sequenzenkalkül in jedem Schritt nur eine Regel anwenden? Wenn ja, hat man dann beispielsweise bei der 3b) nicht ziemlich viel Schreibarbeit? :shock:

Außerdem: ich gehe mal davon aus, dass man die Sequenz unten aufs Blatt schreibt und sich dann nach oben vorarbeited (also quasi jeweils von der Konklusion zur Prämisse geht, so haben wir es zumindest in der Übung immer gemacht). Kann man dann einen "Ast" (also im Falle, dass man die Sequenz aufteilt, wie beispielsweise bei der Regel (vL)) mit einem Axiom beenden, wenn auf der linken und rechten Seite der Konklusion die selbe Formel steht, selbst, wenn man den Rest der Formel noch nicht weiter aufgeteilt hat? Beispiel:

__________________ (Ax)
(Rcd v Pcd), Pdc |- Rxy, Pdc

Wäre das ein korrekter Schritt, um die Sequenzenherleitung an dieser Stelle abzuschließen oder müsste man das (Rcd v Pcd) auf der linken Seite vorher erst irgendwie herleiten?

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von Kineese » 27. Aug 2011 16:39

fscheepy hat geschrieben: Außerdem: ich gehe mal davon aus, dass man die Sequenz unten aufs Blatt schreibt und sich dann nach oben vorarbeited (also quasi jeweils von der Konklusion zur Prämisse geht, so haben wir es zumindest in der Übung immer gemacht). Kann man dann einen "Ast" (also im Falle, dass man die Sequenz aufteilt, wie beispielsweise bei der Regel (vL)) mit einem Axiom beenden, wenn auf der linken und rechten Seite der Konklusion die selbe Formel steht, selbst, wenn man den Rest der Formel noch nicht weiter aufgeteilt hat? Beispiel:

__________________ (Ax)
(Rcd v Pcd), Pdc |- Rxy, Pdc

Wäre das ein korrekter Schritt, um die Sequenzenherleitung an dieser Stelle abzuschließen oder müsste man das (Rcd v Pcd) auf der linken Seite vorher erst irgendwie herleiten?
Ja das ist möglich da das ja egal ist wie \(\Gamma\) aussieht, sofern \(\varphi\) auf beiden seiten ist.

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von fscheepy » 27. Aug 2011 17:10

Okay.
Nur, um es nochmal klarzustellen: Aufgaben wie die 2b und 2c können bei uns nicht drankommen? Also Klauselform und (Grundinstanzen-)Resolution in FO? Und was ist allgemein mit der Klauselform gemeint? Ist das die KNF?

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von Kineese » 27. Aug 2011 17:17

fscheepy hat geschrieben:Okay.
Nur, um es nochmal klarzustellen: Aufgaben wie die 2b und 2c können bei uns nicht drankommen? Also Klauselform und (Grundinstanzen-)Resolution in FO?
Klausuelform in FO ist das gleiche wie in AL denke ich mal; sprich \(K \equiv \{C_{1} ,C_{2} ,... ,C_{n}\} \equiv C_{1} \wedge ... \wedge C_{n}\) nur das bei FO halt noch der Allquantor dabei steht, oder irre ich mich da irgendwie?

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von fscheepy » 27. Aug 2011 17:43

Kineese hat geschrieben:
fscheepy hat geschrieben:Okay.
Nur, um es nochmal klarzustellen: Aufgaben wie die 2b und 2c können bei uns nicht drankommen? Also Klauselform und (Grundinstanzen-)Resolution in FO?
Klausuelform in FO ist das gleiche wie in AL denke ich mal; sprich \(K \equiv \{C_{1} ,C_{2} ,... ,C_{n}\} \equiv C_{1} \wedge ... \wedge C_{n}\) nur das bei FO halt noch der Allquantor dabei steht, oder irre ich mich da irgendwie?
Kann sein, keine Ahnung, hatten wir das denn bzw. kann es drankommen?

Ansonsten: irgendwie hänge ich gerade bei der 1b). Da komme ich für phi z.b. auf:
~( (~q v ~r) ^ (p v q v r) )
Ist das jetzt trotz der Negation am Anfang eine KNF/Klauselform? Ich wüsste nämlich nicht, wie ich da noch weitermachen soll...

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von eintopf » 28. Aug 2011 15:32

fscheepy hat geschrieben:
Kineese hat geschrieben: Ansonsten: irgendwie hänge ich gerade bei der 1b). Da komme ich für phi z.b. auf:
~( (~q v ~r) ^ (p v q v r) )
Ist das jetzt trotz der Negation am Anfang eine KNF/Klauselform? Ich wüsste nämlich nicht, wie ich da noch weitermachen soll...
EDIT:
Für Phi bin ich jetzt folgende Schritte gegangen
(q and r) or not(p or q or r)
= (q and r) or (not p and not q and not r)
= (q or not p) and (q or not r) and (r or not p) and (r or not q)
Zuletzt geändert von eintopf am 28. Aug 2011 16:37, insgesamt 1-mal geändert.

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von Kineese » 28. Aug 2011 16:34

eintopf hat geschrieben:
fscheepy hat geschrieben:
Kineese hat geschrieben: Ansonsten: irgendwie hänge ich gerade bei der 1b). Da komme ich für phi z.b. auf:
~( (~q v ~r) ^ (p v q v r) )
Ist das jetzt trotz der Negation am Anfang eine KNF/Klauselform? Ich wüsste nämlich nicht, wie ich da noch weitermachen soll...
EDIT:
Für Phi bin ich jetzt folgende Schritte gegangen
(q and r) or not(p or q or r)
= (q and r) or (not p and not q and not r)
= (q or not p) and (q or not r) and (r or not p) and (r or not q) (durch assoziativität)
Häh geht das? Sieht mir jetzt gerade auf anhieb etwas falsch aus^^

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

Re: Prüfung Ws 07/08 Sequenzenregeln beweisen

Beitrag von fscheepy » 28. Aug 2011 17:54

Kineese hat geschrieben:
eintopf hat geschrieben: EDIT:
Für Phi bin ich jetzt folgende Schritte gegangen
(q and r) or not(p or q or r)
= (q and r) or (not p and not q and not r)
= (q or not p) and (q or not r) and (r or not p) and (r or not q) (durch assoziativität)
Häh geht das? Sieht mir jetzt gerade auf anhieb etwas falsch aus^^
Hab auch schon überlegt, ob das geht, dachte auch das wäre falsch, aber die beiden Formeln scheinen die gleiche Wertetabelle zu haben. Ist das also das Mittel der Wahl hier?

Antworten

Zurück zu „Archiv“