Ausdrücke erster Stufe/Über Alphabet/Rekursiv/Definition

Aus Wikiversity
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.

  1. Wenn und Terme sind, so ist

    ein Ausdruck.

  2. Wenn ein -stelliges Relationssymbol ist und Terme sind, so ist

    ein Ausdruck.

  3. Wenn und Ausdrücke sind, so sind auch

    Ausdrücke.

  4. Wenn ein Ausdruck und eine Variable ist, so sind auch

    Ausdrücke.