Prädikatenlogik/Freie und gebundene Variablen/Textabschnitt

In einem Ausdruck ${}\alpha \in L^{S}$ über einem Symbolalphabet ${}S$ nennt man die Variablen, die (und zwar für jedes Vorkommen) innerhalb der Reichweite eines Quantors stehen, gebunden, die anderen frei. Dies wird streng über den Aufbau der Ausdrücke definiert.

1. ${}\operatorname {Frei} \,(t_{1}=t_{2})=\operatorname {Var} \,(t_{1})\cup \operatorname {Var} \,(t_{2})\,.$

2. ${}\operatorname {Frei} \,(Rt_{1}\ldots t_{n})=\operatorname {Var} \,(t_{1})\cup \operatorname {Var} \,(t_{2})\cup \ldots \cup \operatorname {Var} \,(t_{n})\,$

   für ein ${}n$-stelliges Relationssymbol ${}R$ und ${}n$ Terme ${}t_{1},t_{2},\ldots ,t_{n}$.

3. ${}\operatorname {Frei} \,(\neg \alpha )=\operatorname {Frei} \,(\alpha )\,$

   für einen Ausdruck ${}\alpha$.

4. ${}\operatorname {Frei} \,(\alpha \rightarrow \beta )=\operatorname {Frei} \,(\alpha )\cup \operatorname {Frei} \,(\beta )\,$

   für Ausdrücke ${}\alpha$ und ${}\beta$. Ebenso für ${}\leftrightarrow ,\wedge ,\vee$.

5. ${}\operatorname {Frei} \,(\forall x\alpha )=\operatorname {Frei} \,(\alpha )\setminus \{x\}\,$

   für einen Ausdruck ${}\alpha$ und eine Variable ${}x$.

6. ${}\operatorname {Frei} \,(\exists x\alpha )=\operatorname {Frei} \,(\alpha )\setminus \{x\}\,$

   für einen Ausdruck ${}\alpha$ und eine Variable ${}x$.

Einen Ausdruck ohne freie Variablen nennt man einen Satz, auch wenn diese Bezeichnung nicht ganz glücklich ist, da „Satz“ die Gültigkeit einer Aussage suggeriert. Die Menge der Sätze wird mit ${}L_{0}^{S}$ bezeichnet, die Menge der Ausdrücke mit genau einer freien Variablen (die aber in dem Ausdruck beliebig oft vorkommen darf) mit ${}L_{1}^{S}$.