Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.

Es ist keine Literatur angegeben. --Maformatiker (Diskussion) 18:02, 10. Dez. 2016 (CET)

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.

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:

Ist eine Aussage ${\displaystyle A}$ ein Theorem und ist ${\displaystyle A'}$ das Resultat der universellen Substitution von ${\displaystyle b}$ durch ${\displaystyle C}$, so ist ${\displaystyle A'}$ wiederum ein Theorem. Wichtig ist hier, dass universell substituiert wird; bei bloß einfacher Substitution ist nicht gewährleistet, dass ${\displaystyle A'}$ ein Theorem ist. Eine weitere Voraussetzung ist, dass es sich bei dem Substituendum ${\displaystyle b}$ um einen „Satzparameter“ handelt, d. h. um eine nicht-komplexe Formel, die überdies in keinem Axiom vorkommt. Für das Substituens ${\displaystyle C}$ gibt es keine entsprechende Beschränkung.

Beispiel:

In dem Theorem

${\displaystyle b\Rightarrow b}$

können wir den Ausdruck ${\displaystyle b}$ universell ersetzen durch

${\displaystyle c\vee d}$

und erhalten wiederum ein Theorem, nämlich:

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

Bei einfacher Substitution könnten wir auch folgendes erhalten:

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

was kein Theorem ist. Wenn wir die Forderung fallenließen, dass das Substituendum ein Satzparameter ist, so könnten wir den ganzen Ausdruck ${\displaystyle b\Rightarrow b}$ durch eine Formel, etwa ${\displaystyle c}$, ersetzen und erhielten:

${\displaystyle c,}$

was natürlich ebenfalls kein Theorem ist.

Die Eigenschaft, dass universelle Substitution die Theorem-Eigenschaft erhält, wird in manchen Kalkülen ausgenutzt, indem dies als Schlussregel formuliert wird. Die Regel der universellen Substitution besagt, dass man in jeder Formel, die man mit einem Beweis gewonnen hat, jeden Satzparameter durch eine beliebige Aussage universell ersetzen kann.

Sind zwei Aussagen ${\displaystyle B}$ und ${\displaystyle C}$ äquivalent und ist ${\displaystyle A'}$ ein Resultat der einfachen Substitution von ${\displaystyle B}$ durch ${\displaystyle C}$ in ${\displaystyle A}$, dann sind ${\displaystyle A}$ und ${\displaystyle A'}$ ebenfalls äquivalent.

Beispiel:

Zwei äquivalente Aussagen sind beispielsweise:

${\displaystyle B:b\wedge c}$

und

${\displaystyle C:c\wedge b}$,

Wenn wir nun in der Aussage

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

${\displaystyle B}$ durch ${\displaystyle C}$ einfach substituieren, können wir folgendes erhalten:

${\displaystyle A':(c\wedge b)\Rightarrow ((b\wedge c)\wedge d)}$

${\displaystyle A}$ und ${\displaystyle A'}$ sind nun wiederum äquivalent.

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“.