Als Substitution bezeichnet man in der Logik allgemein die Ersetzung eines Ausdrucks durch einen anderen.

Genauer müssen hier vier verschiedene Ausdrücke voneinander unterschieden werden:

• das Substituendum (lat.: „das zu Ersetzende“): der Ausdruck, der ersetzt wird
• das Substituens (lat.: „das Ersetzende“): der Ausdruck, der ersetzt
• die Substitutions-Basis: der Ausdruck, in dem ersetzt wird
• das Substitutionsresultat: das Ergebnis der Ersetzung.

Beispiel:

Ersetzen wir in dem Ausdruck

${\displaystyle a\Rightarrow (b\wedge c)}$

(lies: „wenn ${\displaystyle a}$, dann ${\displaystyle b}$ und ${\displaystyle c}$“) den Ausdruck ${\displaystyle b}$ durch

${\displaystyle c\vee d}$

(lies: „${\displaystyle c}$ oder ${\displaystyle d}$“), so erhalten wir:

${\displaystyle a\Rightarrow ((c\vee d)\wedge c)}$.

Dabei ist ${\displaystyle b}$ Substituendum, ${\displaystyle c\vee d}$ Substituens, ${\displaystyle a\Rightarrow (b\wedge c)}$ Substitutionsbasis und ${\displaystyle a\Rightarrow ((c\vee d)\wedge c)}$ Substitutionsresultat.

Man unterscheidet zwischen universeller und einfacher Substitution, außerdem ist in der Quantorenlogik auch der Begriff „frei zur Substitution“ von Bedeutung.

Universelle und einfache Substitution

Bei der universellen Substitution müssen alle Vorkommnisse des Substituendums ersetzt werden, bei der einfachen Substitution brauchen nicht alle Vorkommnisse ersetzt zu werden. Der Unterschied zwischen den beiden Substitutions-Arten wird also erst relevant, wenn es mindestens zwei Vorkommnisse des Substituendums in der Substitutions-Basis gibt. Bei der universellen Substitution kommt das Substituendum im Substitutions-Resultat nicht mehr vor, bei der einfachen Substitution kann es immer noch vorkommen.

Beispiel:

Ersetzen wir in dem Ausdruck

${\displaystyle b\Rightarrow (b\wedge c)}$

den Ausdruck ${\displaystyle b}$ durch

${\displaystyle c\vee d}$,

so erhalten wir bei universeller Substitution:

${\displaystyle (c\vee d)\Rightarrow ((c\vee d)\wedge c)}$.

Bei einfacher Substitution könnten wir auch folgendes erhalten:

${\displaystyle (c\vee d)\Rightarrow (b\wedge c)}$

Universelle und einfache Substitution spielen in unterschiedlichen Gesetzen eine Rolle:

Der Begriff „zur Substitution frei“

Ein Term ${\displaystyle t}$ ist zur Substitution durch eine Variable ${\displaystyle x}$ in einer Formel ${\displaystyle B}$ frei, wenn ${\displaystyle t}$ nicht im Skopus eines Quantors ${\displaystyle \forall x}$ oder ${\displaystyle \exists x}$ steht.

Der Hintergrund dieser Definition ist folgender: Man will in der Quantorenlogik davon sprechen, dass eine Aussage eine All- oder Existenz-Generalisierung einer anderen darstellt. Zum Beispiel ist

Jemand raucht,

formal:

${\displaystyle \exists xR(x)}$

eine Existenz-Generalisierung von

Frank raucht,

formal:

${\displaystyle R(f)}$

Es scheint nun so, als erhielte man eine Generalisierung, wenn man die Vorkommnisse des zu generalisierenden Terms (im Beispiel „Frank“ bzw. ${\displaystyle f}$) universell durch ${\displaystyle x}$ ersetzt und einen Quantor ${\displaystyle \forall x}$ oder ${\displaystyle \exists x}$ vor die Aussage setzt. Man erhält eine Generalisierung aber nur unter der zusätzlichen Voraussetzung, dass der zu generalisierende Term zur Ersetzung durch ${\displaystyle x}$ frei ist.

Beispiel

Man betrachte die Aussage

Wenn jemand Frank liebt, ist Frank glücklich,

formal

${\displaystyle A:\exists xL(x,f)\Rightarrow G(f)}$

Man beachte, dass hier ${\displaystyle f}$ nicht zur Substitution durch ${\displaystyle x}$ frei ist, da es im Skopus des Existenzquantors ${\displaystyle \exists x}$ vorkommt. Daher ist auch folgende Aussage keine All-Generalisierung von ${\displaystyle A}$:

${\displaystyle \forall x(\exists xL(x,x)\Rightarrow G(x))}$

denn diese Aussage bedeutet:

„Wenn jemand sich selbst liebt, sind alle glücklich“

und dies geht vollkommen an der Bedeutung der ursprünglichen Aussage vorbei.

Man kann aber in einem solchen Fall immer eine Generalisierung mit einer anderen Variable vornehmen. Beispielsweise ist ${\displaystyle f}$ in ${\displaystyle A}$ zur Substitution mit ${\displaystyle y}$ frei, daher kann man folgende All-Generalisierung bilden:

${\displaystyle \forall y(\exists xL(x,y)\Rightarrow G(y))}$

und diese Aussage hat dann die gewünschte Bedeutung, nämlich:

„Alle, die jemand liebt, sind glücklich“.