Benutzer:Jürgen-Michael Glubrecht/Formale Sprachen

Aussagenlogik Bearbeiten

 
Mathematische Symbole und Zeichen.

In den beiden vorangegangenen Kapiteln, hast du Aussagen und Junktoren kennengelernt. Mit Hilfe der Junktoren kann man aus Aussagen weitere Aussagen erzeugen. Wir hatten auch gesehen, dass in der Mathematik eine formalisierte Sprache benutzt wird. Das hat mehrere Gründe:

  • Zum einen ist unsere natürliche Sprache nicht eindeutig. Die Eindeutigkeit der Begriffe und Zusammenhänge ist aber für die Mathematik ganz wesentlich.
  • Zum anderen werden in der Mathematik viele abstrakte Sachverhalte beschrieben und analysiert, für die neue Begriffe mit einer genau festgelegten Bedeutung benötigt werden.

Deshalb benutzt die Mathematik eine künstliche Sprache, die als formale Sprache bezeichnet wird. Wir werden diese Sprache schrittweise vorstellen und beginnen damit in diesem Kapitel. Die weiteren Schritte folgen in der Prädikatenlogik und in der Klassenlogik.

Die folgenden Definitionen erscheinen sehr formal, insbesondere dann, wenn ihr zum ersten Mal damit konfrontiert werdet. Diese formale Strenge hilft jedoch dabei, Fehlschlüsse zu vermeiden und die Mathematik auf eine sichere Grundlagen zu stellen.

Vorbemerkung Bearbeiten

Was also macht uns eigentlich so sicher, dass die Sätze der Mathematik wahr sind? In den Naturwissenschaften werden Theorien in Experimenten geprüft. Nur dann, wenn die gemessenen Ergebnisse zu den errechneten Werten passen, wird eine Theorie akzeptiert. Aber in der Mathematik wird nichts gemessen. Da gibt es keine Experimente, mit denen eine Theorie geprüft wird. Allenfalls in der Geometrie können bestimmte Ergebnisse mit einer Zeichnung verdeutlicht werden. So beispielsweise der Satz des Pythagoras:  .

Die Grundlage für mathematische Theorien sind Aussagen, die in diesem Zusammenhang Axiome genannt werden. Aus den Axiomen werden weitere Sätze allein mit logischen Schlüssen abgeleitet. Alle diese Sätze sind daher von der Art "Wenn die Axiome gelten, dann ist   wahr." Die Mathematiker berufen sich also auf die Logik. Die Logik stellt sicher, dass die Sätze der Mathematik wahr sind. Die Gesetze der Logik

Wir wollen in diesem Kapitel damit beginnen, die Sprache der Mathematik ganz exakt aufzubauen. Warum? Weil wir genau wissen wollen, was wir als Grundlage für die Mathematik nutzen.

Die Sprache der Aussagenlogik Bearbeiten

Für die Logik ist die formale Sprache besonders wichtig, denn mit Hilfe der Logik werden ja die mathematischen Beweise geführt. Beweise verlaufen nach ganz bestimmten Regeln. Das Einhalten dieser Regeln muss automatisiert nachprüfbar sein! Und das geht in einer formalisierten Sprache am besten. Die Sprache, in der Aussagen mit Junktoren verknüpft werden, ist die Sprache der Aussagenlogik. Wie unsere natürliche Sprache hat sie ein Alphabet:

Definition (Alphabet der Aussagenlogik)

Die Sprache der Aussagenlogik hat drei Arten von Zeichen:

  1. die Aussagenkonstanten  ,   und  ,
  2. die Junktoren  ,  ,  ,  ,   und  ,
  3. die Klammern   und  .

Die Zeichen heißen   (Wahr) und   (Falsch), die Junktoren   (Negation),   (Konkunktion),   (Disjunktion),   (Kontravalenz),   (Implikation) und   (Äquivalenz).

Anmerkung: Genaugenommen bestehen die Konstanten selbst aus mehreren Zeichen, dem Buchstaben   und einer Zahl. Wir wollen die Konstanten hier aber als eine Einheit betrachten. Es ist nicht weiter wichtig, wie sie genau realisiert werden. Wichtig ist nur, dass wir ausreichend viele Konstanten haben und bei Bedarf immer noch ein paar neue hinzunehmen können.

Aus diesen Zeichen können nach bestimmten Regeln Wörter gebildet werden, die in diesem Zusammenhang Formeln oder wohlgeformte Zeichenreihen genannt werden. Zeichenreihen entstehen einfach dadurch, das Zeichen aus dem Alphabet hintereinander geschrieben werden, zum Beispiel so:  . Aber das ist keine Formel!

Definition (Formeln der Aussagenlogik)

Die Formeln der Aussagenlogik werden nach folgenden Regeln gebildet:

  1. Jede Aussagenkonstante ist eine Formel,   und   sind Formeln.
  2. Ist   eine Formel, so ist auch   eine Formel.
  3. Sind   und   Formeln, so sind auch  ,  ,  ,   und   Formeln.

Es gibt keine weiteren Formeln.

Eine solche Definition wird rekursiv (lat. zurückgehend) genannt, weil bei der Erzeugung weiterer Formeln auf bereits erzeugte Formel zurückgegriffen wird.

Beispiel für eine Formel Bearbeiten

Um zu zeigen, wie diese Regeln angewendet werden, zeigen wir, dass   eine Formel der Aussagenlogik

Zeile Formel Begründung
1   nach Regel 1,   ist eine Aussagenkonstante
2   nach Regel 1,   ist eine Aussagenkonstante
3   nach Regel 3 angewendet auf Zeile 1 und 2
4   nach Regel 2 angewendet auf Zeile 3
5   nach Regel 3 angewendet auf Zeile 1 und 2
6   nach Regel 3 angewendet auf Zeile 4 und 5

Beweis über den Aufbau der Formeln Bearbeiten

Die rekursive Definition der Formeln erlaubt ein besonderes Beweisverfahren. Um eine Behauptung für alle Formeln zu beweisen, genügen zwei Schritte:

  1. Im ersten Schritt wird die Behauptung für die Aussagenkonstanten   und für   und   gezeigt.
  2. Im zweiten Schritt wird gezeigt, dass sich die Behauptung unter den Regeln vererbt. Das heisst folgendes:
    • Wenn die Behauptung für eine Formel   gilt, dann gilt sie auch für die Formel  .
    • Wenn die Behauptung für die Formeln   und   gilt, dann gilt sie auch für die Formel  ,  ,  ,   und  .

Es ist klar, dass die Behauptung dann für alle Formeln gelten muss, denn Formeln können ja nur aufgrund dieser Regeln entstehen! Wir zeigen als Beispiel den folgenden einfachen Satz:

Satz

Jede Formel enthält genauso viele linke wie rechte Klammern.

Beweis

  1. Für beliebige Aussagenkonstanten   und für   und   ist das richtig, denn sie enthalten gar keine Klammern.
  2. Wenn   genauso viele linke wie rechte Klammern enthält, dann gilt das auch für  , denn bei der Bildung der Negation kommen keine Klammern dazu. Haben schließlich   und   jeweils gleichviele linke wie rechte Klammern, so kommen bei   genau eine linke und eine rechte Klammer dazu. Also bleiben es gleichviele. So ist es auch bei den weiteren Regeln für  ,  ,   und  . ✔

Klammerersparnis, Schreibweisen Bearbeiten

Bei der Schreibweise von Formeln lassen wir die Außenklammern in der Regel weg und erlauben uns auch andere Freiheiten. Es muss nur immer klar sein, welche Formel im Sinne der obigen Definition gemeint ist. Natürlich übernehmen wir auch die Bindungsregeln aus dem Kapitel über Junktoren um Klammern wegzulassen:

  1. Negation  
  2. Konjunktion  
  3. Disjunktion  
  4. Implikation  
  5. Äquivalenz  

Falls es dem Verständnis dient, setzen wir auch zusätzliche Klammern.

Aussagen formalisieren Bearbeiten

Wir greifen nun einige Aussagen auf, die wir schon im Kapitel Junktoren angesprochen haben. Wenn wir Aussagen formalisieren dann heißt das nichts anderes als sie in eine Formel zu übersetzen, die der Aussage möglich gut entspricht.

Beispiel 1: Zwei Aussagen werden mit dem Junktor und verbunden.

  ist durch 2 teilbar und   ist gerade.“

Zur Zeit haben wir nur die Möglichkeit, die beiden Aussagen durch eine Konstante widerzugeben, sagen wir durch   ("  ist durch 2 teilbar.") und   ("  ist gerade."). Dann lautet die formalisierte Aussage einfach:

 

Da es hierbei auf die Konstanten   und   gar nicht ankommt, verwendet man einfach auch die Variablen   und   und schreibt   für die formalisierte Aussage. Wir wissen aber aus dem Zusammenhang, dass damit eine exakte Formel der Aussagenlogik gemeint ist.

Anmerkung: Wir werden in den Kapiteln Prädikatenlogik und Klassenlogik weitere Möglichkeiten kennenlernen, Aussagen besser zu formalisieren.

Verständnisfrage: Formalisiere die folgenden Aussagen:

  1. Wenn Berlin in Deutschland liegt und der Rhein durch Deutschland fließt, dann liegt Berlin am Rhein.
  2. Teilt   eine natürliche Zahl  , dann wird   entweder von   oder von   geteilt.
  3. Es gibt unendlich viele Primzahlen.

Antwort:

  1. Sei   Berlin liegt in Deutschland,   Der Rhein fließt durch Deutschland,  Berlin liegt am Rhein. Dann lautet die Formalisierung  . Die Klammern könnten wir wegen der Bindungsregeln weglassen.
  2.  , wobei  ,   und   bedeuten.
  3. Diese Aussage enthält keine Junktoren. In der Aussagenlogik kann man sie nur durch eine Konstante formalisieren.

Teilformeln Bearbeiten

Beim rekursiven Aufbau einer Formel   erhält man zwischen durch weitere Formeln. Diese Formeln werden Teilformeln genannt. Die genaue Definition ist natürlich ebenfalls rekursiv. Teilformeln, die keine Teilformeln haben, heißen atomare Formeln.

Definition (Teilformeln, atomare Formeln)

  1. Die Aussagenkonstanten   und die Formeln   und   sind atomare Formeln.
  2. Die Teilformeln von   sind die Teilformeln von   und   selbst. Die Teilformeln von  ,  ,  ,   und   sind die Teilformeln von   und  , sowie   und   selbst.

Verständnisfrage: Welche Teilformeln hat die im Beispiel oben erstellte Formel  ?

Antwort:

Atomere Formeln:   und  . Weitere Teilformeln:  ,   und  

Prädikatenlogik Bearbeiten

 
Arithmetische Operationssymbole

In den beiden Kapiteln Quantoren und Aussageform und Substitution haben wir Begriffe eingführt, die über die Aussagenlogik hinaus gehen und zur Prädikatenlogik gehören. Wir fassen diese Begriffe am Beispiel der Arithmetik noch einmal zusammen.

Beispiel Arithmetik Bearbeiten

Wenn wir über die natürlichen Zahlen reden wollen, dann brauchen wir Variable  , die für beliebige natürliche Zahlen stehen. Für die speziellen Zahlen   benötigen wir Konstanten. Desweiteren brauchen wir Operationssymbole für die vier Rechenarten  . Anstelle von   und   werden oft auch die Symbole   und   verwendet. Diese Operationen sind alle 2-stellig. Mit diesem Material können wir Terme bilden, die weitere Zahlen bezeichnen, zum Beispiel:

  •  
  •  

Um auszudrücken, das zwei Terme dieselbe Zahl bezeichnen benötigen wir das Gleichheitszeichen   und für Ungleichungen das 2-stellige Prädikat Kleiner-oder-gleich  . Die weiteren Ordnungen lassen sich dann definieren. Ein 1-stelliges Prädikat   mit der Bedeutung "... ist eine natürliche Zahl" ersetzt  , die Menge der natürlichen Zahlen. Diese steht erst in der sogenannten Klassenlogik zur Verfügung. Und der wichtigste Teil der Prädikatenlogik sind die Quantoren  . Natürlich stehen die Junktoren   weiterhin zur Verfügung. Damit können wir wesentlich mehr Formeln bilden als in der Aussagenlogik. Insbesondere können wir die atomaren Formeln der Aussagenlogik nun genauer analysieren.

Beispiel 1: In der Aussagenlogik konnten wir die Aussage "  ist kleiner als   und   ist gerade." nur in der Form   widergeben. Nun geht es so:

 

Dabei steht   für "  ist gerade." Eine andere Möglichkeit ist es, hierfür ein weiteres 1-stelliges Prädikat   zu benutzen.

Beispiel 2: Wie können wir folgende Aussage formalisieren? "Für beliebige Zahlen   und   gilt: Ist   verschieden von   und kleiner-oder-gleich  , dann ist die Differenz von   und   keine natürliche Zahl."

 

Mit der Definition von Echt-kleiner   lässt sich das noch vereinfachen:

 

Die Sprache der Prädikatenlogik Bearbeiten

Wir erweitern das Alphabet der Aussagenlogik wie folgt:

Definition (Alphabet der Prädikatenlogik)

Die Sprache der Prädikatenlogik hat neun Arten von Zeichen:

  1. die Aussagenkonstanten  ,   und  ,
  2. die Junktoren  ,  ,  ,  ,   und  ,
  3. die Klammern   und  ,
  4. die Individuenkonstanten  ,
  5. die Operationssymbole  ,
  6. die Prädikate  ,
  7. das Gleichheitszeichen  ,
  8. die Variable  ,
  9. die Quantoren  ,   und  .

Jedem Prädikat und jedem Operationssymbol ist eine natürliche Zahl   als Stellenzahl zugeordnet.

Die Prädikate werden auch Relationszeichen genannt und die Operationssymbole heissen auch Funktionszeichen.

Definition (Terme der Prädikatenlogik)

Die Terme der Prädikatenlogik werden nach folgenden Regeln gebildet:

  1. Jede Individuenkonstante   ist ein Term.
  2. Sind   Terme und ist   ein  -stelliges Operationssymbol, so ist   ein Term.

Es gibt keine weiteren Terme.

Definition (Formeln der Prädikatenlogik)

Die Formeln der Aussagenlogik werden nach folgenden Regeln gebildet:

  1. Jede Aussagenkonstante ist eine Formel,   und   sind Formeln.
  2. Ist   eine Formel, so ist auch   eine Formel.
  3. Sind   und   Formeln, so sind auch  ,  ,  ,   und   Formeln.
  4. Sind   Terme und ist   ein  -stelliges Prädikat, so ist   eine Formel.
  5. Sind   und   Terme, so ist   eine Formel.
  6. Ist   eine Variable und ist   eine Formel, so sind    ,       und       Formeln.

Es gibt keine weiteren Formeln.

Die Regeln 1. bis 3. sind dieselben, wie in der Aussagenlogik. Deshalb sind alle Formeln der Aussagenlogik auch Formeln der Prädikatenlogik! Zusätzlich können die Regeln 2. und 3. auf weitere Formeln angewendet werden, z.B. auf Formeln, die mit Prädikaten und Quantoren gebildet wurden. Wir halten fest:

Satz

Alle Formeln der Aussagenlogik sind auch Formeln der Prädikatenlogik.

Ein Ausdruck der Prädikatenlogik ist ein Term oder eine Formel.

Notation Bearbeiten

Klassenlogik Bearbeiten

 
Satz des Pythagoras

Die Sprache der Klassenlogik Bearbeiten

Wir erweitern nun die Prädikatenlogik um die Elementbeziehung   und um den Klassenbildungsoperator  .

Hinweis

In der Klassenlogik werden die (naiven) Mengen Klassen genannt. Deswegen heißt der Operator nicht Mengenbildungsoperator.

Definition (Alphabet der Klassenlogik)

Die Sprache der Klassenlogik hat zwölf Arten von Zeichen:

  1. die Aussagenkonstanten  ,   und  ,
  2. die Junktoren  ,  ,  ,  ,   und  ,
  3. die Klammern   und  ,
  4. die Individuenkonstanten  ,
  5. die Operationssymbole  ,
  6. die Prädikate  ,
  7. das Gleichheitszeichen  ,
  8. die Variable  ,
  9. die Quantoren  ,   und  .
  10. die Konstanten  ,
  11. das Elementzeichen  ,
  12. den Klassenbildungsoperator  .

Jedem Prädikat und jedem Operationssymbol ist eine natürliche Zahl   als Stellenzahl zugeordnet.

Definition (Terme und Formeln der Klassenlogik)

Die Terme und die Formeln der Klassenlogik werden nach folgenden Regeln gebildet:

  1. Jede Individuenkonstante  , jedes Operationssymbol  , jedes Prädikat   und jede Konstante   ist ein Term.
  2. Sind   Terme und ist   ein  -stelliges Operationssymbol, so ist   ein Term.
  3. Jede Aussagenkonstante ist eine Formel,   und   sind Formeln.
  4. Ist   eine Formel, so ist auch   eine Formel.
  5. Sind   und   Formeln, so sind auch  ,  ,  ,   und   Formeln.
  6. Sind   Terme und ist   ein  -stelliges Prädikat, so ist   eine Formel.
  7. Sind   und   Terme, so sind   und   eine Formeln.
  8. Ist   eine Variable und ist   eine Formel, so sind    ,       und       Formeln.
  9. Ist   eine Variable und ist   eine Formel, so ist       ein Term.

Es gibt keine weiteren Terme und Formeln.

Ein Ausdruck der Klassenlogik ist ein Term oder eine Formel der Klassenlogik.

Satz

Alle Terme der Prädikatenlogik sind auch Terme der Klassenlogik.

Alle Formeln der Prädikatenlogik sind auch Formeln der Klassenlogik.

Beweis

Die Regeln zur Bildung von Termen und Formeln der Prädikatenlogik habe wir ja wörtlich für die Klassenlogik übernommen! Wir können daher jeden Term und jede Formel der Prädikatenlogik in der Klassenlogik auf dieselbe Weise bilden.