Koinzidenzlemma
Einfache Sprache
Der Wahrheitswert einer Aussagenlogischen Formel unter einer Belegung $\beta$ hängt nur von den in der Formel vorkommenden Variablen ab.
Warum ist das Interessant? Weil es die Definition von Belegungen als partielle Funktionen, da es genügt, die Belegungen der in der Formel vorkommenden Variablen anzugeben.
Letztendlich ermöglicht es uns zu sagen das: eine Passende Variablenbelegung $\beta$ ist genau dann ein Modell einer einer Formel $\varphi$, wenn die Knappe Variablenbelegung $\beta|_{vars(\varphi)}$ ein Modell von $\varphi$ ist.
Def. Koinzidenzlemma
Für jede Aussagenlogischen Formel $\varphi \in \mathbf F_{AL}$ und alle Belegungen $\beta_0,\beta_1$ mit $\beta_0 |_{\text{vars}(\varphi))} = \beta_1|_{\text{vars}(\varphi)}$ gilt $\textlbrackdbl\varphi\textrbrackdbl_{\beta_0} = \textlbrackdbl\varphi\textrbrackdbl_{\beta_1}$.
Beweis: induktiv über Aufbau von $\varphi$.
Basiselemente: Für $\varphi = \bot$ gilt:
$$\begin{align}\textlbrackdbl\bot\textrbrackdbl_{\beta_0} &= 0&\Huge|\normalsize\text{Semantik $\bot$}\\&= \textlbrackdbl\bot\textrbrackdbl_{\beta_1}&\Huge|\normalsize\text{Semantik $\bot$}\\\end{align}$$Für $\varphi = \top$ gilt:
$$\begin{align}\textlbrackdbl\top\textrbrackdbl_{\beta_0} &= 1&\Huge|\normalsize\text{Semantik $\bot$}\\&= \textlbrackdbl\bot\textrbrackdbl_{\beta_1}&\Huge|\normalsize\text{Semantik $\top$}\\\end{align}$$Für $\varphi = X_i$ mit $X_i\in\mathbf{V}_{AL}$ gilt:
$$\begin{align}\textlbrackdbl X_i\textrbrackdbl_{\beta_0} &= \beta_0(X_i)&\Huge|\normalsize\text{Semantik von Variablen}\\&= \beta_1(X_i)&\Huge|\normalsize\text{$\beta_0 |_{\text{vars}(\varphi))} = \beta_1|_{\text{vars}(\varphi)}$ und $\mathrm{vars}(X_i) = \{X_i\}$}\\&= \textlbrackdbl X_i\textrbrackdbl_{\beta_1}&\Huge|\normalsize\text{Semantik von Variablen}\\\end{align}$$Induktiver Schritt Wir nutzen das Lemma Falls einschränkt gleich dann auch für Teilmenge der Einschränkung gleich.
Sei $\varphi_0,\ldots,\varphi_{n-1}\in\mathbf F_{AL}$, $C$ ein $n$-stelliger Junktor und $\varphi = C(\varphi_0,\ldots,\varphi_{n-1})$. Aus dem Lemma wissen wir das $\beta_0 |_{\text{vars}(\varphi))} = \beta_1|_{\text{vars}(\varphi)}$. Wir müssen nun $\textlbrackdbl\varphi\textrbrackdbl_{\beta_0} = \textlbrackdbl\varphi\textrbrackdbl_{\beta_1}$ zeigen.
Wir nehmen an das für $i Aus der Definition von $\varphi$ und von vars folg, dass $\mathrm{vars}(\varphi_i)\subseteq\mathrm{vars}(\varphi)$ für alle $i Zusammen mit diesem Lemma folgt $\beta_0 |_{\text{vars}(\varphi_i))} = \beta_1|_{\text{vars}(\varphi_i)}$ für alle $i Es ergibt sich folgende Gleichung