Elementare Sprache

Eine elementare Sprache ${\displaystyle L^{S}}$ (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

Definition

Das Alphabet e​iner Sprache erster Stufe umfasst folgende Zeichen:

1.  ${\displaystyle v_{0},v_{1},v_{2},\ldots }$  Symbole für Variablen;
2.  ${\displaystyle \neg ,\wedge ,\vee ,\rightarrow ,\leftrightarrow }$  Junktoren: nicht, und, oder, wenn - so, genau dann wenn;
3.  ${\displaystyle \forall ,\exists }$  Quantoren: für alle, es gibt;
4.  ${\displaystyle \equiv }$  Gleichheitszeichen;
5.  ${\displaystyle ),(}$  technische Zeichen: Klammersymbole;
6.  sowie

a)  für jedes ${\displaystyle n\geq 1}$ eine (eventuell leere) Menge von ${\displaystyle n}$-stelligen Relationssymbolen, alle zusammen: ${\displaystyle R_{1},R_{2},\ldots }$;

b)  für jedes ${\displaystyle n\geq 1}$ eine (eventuell leere) Menge von ${\displaystyle n}$-stelligen Funktionssymbolen, alle zusammen: ${\displaystyle f_{1},f_{2},\ldots }$;

c)  eine (eventuell leere) Menge von Symbolen für Konstanten ${\displaystyle c_{1},c_{2},\ldots }$ (siehe Anmerkung unten zu 0-stelligen Funktionen).

Die Menge d​er Zeichen u​nter Punkt 1 b​is 5 s​ind die logischen Zeichen; s​ie sind für a​lle Sprachen erster Ordnung dieselben; s​ie werden m​it A bezeichnet.

Die Menge der Zeichen unter Punkt 6 bezeichnet man als Symbolmenge (auch Signatur) ${\displaystyle S=\{R_{1},R_{2},\ldots ,f_{1},f_{2},\ldots ,c_{1},c_{2},\ldots \}}$; durch sie wird die spezielle Sprache erster Stufe bestimmt.

Hinweise

• 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 (${\displaystyle n=0}$), 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

Um d​en Begriff d​er Gruppe u​nd die definierenden Axiome z​u formalisieren, g​eht man w​ie folgt vor:

1. Die Variablen ${\displaystyle x,y,z,\ldots }$ stehen für Elemente der Gruppe; außerdem gibt es eine Konstante ${\displaystyle e}$.
2. Es wird ein Symbol ${\displaystyle \circ }$ eingeführt; dieses steht für die zweistellige Verknüpfung zweier Elemente.
3. Assoziativgesetz: ${\displaystyle \forall x\forall y\forall z(x\circ y)\circ z\equiv x\circ (y\circ z)}$
4. Neutrales Element: ${\displaystyle \forall x(x\circ e\equiv x)}$
5. Inverse Elemente: ${\displaystyle \forall x\exists y(x\circ y\equiv e)}$

In diesem Fall gibt es also ein zweistelliges Funktionssymbol ${\displaystyle \circ }$ sowie eine einzige Konstante ${\displaystyle e}$.

Weitere Beispiele

Relationssymbole	Funktionssymbole	Konstanten	Name
${\displaystyle \leq }$ (zweistellig)	${\displaystyle +,\cdot }$ (beide zweistellig)	0, 1	Geordnete Körper
	${\displaystyle \circ }$ (zweistellig)	e	Gruppen
	+,${\displaystyle \cdot }$ (beide zweistellig)	0, 1	Ringe
${\displaystyle \sim }$ (zweistellig)			Äquivalenzrelation

Terme

→ Hauptartikel: Terme

Die Definition der Terme ${\displaystyle T^{S}}$ 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 ${\displaystyle f}$ ein ${\displaystyle n}$-stelliges Funktionssymbol und ${\displaystyle t_{1},\ldots ,t_{n}}$ Terme sind, dann ist auch ${\displaystyle f(t_{1},\ldots ,t_{n})}$ ein Term.

Symbolmenge S	Beispiel für Terme aus ${\displaystyle T^{S}}$
${\displaystyle (0,1,+,\cdot ,<)\ }$	${\displaystyle 0,1,0+1,(0+v_{1})\cdot ((v_{0}+1)+(v_{2}+1))\ }$,
${\displaystyle (0,+)\ }$	${\displaystyle 0+v_{0}\ }$
${\displaystyle (1,S)\ }$	${\displaystyle 1,S(1),S(S(1)),\ldots }$

Anmerkungen

• Es gibt auch klammerfreie Notationen wie etwa die polnische Notation; in der Regel sind diese aber nicht so leicht zu lesen. Die dritte obige Definitionszeile lautet in dieser Notation (vergleiche: Prädikatenlogik erster Stufe §Terme):

o  Wenn ${\displaystyle f}$ ein n-stelliges Funktionssymbol ist und ${\displaystyle t_{1},\dotsc ,t_{n}}$ Terme sind, so ist auch ${\displaystyle ft_{1},\dotsc ,t_{n}}$ ein Term.

• Gelegentlich werden die Konstanten als nullstellige Funktionen subsumiert, was sich besonders natürlich in der klammerfreien Notation darstellt.

Formeln

→ Siehe auch: Logische Formeln;  Term §Ausdrücke;  Prädikatenlogik erster Stufe §Ausdrücke.

Die Formeln der Sprache ${\displaystyle L^{S}}$ werden durch endlich viele Anwendungen der folgenden Regeln erhalten:

Atomformeln

1. Wenn ${\displaystyle t_{1}}$ und ${\displaystyle t_{2}}$ Terme sind, dann ist ${\displaystyle t_{1}=t_{2}}$ eine Formel.
2. Wenn ${\displaystyle R}$ ein ${\displaystyle n}$-stelliges Relationssymbol und ${\displaystyle t_{1},\ldots ,t_{n}}$ Terme sind, dann ist ${\displaystyle R(t_{1},\ldots ,t_{n})}$ eine Formel.[2]

Aussagenlogische Verknüpfungen

1. Wenn ${\displaystyle \psi }$ eine Formel ist, dann auch ${\displaystyle \neg \psi }$.
2. Wenn ${\displaystyle \psi }$ und ${\displaystyle \theta }$ Formeln sind, dann auch
   • ${\displaystyle \psi \wedge \theta }$
   • ${\displaystyle \psi \vee \theta }$
   • ${\displaystyle \psi \rightarrow \theta }$
   • ${\displaystyle \psi \leftrightarrow \theta }$

Quantoren

→ Hauptartikel: Quantoren

Wenn ${\displaystyle \psi }$ eine Formel und ${\displaystyle x}$ ein beliebiges Variablensymbol ist, dann sind auch

${\displaystyle \exists x\psi }$ und

${\displaystyle \forall x\psi }$

Formeln.

Die elementare Sprache ${\displaystyle L^{S}}$ zur Symbolmenge (Signatur) ${\displaystyle S}$ besteht nun aus allen nach den obigen Regeln gebildeten Formeln.

Zusammenhang mit Chomsky-Hierarchie

Siehe auch: Chomsky-Hierarchie

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

• 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

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