Interpretation von prädikatenlogische Formeln

Einfache Sprache

Def. Interpretation von prädikatenlogische Formeln

Sei $\mathcal S$ eine Signatur und $\mathcal A$ eine $\mathcal S$-Struktur.

Für eine A-Belegung $\beta$ hat eine $\mathcal S$-Formel $\varphi$ in $\mathcal A$ unter $\beta$, geschrieben $\textlbrackdbl \varphi\textrbrackdbl^\mathcal A_\beta$, den Wahrheitswert induktiv definiert durch

IA:

• Für Boolescher Wert gilt $\textlbrackdbl \top\textrbrackdbl^\mathcal A_\beta = 1$ und $\textlbrackdbl \bot\textrbrackdbl^\mathcal A_\beta = 0$.
• Für alle $\mathcal S$-Terme $t_0,t_1$ gilt $$\textlbrackdbl t_0\doteq t_1\textrbrackdbl^\mathcal A_\beta = \begin{cases}1 &\text{if } \textlbrackdbl t_0\textrbrackdbl^\mathcal A_\beta = \textlbrackdbl t_1\textrbrackdbl^\mathcal A_\beta\\ 0 & \text{else.}\end{cases}$$
• Für jedes Relationssymbol $R\in\mathcal R$ mit der Stelligkeit $n = \Sigma(R)$ und $\mathcal S$-Terme $t_0,\ldots,t_{n-1}$ gilt $$\textlbrackdbl R(t_0,\ldots,t_{n-1})\textrbrackdbl^\mathcal A_\beta = \begin{cases}1 &\text{if } (\textlbrackdbl t_0\textrbrackdbl^\mathcal A_\beta,\ldots,\textlbrackdbl t_{n-1}\textrbrackdbl^\mathcal A_\beta)\in R^\mathcal A\\ 0 & \text{else.}\end{cases}$$

IS:

• Für jeden $n$-stelligen Junktor $C$ und $\mathcal S$-Formeln $\varphi_0,\ldots,\varphi_{n-1}$ gilt $$\textlbrackdbl C(\varphi_0,\ldots,\varphi_{n-1})\textrbrackdbl^\mathcal A_\beta = f_C(\textlbrackdbl \varphi_0\textrbrackdbl^\mathcal A_\beta ,\ldots,\textlbrackdbl \varphi_{n-1}\textrbrackdbl^\mathcal A_\beta) \;.$$
• Für eine $\mathcal S$-Formel $\varphi$ und $I\in\mathbb N$ gilt, mithilfe der Variablenbelegungsveränderung $$\textlbrackdbl \forall x_i\varphi\textrbrackdbl^\mathcal A_\beta = \begin{cases}1&\text{if } \forall a\in A:\textlbrackdbl \varphi\textrbrackdbl^\mathcal A_{\beta[\frac{x_i}{a}]} = 1\\ 0 & \text{else}\end{cases}$$ und $$\textlbrackdbl \forall x_i\varphi\textrbrackdbl^\mathcal A_\beta = \begin{cases}1&\text{if } \exists a\in A:\textlbrackdbl \varphi\textrbrackdbl^\mathcal A_{\beta[\frac{x_i}{a}]} = 1\\ 0 & \text{else.}\end{cases}$$