Ausdruck in einer Sprache erster Stufe
Es sei ein
Alphabet einer Sprache erster Stufe
gegeben. Dann nennt man die folgenden rekursiv definierten Wörter über diesem Alphabet die
Ausdrücke
dieser Sprache.
- Wenn
und
Terme sind, so ist
-

ein Ausdruck.
- Wenn
ein
-stelliges Relationssymbol ist und
Terme sind, so ist
-
ein Ausdruck.
- Wenn
und
Ausdrücke sind, so sind auch
-
Ausdrücke.
- Wenn
ein Ausdruck und
eine Variable ist, so sind auch
-
Ausdrücke.