Elementare Sprache

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 Stufe[Bearbeiten | Quelltext bearbeiten]

Definition[Bearbeiten | Quelltext bearbeiten]

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.

Hinweise[Bearbeiten | Quelltext bearbeiten]

  • In Alphabet (Mathematik) 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: Gruppentheorie[Bearbeiten | Quelltext bearbeiten]

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 Beispiele[Bearbeiten | Quelltext bearbeiten]

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

Terme[Bearbeiten | Quelltext bearbeiten]

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.

Formeln[Bearbeiten | Quelltext bearbeiten]

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

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

Atomformeln[Bearbeiten | Quelltext bearbeiten]

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

Aussagenlogische Verknüpfungen[Bearbeiten | Quelltext bearbeiten]

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

Quantoren[Bearbeiten | Quelltext bearbeiten]

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-Hierarchie[Bearbeiten | Quelltext bearbeiten]

  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.

Quellen[Bearbeiten | Quelltext bearbeiten]

  • 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.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  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]).