Elementare Sprache

Eine elementare Sprache $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 einer Sprache erster Stufe umfasst folgende Zeichen:

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

a) für jedes

n\geq 1

eine (eventuell leere) Menge von

n

-stelligen Relationssymbolen, alle zusammen:

R_{1},R_{2},\ldots

;

b) für jedes

n\geq 1

eine (eventuell leere) Menge von

n

-stelligen Funktionssymbolen, alle zusammen:

f_{1},f_{2},\ldots

;

c) eine (eventuell leere) Menge von Symbolen für Konstanten

c_{1},c_{2},\ldots

(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) $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 (6)(c) nicht aufgeführt; dafür sind in (6)(a) nullstellige Relationen und Funktionen erlaubt ( $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 den Begriff der Gruppe und die definierenden Axiome zu formalisieren, geht man wie folgt vor:

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

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

Weitere Beispiele

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

Terme

Die Definition der Terme $T^{S}$ einer elementaren Sprache erfolgt rekursiv. Ein Term der elementaren Sprache wird durch endlich viele Anwendungen der folgenden Regeln erhalten

Variablensymbole sind Terme.
Konstantensymbole sind Terme.
Wenn $f$ ein $n$ -stelliges Funktionssymbol und $t_{1},\ldots ,t_{n}$ Terme sind, dann ist auch $f(t_{1},\ldots ,t_{n})$ ein Term.

Symbolmenge S	Beispiel für Terme aus $T^{S}$
$(0,1,+,\cdot ,<)\$	$0,1,0+1,(0+v_{1})\cdot ((v_{0}+1)+(v_{2}+1))\$ ,
$(0,+)\$	$0+v_{0}\$
$(1,S)\$	$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

f

ein n-stelliges Funktionssymbol ist und

t_{1},\dotsc ,t_{n}

Terme sind, so ist auch

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 $L^{S}$ werden durch endlich viele Anwendungen der folgenden Regeln erhalten:

Atomformeln

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

Aussagenlogische Verknüpfungen

Wenn $\psi$ eine Formel ist, dann auch $\neg \psi$ .
Wenn $\psi$ und $\theta$ Formeln sind, dann auch
- $\psi \wedge \theta$
- $\psi \vee \theta$
- $\psi \rightarrow \theta$
- $\psi \leftrightarrow \theta$

Quantoren

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

\exists x\psi

und

\forall x\psi

Formeln.

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

Zusammenhang mit Chomsky-Hierarchie

Die Regeln für Terme entsprechen einer kontextfreien Sprache.
Die Regeln für Formeln entsprechen ebenfalls einer kontextfreien Sprache: Elementare Sprachen sind also kontextfreie Sprachen und damit eine spezielle Klasse von formalen Sprachen.
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.
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

↑ Ebbinghaus u. a., Kapitel VII § 2: Mathematik im Rahmen der ersten Stufe.
↑ 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]).

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

[1]

[2]

Fahrer / Team für die Suche eingeben: