Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenFreitag, 31. Oktober 2014 

Formales System (Logik)


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Formale Systeme werden in der Logik zur exakten Untersuchung der Bedingungen für Folgern einer Aussage eingesetzt. Die Formalisierung der logischen Schlussregeln ihren Ausgangspunkt gegen Ende des 19. Jahrhunderts durch den Logiker Mathematiker und Philosophen Gottlob Frege . Die Logik erhielt dadurch eine der Formelsprache entsprechende Form in der exakte mathematisch Ableitungen und Beweise möglich werden. Freges Ansatz dann durch Mathematiker wie David Hilbert und Bertrand Russell erweitert.

Inhaltsverzeichnis

Das MU-Rätsel

Ein berühmtes Beispiel für ein formales ist das MU Rätsel aus dem Buch Gödel Escher Bach in dem die Beweisbarkeit eines formalen und der Bezug formaler Systeme zu den der Mathematik deutlich wird:

Das formale M I U-System

Douglas R. Hofstadter erfand dieses System um die Anwendung formalen Systemen im Bereich der Logik und zu veranschaulichen. Es ist ein sehr einfaches das nur drei Symbole und vier Regeln Schon die Grundrechenarten der Arithmetik ebenfalls ein System sind wesentlich komplexer. Da das System Entsprechungen für reale Dinge hat im Gegensatz zu Zahlwörtern wird der formale Charakter besonders Im formalen System spielt ja genau die der Symbole keine Rolle mehr.

Das System besteht aus den drei M I und U . Symbolketten können durch die folgenden vier in andere Ketten verwandelt werden:

Regel1: Wenn das letzte Symbol I ist kann U angefügt werden (aus MI wird MIU )
Regel2: Aus M x kann M xx erzeugt werden (aus MIU wird MIUIU )
Regel3: III kann durch U ersetzt werden (aus MUIIII wird MUIU )
Regel4: UU kann gestrichen werden (aus MUUUI wird MUI )

x in Regel2 steht für eine beliebige Symbolkette. xx bedeutet die Verdoppelung der Kette diese also zweimal hinterander gesetzt.

Die Regeln dürfen in beliebiger Reihenfolge eine Symbolkette angewendet werden auch mehrmals hintereinander.

  1. MI
  2. MII (Regel2)
  3. MIIII (Regel2)
  4. MUI (Regel3)
  5. MUIU (Regel1)
  6. MUIUUIU (Regel2)
  7. MUIIU (Regel4)

Das Rätsel

  1. Vorgegeben ist die Symbolkette MI
  2. Gibt es eine Folge der Anwendung der so dass die Symbolkette MU aus MI entsteht?

Die Aufgabe kann nicht durch einfaches aller möglichen Symbolketten ( Brute Force -Suche) gelöst werden.

Die Lösung des Rätsels steht am Schluss Artikels

Axiomensysteme als formale Systeme

Axiome sind Sätze die von vornherein wahr vorausgesetzt werden. In Axiomensystemen existieren meist nur wenige Axiome. Die euklidische Geometrie hat z.B. nur fünf Axiome.

Im formalen System lassen sich Axiome Symbolfolgen darstellen. Im MU-Rätsel ist MI das einzige Axiom. Dieses ist also Definition wahr . Mit Hilfe der Umwandlungsregeln lassen sich den Axiomen andere Symbolfolgen erzeugen. Der Wahrheitswert sich bei Anwendung dieser Regeln nicht daher die abgeleiteten Symbolketten ebenfalls als wahr .

Eine Symbolkette wird als mathematischer oder Satz bezeichnet. Die Axiom-Symbolketten sind daher in Fall auch Sätze. Auch die durch Umwandlung Symbolketten sind Sätze genauso wie jede beliebige

Kennt man eine Folge der Anwendung Regeln die einen Satz aus den Axiom-Symbolketten so ist der Satz wahr . Die Folge ist der Beweis dieses Satzes. Sätze für die prinzipiell Beweis exisitiert nennt man beweisbar. Da sich nicht jede Symbolkette erzeugen läßt gibt es und nicht beweisbare Sätze.

Im formalen System ist ein Satz wenn es prinzipiell möglich ist ihn durch aus den Axiomen zu erzeugen. Das MU-Rätsel nach der Beweisbarkeit des "Satzes" MU . Hier darf man nicht Beweis und verwechseln. Kennt man einen Beweis so ist die Beweisbarkeit nachgewiesen. Es ist jedoch nicht nötig oder möglich einen Beweis zu finden. können unter Umständen Aussagen zur Beweisbarkeit oder gemacht werden obwohl man den Beweis selbst kennt.

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
Das M I U-System als Axiomensystem

Widerspruchsfreiheit von Axiomensystemen

Verwendet man ein Symbol zum Ausdrücken Verneinung (z. B. <math>\neg</math>) und definiert dass wahr gleich falsch ist so ist ein widerspruchsfrei wenn nicht gleichzeitig ein Satz und Verneinung bewiesen werden kann.

Vervollständigung von Axiomensystemen

Beweisbare Sätze sind nach Defintion stets In den meisten formalen Systemen können Sätze werden die weder beweis- noch widerlegbar sind. ist dabei der Beweis der Verneinung. Man ein formales System dann erweiteren indem man einen solchen Satz einfach definiert ob er oder falsch ist. Im erweiterten System existiert ein Beweis oder eine Widerlegung nämlich einfach hinzugefügte Definition.

Erstaunlicherweise kann man jedoch nicht jedes so erweitern dass alle Sätze auch beweis- widerlegbar sind. In manchen Systemen bleiben stets Sätze übrig. Dies hat Kurt Gödel 1930 mit seinem Unvollständigkeitssatz zweifelsfrei nachgewiesen.

Symbolische Logik

Logiksysteme wie die Aussagenlogik können durch formales System definiert werden. Dazu könnte man Wörter wie und oder nicht verwenden was die Verständlichkeit erhöhen würde. haben solche Wörter stets Nebenbedeutungen die den Charakter der Aussagen nicht widerspiegeln. Daher werden Symbole eingeführt deren Interpretation keinen Freiraum mehr

Symbole zur Darstellung der Aussagenlogik

Die folgende Tabelle gibt Symbole wieder zu einer Definition der Aussagenlogik dienen können:
Symbol Beschreibung
A B C ... Aussage . Eine Aussage wird durch einen Grossbuchstaben
<math>\neg</math> nicht . Verneinung einer Aussage <math>\neg A</math> ist dann wahr wenn A falsch ist und umgekehrt.
<math>\wedge</math> und . Die Gesamtaussage <math>A \wedge B</math> ist dann wahr wenn sowohl A als auch B wahr sind.
<math>\vee</math> oder . Die Gesamtaussage <math>A \vee B</math> ist dann wahr wenn entweder A oder B oder beide wahr sind.
<math>\leftrightarrow</math> ist gleichwertig zu . Die Gesamtaussage <math>\leftrightarrow</math> ist wahr wenn A und B beide wahr oder beide falsch sind.
<math>\rightarrow</math> aus folgt . Die Folgerung <math>A \rightarrow B</math> ist wenn A wahr aber B dennoch falsch ist. In allen anderen ist <math>A \rightarrow B</math> wahr.
( ) Klammern . Klammern dienen dazu die Ausführung einer vor einer anderen zu erzwingen wenn Unklarheiten

Symbolfolgen sind Sätze

In formalen Systemen entspricht ein Satz einer Folge von Symbolen also einer Symbolkette

Satz:
<math>A \wedge B \leftrightarrow \neg ((\neg A) (\neg B))</math>

Übersetzt heißt dies: Die Aussage "A B" hat denselben Wahrheitswert wie die Verneinung Aussage "nicht A oder nicht B".

Ein Satz kann wahr oder falsch

Umwandlungsregeln in einer Logik

Symbolfolgen kann man in formalen Systemen Regeln in andere Symbolfolgen umformen. Zur Definition zugelassenen Regeln kann man auch ein (einfacheres) System verwenden:

Symbol Beschreibung
a b c ... Symbolfolge . Ein Kleinbuchstabe kann durch eine Symbolfolge werden. Gleiche Kleinbuchstaben in einer Folge müssen gleiche Symbolfolgen ersetzt werden.
<math>\Leftrightarrow</math> kann ersetzt werden durch . Die Symbolfolge auf der linken Seite durch die Folge auf der rechten Seite werden ohne den Wahrheitsgehalt zu ändern. Ebenso die rechte Folge durch die linke ersetzt
wahr falsch Symbole für eindeutig wahre und falsche Aussagen
Symbole für Umwandlungsregeln (Beispiel)

Eine Umwandlungsregel könnte dann so aussehen:

Schlussregel1: <math>\neg\neg a \Leftrightarrow a</math>.

Dies bedeutet dass man <math>\neg\neg</math> auf linken Seite jedes Satzes entfernen oder hinzufügen Umgangssprachlich entspricht dies der doppelten Verneinung:

Schlussregel1: Die Verneinung der Verneinung einer Aussage die Aussage selbst

Weitere Umwandlungsregeln sind z.B.

Schlussregel2: <math>\neg falsch \Leftrightarrow wahr</math>
Schlussregel3: <math>wahr \vee a \Leftrightarrow wahr</math>
Schlussregel4: <math>a \vee \neg a \Leftrightarrow wahr</math>
Schlussregel5: <math>a \rightarrow b \Leftrightarrow (\neg a) \vee
Schlussregel6: <math>\neg a \vee \neg b \Leftrightarrow \neg \wedge b)</math>
Schlussregel7: <math>\neg a \wedge \neg b \Leftrightarrow \neg \vee b)</math>
<math>\cdots</math> <math>\cdots</math>
Die Punkte deuten an dass noch weitere Umwandlungsregeln definiert werden können. Dies sind Schlussfolgerungs-Regeln für die formale Logik. Sie können formal ohne Bezug zur Bedeutung der Symbole werden. Damit verhalten sich die Regeln wie Rechenregeln .

Trotzdem wurden die Regeln "sinnvoll" gewählt. Schlussregel3 bedeutet dass eine wahre Aussage oder eine beliebige Aussage als Gesamtaussage immer ist. Dagegen bedeutet die kompliziertere Schlussregel5 (Folgerung) übersetzt etwa:

Schlussregel5: aus a folgt b kann ersetzt durch die Aussage "Verneinung von Aussage a Aussage b" .

Die Folgerung <math>a \rightarrow b</math> ist dann falsch wenn a wahr aber b falsch ist. Umgekehrt ist sie also wahr a falsch oder wenn b wahr ist. entspricht formal <math>(\neg a) \vee b</math> ( lies: nicht a oder b).

Beweise

Ein Beweis besteht aus einer Behauptung und einer Im formalen System wird eine Behauptung b als Symbolfolge dargestellt ebenso die Schlussfolgerung s . Der Beweis wird geführt indem der "aus der Behauptung folgt die Schlussfolgerung" in umgewandelt wird:

Formaler Beweis :
<math>b \rightarrow s</math> (aus der Behauptung b folgt die Schlussfolgerung s ) kann mit Hilfe der Umwandlungsregeln überführt in <math>wahr</math>.

Beweis des Satzes: Aus Falschem folgt Beliebiges

Der klassische Satz ex falsum quod libet (aus Falschem folgt Beliebiges) kann formal und bewiesen werden. In unserem formalen System er:

<math>falsch \rightarrow b</math>

Die Folgerung aus einer falschen Aussage ist wahr

Beweis:

Zum Beweis wenden wir die Umformungsregel die Folgerung an:

<math>\neg falsch \vee b</math> (Schlussregel5)

Nicht falsch ist aber wahr:

<math>wahr \vee b</math> ( Schlussregel2 )

Schliesslich ist eine wahre Aussage oder Beliebiges immer war.

<math>wahr</math> ( Schlussregel3 )

Der Satz ist damit formal bewiesen. Der Beweis könnte durch ein erfolgen das nur die Symbole kennt und 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 ersten Abschnitt des Artikels nicht aus der Kette MI erzeugt werden.

Verkürzung und Verlängerung

Der Beweis kann aber nicht innerhalb M I U-Systems geführt werden. Regel1 und Regel2 verlängern eine Kette Regel3 und Regel4 verkürzen sie dagegen. Eine sehr lange könnte also unter Umständen doch MU ergeben.

Eigenschaften beweisbarer Sätze

Zur Lösung kann man die Eigenschaften beweisbaren Sätze untersuchen. Eine solche Eigenschaft ist Anzahl der I -Symbole in einer Kette die ab jetzt I-Wert genannt werden soll. Der I-Wert des 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

Regel1 und Regel4 lassen den I-Wert unverändert.
Regel2 verdoppelt den I-Wert
Regel3 verringert den I-Wert um drei

Den I-Wert kann man aus der der Anwendungen von Regel2 und Regel3 berechnen. I-Wert des Axioms ist wie gesagt eins. man Regel2 an so erhält man einen von 2. Wendet man sie nochmals an ergibt sich 4 8 16 usw. n-malige ergibt also einen I-Wert von <math>2^n</math>. Jede von Regel3 verringert den I-Wert eines Satzes drei m-malige Anwendung also um <math>3\cdot m</math>. I-Wert ist also

<math>I_{Wert}=2^n-3\cdot m</math>
Regel2 wird n -mal angewendet
Regel3 wird m -mal angewendet

Beweis

Da der zu beweisende Satz MU die I-Zahl null hat muss die

<math>2^n-3\cdot m=0</math>

gelöst werden wobei n und m Zahlen sein müssen. Der Term auf der 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 nicht möglich. Damit ist der Satz MU wie jeder Satz mit dem I-Wert nicht beweisbar die Lösung des Rätsels lautet

Nein



Bücher zum Thema Formales System (Logik)

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Formales_System_(Logik).html">Formales System (Logik) </a>