Ja, herzlich willkommen zur zweiten Sitzung von Grundlagen der Logik in der Informatik.

Die heutige Sitzung ist gewidmet dem Thema Induktion. Unter anderem deswegen,

weil das eben ein Thema ist, das erfahrungsgemäß mittlere bis einigermaßen große Schwierigkeiten

verursacht. Deswegen machen wir das gleich am Anfang und machen dafür eine ganze Sitzung.

Eine Art von Induktion werden vermutlich viele von Ihnen kennen. Induktion auf natürlichen

Zahlen. Wem ist das geläufig, nun mal so stichprobenartig? Wem nicht? Es sind eine ganze Menge,

weiß nichts. Wie viele da haben sich jetzt enthalten? Okay, es enthalten sich also etliche

auch noch von der Enthaltung. Na gut, also wiederholen wir es einfach mal.

Also nehmen wir mal her eine Aussage über natürliche Zahlen. Wir nennen sie P. Also P ist eine

Aussage über eine einzelne natürliche Zahl N. So, wenn ich jetzt die folgenden beiden Dinge

hinbekomme. Wenn erstens P für Null gilt, also wenn ich hinbekomme zu zeigen, dass P für Null

gilt. Das nennt man typischerweise den Induktionsanfang. Und zweitens,

wenn für alle natürlichen Zahlen folgendes gilt, das ist jetzt grammatikalisch schlecht,

weil ich schon für alle gesagt habe. Ich möchte irgendwas zwischen diese beiden Aussagen hier

packen, insofern sehen sie immer nach, dass ich hier redundant bin. Also wenn für alle natürlichen

Zahlen aus P von N stets Pn plus 1 folgt, das liest sich ja also unter der Annahme,

dass Pn gilt. Muss ich zeigen, dass Pn plus 1 gilt. Dieser Teil heißt der Induktionsschritt,

weil ich einen Schritt mache von N auf N plus 1. Ich nehme die Behauptung an für N und zeige

sie dann für N plus 1. Wenn das beides der Fall ist, dann gilt P für alle natürlichen

Zahlen schlechthin. In Formel für alle Np von N. Man beachte also hier die Formulierung

eines sogenannten Induktionsprinzips. Das ist das ganze Ding hier. Also diese ganzen

vier Zeilen zusammen, die heißen ein Induktionsprinzip. Das Induktionsprinzip besteht also darin,

dass es mir sagt, erstens, was erlaubt es mir zu zeigen? Es erlaubt mir in diesem Falle

zu zeigen, dass eine Aussage für alle natürlichen Zahlen gilt. Und zweitens, was muss ich dafür

machen? Nun, ich muss den Induktionsanfang hinkriegen. Ich muss zeigen, dass P von 0

gilt. Und zweitens, ich muss den Induktionsschritt durchführen. Ich muss zeigen, dass P von N

plus 1 aus P von N folgt. So, das ist jetzt einmal hoffentlich hinreichend exakt aufgeschrieben

das übliche Prinzip der Induktion über natürliche Zahlen. So, ich bin jetzt gnadenlos. Wir

schreiben das nicht nur nochmal an, sondern ich mache das auch gleich nochmal an einem

Beispiel. Das ist sehr zen hier irgendwie. So.

So, ein Beispiel, das Sie vermutlich, wenn Sie Induktion überhaupt kennen, auch schon

konkreter kennen, nämlich, nämlich mal ein Beispiel einer konkreten Eigenschaft T von

N, die ich jetzt für alle natürlichen Zahlen N beweisen möchte. Nämlich, ja, so eine

typische Dreieckseigenschaft, das sagt was aus über die Summe der ersten N ungeraden

Zahlen. Also, ich fange hier an bei i gleich 1 zu summieren. Da habe ich also 2 mal 1 minus

1. Da fange ich bei 1 an und summiere bis i gleich N. So, die ersten N ungeraden Zahlen

summiere ich da und ich behaupte, da kommt raus die Nte Quadratzahl, N Quadrat. So. Wie

vielen kommt das bekannt vor? Ja, immer noch relativ viele. Eines der ganz typischen Beispiele,

die man halt nimmt. So, das Induktionsprinzip sagt mir, um das jetzt für alle natürlichen

Zahlen zu beweisen, muss ich zwei Dinge tun. Erstens Induktionsanfang. Induktionsanfang

kürze ich in Zukunft, wenn es dann mal wieder vorkommt, mit i a ab. So. Also, was muss ich

machen? Ich muss zeigen, diese Aussage gilt für Null. Also, zu zeigen ist P von Null.

Das heißt, ja, ich habe jetzt ganz mechanisch nichts zu tun, als hier überall für N Null

einzusetzen. Also, ich muss zeigen, dass wenn ich die ersten Null ungeraden Zahlen summiere,

dann N Quadrat rauskommt. Nun gut, das hake ich mal ab. N Null Zahlen summieren, gibt

per Konvention die Null. Null Quadrat ist natürlich auch Null. Okay, fine. So, und den Induktionsschritt,

den kürzen wir ab jetzt mit i s ab. So, das ist der, der erfahrungsgemäß nicht so ein

bisschen Knoten im Gehirn verursacht. Also, was müssen wir tun? Wir müssen eine Implikation

herleiten. Ja, wir müssen zeigen, dass eine Sache aus einer anderen folgt. Dazu nehmen

wir das, worauf es folgen soll an. Ja. Und dafür gibt es ein magisches Wort. Das magische