www.wikidata.de-de.nina.az

Strukturelle Induktion Die strukturelle Induktion ist ein Beweisverfahren das unter anderem in der Logik der theoretisch

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 (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 Induktion Bearbeiten

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

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

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 Bearbeiten

Bewiesen wird der Satz:

Der Beweis:

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.

Literatur Bearbeiten

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

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 vollstandigen Induktion Mit dem Verfahren lassen sich Aussagen uber die Elemente von rekursiv aufgebauten Mengen zum Beispiel Mengen von Listen Formeln Graphen beweisen Bei der vollstandigen Induktion werden Eigenschaften der naturlichen Zahlen bewiesen bei der strukturellen Induktion werden Eigenschaften fur 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 naturlichen Zahlen ist das Grundelement 0 displaystyle 0 oder 1 displaystyle 1 je nach Definition der naturlichen Zahlen und der Konstruktionsschritt ist der Ubergang von einer Zahl n displaystyle n zur Zahl n 1 displaystyle n 1 Um eine Aussage fur die Elemente einer Menge zu beweisen zeigt man im Induktionsanfang die Gultigkeit der Aussage fur die einfachsten Elemente und im Induktionsschluss die Gultigkeit der Aussage fur die rekursiv gebildeten Elemente unter der Voraussetzung dass die Aussage fur die in der Konstruktion verwendeten Elemente gilt Ist beides erfullt so gilt die Aussage fur alle Elemente Man fuhrt die Induktion also uber den strukturellen Aufbau der Elemente Strukturelle Induktion ist ein Spezialfall der Induktion fur Mengen mit einer wohlfundierten partiellen Ordnung Inhaltsverzeichnis 1 Beispiel fur eine Definition durch strukturelle Induktion 2 Beispiel fur einen Beweis durch strukturelle Induktion 3 Literatur 4 WeblinksBeispiel fur eine Definition durch strukturelle Induktion BearbeitenDie Menge der aussagenlogischen Formeln lasst sich mittels struktureller Induktion wie folgt definieren Induktionsanfang Falls A displaystyle A nbsp eine atomare aussagenlogische Formel ist ist A displaystyle A nbsp eine aussagenlogische Formel Induktionsschritt 1 Falls F displaystyle F nbsp eine aussagenlogische Formel ist ist auch F displaystyle lnot F nbsp eine aussagenlogische Formel Induktionsschritt 2 Falls F displaystyle F nbsp und G displaystyle G nbsp aussagenlogische Formeln sind ist auch F G displaystyle F land G nbsp eine aussagenlogische Formel Induktionsschritt 3 Falls F displaystyle F nbsp und G displaystyle G nbsp aussagenlogische Formeln sind ist auch F G displaystyle F lor G nbsp eine aussagenlogische Formel Induktionsschritt 4 Falls F displaystyle F nbsp und G displaystyle G nbsp aussagenlogische Formeln sind ist auch F G displaystyle F to G nbsp eine aussagenlogische Formel Induktionsschritt 5 Falls F displaystyle F nbsp und G displaystyle G nbsp aussagenlogische Formeln sind ist auch F G displaystyle F leftrightarrow G nbsp eine aussagenlogische Formel Nach dieser Definition sind z B die folgenden Terme aussagenlogische Formeln A B displaystyle lnot A land B nbsp A B C displaystyle A to B lor lnot C nbsp A B A B displaystyle A lor lnot B land lnot A lor B nbsp Weitere Beispiele fur Definitionen durch strukturelle Induktion finden sich in den Artikeln Elementare Sprache und Wort Theoretische Informatik Definition der Spiegelung Beispiel fur einen Beweis durch strukturelle Induktion BearbeitenBewiesen wird der Satz Fur jede aussagenlogische Formel F displaystyle F nbsp gibt es eine aquivalente aussagenlogische Formel F displaystyle F nbsp in der als einzige Operatoren displaystyle lnot nbsp und displaystyle land nbsp vorkommen Der Beweis Induktionsanfang Falls F A displaystyle F A nbsp fur eine atomare aussagenlogische Formel A displaystyle A nbsp ist ist F A displaystyle F A nbsp Induktionsschritt 1 Falls F G displaystyle F lnot G nbsp fur eine aussagenlogische Formel G displaystyle G nbsp gilt ist F G displaystyle F lnot G nbsp Induktionsschritt 2 Falls F G H displaystyle F G land H nbsp fur aussagenlogische Formeln G displaystyle G nbsp und H displaystyle H nbsp gilt ist F G H displaystyle F G land H nbsp Induktionsschritt 3 Falls F G H displaystyle F G lor H nbsp fur aussagenlogische Formeln G displaystyle G nbsp und H displaystyle H nbsp gilt ist F G H displaystyle F lnot lnot G land lnot H nbsp Induktionsschritt 4 Falls F G H displaystyle F G to H nbsp fur aussagenlogische Formeln G displaystyle G nbsp und H displaystyle H nbsp gilt ist F G H displaystyle F lnot G land lnot H nbsp Induktionsschritt 5 Falls F G H displaystyle F G leftrightarrow H nbsp fur aussagenlogische Formeln G displaystyle G nbsp und H displaystyle H nbsp gilt ist F G H G H displaystyle F lnot lnot G land H land lnot lnot G land lnot H nbsp Das Gleichheitszeichen steht hier fur syntaktische Gleichheit d h Gleichheit Zeichen fur Zeichen In jedem Induktionsschritt wird vorausgesetzt dass fur G displaystyle G nbsp und H displaystyle H nbsp jeweils die aquivalenten Formeln G displaystyle G nbsp und H displaystyle H nbsp existieren die nur displaystyle lnot nbsp und displaystyle land nbsp verwenden Induktionsvoraussetzung In einer konkreten Konstruktion kann man die Beweisschritte auch in der umgekehrten Reihenfolge also von aussen nach innen anwenden Fur die mittlere der oben angegebenen aussagenlogischen Formeln gelten z B die folgenden Aquivalenzen A B C A B C IS 4 A B C IS 3 A B C IS 1 A B C 3 IA A B C displaystyle begin aligned A to B lor lnot C amp equiv A to B lor lnot C amp stackrel mbox IS 4 lnot A land lnot B lor lnot C amp stackrel mbox IS 3 lnot A land lnot lnot lnot B land lnot lnot C amp stackrel mbox IS 1 lnot A land lnot lnot lnot B land lnot lnot C amp stackrel 3 times mbox IA lnot A land lnot lnot lnot B land lnot lnot C end aligned nbsp Die Anwendungen des Induktionsschritts 1 und des Induktionsanfangs sind hier leer d h sie verandern den Term nicht Bei der ersten oben angegebenen Formel waren alle Induktionsschritte und der Induktionsanfang leer Dass sich die letzte Formel noch zu A B C displaystyle lnot A land lnot B land C nbsp vereinfachen lasst ist hier ubrigens unerheblich Literatur BearbeitenHartmut Ehrig Bernd Mahr F Cornelius Martin Grosse Rhode P Zeitz Mathematisch strukturelle Grundlagen der Informatik Springer 2013 S 162 168Weblinks BearbeitenFrancois Bry Satz 2 1 4 strukturelle Induktion Skript LMU Christoph Walter Strukturelle Induktion und Induktion nach Rekursion von Prozeduren Skript Uni Darmstadt Abgerufen von https de wikipedia org w index php title Strukturelle Induktion amp oldid 202777207