Hi,
ich hab die ableitung in einem kalkül so verstanden, dass jede formel, die element einer folge von ableitungen ist, entweder element der menge M (aus der abgeleitet wird), oder ein axiom mit einer substitution oder durch anwenden einer inferenzregel entstanden sein. mit anderen worten: nur die axiome dürfen substituiert werden, aber nicht die formeln der menge M oder die formel, die man abgeleitet hat. stimmt das (dass man nur axiome substituieren darf)???
in der musterlösung von aufgabenblatt 6 (http://www.informatik.uni-hamburg.de/TGI/lehre/vl/WS0304/F1/f1loes6.pdf) werden nämlich auch abgeleitete formeln substituiert.

stimmt das (dass man nur axiome substituieren darf)???
in der musterlösung von aufgabenblatt 6 (http://www.informatik.uni-hamburg.de/TGI/lehre/vl/WS0304/F1/f1loes6.pdf) werden nämlich auch abgeleitete formeln substituiert.

Ja im Allgemeinen stimmt das schon. Beim Aufgabenblatt 6 ist es alles ein "Sonderfall" da wir hier wie auch in der Aufgabenstellung (siehe Aufgabe 2) zu lesen ja aus der leeren Menge ableiten! Also leiten wir quasi nur aus einer Menge von Axiomen ab. Da wir ja in Blatt 6 bewiesen haben, dass wenn A aus M ableitbar ist, dann folgt auch A aus M. Also muss wenn M nur aus Tautologien besteht auch A eine Tautologie sein. In diesen Fall leiten wir ja nur aus den Axiomen ab, also ist alles was wir ableiten wieder zwangläufig eine Tautologie und kann nur deshalb wie ein Axiom verwendet werden.

alles klar, danke.
dürfte man dann auch irgendeine beliebige tautologie als axiom benutzen?

dürfte man dann auch irgendeine beliebige tautologie als axiom benutzen?

Ich denke das kommt ganz auf die Aufgabenstellung an. Will man nur innerhalb eines bestimmten Kalküls eine aussagenlogische Ableitung machen, also z.B. zeigen das G in C aus M ableitbar ist, so darf man natürlich nicht einfach Tautologien als Axiome verwenden, die nicht in C sind!

jo, das leuchtet ein. also kann man wohl bei aufgabenblatt 6 die axionemmenge erweitern, weil da kein bestimmtes kalkül angegeben ist….!

also kann man wohl bei aufgabenblatt 6 die axionemmenge erweitern, weil da kein bestimmtes kalkül angegeben ist….!

Ja genauso hab ich mir das auch gedacht.

Ah, fein, ich wollte gestern schon was schreiben, aber irgendwie ging der "Speichern"-Button nicht mehr darum musste ich eben beim Browser rummurksen, jetzt geht's wieder [img]http://www.fb18.de/gfx/22.gif[/img]
Dann mal los:


Nein! {Bezieht sich auf die ursprüngliche Frage, ob man einfach eine beliebige Tautologie zu den Axiomen nehmen darf}

Du hast ein Kalkül gegeben. Dies besteht aus einer Menge von Axiomen, einer Menge von Inferenzregeln (z.B. Modus Ponens) und eine Sprache (gegeben durch ein Alphabet und Regeln zur Bildung von Formeln (=> Syntax!)). {vgl. 6-16}

Wenn du nun eine Folge von Formeln F_1, … , F_n hast, dann ist diese eine aussagenlogische Ableitung von G aus einer Menge M gdw. F_n = G und für jedes F_i (1 <= i <= n) mindestens eins der folgenden drei gilt:

i) F_i ist aus M,
ii) F_i ist durch Substitution in einem der Axiome hervorgegangen,
iii) F_i ist aus den vorherigen F_j (1 <= j < i) durch Anwendung einer der Inferenzregeln hervorgegangen.

{vgl. 6-17}


In der Aufgabe war nun M die leere Menge, d.h. obige Bedingung (i) entfällt. Zudem galt noch (was nicht in den Folien steht), dass jede abgeleitete Formel nachfolgend sozusagen als Axiom gilt, d.h., dass auch auf sie obiges (ii) anwendbar ist.

Mittels obiger Ableitung versucht man rein aus den syntaktischen Eigenschaften von Formeln auf Eigenschaften zu schliessen.

Du kannst jetzt nicht einfach eine beliebige Tautologie als Axiom benutzen, denn: Wo kommt die so plötzlich her? Warum sollte das eine Tautologie sein? (Wenn du jetzt Wahrheitstafeln sagst, dann bist du bereits in der Semantik mit der wir ja gerade jetzt nichts machen wollen, wie gesagt: Über den Syntax wollen wir argumentieren.)

(Wenn du dir selbst ein Kalkül bastelst, dann kannst du das natürlich machen – aber dann kannst du auch jede andere Formel als Axiom benutzen [img]http://www.fb18.de/gfx/25.gif[/img])

Hoff' es hilft.

Cheers,
Frank

P.S. Für Interessierte: "Mathematical Logic for Computer Science" von M. Ben-Ari, Springer Verlag. In der Bibliothek vorhanden, aber für die Prüfungsvorbereitung besser Schöning benutzen (einfacher, gleicher Formalismus wie im Skript/in der Vorlesung). – Aber wie gesagt: Für Interessierte bestimmt spannend [img]http://www.fb18.de/gfx/28.gif[/img]

hm, eine sache ist mir noch nicht ganz klar:
dass man jede abgeleitete formel sozusagen als axiom benutzen kann, ging das nur bei der aufgabe (blatt 6), weil da kein bestimmtes kalkül angegeben war oder ist das immer so, wenn ich aus der leeren menge ableite?

Eine abgeleitete Formel als Axiom zu benutzen (also auf sie eine Substitution anzuwenden) ist durch die Definition im Skript nicht gedeckt! {6-17}
Herr Kudlek hat es aber evtl. in der Vorlesung erwähnt. (Siehe auch obigen Literaturhinweis.)

Für den Aufgabenzettel war es ausdrücklich erlaubt und es war auch ein Kalkül gegeben (bestehend aus der Logik-Sprache der Aussagenlogik, den gegebenen Axiomen und dem Modus Ponens als einzige Inferenzregel), beides wurde aber nur mündlich in den Übungsgruppen mitgeteilt.

Vgl. auch die Musterlösung - insb. 2c, wo 2a benutzt wird.

Cheers,
Frank