Im vorherigen Abschnitt haben wir gesehen, wie der Aufbau komplexer Formeln aus einfache(re)n Formeln genutzt werden kann, um Funktionen über die Formelmenge zu definieren. Ähnlich kann man den Aufbau der Formeln nun nutzen, um Eigenschaften von Formeln nachzuweisen. Dies wird als strukturelle Induktion bezeichnet.
Sei für jede Formel \(F \in \mathcal{L}_{AL}\) dazu \(B(F)\) eine Behauptung zu \(F\) (z.B. die Behauptung, dass die Länge von \(F\) stets größer ist als die Anzahl der Operatoren in \(F\)). Wollen wir nun \(B(F)\) für alle Formeln der Aussagenlogik zeigen, so kann dies mittels struktureller Induktion gelingen.
1. Zeigt man, dass \(B(F)\) für jede atomare Formel \(F\) gilt (Induktionsanfang).
2. Nimmt man an, dass \(B(F)\) und \(B(G)\) für zwei Formeln \(F\) und \(G\) gelten (Induktionsannahme).
3. Zeigt man, dass unter der Annahme bei 2. nun auch \(B(\neg F), B(F \vee G), B(F \wedge G), B(F \Rightarrow G)\) und \(B(F \Leftrightarrow G)\) gelten (Induktionsschritt).
Wir wollen zeigen, dass die Anzahl der Junktoren einer Formel begrenzt ist durch die Länge der Formel oder symbolisch: Für jede Formel \(F \in \mathcal{L}_{AL}\) gilt \(grad(F) \leq L(F)\) (dies ist die Behauptung, also obiges \(B(F)\)). Der Grad einer Formel ist im obigen Abschnitt zur strukturellen Rekursion definiert. Die Länge findet sich in dem dortigen Fragen-Abschnitt.
Wir wollen noch kurz darauf eingehen, warum die strukturelle Induktion nützlich ist. An diesem Beispiel lässt sich das nämlich vermutlich nicht so gut erkennen, denn dass die Länge einer Formel stets mindestens so groß ist, wie die Anzahl der Junktoren (die ja auch stets zur Länge beitragen) glaubt man wohl auch ohne Beweis recht schnell. (Man sollte allerdings auch Dinge, die man meint zu sehen, ruhig beweisen. Bisweilen sind sie dann doch nicht so offensichtlich.)
Warum also ist die strukturelle Induktion nützlich? Mit ihr lassen sich quasi nach einem vorgegebenen Schema Behauptungen für alle aussagenlogischen Formeln beweisen. Im Schema muss man zwar noch Lücken füllen (was manchmal recht schwierig ist), aber das Schema gibt einem dennoch eine gute Hilfe. Die strukturelle Induktion ist also quasi ein Beweiswerkzeug oder -schema. Spätere, kompliziertere Behauptungen lassen sich mit ihr gut beweisen. Außerdem lässt sich die strukturelle Induktion auch bei anderen Logiken (oder allgemein bei anderen Strukturen) einführen und ist dort hilfreich. Die strukturelle Induktion dient uns also als Beweisschema und auch wenn wir hier noch keine sinnvollen Beispiele für ihre Anwendung sehen, so gibt es zwei gute Gründe sie hier einzuführen und zu verstehen: 1. Kann sie später für den Beweis komplizierterer Behauptungen genutzt werden und 2. Kann sie später bei anderen Logiken definiert und eingesetzt werden.
Satz 2.3.1
Für jede aussagenlogische Formel \(F\) gilt \(grad(F) \leq L(F)\).Beweis
Wir führen den Beweis mittels struktureller Induktion. Wir gehen zunächst recht ausführlich erklärend vor. Eine kurze Version des Beweises findet sich im Anschluss.
Induktionsanfang. Im Induktionsanfang ist zu zeigen, dass die Aussage für alle atomaren Formeln gilt. Sei also \(A\) ein beliebiges Aussagensymbol (also eine atomare Formel). Da wir \(A\) beliebig wählen, gilt die Behauptung dann, sollten wir sie für \(A\) beweisen können, für alle Aussagensymbole. Betrachten wir nun zuerst was der Grad von \(A\) und die Länge von \(A\) ist, also \(grad(A)\) und \(L(A)\). Nach Definition von \(grad\) ist \(grad(A) = 0\) und nach Definition von \(L\) ist \(L(A) = 1\), womit wir sofort \(grad(A) = 0 \leq 1 = L(A)\) haben. Mit dem Induktionsanfang sind wir nun bereits fertig. Wie eben gezeigt gilt die Aussage für \(A\) und da \(A\) beliebig gewählt war damit für alle Aussagensymbole.
Induktionsannahme. Gelte die Behauptung für zwei Formeln \(F\) und \(G\). So kann man die Induktionsannahme immer schreiben. Es hilft aber oft, sich noch einmal genau zu notieren, was denn nun gilt. Wir schreiben daher: Seien \(F\) und \(G\) Formeln für die die Behauptung gilt, d.h. mit \(grad(F) \leq L(F)\) und \(grad(G) \leq L(G)\).
Induktionsschritt. Wir betrachten nun zunächst \(\neg F\). Wir wollen \(grad(\neg F) \leq L(\neg F)\) zeigen. Betrachten wir zunächst \(grad(\neg F)\) nach Definition von \(grad\) ist \(grad(\neg F) = grad(F) + 1\). Für die Länge gilt nach Definition \(L(\neg F) = L(F) + 1\). Ferner wissen wir aus der Induktionsannahme \(grad(F) \leq L(F)\) (wir haben ja in der Induktionsannahme explizit angenommen, dass \(F\) eine Formel ist mit \(grad(F) \leq L(F)\), daher dürfen wir das jetzt auch benutzen!). Bauen wir dies alles zusammen, so erhalten wir \(grad(\neg F) = grad(F) + 1 \leq L(F) + 1 = L(\neg F)\), wobei die Ungleichung wegen der Induktionsannahme gilt, die beiden Gleichheitszeichen wegen der Definitionen von \(grad\) bzw. \(L\).
Nun betrachten wir \((F \vee G)\). Wir wollen \(grad((F \vee G)) \leq L((F \vee G))\) zeigen. Zunächst ist wegen der Definition von \(grad\) bzw. von \(L\) wieder \(grad((F \vee G)) = grad(F) + grad(G) + 1\) und \(L((F \vee G)) = L(F) + L(G) + 3\). Wegen der Induktionsannahme dürfen wir wieder \(grad(F) \leq L(F)\) und \(grad(G) \leq L(G)\) benutzen. Damit erhalten wir \(grad((F \vee G)) =\) \(grad(F) + grad(G) + 1 \leq\) \(L(F) + L(G) + 1 \leq L(F) + L(G) + 3 =\) \(L((F \vee G))\), wobei die erste \(\leq\)-Beziehung wegen der Induktionsannahme und die zweite einfach wegen \(1 \leq 3\) gilt. Die Gleichheiten gelten wegen der Definitionen von \(grad\) bzw. \(L\).
Die Fälle für \((F \wedge G)\), \((F \Rightarrow G)\) und \((F \Leftrightarrow G)\) zeigt man ganz analog. (Dort passiert tatsächlich überhaupt nichts anderes, da \(grad\) und \(L\) für alle zweistelligen Junktoren gleich definiert sind.)
Vielen, die zum ersten Mal mit der strukturellen Induktion in Berührung kommen, ist nicht klar, warum man die Aussage nun für alle Formeln bewiesen hat? Dies wird nachfolgend erklärt. Wem das klar ist (die Begrüundung ist ganz ähnlich wie bei der vollständigen Induktion), der kann den nachfolgenden Absatz überspringen. Im Anschluss kommt dann noch einmal der Beweis für obige Aussage in deutlich knapperer Form.
Zu Beginn zeigt man im Induktionsanfang die Aussage für alle atomaren Formeln. Für die gilt die Behauptung also schon einmal. Nun nimmt man in der Annahme an, dass \(F\) und \(G\) zwei Formeln sind, für die die Behauptung gilt. Ob es solche Formeln auch gibt, ist eigentlich ganz egal. Man könnte auch weitermachen, wenn es solche nicht gäbe, nur würde man dann nichts sinnvolles beweisen. Es gibt aber bereits Formeln für die wir wissen, dass die Aussage gilt: Die atomaren Formeln nämlich!
Hat man den Induktionsschritt bewiesen, dann weiß man, dass man Formeln für die die Behauptung gilt nun kombinieren kann. Da wir aus dem Induktionsanfang wissen, dass die Behauptung für die atomaren Formeln gilt, gilt sie dann auch für z.B. \((A \wedge B)\). Nun könnte man für das \(F\) aus der Annahme gerade diese Formel nehmen und so auch Schlussfolgern, dass die Behauptung für z.B. \(((A \wedge B) \Rightarrow C)\) gilt. So kann man immer weiter machen und alle Formeln der Aussagenlogik erhalten.
Anders kann man auch sagen, dass man gerade die Definition des Syntax nachbildet. Dort wird nämlich auch gesagt alle Aussagensymbole sind Formeln (für die zeigt man die Behauptung im Induktionsanfang) und dann wird in der Definition der Syntax gesagt wenn \(F\) und \(G\) Formeln sind (vgl. mit der Induktionsannahme!), dann sind auch \(\neg F\), \((F \wedge G)\) usw. Formeln (dies wird durch den Induktionsschritt abgedeckt).
Mit der strukturellen Induktion zeigt man eine Behauptung also tatsächlich für alle Formeln der Aussagenlogik.
Hat man etwas Übung, so geht man bei obigem knapper vor. Zur Illustration wollen wir dies hier einmal machen. Wir wollen \(grad(F) \leq L(F)\) für alle \(F \in \mathcal{L}_{AL}\) beweisen.
Beweis
Wir zeigen dies mittels struktureller Induktion. Der Induktionsanfang ist klar, denn für jedes Aussagensymbol \(A\) gilt \(grad(A) = 0 \leq 1 = L(A)\). Sei nun angenommen, dass \(F\) und \(G\) zwei Formeln sind mit \(grad(F) \leq L(F)\) und \(grad(G) \leq L(G)\). Im Induktionsschritt ergibt sich nun \(grad(\neg F) = grad(F) + 1 \leq L(F) + 1 = L(\neg F)\) und \(grad((F \circ G)) = grad(F) + grad(G) + 1 \leq L(F) + L(G) + 1 \leq L(F) + L(G) + 3 = L((F \circ G))\) für jeden zweistelligen Junktor \(\circ\).