Hallo Leute. Ich hatte immer schon Probleme mit der vollständigen Induktion, selbiges gilt deswegen natürlich auch für die strukturelle. Ich habe Google jetzt schon eine Weile bemüht, doch es spuckt einfach keine brauchbare Einleitung in die Strukturelle Induktion aus.

Es wird echt mal an der Zeit, dass ich das Prinzip verstehe und wollte hier einfach mal auf gut Glück fragen, ob jemand von euch einen hübschen Link für mich hätte - strukturelle Induktion for dummies o.ä.

Wäre vllcht sogar bereit mir ein Buch zu besorgen, gibt es da Tipps? Wichtig ist mir eine natürlich Sprachliche erklärung und nicht lauter so kurz wie möglich gehaltene formale Notationen für deren entschlüsselung ich wieder ein Buch brauche.

Kann mir vorstellen, dass es viele gibt die daran interessiert wären.


Danke im Vorraus. :)

Hallo,

ich weiss jetzt keine Quelle, die du dir angucken kannst aber ich kann ja mal strukturelle Induktion mit meinen Worten erklaeren. Ich finde im uebrigen Strukturelle Induktion noch etwas einfacher zu verstehen als vollstaendige Induktion.

Strukturelle Induktion benutzt man um Beweise ueber irgendwelchen Strukturen zu fuehren, die induktiv definiert sind.

Die Aussagenlogik ist beispielsweise folgendermassen definiert

Eine Atomare Aussage A ist eine Aussagenlogische Formel

Jetzt kommt das Induktive

Die Negation einer Aussagenlogischen Formel F ist eine Aussagenlogische Formel: not(F)
Zwei Aussagenlogische Formeln, die mit einem der Junktoren (AND, OR, …, je nach definition) verknuepft sind, sind Aussagenlogische Formeln.. also z. B. F AND G

So kann man sich dann eine Formel zusammenbauen
z. B. gilt A, B sind atomare Formeln, dann sind sie auch aussagenlogische Formeln
demnach ist auch not(A)
zwei formeln mit einem junktor verknuepft sind formeln also auch
not(A) OR B
und das kann man immer weiter fuehren… so sind alle aussagenlogischen Formeln definiert


Fuer die Strukturelle Induktion macht maan sich das jetzt zu nutze. Man beweist eine bestimmte eigenschaft fuer atomare Aussagen. Und dann beweist man, dass die Eigenschaft fuer die Negation und die Verkuepfung zweier Aussagen gilt. Dabei benutzt man dann, dass man das fuer atomare Aussagen bewiesen hat.


also wenn man zum Beispiel grad(F) >= tiefe(F) (Klassiker) beweisen soll

Anfang:
Beweis das es fuer atomare aussagen gilt: gilt nach definition der beiden

Annahme:
F sei eine Formel fuer die grad(F) >= tiefe(F) gilt und G sei eine Formel fuer die grad(G) >= tiefe(G) gilt.

Schritt:
Nun benutzt man die Annahme. Man geht davon aus, dass fuer beliebige Formeln F und G die Eigenschaft gilt. Man hat zwar erst bewiesen, dass es fuer atomare Formeln gilt aber wenn man mit dem Induktionsschrit beweisen kann, dass fuer beliebige Formeln F fuer die grad(F) >= tiefe(F) und grad(G) >= tiefe(G) auch grad(F JUNKTOR G) >= tiefe(F JUNKTOR G) und grad(not(F)) >= tiefe(not(F)) gilt, dann kann man ja sich mit Hilfe des Anfangs beliebiggrosse Formeln zusammenbauen fuer die das gilt (nach der Induktiven Definition).
Die Eigenschaft gilt also fuer A (atomar). und nach dem Induktionsschritt gilt sie dann auch fuer not(A). Die Eigenschaft gilt fuer B (atomar). Nach Induktionsschritt gilt die Eigenschaft dann also auch fuer not(A) AND B u.s.w. Da so die Formeln definiert sind hat man diese Eigenschaft also fuer alle Formeln bewiesen.

Im Schritt wuerde man dann folgendes zeigen

grad(F) >= tiefe(F) gilt nach Annahme, also gilt auch grad(not(F)) >= tiefe(not(F)), weil ja nach definition grad(not(F)) = grad(F) + 1 und tiefe(not(F)) = tiefe(F) + 1. setzt man das links ein sieht man, dass die Eigenschaft fuer die negation schonmal gilt.

grad(F) >= tiefe(F) gilt nach Annahme (und bei G auch), dass heisst im schlimmsten Fall sind grad und tiefe von f bzw. gleich. Wenn man damit rechnet hat man es auf jeden fall auch fuer die Faelle gezeigt, bei denen tiefe(f) kleiner ist als grad(F). Also ist auch grad(F JUNKTOR G) >= tiefe(F JUNKTOR G), weil nach definition grad(F JUNKTOR G) = grad(F) + grad(G) + 1 und tiefe(F JUNKTOR G) = max(tiefe(F), tiefe(G)) + 1. da grad(F) + grad(G) + 1 >= max(tiefe(F), tiefe(G)) + 1, weil man weiss, dass tiefe nicht goesser sein kann als grad und weil man weiss, dass grad niemals negativ wird. Daher ist die Summe immer mindestens so gross wie das maximum der beiden Zahlen.



Ich hoffe das hilft beim Verstehen.

Bei der vollstaendingen Induktion macht man das im Prinzip aehnlich, nur dass man dort die Induktive Definition der natuerlichen Zahlen benutzt (0 ist natuerliche Zahl und der nachfolger einer natuerlichen Zahl ist eine natuerliche Zahl).

Doodles

Dankeschön, das ist echt lieb von dir!


Kann nicht sagen, dass ich es jetzt nach einmal Durchlesen komplett verstanden habe, aber einige Sachen die ich vorher überhaupt nicht durchdringen konnte sind mir jetzt etwas klarer geworden.

Danke nochmal! Werde das noch einpaar mal lesen und vielleicht mal probieren dasselbe ohne deine Anleitung zu beweisen. Das wird am besten sein.

Wollte nur mal sagen, dass ich die Induktion nun mehr oder weniger beherrsche!

:D :D :D

Ich hatte immer schon Probleme mit der vollständigen Induktion

Wäre vllcht sogar bereit mir ein Buch zu besorgen, gibt es da Tipps?

Im Buch "Abenteuer Mathematik" von Pierre Basieux wird die vollständige Induktion auf Seite 54 ff. behandelt ("Endlicher Beweis unendlich vieler Aussagen"). Ich besitze das Buch seit etwa 10 Jahren und schaue immer gerne mal wieder rein. Hauptsächlich Fließtext mit ein paar Formeln.

Alleine das Inhaltsverzeichnis ist schon sehr cool: Fängt bei -1 an und endet bei unendlich [28]

EDIT: Gibt's bei amazon gebraucht für 1 Cent, zusätzlich 3,00 Euro Versandkosten.