- 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 0 (oder 1, je nach Definition der natürlichen Zahlen) und der Konstruktionsschritt ist der Übergang von einer Zahl n zur Zahl 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.
Beispiel für eine Definition durch strukturelle Induktion
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 Induktion
Bewiesen wird der Satz:
- Für jede aussagenlogische Formel
gibt es eine äquivalente aussagenlogische Formel
, in der als einzige Operatoren
("nicht") und
("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.
- Induktionsanfang: Falls
Wikimedia Foundation.