Strukturelle Induktion

Die strukturelle Induktion ist ein Beweisverfahren, das unter anderem in der Logik, der theoretischen Informatik und der Graphentheorie eingesetzt wird. Es handelt sich um eine allgemeinere Form der vollständigen Induktion. Mit dem Verfahren lassen sich Aussagen über die Elemente von rekursiv aufgebauten Mengen (zum Beispiel Mengen von Listen, Formeln, Graphen) beweisen.

Bei der vollständigen Induktion werden Eigenschaften der natürlichen Zahlen bewiesen; bei der strukturellen Induktion werden Eigenschaften für Mengen bewiesen, deren Elemente aus Grundelementen durch eine endliche Anzahl von Konstruktionsschritten (unter Verwendung bereits konstruierter Elemente) bzw. mittels eines Erzeugungssystems entstehen. Es gibt also minimale (auch: einfachste oder Grund-)Elemente und rekursiv definierte (oder: rekursiv gebildete) Elemente der Menge. Bei den natürlichen Zahlen ist das Grundelement ${\displaystyle 0}$ (oder ${\displaystyle 1}$, je nach Definition der natürlichen Zahlen) und der Konstruktionsschritt ist der Übergang von einer Zahl ${\displaystyle n}$ zur Zahl ${\displaystyle n+1}$.

Um eine Aussage für die Elemente einer Menge zu beweisen, zeigt man im Induktionsanfang die Gültigkeit der Aussage für die einfachsten Elemente und im Induktionsschluss die Gültigkeit der Aussage für die rekursiv gebildeten Elemente unter der Voraussetzung, dass die Aussage für die in der Konstruktion verwendeten Elemente gilt. Ist beides erfüllt, so gilt die Aussage für alle Elemente. Man führt die Induktion also über den strukturellen Aufbau der Elemente.

Strukturelle Induktion ist ein Spezialfall der Induktion für Mengen mit einer wohlfundierten (partiellen) Ordnung.

Die Menge der aussagenlogischen Formeln lässt sich mittels struktureller Induktion wie folgt definieren:

Induktionsanfang: Falls ${\displaystyle A\!\,}$ eine atomare aussagenlogische Formel ist, ist ${\displaystyle A\!\,}$ eine aussagenlogische Formel.

Induktionsschritt 1: Falls ${\displaystyle F\!\,}$ eine aussagenlogische Formel ist, ist auch ${\displaystyle \lnot F}$ eine aussagenlogische Formel.

Induktionsschritt 2: Falls ${\displaystyle F\!\,}$ und ${\displaystyle G\!\,}$ aussagenlogische Formeln sind, ist auch ${\displaystyle (F\land G)}$ eine aussagenlogische Formel.

Induktionsschritt 3: Falls ${\displaystyle F\!\,}$ und ${\displaystyle G\!\,}$ aussagenlogische Formeln sind, ist auch ${\displaystyle (F\lor G)}$ eine aussagenlogische Formel.

Induktionsschritt 4: Falls ${\displaystyle F\!\,}$ und ${\displaystyle G\!\,}$ aussagenlogische Formeln sind, ist auch ${\displaystyle \!\,(F\to G)}$ eine aussagenlogische Formel.

Induktionsschritt 5: Falls ${\displaystyle F\!\,}$ und ${\displaystyle G\!\,}$ aussagenlogische Formeln sind, ist auch ${\displaystyle (F\leftrightarrow G)}$ eine aussagenlogische Formel.

Nach dieser Definition sind z. B. die folgenden Terme aussagenlogische Formeln:

• ${\displaystyle \lnot (A\land B)}$
• ${\displaystyle (A\to (B\lor \lnot C))}$
• ${\displaystyle ((A\lor \lnot B)\land (\lnot A\lor B))}$

Weitere Beispiele für Definitionen durch strukturelle Induktion finden sich in den Artikeln Elementare Sprache und Wort (Theoretische Informatik) (Definition der Spiegelung).

Bewiesen wird der Satz:

Für jede aussagenlogische Formel ${\displaystyle F}$ gibt es eine äquivalente aussagenlogische Formel ${\displaystyle [F]}$, in der als einzige Operatoren ${\displaystyle \lnot }$ und ${\displaystyle \land }$ vorkommen.

Der Beweis:

Induktionsanfang: Falls ${\displaystyle F=A}$ für eine atomare aussagenlogische Formel ${\displaystyle A}$ ist, ist ${\displaystyle [F]=A}$.

Induktionsschritt 1: Falls ${\displaystyle F=\lnot G}$ für eine aussagenlogische Formel ${\displaystyle G}$ gilt, ist ${\displaystyle [F]=\lnot [G]}$.

Induktionsschritt 2: Falls ${\displaystyle F=(G\land H)}$ für aussagenlogische Formeln ${\displaystyle G}$ und ${\displaystyle H}$ gilt, ist ${\displaystyle [F]=([G]\land [H])}$.

Induktionsschritt 3: Falls ${\displaystyle F=(G\lor H)}$ für aussagenlogische Formeln ${\displaystyle G}$ und ${\displaystyle H}$ gilt, ist ${\displaystyle [F]=\lnot (\lnot [G]\land \lnot [H])}$.

Induktionsschritt 4: Falls ${\displaystyle F=(G\to H)}$ für aussagenlogische Formeln ${\displaystyle G}$ und ${\displaystyle H}$ gilt, ist ${\displaystyle [F]=\lnot ([G]\land \lnot [H])}$.

Induktionsschritt 5: Falls ${\displaystyle F=(G\leftrightarrow H)}$ für aussagenlogische Formeln ${\displaystyle G}$ und ${\displaystyle H}$ gilt, ist ${\displaystyle [F]=\lnot (\lnot ([G]\land [H])\land \lnot (\lnot [G]\land \lnot [H]))}$.

Das Gleichheitszeichen steht hier für syntaktische Gleichheit, d. h. Gleichheit Zeichen für Zeichen. In jedem Induktionsschritt wird vorausgesetzt, dass für ${\displaystyle G}$ und ${\displaystyle H}$ jeweils die äquivalenten Formeln ${\displaystyle [G]}$ und ${\displaystyle [H]}$ existieren, die nur ${\displaystyle \lnot }$ und ${\displaystyle \land }$ verwenden (Induktionsvoraussetzung).

In einer konkreten Konstruktion kann man die Beweisschritte auch in der umgekehrten Reihenfolge, also „von außen nach innen“, anwenden. Für die mittlere der oben angegebenen aussagenlogischen Formeln gelten z. B. die folgenden Äquivalenzen:

${\displaystyle {\begin{aligned}(A\to (B\lor \lnot C))&\equiv [(A\to (B\lor \lnot C))]\\&{\stackrel {\mbox{IS 4}}{=}}\lnot ([A]\land \lnot [(B\lor \lnot C)])\\&{\stackrel {\mbox{IS 3}}{=}}\lnot ([A]\land \lnot \lnot (\lnot [B]\land \lnot [\lnot C]))\\&{\stackrel {\mbox{IS 1}}{=}}\lnot ([A]\land \lnot \lnot (\lnot [B]\land \lnot \lnot [C]))\\&{\stackrel {3\times {\mbox{IA}}}{=}}\lnot (A\land \lnot \lnot (\lnot B\land \lnot \lnot C))\end{aligned}}}$

Die Anwendungen des Induktionsschritts 1 und des Induktionsanfangs sind hier leer, d. h., sie verändern den Term nicht. (Bei der ersten oben angegebenen Formel wären alle Induktionsschritte und der Induktionsanfang leer.) Dass sich die letzte Formel noch zu ${\displaystyle \lnot (A\land (\lnot B\land C))}$ vereinfachen lässt, ist hier übrigens unerheblich.

• Hartmut Ehrig, Bernd Mahr, F. Cornelius, Martin Große-Rhode, P. Zeitz: Mathematisch-strukturelle Grundlagen der Informatik. Springer, 2013, S. 162–168

• François Bry: Satz 2.1.4 (strukturelle Induktion). Skript, LMU
• Christoph Walter: Strukturelle Induktion und Induktion nach Rekursion von Prozeduren. Skript, Uni Darmstadt