Alphabet (Mathematik)

Unter einem Alphabet A versteht man eine nichtleere Menge von Zeichen bzw. Symbolen. Alphabete sind ein zentraler Begriff der theoretischen Informatik und sind die Grundbausteine von Wörtern, die wiederum die Bausteine von Sprachen bilden. Der zentrale Bestandteil einer Logik ist deren zugrundeliegende Sprache. Das Alphabet dieser Sprache gibt dann die Menge der zulässigen Zeichen an, die benutzt werden dürfen, um die Terme und Ausdrücke dieser Logik aufzubauen. Endliche lineare Reihen von Zeichen eines Alphabets heißen Zeichenreihen oder Wörter über A. Die Menge der Wörter wird mit A^* bezeichnet. Auch die Zeichenreihe, die keine Symbole enthält, ist ein Wort - das leere Wort. Es wird mit ε bezeichnet.

Das Alphabet einer Prädikatenlogik erster Stufe^[1]

Das Alphabet einer Prädikatenlogik erster Stufe umfasst die folgenden Zeichen:

1. $v_0, v_1, v_2, \ldots$ (Variablen)
2. $\neg, \wedge, \vee, \rightarrow, \leftrightarrow$ (Negation (nicht), Konjunktion (und), Disjunktion (oder), Implikation (wenn - dann), Äquivalenz (genau dann wenn))
3. $\forall, \exists$ (universaler und existenzieller Quantor)
4. $\equiv$ (Gleichheitszeichen)
5. ),(,, (Klammersymbole und Komma)
6. des weiteren
   1. eine (eventuell leere) Menge von Konstantensymbolen
   2. für jedes n $\ge$ 0 eine (eventuell leere) Menge von n-stelligen Relationssymbolen
   3. für jedes n $\ge$ 0 eine (eventuell leere) Menge von n-stelligen Funktionssymbolen

Sei A die Menge der in (1) bis (5) aufgelisteten Symbole und S die Symbole aus (6). Dann bezeichne A_S die Vereinigung von A und S. Man nennt A_S das Alphabet der Prädikatenlogik erster Stufe und S seine Symbolmenge. Um das Alphabet einer Prädikatenlogik erster Stufe anzugeben, ist es ausreichend seine Symbolmenge anzugeben, da die Menge A bei allen Alphabeten für Prädikatenlogiken erster Stufe dieselbe ist.

Manchmal verzichtet man in einem Alphabet auf das Gleichheitszeichen. In diesem Fall muss die Symbolmenge zumindest ein Relationssymbol enthalten, da ansonsten keine Formeln gebildet werden können.

Beispiel

Die wichtigste Prädikatenlogik erster Stufe, die Sprache der Mengenlehre, enthält nur ein einziges Zeichen in der Symbolmenge ihres Alphabets, nämlich das zweistellige Relationssymbol $\in$ (siehe Menge (Mathematik)).

Einzelnachweis

1. ↑ Hans Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. Spektrum Akademischer Verlag, Heidelberg 2007, ISBN 3-8274-1691-4.