Seite 1 von 1

Übung 2.2c)

Verfasst: 25. Okt 2007 15:38
von Bappsack
Wunderschönen guten Donnerstag Spätnachmittag,

Ich hoffe ihr habt alle viel Spaß mit den Zugstreiks, da ich somit nicht nach Hause komme, habe ich mich der Übung verschrieben und bin über Probleme größeren Ausmaßes gestolpert:

Folgende Fragen zur 2. Aufgabe, Aufgabenteil c) :

1.)Man hatte uns mitgeteilt, dass wir uns am Script von Prof. Otto orientieren könnten, doch schnell wurde mir klar, dass die Folien, wie auch die Übung leider komplett anders definiert wurden; besonders was das Sequenzenkalkül angeht!

2.)In der Übung sollen wir beweisen, dass die gegebenen Regeln stimmen. Mit logischem denken habe ich es zu ein paar Ansätzen geschafft, doch als es an (v A) [für was steht das überhaupt?] kam stellte sich mir ein fundamentales Problem:
Nach der Definition auf der Folie steht das "Ableitbarkeitssymbol" ganz links von der Konklusion (was auch logisch ist und auch im Script von Prof. Otto so beschrieben ist). Doch wenn ich mich recht entsinne besteht die Regel aus:
"Konjunktionen |-- Disjunktionen"
Worauf ich hinaus möchte ist ersichtlich. Eine Regel bei der das Auflösen von einem "Oder" auf der rechten Seite steht, gibt es nicht in der Form.

Ich würde mich einfach freuen, wenn wir einheitliche Regeln verwenden würden und die Aufgaben "besser" formuliert werden würden. Auch bei Aufgabe 2.a) war mir einiges nicht klar, zB ob wir eine eigene Struktur definieren sollen oder nicht. Aber das sei mal dahingestellt, hab jetzt einfach eine definiert. Da ich als Bsc Inf FGI2 hatte is das Problem noch schaffbar, aber was ist mit den anderen ;)

Nehmt das bitte als produktive Kritik,
danke im Vorraus für Hillfe und Denkansätze!

Liebe Grüße
MoH

Verfasst: 25. Okt 2007 18:35
von Mspringer
Es ist schon die gleiche Definition nur ein wenig anders benannt. Regeln wie v L oder v R werden nur nicht genannt, weil wir sie hier nicht brauchen.

Verfasst: 25. Okt 2007 23:57
von Bappsack
Das hat aber die selbe Definition wie die Disjunktionselimination auf der linken Seite. Nur das sie "komisch"definiert sind, da man eine Disjunktion auf der Rechten Seite nicht auf dem Weg eliminieren darf!

Verfasst: 27. Okt 2007 23:25
von kaesebrot
Hallo,
mir fehlt ein Ansatz, wie ich an die Beweise herangehen soll. Hat jemand einen Tip für mich?

Verfasst: 29. Okt 2007 00:27
von MuldeR
Also, das ist wirklich alles total undefiert bei dieser Aufgabe! :x

Wenn ich beispielweise diese Formel hab:
Bild

Was soll das dann "oben" bei den Prämissen heißen ???

1. (Gamma |= a und b) und (Gamma |= c und b)
2. (Gamma |= a und b) oder (Gamma |= c und b)
3. (Gamma |= a oder b) und (Gamma |= c oder b)
4. (Gamma |= a oder b) oder (Gamma |= c oder b)


Hatte mir überlegt, dass es bei (VA) eigentlich nur Variante 2. sein kann:

(Gamma |= a und b) oder (Gamma |= c und b)
-------------------------------------------------------------------
Gamma |= (a oder c) und b


Okay, aber wenn man sich dann die (FU) Regel an sieht, passt das auch net.
Eigentlich wäre ja die Variante 3. am sinnvollsten und würde sich auch mit dem Otto Skript decken.
Aber denn macht die (VA) regel wiederum keinen Sinn...

:(

Verfasst: 29. Okt 2007 04:59
von Tillmann
Vorsicht! Der Sequenzenkalkül wird hier anders angefasst als bei Otto. Vom Prinzip her ist es aber das gleiche :twisted:
MuldeR hat geschrieben:Wenn ich beispielweise diese Formel hab:
Bild
Das ist eine Regel, keine Formel :shock: und sie bedeutet zunächst natürlich nur folgendes:

Wenn \(\Gamma \alpha \beta\) und \(\Gamma \gamma \beta\) ableitbar sind, dann ist auch \(\Gamma (\alpha \vee \gamma) \beta\) ableitbar. Folie 45 im Skript verrät uns auch, was die Ableitbarkeit einer Sequenz bedeuten soll:

\(\varphi_1 \varphi_2 \varphi_3 \varphi_4\) bedeutet \(\varphi_1 \wedge \varphi_2 \wedge \varphi_3 \,\Rightarrow\, \varphi_4\).
MuldeR hat geschrieben:Was soll das dann "oben" bei den Prämissen heißen ???

1. (Gamma |= a und b) und (Gamma |= c und b)
2. (Gamma |= a und b) oder (Gamma |= c und b)
3. (Gamma |= a oder b) und (Gamma |= c oder b)
4. (Gamma |= a oder b) oder (Gamma |= c oder b)
Nichts davon, denn das |= muß nicht einfach hinter das Gamma, sondern immer vor die letzte Formel in der Sequenz! Also:
  • (Gamma, a |= b) und (Gamma, c |= b)
Und die Konklusion bedeutet (Gamma, (a oder c) |= b). Das macht auch Sinn:

Wenn wir bereits wissen, daß b sowohl aus Gamma und a als auch aus Gamma und c folgt, dann ist es uns egal, ob wir nun a oder c vorliegen haben. Also folgt b auch aus Gamma und (a oder c).


Ich finde es meist einfacher, solche Regeln "von unten nach oben" zu lesen: Wenn ich (Gamma und (a oder c) => b) beweisen möchte, was muß ich dann beweisen? Da ich ja nicht weiß, ob nun a oder c gilt, muß ich für beide Varianten einen Beweis parat haben, ich muß also sowohl Gamma und a => b als auch Gamma und c => b beweisen. In dieser Richtung wendet ja auch ein Theorembeweiser die Regeln eines Sequenzenkalküls an: Das Beweisziel wird solange zerlegt, bis nichts mehr übrigbleibt.

Zum Korrektheitsbeweis muß man natürlich "von oben nach unten" vorgehen: Reichen die Informationen aus der Prämisse denn auch wirklich aus, damit die Konklusion korrekt ist? Aber bevor man mit dem Beweisen anfängt, muß man die Regel ja erstmal verstanden haben.

Verfasst: 29. Okt 2007 20:01
von MuldeR
Danke Tillmann :)

Deine Erklärung macht natürlich Sinn! Das Problem war vorallem, dass mir die Syntax nicht klar war. Leider war das aus dem FoC Skript nicht wirklich ersichtlich! Vorallem der Fall, wenn zwei Formeln neben dem Gamma stehen. Dass die eine der beiden Formeln dann quasi noch zu der Gamma-Menge hinzugefügt werden muss, auf die Idee bin ich nich gekommen. Wenn man schon eine andere Syntax als im Otto Skript wählt (yeah, hauptsache Verwirrung), dann hätte man es doch wenigstens etwas besser erklären können...

Hab den Beweis jetzt über Interpretationen versucht. Hoffe mal das geht in die richtige Richtung :wink:

Verfasst: 29. Okt 2007 20:33
von Red*Star
Hmja, ok... aber wie schreibt man das nun auf? Da Wahrheitstafeln bei der PL ausfallen und wir keine Regeln haben, die wir schon benutzen dürfen, bleibt doch nur Prosa übrig, oder?

Und das mit den Interpretationen ist mir dann doch irgendwie etwas zu low-level :D (nichts für ungut @ MuldeR). Ich meine, bei mindestens zwei von den Regeln "sieht man" ja, dass sie korrekt sind *grml*... Leider ist man laut Strafgesetzbuch §10011100 Absatz (Ant) ja erst als Professor berechtigt, Sätze mit dem Wort "Trivial." beweisen zu dürfen ;). [Abgesehen davon, dass ich es erst ab dem Moment trivial gefunden habe, als ich verstanden hab, was eigentlich in der Aufgabe verlangt war... was uns zu der Konklusion führt, dass mathematische Sätze (in Abhängigkeit von der Betrachtungszeit) entweder den Schwierigkeitsgrad "unendlich" oder den Schwierigkeitsgrad "sieht man" haben, aber das ist wieder was anderes.]

Verfasst: 29. Okt 2007 23:37
von E.d.u.
habt ihr die regel (VS) verstanden?
wieso soll aus \(\Gamma\alpha , \Gamma(\alpha oder \beta) \) folgen? oder müsste bei einer der regel oben \( \Gamma\beta \) stehen? Ich meine wo kommt \(\beta \) her?

Verfasst: 30. Okt 2007 12:00
von Alp.traum
Das bedeutet, dass du unabhängig von weiteren Formeln die Ableitbarkeit garantieren kannst wenn sie ODER-verknüpft sind. Also, wenn du weißt dass \(\Gamma\alpha\) ableitbar ist, dann ist auch \(\Gamma(\alpha oder \beta)\) ableitbar. Bei einer UND-Verknüpfung würde das nicht klappen da du die zweite Bedingung (\(\beta\)) zwingend überprüfen musst. Stimmt's so?

Verfasst: 30. Okt 2007 13:56
von MisterD123
die sache ist glaube ich, wenn a unter der voraussetzung wahr ist, ist a oder b natürlich auch wahr (und genauso b oder a, ist ja vertauschbar).

Verfasst: 30. Okt 2007 18:12
von Tillmann
E.d.u. hat geschrieben:wieso soll aus \(\Gamma\alpha , \Gamma(\alpha oder \beta)\) folgen?
Naja, das ist halt so... :D Setzen wir mal \(\Gamma\)= leere Liste. Dann steht da:

Wenn \(\alpha\) gilt, gilt auch \(\alpha \vee \beta\). Oder, rückwärts gelesen: Um \(\alpha \vee \beta\) zu beweisen, genügt es, \(\alpha\) zu zeigen. Das gilt genauso auch, wenn man noch eine \(\Gamma\)-Liste mit Hypothesen hinzufügt.

Verfasst: 31. Okt 2007 00:31
von MuldeR
E.d.u. hat geschrieben:habt ihr die regel (VS) verstanden?
wieso soll aus \(\Gamma\alpha , \Gamma(\alpha oder \beta)\) folgen? oder müsste bei einer der regel oben \(\Gamma\beta\) stehen? Ich meine wo kommt \(\beta\) her?
\(\Gamma\alpha\) besagt, dass jede Interpretation, die alle Formeln in Gamma wahr macht, auch das Alpha wahr macht. Das ist unsere Vorbedingung bzw. Vorraussetzung.

\(\Gamma(\alpha oder \beta)\) besagt nun, dass jede Interpretation, die alle Formeln in Gamma wahr macht, auch (Alpha oder Beta) wahr macht. Genau das wollen wir ableiten. Und das ist auch wieder eine gültige Formel, denn: Wenn eine Interpretation Gamma wahr macht, macht sie (laut Voraussetzung) auch Alpha wahr und damit natürlich auch (Alpha oder Beta). Es gilt immer (true oder x) = true, egal was x ist. Für Beta haben wir ja eh keine Vorbedingungen...

Verfasst: 31. Okt 2007 08:01
von Gnomix
Vielleicht liegt der Fehler auch dahingehend, dass einmal a|-b und einmal a|b (mit | = oder, - = not) erscheinen soll.