Frage von StressedM, 15

Strukturelle induktion frage?

Hallo, ich jabe eine grundsätzliche frage wie man bei der strukturellen induktion vorgeht.

Also man hat ja am anfang Elementaraussagen bzw atomare formeln gegeben und ein regelwerk wie man so eine atomare formel ableitet und wie man eine zusammengesetzte formel ableitet.

Anschließend hat man eine eigenschaft die gelten soll (für alle formeln)

Dann muss man ja als 1.

Induktionsbasis: Zeigen dass für eine atomare die eigenschaft gilt (ein a€true,false,V nehmen und in eigenschaftsformel setzen)

Induktionsvoraussetzung:

Annehmen es gäbe x Formeln z.B. F1,F2 für die die eigenschaft gilt

Induktionsschluss:

Zeigen dass für eine Formel F die sich aus den Teilformeln F1 und/oder F2 zusammensetzt ebenfalls diese eigenschaft gilt (wobei man diese wie bei den ableitungsregeln zusammensetzt):

z.B. F = -F1 ... F = F1 UND F2 ... usw.

Ist das richtig so?

Antwort
von Voeglein93, 12

Prinzipiell ist der Ansatz richtig, vermutlich passt das alles, auch wenn ich nicht weiss, worueber die Induktion laeuft.

Aber es ist wichtig, worueber die Induktion laeuft, zum Beispiel ueber die Anzahl Glieder einer Summe oder das Grad eines Polynoms. 

Diese Eigenschaft muss ueblicherweise als natuerliche Zahl darstellbar sein.

Nach Schritt 1 folgt Schritt 2, die Induktionsvoraussetzung, naehmlich fuer eine beliebige natuerliche Zahl hat die Formel die gewuenschte Eigenschaft.

Dann nimmst du die Formel fuer eine groessere natuerliche Zahl und zerlegst sie in "kleinere" Formeln, fuer die die Eigenschaft nach Voraussetzung gilt.

Kommentar von StressedM ,

ok danke. strukturelle induktion benutzt man für induktiv definierte funktionen bzw solche Datenstrukturen die eine Baumstruktur haben. bei deinem beispiel gehts ja mehr um vollständige induktion

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten