Aussagenlogik: Variablen in Ausdrücken

[Oestinator]

Hi!
Ich habe hier in Aufgabenstellung in Logik, die mir einigermaßen Kopfzerbrechen bereitet:


Zeigen Sie durch einen induktiven Beweis für beliebige Ausdrücke H Є ausd:

In H kommen endlich viele Aussagenvariablen vor.

Anm.: ausd sei die Menge aller Ausdrücke.

Meine bisherige Überlegung dazu war, dass dass die Menge der Aussagenvariablen (kurz: AV) eine Teilmenge eines bel. Ausdrucks H darstellt. Dabei sei eine beliebige Aussagevariable p Є AV, sowie seine "Nachfolger" p*,p**,p***,...
Wir haben dabei in der Vorlesung vereinbart, dass man für p* auch p1, für p** auch p2 und für p**...*=pi schreiben kann und dass die Menge {p,*} eine Teilmenge der AV ist.

Dadurch kam ich zu dem Schluss, dass die Menge AV unendlich viele Aussagenvariablen enthält und da laut meiner Überlegung die Menge AV eine Teilmenge eines bel. Ausdrucks H ist, auch selbiger Ausdruck unendlich viele Aussagenvariablen enthalten kann.
Das steht jedoch im Widerspruch zur Annahme, die ich eigentlich ziegen soll.

Meine Frage ist von daher, wo genau jetzt der Fehler in meiner Überlegung liegt, oder ob meine Überlegung überhaupt in die richtige Richtung verläuft. Ich bin für jeden HInweis dankbar.

[Tyr]

Ich habe mein Logikbuch jetzt nicht extra rausgekramt um eine vollständige Lösung zu präsentieren, aber beim Durchlesen der Aufgabenstellung habe ich mir gedacht:
Ein Ausdruck ist doch immer endlich, (wenn ich mich nicht irre ist ein Wort über einem Alphabet endlich) also müssen auch die Aussagenvariablen endlich sein. Oder nicht?
Die Lösung des ganzen meiner Meinung nach ist dann, dass man für i = 1 erstmal alle möglichen Grundwörter durchgeht, die ein Ausdruck haben kann (das wären dann eine oder zwei Variablen) und dann darauf aufbauend für beliebig große (aber endliche) i, aus denen sich der Ausdruck zusammensetzt trotzdem höchstens eine bestimmte endliche Anzahl an AV hat.

Ist aber alles schon länger her bei mir. Wenn niemand sonst antwortet und eine detaillierte Lösung gewünscht ist, kann ich auch nochmal in meinen Aufzeichnungen nachschauen, ob ich die Aufgabe da vielleicht zu stehen habe.

[Oestinator]

Die Lösung des ganzen meiner Meinung nach ist dann, dass man für i = 1 erstmal alle möglichen Grundwörter durchgeht, die ein Ausdruck haben kann (das wären dann eine oder zwei Variablen) und dann darauf aufbauend für beliebig große (aber endliche) i, aus denen sich der Ausdruck zusammensetzt trotzdem höchstens eine bestimmte endliche Anzahl an AV hat.

Also meinst du damit, dass ich mir erst mal 2 Aussagenvariablen p und p1 her nehme, welche durch beliebige Aussageverknüpfungen (also "und", "oder", "nicht", etc...) einen beliebigen Ausdruck H bilden und diese Methode dann auf i Aussagenvariablen erweitere? Damit habe ich doch aber nicht sicher gestellt, dass die AV eine endlich Menge bildet, da ich ja mit {p,*} unendlich viele Elemente in AV bilden kann. Oder gehe ich einfach aufgrund der Beweisannahme davon aus, dass die AV endlich viele Elemente besitzt?


Wenn niemand sonst antwortet und eine detaillierte Lösung gewünscht ist, kann ich auch nochmal in meinen Aufzeichnungen nachschauen, ob ich die Aufgabe da vielleicht zu stehen habe.
Eine detaillierte Lösung wird nicht von Nöten sein, da mir eigentlich nur der richtige Denkanstoß fehlt, um den Beweis zu erbringen ;)

Aber danke schon mal für deinen Lösungsvorschlag (sofern ich ihn richtig verstanden habe ;))

[Tyr]

Wir brauchen nur nicht, und und oder, da die Implikation und die Äquivalenz aus diesen resultiert. Außerdem können wir zeigen, dass die Negation unseren Ausdruck nicht in der AV-Anzahl größer machen kann, da nur eine Variable durch eine Variable mit einem nicht ausgedrückt wird.

Wichtig sind also nur und und oder, die beide vom Aufbau her gleich sind und zwar wird eine Variable (damit meine ich nicht eine AV sondern nur eine Stelle im Ausdruck, welcher eine AV oder eine weiteren Teilausdruck beinhalten kann, mir fällt grade das richtige Wort nicht ein) durch einen Ausdruck mit zwei Variablen, die mit einem und/oder verbunden sind ersetzt.

Die Induktion aufbauend auf i = 1 mit (p1 und p2) bzw (p1 oder p2) zeigt dann, das pro Induktionstiefe (i steht für die Teilausdrücke aus denen der Ausdruck aufgebaut ist) der Ausdruck um Maximal 1 AV erweitert werden kann.

Die Tiefe i des Ausdrucks ist endlich und die Anzahl der AV damit auch, denn diese ist dann i+1.

[Oestinator]

Alles klar, jetzt habe ich es verstanden, danke :)

[Stefan]

Wir brauchen nur nicht, und und oder, da die Implikation und die Äquivalenz aus diesen resultiert.
Sorry, aber so einfach sollte und darf man es sich nicht machen: Das Ganze ist eine formale Sprache, in der die Zeichenketten und ihre einzelnen Bestandteile grundsätzlich einmal gar keine Interpretation haben, außer eben den rein syntaktischen Begriffen wie eben "Variabel" oder weiterführend "Formel". Ob bestimmte Ausdrücke unter klassischer Interpretation 'gleichwertig' sind ist wurscht, die Sprache könnte ja auch das Grundgerüst für eine schwächere Logik, wie der intuitionistischen oder der Minimallogik sein, in denen z.B. die Gleichwertigkeit von (A → B) und (¬A ∨ B) nicht gilt, oder irgendeiner obskuren, eventuell sogar widersprüchlichen Logik sein. Der Sachverhalt dass ein Ausdruck der Sprache nur endlich viele Variabeln enthält besteht trotzdem, nur müssen wir auch → und ≡ in unsere Betrachtungen miteinbeziehen falls sie in gewöhnlicher Weise Teil der Sprache sind.

[Tyr]

Ja, damit hast du natürlich recht. Da wir nicht auf die Funktion der Operationen achten, sondern nur auf den Aufbau der Aussagen, können wir dann allgemein die 4 Operationen für die Induktion zu dem Fall (A op B) zuordnen während der andere Fall dann neg(A) ist.

Ich habe auch anderen (verallgemeinerten) Quatsch da oben in meiner Ausführung geschrieben. Oestinator sollte das dann bitte ausführlicher und verbessert niederschreiben, das war bloß ein Gedankenanstoß von mir, den ich schnell zusammengetippt habe. ;)

[Kadaj]

Ich hätte da auch eine (simple) Frage zur Aussagenlogik.

Beispiel:
r=1
p=1
q=0

Ich hab jetzt am Ende einer etwas längeren Gleichung dann dastehen:
q=>r
sprich:
0=>1
= 1

Im Grunde sagt das ja aus, dass aus einer falschen Aussage eine wahre folgt. Aber warum kommt dann als Ergebnis 1 raus? Warum ist die Aussage wahr? Wie kann aus etwas falschem etwas wahres werden?

[R.F.]

Es steht doch schon in der Definition einer Implikation, dass aus was Falschem etwas Wahres gefolgert werden kann. So funktioniert doch auch der Beweis mittels Widerspruch. Du nimmst etwas an, was nicht gelten kann, führst es auf besagten Widerspruch und kannst daraus dann das Wahre folgern.

[gas]

^ Was er sagt. Die Implikation ist formal über eine Wahrheitstabelle definiert (siehe z.B. http://de.wikipedia.org/wiki/Implikation#Wahrheitsfunktionale_Implikation). So funktioniert die Implikation, und aus formaler Sicht ist damit alles gesagt. Deine Frage ist vermutlich, warum man diese Definition gewählt hat.

Der Grund dafür ist wohl, dass man (im Kalkül des natürlichen Schließens) aus einer falschen Annahme eine beliebige Aussage folgern kann (ex falso quodlibet (http://en.wikipedia.org/wiki/Ex_falso_quodlibet)).

[Kadaj]

Der Grund dafür ist wohl, dass man (im Kalkül des natürlichen Schließens) aus einer falschen Annahme eine beliebige Aussage folgern kann (ex falso quodlibet (http://en.wikipedia.org/wiki/Ex_falso_quodlibet)).

Ah ja, so hatte unser Prof das mal in der Vorlesung erklärt. Da hatte ich das mal kurzzeitig nachvollziehen können, inzwischen wars aber wieder weg... ^^

Danke jedenfalls für die Antworten.