Elementare Sprache

Eine elementare Sprache (auch: Sprache erster Stufe mit der Symbolmenge S) ist eine im Rahmen der Prädikatenlogik erster Stufe definierte formale Sprache. Mit diesen Sprachen lassen sich mathematische Theorien formallogisch behandeln; so z. B. die Mengenlehre usw. Die Erfahrung zeigt sogar, dass sich alle mathematischen Aussagen in einer geeigneten Sprache erster Stufe formalisieren lassen, und dass sich alle beweisbaren Aussagen innerhalb einer Sprache erster Stufe mit Hilfe des Sequenzenkalküls ableiten lassen.[1]

Das Alphabet einer Sprache erster StufeBearbeiten

DefinitionBearbeiten

Das Alphabet einer Sprache erster Stufe umfasst folgende Zeichen:

  1.     Symbole für Variablen;
  2.     Junktoren: nicht, und, oder, wenn - so, genau dann wenn;
  3.     Quantoren: für alle, es gibt;
  4.     Gleichheitszeichen;
  5.     technische Zeichen: Klammersymbole;
  6.  sowie
a)  für jedes   eine (eventuell leere) Menge von  -stelligen Relationssymbolen, alle zusammen:  ;
b)  für jedes   eine (eventuell leere) Menge von  -stelligen Funktionssymbolen, alle zusammen:  ;
c)  eine (eventuell leere) Menge von Symbolen für Konstanten   (siehe Anmerkung unten zu 0-stelligen Funktionen).

Die Menge der Zeichen unter Punkt 1 bis 5 sind die logischen Zeichen; sie sind für alle Sprachen erster Ordnung dieselben; sie werden mit A bezeichnet.

Die Menge der Zeichen unter Punkt 6 bezeichnet man als Symbolmenge (auch Signatur)  ; durch sie wird die spezielle Sprache erster Stufe bestimmt.

HinweiseBearbeiten

  • In Alphabeten sind bei sonst identischer Definition die Konstanten aus (f)(3) nicht aufgeführt; dafür sind in (f)(1) nullstellige Relationen und Funktionen erlaubt ( ), letztere entsprechen den Konstanten aus der obigen Definition (siehe auch Nullstellige Verknüpfungen).
  • Die einstelligen Relationen definieren Zusammenfassungen wie sie Mengen oder allgemeiner Klassen entsprechen.

Beispiel: GruppentheorieBearbeiten

Um den Begriff der Gruppe und die definierenden Axiome zu formalisieren, geht man wie folgt vor:

  1. Die Variablen   stehen für Elemente der Gruppe; außerdem gibt es eine Konstante  .
  2. Es wird ein Symbol   eingeführt; dieses steht für die zweistellige Verknüpfung zweier Elemente.
  3. Assoziativgesetz:  
  4. Neutrales Element:  
  5. Inverse Elemente:  

In diesem Fall gibt es also ein zweistelliges Funktionssymbol   sowie eine einzige Konstante  .

Weitere BeispieleBearbeiten

Relationssymbole Funktionssymbole Konstanten Name
  (zweistellig)   (beide zweistellig) 0, 1 Geordnete Körper
  (zweistellig) e Gruppen
+,  (beide zweistellig) 0, 1 Ringe
  (zweistellig) Äquivalenzrelation

TermeBearbeiten

Die Definition der Terme   einer elementaren Sprache erfolgt rekursiv. Ein Term der elementaren Sprache wird durch endlich viele Anwendungen der folgenden Regeln erhalten

  1. Variablensymbole sind Terme.
  2. Konstantensymbole sind Terme.
  3. Wenn   ein  -stelliges Funktionssymbol und   Terme sind, dann ist auch   ein Term.
Symbolmenge S Beispiel für Terme aus  
   ,
   
   
Anmerkungen
o  Wenn   ein n-stelliges Funktionssymbol ist und   Terme sind, so ist auch   ein Term.
  • Gelegentlich werden die Konstanten als nullstellige Funktionen subsumiert, was sich besonders natürlich in der klammerfreien Notation darstellt.

FormelnBearbeiten

→ Siehe auch: Logische FormelnTerm §AusdrückePrädikatenlogik erster Stufe §Ausdrücke.

Die Formeln der Sprache   werden durch endlich viele Anwendungen der folgenden Regeln erhalten:

AtomformelnBearbeiten

  1. Wenn   und   Terme sind, dann ist   eine Formel.
  2. Wenn   ein  -stelliges Relationssymbol und   Terme sind, dann ist   eine Formel.[2]

Aussagenlogische VerknüpfungenBearbeiten

  1. Wenn   eine Formel ist, dann auch  .
  2. Wenn   und   Formeln sind, dann auch
    •  
    •  
    •  
    •  

QuantorenBearbeiten

Wenn   eine Formel und   ein beliebiges Variablensymbol ist, dann sind auch

  und
 

Formeln.

Die elementare Sprache   zur Symbolmenge (Signatur)   besteht nun aus allen nach den obigen Regeln gebildeten Formeln.

Zusammenhang mit Chomsky-HierarchieBearbeiten

  1. Die Regeln für Terme entsprechen einer kontextfreien Sprache.
  2. Die Regeln für Formeln entsprechen ebenfalls einer kontextfreien Sprache: Elementare Sprachen sind also kontextfreie Sprachen und damit eine spezielle Klasse von formalen Sprachen.
  3. Die Regeln für Beweise entsprechen einer kontextsensitiven Sprache. Durch eine kontextsensitive Analyse kann entschieden werden, ob ein gegebener Beweis für eine Formel vorliegt.
  4. Die Regeln für das Ableiten einer Formel aus einem Axiomensystem entspricht einer semi-entscheibaren Sprache. Es gibt im Allgemeinen keinen Algorithmus, um einen Beweis zu erhalten, der eine Formel aus einer anderen Aussagenmenge ableitet.

QuellenBearbeiten

  • H.D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik. BI-Wiss. Verlag, Mannheim / Leipzig / Wien / Zürich 1992, ISBN 3-411-15603-1.
  • Hans-Peter Tuschik, Helmut Wolter: Mathematische Logik - kurzgefasst. Grundlagen, Modelltheorie, Entscheidbarkeit, Mengenlehre. BI-Wiss. Verlag, Mannheim / Leipzig / Wien / Zürich 1994, ISBN 3-411-16731-9.

EinzelnachweiseBearbeiten

  1. Ebbinghaus u. a., Kapitel VII §2: Mathematik im Rahmen der ersten Stufe.
  2. Gelegentlich werden nullstellige Relationen zugelassen, dies treten dann als logische Konstanten (im Prinzip Bezeichner für wahr oder falsch) auf.
    Stefan Brass: Mathematische Logik mit Datenbank-Anwendungen. Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik, Halle 2005, S. 176, hier S. 19 (informatik.uni-halle.de [PDF]).