Substitution

Einfache Sprache

Bei einer Substitution werden Variablen der Formel durch eine andere Formel ersetzt. Ziel ist es

Def. Substitution

Eine Substitution ist eine Partielle Funktion $\sigma:\mathbf V_{AL}\rightharpoonup\mathbf F_{AL}$, die Aussagenlogische Variable auf Aussagenlogischen Formel abbildet. Geschrieben wird bei einer Anwendung einer Substitution $\sigma$ auf einer Formel $\phi$ wie folgt: $\varphi\sigma$. $\sigma$ ist induktiv definiert durch:

Basiselemente: Es gilt für Wahrheitswerte

$$\top\sigma = \top$$

und

$$\bot\sigma=\bot\;.$$

Für die eine Variable $X_i > Sei $\varphi\in\mathbf F_{AL}$ und $\sigma\in\mathbf V_{AL}$, dann gilt $$X(m,n)=\begin{cases} \sigma(X_i)& X_i\in\mathrm{dom}(\sigma)\\X_i& \text{else.}\end{cases}$$

Induktiver Schritt: Seien $\varphi_0, \ldots, \varphi_{n-1} \in \mathbf F_{AL}$ aussagelogische Formeln und $C$ ein $n$-stelliger Junktor, dann gilt

$$(C(\varphi_0, \ldots, \varphi_{n-1}))\sigma = C(\varphi_0\sigma, \ldots, \varphi_{n-1}\sigma)\;.$$

Beispiel Substitution

Sei die Substitution $\sigma$ gegeben durch $\sigma = \{X_0\to \neg X_3,X_1 \to X_2 \lor X_0\}.$ Dann ergibt sich folgende Gleichung:

$$\begin{align}(X_0\land\neg(X_2\to X_1))\sigma &= X_0\sigma\land(\neg(X_2\to X_1))\sigma&\Huge|\normalsize\text{Ind. Regel für $\land$}\\&= \sigma(X_0)\land(\neg(X_2\to X_1))\sigma&\Huge|\normalsize\text{Basiselemente}\\&= \sigma(X_0)\land\neg((X_2\to X_1)\sigma)&\Huge|\normalsize\text{Ind. Regel für $\neg$}\\&= \sigma(X_0)\land\neg(X_2\sigma\to X_1\sigma)&\Huge|\normalsize\text{Ind. Regel für $\to$}\\&= \sigma(X_0)\land\neg(\sigma(X_2)\to \sigma(X_1))&\Huge|\normalsize\text{Basiselemente}\\&= \neg X_3\land\neg(X_2\to (X_2\lor X_1))&\Huge|\normalsize\text{Def. $\sigma$}\\\end{align}$$

Ein Sonderfall der Substitution ist die Äquivalente Substitution.