Formales System (Logik)
Formale Systeme werden in der Logik zur exakten Untersuchung der Bedingungen für das Folgern einer Aussage eingesetzt. Die Formalisierung der logischen Schlussregeln hatte ihren Ausgangspunkt gegen Ende des 19. Jahrhunderts durch den Logiker, Mathematiker und Philosophen Gottlob Frege. Die Logik erhielt dadurch eine der mathematischen Formelsprache entsprechende Form, in der exakte, mathematisch strenge Ableitungen und Beweise möglich werden. Freges Ansatz wurde dann durch Mathematiker wie David Hilbert und Bertrand Russell erweitert.
Table of contents |
2 Symbolische Logik 3 Literatur 4 Weblinks 5 Anhang: Lösung des MU-Rätsels |
Ein berühmtes Beispiel für ein formales System ist das MU Rätsel aus dem Buch Gödel, Escher, Bach, in dem die Beweisbarkeit eines formalen "Satzes" und der Bezug formaler Systeme zu den Axiomensystemen der Mathematik deutlich wird:
Douglas R. Hofstadter erfand dieses System, um die Anwendung von formalen Systemen im Bereich der Logik und Mathematik zu veranschaulichen. Es ist ein sehr einfaches System, das nur drei Symbole und vier Regeln enthält. Schon die Grundrechenarten der Arithmetik, ebenfalls ein formales System, sind wesentlich komplexer. Da das System keine Entsprechungen für reale Dinge hat, im Gegensatz z.B. zu Zahlwörtern, wird der formale Charakter besonders deutlich. Im formalen System spielt ja genau die Bedeutung der Symbole keine Rolle mehr.
Das System besteht aus den drei Symbolen M, I und U. Symbolketten können durch die folgenden vier Regeln in andere Ketten verwandelt werden:
Die Regeln dürfen in beliebiger Reihenfolge auf eine Symbolkette angewendet werden, auch mehrmals hintereinander.
Die Lösung des Rätsels steht am Schluss des Artikels
Im formalen System lassen sich Axiome durch Symbolfolgen darstellen. Im MU-Rätsel ist MI das einzige Axiom. Dieses ist also nach Definition wahr. Mit Hilfe der Umwandlungsregeln lassen sich aus den Axiomen andere Symbolfolgen erzeugen. Der Wahrheitswert ändert sich bei Anwendung dieser Regeln nicht, daher gelten die abgeleiteten Symbolketten ebenfalls als wahr.
Eine Symbolkette wird als mathematischer oder logischer Satz bezeichnet. Die Axiom-Symbolketten sind daher in jedem Fall auch Sätze. Auch die durch Umwandlung erzeugten Symbolketten sind Sätze, genauso wie jede beliebige Symbolfolge.
Kennt man eine Folge der Anwendung der Regeln, die einen Satz aus den Axiom-Symbolketten erzeugt, so ist der Satz wahr. Die Folge ist der Beweis dieses Satzes. Sätze, für die prinzipiell ein Beweis exisitiert, nennt man beweisbar. Da sich normalerweise nicht jede Symbolkette erzeugen läßt, gibt es beweisbare und nicht beweisbare Sätze.
Im formalen System ist ein Satz beweisbar, wenn es prinzipiell möglich ist, ihn durch Umwandlung aus den Axiomen zu erzeugen. Das MU-Rätsel fragt nach der Beweisbarkeit des "Satzes" MU. Hier darf man nicht Beweis und Beweisbarkeit verwechseln. Kennt man einen Beweis, so ist damit die Beweisbarkeit nachgewiesen. Es ist jedoch nicht immer nötig oder möglich, einen Beweis zu finden. Trotzdem können unter Umständen Aussagen zur Beweisbarkeit oder Nichtbeweisbarkeit gemacht werden, obwohl man den Beweis selbst nicht kennt.
Erstaunlicherweise kann man jedoch nicht jedes System so erweitern, dass alle Sätze auch beweis- oder widerlegbar sind. In manchen Systemen bleiben stets unentscheidbare Sätze übrig. Dies hat Kurt Gödel 1930 mit seinem Unvollständigkeitssatz zweifelsfrei nachgewiesen.Das MU-Rätsel
Das formale M,I,U-System
x in Regel2 steht für eine beliebige Symbolkette. xx bedeutet die Verdoppelung der Kette, diese wird also zweimal hinterander gesetzt.Das Rätsel
Die Aufgabe kann nicht durch einfaches Erzeugen aller möglichen Symbolketten (Brute Force-Suche) gelöst werden.Axiomensysteme als formale Systeme
Axiome sind Sätze, die von vornherein als wahr vorausgesetzt werden. In Axiomensystemen existieren meist nur einige wenige Axiome. Die euklidische Geometrie hat z.B. nur fünf Axiome.
Das M,I,U-System als Axiomensystem
Element
Symbole
M, I und U
Satz
Jede beliebige Folge der Symbole M I U
Axiom
MI
Schlussfolgerungs-Regeln
Regel1 bis Regel4 (siehe oben)
Beweis eines Satzes
Reihenfolge der Anwendung von Regel1 bis Regel4 auf das Axiom MI, bis der zu beweisende Satz entsteht.
Beweisbarkeit eines Satzes
Möglichkeit der Existenz eines Beweises
MU-Rätsel
Beweisbarkeit des Satzes MU
Widerspruchsfreiheit von Axiomensystemen
Verwendet man ein Symbol zum Ausdrücken der Verneinung (z. B. ) und definiert, dass nicht wahr gleich falsch ist, so ist ein System widerspruchsfrei, wenn nicht gleichzeitig ein Satz und seine Verneinung bewiesen werden kann.Vervollständigung von Axiomensystemen
Beweisbare Sätze sind nach Definition stets wahr. In den meisten formalen Systemen können Sätze formuliert werden, die weder beweis- noch widerlegbar sind. Widerlegung ist dabei der Beweis der Verneinung. Man kann ein formales System dann erweiteren, indem man für einen solchen Satz einfach definiert, ob er wahr oder falsch ist. Im erweiterten System existiert dann ein Beweis oder eine Widerlegung, nämlich einfach die hinzugefügte Definition.
Symbol | Beschreibung |
---|---|
A B C ... | Aussage. Eine Aussage wird durch einen Grossbuchstaben repräsentiert. |
nicht. Verneinung einer Aussage ist genau dann wahr, wenn A falsch ist, und umgekehrt. | |
und. Die Gesamtaussage ist genau dann wahr, wenn sowohl A als auch B wahr sind. | |
oder. Die Gesamtaussage ist genau dann wahr, wenn entweder A oder B oder beide wahr sind. | |
ist gleichwertig zu. Die Gesamtaussage ist wahr, wenn A und B beide wahr oder beide falsch sind. | |
aus folgt. Die Folgerung ist falsch, wenn A wahr, aber B dennoch falsch ist. In allen anderen Fällen ist wahr. | |
( ) | Klammern. Klammern dienen dazu, die Ausführung einer Operation vor einer anderen zu erzwingen, wenn Unklarheiten bestehen. |
Symbol | Beschreibung |
---|---|
a b c ... | Symbolfolge. Ein Kleinbuchstabe kann durch eine Symbolfolge ersetzt werden. Gleiche Kleinbuchstaben in einer Folge müssen durch gleiche Symbolfolgen ersetzt werden. |
kann ersetzt werden durch. Die Symbolfolge auf der linken Seite kann durch die Folge auf der rechten Seite ersetzt werden, ohne den Wahrheitsgehalt zu ändern. Ebenso kann die rechte Folge durch die linke ersetzt werden. | |
wahr falsch | Symbole für eindeutig wahre und falsche Aussagen |
Eine Umwandlungsregel könnte dann so aussehen:
Schlussregel1: | . |
Dies bedeutet, dass man auf der linken Seite jedes Satzes entfernen oder hinzufügen darf. Umgangssprachlich entspricht dies der doppelten Verneinung:
Schlussregel1: Die Verneinung der Verneinung einer Aussage ist die Aussage selbst
Weitere Umwandlungsregeln sind z.B.
Schlussregel2: | |
Schlussregel3: | |
Schlussregel4: | |
Schlussregel5: | |
Schlussregel6: | |
Schlussregel7: | |
Trotzdem wurden die Regeln "sinnvoll" gewählt. Schlussregel3 bedeutet, dass eine wahre Aussage oder eine beliebige Aussage als Gesamtaussage immer wahr ist. Dagegen bedeutet die kompliziertere Schlussregel5 (Folgerung) übersetzt etwa:
Schlussregel5: aus a folgt b kann ersetzt werden durch die Aussage "Verneinung von Aussage a oder Aussage b".
Die Folgerung ist genau dann falsch, wenn a wahr, aber b dennoch falsch ist. Umgekehrt ist sie also wahr, wenn a falsch oder wenn b wahr ist. Dies entspricht formal (lies: nicht a oder b).
Der klassische Satz ex falsum quod libet (aus Falschem folgt Beliebiges) kann formal dargestellt und bewiesen werden. In unserem formalen System lautet er:
Zum Beweis wenden wir die Umformungsregel für die Folgerung an:
Beweise
Ein Beweis besteht aus einer Behauptung und einer Schlussfolgerung. Im formalen System wird eine Behauptung b als Symbolfolge dargestellt, ebenso die Schlussfolgerung s. Der Beweis wird geführt, indem der Satz "aus der Behauptung folgt die Schlussfolgerung" in umgewandelt wird:
Beweis des Satzes: Aus Falschem folgt Beliebiges
Beweis:
Nicht falsch ist aber wahr:
Schliesslich ist eine wahre Aussage oder Beliebiges immer war.
Der Satz ist damit formal bewiesen. Der Beweis könnte durch ein Computerprogramm erfolgen, das nur die Symbole kennt und die Schlussregeln anwendet.Literatur
Weblinks
Siehe auch: Formales System (Mathematik)
Anhang: Lösung des MU-Rätsels
Die Symbolkette MU kann durch Anwendung der Regeln aus dem ersten Abschnitt des Artikels nicht aus der Kette MI erzeugt werden.Verkürzung und Verlängerung
Der Beweis kann aber nicht innerhalb des M,I,U-Systems geführt werden. Regel1 und Regel2 verlängern eine Kette, Regel3 und Regel4 verkürzen sie dagegen. Eine sehr lange Folge könnte also unter Umständen doch MU ergeben.Eigenschaften beweisbarer Sätze
Zur Lösung kann man die Eigenschaften der beweisbaren Sätze untersuchen. Eine solche Eigenschaft ist die Anzahl der I-Symbole in einer Kette, die ab jetzt I-Wert genannt werden soll. Der I-Wert des Axioms MI ist eins, da I einmal vorkommt. Der I-Wert des Satzes MU ist dagegen null.Eigenschaften des I-Werts
Die Umwandlungsregeln verändern den I-Wert wie folgt:
Den I-Wert kann man aus der Anzahl der Anwendungen von Regel2 und Regel3 berechnen. Der I-Wert des Axioms ist wie gesagt eins. Wendet man Regel2 an, so erhält man einen I-Wert von 2. Wendet man sie nochmals an, so ergibt sich 4,8,16, usw. n-malige Anwendung ergibt also einen I-Wert von . Jede Anwendung von Regel3 verringert den I-Wert eines Satzes um drei, m-malige Anwendung also um . Der I-Wert ist alsoBeweis
Da der zu beweisende Satz MU die I-Zahl null hat, muss die Gleichung
gelöst werden, wobei n und m ganze Zahlen sein müssen. Der Term auf der linken Seite ergibt nur die Zahlen 1, 2, 4, 5, 7, 8, 10, 11, usw. aber niemals 0, 3, 6, usw. Ein I-Wert von Null ist also nicht möglich. Damit ist der Satz MU wie jeder Satz mit dem I-Wert Null nicht beweisbar, die Lösung des Rätsels lautet