Hauptmenü öffnen

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 (oder , je nach Definition der natürlichen Zahlen) und der Konstruktionsschritt ist der Übergang von einer Zahl zur Zahl .

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.

Beispiel für eine Definition durch strukturelle InduktionBearbeiten

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

Induktionsanfang: Falls   eine atomare aussagenlogische Formel ist, ist   eine aussagenlogische Formel.
Induktionsschritt 1: Falls   eine aussagenlogische Formel ist, ist auch   eine aussagenlogische Formel.
Induktionsschritt 2: Falls   und   aussagenlogische Formeln sind, ist auch   eine aussagenlogische Formel.
Induktionsschritt 3: Falls   und   aussagenlogische Formeln sind, ist auch   eine aussagenlogische Formel.
Induktionsschritt 4: Falls   und   aussagenlogische Formeln sind, ist auch   eine aussagenlogische Formel.
Induktionsschritt 5: Falls   und   aussagenlogische Formeln sind, ist auch   eine aussagenlogische Formel.

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

  •  
  •  
  •  

Viele Klammern können weggelassen werden, wenn man die Assoziativität von   und   ausnutzt und eine Operatorrangfolge vereinbart.

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

Beispiel für einen Beweis durch strukturelle InduktionBearbeiten

Bewiesen wird der Satz:

Für jede aussagenlogische Formel   gibt es eine äquivalente aussagenlogische Formel  , in der als einzige Operatoren   und   vorkommen.

Der Beweis:

Induktionsanfang: Falls   für eine atomare aussagenlogische Formel   ist, ist  .
Induktionsschritt 1: Falls   für eine aussagenlogische Formel   gilt, ist  .
Induktionsschritt 2: Falls   für aussagenlogische Formeln   und   gilt, ist  .
Induktionsschritt 3: Falls   für aussagenlogische Formeln   und   gilt, ist  .
Induktionsschritt 4: Falls   für aussagenlogische Formeln   und   gilt, ist  .
Induktionsschritt 5: Falls   für aussagenlogische Formeln   und   gilt, ist  .

Das Gleichheitszeichen steht hier für syntaktische Gleichheit, d. h. Gleichheit Zeichen für Zeichen. In jedem Induktionsschritt wird vorausgesetzt, dass für   und   jeweils die äquivalenten Formeln   und   existieren, die nur   und   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:

 

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   vereinfachen lässt, ist hier übrigens unerheblich.