Ersetzungslemma
Einfache Sprache
Das Ersetzungslemmas besagt, dass zwei Formel gleich sind, wenn nur ein Teil der Formel durch eine äquivalente Teil ersetzt wurde.
Def. Ersetzungslemma
Seien $\sigma,\sigma'$ äquivalente Substitutionen und sei $\varphi\in\mathbf F_{AL}$ eine Aussagenlogischen Formel. Dann gilt $\varphi\sigma\models=|\varphi\sigma'$.
Beweis: Sei $\varphi\in\mathbf F_{AL}$ eine Aussagenlogischen Formel und $\sigma, \sigma'$ Äquivalente Substitution. Beweis per Induktion über $\varphi$.
Basiselemente: Für die Wahrheitswerte gilt
$$\begin{align}\top\sigma &= \top &\Huge|\normalsize\text{Def. Substitution}\\&= \top\sigma' &\Huge|\normalsize\text{Def. Substitution}\\\end{align}$$und
$$\begin{align}\bot\sigma &= \bot &\Huge|\normalsize\text{Def. Substitution}\\&= \bot\sigma' &\Huge|\normalsize\text{Def. Substitution}\\\end{align}$$Für jedes $X_i\in\mathrm{dom}(\sigma)$ und damit auf für jedes $X_i\in\mathrm{dom}(\sigma')$,wegen der Äquivalenz von $\sigma$ und $\sigma'$, gilt:
$$\begin{align}X_i\sigma &= \sigma(X_i) &\Huge|\normalsize\text{Def. Substitution}\\&= \sigma'(X_i) &\Huge|\normalsize\text{$\sigma\models=|\sigma'$}\\&= X_i\sigma' &\Huge|\normalsize\text{Def. Substitution}\\\end{align}$$Induktionsschritt: Sei $\varphi', \psi\in\mathbf F_{AL}$ und nehmen wir an das $\varphi'\sigma\models =|\varphi'\sigma'$ und $\psi'\sigma\models =|\psi'\sigma'$ für alle äquivalenten Substitutionen gilt (Induktionshypothese). Zu zeigen ist, dass die Konjunktion der beiden Formeln $\varphi'\land\psi$ auch äquivalent ist. Für alle Variablenbelegungen $\beta$ gilt:
$$\begin{align}\textlbrackdbl(\varphi'\land\psi)\sigma\textrbrackdbl_\beta &= \textlbrackdbl\varphi'\sigma\land\psi\sigma\textrbrackdbl_\beta&\Huge|\normalsize\text{Def. Substitution}\\&= f_\land(\textlbrackdbl\varphi'\sigma\textrbrackdbl_\beta, \textlbrackdbl\psi\sigma\textrbrackdbl_\beta)&\Huge|\normalsize\text{Semantik $\land$}\\&= f_\land(\textlbrackdbl\varphi'\sigma'\textrbrackdbl_\beta, \textlbrackdbl\psi\sigma'\textrbrackdbl_\beta)&\Huge|\normalsize\text{Induktionshypothese}\\&= \textlbrackdbl\varphi'\sigma'\land\psi\sigma'\textrbrackdbl_\beta &\Huge|\normalsize\text{Semantik $\land$}\\&= \textlbrackdbl(\varphi'\land\psi)\sigma'\textrbrackdbl_\beta &\Huge|\normalsize\text{Def. Substitution}\\\end{align}$$Daraus folgt, dass $(\varphi'\land\psi)\sigma\models=| (\varphi'\land\psi)\sigma'$. Für die anderen Junktoren funktioniert der Beweis analog. $\bullet$
Beispiel
Sei $\varphi = X_2 \land (X_0\lor \neg X_1)$ und betrachte $\sigma_0 = \{X_2 \mapsto \neg X_0 \lor X_1\}$ und $\sigma_1 = \{X_2 \mapsto X_0 \rightarrow X_1\}$. Dann sind die Substitutionen äquivalent gemäß der Paraphrasierung von $\rightarrow$. Mit dem Ersetzungslemma erhalten wir nun
$$(\neg X_0 \lor X_1) \land (X_0 \lor \neg X_1) \models=| (X_0 \rightarrow X_1) \land (X_0 \lor \neg X_1).$$$\bullet$