WEBVTT 00:03.100 --> 00:05.710 Ja, schönen guten Tag nochmal von mir. 00:05.990 --> 00:09.010 Also machen wir weiter mit Grundbegriffe der Informatik. 00:09.750 --> 00:12.250 Und das erste ist, dass wir jetzt noch dieses Kapitel über 00:12.250 --> 00:14.210 Aussagenlogik fertig machen. 00:15.370 --> 00:20.890 Und danach kommen wir zu einem ganz, ganz wichtigen Beweisprinzip, das 00:20.890 --> 00:24.630 Sie vielleicht, wahrscheinlich zum Teil schon in der Schule gesehen 00:24.630 --> 00:26.390 haben, vollständige Induktion. 00:29.850 --> 00:37.810 Ja, wir hatten das letzte Mal also erstens definiert, was sind 00:37.810 --> 00:39.410 aussagenlogische Formeln. 00:41.730 --> 00:47.510 Da unten, also das ganz unten ist natürlich keine aussagenlogische 00:47.510 --> 00:54.110 Formel, aber das, wo drüber steht sinnvolles Beispiel, ist ein 00:54.110 --> 00:55.010 sinnvolles Beispiel. 00:58.870 --> 01:01.730 Also wir haben Aussagevariablen, da schreiben wir irgendwelche 01:01.730 --> 01:05.510 Großbuchstaben aus der hinteren Hälfte des Alphabets, meistens so pqr 01:05.510 --> 01:07.470 oder p1, p2, p3, p... 01:07.470 --> 01:09.110 Ich weiß nicht, wie viel, wenn man viele braucht. 01:10.470 --> 01:15.390 Und die darf man dann halbwegs plausibel zusammensetzen mit Hilfe... 01:15.390 --> 01:18.690 Zum einen darf man vor eine Formel, die man schon hat, so ein 01:18.690 --> 01:21.390 Negationszeichen schreiben und dann immer noch schön Klammern 01:21.390 --> 01:21.930 außenrum. 01:21.930 --> 01:26.250 Oder man nimmt zwei Formeln und schreibt so ein kleines Dach, das ist 01:26.250 --> 01:29.690 das Zeichen für das logische und oder das umgedrehte für das logische 01:29.690 --> 01:32.830 oder oder so ein Pfeil für die Implikation dazwischen. 01:35.110 --> 01:38.490 Und dann hat man festgelegt, was sind Formeln, aber man hat noch 01:38.490 --> 01:40.210 überhaupt nicht festgelegt, was soll das alles. 01:41.470 --> 01:45.710 Und worauf man hinaus will, ist, dass jede Formel eine boolische 01:45.710 --> 01:49.870 Funktion beschreibt, das ist also eine Abbildung... 01:52.030 --> 01:55.910 Da stecke ich als Argumente ein oder mehr an Wahrheitswerte rein, also 01:55.910 --> 01:59.310 der Grundbereich ist irgendwie die Menge, die wahr und falsch, true 01:59.310 --> 02:01.870 und false und wie auch immer Sie das nennen wollen, enthält. 02:03.850 --> 02:09.370 Und boolische Funktionen nehmen also solche Argumente und liefern als 02:09.370 --> 02:11.730 Funktionswert auch wieder so einen Wahrheitswert. 02:13.370 --> 02:15.890 Und da hatten wir uns so ein bisschen was angeguckt. 02:16.870 --> 02:21.330 Das Wichtigste ist vielleicht aus diesem Bereich, dass Sie sich bitte 02:21.330 --> 02:25.710 daran erinnern oder nochmal klarmachen, wir haben dann hier so eine 02:25.710 --> 02:31.730 boolische Funktion für die Implikation sozusagen und das ist einfach 02:31.730 --> 02:34.970 die Definition von wann ist eine Implikation wahr. 02:37.610 --> 02:45.590 Nämlich genau dann, wenn x-Pfeil y sozusagen ist wahr, wenn x falsch 02:45.590 --> 02:48.790 ist oder y wahr. 02:48.950 --> 02:51.730 Also das ist nichts anderes, wenn Sie hier die Tabellen, die Spalten 02:51.730 --> 02:54.950 vergleichen, das ist nichts anderes wie nicht x oder y. 02:55.230 --> 02:59.710 Das ist die Definition dann von Implikation, also hier der boolischen 02:59.710 --> 03:00.990 Implikationsfunktion. 03:04.970 --> 03:08.050 Also auch boolische Funktionen und was man jetzt machen will, ist zu 03:08.050 --> 03:16.110 sagen, jede aussagenlogische Formel hat eine Bedeutung und die 03:16.110 --> 03:17.890 Bedeutung ist so eine boolische Funktion. 03:22.130 --> 03:28.610 Zu diesem Zwecke, also wir haben immer zugrunde liegend eine Menge von 03:28.610 --> 03:34.290 Aussagevariablen und dann als erstes, was ganz nützlich ist, ein 03:34.290 --> 03:38.330 Begriff, den man ständig benutzen will und deswegen führt man ihn ein, 03:38.950 --> 03:42.650 im alltäglichen Leben, auch bei Ihnen, wenn Sie irgendwas Größeres mal 03:42.650 --> 03:44.810 beweisen oder aufschreiben, werden Sie merken an irgendwelchen 03:44.810 --> 03:47.610 Stellen, jetzt schreibe ich zum dritten, vierten, fünften Mal 03:47.610 --> 03:51.890 irgendetwas Längeres, diesem Ding sollte ich vielleicht einen Namen 03:51.890 --> 03:54.830 geben, damit ich bequemer reden kann, kompakter. 03:56.110 --> 03:59.690 Und das ist hier so ein Fall und wir warten nicht darauf, dass wir 03:59.690 --> 04:01.930 merken, dass wir immer wieder über das Gleiche reden, sondern ich sage 04:01.930 --> 04:05.130 Ihnen gleich, was man brauchen kann, sind sogenannte Interpretationen, 04:05.650 --> 04:06.770 das sind einfach Abbildungen. 04:06.850 --> 04:09.890 Eine Interpretation ist eine Abbildung, die legt einfach für jede 04:09.890 --> 04:13.990 Aussagevariable einen Wahrheitswert fest, also P ist wahr, Q ist 04:13.990 --> 04:17.050 falsch, R ist falsch, S ist wahr oder so etwas. 04:17.990 --> 04:23.710 Und jede solche Abbildung oder wenn Sie P1, P2, P3 haben, jede solche 04:23.710 --> 04:27.650 Abbildung legt eben für jede Aussagevariable, die Sie gerade 04:27.650 --> 04:30.390 interessiert, das sind immer typischerweise nur endlich viele, weil 04:30.390 --> 04:33.290 jede Formel endlich ist, da können nur endlich viele Aussagevariablen 04:33.290 --> 04:37.250 auftauchen, legt für jede Variable fest, was soll Ihr Wahrheitswert 04:37.250 --> 04:37.590 sein. 04:38.150 --> 04:42.370 Also wenn Sie hier so für jede Aussagevariable eine Spalte machen, 04:44.810 --> 04:48.550 dann steht hier in jeder Zeile eine Interpretation der drei 04:48.550 --> 04:52.850 Aussagevariablen, P1, P2, P3 und das sind hier acht Zeilen für alle 04:52.850 --> 04:53.770 acht Möglichkeiten. 04:54.630 --> 04:57.550 Zwei Möglichkeiten für die erste, mal zwei Möglichkeiten für die 04:57.550 --> 05:00.210 zweite, mal zwei Möglichkeiten für die dritte Aussagevariable. 05:02.270 --> 05:05.830 Also eine Interpretation legt für jede Aussagevariable einen 05:05.830 --> 05:06.590 Wahrheitswert fest. 05:07.930 --> 05:11.030 Und ich weiß gar nicht, ob wir das schon irgendwo brauchen, aber für 05:11.030 --> 05:16.270 die Menge aller Abbildungen von V nach B, zum Beispiel schreibe ich B 05:16.270 --> 05:19.510 hoch V, nur mal so am Rande, falls das irgendwo auftaucht, ich glaube 05:19.510 --> 05:19.930 noch nicht. 05:20.250 --> 05:22.830 Wir reden da später nochmal in einem späteren Kapitel ausführlich 05:22.830 --> 05:23.110 drüber. 05:23.690 --> 05:26.510 Also der Punkt ist, jede Aussagevariable kriegt einen Wahrheitswert. 05:27.550 --> 05:30.890 So, und jetzt aussagenlogische Formeln, wie waren die definiert? 05:31.210 --> 05:34.430 Also da gab es erstens den Fall, dass man gesagt hat, eine einzelne 05:34.430 --> 05:38.190 Aussagevariable ist schon eine aussagenlogische Formel. 05:38.310 --> 05:40.410 Wenn Sie einfach P hinschreiben, dann ist das schon eine 05:40.410 --> 05:41.430 aussagenlogische Formel. 05:42.190 --> 05:46.590 Das sind die einfachsten und die komplizierteren sind so mithilfe von 05:46.590 --> 05:49.730 Konnektiven aus kleineren zusammengesetzt. 05:51.550 --> 05:55.090 Und für einzelne Aussagevariable, wenn man eine Interpretation hat, 05:55.150 --> 05:56.750 weiß man, sie ist wahr oder falsch. 05:57.430 --> 06:00.630 Die Interpretation sagt einem das, die sagt einem das ja für jede 06:00.630 --> 06:01.510 Aussagevariable. 06:02.810 --> 06:05.410 Und jetzt muss man das irgendwie hochziehen und sagen, ja, wenn die 06:05.410 --> 06:08.730 Formel komplizierter ist und aus einfacheren Teilen zusammengesetzt, 06:09.450 --> 06:12.650 wie setze ich denn dann aus den Wahrheitswerten für die einzelnen 06:12.650 --> 06:16.370 Teile, wie berechne ich daraus den Wahrheitswert für die ganze Formel? 06:19.270 --> 06:22.490 Also erstmal, man stellt sich auf den Standpunkt, das geht, wie 06:22.490 --> 06:27.410 gesagt, die Wahrheit einer Aussage soll nur abhängen von den 06:27.410 --> 06:31.310 Wahrheitswerten der Teilaussagen und von nichts anderem. 06:32.430 --> 06:33.730 Und wie zieht man das jetzt hoch? 06:33.850 --> 06:38.610 Na ja, also wir wollen jetzt für jede Aussagenlogische Formel groß F 06:38.610 --> 06:44.370 definieren, was kommt daraus, wenn ich die auswerte und zugrunde lege 06:44.370 --> 06:46.110 eine bestimmte Interpretation I. 06:46.890 --> 06:49.910 Also wenn Sie irgendeine Interpretation I haben, dann die Abbildung 06:49.910 --> 06:55.610 Wall und ein I, soll für jede Formel sagen, ist die jetzt wahr oder 06:55.610 --> 06:56.010 falsch. 06:57.190 --> 07:01.310 Und dann muss man also Wall I von F für jede Möglichkeit, was F sein 07:01.310 --> 07:02.390 kann, irgendwie definieren. 07:03.650 --> 07:06.890 Und die Definition für die Formeln war, man nimmt Aussagevariablen 07:06.890 --> 07:09.190 oder setzt das aus kleineren Dingen zusammen. 07:09.910 --> 07:14.250 Und analog hangelt sich jetzt die Definition von, was ist Wall I von F 07:14.250 --> 07:15.230 auch hoch. 07:16.250 --> 07:19.350 Und man fängt also an, bei einer einzelnen Aussagevariable, also wenn 07:19.350 --> 07:23.510 Groß X jetzt hier irgendeine Aussagevariable ist, dann was bedeutet 07:23.510 --> 07:24.910 es, X auszuwerten? 07:25.230 --> 07:28.090 Na ja, man schaut einfach in der Interpretation nach, welchen 07:28.090 --> 07:33.210 Wahrheitswert, welcher Wahrheitswert wird in der Interpretation für 07:33.210 --> 07:35.130 die Aussagevariable X vorgegeben. 07:35.950 --> 07:40.110 Also für jedes X soll die Auswertung von X einfach der Wert in der 07:40.110 --> 07:41.090 Interpretation sein. 07:41.950 --> 07:46.150 Was soll es bedeuten, die Negation einer Formel auszuwerten? 07:46.850 --> 07:50.310 Na ja, da wertet man erstmal die Originalformel aus und dann negiert 07:50.310 --> 07:51.270 man den Wahrheitswert. 07:53.090 --> 07:56.890 Was bedeutet es, eine Formel der Formel G und H auszuwerten? 07:56.950 --> 08:00.950 Da wertet man erstmal G und H aus und dann wendet man die Buhl'sche 08:00.950 --> 08:02.550 Funktion für das logische UND aus. 08:03.090 --> 08:08.510 Mit der Konsequenz, G und H ist genau dann wahr, wenn sowohl G wahr 08:08.510 --> 08:13.590 ist zu wahr ausgewertet wird bei der Interpretation als auch H. 08:14.490 --> 08:19.730 Und G oder H ist wahr, wenn mindestens eine der Formeln G oder H wahr 08:19.730 --> 08:20.090 ist. 08:20.770 --> 08:26.270 Und die Implikation G-Pfeil H ist wahr genau dann, wenn die Buhl'sche 08:26.270 --> 08:31.610 Funktion, die wir da gerade hatten für den Pfeil, eben wahr liefert 08:31.610 --> 08:36.470 und das heißt, G muss zu falsch ausgewertet werden oder H zu wahr. 08:36.810 --> 08:37.410 Oder beides. 08:39.690 --> 08:42.850 Und ich hatte ja das letzte Mal schon gesagt, dass statt dieser 08:42.850 --> 08:48.270 Buhl'schen Funktionen hier B unten Dach, B unten irgendwas, manche 08:48.270 --> 08:51.030 Leute schreiben dann auch einfach eben für die Buhl'sche Funktion auch 08:51.030 --> 08:54.250 wieder in Fixnotationen so ein UND oder ein ODER oder NICHT. 08:55.130 --> 09:01.430 Und dann sieht die Definition von dieser, was ist aus Wall I einer 09:01.430 --> 09:04.270 Formel F noch viel plausibler aus sozusagen. 09:04.430 --> 09:08.970 Auswertung von G und H ist Auswertung von G, Buhl'sche Funktion und 09:08.970 --> 09:09.910 Auswertung von H. 09:10.170 --> 09:13.530 Und genauso für das ODER und sozusagen analog für das NICHT. 09:14.090 --> 09:18.170 Also in Anführungszeichen, ja man zieht das Auswerten einfach zu den 09:18.170 --> 09:19.210 Teilformeln rein. 09:20.290 --> 09:23.510 Aber bitte dann, wenn Sie es reingezogen haben, hier auf der rechten 09:23.510 --> 09:26.770 Seite das DACH, das ODER, das NICHT, das sind jetzt nicht mehr die 09:26.770 --> 09:30.410 Symbole aus aussagenlogischen Formeln, sondern das sind diese 09:30.410 --> 09:32.110 Buhl'schen Funktionen. 09:32.910 --> 09:35.770 Und für Implikationen gibt es keine gängige Schreibweise, deswegen 09:35.770 --> 09:37.250 habe ich da nicht nochmal was hingeschrieben. 09:39.350 --> 09:42.650 Und da kann man sich jetzt hier natürlich auch wieder fragen, das 09:42.650 --> 09:44.790 werden wir jetzt an der Stelle aber noch nicht ausführlich 09:44.790 --> 09:49.310 diskutieren, warum ist das denn wirklich so, dass jetzt tatsächlich 09:49.310 --> 09:54.330 aufgrund dieser fünf Gleichungen, die da auf der linken Seite hier 09:54.330 --> 09:59.790 stehen, wirklich erstens für jede Formel ein Wahrheitswert festgelegt 09:59.790 --> 10:03.910 wird und zweitens für keine Formel, wo möglich auf unterschiedlichen 10:03.910 --> 10:07.530 Wegen verschiedene Wahrheitswerte festgelegt werden, dass das Ganze 10:07.530 --> 10:09.490 widersprüchlich wäre, das will man natürlich auch nicht. 10:09.830 --> 10:13.050 Also man will, dass für alle Fälle was festgelegt wird und dass es 10:13.050 --> 10:14.630 immer eindeutig ist, was rauskommt. 10:14.630 --> 10:15.490 So. 10:17.370 --> 10:17.890 Gut. 10:20.710 --> 10:23.650 Ganz einfaches Beispiel, einfach, dass Sie sehen, dass das alles 10:23.650 --> 10:25.050 anscheinend irgendwie sinnvoll ist. 10:25.410 --> 10:29.110 Nehmen Sie an, wir haben eine Interpretation, wo P denn wahr ist und Q 10:29.110 --> 10:33.990 falsch und wir fragen uns jetzt, was kommt raus, wenn ich die Formel 10:33.990 --> 10:35.990 nicht P und Q auswerte? 10:36.170 --> 10:41.910 Also was ist der Fall I von G für diese Formel G hier, nicht P und Q? 10:42.610 --> 10:45.630 Und da muss man, das ist jetzt wirklich eine Stelle, da muss man 10:45.630 --> 10:47.470 sozusagen gar nicht groß nachdenken. 10:50.350 --> 10:54.190 Manchmal mit Nachdenken kann man irgendwelche Dinge vereinfachen, 10:54.270 --> 10:59.050 abkürzen, das ist nicht verboten, aber hier können wir es nicht, 10:59.110 --> 10:59.710 brauchen wir es nicht. 11:00.070 --> 11:02.250 Was ist Auswertung von nicht P und Q? 11:02.750 --> 11:06.150 Die Definition sagt, wenn das im Großen und Ganzen der Formel ist von 11:06.150 --> 11:11.130 der Bauart Negation von irgendetwas, dann werte man erst mal das 11:11.130 --> 11:14.910 Irgendetwas aus, was hinterher noch negiert wird und darauf wende man 11:14.910 --> 11:16.610 die Negationsfunktion an. 11:17.270 --> 11:21.150 Und dann müssen Sie hier drin P und Q, diese Formel P und Q auswerten, 11:21.250 --> 11:25.210 die Definition sagt, da wertet man erst mal P und Q aus und wendet 11:25.210 --> 11:27.210 dann die Buhlschuhfunktion fürs logische Und an. 11:28.290 --> 11:32.130 Und dann steht hier, man werte P beziehungsweise Q aus, was heißt das? 11:32.390 --> 11:35.530 Laut Definition einfach nachgucken, was die Interpretation 11:35.530 --> 11:36.190 vorschreibt. 11:37.610 --> 11:41.530 Also für einzelne Aussagevariable, das ist die Interpretation von P 11:41.530 --> 11:44.010 und der Wert von Q ist die Interpretation von Q. 11:44.550 --> 11:48.170 Und dann können Sie hier einfach einsetzen, P ist wahr, Q ist falsch 11:48.170 --> 11:52.610 und logisches Und von wahr und falsch ist falsch und Negation von 11:52.610 --> 11:53.250 falsch ist wahr. 11:53.950 --> 11:54.370 Fertig. 11:55.050 --> 11:55.730 Das ist alles. 11:56.690 --> 12:00.630 Und auf diese Art und Weise, das klappt immer, für jede 12:00.630 --> 12:03.650 Interpretation, für jede Formel können Sie im Prinzip so rechnen, wenn 12:03.650 --> 12:07.050 Sie hinreichend geduldig sind und am Ende kommt wahr oder falsch raus. 12:08.750 --> 12:12.630 Und da haben wir jetzt also gegeben eine Interpretation, immer 12:12.630 --> 12:16.370 festgelegt, für diese Interpretation irgendeine Formel, was ist der 12:16.370 --> 12:17.450 Wahrheitswert insgesamt. 12:19.710 --> 12:21.950 Achso, und hier ist dann nochmal das Gleiche hingeschrieben, aber 12:21.950 --> 12:24.650 nicht mit diesen komischen burschen Funktionen, sondern so, wie man es 12:24.650 --> 12:25.830 dann üblicherweise macht. 12:28.130 --> 12:32.170 Also Negation von Wahl P und Q, das ist Wahl P, logisches Und, Wahl Q, 12:32.410 --> 12:35.570 das ist I von P und I von Q, wahr und falsch, falsch nicht, falsch ist 12:35.570 --> 12:35.790 wahr. 12:37.610 --> 12:37.890 Gut. 12:41.850 --> 12:46.210 Und dann kommt man manchmal in die Situation, zum Beispiel auf der 12:46.210 --> 12:48.950 nächsten oder übernächsten Folie, da will man eine Formel nicht nur 12:48.950 --> 12:51.550 für eine Interpretation auswerten, sondern für alle. 12:54.130 --> 12:56.990 Na ja, dann macht man das im Prinzip genauso. 12:57.990 --> 13:01.310 Da fängt man an, also man schreibt sich dann erstmal in so einer 13:01.310 --> 13:04.970 Tabelle Spalten hin für alle Aussagen, Variablen, die vorkommen. 13:05.450 --> 13:09.050 Also meinetwegen bei unserer Formel nicht P und Q, eben eine Spalte 13:09.050 --> 13:12.390 für P, eine Spalte für Q und schreibt dann darunter alle 13:12.390 --> 13:14.510 Interpretationen, die überhaupt möglich sind. 13:14.850 --> 13:18.950 Beide falsch, nur die P falsch, nur Q falsch, beide wahr. 13:20.530 --> 13:24.790 Und dann hangelt man sich so langsam hoch, so wie die Formel aufgebaut 13:24.790 --> 13:32.350 ist und wertet irgendwelche Dinge aus, zum Beispiel hier in der 13:32.350 --> 13:35.730 vorletzten Spalte ignorieren Sie jetzt mal die Spalten 3, 4 und 5 für 13:35.730 --> 13:36.190 den Moment. 13:37.150 --> 13:42.090 P und Q, können Sie jetzt für jede Interpretation von P und Q hier 13:42.090 --> 13:45.130 vorne, stehen die alle, können Sie mal hinschreiben, was gibt jetzt 13:45.130 --> 13:46.690 die Auswertung von P und Q. 13:46.870 --> 13:50.610 Also erste Zeile falsch und falsch gibt falsch, zweite Zeile falsch 13:50.610 --> 13:53.570 und wahr gibt falsch, dritte Zeile wahr und falsch gibt falsch, wahr 13:53.570 --> 13:54.250 und wahr gibt wahr. 13:56.010 --> 13:59.190 Und dann die Negation davon, da müssen Sie diese Werte hier alle noch 13:59.190 --> 14:00.730 umkippen, wahr, wahr, wahr, falsch. 14:02.770 --> 14:05.810 Und jetzt habe ich hier spaßhalber nochmal Spalten hingeschrieben für 14:05.810 --> 14:08.970 nicht P und nicht Q, die kriegt man ganz leicht, Sie nehmen die Spalte 14:08.970 --> 14:12.070 für W, drehen alles um, Sie nehmen die Spalte für Q, drehen alles um 14:12.070 --> 14:18.010 und dann das oder von nicht P und nicht Q und dann war oder war ist 14:18.010 --> 14:21.030 wahr, war oder falsch ist wahr, falsch oder war ist wahr, falsch oder 14:21.030 --> 14:21.810 falsch ist falsch. 14:22.810 --> 14:27.070 Und dann sehen Sie hier in der drittletzten Spalte jetzt für alle 14:27.070 --> 14:29.990 Interpretationen, die denkbar sind, für die Formel nicht P oder nicht 14:29.990 --> 14:34.750 Q, kommt raus war, war, war falsch und für die andere Formel, die wir 14:34.750 --> 14:37.690 gerade schon hatten, kommt auch raus, war, war, war falsch. 14:41.700 --> 14:45.160 Da steht also in der drittletzten Spalte und in der letzten Spalte für 14:45.160 --> 14:47.700 jede Interpretation das Gleiche. 14:48.240 --> 14:53.180 Also diese beiden Formeln nicht P oder nicht Q und nicht P und Q sind 14:53.180 --> 14:56.620 so, egal welche Interpretation Sie nehmen, da kommt immer das Gleiche 14:56.620 --> 14:57.680 raus bei beiden Formeln. 14:57.740 --> 15:01.660 Das sind verschiedene Formeln, syntaktisch, in der einen kommt ein 15:01.660 --> 15:05.080 oder vor, aber kein und, in der anderen kommt ein und vor, aber kein 15:05.080 --> 15:08.480 oder, das sind syntaktisch unterschiedliche Gebilde, die sind sogar 15:08.480 --> 15:13.060 unterschiedlich lang, in der einen, ach so, wegen der Klammern sieht 15:13.060 --> 15:14.580 es jetzt gleich aus, na gut. 15:16.580 --> 15:19.900 Also das sind syntaktisch verschiedene Gebilde, aber für jede 15:19.900 --> 15:26.140 Interpretation der Wahrheitswert ist immer der Gleiche. 15:26.300 --> 15:27.520 Sowas kommt vor. 15:28.160 --> 15:33.120 Genauso wie zweimal X das Gleiche, wenn Sie in Zahlen, in irgendeinem 15:33.120 --> 15:36.420 Zahlenbereich rechnen, zweimal X, da kommt immer das Gleiche raus wie 15:36.420 --> 15:37.360 bei X plus X. 15:39.880 --> 15:43.180 Es gibt verschiedene Ausdrücke, die irgendwie immer das Gleiche 15:43.180 --> 15:45.000 bedeuten, in Anführungszeichen. 15:47.180 --> 15:50.820 So, und das ist ein wichtiges Konzept, deswegen kriegt das auch 15:50.820 --> 15:54.160 gleichen Namen und zwei Formeln, G und H, wollen wir Äquivalent 15:54.160 --> 15:59.300 nennen, wenn gilt, egal welche Interpretation man hernimmt, wenn man 15:59.300 --> 16:01.900 die eine Formel auswertet, wenn man die andere Formel auswertet, in 16:01.900 --> 16:04.700 der gleichen Interpretation, es kommt der gleiche Wahrheitswert raus. 16:05.320 --> 16:07.600 Für alle Interpretationen. 16:09.100 --> 16:10.120 Das ist das, was hier steht. 16:10.280 --> 16:13.040 Für jede Interpretation, Auswertung der einen Formel liefert das 16:13.040 --> 16:14.500 Gleiche wie Auswertung der anderen Formel. 16:14.800 --> 16:17.620 Und dafür schreiben wir jetzt dann im Folgenden vielleicht mal so G 16:17.620 --> 16:22.380 und drei waagerechte Striche H, so für Kurzform, Umgangssprache, für 16:22.380 --> 16:23.400 diesen Äquivalent. 16:24.080 --> 16:26.540 Und Äquivalent hat aber eine präzise Bedeutung. 16:27.980 --> 16:31.080 Und das erste Beispiel haben wir also gerade gesehen, Nicht-P oder 16:31.080 --> 16:33.740 Nicht -Q ist Äquivalent zu Nicht-P und Q. 16:34.920 --> 16:39.800 Man kann sich auch überlegen, Nicht-Nicht-P ist Äquivalent zu P. Man 16:39.800 --> 16:44.220 kann sich auch überlegen, das ist das, was wir in einer der Tabellen 16:44.220 --> 16:48.240 bei den burschen Funktionen gesehen haben, P-Pfeil-Q ist Äquivalent zu 16:48.240 --> 16:49.660 Nicht -P oder Q. 16:51.800 --> 16:57.940 Und das ist irgendwie die einzige Stelle bei der Implikation, wo man 16:57.940 --> 17:00.620 sich vielleicht, je nachdem, wie viel Sie schon in der Schule gesehen 17:00.620 --> 17:04.520 haben, noch ein bisschen an etwas gewöhnen muss, dass das so gesehen 17:04.520 --> 17:04.840 wird. 17:06.120 --> 17:11.080 P -Pfeil-Q ist unter anderem immer dann wahr, wenn P falsch ist. 17:13.960 --> 17:17.680 Egal, ob Sie daraus etwas folgern, was wahr oder falsch ist. 17:18.580 --> 17:22.120 Wenn die Voraussetzung falsch ist, die Implikation stimmt immer. 17:27.180 --> 17:31.440 Um vielleicht ein etwas besseres Gefühl dafür zu kriegen, fragen Sie 17:31.440 --> 17:36.060 sich mal, was ist denn das Gegenteil von P-Pfeil-Q, also jetzt mal 17:36.060 --> 17:39.340 umgangssprachlich, aus P folgt Q. 17:40.740 --> 17:50.160 Was würden Sie so anschaulich, das Gegenteil wäre, wenn Nicht aus P Q 17:50.160 --> 17:57.200 folgt, dass es also irgendwie geht, dass P wahr ist, aber Q nicht. 17:57.620 --> 17:59.540 Und das heißt, Nicht-Q ist wahr. 18:00.840 --> 18:09.260 Also P und Nicht-Q ist sozusagen das Gegenteil von P-Pfeil-Q. 18:09.620 --> 18:14.040 Das heißt, P-Pfeil-Q ist irgendwie äquivalent zu der Negation von P 18:14.040 --> 18:14.860 und Nicht-Q. 18:15.500 --> 18:19.880 Und jetzt können Sie zum Beispiel diese Äquivalenz von hier oben, die 18:19.880 --> 18:25.140 erste, ausnutzen und sagen, ja, Nicht-P und Nicht-Q ist äquivalent zu 18:25.140 --> 18:31.240 Nicht -das-erste, Nicht-P, oder Nicht-das-zweite, also Nicht-Nicht-Q. 18:31.980 --> 18:36.660 Und Nicht-Nicht-Q ist äquivalent zu Q und dann haben Sie Nicht-P oder 18:36.660 --> 18:43.440 Q als äquivalent zu P-Pfeil-Q in Anführungszeichen erkannt. 18:45.960 --> 18:49.480 Also das ist unsere Definition von Implikation. 18:50.700 --> 18:54.700 Das findet man manchmal in einigen Extremfällen etwas kurios, aber so 18:54.700 --> 18:55.120 ist sie. 18:55.860 --> 18:58.020 Und sie hat sich bewährt, diese Festlegung. 18:58.280 --> 18:59.300 Und deswegen nimmt man die. 18:59.900 --> 19:03.840 Jetzt würde man ja vielleicht gerne, also wenn Sie jetzt eine 19:03.840 --> 19:09.800 aussagenlogische Formel haben, für jede Interpretation, es kommt beim 19:09.800 --> 19:11.220 Auswerten ein Wahrheitswert raus. 19:11.320 --> 19:14.520 Das heißt, jede Formel legt irgendwie so eine Abbildung fest von 19:14.520 --> 19:18.040 Interpretation zu Gesamtwahrheitswert. 19:18.960 --> 19:22.120 Das gibt dann also, jede Formel legt dann also so eine Abbildung fest 19:22.120 --> 19:26.120 von BHV, Menge aller Interpretationen, nach Buhlscher Wert, der bei 19:26.120 --> 19:27.400 der Auswertung rauskommt. 19:29.120 --> 19:34.900 Und jetzt, wenn Sie die beiden Formeln nehmen, P0 und P0 einerseits 19:34.900 --> 19:39.880 und P2 und P2 andererseits, dann sind jetzt nach allem, was wir 19:39.880 --> 19:42.760 definiert haben, diese beiden Formeln nicht äquivalent. 19:44.080 --> 19:47.780 Wenn Sie nämlich eine Interpretation nehmen, wo P0 wahr ist und P2 19:47.780 --> 19:54.940 falsch, ist das der Fall, ja, dann P0 und P0 ist wahr, P2 und P2 ist 19:54.940 --> 19:55.420 falsch. 19:56.260 --> 19:57.180 Aber irgendwie, 20:00.800 --> 20:04.540 Hände wedeln, so richtig unterschiedlich sind die Formeln ja nicht, da 20:04.540 --> 20:06.200 ist ja nur die Variable umbenannt. 20:06.400 --> 20:10.180 Das ist doch in irgendeinem plausiblen Sinne das Gleiche. 20:11.820 --> 20:18.020 Und deswegen, was man dann machen kann, ist, man sagt, ja okay, also 20:18.020 --> 20:26.360 wir wollen jetzt einer Formel eine Buhlsche Funktion zuordnen, also 20:26.360 --> 20:30.780 nicht eine Abbildung aus jeder Interpretation ergibt sich ein 20:30.780 --> 20:36.460 Buhlscher Wert dann, sondern wirklich, man hat k-Buhlsche Werte und 20:36.460 --> 20:40.820 die werden durch die Formel auf einen Buhlschen Wert abgebildet und ob 20:40.820 --> 20:46.580 in der Formel die Variablen jetzt P1, P2, P3 oder P100, P101, P102 20:46.580 --> 20:47.580 heißen, ganz egal. 20:48.860 --> 20:50.900 Und was man dann machen kann, ist, man sagt, naja, 20:54.020 --> 21:00.400 wenn man die k-Wahrheitswerte hat, dann soll halt der erste 21:00.400 --> 21:04.260 Wahrheitswert für die Aussagevariable mit dem kleinsten Index sein, 21:04.480 --> 21:08.160 der zweite Wahrheitswert für die Aussagevariable mit dem zweitgrößten, 21:08.420 --> 21:11.200 die dritte der Wahrheitswert für die Aussagevariable mit dem 21:11.200 --> 21:14.140 drittgrößten Index und so weiter. 21:15.160 --> 21:18.780 Also Sie ignorieren dann die Nummerierung und interessieren sich nur 21:18.780 --> 21:22.120 für kleinster Index, zweitkleinster, drittkleinster. 21:22.620 --> 21:26.980 Und da stellt man sich jetzt wirklich, wir haben immer P0, P1, P2 und 21:26.980 --> 21:27.920 nicht so PQR. 21:34.690 --> 21:39.650 Also in einem plausiblen Sinne, wenn Sie eine Formel haben, Sie können 21:39.650 --> 21:43.790 sich so eine Tabelle machen für jede Interpretation, eine Zeile und 21:43.790 --> 21:46.250 die Formel auswerten, was kommt insgesamt raus. 21:47.090 --> 21:48.510 Das ist das Wesentliche. 21:49.330 --> 21:54.010 So, und jetzt kommen wir an eine Stelle, da werden jetzt noch zwei, 21:54.110 --> 22:00.950 drei Begriffe festgelegt und dann kommen ein paar Aussagen, die wir 22:00.950 --> 22:07.930 gar nicht beweisen werden, weil das irgendwie dann doch, in einem Fall 22:07.930 --> 22:09.970 eine Andeutung gebe ich Ihnen noch, aber ansonsten führt das 22:09.970 --> 22:14.990 vielleicht ein bisschen weit, aber ich möchte doch die wesentlichen 22:14.990 --> 22:16.290 Dinge gesagt haben. 22:18.910 --> 22:22.470 Später in dem Kapitel über Prädikatenlogik werden Sie sehen, das 22:22.470 --> 22:25.330 gleiche Programm taucht wieder auf, da sind die Beweise natürlich noch 22:25.330 --> 22:28.570 schwieriger, die werden wir erst recht nicht machen, aber einfach, 22:28.710 --> 22:33.170 dass Sie schon mal ein Gefühl dafür kriegen, was man da anstellt und 22:33.170 --> 22:36.570 warum das vielleicht ganz schön ist, was man da hinkriegt. 22:43.410 --> 22:47.030 Wenn Sie eine Aussagenlogische Formel G haben und eine Interpretation, 22:47.170 --> 22:49.910 dann gibt es zwei Möglichkeiten, wenn Sie die Formel auswerten mit der 22:49.910 --> 22:52.690 Interpretation, dann kommt da wahr oder falsch raus. 22:53.710 --> 22:56.430 Und jetzt stellen wir uns mal, oder jetzt sagt man, eine 22:56.430 --> 23:00.510 Interpretation ist ein Modell für eine Formel, wenn bei der Auswertung 23:00.510 --> 23:01.410 wahr rauskommt. 23:01.930 --> 23:03.470 Das ist sozusagen der schöne Fall. 23:06.690 --> 23:09.630 Und wenn man gleich mehrere Formeln hat, dann sagt man, eine 23:09.630 --> 23:14.530 Interpretation ist ein Modell für die ganze Menge von Formeln, wenn 23:14.530 --> 23:19.230 halt jede der Formeln aus der ganzen Menge immer ausgewertet war, gibt 23:19.230 --> 23:20.790 für diese Interpretation I. 23:25.780 --> 23:31.860 Und jetzt kann es sein, Sie haben eine Menge Großgamma von Formeln und 23:31.860 --> 23:38.440 eine Interpretation ist ein Modell für jede Formel in dieser 23:38.440 --> 23:39.880 Formelmenge Großgamma. 23:43.160 --> 23:48.100 Und jetzt kann es sein, dass für jede dieser Interpretationen, die ein 23:48.100 --> 23:52.660 Modell von Großgamma ist, auch ein Modell ist für irgendeine Formel 23:52.660 --> 23:53.080 GroßG. 23:54.460 --> 23:58.320 Also Sie haben so eine Formelmenge Gamma, vielleicht mehrere Formeln, 23:58.400 --> 24:01.040 vielleicht auch nur eine, vielleicht gar keine, wer weiß. 24:02.440 --> 24:07.120 Und Sie haben eine Formel GroßG, auf jeden Fall eine, und jetzt kann 24:07.120 --> 24:10.740 es sein, dass jede Interpretation, die alle Formeln aus Gamma 24:10.740 --> 24:13.500 wahrmacht, immer auch die Formel G wahrmacht. 24:14.620 --> 24:16.460 Egal, welche Interpretation Sie nehmen. 24:16.640 --> 24:19.380 Jede, die alle Formeln aus Gamma wahrmacht, macht auch G wahr. 24:20.360 --> 24:23.880 Und dann schreibt man da sowas hin, auf der linken Seite die 24:23.880 --> 24:28.180 Formelmenge Gamma, auf der rechten Seite die Formelmenge G und 24:28.180 --> 24:31.680 dazwischen so ein Zeichen, ein senkrechter Strich und daran kleben 24:31.680 --> 24:32.860 zwei waagerechte Striche. 24:37.150 --> 24:41.670 Also das bedeutet, jede Interpretation, die alle Formeln aus Gamma 24:41.670 --> 24:43.890 wahrmacht, macht auch die Formel G wahr. 24:48.720 --> 24:53.880 Und wenn die Formelmenge Gamma nur eine Formel enthält, dann schreibt 24:53.880 --> 24:57.880 man meistens nicht die Formel mit geschweiften Klammern außenrum hin, 24:57.920 --> 25:00.080 damit es eine ganze Menge ist, sondern man spart sich die Klammern, 25:00.080 --> 25:03.040 dann schreibt man nur die Formel hin und wenn die Formelmenge Gamma 25:03.040 --> 25:06.340 leer ist, dann schreibt man da nicht die leere Menge hin, sondern gar 25:06.340 --> 25:09.120 nichts, dann steht da nur dieses Zeichen, senkrechter Strich mit zwei 25:09.120 --> 25:12.700 waagerechten und dahinter die Formel G und wenn man das hinschreibt, 25:12.820 --> 25:13.300 was heißt das? 25:14.020 --> 25:17.700 Jede Interpretation, in der alle Formeln aus der leeren Menge wahr 25:17.700 --> 25:23.300 sind, und das sind alle Interpretationen, es gibt in der leeren Menge 25:23.300 --> 25:27.440 keine Formel, die falsch werden könnte, also das heißt dann, alle 25:27.440 --> 25:33.520 Interpretationen sind so, dass G in dieser Interpretation wahr wird. 25:33.620 --> 25:35.900 Also jede Interpretation macht die Formel G wahr. 25:36.460 --> 25:39.320 Die Formel G, da können Sie auswerten, mit jeder x-beliebigen 25:39.320 --> 25:41.560 Interpretation, da wird immer wahr rauskommen. 25:42.400 --> 25:44.900 Das ist ein besonders interessanter Fall, behaupte ich. 25:46.040 --> 25:47.480 Also da schreibt man dann so was. 25:49.360 --> 25:53.440 Und wir sind hier bei Interpretationen und das ist alles so 25:53.440 --> 25:57.720 semantisch, wir gucken an, was ist denn die Bedeutung der Formeln. 25:59.880 --> 26:06.480 Und so eine Formel, die in allen Interpretationen ausgewertet immer 26:06.480 --> 26:11.300 wahr gibt, wo jede Interpretation ein Modell ist, also wo gilt, 26:11.500 --> 26:16.220 senkrechter Strich mit zwei waagerechten G, eine solche Formel nennt 26:16.220 --> 26:17.520 man allgemeingültig. 26:17.660 --> 26:21.160 Die liefert immer wahr, da können Sie einsetzen für die Aussage 26:21.160 --> 26:23.120 variablen, was Sie wollen, liefert immer wahr. 26:24.100 --> 26:27.140 Oder man sagt dann auch, das ist eine sogenannte Tautologie. 26:32.200 --> 26:36.220 Hier zwei kleine Beispiele, ja, P oder nicht P, da können Sie für P 26:36.220 --> 26:40.240 einsetzen, was Sie wollen, als Beendeinterpretation wahr oder falsch. 26:40.660 --> 26:43.800 Da steht entweder wahr oder falsch oder es steht falsch oder wahr. 26:44.540 --> 26:47.020 P oder nicht P, da kommt immer wahr raus. 26:47.860 --> 26:51.860 Und genauso die zweite Formel hier, P-Pfeil in runden Klammern, Q 26:51.860 --> 26:55.440 -Pfeil, P, können Sie auch mal spaßhalber für P und Q alle 26:55.440 --> 26:58.580 Möglichkeiten durchprobieren, was man da einsetzen kann, da wird immer 26:58.580 --> 26:59.420 wahr rauskommen. 27:00.200 --> 27:00.500 Wieso? 27:02.260 --> 27:06.720 Wenn Sie für P falsch einsetzen, dann kommt da immer wahr raus. 27:06.860 --> 27:10.500 Sie erinnern sich, Definition von Auswertung vom Pfeil ist, wenn das 27:10.500 --> 27:12.040 vordere falsch ist, stimmt es sowieso. 27:13.500 --> 27:17.380 Also wenn Sie für P falsch einsetzen, ist das garantiert wahr, die 27:17.380 --> 27:18.340 ganze Implikation? 27:18.520 --> 27:18.720 Okay. 27:19.320 --> 27:24.220 Andere Möglichkeit, wir setzen für P wahr ein, also für P setzen wir 27:24.220 --> 27:27.780 wahr ein, dann ist das vordere wahr, dann muss laut Definition 27:27.780 --> 27:30.600 Bedeutung von Pfeil das hintere auch wahr sein. 27:31.360 --> 27:35.100 Da steht Q-Pfeil P, also wieder so eine Implikation und P ist jetzt 27:35.100 --> 27:38.140 wahr und da haben wir gesehen, ja, wenn P wahr ist, dann ist die 27:38.140 --> 27:39.360 Implikation sowieso immer wahr. 27:40.140 --> 27:43.060 Auch aus wahr folgt wahr und aus falsch folgt wahr. 27:43.520 --> 27:45.800 Also wenn vorne das wahr ist, ist das da hinten auch immer wahr. 27:45.800 --> 27:47.920 Da können Sie tun, was Sie wollen, es kommt immer wahr raus. 27:49.380 --> 27:51.680 So, solche Formeln heißen allgemeingültig. 27:56.880 --> 27:58.700 Alle Interpretationen sind Modelle. 27:59.320 --> 28:02.960 Und dann gibt es noch einen anderen interessanten Fall, nämlich 28:02.960 --> 28:07.420 Formeln, wo es wenigstens eine Interpretation gibt, für die Sie wahr 28:07.420 --> 28:07.860 liefern. 28:08.520 --> 28:16.820 Solche Formeln heißen erfüllbar und erfüllbare Formeln sind an 28:16.820 --> 28:20.900 diversen Stellen in der Informatik wichtig, also insbesondere das 28:20.900 --> 28:25.980 Problem von einer Formel herauszufinden, ist die jetzt erfüllbar oder 28:25.980 --> 28:26.300 nicht? 28:26.420 --> 28:29.600 Also kann ich Wahrheitswerte für die Aussagevariablen finden, so dass 28:29.600 --> 28:31.620 wahr rauskommt, ja oder nein? 28:32.860 --> 28:36.400 Und das ist für manche Formeln, da sieht man sozusagen sofort, ob es 28:36.400 --> 28:39.200 so eine Interpretation gibt. 28:39.460 --> 28:45.360 Wenn Sie so ein großes oder haben, von linksem und rechtsem und, ja da 28:45.360 --> 28:48.420 müssen Sie einfach nur bei dem oder, es reicht, wenn Sie das linke 28:48.420 --> 28:50.260 wahr machen und wie machen Sie so ein und wahr? 28:50.360 --> 28:53.320 Na ja, p ist wahr und nicht q ist wahr, also q falsch. 28:53.620 --> 28:54.500 Das ist ganz einfach. 28:54.960 --> 28:58.780 Wenn Sie so ein und, so eine Konjunktion sagt man auch von zwei 28:58.780 --> 29:03.300 Ausdrücken haben, wo oder vorkommt, da sieht man das jetzt erstmal 29:03.300 --> 29:06.280 jedenfalls in diesem Mickey-Maus-Beispiel irgendwie nicht ganz so 29:06.280 --> 29:06.920 schnell. 29:07.740 --> 29:09.460 Da muss man sich vielleicht auch was überlegen. 29:09.520 --> 29:12.840 Dass man sich nicht ganz so schnell sieht, liegt daran, dass ja in 29:12.840 --> 29:16.300 beiden Teilen irgendwie die gleiche Aussagevariable vorkommen kann. 29:16.940 --> 29:19.700 Und wenn Sie einen Teil wahr machen, weil Sie für p irgendetwas 29:19.700 --> 29:22.940 bestimmtes wählen, dann im anderen Teil haben Sie vielleicht nicht p 29:22.940 --> 29:23.960 und das ist dann falsch. 29:24.220 --> 29:30.980 Und hier ist es jetzt auch noch nicht schwierig, aber im Allgemeinen 29:30.980 --> 29:34.860 von einer aussagenlogischen Formel herauszufinden, ob sie erfüllbar 29:34.860 --> 29:41.720 ist, ist anscheinend nicht so ganz einfach. 29:43.360 --> 29:48.100 Also man kennt bis jetzt in einem präzisen Sinne keine Algorithmen, 29:49.220 --> 29:53.560 die das in einem präzisen Sinne für schnell schnell herausfinden. 29:55.640 --> 30:03.340 Es gibt ganze Firmen, die, ich will nicht sagen nur existieren, aber 30:03.340 --> 30:05.760 unter anderem existieren, weil sie auch für die schwierigen Fälle 30:05.760 --> 30:08.600 irgendwelche Tricks haben, um möglichst schnell herauszufinden, ob 30:08.600 --> 30:10.360 eine Formel erfüllbar ist oder nicht. 30:11.500 --> 30:14.800 Aber es ist im Allgemeinen etwas kniffliger, das taucht dann zum 30:14.800 --> 30:17.500 Beispiel in theoretische Grundlagen der Informatik, wird das nochmal 30:17.500 --> 30:20.220 genauer behandelt, was heißt hier anscheinend schwierig und so. 30:26.560 --> 30:29.180 Tautologien, ich habe ja behauptet, Tautologien sind auch wichtig, das 30:29.180 --> 30:30.740 sind also Formeln, die sind immer wahr. 30:31.540 --> 30:32.860 Wo kriegt man welche her? 30:36.400 --> 30:39.480 Sie erinnern sich, wenn Sie zwei Formeln G und H haben, dann haben wir 30:39.480 --> 30:43.800 so eine Abkürzung G Doppelpfeil H eingeführt, einfach als Abkürzung 30:43.800 --> 30:47.640 für G impliziert H und H impliziert G. 30:47.640 --> 30:52.080 Hier sind jetzt keine Klammern hingeschrieben und das ist ganz 30:52.080 --> 30:54.540 schlecht, denn so wie es da steht, ist es mit unseren Klammer 30:54.540 --> 30:56.280 -Einsparungsregeln falsch. 30:57.340 --> 30:59.900 Ich werde das dann mal in den Folien noch korrigieren. 31:00.340 --> 31:04.180 Also stellen Sie sich bitte vor, G-Pfeil H ist geklammert und H-Pfeil 31:04.180 --> 31:05.400 G ist auch geklammert. 31:08.980 --> 31:13.040 So, wenn Sie jetzt das auswerten, also was gemeint ist, ist das 31:13.040 --> 31:19.080 logische und der Auswertung von G-Pfeil H und H-Pfeil G, dann stellen 31:19.080 --> 31:28.240 Sie fest, wenn Sie jetzt zwei Formeln haben, die äquivalent sind, die 31:28.240 --> 31:33.380 also für die gleichen Interpretationen wahr und für die gleichen 31:33.380 --> 31:37.820 Interpretationen falsch sind, wenn Sie zwei Formeln G und H haben, die 31:37.820 --> 31:40.780 äquivalent sind, also Auswertung von G ist immer das Gleiche wie 31:40.780 --> 31:46.200 Auswertung von H, dann diese Formel liefert tatsächlich immer wahr, 31:51.960 --> 31:56.420 denn Auswertung von G, Implikation Auswertung von G steht dann da, 31:56.860 --> 32:00.940 weil ja Auswertung von H das Gleiche ist wie Auswertung von G und dann 32:00.940 --> 32:04.160 ist das immer wahr und das immer wahr und das logische und ist auch 32:04.160 --> 32:04.620 immer wahr. 32:05.160 --> 32:07.720 Also wenn Sie zwei äquivalente Formeln haben, ist es einfach 32:07.720 --> 32:10.620 Tautologien hinzuschreiben, schreiben Sie einfach die äquivalenten 32:10.620 --> 32:12.820 Formeln hin, mit einem Doppelpfeil dazwischen. 32:18.460 --> 32:21.200 Also was das eben zeigt, ist, wenn Sie zwei Formeln haben, die 32:21.200 --> 32:26.620 äquivalent sind, dann G-Doppelpfeil H ist eine Tautologie, das ist 32:26.620 --> 32:31.220 dann immer wahr, das haben wir gerade so mehr oder weniger 32:31.220 --> 32:32.500 händewedelnd uns überlegt. 32:33.820 --> 32:38.280 Also ich gehe nochmal zurück zu der vorigen Formelfolie, wir kommen 32:38.280 --> 32:41.620 hier beim Auswerten an eine Stelle, da steht manchmal Auswertung G, 32:41.720 --> 32:44.960 Auswertung von H und wenn die Formeln äquivalent sind, ist das das 32:44.960 --> 32:48.260 Gleiche und dann kommt da einfach wahr raus. 32:49.420 --> 32:52.720 Also wenn zwei Formeln äquivalent sind, dann ist G-Doppelpfeil H eine 32:52.720 --> 32:53.440 Tautologie. 32:54.980 --> 32:57.480 Und siehe da, das Umgekehrte gilt auch. 32:58.840 --> 33:05.800 Wenn G-Doppelpfeil H eine Tautologie ist, dann sind G und H 33:05.800 --> 33:06.900 äquivalente Formeln. 33:11.210 --> 33:14.010 Und das werden wir nicht beweisen, können Sie ja mal so ein bisschen 33:14.010 --> 33:16.330 drüber nachdenken, dass das vielleicht ganz plausibel ist. 33:17.230 --> 33:20.450 Aber bitte beachten Sie ja dieses Äquivalenzzeichen hier rechts, das 33:20.450 --> 33:23.990 ist so ein semantisches Zeichen aus der Umgangssprache, na ja, 33:24.030 --> 33:26.650 semantisches Zeichen ist Quatsch, aber das ist so was, das schreiben 33:26.650 --> 33:29.390 wir umgangssprachlich, um auszudrücken, die beiden Formeln sind 33:29.390 --> 33:32.710 äquivalent für alle Interpretationen, es kommt immer das Gleiche raus. 33:33.290 --> 33:36.290 Auf der linken Seite, das ist eine Abkürzung für eine aussagenlogische 33:36.290 --> 33:38.030 Formel, was Syntaktisches. 33:40.310 --> 33:44.310 Und seien Sie froh, dass ich hier wenn dann geschrieben habe und nicht 33:44.310 --> 33:47.250 auch noch für dieses Umgangssprachliche, wenn dann einen Pfeil, dann 33:47.250 --> 33:48.790 wäre das hier alles irgendwie nicht mehr so schön. 33:51.990 --> 33:56.990 Man kann einen Haufen Tautologien aufschreiben, ohne viel Mühe findet 33:56.990 --> 33:57.430 man die. 33:57.790 --> 34:01.790 Also eine Möglichkeit ist jetzt also, äquivalente Formeln 34:01.790 --> 34:04.630 hinzuschreiben mit einem Doppelpfeil dazwischen, nicht nicht G, 34:04.870 --> 34:05.730 Doppelpfeil G. 34:07.270 --> 34:13.710 G impliziert H, Doppelpfeil, nicht G oder H und und und und, G und G, 34:13.810 --> 34:17.610 Doppelpfeil G, lauter solche Sachen, ja, alles Tautologien. 34:22.570 --> 34:25.250 Hier haben Sie mal ein paar Tautologien, wo nicht überall ein 34:25.250 --> 34:30.190 Doppelpfeil vorkommt sozusagen, G im Pfeil G, für jede Formel G ist 34:30.190 --> 34:33.830 immer eine Tautologie, da können Sie für G wahr einsetzen, falsch, 34:34.690 --> 34:37.610 irgendeine Formel einsetzen, die Auswertung wird immer vorne und 34:37.610 --> 34:40.510 hinten das Gleiche liefern und dann ist die Implikation immer wahr. 34:41.490 --> 34:46.350 Nicht G oder G, genau das Gleiche, egal was die Auswertung von G 34:46.350 --> 34:50.230 liefert, wahr oder falsch, bei dem oder dann eins ist wahr, eins ist 34:50.230 --> 34:52.810 falsch, also eins ist auf jeden Fall wahr und dann ist das oder auch 34:52.810 --> 34:53.030 wahr. 34:53.710 --> 35:01.670 Und und und und und, also auch das hier unten, das Vorletzte, das ist 35:01.670 --> 35:07.910 eine verklausulierte Formulierung von, wenn aus G und H die Formel K 35:07.910 --> 35:12.290 folgt und wenn aus G sowieso schon H automatisch folgt, dann aus G 35:12.290 --> 35:13.150 folgt direkt K. 35:16.500 --> 35:19.640 Und der Beweis, dass das Tautologien sind, im Zweifelsfall große 35:19.640 --> 35:22.160 Tabellen malen, alle Fälle durchprobieren. 35:28.770 --> 35:35.690 Also, Semantik von aussagenlogischen Formeln ist, die legen für jede 35:35.690 --> 35:40.530 Interpretation insgesamt einen Wahrheitswert für die ganze Formel. 35:40.950 --> 35:44.270 Also so eine Formel legt so eine Abbildung fest von Wahrheitswerte 35:44.270 --> 35:47.870 rein nach insgesamt Wahrheitswert bei der Auswertung kommt raus. 35:49.190 --> 35:52.350 Das ist so was Inhaltliches, so semantisch irgendwie. 35:52.410 --> 35:55.410 Was bedeutet eine Formel, so eine Abbildung von Wahrheitswerten auf 35:55.410 --> 35:56.070 Wahrheitswerte? 36:00.190 --> 36:04.130 Und dem wird jetzt was anderes gegenübergestellt, wo wir überhaupt 36:04.130 --> 36:07.430 nicht mehr über Interpretationen reden, über wahr und falsch. 36:08.910 --> 36:09.470 Erstmal. 36:14.010 --> 36:17.530 Also, es stellt sich dann nur hinterher fest heraus, ja, wir haben da 36:17.530 --> 36:20.470 was Geschicktes gemacht, aber erstmal vergessen wir das mit den 36:20.470 --> 36:23.890 Wahrheitswerten komplett und machen was ganz anderes. 36:26.830 --> 36:31.150 Nämlich, wir reden über Beweisbarkeit, also wir wollen jetzt darauf 36:31.150 --> 36:36.150 hinaus, dass man in irgendeinem Sinne aussagenlogische Formen beweisen 36:36.150 --> 36:36.510 kann. 36:39.170 --> 36:43.950 Und die allgemeine Situation, wenn man in der Aussagenlogik oder dann 36:43.950 --> 36:47.650 später in der Prädikatenlogik erster Stufe oder in noch irgendwas 36:47.650 --> 36:52.170 anderem über Beweisbarkeit redet, ist, dass man einen sogenannten 36:52.170 --> 36:53.510 Kalkül festlegt. 36:55.530 --> 36:59.070 Das formalisiert jetzt so ein bisschen das, was Sie einfach auch aus 36:59.070 --> 37:00.810 dem Mathematikunterricht oder so kennen. 37:01.230 --> 37:02.290 Was macht man da immer? 37:02.890 --> 37:09.730 Da hat man so Aktionen, irgendwie so Grundannahmen, die werden nicht 37:09.730 --> 37:12.230 weiter hinterfragt, die darf man einfach benutzen. 37:13.370 --> 37:16.050 x plus y gleich y plus x. 37:17.450 --> 37:20.350 Das werden Sie nie bewiesen haben, weil Sie wahrscheinlich nie 37:20.350 --> 37:25.070 definiert haben, Addition von natürlichen Zahlen. 37:26.390 --> 37:30.430 Wenn man es geeignet definiert, kann man es tatsächlich beweisen, aber 37:30.430 --> 37:31.650 das ist einfach so. 37:31.870 --> 37:36.070 x plus y ist y plus x, das verwenden Sie ständig, ohne groß drauf 37:36.070 --> 37:36.770 rumzureiten. 37:37.710 --> 37:45.590 Also man hat so Aktionen, jetzt dann eben Formeln, die muss man nicht 37:45.590 --> 37:50.650 beweisen, die sind einfach da, die darf man jederzeit hinschreiben und 37:50.650 --> 37:51.090 fertig. 37:53.850 --> 37:58.730 Und jetzt bei uns dann, Aktionen sind aussagenlogische Formeln, also 37:58.730 --> 38:02.370 man hat allgemein bei jedem Kalkül irgendwie so irgendeine Art von 38:02.370 --> 38:03.130 Formeln festgelegt. 38:04.630 --> 38:08.670 Muss man als erstes machen, was ist eine syntaktisch korrekte Formel? 38:08.970 --> 38:11.130 Wir haben es gesehen für aussagenlogische Formeln. 38:12.670 --> 38:16.810 Und dann legt man eine Teilmenge und der interessante Fall ist 38:16.810 --> 38:21.130 wirklich eine, in Anführungszeichen, kleine Teilmenge aller Formeln 38:21.130 --> 38:24.530 fest, sagt, das sind Aktionen, die darf ich jederzeit benutzen, da 38:24.530 --> 38:26.570 muss ich mich nicht rechtfertigen, die kann ich in jedem Beweis 38:26.570 --> 38:29.610 hinschreiben, keiner wird sich beschweren. 38:30.350 --> 38:35.250 Und das andere, was Sie dann machen, wenn Sie rechnen oder irgendwas 38:35.250 --> 38:40.430 beweisen ist, Sie sagen, naja, ich weiß das, ich weiß das, deswegen 38:40.430 --> 38:44.070 habe ich jetzt auch bewiesen noch etwas, was folgt aus dem, was ich 38:44.070 --> 38:44.850 schon vorher hatte. 38:45.610 --> 38:51.190 Da wendet man sogenannte Schlussregeln an, wenn ich schon erstens, 38:51.270 --> 38:55.330 zweitens, drittens, viertens bewiesen habe, dann gibt es eine 38:55.330 --> 38:59.510 allgemeine Schlussregel, die sagt, auf jeden Fall, dann gilt auch das 38:59.510 --> 39:00.470 und das als bewiesen. 39:01.510 --> 39:05.530 Und in dem Kalkül hier für die Aussagenlogik benutzen wir überhaupt 39:05.530 --> 39:12.730 nur eine Schlussregel, die heißt Modus ponens und die ist ganz 39:12.730 --> 39:13.270 einfach. 39:13.270 --> 39:17.750 Das steht jetzt hier ganz unten auf der nächsten Folie, nämlich wenn 39:17.750 --> 39:23.310 Sie so etwas wie einen Beweis bauen und Sie wollen Modus ponens 39:23.310 --> 39:28.990 anwenden, dann geht das nur in der folgenden Situation, Sie haben 39:28.990 --> 39:34.330 schon irgendwo bewiesen, die Formel G impliziert H, G-Pfeil H, die 39:34.330 --> 39:37.670 Formel haben Sie schon irgendwo stehen, Sie wissen schon, die gilt, 39:38.770 --> 39:42.550 warum auch immer, und Sie müssen schon irgendwo stehen haben, ah, die 39:42.550 --> 39:47.550 Formel G, die ist auch bewiesen, und dann sagt Modus ponens, also wenn 39:47.550 --> 39:51.830 Sie G-Pfeil H schon haben als bewiesen gilt und wenn G auch schon als 39:51.830 --> 39:56.010 bewiesen gilt, dann in Zukunft ab sofort darf man auch davon ausgehen, 39:56.090 --> 39:56.910 H ist bewiesen. 39:59.030 --> 40:01.370 Das klingt hoffentlich für Sie plausibel. 40:02.370 --> 40:05.870 Wenn man G-Pfeil H bewiesen hat und man hat bewiesen, G übrigens 40:05.870 --> 40:07.870 sowieso, naja, dann H auch. 40:09.770 --> 40:13.810 Aber das ist also rein syntaktisches Ding, man guckt sich die Struktur 40:13.810 --> 40:17.630 von den Formeln an, ist eine von der Form G-Pfeil H, ist die andere 40:17.630 --> 40:21.630 von der Form genau das, was vor dem Pfeil steht, dann dürfen Sie jetzt 40:21.630 --> 40:24.670 im nächsten Schritt in Ihrem Beweis auch hinschreiben, H gilt jetzt 40:24.670 --> 40:25.510 auch als bewiesen. 40:25.510 --> 40:28.670 Weil, ja, Modus ponens aus den beiden anderen. 40:30.470 --> 40:36.250 Also das ist die einzige Schlussregel in dem Aussagenkalkül, die wir 40:36.250 --> 40:37.270 hier mal annehmen wollen. 40:38.390 --> 40:41.770 Man kann es sich bequemer machen, aber darum geht es uns jetzt nicht. 40:42.470 --> 40:45.710 Wir werden keine großen Beweise in diesem Kalkül machen, die sind alle 40:45.710 --> 40:49.370 unglaublich umständlich, es geht nur darum, dass Sie den Plan 40:49.370 --> 40:49.870 mitkriegen. 40:49.870 --> 40:55.190 Und als Axiome für den Aussagenkalkül nimmt man diese drei Mengen von 40:55.190 --> 41:02.490 Formeln, die haben wir gerade schon gesehen, G-Pfeil, H-Pfeil, G, G 41:02.490 --> 41:07.490 -Pfeil, H, H, blablabla, und nicht H folgt nicht G-Pfeil, das haben 41:07.490 --> 41:09.970 wir uns nicht angeguckt, nicht Pfeil folgt G, folgt H. 41:10.710 --> 41:13.570 Und wenn man sich das mal genauer unter die Lupe nimmt, dann stellt 41:13.570 --> 41:18.930 man fest, also für beliebige Formeln G, H, aber alle diese Axiome, die 41:18.930 --> 41:22.430 hier stehen, das sind alles Tautologien. 41:23.910 --> 41:25.390 Das sind alles Tautologien. 41:27.490 --> 41:31.090 Gut, im Allgemeinen, die Axiome können sich aussuchen. 41:32.810 --> 41:35.270 Je nachdem kriegen Sie halt dann einen sinnigen oder einen nicht so 41:35.270 --> 41:36.070 sinnigen Kalkül. 41:37.330 --> 41:41.150 Aber also hier sollen es diese drei Sorten von Formeln sein. 41:42.210 --> 41:50.230 So, also immer, man hat Axiome und Schlussregeln. 41:51.790 --> 41:58.870 Und jetzt, was ist ein Beweis oder etwas Allgemeiner, eine Ableitung 41:58.870 --> 42:05.890 einer Formel aus einer Menge von Formeln, die man als sogenannte 42:05.890 --> 42:08.390 Hypothesen oder so zur Verfügung hat? 42:13.890 --> 42:16.730 Ein Beweis ist einfach eine Folge von Formeln. 42:17.030 --> 42:19.490 Erste Formel, zweite, dritte, vierte, fünfte, sechste. 42:20.230 --> 42:23.190 Und für jede Formel muss es eine Rechtfertigung geben, dass man die in 42:23.190 --> 42:24.490 den Beweis hinschreiben darf. 42:25.410 --> 42:28.770 Und was Sie in jedem Beweis, in jeder Ableitung hinschreiben können, 42:29.050 --> 42:31.410 an jeder Stelle, ohne Rechtfertigung, sind Axiome. 42:32.030 --> 42:33.570 Sie können immer ein Axiom hinschreiben. 42:34.650 --> 42:36.670 Das ist einfach erlaubt per Definition. 42:36.670 --> 42:37.670 Punkt eins. 42:38.570 --> 42:39.210 Punkt zwei. 42:39.550 --> 42:44.130 Wenn Sie eine nicht leere Menge von Hypothesen oder Prämissen haben, 42:45.750 --> 42:48.890 so nach dem Motto, ich will jetzt nicht etwas x-beliebiges beweisen, 42:49.410 --> 42:54.190 sondern ich will jetzt nur etwas beweisen für beliebige Zahlen, 42:54.290 --> 42:58.430 sondern nur für Zweierpotenzen oder so, dann könnte vielleicht, also 42:58.430 --> 43:01.330 das ist jetzt nicht Aussagenlogik, aber dann könnte vielleicht die 43:01.330 --> 43:05.830 Prämisse sein, also jede Zahl ist eine Zweierpotenz oder so etwas. 43:08.010 --> 43:12.030 Also diese Formeln aus der Formelmenge Gamma, die nennt man dann 43:12.030 --> 43:15.130 Hypothesen oder Prämissen, das sind jetzt im Allgemeinen dann keine 43:15.130 --> 43:20.630 Axiome, aber man sagt, okay, also das soll auch noch mit einfließen 43:20.630 --> 43:21.910 dürfen in jeden Beweis. 43:22.690 --> 43:26.690 Und so eine Hypothese, so eine Formel aus der Formelmenge Gamma, 43:27.010 --> 43:30.450 dürfen Sie auch an jeder Stelle im Beweis, da stehen lauter Formeln, 43:30.890 --> 43:34.050 an jeder Stelle dürfen Sie eine Prämisse hinschreiben, sagt man halt 43:34.050 --> 43:36.970 noch dazu, das darf hier stehen, denn es ist ja eine Prämisse. 43:38.950 --> 43:41.790 So, also was darf man bis jetzt, Axiome darf man immer hinschreiben, 43:41.950 --> 43:46.150 sowieso, und wenn man Prämissen hat, Hypothesen, die darf man auch 43:46.150 --> 43:48.190 einfach hinschreiben, an jeder x-beliebigen Stelle. 43:50.390 --> 43:53.710 Und das einzige andere, was man jetzt noch tun darf, wenn man so ein 43:53.710 --> 43:58.930 Kalkül hat, ist, und bei uns ist das einfach nur Modus ponens, was 43:58.930 --> 44:03.290 anderes haben wir nicht, wenn Sie in Ihrer Liste, die ist ja 44:03.290 --> 44:08.290 durchnummeriert, 1, 2, 3, weiter vorne in Ihrer Liste zwei Formeln 44:08.290 --> 44:13.550 finden, die von der Bauart sind, G-Pfeil H und G, dann dürfen Sie 44:13.550 --> 44:16.790 jetzt weiter unten sagen, ja, jetzt darf ich hier H auch hinschreiben, 44:17.170 --> 44:20.150 das folgt mit Modus ponens aus den beiden Formeln da oben. 44:22.690 --> 44:23.190 Fertig. 44:24.210 --> 44:28.090 Also Sie dürfen Schlussregeln benutzen, um aus Formeln, aufgrund der 44:28.090 --> 44:32.130 Tatsache, dass schon manche Formeln in Ihrem Beweis stehen haben, eine 44:32.130 --> 44:35.810 unter Umständen neue Formel da auch noch unten anfügen zu dürfen, bei 44:35.810 --> 44:36.450 Ihrem Beweis. 44:40.090 --> 44:47.490 Das ist eine Ableitung einer Formel G aus einer Formelmenge Gamma, ist 44:47.490 --> 44:51.250 also eine Formel, eine Liste von endlich vielen Formeln, G1, G2 bis 44:51.250 --> 44:54.210 Gn, und jede Formel ist also... 44:57.870 --> 45:01.590 Die letzte Formel sollte die Formel G sein, bei der man rauskommen 45:01.590 --> 45:03.030 will, die möchte man beweisen. 45:03.710 --> 45:06.270 Gn sollte die Formel G sein, um die es einem geht. 45:08.470 --> 45:10.990 Und danach muss man nichts mehr hinschreiben, dann ist man ja fertig 45:10.990 --> 45:11.430 sozusagen. 45:12.710 --> 45:20.510 Und die anderen Formeln, G1 bis Gn-1, müssen alle so sein, es ist eine 45:20.510 --> 45:28.070 Aktion oder es ist eine Hypothese oder die Formel ergibt sich durch 45:28.070 --> 45:30.410 Modus Ponens aus Formeln weiter vorne in der Liste. 45:30.750 --> 45:34.550 Und die letzte Formel Gn muss sich dann auch irgendwie durch Modus 45:34.550 --> 45:36.650 Ponens im Zweifelsfall aus welchen weiter vorne geben. 45:37.330 --> 45:40.890 Und wenn man so eine Liste von Formeln hinschreiben kann, und bitte, 45:40.970 --> 45:43.890 haben Sie das gemerkt, wir reden überhaupt nicht über Wahrheitswerte. 45:44.730 --> 45:45.290 Gar nicht. 45:46.550 --> 45:49.530 Wir reden nur über, man darf Aktionen hinschreiben, man darf 45:49.530 --> 45:52.130 Hypothesen hinschreiben und da darf Modus Ponens anwenden. 45:53.670 --> 45:59.050 Wenn Sie sowas hinschreiben können, dann schreibt man wieder auf der 45:59.050 --> 46:02.350 linken Seite eine Formelmenge Gamma, auf der rechten Seite die Formel 46:02.350 --> 46:07.330 G, die man abgeleitet hat aus Gamma, und dazwischen ein Zeichen mit 46:07.330 --> 46:11.050 einem senkrechten Strich und an dem klebt nach rechts dran ein 46:11.050 --> 46:11.970 waagerechter Strich. 46:12.090 --> 46:13.410 Nicht zwei, sondern einer. 46:14.250 --> 46:18.350 Wir hatten vorhin bei jeder Interpretation, die Gamma erfüllt, erfüllt 46:18.350 --> 46:20.970 auch G, haben wir zwei waagerechte Striche, das war so ein 46:20.970 --> 46:21.830 semantisches Ding. 46:21.830 --> 46:23.730 Wir reden über Erfüllbarkeit. 46:24.350 --> 46:30.290 Hier mit einem Strich, das bedeutet, G ist beweisbar, aus den Aktionen 46:30.290 --> 46:34.850 mit Hilfe von Modus Ponens sitzt bei uns, aus der Formelmenge Gamma. 46:40.600 --> 46:45.280 Und ein Beweis ist eine Ableitung, für die Sie keine Hypothesen 46:45.280 --> 46:45.660 brauchen. 46:45.860 --> 46:49.060 Also dann bleibt nur übrig, Sie dürfen Aktionen hinschreiben und Sie 46:49.060 --> 46:50.440 dürfen Modus Ponens anwenden. 46:51.180 --> 46:52.300 Hypothesen gibt es nicht. 46:53.200 --> 46:57.740 Jede Formel muss Aktion sein oder sich durch Modus Ponens aus früheren 46:57.740 --> 46:58.100 ergeben. 46:59.440 --> 47:03.180 Und wenn Gamma leer ist, dann schreibt man da links von dem Zeichen 47:03.180 --> 47:04.000 gar nichts hin. 47:04.620 --> 47:07.300 Und in so einem Fall sagt man dann auch, die Formel G ist ein Theorem 47:07.300 --> 47:08.300 des Kalküls. 47:10.240 --> 47:10.720 Beweisbar. 47:11.780 --> 47:15.120 Theoreme sind das, was beweisbar ist in einem Kalkül. 47:19.080 --> 47:22.960 So, hier, damit Sie einmal ein Beispiel gesehen haben und gesehen 47:22.960 --> 47:27.100 haben, wie blöd das alles Hand zu haben ist, wenn man den Kalkül 47:27.100 --> 47:30.560 nimmt, den ich Ihnen hier gezeigt habe, es gibt bessere. 47:31.100 --> 47:33.300 Also bessere in dem Sinn, es geht schöner, ja. 47:34.500 --> 47:42.440 Aber, also, wir wollen beweisen P Pfeil P. Uns interessiert überhaupt 47:42.440 --> 47:46.460 nicht, ob das wahr oder falsch ist, wir wollen das beweisen in dem 47:46.460 --> 47:48.840 Kalkül für die Aussagenlogik, die wir gesehen haben. 47:49.560 --> 47:52.200 Da muss man also eine Liste von Formeln hinschreiben. 47:53.560 --> 47:57.680 Die letzte Formel sollte die sein, die man haben will, P Pfeil P. Und 47:57.680 --> 48:02.280 für jede Formel muss gelten, es ist ein Aktion oder die Formel ergibt 48:02.280 --> 48:04.040 sich durch Modus Ponens aus früheren. 48:04.180 --> 48:05.140 Was anderes gilt nicht. 48:06.940 --> 48:10.280 So, und dann habe ich Ihnen jetzt hier mal zum Beispiel als erste 48:10.280 --> 48:11.720 Formel eine hingeschrieben. 48:12.640 --> 48:16.540 Und wenn Sie nachgucken, was wir als Axiome definiert haben, stellen 48:16.540 --> 48:22.140 Sie fest, ja, diese Formel hat die Struktur, die ausreicht, damit das 48:22.140 --> 48:23.260 ein Axiom ist. 48:25.140 --> 48:27.560 Ich blätter jetzt nicht zurück, können Sie einfach nachgucken. 48:28.020 --> 48:30.360 Das war so eine Menge, drei Mengen von Axiomen. 48:30.880 --> 48:34.280 Und in der zweiten von den drei Mengen, was da steht, das erschlägt 48:34.280 --> 48:35.760 unter anderem diese Formel da. 48:36.060 --> 48:37.120 Das ist ein Axiom. 48:38.080 --> 48:41.620 Dann in der ersten von den drei Mengen, die war so definiert, dass 48:41.620 --> 48:46.120 das, was hier als zweite Formel steht, auch ein Axiom ist. 48:46.520 --> 48:47.440 Das ist einfach so. 48:48.440 --> 48:51.880 Und wenn etwas ein Axiom ist, ich darf es einfach hinschreiben in dem 48:51.880 --> 48:53.020 Beweis als eine Formel. 48:53.160 --> 48:55.540 Muss ich mir nicht rechtfertigen, ist ein Axiom fertig. 48:56.660 --> 48:59.460 Und das einzige andere, was wir hier noch tun dürfen, ist Modus Ponens 48:59.460 --> 48:59.940 anwenden. 49:01.140 --> 49:04.660 Und hurra, das funktioniert jetzt direkt ein erstes Mal. 49:04.660 --> 49:10.960 Die zweite Formel hier, da sehen Sie, die ist auch das Anfangsstück 49:10.960 --> 49:12.260 von der ersten Formel. 49:13.880 --> 49:16.300 Und dann kommt ein Pfeil und dann kommt irgendwas dahinter. 49:16.460 --> 49:19.520 Also die erste Formel ist von der Form G impliziert H. 49:20.120 --> 49:22.720 Die zweite Formel ist das G. 49:23.560 --> 49:27.700 Und dann sagt Modus Ponens, wenn ich schon G-Pfeil H bewiesen habe und 49:27.700 --> 49:30.900 G bewiesen habe, dann darf ich auch einfach H hinschreiben. 49:31.400 --> 49:34.940 Also der hintere Teil von der ersten Formel hier, das steht jetzt hier 49:34.940 --> 49:39.060 in der dritten Zeile als Formel, ergibt sich durch Modus Ponens aus 49:39.060 --> 49:39.780 den ersten beiden. 49:42.700 --> 49:45.060 Und immer, man kann hinschreiben, was ist die Rechtfertigung. 49:45.560 --> 49:47.780 Also hier jetzt Modus Ponens aus Zeilen 1 und 2. 49:48.480 --> 49:50.700 Dann habe ich hier nochmal was hingeschrieben, können Sie auch wieder 49:50.700 --> 49:55.440 nachgucken, ist ein Axiom gemäß dieser ersten Teilmenge von Axiomen. 49:56.040 --> 50:00.560 Und dann Hurra, das was hier steht, ist wieder der erste Teil dieser 50:00.560 --> 50:03.620 Formel in drittens, die von der Bauart ist. 50:03.720 --> 50:06.880 Da steht vorne eine Formel G und dann ein Pfeil und hinten eine Formel 50:06.880 --> 50:07.080 H. 50:08.760 --> 50:12.840 Und die Formel G ist genau das, was hier als Axiom in Zeile 4 steht. 50:13.100 --> 50:14.920 Können Sie wieder Modus Ponens anwenden. 50:15.020 --> 50:15.520 Was steht da? 50:15.640 --> 50:19.020 P, Pfeil, P. Und das ist das, was wir beweisen wollten. 50:19.780 --> 50:22.120 Und dann haben wir also dreimal ein Axiom hingeschrieben und zweimal 50:22.120 --> 50:25.820 Modus Ponens angewendet und sind rausgekommen ohne zusätzliche 50:25.820 --> 50:28.660 Hypothesen bei der Formel, die wir beweisen wollten. 50:30.840 --> 50:32.960 Das ist ein Beweis in diesem Kalkül. 50:34.840 --> 50:37.420 Man kann das durchgehen, man kann immer mit dem Kopf flicken und 50:37.420 --> 50:40.440 sagen, ja, das ist korrekt, ja, so war das definiert, ja, alles in 50:40.440 --> 50:40.800 Ordnung. 50:41.300 --> 50:43.120 Wirklich verstehen tut man das nicht, was da steht. 50:44.380 --> 50:47.000 Also man muss da länger drauf gucken, um überhaupt erstmal so ein 50:47.000 --> 50:50.700 Gefühl dafür zu kriegen und auch nach längerem Draufgucken denkt man 50:50.700 --> 50:53.680 immer noch, das ist ja alles ganz schön, aber wie komme ich denn zum 50:53.680 --> 50:56.800 Beispiel drauf, als erste Formel dieses lange Ding da hinzuschreiben, 50:57.200 --> 50:59.420 ausgerechnet das zu nehmen als Axiom. 51:01.600 --> 51:04.460 Naja, im Allgemeinen, man sieht es nicht. 51:06.800 --> 51:11.240 Und wir wollen die Fähigkeiten dann hier und da doch mal so etwas zu 51:11.240 --> 51:13.660 sehen, nicht vertiefen, das ist jetzt nichts, was man unbedingt lernen 51:13.660 --> 51:13.960 muss. 51:16.940 --> 51:18.180 Noch ein Beispiel. 51:20.040 --> 51:24.020 Wir wollen beweisen, Klammer auf, nicht P Pfeil P, Klammer zu P Pfeil 51:24.020 --> 51:27.220 P. Was ist ein Beweis? 51:27.400 --> 51:30.780 Eine Folge von Formeln und alles ist Axiom oder ergibt sich durch 51:30.780 --> 51:31.400 Modus ponens. 51:32.660 --> 51:35.860 So und meine Behauptung ist, da kann man mit etwas anfangen, was zu 51:35.860 --> 51:37.880 dem Axiom-Schema dritter Teil passt. 51:38.780 --> 51:42.720 Das schreibt man einfach hin, warum auch immer, es erweist sich als 51:42.720 --> 51:43.260 nützlich. 51:43.260 --> 51:48.560 So und dann habe ich hier als zweites hingeschrieben, nicht P Pfeil 51:48.560 --> 51:54.760 nicht P. Das ist kein Axiom, ergibt sich auch nicht durch Modus 51:54.760 --> 51:57.080 ponens, also eigentlich darf ich das gar nicht hinschreiben. 51:57.780 --> 52:01.840 Aber das ist im Prinzip genau von der Bauart, wie wir das gerade im 52:01.840 --> 52:03.520 ersten Beispiel bewiesen haben. 52:03.860 --> 52:07.660 Wenn Sie hier im ersten Beispiel statt P überall P durch nicht P 52:07.660 --> 52:09.260 ersetzen, funktioniert es immer noch. 52:10.140 --> 52:15.580 Das heißt, wenn Sie jetzt den so umbauen, statt P überall nicht P 52:15.580 --> 52:20.040 nehmen, dann haben Sie einen fünfzeiligen Beweis für nicht P Pfeil P. 52:21.260 --> 52:25.480 Den könnten Sie jetzt hier statt der zweiten Zeile hinschreiben, die 52:25.480 --> 52:26.260 fünf Zeilen. 52:26.860 --> 52:29.440 Das habe ich mir jetzt gespart, das haben wir vorher schon gemacht. 52:31.720 --> 52:35.220 Das packen wir jetzt sozusagen ein in ein kleines Schächtelchen, 52:35.620 --> 52:36.700 machen einen Aufkleber drauf. 52:36.700 --> 52:40.860 Wir haben schon bewiesen, nicht P Pfeil nicht P. Und benutzen das 52:40.860 --> 52:44.360 jetzt hier und sagen, naja, den Beweis haben wir schon gesehen, man 52:44.360 --> 52:48.180 könnte ihn hier reinschreiben, aber das sparen wir uns jetzt hier. 52:48.760 --> 52:51.960 Und dann können Sie wieder einmal Modus ponens noch anwenden und Sie 52:51.960 --> 52:54.460 landen bei der Formel, die Sie haben wollten. 52:55.060 --> 53:00.340 Also natürlich, und das bitte, wenn Sie mal später was Größeres 53:00.340 --> 53:03.440 beweisen oder Sie werden merken, wenn Sie was lesen, wenn man etwas 53:03.440 --> 53:08.420 beweist, das strukturiert man, man beweist erstmal so kleine Teile und 53:08.420 --> 53:10.720 aus den kleineren Teilen setzt man dann größere zusammen. 53:11.420 --> 53:14.740 Und das Zusammensetzen hier ist trivial, also man müsste nur die Zeile 53:14.740 --> 53:18.520 rausnehmen und stattdessen die Zeilen einsetzen, die wir auf der Folie 53:18.520 --> 53:19.480 vorher gesehen haben. 53:20.240 --> 53:23.100 Es ändern sich dann halt hier die Zeilennummern, naja gut. 53:25.260 --> 53:27.300 So, also sowas geht. 53:28.640 --> 53:31.300 Jetzt, wofür ist das alles gut oder was ist das Schöne? 53:33.960 --> 53:37.680 Um das zu sehen, gucken wir uns zwei Dinge an. 53:37.740 --> 53:42.120 Das Erste ist dieser Modus ponens, also wenn wir bewiesen haben, 53:42.400 --> 53:46.960 Formel G Pfeil Formel H und wenn wir bewiesen haben, Formel G, dann 53:46.960 --> 53:51.320 dürfen wir auch angeblich hinschreiben, Formel H gilt jetzt auch als 53:51.320 --> 53:51.760 bewiesen. 53:52.520 --> 53:55.260 Definieren kann man ja viel, wenn der Tag lang ist, warum ist das 53:55.260 --> 53:55.780 sinnvoll? 53:58.740 --> 54:02.380 Hier steht, warum das sinnvoll ist, wenn nämlich G Pfeil H eine 54:02.380 --> 54:07.280 Tautologie ist und wenn G eine Tautologie ist, dann ist H auch eine 54:07.280 --> 54:07.880 Tautologie. 54:08.800 --> 54:10.640 Sie erinnern sich, was ist eine Tautologie? 54:11.100 --> 54:14.860 Egal, welche Interpretation Sie nehmen, wenn Sie die Formel auswerten, 54:14.900 --> 54:16.040 es kommt immer wahr raus. 54:16.560 --> 54:19.060 Es geht hier um die Formeln, die immer wahr sind. 54:20.500 --> 54:24.800 Naja, also wenn G Pfeil H eine Tautologie ist, da kommt also immer 54:24.800 --> 54:30.060 wahr raus und das heißt entweder... 54:32.790 --> 54:34.850 Achso, gut, da kommt immer wahr raus. 54:34.990 --> 54:38.270 Wenn außerdem G Tautologie ist, dann weiß man, die Auswertung von G 54:38.270 --> 54:42.770 ist immer wahr und dann bedeutet das für die Auswertung von G Pfeil H, 54:42.890 --> 54:47.590 da steht immer vorne ein W und hinten die Auswertung von H und wenn 54:47.590 --> 54:51.470 Sie sich die Buhlsche Funktion für die Implikation angucken, wenn die 54:51.470 --> 54:56.350 Voraussetzung wahr ist, wenn das, was da als Konsequenz steht, auch 54:56.350 --> 54:59.590 wahr ist, ist die Implikation wahr und wenn das, was als Konsequenz da 54:59.590 --> 55:01.670 steht, falsch ist, ist die Implikation falsch. 55:02.370 --> 55:07.030 Also aus wahr folgt irgendetwas, das ist genau dieser Wahrheitswert 55:07.030 --> 55:07.890 von irgendetwas. 55:08.290 --> 55:14.190 Also immer wahr, Pfeil, Formel H, das ist der Wahrheitswert der Formel 55:14.190 --> 55:14.510 H. 55:14.510 --> 55:18.410 Wir hatten ja nur Interpretationen, 55:21.910 --> 55:27.410 diese ganze Argumentation war für jedes I und dann steht hier also für 55:27.410 --> 55:32.390 jedes I, Auswertung von H ist wahr. 55:33.970 --> 55:37.950 Also auch H, immer egal, welche Interpretation, wenn Sie H auswerten, 55:38.010 --> 55:39.410 es muss immer wahr rauskommen. 55:39.850 --> 55:42.050 Also H ist auch eine Tautologie. 55:42.050 --> 55:45.430 Also wenn Sie in Modus ponens zwei Formeln reinstrecken, die 55:45.430 --> 55:49.990 Tautologien sind, immer wahr, dann das, was Modus ponens rauspuckt als 55:49.990 --> 55:51.750 dritte Formel, ist auch immer wahr. 55:52.850 --> 55:54.790 Tautologien rein, Tautologie raus. 55:57.550 --> 56:02.210 Außerdem, wenn Sie sich diese Axiome angucken, die ich Ihnen hier 56:02.210 --> 56:07.450 hingeschrieben hatte, diese drei Mengen für Aussagenkalkül, dann sehen 56:07.450 --> 56:10.710 Sie, die Axiome sind alle Tautologien, hatte ich vorhin glaube ich 56:10.710 --> 56:13.950 auch schon mal erwähnt, dass das halt so ist, muss man halt alles mal 56:13.950 --> 56:17.450 ausprobieren, Tabellen malen, auswerten, man sieht, es kommt immer 56:17.450 --> 56:18.090 wahr raus. 56:22.870 --> 56:25.650 Also, die Axiome, die wir da hingeschrieben hatten, sind alle 56:25.650 --> 56:30.110 Tautologien und wenn Sie Modus ponens anwenden auf zwei Tautologien, 56:30.210 --> 56:32.030 was rauskommt, ist wieder eine Tautologie. 56:33.630 --> 56:38.810 Also, wenn Sie so einen Beweis haben in dem Aussagekalkül, eine Formel 56:38.810 --> 56:42.870 nach der anderen und jede ist Axiom oder ergibt sich durch Modus 56:42.870 --> 56:47.290 ponens, alle Formeln, die da stehen, werden immer alle Tautologien 56:47.290 --> 56:47.650 sein. 56:48.110 --> 56:52.130 Da kommen Sie gar nicht drum rum, weil die Axiome Tautologien sind und 56:52.130 --> 56:55.490 Modus ponens aus Tautologien auch immer wieder Tautologien macht. 56:59.640 --> 57:07.720 Also, alles, was Sie beweisen können, jedes Theorem des Aussagekalküls 57:07.720 --> 57:09.160 ist eine Tautologie. 57:09.780 --> 57:12.080 Alles, was Sie beweisen können, ist immer wahr. 57:13.640 --> 57:14.520 Salopp gesprochen. 57:17.220 --> 57:21.480 So, das ist relativ einfach zu sehen. 57:24.320 --> 57:28.220 Und Überraschung oder vielleicht so ein bisschen die umgekehrte 57:28.220 --> 57:29.280 Richtung gilt auch. 57:30.460 --> 57:35.840 Wenn Sie eine aussagenlogische Formel haben, die Tautologie ist, also 57:35.840 --> 57:40.220 in jeder Interpretation immer, wenn Sie es auswerten, es kommt wahr 57:40.220 --> 57:44.340 raus, wenn Sie so eine aussagenlogische Formel haben, die immer wahr 57:44.340 --> 57:50.680 ist, dann ist sie auch in dem Kalkül beweisbar. 57:50.680 --> 57:52.080 Dann ist sie Theorem. 57:55.780 --> 58:00.860 Und das heißt also, wenn Tautologie, dann beweisbar. 58:00.940 --> 58:02.560 Wenn beweisbar, dann Tautologie. 58:03.180 --> 58:08.440 Also für jede Formel, das eine gilt genau dann, wenn das andere gilt. 58:09.200 --> 58:13.580 Sie können in dem Kalkül genau das beweisen, die Formeln beweisen, die 58:13.580 --> 58:14.480 immer wahr sind. 58:15.460 --> 58:17.300 Und das passt irgendwie nett zusammen. 58:17.560 --> 58:19.480 Das klingt irgendwie so, als wollte man es haben. 58:19.560 --> 58:21.360 Man möchte das beweisen können, was immer wahr ist. 58:22.620 --> 58:25.060 Wir sind hier nur im Aussagekalkül, aber immerhin. 58:27.980 --> 58:31.520 Dass diese zweite Richtung auch gilt, ist ein bisschen mühsamer zu 58:31.520 --> 58:31.960 beweisen. 58:32.080 --> 58:33.900 Das wollen wir jetzt nicht im Detail veranstalten. 58:36.600 --> 58:38.120 Also genauer gesagt gar nicht. 58:39.080 --> 58:40.600 Das ist nicht so ganz banal. 58:40.680 --> 58:43.940 Also Sie haben eine Formel, da wissen Sie erstmal nur, wenn ich die 58:43.940 --> 58:47.100 Tabelle hinmale, Auswertung in allen Interpretationen, da kommt am 58:47.100 --> 58:48.300 Ende immer wahr raus. 58:49.540 --> 58:52.580 Und jetzt wissen Sie daraus, und das kann man hier tatsächlich noch 58:52.580 --> 58:57.260 machen, konstruktiv irgendwie einen Beweis basteln in diesem Kalkül. 58:57.520 --> 59:00.120 Das kriegt man hin, ist aber ein Haufen Arbeit. 59:01.780 --> 59:03.780 Aber wir merken uns, das geht. 59:04.320 --> 59:07.080 Und das Schöne ist, wir werden sehen in Prädikatenlogik erster Stufe, 59:07.200 --> 59:08.480 das kriegt man auch noch hin. 59:09.660 --> 59:13.060 Da macht man auch ein Kalkül und alles, was da beweisbar ist, ist auch 59:13.060 --> 59:17.700 genau das, was da bei den prädikatenlogischen Formeln immer wahr ist. 59:18.840 --> 59:21.880 Das ist schön, das möchte man haben, aber es ist natürlich auch kein 59:21.880 --> 59:22.580 Zufall. 59:23.860 --> 59:27.800 Man hat natürlich diesen Kalkül so gebaut, dass es klappt, also 59:27.800 --> 59:32.480 insbesondere erstmal, dass Sie da nur Tautologien ableiten können. 59:34.100 --> 59:36.520 Und dass die umgekehrte Richtung auch geht, ist schön. 59:40.920 --> 59:45.020 Und das wird auch bei Prädikatenlogik immer noch genauso sein. 59:47.240 --> 59:50.000 Etwas anderes ist hier auch noch ganz schön. 59:52.040 --> 59:55.100 Das wird bei Prädikatenlogik nicht mehr funktionieren. 59:57.020 --> 01:00:01.300 Und deswegen bitte Vorsicht, wenn das, was da steht, für Sie einen 01:00:01.300 --> 01:00:03.720 ganz plausiblen, naheliegenden Eindruck macht. 01:00:04.240 --> 01:00:08.780 Ist ja gut, für Aussagenlogische Formeln ist es auch plausibel, es ist 01:00:08.780 --> 01:00:09.420 einfach richtig. 01:00:09.420 --> 01:00:15.960 Aber Vorsicht, Vorsicht, Vorsicht, später, es geht auch mal schief. 01:00:17.600 --> 01:00:20.880 Und das ist ein Satz, den werden wir auch nicht im Detail beweisen, 01:00:21.540 --> 01:00:23.140 aber die Aussage ist die folgende. 01:00:24.760 --> 01:00:29.160 Stellen Sie sich vor, Sie haben zwei Aussagenlogische Formeln, G und 01:00:29.160 --> 01:00:29.440 H. 01:00:31.340 --> 01:00:37.000 Und Sie können einen Beweis für H hinschreiben, eine Ableitung für H 01:00:37.000 --> 01:00:43.040 hinschreiben und da brauchen Sie Axiome, Modus ponens und eine weitere 01:00:43.040 --> 01:00:43.580 Formel G. 01:00:45.180 --> 01:00:49.220 Also wenn Sie die Formel G als Hypothese, als Prämisse noch haben, 01:00:49.320 --> 01:00:51.320 dann können Sie ableiten H. 01:00:52.300 --> 01:00:58.040 Wenn das der Fall ist, können Sie in dem Kalkül auch ableiten, ohne 01:00:58.040 --> 01:01:00.560 Voraussetzungen, G-Pfeil H. 01:01:01.840 --> 01:01:06.080 Das klingt vernünftig, es funktioniert auch. 01:01:08.120 --> 01:01:14.420 Und die umgekehrte Richtung gilt auch, wenn Sie G-Pfeil H ableiten 01:01:14.420 --> 01:01:18.160 können, dann können Sie auch, wenn Sie als Prämisse G haben, H 01:01:18.160 --> 01:01:18.660 ableiten. 01:01:18.800 --> 01:01:19.840 Das ist ganz einfach. 01:01:20.460 --> 01:01:23.720 Stellen Sie sich vor, das ist der einfachere Fall, Sie können G-Pfeil 01:01:23.720 --> 01:01:28.240 H ableiten, also Sie können einen Beweis hinschreiben, keine 01:01:28.240 --> 01:01:30.920 Prämissen, einfach G-Pfeil H ist beweisbar. 01:01:31.640 --> 01:01:35.240 Axiome, Modus ponens, Axiome, Modus ponens, Axiome, Axiome, Modus 01:01:35.240 --> 01:01:36.260 ponens, G-Pfeil H. 01:01:37.580 --> 01:01:44.260 Wenn Sie das haben und Sie haben jetzt zusätzlich auch noch G als 01:01:44.260 --> 01:01:47.100 Prämisse, dann dürfen Sie als nächstes einfach G hinschreiben, weil es 01:01:47.100 --> 01:01:48.420 als Hypothese erlaubt ist. 01:01:49.160 --> 01:01:52.580 Und dann haben Sie G-Pfeil H und G, machen einmal Modus ponens, steht 01:01:52.580 --> 01:01:53.040 H da. 01:01:53.800 --> 01:01:57.500 Und dann sehen Sie sofort, wenn ich G als Hypothese beenden darf, dann 01:01:57.500 --> 01:01:58.360 folgt auch H. 01:01:58.900 --> 01:02:01.960 Sie machen einfach noch zwei Formeln an den Originalbeweis hinten 01:02:01.960 --> 01:02:02.260 dran. 01:02:03.960 --> 01:02:06.020 Die umgekehrte Richtung ist komplizierter. 01:02:09.680 --> 01:02:15.920 Sie haben einen Beweis, da steht am Ende H und was Sie vorher stehen 01:02:15.920 --> 01:02:20.100 haben, sind Axiome und wir machen Modus ponens und die Hypothese G. 01:02:21.200 --> 01:02:24.740 Und jetzt wollen Sie einen neuen Beweis haben, wo Sie die Hypothese G 01:02:24.740 --> 01:02:30.680 nicht mehr benutzen, nur noch Axiome und dafür muss rauskommen G-Pfeil 01:02:30.680 --> 01:02:30.920 H. 01:02:32.840 --> 01:02:39.920 Das kriegt man auch hin und das ist auch sozusagen noch konstruktiv, 01:02:41.400 --> 01:02:46.060 aber ehrlich gesagt, das überspringe ich jetzt einfach. 01:02:46.740 --> 01:02:50.820 Gucken Sie sich es mal an, da lernt man noch so ein bisschen umgehen 01:02:50.820 --> 01:02:55.000 mit Beweisen, aber es ist jetzt auch nicht so wahnsinnig wichtig für 01:02:55.000 --> 01:02:56.040 die Vorlesung. 01:02:58.780 --> 01:02:59.220 Gut. 01:02:59.220 --> 01:03:01.520 Und damit sind wir am Ende dieses Kapitels. 01:03:04.300 --> 01:03:04.740 Wichtig. 01:03:05.920 --> 01:03:08.660 Also erstens, wir haben definiert, was sind aussagenlogische Formeln 01:03:09.560 --> 01:03:14.560 und da muss man also erstmal sagen, syntaktisch, wie sehen die Dinge 01:03:14.560 --> 01:03:17.520 aus, was darf ich hinschreiben, damit es eine aussagenlogische Formel 01:03:17.520 --> 01:03:19.380 ist und was darf ich nicht hinschreiben. 01:03:20.100 --> 01:03:20.460 Gut. 01:03:22.600 --> 01:03:29.020 Und dann haben wir zum einen sozusagen eine Bedeutung von 01:03:29.020 --> 01:03:32.900 aussagenlogischen Formeln festgelegt, für jede Interpretation, es 01:03:32.900 --> 01:03:36.600 kommt ein Wahrheitswert raus, die legen irgendwie busche Funktionen 01:03:36.600 --> 01:03:37.000 fest. 01:03:37.860 --> 01:03:41.180 Und dann gibt es eben insbesondere solche aussagenlogischen Formeln, 01:03:41.300 --> 01:03:43.300 die immer wahr sind, Tautologien. 01:03:45.040 --> 01:03:46.360 Formeln, die sind immer wahr. 01:03:47.020 --> 01:03:49.580 Das ist das eine, also so ein semantischer Begriff. 01:03:50.480 --> 01:03:54.560 Und das andere ist, dass wir hier so ein erstes, einfaches, kleines 01:03:54.560 --> 01:03:58.500 Beispiel so mal oberflächlich angeguckt haben von einem Kalkül, da 01:03:58.500 --> 01:04:04.480 haben Sie Axiome und Sie haben eine Ableitungsregel, Modus ponens und 01:04:04.480 --> 01:04:09.000 ein Beweis ist dann einfach eine Liste von Formeln, ohne über 01:04:09.000 --> 01:04:12.040 Wahrheitswerte zu reden, einfach eine Liste von Formeln und da dürfen 01:04:12.040 --> 01:04:14.860 Sie Axiome hinschreiben und Formeln, die sich durch Modus ponens aus 01:04:14.860 --> 01:04:15.620 früheren ergeben. 01:04:16.480 --> 01:04:17.000 Fertig. 01:04:17.380 --> 01:04:22.420 Dieser Beweisbegriff ist völlig schematisch, völlig mechanisch. 01:04:23.140 --> 01:04:26.360 Genau das Richtige für blöde Rechner, immer stumpfsinnig irgendwas 01:04:26.360 --> 01:04:27.080 runternudeln. 01:04:27.800 --> 01:04:29.200 Das will man nicht als Mensch machen. 01:04:30.640 --> 01:04:34.740 Und die Beobachtung ist, da habe ich Ihnen so mitgeteilt, man hat das 01:04:34.740 --> 01:04:40.660 geschickt hingekriegt, der Kalkül ist so gebaut, es ist genau das 01:04:40.660 --> 01:04:42.360 beweisbar, was immer wahr ist. 01:04:42.700 --> 01:04:45.740 Genau die Tautologien sind beweisbar und nichts anderes. 01:04:47.300 --> 01:04:48.700 Passt irgendwie nett zusammen. 01:04:50.120 --> 01:04:54.180 Ja und naja, also rechnen Sie halt mal noch ein bisschen mit bulschen 01:04:54.180 --> 01:04:55.140 Funktionen rum 01:04:58.340 --> 01:05:03.120 und ich weiß nicht, schreiben Sie sich mal ein paar einfache bulsche 01:05:03.120 --> 01:05:06.900 Aussagen, logische Formeln hin und fragen Sie sich, ob die erfüllbar 01:05:06.900 --> 01:05:07.800 sind oder nicht. 01:05:08.700 --> 01:05:11.400 Und gucken Sie mal, ob das vielleicht manchmal schwierig wird, das 01:05:11.400 --> 01:05:12.160 rauszufinden. 01:05:12.980 --> 01:05:17.140 Also raus, ob eine Formel erfüllbar ist, rausfinden geht immer, man 01:05:17.140 --> 01:05:19.600 probiert einfach alle Interpretationen durch. 01:05:21.060 --> 01:05:24.880 Aber wenn Sie n Aussagevariablen haben, haben Sie halt zwei hoch n 01:05:24.880 --> 01:05:28.100 Interpretationen, das könnte etwas länger dauern. 01:05:30.360 --> 01:05:31.740 Das ist der Haken an der Sache. 01:05:31.740 --> 01:05:34.740 Deswegen die Frage ist, geht es irgendwie schneller? 01:05:35.720 --> 01:05:37.360 Für irgendeine Definition von schneller. 01:05:39.640 --> 01:05:44.340 Okay, damit sind wir am Ende dieses Kapitels und wir kommen jetzt zu 01:05:44.340 --> 01:05:49.840 etwas, das ist schon immer mal so ein bisschen angeklungen, nämlich 01:05:49.840 --> 01:05:52.340 insbesondere beweist durch vollständige Induktion. 01:05:54.140 --> 01:05:58.500 Und da blende ich jetzt hier kurz eine URL ein, denn ich bin mir nicht 01:05:58.500 --> 01:06:01.960 ganz sicher, die Vorlesung wird ja aufgezeichnet, ob das, was ich 01:06:01.960 --> 01:06:04.320 Ihnen jetzt gleich zeige, das schnipselige Video, ob das in der 01:06:04.320 --> 01:06:07.840 Aufzeichnung drin sein darf oder nicht, falls es rausgeschnitten wird, 01:06:08.260 --> 01:06:09.420 da ist es. 01:06:12.300 --> 01:06:16.120 Und das kennen Sie alle, manchmal macht man es auch zu Hause, 01:06:16.240 --> 01:06:18.940 vielleicht eher mit Dominosteinen auf dem Tisch als im Garten mit 01:06:18.940 --> 01:06:24.760 Steinen, aber wenn da so Steine hintereinander stehen und man schweißt 01:06:24.760 --> 01:06:30.800 dann den ersten um, dann so nach und nach fällt ein Stein nach dem 01:06:30.800 --> 01:06:31.360 anderen um. 01:06:32.060 --> 01:06:33.840 Das ist vollständige Induktion. 01:06:34.860 --> 01:06:35.140 Prima. 01:06:35.340 --> 01:06:36.320 Kommen wir zum nächsten Kapitel. 01:06:36.660 --> 01:06:42.740 Nein, also so nach und nach fallen die alle um. 01:06:43.900 --> 01:06:45.020 Wieso klappt das? 01:06:46.140 --> 01:06:51.940 Na, jemand schmeißt den ersten Stein um und dann steht der erste so 01:06:51.940 --> 01:06:55.420 nah beim zweiten, dass wenn der umfällt, er den zweiten anschubst und 01:06:55.420 --> 01:06:56.380 der fällt dann auch um. 01:06:56.860 --> 01:07:01.980 Und außerdem, wenn der zweite umfällt, dann steht der irgendwie so nah 01:07:01.980 --> 01:07:05.000 beim dritten, dass wenn der zweite umfällt, irgendwann schubst du den 01:07:05.000 --> 01:07:05.600 dritten an. 01:07:06.060 --> 01:07:09.680 Und dann steht der dritte so bei dem vierten, dass wenn er dann 01:07:09.680 --> 01:07:11.400 umfällt, er schubst den vierten an. 01:07:12.580 --> 01:07:16.500 Und wenn man sich sicher sein will, dass alle umfallen, ja, da muss 01:07:16.500 --> 01:07:18.820 man halt diese Stellen alle angucken im Zweifelsfall. 01:07:18.820 --> 01:07:22.960 Ja, also wenn da irgendjemand einfach wild Steine hintereinander 01:07:22.960 --> 01:07:26.460 hingestellt hat und Sie wollen sicher sein, dass die alle umfallen, 01:07:26.520 --> 01:07:27.720 müssen Sie sich alle Stellen angucken. 01:07:29.180 --> 01:07:32.460 Das ist viel Arbeit, das ist nicht so schön, ja. 01:07:34.240 --> 01:07:36.220 Wie kann man sich das vereinfachen? 01:07:36.720 --> 01:07:39.600 Na, der, der die Steine aufgestellt hat, war vielleicht nett und hat 01:07:39.600 --> 01:07:43.140 gesagt, hier, ich habe so eine Schablone, ich habe mir das überlegt, 01:07:43.320 --> 01:07:47.960 ein gewisser Abstand ist passend und das benutze ich überall, ich 01:07:47.960 --> 01:07:51.460 mache genau den gleichen Abstand zwischen 1 und 2, zwischen 2 und 3, 01:07:51.620 --> 01:07:54.780 zwischen 3 und 4, 4 und 5, das ist überall das Gleiche. 01:07:55.660 --> 01:07:59.540 Und wenn du dir klar machen willst, dass der siebte Stein den achten 01:07:59.540 --> 01:08:03.280 umschmeißt oder dass der neunzehnte den zwanzigsten umschmeißt, das 01:08:03.280 --> 01:08:06.260 muss man sich nicht alles getrennt angucken, das ist immer der gleiche 01:08:06.260 --> 01:08:10.320 Abstand, überlegst dir einmal allgemein, ja, wenn Stein Nummer N 01:08:10.320 --> 01:08:13.060 umfällt, er schubst auf Stein Nummer N plus 1 an. 01:08:15.620 --> 01:08:19.120 Und dann muss man nicht mehr alle Stellen angucken, sondern einmal das 01:08:19.120 --> 01:08:22.540 Schema angucken und schauen, es klappt immer, es klappt in diesem Fall 01:08:22.540 --> 01:08:27.160 und wenn das für beliebiges N sozusagen funktioniert, ja, dann 01:08:27.160 --> 01:08:28.140 überall. 01:08:29.720 --> 01:08:34.160 So, jetzt für mich mal, wer hat denn in der Schule schon mal 01:08:34.160 --> 01:08:35.640 vollständige Induktion gemacht? 01:08:36.880 --> 01:08:38.060 Wer noch nicht? 01:08:39.460 --> 01:08:43.420 Okay, gut, also zumindest für die Hälfte oder so ist das irgendwie 01:08:43.420 --> 01:08:43.740 neu. 01:08:46.960 --> 01:08:48.540 Als einführendes Beispiel, 01:08:52.380 --> 01:08:56.240 also ich weiß ja, dass es bald Essen in der Mensa gibt, aber 01:08:56.240 --> 01:08:59.960 vielleicht nur so als Hinweis, wir gucken uns das gleich nochmal so 01:08:59.960 --> 01:09:03.660 ein bisschen an und Sie verpassen was, wenn Sie jetzt gehen. 01:09:09.530 --> 01:09:13.290 Nehmen wir als Beispiel etwas aus einem früheren Kapitel, da hat man 01:09:13.290 --> 01:09:16.810 mal definiert, was sind Potenzen eines Wortes, beliebiges Wort W, ja, 01:09:17.330 --> 01:09:19.930 hat man so gemacht, W hoch 0, haben wir gesagt, ist immer das leere 01:09:19.930 --> 01:09:24.590 Wort und W hoch N plus 1 ist immer W hoch N, konkateniert mit W, für 01:09:24.590 --> 01:09:25.650 jedes N aus N0. 01:09:29.610 --> 01:09:34.230 Behauptung, egal welches Wort man da hat, egal welches Alphabet, die 01:09:34.230 --> 01:09:37.210 Länge von W hoch N ist immer N mal die Länge von W. 01:09:40.110 --> 01:09:41.410 Wie beweist man das? 01:09:41.550 --> 01:09:44.090 Na ja, man kann es ja erstmal für ein paar einfache Fälle ausrechnen, 01:09:44.210 --> 01:09:47.290 für W hoch 0 ist es einfach. 01:09:53.790 --> 01:09:58.290 Wir hatten erstmal gesehen, mit den Dingern kann man rechnen, also W 01:09:58.290 --> 01:10:02.230 hoch 0 ist leere Wort, ist Definition, W hoch 1 können Sie einsetzen, 01:10:02.590 --> 01:10:05.450 nehmen Sie die zweite Zahl in der Definition, es gibt W hoch 0, 01:10:05.570 --> 01:10:09.710 konkateniert mit W, kommt W raus, W hoch 2 ist W, konkateniert mit W 01:10:09.710 --> 01:10:11.350 und so weiter, haben wir schon mal gesehen. 01:10:14.070 --> 01:10:16.890 Jetzt, der Beweis, dass das mit den Wortlängen immer stimmt. 01:10:18.610 --> 01:10:21.090 Ja, fangen wir doch mal an mit dem einfachsten Fall, die Länge des 01:10:21.090 --> 01:10:25.370 Wortes, das N ist gleich 0, also für irgendein Wort W, was ist die 01:10:25.370 --> 01:10:26.590 Länge von W hoch 0? 01:10:27.950 --> 01:10:30.270 Ja, da muss man halt nachgucken, was die Definition von W hoch 0 ist, 01:10:30.310 --> 01:10:32.890 das ist das leere Wort, was ist die Länge des leeren Wortes, das ist 01:10:32.890 --> 01:10:33.170 0. 01:10:33.850 --> 01:10:38.850 Und in der Tat 0 ist 0 mal die Länge von W, egal wie lang W ist. 01:10:39.530 --> 01:10:43.010 Also die Länge von W hoch 0 ist immer gleich 0 mal Länge von W. 01:10:44.130 --> 01:10:46.950 Nehmen wir den Fall N gleich 1, da können Sie genauso rechnen. 01:10:48.390 --> 01:10:50.210 Was ist die Länge von W hoch 1? 01:10:50.370 --> 01:10:54.330 Das ist Definition von W hoch 1, ist W hoch 0, konkateniert mit W. 01:10:55.010 --> 01:10:56.190 Was ist die Länge davon? 01:10:56.770 --> 01:10:59.630 Das haben wir gesehen bei der Definition von Konkatenation, das ist 01:10:59.630 --> 01:11:02.370 einfach Summe der Längen der beteiligten Faktoren. 01:11:03.170 --> 01:11:04.530 Länge von W hoch 0 und W. 01:11:05.170 --> 01:11:08.630 Und Länge von W hoch 0, das haben wir uns ja gerade überlegt, das ist 01:11:08.630 --> 01:11:15.410 0 mal Länge von W plus Länge von W und gibt zusammen einmal Länge von 01:11:15.410 --> 01:11:15.650 W. 01:11:16.790 --> 01:11:19.570 Also für N gleich 1 hat das jetzt geklappt, weil wir sozusagen 01:11:19.570 --> 01:11:22.870 wussten, ja für N gleich 0 stimmt das, Länge von W hoch 0 ist nun mal 01:11:22.870 --> 01:11:23.410 Länge von W. 01:11:24.130 --> 01:11:28.450 Länge von W hoch 2 ist Länge von W hoch 1 plus Länge von W. 01:11:29.350 --> 01:11:31.790 Und da haben wir auch wieder den Fall, oh, Länge von W hoch 1, das 01:11:31.790 --> 01:11:35.390 hatten wir uns gerade überlegt, ist einmal Länge von W und einmal 01:11:35.390 --> 01:11:37.550 Länge von W plus W ist zweimal Länge von W. 01:11:38.690 --> 01:11:41.890 Ja und dann kann man das für 3 und für 4 und für 5 immer wieder 01:11:41.890 --> 01:11:45.950 hinschreiben, hinschreiben, hinschreiben und irgendwann merkt man ja 01:11:45.950 --> 01:11:49.010 offensichtlich, das geht immer, das ist immer das gleiche Schema, 01:11:49.210 --> 01:11:50.430 immer das gleiche Schema. 01:11:51.630 --> 01:11:55.170 Ja, man weiß es schon für W hoch N und dann kann man es auch für W 01:11:55.170 --> 01:11:56.150 hoch N plus 1. 01:11:57.630 --> 01:12:01.590 Und das ist dann sozusagen die vollständige Induktion und dass 01:12:01.590 --> 01:12:06.330 vollständige Induktion funktioniert, liegt an einer Eigenschaft der 01:12:06.330 --> 01:12:12.610 natürlichen Zahlen und natürliche Zahlen nehmen wir einfach so hin und 01:12:12.610 --> 01:12:15.130 dann müssen wir auch die Eigenschaft, die wir ausnutzen, einfach so 01:12:15.130 --> 01:12:18.430 hinnehmen, aber wenn Sie natürliche Zahlen definieren, dann ist das, 01:12:18.510 --> 01:12:21.570 was wir ausnutzen, tatsächlich Bestandteil der Definition von 01:12:21.570 --> 01:12:27.190 natürlichen Zahlen, nämlich, wenn Sie eine Menge haben, die, sagen wir 01:12:27.190 --> 01:12:33.350 mal, nur Zahlen aus N0 enthält und wenn Sie wissen, erstens, die 0 ist 01:12:33.350 --> 01:12:39.110 drin und zweitens, wenn irgendeine Zahl N, eine natürliche Zahl N in 01:12:39.110 --> 01:12:42.430 dieser Menge drin ist, dann N plus 1 ist garantiert auch drin. 01:12:43.890 --> 01:12:48.710 Wenn Sie eine Menge haben mit dieser Eigenschaft, die 0 ist drin und 01:12:48.710 --> 01:12:55.190 für jede Zahl auch ihr Nachfolger, dann versprochen, garantiert, diese 01:12:55.190 --> 01:12:58.730 Menge enthält alle Zahlen aus N0. 01:13:00.050 --> 01:13:03.310 Und wenn sie nur solche Zahlen enthält, dann ist eben M gleich N0. 01:13:04.150 --> 01:13:09.130 Also wenn 0 drin ist und wenn gilt, wenn eine Zahl drin ist, dann auch 01:13:09.130 --> 01:13:11.490 die 1 größere, dann sind alle Zahlen drin. 01:13:16.360 --> 01:13:18.760 Ich kann Ihnen auch Mengen hinschreiben... 01:13:20.660 --> 01:13:22.560 Also nein, lassen wir das. 01:13:23.200 --> 01:13:28.220 Also das gehört wirklich zur Definition von natürlichen Zahlen. 01:13:29.020 --> 01:13:32.340 Das können Sie nicht einfach so aus heiterem Himmel beweisen. 01:13:34.120 --> 01:13:38.560 Und das benutzt man bei Beweisen mit vollständiger Induktion. 01:13:39.100 --> 01:13:42.380 Da hat man für jedes N aus N0, sagen wir mal jetzt im einfachsten 01:13:42.380 --> 01:13:52.190 Fall, so eine Aussage, A N, und man möchte gerne beweisen, für jedes N 01:13:52.190 --> 01:13:54.510 die Aussage A N ist wahr. 01:13:54.930 --> 01:13:58.070 Also man möchte beweisen, nicht nur A 0 ist wahr und A 1 ist wahr und 01:13:58.070 --> 01:14:01.630 A 2, sondern auch 3, 4, 5, jedes A N. 01:14:03.050 --> 01:14:04.410 Und wie macht man das? 01:14:05.250 --> 01:14:08.850 Na, man guckt sich die Menge, M habe ich die hier mal genannt, aller 01:14:08.850 --> 01:14:12.010 Zahlen N an mit der Eigenschaft A N ist wahr. 01:14:12.430 --> 01:14:14.190 Also diese Menge kann man erstmal definieren. 01:14:16.690 --> 01:14:21.450 Und was man gerne beweisen möchte ist, diese Menge ist ganz N0. 01:14:22.530 --> 01:14:25.410 Für alle N aus N0 soll die Aussage A N wahr sein. 01:14:26.090 --> 01:14:29.030 Also man ist hier gerade in der Situation, dass man zeigen will, eine 01:14:29.030 --> 01:14:30.330 Menge ist gleich N0. 01:14:31.070 --> 01:14:34.790 Und da macht man genau das, was gerade eben Bestandteil der Definition 01:14:34.790 --> 01:14:34.990 ist. 01:14:35.070 --> 01:14:37.370 Man zeigt erstens, die 0 ist da drin. 01:14:38.770 --> 01:14:42.710 Und man zeigt zweitens, wenn eine Zahl N da drin ist, dann auch N plus 01:14:42.710 --> 01:14:43.050 1. 01:14:44.190 --> 01:14:47.790 Und dann nach dieser Eigenschaft der natürlichen Zahlen, wenn das 01:14:47.790 --> 01:14:50.410 klappt, dann weiß man, M ist gleich N0. 01:14:51.890 --> 01:14:54.490 Das ist einfach diese Eigenschaft, die man da ausnutzt. 01:14:55.290 --> 01:14:56.330 So, was muss man da tun? 01:14:56.730 --> 01:15:00.910 Also man muss zeigen, 0 ist in M, das heißt A 0 ist wahr. 01:15:01.770 --> 01:15:02.710 Das muss man zeigen. 01:15:04.790 --> 01:15:06.090 Und was muss man noch zeigen? 01:15:06.150 --> 01:15:09.210 Man muss zeigen, wenn N drin ist, dann auch N plus 1. 01:15:09.210 --> 01:15:12.170 N in M heißt, A N ist wahr. 01:15:13.390 --> 01:15:16.370 N plus 1 in M heißt, A N plus 1 ist wahr. 01:15:16.810 --> 01:15:20.530 Also man muss zeigen, wenn A N wahr ist, dann ist auch A N plus 1 01:15:20.530 --> 01:15:20.810 wahr. 01:15:22.750 --> 01:15:24.910 Wohlgemerkt, man muss hier eine Implikation zeigen. 01:15:25.010 --> 01:15:28.030 Man muss nicht zeigen, A N ist wahr oder so etwas. 01:15:28.130 --> 01:15:31.130 Man muss zeigen, wenn das eine wahr ist, dann auch das nächste. 01:15:33.070 --> 01:15:33.950 Ja, so. 01:15:40.610 --> 01:15:43.330 Also das macht man dann bei so einer vollständigen Induktion. 01:15:43.450 --> 01:15:47.530 Man zeigt, A 0 ist wahr und man zeigt, wenn A N wahr ist, dann auch A 01:15:47.530 --> 01:15:50.330 N plus 1 für jedes N aus N 0. 01:15:53.030 --> 01:15:56.470 Und das erste nennt man dann typischerweise den Induktionsanfang. 01:15:58.230 --> 01:16:03.650 Und dieses zweite für jedes N gilt, wenn A N wahr ist, dann auch A N 01:16:03.650 --> 01:16:05.650 plus 1, das nennt man den Induktionsschritt. 01:16:08.590 --> 01:16:11.750 Und dieses A N, da muss man also so eine Implikation beweisen. 01:16:12.110 --> 01:16:14.350 Wenn A N wahr ist, dann auch A N plus 1. 01:16:14.970 --> 01:16:18.030 Und was man dann tut, ist, man verwendet die sogenannte 01:16:18.030 --> 01:16:19.190 Induktionsvoraussetzung. 01:16:19.770 --> 01:16:23.030 A N ist schon wahr für ein beliebiges N. 01:16:23.130 --> 01:16:25.290 Also wie beweist man, dass das für jedes N gilt? 01:16:25.390 --> 01:16:27.010 Man sagt, na, ich nehme einfach irgendeins. 01:16:27.550 --> 01:16:28.650 Ich weiß nicht welches. 01:16:29.290 --> 01:16:31.970 Alles, was ich jetzt tue, soll für jedes funktionieren. 01:16:31.970 --> 01:16:34.770 Und wenn das so ist, dann funktioniert es eben für jedes. 01:16:36.430 --> 01:16:38.590 Also A N heißt Induktionsvoraussetzung. 01:16:39.510 --> 01:16:44.330 Und man benutzt dann die Annahme, A N ist wahr, und muss dann folgern, 01:16:44.510 --> 01:16:45.830 A N plus 1 ist auch wahr. 01:16:47.010 --> 01:16:50.970 Also hier bei unserer Aussage, Länge von W hoch N ist N mal Länge von 01:16:50.970 --> 01:16:51.230 W. 01:16:53.870 --> 01:16:55.090 Induktionsanfang N gleich 0. 01:16:55.170 --> 01:16:58.590 Wir müssen zeigen, Länge von W hoch 0 ist gleich 0 mal Länge von W. 01:16:59.790 --> 01:17:02.530 Naja, dann nehmen Sie eben die Definition, wie gerade schon gesehen. 01:17:02.630 --> 01:17:05.370 Das ist 0 und dann schreibt man es vielleicht nochmal in der Form, wie 01:17:05.370 --> 01:17:06.190 man es haben möchte. 01:17:06.430 --> 01:17:07.530 0 mal Länge von W. 01:17:08.050 --> 01:17:08.810 N ist ja 0. 01:17:10.650 --> 01:17:12.410 Und dann kommt der Induktionsschritt. 01:17:13.890 --> 01:17:15.670 Und nochmal, was müssen wir tun? 01:17:15.750 --> 01:17:17.350 Wir müssen so eine Implikation zeigen. 01:17:17.430 --> 01:17:22.490 Wir müssen zeigen, wenn die Länge von W hoch N, N mal Länge von W ist, 01:17:22.650 --> 01:17:26.690 dann die Länge von W hoch N plus 1 ist N plus 1 mal Länge von W. 01:17:29.290 --> 01:17:31.570 Gut, also tun wir das. 01:17:33.470 --> 01:17:35.530 Also Induktionsvoraussetzung, AN ist wahr. 01:17:35.890 --> 01:17:38.430 Und wie zeigen wir, dass das für jedes N gilt? 01:17:38.510 --> 01:17:39.910 Wir nehmen einfach irgendeins. 01:17:40.590 --> 01:17:44.510 Keine weiteren Annahmen, N ist gerade oder eine Primzahl oder 01:17:44.510 --> 01:17:44.870 irgendwas. 01:17:45.110 --> 01:17:46.490 Einfach irgendeins. 01:17:47.490 --> 01:17:48.730 Ohne weitere Einschränkungen. 01:17:48.810 --> 01:17:50.630 Wenn es für irgendeins gilt, dann gilt es für jedes. 01:17:52.190 --> 01:17:54.030 Und wir nehmen an, AN ist wahr. 01:17:54.210 --> 01:17:56.510 Also Länge von W hoch N ist N mal Länge von W. 01:17:56.510 --> 01:17:58.190 Und was müssen wir jetzt zeigen? 01:17:58.330 --> 01:18:00.070 Ja, dann ist auch AN plus 1 wahr. 01:18:00.250 --> 01:18:02.650 Also Länge von W hoch N plus 1 ist N plus 1 mal Länge von W. 01:18:03.030 --> 01:18:06.550 Und dann schreibt man eben diese Induktion, diese Rechnung hin von 01:18:06.550 --> 01:18:06.870 eben. 01:18:07.310 --> 01:18:10.970 Und dann gibt es eben diese eine Stelle, wenn man das so macht, da 01:18:10.970 --> 01:18:13.830 steht, kommt vor in der Rechnung die Länge von W hoch N. 01:18:14.410 --> 01:18:17.070 Und dann ist man an der Stelle, wo man die Induktionsvoraussetzung 01:18:17.070 --> 01:18:21.170 anwenden kann und weiß, ah, für N weiß ich das. 01:18:21.230 --> 01:18:23.790 Die Länge von W hoch N ist N mal die Länge von W. 01:18:23.790 --> 01:18:25.970 Das darf ich hier ersetzen. 01:18:27.030 --> 01:18:30.010 Und dann rechnet man fröhlich weiter und landet genau da, wo man 01:18:30.010 --> 01:18:30.650 hinkommen will. 01:18:31.270 --> 01:18:32.090 Und ist fertig. 01:18:38.710 --> 01:18:44.730 Und das wird in Grundbegriffe immer wieder auftauchen und das wird 01:18:44.730 --> 01:18:48.090 auch später in Vorlesungen an allen möglichen und unmöglichen Stellen, 01:18:48.350 --> 01:18:51.710 wo Sie es jetzt noch nicht vermuten, auch wieder auftauchen. 01:18:52.650 --> 01:18:55.550 Zum Beispiel im Programmieren bei While-Schleifen. 01:18:58.850 --> 01:18:59.490 So. 01:19:00.070 --> 01:19:01.690 Und das ist der einfachste Fall. 01:19:01.950 --> 01:19:06.170 Hier so Null und für jede Zahl, auch die nächstgrößere, gibt ganz N 01:19:06.170 --> 01:19:06.430 Null. 01:19:07.590 --> 01:19:09.010 Davon gibt es jetzt Varianten. 01:19:11.210 --> 01:19:14.150 Ich habe Ihnen hier mal drei hingeschrieben. 01:19:14.610 --> 01:19:18.370 Die einfachste, gucken wir uns jetzt vielleicht gerade noch an. 01:19:21.990 --> 01:19:25.150 Manchmal ist es irgendwie natürlich, nicht bei Null anzufangen, 01:19:25.290 --> 01:19:27.230 sondern man hat irgendwas nur ab Eins. 01:19:28.730 --> 01:19:30.550 Ja, dann macht man es halt ab Eins. 01:19:30.790 --> 01:19:33.530 Also dann ist der Induktionsanfang im einfachen Fall einfach für N 01:19:33.530 --> 01:19:34.290 gleich Eins. 01:19:35.830 --> 01:19:40.890 Und dann auch wieder für jede Zahl N, wenn N dazugehört. 01:19:40.990 --> 01:19:43.150 Wenn es für N klappt, dann auch für N plus Eins. 01:19:44.670 --> 01:19:48.350 Das passt ins Originalschema, wenn Sie sozusagen aus diesen Aussagen, 01:19:48.410 --> 01:19:52.450 die für N gleich Eins vorhanden sind, durch Umnummerieren Aussagen 01:19:52.450 --> 01:19:53.970 machen, wo ab Null nummeriert wird. 01:19:54.110 --> 01:19:59.950 B Null ist A Eins, B Eins ist A Zwei, B I ist A I plus Eins. 01:20:00.690 --> 01:20:04.710 Und dann die normale vollständige Induktion für die Bs ab Null liefert 01:20:04.710 --> 01:20:08.290 Ihnen die Korrektheit der As ab Eins. 01:20:08.830 --> 01:20:10.130 Das ist ganz harmlos. 01:20:12.110 --> 01:20:12.670 So. 01:20:13.730 --> 01:20:17.410 Und wir gucken gleich noch ein Schnipselchen Video. 01:20:17.410 --> 01:20:20.810 Und vorher vielleicht schon mal als Ausblick. 01:20:24.150 --> 01:20:28.510 Bei dem Induktionsschritt, was wir bisher haben, ist, na ja, man muss 01:20:28.510 --> 01:20:31.070 zeigen, wenn A N gilt, dann auch A N plus Eins. 01:20:31.810 --> 01:20:35.290 Anders gesagt, um zu beweisen, dass A N plus Eins wahr ist, was Sie 01:20:35.290 --> 01:20:37.510 haben, ist, Sie können A N benutzen. 01:20:39.410 --> 01:20:43.810 Aber jetzt so anschaulich, also man hat sich da ja ab Null so langsam 01:20:43.810 --> 01:20:45.010 vorgearbeitet. 01:20:45.010 --> 01:20:48.750 Es sollte eigentlich auch okay sein, nicht nur A N, sondern auch noch 01:20:48.750 --> 01:20:52.810 früher andere Aussagen mit kleineren Indizien zu benutzen. 01:20:53.210 --> 01:20:55.050 Die sind ja auch schon irgendwie... 01:20:55.050 --> 01:20:57.090 Für die kann man ja auch beweisen, dass sie wahr sind. 01:20:58.330 --> 01:21:02.110 Also manchmal ist es bequemer, wenn man nicht nur ein bisschen 01:21:02.110 --> 01:21:03.810 zurückgucken kann, sondern ein bisschen weiter. 01:21:03.930 --> 01:21:06.370 Und das werden wir uns das nächste Mal angucken, dass das völlig legal 01:21:06.370 --> 01:21:06.630 ist. 01:21:06.710 --> 01:21:07.450 Das dürfen Sie machen. 01:21:08.570 --> 01:21:09.910 Hat keiner was dagegen. 01:21:10.710 --> 01:21:17.110 Das zweite Hinweis, es gibt etwas, das ist etwas verblüffend. 01:21:19.130 --> 01:21:25.010 Manchmal, wichtig, aufgemerkt, manchmal wird vollständige Induktion 01:21:25.010 --> 01:21:31.310 leichter, wenn das, was Sie beweisen, sozusagen mehr ist, schwieriger 01:21:31.310 --> 01:21:31.650 ist. 01:21:34.050 --> 01:21:38.650 Vollständige Induktionen werden manchmal einfacher zu führen, wenn Sie 01:21:38.650 --> 01:21:41.510 nicht nur das beweisen, was Sie beweisen wollen, sondern ein bisschen 01:21:41.510 --> 01:21:41.870 mehr. 01:21:42.890 --> 01:21:46.250 Dann muss man zwar immer ein bisschen mehr beweisen, aber beim 01:21:46.250 --> 01:21:50.770 Induktionsschritt, in der Induktionsvoraussetzung steht halt auch ein 01:21:50.770 --> 01:21:51.550 bisschen mehr. 01:21:51.910 --> 01:21:53.370 Und das hilft einem dann manchmal. 01:21:54.510 --> 01:21:57.390 Also wundern Sie sich nicht, wenn Sie irgendwann mal über sowas 01:21:57.390 --> 01:21:58.010 stolpern. 01:21:58.870 --> 01:22:01.930 So, so weit zu dem Stoff heute. 01:22:02.590 --> 01:22:06.170 Und jetzt kommen wir zu dem zweiten Schnipselchen aus dem Video. 01:22:06.170 --> 01:22:09.790 Und Sie können dann auf dem Weg in die nächste Lehrveranstaltung oder 01:22:09.790 --> 01:22:14.390 in die Mensa oder wohin auch immer ja mal überlegen, was da passiert. 01:22:17.580 --> 01:22:21.700 Es gibt einen Unterschied zwischen den natürlichen Zahlen und dieser 01:22:21.700 --> 01:22:22.420 Gartenmauer. 01:22:22.500 --> 01:22:23.680 Die Gartenmauer ist endlich. 01:22:26.140 --> 01:22:29.120 Und Sie können jetzt mal überlegen kurz, was passiert. 01:22:30.620 --> 01:22:32.560 Und dann gucken wir uns das mal an. 01:22:34.560 --> 01:22:36.100 Viel Spaß beim Nachdenken. 01:22:37.440 --> 01:22:38.320 Los geht's. 01:22:43.360 --> 01:22:44.420 So, Achtung jetzt. 01:22:53.350 --> 01:22:53.790 Ups. 01:22:55.290 --> 01:22:56.830 Ja, überlegen Sie mal, was da los ist. 01:22:57.330 --> 01:22:58.390 Machen Sie es gut, bis Freitag.