Prädikatenlogik/Sprache/Einführung/Textabschnitt

Definition

Ein Alphabet einer Sprache erster Stufe umfasst die folgenden Daten.

1. Eine Grundtermmenge, also eine Menge aus Variablen, Konstanten und Funktionssymbolen.
2. Zu jeder natürlichen Zahl ${}n\in \mathbb {N} _{+}$ eine Menge ${}R_{n}$ von ${}n$-stelligen Relationssymbolen.
3. Die aussagenlogischen Junktoren

   $\neg ,\,\wedge ,\,\vee ,\,\rightarrow ,\,\leftrightarrow .$

4. Das Gleichheitszeichen ${}=$.
5. Die Quantoren ${}\forall$ und ${}\exists$.
6. Klammern, also ${}($ und ${})$.

Die aussagenlogischen Junktoren werden als Negation, Konjunktion (und), Disjunktion (Alteration, einschließliches Oder), Implikation (wenn, dann) und Äquivalenz (genau dann, wenn) bezeichnet. Der Quantor ${}\forall$ heißt Allquantor und ${}\exists$ heißt Existenzquantor. Diese Liste ist etwas redundant, da man, von der späteren Interpretation her gesehen, einige aussagenlogische Junktoren durch andere ersetzen kann, beispielsweise ist für zwei Aussagen ${}\alpha$ und ${}\beta$ die Aussage ${}\alpha \rightarrow \beta$ gleichwertig mit ${}\neg \alpha \vee \beta$, und so könnte man den Implikationspfeil auch weglassen. Ebenso kann man den einen Quantor mit Hilfe des anderen und der Negation ausdrücken, es ist nämlich ${}\forall x\alpha$ gleichbedeutend mit ${}\neg \exists x\neg \alpha$. Um die Lesbarkeit der Ausdrücke zu erhöhen, ist es aber alles in allem vorteilhaft, nicht allzu minimalistisch sein zu wollen (man könnte die unnötigen Symbole auch als Abkürzungen einführen). Das Gleichheitszeichen könnte man zwar auch als ein weiteres zweistelliges Relationssymbol auffassen, allerdings sind die weiter unten einzuführenden Schlussregeln für das Gleichheitszeichen (insbesondere die Möglichkeit einzusetzen) für die Logik erster Stufe konstitutiv. Da ein Alphabet einer Sprache erster Stufe eine Termgrundmenge enthält, ist klar, was als Term in der Sprache zu gelten hat. Als nächstes erklären wir formal, was wir als einen Ausdruck (oder eine formale Aussage) in dieser Sprache ansehen.

Definition

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 ${}t_{1}$ und ${}t_{2}$ Terme sind, so ist

   ${}t_{1}=t_{2}\,$

   ein Ausdruck.

2. Wenn ${}R$ ein ${}n$-stelliges Relationssymbol ist und ${}t_{1},\ldots ,t_{n}$ Terme sind, so ist

   $Rt_{1}{\ldots }t_{n}$

   ein Ausdruck.

3. Wenn ${}\alpha$ und ${}\beta$ Ausdrücke sind, so sind auch

   $\neg {\left(\alpha \right)},\,{\left(\alpha \right)}\wedge {\left(\beta \right)},\,{\left(\alpha \right)}\vee {\left(\beta \right)},\,{\left(\alpha \right)}\rightarrow {\left(\beta \right)},\,{\left(\alpha \right)}\leftrightarrow {\left(\beta \right)}$

   Ausdrücke.

4. Wenn ${}\alpha$ ein Ausdruck und ${}x$ eine Variable ist, so sind auch

   $\forall x{\left(\alpha \right)}\,\,{\text{ und }}\,\,\exists x{\left(\alpha \right)}$

   Ausdrücke.

Die Klammern sind hier auch nur nötig, weil wir die zweistelligen Junktoren anders als die Funktionssymbole in der Mitte schreiben. Die Menge der Konstanten, der Variablen, der Funktionssymbole und der Relationssymbole nennt man zusammen auch das Symbolalphabet der Sprache, das wir mit ${}S$ bezeichnen. Die anderen Symbole (Junktoren, Quantoren, Gleichheitszeichen, Klammern) sind immer gleich, sodass eine Sprache erster Stufe im Wesentlichen nur von der gewählten Symbolmenge ${}S$ abhängt. Für die zugehörige Sprache schreibt man ${}L^{S}$.