Übung 2.2c)

Bappsack
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 25. Okt 2007 15:16
Wohnort: Alsbach-Hähnlein

Übung 2.2c)

Beitrag 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

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Beitrag 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.

Bappsack
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 25. Okt 2007 15:16
Wohnort: Alsbach-Hähnlein

Beitrag 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!
Rächdschreipung ohne Gewehr!!!

Benutzeravatar
kaesebrot
Neuling
Neuling
Beiträge: 10
Registriert: 22. Okt 2007 22:59
Kontaktdaten:

Beitrag von kaesebrot »

Hallo,
mir fehlt ein Ansatz, wie ich an die Beweise herangehen soll. Hat jemand einen Tip für mich?
Joghurt schmeckt nach Joghurt

MuldeR
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 18. Okt 2005 16:14
Wohnort: (d)armstadt
Kontaktdaten:

Beitrag 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...

:(

Tillmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

Beitrag 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.

MuldeR
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 18. Okt 2005 16:14
Wohnort: (d)armstadt
Kontaktdaten:

Beitrag 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:

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag 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.]
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

Benutzeravatar
E.d.u.
Nerd
Nerd
Beiträge: 633
Registriert: 3. Feb 2004 17:01
Wohnort: Darmstadt
Kontaktdaten:

Beitrag 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?

Benutzeravatar
Alp.traum
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 3. Feb 2004 15:15
Wohnort: Darmstadt
Kontaktdaten:

Beitrag 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?

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Beitrag 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).

Tillmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

Beitrag 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.

MuldeR
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 18. Okt 2005 16:14
Wohnort: (d)armstadt
Kontaktdaten:

Beitrag 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...

Benutzeravatar
Gnomix
Computerversteher
Computerversteher
Beiträge: 306
Registriert: 31. Okt 2005 08:44

Beitrag von Gnomix »

Vielleicht liegt der Fehler auch dahingehend, dass einmal a|-b und einmal a|b (mit | = oder, - = not) erscheinen soll.

Antworten

Zurück zu „Archiv“