WEBVTT 00:10.540 --> 00:12.680 So, einen wunderschönen guten Morgen. 00:13.660 --> 00:18.560 Dann machen wir weiter jetzt mit den Grundbegriffen der Informatik und 00:18.560 --> 00:22.520 nachdem wir uns letztes Mal mit formalen Sprachen beschäftigt hatten 00:22.520 --> 00:27.460 und wir bei der Definition von formalen Sprachen schon das Prinzip der 00:27.460 --> 00:32.600 vollständigen Induktion kennengelernt hatten, gibt es jetzt einen 00:32.600 --> 00:36.660 Zwischenschub, bevor wir dann mit dem eigentlichen Beweisen durch 00:36.660 --> 00:39.280 Induktion weitermachen. 00:39.420 --> 00:43.520 Wir beschäftigen uns jetzt noch zwischendurch mit der Aussagenlogik. 00:44.280 --> 00:47.380 Auch die Aussagenlogik ist ein ganz wichtiges und grundlegendes 00:47.380 --> 00:49.400 Kapitel der Informatik. 00:49.660 --> 00:53.580 Ist Ihnen allen schon mal zumindest irgendwie informell begegnet, wie 00:53.580 --> 00:57.260 Sie aussagenlogische Aussagen treffen können, zum Beispiel in der 00:57.260 --> 00:58.320 Mathematik in der Schule. 00:58.720 --> 01:01.580 Und hier in der Informatik werden wir das Ganze jetzt halt 01:01.580 --> 01:06.400 entsprechend schön formalisieren, sodass wir also umfassend 01:06.400 --> 01:08.580 aussagenlogische Formeln erstellen können. 01:09.620 --> 01:12.860 Also wir werden also nicht nur lernen, aussagenlogische Formeln 01:12.860 --> 01:17.920 korrekt zu formulieren, sondern wir werden auch schauen, wie können 01:17.920 --> 01:21.860 wir aussagenlogische Formeln beweisen, wie können wir Sachen in der 01:21.860 --> 01:25.760 Aussagenlogik ableiten, sodass wir Beweise herstellen können. 01:27.060 --> 01:29.820 Wie ich schon sagte, informell sind Ihnen allen schon mal 01:29.820 --> 01:35.600 aussagenlogische Formeln, aussagenlogische Begriffe begegnet. 01:35.900 --> 01:39.400 Wir machen das informell in der Regel so, dass wir Aussagen haben und 01:39.400 --> 01:43.660 diese Aussagen können entweder wahr sein oder sie können falsch sein. 01:44.300 --> 01:47.480 Wenn Sie sich zurückerinnern an diese Abbildung, die wir da hatten, 01:47.600 --> 01:48.780 die nannte sich Unicode. 01:49.500 --> 01:55.340 Da wurde aus dem Alphabet der Unicode Zeichen abgebildet auf die Code 01:55.340 --> 01:59.760 Points, natürliche Zahlen und dann kann man zum Beispiel sagen, die 01:59.760 --> 02:03.620 Aussage machen, die Abbildung Unicode ist injektiv. 02:04.600 --> 02:08.880 Oder ich könnte die Aussage treffen, die Abbildung Unicode zum 02:08.880 --> 02:10.080 Beispiel ist sujektiv. 02:11.360 --> 02:13.460 Jetzt ist die Frage, jetzt erinnern Sie sich zurück an diese 02:13.460 --> 02:15.500 Abbildung, war diese Abbildung Unicode? 02:15.660 --> 02:16.940 War die injektiv? 02:18.300 --> 02:19.240 Wer ist für ja? 02:19.380 --> 02:19.920 Hand hoch. 02:21.240 --> 02:22.040 Wer ist für nein? 02:22.180 --> 02:23.080 Wer sagt, es ist falsch? 02:23.740 --> 02:25.400 Okay, genau, die war injektiv. 02:25.500 --> 02:26.840 War die Abbildung sujektiv? 02:27.060 --> 02:27.620 Wer sagt ja? 02:29.000 --> 02:30.980 Keiner, also alle richtig geraten. 02:32.020 --> 02:35.220 Das heißt, wir können solchen Aussagen objektive Wahrheitswerte 02:35.220 --> 02:35.800 zuordnen. 02:36.020 --> 02:39.140 Wir können sagen, solche Aussagen sind entweder wahr oder solche 02:39.140 --> 02:40.300 Aussagen sind falsch. 02:42.580 --> 02:45.800 Manche Aussagen, die wir formulieren, denen können wir auch überhaupt 02:45.800 --> 02:47.840 keinen Wahrheitswert zuordnen. 02:47.940 --> 02:50.180 Solche Aussagen sind unsinnig. 02:50.520 --> 02:52.140 Hier ist so ein typisches Beispiel. 02:52.740 --> 02:56.620 Ein Babir ist ein Mann, der genau all diejenigen Männer rasiert, die 02:56.620 --> 02:57.620 sich nicht selbst rasieren. 02:58.360 --> 02:59.840 Ist das eine wahre Aussage? 03:02.980 --> 03:05.700 Wenn es keine wahre Aussage ist, ist es eine falsche Aussage? 03:07.900 --> 03:09.380 Auch keine falsche Aussage. 03:10.080 --> 03:12.480 Wenn man uns das überlegt, also ein Babir ist ein Mann, der all genau 03:12.480 --> 03:14.560 diejenigen Männer rasiert, die sich nicht selbst rasieren. 03:14.560 --> 03:15.660 Was ist denn dann mit dem Babir? 03:16.560 --> 03:17.780 Rasiert der Babir sich selber? 03:19.940 --> 03:23.820 Na, kann ja nicht sein, weil wenn er sich selber rasieren würde, dann 03:23.820 --> 03:26.680 würde er sich ja selber rasieren, aber das geht nicht, weil ein Babir 03:26.680 --> 03:29.380 nur genau diejenigen Männer rasiert, die sich eben nicht selber 03:29.380 --> 03:30.040 rasieren. 03:33.040 --> 03:36.940 Und der genau alle diejenigen rasiert, die sich nicht selber rasieren. 03:37.040 --> 03:38.760 Das heißt, es darf eigentlich auch keinen anderen geben, der ihn 03:38.760 --> 03:39.160 rasiert. 03:40.480 --> 03:43.220 Weil dann wäre er nicht mehr derjenige, der all genau diejenigen 03:43.220 --> 03:45.860 Männer rasiert, die sich nicht selber rasieren, weil er rasiert sich 03:45.860 --> 03:46.320 ja nicht selber. 03:47.480 --> 03:51.840 Das heißt also, das ist eine Aussage, die kann man, da kann man gar 03:51.840 --> 03:53.220 keinen Wahrheitswert zuordnen. 03:53.340 --> 03:57.000 So, das ist eine Aussage, die man zum Beispiel da nicht als 03:57.000 --> 04:02.660 aussagenlogische Formel formulieren könnte, weil wir in der 04:02.660 --> 04:06.160 Aussagenlogik eben fordern, dass wir jede Aussage, die wir aufstellen, 04:06.520 --> 04:09.940 diesen Wahrheitswert wahr oder falsch zuordnen können. 04:11.640 --> 04:16.580 Wenn wir jetzt so zwei Aussagen haben, nennen wir sie p und q, seien 04:16.580 --> 04:20.340 beliebige Aussagen, dann wollen wir auch erlauben, dass wir diese 04:20.340 --> 04:24.440 Aussagen irgendwie verknüpfen, dass wir mit diesen Aussagen neue 04:24.440 --> 04:25.600 Aussagen konstruieren. 04:26.180 --> 04:28.500 Wir können zum Beispiel die Sache negieren. 04:28.960 --> 04:31.180 Wir können zum Beispiel sagen, die Aussage p gilt nicht. 04:32.240 --> 04:36.180 Oder wir können halt die beiden Aussagenformeln logisch miteinander 04:36.180 --> 04:36.740 verknüpfen. 04:36.840 --> 04:40.380 Wir können sagen, die Aussage p gilt und die Aussage q gilt. 04:41.360 --> 04:44.820 Oder wir können sie mit einem logischen oder verknüpfen. 04:44.980 --> 04:48.760 Wir können entweder sagen, wir sagen p gilt oder q gilt. 04:49.340 --> 04:53.040 Und dann haben wir noch als weiteres Konstrukt die logische Folgerung. 04:54.020 --> 04:59.720 Man sagt entweder p impliziert q oder man spricht es häufig wenn p 04:59.720 --> 05:00.640 dann q. 05:01.960 --> 05:03.400 Und jetzt kommt was ganz Wichtiges. 05:04.160 --> 05:07.200 Gerade bei dieser letzten logischen Folgerung. 05:07.880 --> 05:11.720 Diese logische Folgerung ist nicht das, was sie als Kausalität kennen. 05:12.520 --> 05:15.140 Diejenigen von Ihnen, die schon ein bisschen Statistik gemacht haben, 05:15.260 --> 05:16.280 kennen den alten Lehrsatz. 05:16.940 --> 05:19.260 Korrelation ist nicht gleich Kausalität. 05:20.040 --> 05:24.720 Nur weil zwei Dinge gleichzeitig passieren, heißt das nicht, dass sie 05:24.720 --> 05:27.880 eine Folge sind oder wenn zwei Dinge hintereinander passieren. 05:28.540 --> 05:30.800 Gilt nicht post hoc ergo propte hoc. 05:30.940 --> 05:35.460 Also nicht, weil etwas nach etwas passiert, passiert es deswegen. 05:36.260 --> 05:38.360 Die Sonne geht nicht auf, weil der Hahn schreit. 05:39.300 --> 05:42.440 Auch wenn der Hahn schreit und danach immer die Sonne aufgeht. 05:42.520 --> 05:45.420 Das hat das nichts damit zu tun, dass der Hahn schreit. 05:45.680 --> 05:47.440 Das ist nicht der Grund dafür, dass die Sonne geht. 05:48.460 --> 05:53.980 Und diese Kausalität bei Statistik, die gilt genauso, dieses nicht 05:53.980 --> 05:57.960 vorhandenseinende Kausalität bei Statistik, die gilt genauso bei der 05:57.960 --> 05:58.780 Aussagenlogik. 06:00.280 --> 06:04.020 Auch wenn es heißt, P impliziert Q, dann heißt das nicht, dass 06:04.020 --> 06:07.480 zwischen P und Q irgendein kausaler Zusammenhang sein muss. 06:07.860 --> 06:08.740 Der existiert nicht. 06:09.780 --> 06:11.680 Kann man ein einfaches Beispiel aufstellen? 06:15.000 --> 06:22.120 Zum Beispiel im Jahr 2014 gab es in Japan etwa 4,7 Millionen PKWs, die 06:22.120 --> 06:23.180 neu zugelassen wurden. 06:24.400 --> 06:28.240 Und im Jahr 1999 gab es in Deutschland etwa 11,2 Millionen 06:28.240 --> 06:29.080 Internetnutzer. 06:30.000 --> 06:32.700 Das sind Aussagen, denen können wir in den Wahrheitswert werfen. 06:32.860 --> 06:33.640 Wahr oder falsch. 06:34.700 --> 06:35.740 Und die sind beide wahr. 06:36.500 --> 06:39.380 Und dann kann man auch sagen, wenn P, dann Q. 06:40.680 --> 06:43.160 Aber es dürfte keinen überraschen, dass überhaupt kein kausaler 06:43.160 --> 06:44.920 Zusammenhang erhält. 06:45.200 --> 06:48.680 Also es gab nicht in 1999 in Deutschland 11,2 Millionen 06:48.680 --> 06:58.880 Internetnutzer, weil es 2014 in Japan 4,7 Millionen PKWs neu 06:58.880 --> 06:59.560 zugelassen wurden. 06:59.920 --> 07:03.360 Also eine Kausalität hat nichts zu tun mit den Wahrheitswerten der 07:03.360 --> 07:04.120 Aussagenlogik. 07:05.820 --> 07:08.500 Jede Aussage ist entweder wahr oder falsch, oder sie ist keine 07:08.500 --> 07:09.640 Aussagenlogische Formel. 07:10.040 --> 07:13.320 Und sie werden zusammengesetzt aus den Wahrheitswerten der Teil 07:13.320 --> 07:13.760 -Aussagen. 07:14.220 --> 07:17.640 Also aus diesen Konstruktionen, die wir hatten, dieses Nicht-P, P oder 07:17.640 --> 07:22.760 Q, P und Q, aus den einzelnen Wahrheitswerten dieser Teil-Aussagen 07:22.760 --> 07:25.860 setzen wir hinterher den Wahrheitswert der gesamten Aussage zusammen. 07:27.040 --> 07:31.420 Aber es gibt keinen Inhalt, der irgendwas mit Kausalität zu tun hat, 07:31.700 --> 07:34.100 der irgendwas mit der Semantik der Aussagen zu tun hat. 07:34.660 --> 07:38.080 Sondern wir gehen rein nach den objektiven Wahrheitswerten und setzen 07:38.080 --> 07:41.040 daraus neue Wahrheitswerte zusammen. 07:45.670 --> 07:48.310 Das Erste, was wir immer machen, wenn wir uns solche Konstrukte 07:48.310 --> 07:51.150 anschauen, das Erste ist, wir schauen uns an, was ist die Syntax? 07:51.510 --> 07:55.690 Also wie schreibe ich syntaktisch korrekte aussagenlogische Formeln 07:55.690 --> 07:55.910 hin? 07:56.790 --> 08:00.510 Und wenn ich das kann, dann mache ich als nächsten Schritt, wie 08:00.510 --> 08:03.990 berechne ich jetzt die Wahrheitswerte dieser aussagenlogischen 08:03.990 --> 08:06.770 Formeln, die ich immerhin syntaktisch korrekt hinschreiben kann? 08:07.430 --> 08:12.190 Das ist ungefähr so, als wenn Sie lernen, wie setzt man Wörter in 08:12.190 --> 08:14.450 einer Sprache korrekt zusammen, um einen Satz zu machen? 08:15.270 --> 08:18.210 Und danach kümmere ich mich darum, was hat das überhaupt für eine 08:18.210 --> 08:18.710 Bedeutung? 08:20.530 --> 08:26.050 Wenn wir jetzt Aussagenlogik machen, dann können wir zurückgreifen auf 08:26.050 --> 08:28.250 das, was wir gelernt haben in den formalen Sprachen. 08:28.870 --> 08:33.810 Wir können jetzt die Aussagenlogik, die Menge aller syntaktisch 08:33.810 --> 08:39.270 korrekten aussagenlogischen Formeln, als eine Sprache auffassen, als 08:39.270 --> 08:40.330 eine formale Sprache. 08:40.610 --> 08:43.210 Und damit wir es als formale Sprache auffassen können, brauchen wir 08:43.210 --> 08:44.250 als erstes ein Alphabet. 08:45.330 --> 08:49.710 Und dieses Alphabet der aussagenlogischen Formeln, das setzen wir 08:49.710 --> 08:53.010 zusammen aus zwei Teilalphabeten. 08:53.730 --> 08:57.550 Das erste ist das Alphabet der aussagenlogischen Variablen. 08:58.230 --> 09:03.150 Wir legen uns also ein Alphabet her und sagen, das Alphabet der 09:03.150 --> 09:07.690 aussagenlogischen Variablen, das ist eine Teilmenge von dieser Menge, 09:07.830 --> 09:08.550 die so aussieht. 09:08.670 --> 09:12.910 Es gibt p mit dem Index i und die i sind aus den N Null. 09:15.190 --> 09:19.090 Es gibt also irgendwelche Variablen p mit einem unteren Index und der 09:19.090 --> 09:21.550 Index kommt aus der Menge der natürlichen Variablen. 09:22.210 --> 09:26.550 Jetzt sehen Sie da oben ein Teilmengensymbol. 09:27.970 --> 09:30.450 Und wenn Sie noch in die Schule zurück sich erinnern, da gab es 09:30.450 --> 09:31.830 manchmal zwei Teilmengensymbol. 09:31.930 --> 09:35.270 Es gab das Teilmengensymbol, so wie wir es kennengelernt haben und es 09:35.270 --> 09:38.770 gab das Teilmengensymbol ohne diesen Strich unter dem Halbkreis. 09:39.750 --> 09:44.430 Und dieser ohne diesen Strich unter dem Halbkreis bedeutete, es musste 09:44.430 --> 09:45.770 eine echte Teilmenge sein. 09:45.890 --> 09:49.570 Das heißt, die Teilmenge dürfte nicht gleich der Menge sein. 09:49.810 --> 09:50.970 Wir kennen das jetzt aber nicht. 09:51.670 --> 09:53.330 Wir definieren das als Teilmenge. 09:53.910 --> 09:55.850 Darf das Ganze denn aber gleich sein? 09:56.050 --> 10:01.810 Also dürfte das Alphabet der aussagenlogischen Variablen, dürfte das 10:01.810 --> 10:05.610 gleich sein der Menge a la PI mit I aus N0. 10:06.890 --> 10:07.590 Wer ist für Ja? 10:09.770 --> 10:10.970 Wer ist für Nein? 10:12.930 --> 10:13.970 Warum Nein? 10:16.960 --> 10:19.140 Genau, ein Alphabet muss endlich sein. 10:19.560 --> 10:22.740 Ein Alphabet ist eine nicht leere endliche Menge von Zeichen und 10:22.740 --> 10:23.200 Symbolen. 10:24.020 --> 10:28.180 Diese Menge da, PI mit I Element N0, ist offensichtlich unendlich, 10:28.280 --> 10:30.080 weil die Menge natürlich in Zahlen unendlich ist. 10:30.460 --> 10:33.760 Das heißt, streng genommen muss das Alphabet der aussagenlogischen 10:33.760 --> 10:36.400 Variablen eine echte Teilmenge von dieser Menge sein. 10:37.360 --> 10:38.940 Und dann haben wir eine zweite Menge. 10:39.040 --> 10:42.360 Wir nennen das die Menge der aussagenlogischen Konnektive. 10:43.420 --> 10:46.420 Und das sind die hier in blau gezeichneten Konnektive. 10:46.500 --> 10:50.940 Und hier kommt ins Spiel, dass Farbe irgendwie eine Bedeutung hat. 10:51.500 --> 10:54.680 Und Farbe hat hier die Bedeutung, dass alles was irgendwie blau ist, 10:55.140 --> 10:58.060 das soll jetzt zu dem Alphabet der Aussagenlogik gehören. 10:58.620 --> 11:02.520 Das sind einmal diese Konnektive, der Pfeil, dieses Zeichen, das wir 11:02.520 --> 11:04.980 für die Negation verwenden, dieses Dach, das wir für das 11:04.980 --> 11:09.700 aussagenlogische Und verwenden und das Oder, dieses umgekehrte Dach 11:09.700 --> 11:11.620 für das aussagenlogische Ort Oder. 11:12.000 --> 11:14.900 Und wenn wir die Menge vereinigen mit der Menge der Variablen der 11:14.900 --> 11:19.760 Aussagenlogik, dann bekommen wir das Alphabet der aussagenlogischen 11:19.760 --> 11:20.800 Variablen. 11:24.650 --> 11:29.530 Jetzt muss ich irgendwie über diesem Alphabet syntaktisch korrekte 11:29.530 --> 11:31.030 Wörter bilden. 11:32.250 --> 11:35.330 Und ein Wort ist dann entsprechend eine aussagenlogische Variable. 11:35.450 --> 11:38.710 Jetzt ist die Frage, wie können wir da syntaktisch korrekte Wörter 11:38.710 --> 11:39.130 bilden? 11:39.530 --> 11:42.690 Das Erste, was wir halt machen könnten, okay, wir können versuchen mit 11:42.690 --> 11:44.570 Abbildungen Wörter zu bilden. 11:45.350 --> 11:47.370 Wir nennen sowas dann Konstruktionsabbildung. 11:48.010 --> 11:51.490 Und haben zum Beispiel die eine Abbildung, wir nennen sie F nicht, die 11:51.490 --> 11:55.870 bildet halt ab aus den, von den Wörtern der Aussagenlogik in die 11:55.870 --> 12:00.250 Wörter der Aussagenlogik und die bildet jedes Wort aus der 12:00.250 --> 12:06.870 Aussagenlogik, Wörtern der Aussagenlogik ab, auf, Klammer auf, nicht 12:06.870 --> 12:10.010 dieses Wort, das ich rausnehme, Klammer zu. 12:10.930 --> 12:14.130 Und genau das gleiche mache ich mit Wörtern. 12:15.470 --> 12:18.310 Diese Verknüpfung mache ich mit zwei Wörtern, zum Beispiel mit dem 12:18.310 --> 12:18.810 Unzeichen. 12:18.890 --> 12:20.830 Dann bilde ich halt ab aus dem kathesischen Produkt. 12:22.050 --> 12:26.410 Menge aller aussagenlogischen Wörter mit sich selber, also eine Menge 12:26.410 --> 12:30.210 aller Wörter über dem Alphabet der Aussagenlogik, kathesisches Produkt 12:30.210 --> 12:34.150 mit sich selber und wird dann abgebildet, wieder ein Wort aus dieser 12:34.150 --> 12:39.590 klinischen Hülle der Aussagenlogik, des Aussagenlogischen Alphabetes. 12:39.730 --> 12:44.110 G und H werden dann abgebildet, auf, Klammer auf, G und H, Klammer zu. 12:45.190 --> 12:51.450 Damit kann ich syntaktisch korrekte Aussagenlogische Wörter bilden, 12:51.650 --> 12:52.650 Formeln bilden. 12:54.090 --> 12:58.470 Beispielsweise hier unten kann ich aus P, wenn Q und R kann ich daraus 12:58.470 --> 13:02.150 machen, wenn P dann Q und R. 13:02.850 --> 13:08.110 Ich kann aber nach wie vor syntaktisch falsche Aussagenlogische 13:08.110 --> 13:10.230 Formeln bilden. 13:10.270 --> 13:13.450 Wenn ich zum Beispiel das UND anwende auf diesem Nicht-Pfeil, Klammer 13:13.450 --> 13:16.970 zu, und dann habe ich als zweites ER und ODER. 13:17.230 --> 13:19.550 Das sind beides Wörter aus dieser klinischen Hülle bei dem 13:19.550 --> 13:23.330 Aussagenlogischen Alphabet und kann daraus was Neues bilden und es 13:23.330 --> 13:26.090 kommt was raus, was offensichtlich nicht irgendwie syntaktisch korrekt 13:26.090 --> 13:29.490 zu sein scheint oder nicht syntaktisch korrekt sein sollte, wenn ich 13:29.490 --> 13:33.390 im Hinterkopf habe, welche Bedeutung ich jetzt so diesen einzelnen 13:33.390 --> 13:35.650 Zeichen, den Konnektiven, dazugewiesen habe. 13:37.090 --> 13:39.550 So eine Abbildung vergrößert immer die Anzahl der Konnektive, 13:39.650 --> 13:42.810 logischerweise, und ich kann halt auch noch Quatsch hervor. 13:43.390 --> 13:47.010 Das heißt, mit diesen Konstruktionsabbildungen alleine komme ich 13:47.010 --> 13:51.070 offensichtlich nicht zurecht, wenn ich jetzt nur die syntaktisch 13:51.070 --> 13:52.590 korrekten Wörter bilden will. 13:53.170 --> 13:56.470 Und was war so eine typische Technik, die wir jetzt auch schon ein 13:56.470 --> 13:58.610 paar mal gesehen haben an einfachen Beispielen? 13:59.230 --> 14:02.630 Wie kann ich noch formale Sprachen definieren? 14:03.930 --> 14:04.790 Was kann ich noch machen? 14:06.870 --> 14:08.110 Ich gehe Induktiv vor. 14:08.850 --> 14:11.810 Haben Sie schon an so kleinen Beispielen gesehen, an so 14:11.810 --> 14:15.210 Billigbeispielen, wie man Induktiv etwas definieren kann und auch 14:15.210 --> 14:16.410 Sprachen definieren kann. 14:17.510 --> 14:27.090 Und jetzt kann ich auch das hier definieren, mithilfe eines induktiven 14:27.090 --> 14:27.670 Vorgehens. 14:28.390 --> 14:30.970 Vorher noch kurz die Lesarten, also wie wir da sprechen, hatte ich 14:30.970 --> 14:31.430 schon gesagt. 14:31.510 --> 14:36.370 Das eine nennen wir nicht g, g und h, g oder h, wenn g, dann h, oder 14:36.370 --> 14:39.630 aus g folgt h, g impliziert h. 14:41.050 --> 14:45.470 Gerade dieses, wenn g, dann h, oder aus g folgt h, ist halt immer ein 14:45.470 --> 14:47.530 bisschen problematisch, muss man immer dran denken. 14:48.130 --> 14:50.850 Kausalität hat das nichts zu tun, das ist rein auf die Wahrheitswerte 14:50.850 --> 14:51.290 bezogen. 14:52.830 --> 14:57.730 Wenn ich jetzt also syntaktisch korrekte Formeln haben will, dann kann 14:57.730 --> 15:00.710 ich mithilfe dieser Konstruktionsabbildung das machen, wenn ich 15:00.710 --> 15:01.710 Induktiv vorgehe. 15:02.590 --> 15:05.490 Und wenn ich Induktiv vorgehe, dann muss ich irgendwie anfangen, 15:05.610 --> 15:08.270 irgendwas von kleiner nach größer. 15:08.330 --> 15:11.810 Ich muss irgendwo bei irgendwas 0 anfangen und muss dann immer 15:11.810 --> 15:15.890 definieren, wenn etwas n hat, wie sieht dann das aus, dass n plus 1 15:15.890 --> 15:16.170 hat. 15:16.610 --> 15:19.230 Das heißt, beim induktiven Vorgehen muss man sich also als erstes 15:19.230 --> 15:22.530 überlegen, okay, was sollen diese Zahlen bedeuten, wofür stehen die? 15:23.030 --> 15:25.410 Wir hatten einmal gesehen, das stand zum Beispiel einmal für die Länge 15:25.410 --> 15:29.430 der Worte, als wir so diese klinische Hülle Induktiv definiert haben, 15:29.490 --> 15:32.470 haben wir immer gesagt, die Mengen mit der Worte Länge 0, Länge der 15:32.470 --> 15:34.430 Worte 1, Länge der Worte 2 und so weiter. 15:34.570 --> 15:38.410 Wenn ich Menge der Worte Länge n habe, dann komme ich auf die Menge 15:38.410 --> 15:40.850 der Worte mit Länge n plus 1, wenn ich das mache. 15:41.410 --> 15:44.190 Hier hatten wir gesagt, bei den Konstruktionsabbildungen, so eine 15:44.190 --> 15:48.030 Konstruktionsabbildung vergrößert immer die Anzahl der Konnektive. 15:48.850 --> 15:55.570 Das heißt, hier kann ich mir sowas überlegen, wie häufig, wie ich 15:55.570 --> 15:57.950 kann, dass ich also die Anzahl der Konnektive erhöhe. 15:58.490 --> 16:01.170 Nur das Problem ist, da waren ja mehrere Konnektive. 16:01.250 --> 16:04.190 Da waren immer Klammer auf, Klammer zu und dann noch ein weiteres 16:04.190 --> 16:04.490 Zeichen. 16:04.650 --> 16:07.310 Das heißt, es wird eigentlich nur über drei Konnektive erhöht und 16:07.310 --> 16:11.470 dieses plus drei kennen wir noch nicht, aber das Erhöhen der 16:11.470 --> 16:13.450 Konnektive haben wir gemacht durch Anwendung der 16:13.450 --> 16:15.390 Konstruktionsabbildung. 16:16.010 --> 16:18.870 Das heißt, hier könnte ich zum Beispiel den Index darüber laufen 16:18.870 --> 16:22.830 lassen, wie häufig ich schon eine Konstruktionsabbildung angewandt 16:22.830 --> 16:23.050 habe. 16:24.190 --> 16:25.910 Und dann fange ich an mit 0. 16:26.090 --> 16:30.050 Das heißt, ich habe noch keine einzelne Konstruktionsabbildung 16:30.050 --> 16:35.150 angewandt, wie sollen dann aussagenlogische Formeln aussehen? 16:35.330 --> 16:38.390 Und dann kann man sich überlegen, okay, ich habe Variablen und 16:38.390 --> 16:39.030 Konnektive. 16:39.590 --> 16:42.230 Die Konnektive will ich einführen durch die Konstruktionsabbildung. 16:42.310 --> 16:45.130 Ich habe noch keine Konstruktionsabbildung angewandt, also bleiben mir 16:45.130 --> 16:49.830 nur die Variablen übrig und dementsprechend ist halt die Menge der 16:49.830 --> 16:54.230 aussagenlogischen Formeln, die halt null Konnektive haben, genau 16:54.230 --> 16:57.590 gleich der Menge der Variablen der aussagenlogischen Formeln. 16:59.170 --> 17:04.930 Und wenn ich jetzt die Menge habe m der aussagenlogischen Formeln, bei 17:04.930 --> 17:08.550 der ich schon n mal so eine Konstruktionsabbildung angewandt habe, 17:09.650 --> 17:15.070 kann ich jetzt übergehen auf dieses n plus 1, indem ich das einfach 17:15.070 --> 17:19.110 vereinige, indem ich einmal die Konstruktionsabbildung für nicht 17:19.110 --> 17:24.330 anwende, für und anwende, für oder anwende und für die Implikation 17:24.330 --> 17:24.790 anwende. 17:25.830 --> 17:28.610 Und dann habe ich sozusagen einmal den gesamten Satz der 17:29.470 --> 17:33.370 Konstruktionsanwendung zusätzlich angewandt und habe dann mein n plus 17:33.370 --> 17:33.770 1. 17:34.490 --> 17:36.650 Und wir erinnern uns, wir hatten das auch schön definiert. 17:37.130 --> 17:39.490 Hier haben wir jetzt eine Funktion, da steht keine einzige 17:39.490 --> 17:43.830 aussagenlogische Formel drin, sondern da steht als Argument eine Menge 17:43.830 --> 17:47.050 von aussagenlogischen Formeln. 17:47.050 --> 17:49.570 Aber auch Sie erinnern sich, auch das hatten wir definiert, wie das 17:49.570 --> 17:53.450 ausschaut, wenn wir eine Abbildung anwenden auf eine Menge von Dingen. 17:54.110 --> 17:58.650 Dann ist das nämlich gerade die Menge derjenigen, Werte, 17:58.790 --> 18:02.390 Funktionswerte, die ich bekomme, wenn ich jedes einzelne Element aus 18:02.390 --> 18:06.070 dieser ursprünglichen Menge anwende in dieser Funktion und dann die 18:06.070 --> 18:09.570 Funktionswerte halt in eine Menge reintue und diese Menge erhalte. 18:10.230 --> 18:16.110 Und dann kann ich halt definieren, dass die Formeln der Aussagenlogik 18:16.110 --> 18:19.230 eben gerade die Vereinigung ist über alle diese mm. 18:20.150 --> 18:26.710 Also genauso wie bei den Wörtern bestimmter Länge und daraus dann die 18:26.710 --> 18:27.830 klinische Hülle abzuleiten. 18:29.790 --> 18:33.470 Also einfaches Beispiel angenommen, wir lassen zwei Variablen zu. 18:34.250 --> 18:36.150 Dann ist m0 gleich p und q. 18:36.890 --> 18:39.190 Und damit wir es ein bisschen einfacher haben, schreiben wir jetzt 18:39.190 --> 18:44.190 halt nicht p1, p2 oder p0, p1, sondern wir nennen die einfach um. 18:44.490 --> 18:46.950 Also aus p0 wird halt p und aus p1 wird q. 18:47.630 --> 18:50.130 Also m0 gleich p und q. 18:52.010 --> 18:55.170 Wenden jetzt die Konstruktionsabbildung an und bekommen jede Menge 18:55.170 --> 18:58.030 neuer syntaktisch korrekter Formeln. 18:58.130 --> 19:02.550 Wir bekommen nicht p, nicht q, p und p, p und q, q und p und q und q. 19:03.290 --> 19:08.050 Was man da schon sieht, ist die Reihenfolge bei den Konnektiven ist 19:08.050 --> 19:08.770 wichtig. 19:09.550 --> 19:14.350 Wir haben vorne als Argumente ja auch immer drinstehen, dass a 19:14.350 --> 19:16.090 kathesische Produkte zweier Mengen. 19:16.210 --> 19:17.730 Das heißt es werden Tupen reingesteckt. 19:18.490 --> 19:22.110 Dementsprechend ist also auch hier bei den Wörtern die Reihenfolge 19:22.110 --> 19:26.050 wichtig und p und q ist erstmal prinzipiell was anderes, ein anderes 19:26.050 --> 19:27.130 Wort als q und p. 19:28.090 --> 19:31.090 Ergibt sich aus der Definition, wie wir Wörter definiert haben, ergibt 19:31.090 --> 19:35.510 sich automatisch daraus, wie wir vorne dieses kathesische Produkt da 19:35.510 --> 19:36.250 reinstecken. 19:37.790 --> 19:41.290 Und auf die Art und Weise kann ich jetzt also alle aussagenlogischen 19:41.290 --> 19:45.710 Formeln bilden, bei denen die Menge der Funktionen der Konnektive alle 19:45.710 --> 19:49.550 einmal angewandt wurden und habe daraus aus der Vereinigung dann 19:49.550 --> 19:50.310 entsprechend die Menge. 19:52.330 --> 19:56.770 Dann kann man halt m2 aufmalen, da wird es dann schon relativ groß. 19:57.370 --> 20:00.370 Da enthält das dann zum Beispiel halt solche Dinge wie nicht, nicht p, 20:01.190 --> 20:07.590 q oder nicht q, p oder q und p, p wenn p, dann q wenn, dann wenn q, 20:07.730 --> 20:09.810 dann p und so weiter und so fort. 20:10.710 --> 20:13.290 Was man hier jetzt sieht, das sind relativ viele Klammern. 20:14.270 --> 20:18.270 Das macht das Lesen solcher Formeln anstrengend, macht das unschön. 20:18.910 --> 20:23.970 Das heißt eine Sache, die wir machen ist, dass wir Abkürzungen 20:23.970 --> 20:30.690 einführen, Klammern sparen und zusätzlich noch ein weiteres, eine 20:30.690 --> 20:34.250 weitere Abkürzung einführen, diesen Doppelfeil. 20:35.150 --> 20:40.930 Wir schreiben diesen Doppelfeil, wenn wir g, Doppelfeil h, wenn wir 20:40.930 --> 20:42.510 eigentlich diese Formel meinen. 20:42.750 --> 20:45.850 Das heißt wir können diesen Doppelfeil zusammensetzen aus diesem 20:45.850 --> 20:50.290 einfachen Pfeil, indem wir einfach sagen, wenn g, dann h und wenn h, 20:50.510 --> 20:52.930 dann g, dann schreiben wir das mit diesem Doppelfeil. 20:56.190 --> 20:58.530 Und Klammern lassen wir weg. 20:58.910 --> 21:02.310 Die ganz äußeren Klammer einer aussagenlogischen Formel lassen wir 21:02.310 --> 21:02.890 erstmal weg. 21:03.290 --> 21:04.150 Die brauchen wir nicht. 21:04.730 --> 21:09.970 Wenn das ein und dasselbe Konjektiv mehrfach vorkommt und geklammert 21:09.970 --> 21:13.150 ist, dann nehmen wir implizit eine Linksklammerung an. 21:13.210 --> 21:16.650 Dann nehmen wir implizit an, dass von links nach rechts nach außen 21:16.650 --> 21:18.850 dann geklammert wird, also p und q und r. 21:19.070 --> 21:22.630 Das tun wir so, als sei das p und q in Klammern und dann und r. 21:23.090 --> 21:25.090 Und die äußeren Klammern können wir sowieso weglassen. 21:25.990 --> 21:30.350 Wenn wir jetzt verschiedene Konjektive haben, dann weisen wir denen 21:30.350 --> 21:31.890 verschiedene Bindungsstärken zu. 21:31.990 --> 21:33.310 Das kennen Sie schon aus dem Programmieren. 21:34.050 --> 21:37.170 Das Nichts sagen wir bindet am stärksten, danach bindet das Und, 21:37.510 --> 21:41.430 danach bindet das Oder, dann kommt die Implikation und ganz zum 21:41.430 --> 21:43.990 Schluss dieser Doppelfeil, diese Abkürzung für diese zwei 21:43.990 --> 21:45.870 zusammengesetzten Implikationen. 21:46.550 --> 21:50.470 Das heißt also, wenn ich so eine Formel habe, p, wenn, p oder r, dann 21:50.470 --> 21:55.410 nicht q und r, dann weiß ich, okay, das Nicht, das bindet am 21:55.410 --> 21:58.230 stärksten, das heißt um das Nicht-q muss ich als erstes eine 21:58.230 --> 22:02.930 Klammerung setzen, dann muss ich nachgucken, als zweitstärkstes bindet 22:02.930 --> 22:07.870 das Und, da muss ich also alles, das Und, das Nicht-q und r als 22:07.870 --> 22:10.910 nächstes klammern, dann muss ich mich um das Oder kümmern, dann wird 22:10.910 --> 22:16.510 also links das p oder r geklammert und dann kommt erst der Folgefeil 22:16.510 --> 22:18.650 und der wird dann entsprechend geklammert. 22:19.730 --> 22:22.690 Und auf die Art und Weise macht man das Ganze deutlich übersichtlicher 22:22.690 --> 22:24.590 und deutlich lesbarer. 22:26.750 --> 22:29.730 Jetzt sind wir soweit, dass wir also syntaktisch korrekte 22:30.190 --> 22:32.470 Aussagenlogische Formeln hinschreiben können und wir können einer 22:32.470 --> 22:35.270 Formel auch ansehen, schon mal, wir können es noch nicht beweisen, 22:35.390 --> 22:37.670 aber wir können es zumindest schon mal ansehen, dass das Ganze 22:37.670 --> 22:39.010 syntaktisch korrekt ist. 22:39.410 --> 22:42.310 Wenn man es beweisen wollte, wäre eine Möglichkeit, dass man halt 22:42.310 --> 22:47.430 entsprechend die Konstruktion hinschreibt, dieser Formel. 22:47.910 --> 22:50.190 Die Frage ist jetzt, was bedeutet das Ganze? 22:50.310 --> 22:52.150 Was bedeutet so eine Aussagenlogische Formel? 22:52.210 --> 22:54.170 Wie weise ich da einen Wahrheitswert vor? 22:55.110 --> 22:58.470 Und das geht zurück auf die sogenannten bool'schen Funktionen. 22:58.730 --> 23:03.450 Die wurden eingeführt von George Schmul, Mathematiker, Logiker, 23:03.630 --> 23:08.270 Philosoph aus dem 17. 23:08.510 --> 23:15.550 Jahrhundert, war in Irland Professor und hatte halt seine Ideen halt 23:15.550 --> 23:16.890 entsprechend, also schon aus dem 19. 23:17.070 --> 23:20.490 Jahrhundert, und hat seine Ideen halt entsprechend hingeschrieben in 23:20.490 --> 23:24.170 diesem Buch, An Investigation of Laws of Thought, on which are founded 23:24.170 --> 23:27.530 the mathematical theories of logic and probabilities. 23:28.290 --> 23:31.590 Also mit anderen Worten, sowas wie der erste mathematische Logiker, 23:31.710 --> 23:35.410 der mathematische Logik nicht nur in natürlicher Sprache ausgedrückt 23:35.410 --> 23:38.570 hat, sondern das Ganze schön in mathematischen Formeln hingeschrieben 23:38.570 --> 23:38.810 hat. 23:39.530 --> 23:43.370 Und der hat halt Funktionen aufgestellt und diese nennen wir die 23:43.370 --> 23:44.950 bool'schen Funktionen. 23:44.970 --> 23:49.430 Und diese bool'schen Funktionen weisen jetzt Aussagenlogischen Formeln 23:49.430 --> 23:50.450 Wahrheitswerte zu. 23:51.770 --> 23:56.930 Die Wahrheitswerte, also wahr oder falsch, zeichnen, kürzen wir ab, 23:56.990 --> 23:59.110 schreiben wir hin durch W oder F. 23:59.950 --> 24:02.710 Das heißt, bei solchen bool'schen Funktionen, wenn die Wahrheitswerte 24:02.710 --> 24:06.550 zuordnen sollen, dann muss der Zielbereich dieser Funktionen eben 24:06.550 --> 24:08.870 gerade diese bool'sche Menge sein. 24:09.190 --> 24:10.630 W, W und F. 24:11.970 --> 24:18.630 Und die bool'schen Funktionen bilden jetzt erst mal ab aus Tupeln, aus 24:18.630 --> 24:22.190 K -Tupeln, auf Wahrheitswerte. 24:22.530 --> 24:25.670 Das heißt, ich habe irgendein K-Tupel mit Wahrheitswerten, habe also K 24:25.670 --> 24:29.830 -Werte, wahr oder falsch, in einer bestimmten festgelegten Reihenfolge 24:29.830 --> 24:34.030 und daraus soll dann ein einziger Wahrheitswert wahr oder falsch 24:34.030 --> 24:34.730 gemacht werden. 24:35.830 --> 24:38.850 Und für jedes dieser Konnektive gibt es halt eine Funktion, die das 24:38.850 --> 24:39.710 entsprechend macht. 24:41.270 --> 24:43.410 Die sind hier jetzt mal alle aufgezeichnet. 24:43.510 --> 24:46.550 Die Konnektive haben entweder ein oder zwei Argumente. 24:46.690 --> 24:49.190 Das Nicht hat ein Argument, alle anderen haben zwei Argumente. 24:49.870 --> 24:56.770 Das heißt, für das Nicht reicht ein Ein-Tupel aus, weil das hier x1, 24:56.850 --> 25:00.630 für alle anderen brauche ich aber ein Tupel, x1, x2. 25:01.170 --> 25:05.970 Und alle Möglichkeiten für x1 und x2 aus dieser Menge mit dem Wahr 25:05.970 --> 25:09.330 -Falsch kann man halt schön so systematisch hinschreiben als Stabelle. 25:09.330 --> 25:12.950 Und dann kann man einfach aufschreiben, was sind die Funktionswerte, 25:13.030 --> 25:15.290 diese bool'schen Funktionen, jetzt diesem Tupel zuordnen. 25:15.850 --> 25:18.970 Man sieht das Nicht, macht halt aus einem Falsch einen Wahr und aus 25:18.970 --> 25:20.390 einem Wahr macht es einen Falsch. 25:21.250 --> 25:26.410 Das Und verlangt, dass sowohl der erste als auch der zweite Wert wahr 25:26.410 --> 25:30.210 ist und dann macht es daraus einen Wahr und ansonsten macht es für 25:30.210 --> 25:34.490 alle anderen Tupel, alle anderen Funktionswerte daraus einen Falsch. 25:35.010 --> 25:38.890 Bei dem Oder ist es entsprechend umgekehrt, das ist immer wahr, außer 25:38.890 --> 25:42.670 wenn beide Werte falsch sind, dann ist halt das das Oder falsch und 25:42.670 --> 25:45.830 jetzt kommt das Impliziert und das ist ein bisschen interessant. 25:47.270 --> 25:48.910 Da kann man folgendes daraus ableiten. 25:49.010 --> 25:54.410 Man sieht, wenn links F steht, dann kommt immer wahr raus. 25:55.210 --> 26:00.390 Wenn der zweite Wert F ist, dann kann nur wahr rauskommen, wenn der 26:00.390 --> 26:01.850 erste Wert wahr ist. 26:02.230 --> 26:06.250 Aber wenn der erste Wert wahr ist und der zweite Wert F, dann kommt 26:06.250 --> 26:06.890 falsch raus. 26:07.790 --> 26:11.010 Und daraus gibt es etwas, das kennen Sie aus der Mathematik, ist ein 26:11.010 --> 26:13.090 Prinzip bei dem Beweisen. 26:13.610 --> 26:17.390 Wenn Sie beweisen in der Mathematik, dann kennen Sie den alten 26:17.390 --> 26:20.190 Lehrsatz aus Falschem lässt sich alles beweisen. 26:21.710 --> 26:27.210 Und das ist im Prinzip das Ganze jetzt angewandt auf Bool'sche Logik. 26:27.670 --> 26:31.370 Wenn ich etwas habe, was falsch ist, wenn ich also eine Aussage habe, 26:31.430 --> 26:35.550 die falsch ist, dann ist das, was da rauskommt, was ich daraus 26:35.550 --> 26:39.690 folgere, was daraus impliziert, völlig egal, ob das wahr oder falsch 26:39.690 --> 26:44.750 ist, sondern die Aussage, wenn etwas falsch ist, dann andere Aussage, 26:45.150 --> 26:45.870 ist immer wahr. 26:47.530 --> 26:52.150 Allerdings, wenn die erste Aussage wahr ist, dann kann ich daraus nur 26:52.150 --> 26:54.850 Wahres folgen, aber nichts Falsches mehr. 27:03.110 --> 27:06.310 Bei den Notationen sehen Sie manchmal andere Notationen. 27:06.390 --> 27:08.890 Also wir schreiben in der Regel das nicht mit diesem Strich, mit dem 27:08.890 --> 27:09.750 kleinen Haken dran. 27:10.510 --> 27:13.890 Manche schreiben es so, dass sie so einen Querstrich über die Variable 27:13.890 --> 27:14.230 machen. 27:14.770 --> 27:18.170 Wir schreiben das und immer mit dem Dach und dem umgedrehten Dach. 27:18.710 --> 27:22.130 Manche verwenden dafür ein Malzeichen oder ein Pluszeichen. 27:24.330 --> 27:27.390 Und bei der Implikation verwendet man in der Regel eigentlich immer 27:27.390 --> 27:29.530 den Fall. 27:30.230 --> 27:33.090 Was man macht, wenn man diese Plus-, Mal- und den Querstrich 27:33.090 --> 27:36.430 verwendet, dann verwendet man häufig nicht W und F für wahr und 27:36.430 --> 27:39.490 falsch, sondern man verwendet häufig 0 und 1. 27:39.970 --> 27:41.550 0 für falsch, 1 für wahr. 27:42.250 --> 27:45.950 Wir machen das hier in der Vorlesung explizit nicht, damit man klar 27:45.950 --> 27:48.950 ist, das ist hier keine Arithmetik oder irgendwas, sondern es sind 27:48.950 --> 27:52.750 hier boolsche aussagenlogische Formeln und dann erkenne ich anhand der 27:52.750 --> 27:56.530 Notationen gleich, ob ich hier Arithmetik betreibe oder ob ich hier 27:56.530 --> 27:58.230 wirklich Aussagenlogik betreibe. 28:00.330 --> 28:04.790 Das Interessante ist, diese boolschen Funktionen sind eigentlich 28:04.790 --> 28:05.930 überspezifiziert. 28:06.790 --> 28:12.410 Das heißt, ich könnte theoretisch mit weniger boolschen Funktionen 28:12.410 --> 28:12.870 auskommen. 28:13.590 --> 28:19.830 Ich kann einige boolschen Funktionen relativ leicht aus anderen 28:19.830 --> 28:22.210 boolschen Funktionen zusammensetzen. 28:22.410 --> 28:25.790 Zum Beispiel diesen Implikations- Pfeil, das wenn x dann y. 28:26.870 --> 28:41.270 Stattdessen könnte ich auch schreiben nicht x oder y und hätte daraus 28:41.270 --> 28:45.310 die gleiche Abbildung. 28:46.990 --> 28:50.890 Das kann man sich einfach klar machen, indem man die komplette 28:52.070 --> 28:54.650 Funktionswertetafel aufschreibt, also wieder x und y, alle möglichen 28:54.650 --> 28:57.770 Belegungen und dann guckt man sich halt an, nicht x, wissen wir was 28:57.770 --> 29:01.230 das ist, wahr, wahr, falsch, falsch und dann gucken wir uns an, nicht 29:01.230 --> 29:05.650 x oder y, da kommt dann halt raus, wahr, wahr, falsch, wahr und das 29:05.650 --> 29:08.050 ist eben genau der gleiche Funktionswert, als wenn ich diesen 29:08.050 --> 29:09.370 Implikations -Pfeil verwende. 29:09.950 --> 29:12.750 Das heißt, eigentlich könnte ich bei den boolschen Funktionen auf den 29:12.750 --> 29:16.990 Implikations -Pfeil verzichten und würde vollständig mit nicht, oder 29:16.990 --> 29:17.990 und und auskommen. 29:23.500 --> 29:27.180 Jetzt müssen wir uns immer noch darum kümmern, was ist jetzt die 29:27.180 --> 29:30.160 Semantik einer Formel? 29:30.460 --> 29:31.440 Was bedeutet sie? 29:32.360 --> 29:35.640 Und damit man diese Semantik irgendwie im Rechner fassen und 29:35.640 --> 29:41.260 verarbeiten kann, arbeitet man mit sogenannten Interpretationen. 29:42.100 --> 29:46.320 Der Kern einer jeden Aussagenlogischen Formel ist erstmal, dass ich da 29:46.320 --> 29:50.440 Variablen habe und ich mit dieser Tabelle diesen Variablen 29:50.440 --> 29:52.980 irgendwelche Werte zuweise, von falsch oder wahr. 29:53.640 --> 29:56.880 Und diese Zuweisung, die ich mache, wenn ich also die Variablen 29:56.880 --> 30:00.840 belege, eine Variablenbelegung hernehme mit falsch oder wahr, jeder 30:00.840 --> 30:04.920 Variable in der Formel den Wert falsch oder wahr zuordne, dann nenne 30:04.920 --> 30:06.560 ich das eine Interpretation. 30:07.700 --> 30:10.820 Formal ist jetzt wieder eine Interpretation eine Abbildung, die 30:10.820 --> 30:14.760 abbildet von den Variablen hin in diese Menge der bool'schen Werte. 30:16.020 --> 30:22.360 Und wenn ich mich interessiere für alle möglichen Belegungen, die ich 30:22.360 --> 30:26.200 habe, die ich machen kann, dann gibt es dafür eine spezielle Notation. 30:26.460 --> 30:27.740 Das ist dieses b hoch v. 30:28.480 --> 30:32.440 Das ist eine Notation, die bedeutet, wenn ich zwei Mengen habe, a hoch 30:32.440 --> 30:37.420 b, dann ist das die Menge aller Interpretationen von b nach a. 30:37.780 --> 30:42.420 Und dementsprechend b hoch v, die Menge aller Abbildungen von v nach b 30:42.420 --> 30:46.600 und damit die Menge aller möglichen Interpretationen für eine 30:47.880 --> 30:52.680 aussagenlogische Formel, die die Variablen v benutzt. 30:57.050 --> 31:02.650 Um jetzt also den Wert zu bekommen einer zusammengesetzten komplexen 31:02.650 --> 31:06.410 aussagenlogischen Formel, verwende ich jetzt wieder eine zweite 31:06.410 --> 31:06.930 Funktion. 31:07.050 --> 31:12.350 In diesem Fall, zweite Funktion, nenne ich den Value, den Wert einer 31:12.350 --> 31:15.750 Formel f unter einer Interpretation i. 31:16.970 --> 31:20.690 Das heißt, ich habe also eine Variablenbelegung, ich habe eine Formel 31:20.690 --> 31:24.450 und will jetzt daraus, so wie bei den bool'schen Funktionen, bei den 31:24.450 --> 31:28.050 einfachen Konjektiven, will jetzt aus dieser komplexen Formel damit 31:28.050 --> 31:30.090 den Wahrheitswert herausbekommen. 31:31.950 --> 31:36.010 Und das definiert man jetzt wieder so, dass man das Ganze mehr oder 31:36.010 --> 31:45.170 weniger induktiv definiert und sagt, jede Variable x und jede Formel g 31:45.170 --> 31:50.310 und h ist halt der Wert der Variable x, gerade der Wert der 31:50.310 --> 31:53.370 Interpretation dieser Variable x. 31:55.030 --> 32:03.930 Für nicht g, für g eine Formel, ist der Wert dieser Formel g unter der 32:03.930 --> 32:09.010 Interpretation i gerade eben der Wert der bool'schen Funktion von dem 32:09.010 --> 32:12.750 nicht, von dem Wert der eigentlichen Funktion g selber. 32:13.590 --> 32:14.750 Und genauso bei den uns. 32:15.150 --> 32:18.750 Wenn ich den Wert von g und h haben will, dann ist das halt der Wert 32:18.750 --> 32:22.350 der bool'schen Funktion von und und dann diese Werte-Funktion, die 32:22.350 --> 32:25.250 Value -Funktion reingezogen auf die g's und die h's. 32:26.130 --> 32:29.370 Das ist sowas ein bisschen wie eine umgekehrtes induktive Definition. 32:29.610 --> 32:33.550 Statt von unten nach oben fange ich jetzt von den komplexen hin zu den 32:33.550 --> 32:37.770 weniger komplexen an, indem ich diese Value-Funktion immer nach innen 32:37.770 --> 32:38.470 reinziehe. 32:41.730 --> 32:44.750 Einfaches Beispiel, wenn ich also jetzt die Formel habe, nicht p und 32:44.750 --> 32:49.170 q, und ich habe die Variablenbelegung p gleich wahr und q gleich 32:49.170 --> 32:52.950 falsch, dann kann ich das einfach der Reihe nach auflösen. 32:53.330 --> 32:56.290 Das ist also dann nicht von Value von i, p und q. 32:57.030 --> 33:00.270 Das ist wiederum bool'sche Funktion nicht, von der bool'schen Funktion 33:00.270 --> 33:04.230 und, von Value p und Value q. 33:04.850 --> 33:08.010 Gut, Value p und Value q, das ist halt die Interpretation von p und q, 33:08.110 --> 33:11.210 da gucke ich oben nach, da muss einmal w und einmal f rein und dann 33:11.210 --> 33:14.430 habe ich da stehen halt und von w wahr und falsch. 33:14.650 --> 33:17.090 Das kann ich ausrechnen, kann ich direkt nachgucken in der Tabelle. 33:17.490 --> 33:20.050 Das ist halt falsch und dann habe ich da stehen die bool'sche Funktion 33:20.050 --> 33:23.510 nicht von falsch, kann ich wieder in der Tabelle nachgucken, kommt 33:23.510 --> 33:24.110 wahr bei raus. 33:25.290 --> 33:28.150 Und so kann man das dann entsprechend für beliebig komplexe, 33:28.230 --> 33:32.050 zusammengesetzte Aussagen, logische Formeln ausrechnen. 33:32.490 --> 33:36.410 Damit man es relativ einfach machen kann, macht man das häufig in 33:36.410 --> 33:40.730 solchen Tabellen, dass man also komplexe bool'sche Funktionen auflöst 33:40.730 --> 33:42.710 in ihre kleineren Bestandteile. 33:42.870 --> 33:46.750 Vorne schreibt man halt alle möglichen Belegungen hin und dann setzt 33:46.750 --> 33:53.250 man halt entsprechend die Sachen zusammen aus den einzelnen 33:53.250 --> 33:56.990 Funktionen, die ich halt haben möchte und die ich brauche und dann 33:56.990 --> 34:00.990 hinterher daraus die komplexe Funktion, zum Beispiel dieses nicht p 34:00.990 --> 34:02.750 und q zusammenzusetzen. 34:02.870 --> 34:05.450 Man kann dann für jede Interpretation einen Wahrheitswert anschauen 34:05.450 --> 34:08.130 und wenn die Interpretation gegeben ist, kann ich halt in der Tabelle 34:08.130 --> 34:11.370 nachschauen und kann nicht genau nachgucken. 34:13.490 --> 34:17.010 Wenn wir jetzt zum Beispiel die letzte Spalte und die drittletzte 34:17.010 --> 34:18.090 Spalte vergleichen. 34:18.550 --> 34:21.470 In der rechten Spalte, da haben wir die Wahrheitswerte unseres 34:21.470 --> 34:23.910 ursprünglichen Beispieles, dieses nicht p und q. 34:25.150 --> 34:30.210 In der linken Spalte haben wir jetzt stehen nicht p oder nicht q. 34:31.030 --> 34:34.670 Und die haben für alle Interpretationen, für alle Belegungen der 34:34.670 --> 34:39.410 Variablen, kommt der gleiche Wert raus, weil i von der Formel immer 34:39.410 --> 34:40.150 derselbe Wert. 34:42.030 --> 34:46.750 Das heißt, die haben irgendwie immer die gleiche Auswertung, egal 34:46.750 --> 34:50.050 dafür welchen Wert ich reinstecke. 34:50.670 --> 34:53.310 Bei p und q, das hat eine andere Auswertung. 34:53.670 --> 34:56.670 Nicht p und nicht q haben auch andere Auswertungen, aber nicht p oder 34:56.670 --> 35:00.950 nicht q hat die gleiche Auswertung wie nicht p und q, unabhängig von 35:00.950 --> 35:02.110 der Variablenbelegung. 35:02.790 --> 35:07.050 Und wenn das der Fall ist, dann sagen wir, dass zwei solche Formeln 35:07.050 --> 35:08.710 miteinander äquivalent sind. 35:09.290 --> 35:15.330 Zwei Formeln g und h sind eben äquivalent, wenn für jede 35:15.330 --> 35:19.510 Interpretation gilt, dass diese Auswertung unter der Interpretation 35:19.510 --> 35:24.050 der Formel den gleichen Wert ergibt, egal ob es jetzt g oder h ist. 35:24.730 --> 35:29.050 Und wenn zwei Formeln miteinander sind, dann schreiben wir das eben 35:29.050 --> 35:32.390 mit diesem Dreierstrich, g äquivalent h. 35:33.310 --> 35:37.330 Ein Beispiel haben wir schon gesehen, also nicht p oder nicht q ist 35:37.330 --> 35:42.170 äquivalent zu nicht p und q, oder auch leicht einfach klar machen kann 35:42.170 --> 35:48.570 man sich, nicht nicht p ist äquivalent zu p, oder halt wenn p dann q 35:48.570 --> 35:52.270 ist eben äquivalent zu nicht p oder q. 35:54.570 --> 35:58.210 Jetzt, wenn man sich überlegt, was hat dieser letzte Fall zu bedeuten, 35:58.310 --> 36:03.250 ich hatte Ihnen schon gesagt, das ist dieses, aus Falschen kann alles 36:03.250 --> 36:05.850 folgen und aus Wahren kann nur Wahres kommen. 36:09.270 --> 36:13.510 Wenn ich mir also das angucke, was soll das Gegenteil sein, wenn p 36:13.510 --> 36:20.710 dann q, dann soll das heißen, das Gegenteil ist, dass ich etwas Wahres 36:20.710 --> 36:22.690 habe und etwas Falsches. 36:23.010 --> 36:25.970 Dass ich an erster Stelle etwas Wahres habe und dann kommt etwas 36:25.970 --> 36:26.770 Falsches. 36:27.690 --> 36:32.670 Also muss also p, wenn p, q, äquivalent sein zu genau zu dem 36:32.670 --> 36:33.270 Gegenteil. 36:33.990 --> 36:35.810 Und das Gegenteil erhalte ich halt durch die Negierung. 36:35.990 --> 36:39.790 Also wenn p dann q, muss eben äquivalent sein zu nicht p und nicht q. 36:40.530 --> 36:44.710 Und das ist wiederum äquivalent zu nicht p oder nicht nicht q. 36:45.410 --> 36:48.870 Und das ist wieder äquivalent zu nicht p oder q. 36:50.310 --> 36:53.630 Was wir jetzt hier als Überlegung so hingeschrieben haben, als 36:53.630 --> 36:58.890 informelle Überlegung, warum jetzt dieser Implikationsfall und die 36:58.890 --> 37:02.730 andere Formel äquivalent zueinander sind, das hat schon so etwas den 37:02.730 --> 37:05.510 Charakter eines Beweises. 37:06.370 --> 37:09.870 Wir haben uns da irgendwas überlegt, muss halt das Gegenteil von etwas 37:09.870 --> 37:13.950 sein und dann haben wir angefangen mit anderen Äquivalenzen, die wir 37:13.950 --> 37:17.830 kennen, die wir da oben niedergeschrieben haben, zu argumentieren, 37:18.270 --> 37:22.710 warum eben, wenn p, dann q, gerade nicht p oder q sein soll. 37:23.550 --> 37:27.650 Und dieses Beweisen von äquivalenten Formeln, das können wir ein 37:27.650 --> 37:28.790 bisschen systematischer machen. 37:28.890 --> 37:31.250 Das können wir ein bisschen formal schöner hinschreiben. 37:33.110 --> 37:35.930 Bevor wir das machen, noch eine kleine Randbemerkung. 37:37.650 --> 37:40.570 Wenn wir jetzt, wir machen ja alles in irgendwie Abbildungen oder 37:40.570 --> 37:43.970 Mengen, und wenn wir jetzt so eine Formel auffassen, dann können wir 37:43.970 --> 37:47.250 auch versuchen, so eine Formel als Abbildung aufzufassen. 37:47.950 --> 37:54.870 Und zwar soll diese Abbildung definiert sein über diese Wertzuweisung. 37:55.330 --> 37:59.430 Diese Wertzuweisung definiert halt, diese Wertfunktion y definiert 37:59.430 --> 38:04.290 halt für jede Formel und jede Interpretation eben diese Abbildung, 38:04.630 --> 38:08.330 Interpretation wird abgebildet auf den Wert der Funktion. 38:08.730 --> 38:12.690 Das könnte man jetzt also auch sagen, dass das die Abbildung ist, die 38:12.690 --> 38:13.850 auch diese Formel beschreibt. 38:14.430 --> 38:18.170 Diese also abbildet aus der Belegung, aus einer Interpretation, also 38:18.170 --> 38:21.210 aus der Menge aller möglichen Belegungen, b hoch v, also aller 38:21.210 --> 38:25.470 möglichen Abbildungen von b, v nach b, bildet die ab nach b und die 38:25.470 --> 38:29.630 bildet sie so ab, dass so eine Interpretation abgebildet wird auf yi 38:29.630 --> 38:34.730 von g. Man könnte jetzt sagen, das sei eine Formel, eine 38:34.730 --> 38:37.890 aussagenlogische Formel als Abbildung gefasst. 38:38.610 --> 38:41.150 Das hat allerdings eine kleine Unschönheit. 38:42.190 --> 38:47.170 Das hat die Unschönheit, dass zum Beispiel die Formel g gleich p0 und 38:47.170 --> 38:53.910 p0 und die Formel h gleich p2 und p2 plötzlich nicht äquivalent 38:53.910 --> 38:54.810 zueinander sind. 38:55.390 --> 38:57.270 Und das ist etwas, was wir eigentlich nicht wollen. 38:57.690 --> 39:00.130 Warum sind die jetzt auf einmal nicht mehr äquivalent zueinander? 39:00.930 --> 39:04.150 Naja, wenn ich jetzt eine Interpretation habe, wo ich sage p0 gleich 39:04.150 --> 39:09.230 wahr und p2 gleich falsch, dann ist das eine Interpretation. 39:10.310 --> 39:15.430 Aber die Wahrheitswerte yi von g und yi von h sind einmal wahr und 39:15.430 --> 39:16.090 einmal falsch. 39:16.690 --> 39:23.230 Und das widerspricht eben gerade der Definition unseres Begriffs 39:23.230 --> 39:24.030 Äquivalenz. 39:24.570 --> 39:26.170 Das ist eben gerade nicht Äquivalenz. 39:26.310 --> 39:29.890 Bei Äquivalenz müsste es für jede Belegung den gleichen Wert haben. 39:30.390 --> 39:31.810 Was ist die Krux dahinter? 39:32.250 --> 39:37.790 Die Krux dahinter ist, dass ich halt die Anzahl der Variablen, die ich 39:37.790 --> 39:42.150 sozusagen verwenden kann, nicht irgendwie gebunden sind an die Anzahl 39:42.150 --> 39:45.590 der Variablen, die überhaupt in den einzelnen Teilformeln vorkommen. 39:45.590 --> 39:50.770 Ich habe einmal p0 und einmal p2 und p1 gibt es gar nicht, aber ist 39:50.770 --> 39:54.870 auch bisher nach der Definition gar nicht verlangt worden, sondern ist 39:54.870 --> 39:57.410 nach wie vor einfach zulässig. 39:58.210 --> 40:01.490 Und damit man damit jetzt umgehen kann, gibt es zwei unterschiedliche 40:01.490 --> 40:02.210 Möglichkeiten. 40:02.750 --> 40:06.730 Die eine Möglichkeit wäre, dass man einschränkt die Menge aller 40:06.730 --> 40:10.570 möglichen Aussagen, logischen, korrekten Formeln, in denen man sagt, 40:10.770 --> 40:15.070 dass die Nummerierung, die vorkommt, die muss gerade so übereinstimmen 40:15.070 --> 40:17.450 mit der Anzahl der Variablen, die vorkommt. 40:17.810 --> 40:21.290 Wenn also nur eine Variable vorkommt in der Formel, dann darf die nur 40:21.290 --> 40:22.130 p0 heißen. 40:22.450 --> 40:25.710 Und wenn zwei Variablen vorkommen, dann dürfen die eben nur p0 und p1 40:25.710 --> 40:26.110 heißen. 40:26.470 --> 40:29.230 Und so eine Formel wie p2 und p2 will ich gar nicht haben. 40:29.990 --> 40:31.870 Das ist die eine Möglichkeit, wie man es machen kann. 40:32.490 --> 40:41.170 Die andere Möglichkeit ist, dass man diese Namen, diese konkreten 40:41.170 --> 40:45.890 Namen wegwirft und die Variablen und Formeln in einer gewissen Art und 40:45.890 --> 40:47.330 Weise umbenennt. 40:49.410 --> 40:55.110 Und das kann man machen mit so einer Abbildung, indem ich mir so ein K 40:55.110 --> 41:01.670 -Tupel hernehme von Wahrheitswerten und dann abbilde so ein Tupel X 41:01.670 --> 41:10.550 auf den Wert der Interpretation ix von g. Da ist jetzt natürlich die 41:10.550 --> 41:13.470 Frage, was soll diese Interpretation ix sein? 41:13.930 --> 41:17.230 Diese Interpretation ix definiere ich mir so. 41:18.310 --> 41:24.350 Angenommen, ich habe eine Menge von Variablen, p i1 bis p ik. 41:25.410 --> 41:28.090 Und die sind der Reihe nachgeordnet. 41:28.170 --> 41:30.870 Das heißt, es gibt irgendeinen kleinsten Index, was ich z.B. 41:30.970 --> 41:34.970 die Menge aller der Variablen p3, p7, p10. 41:35.370 --> 41:37.490 Da gibt es den kleinsten Index, das ist p3. 41:37.970 --> 41:39.550 Dann wäre i1 eben 3. 41:40.190 --> 41:42.190 Dann gibt es den höchsten Index, das ist p10. 41:42.550 --> 41:45.410 Da wäre also ik entsprechend 10. 41:45.850 --> 41:47.410 Und dann gab es dazwischen noch p5. 41:47.530 --> 41:50.790 Dann gibt es also dazwischen drin noch ein i2. 41:51.370 --> 41:52.930 Das heißt halt p5. 41:53.630 --> 41:59.210 Das heißt also, ich ordne diese Variablen, die vorkommen, anhand ihres 41:59.210 --> 42:01.890 Index der Reihe nach auf. 42:02.210 --> 42:03.510 Die müssen nicht kontinuierlich sein. 42:03.610 --> 42:05.470 Das muss nicht immer p1, p2, p3, p4 sein. 42:05.610 --> 42:07.690 Das kann... wir sind irgendwie aufgereiht. 42:07.750 --> 42:10.930 Es gibt den kleinsten und größten und der Reihenfolge nach werden die 42:10.930 --> 42:11.610 aufgereiht. 42:11.990 --> 42:14.650 Und dann am Ende stehen in dieser Menge k Variablen. 42:15.370 --> 42:18.090 Und diese k Variablen tue ich halt in so einem k Tupel. 42:19.170 --> 42:23.850 Und jetzt bilde ich jedes dieses pij ab auf den Index j. 42:24.650 --> 42:29.190 Das heißt, aus dem ersten p, dem pi1, das zum Beispiel im Beispiel p3 42:29.190 --> 42:33.010 sein könnte, aus dem wird jetzt nur noch der Index 3. 42:33.990 --> 42:39.310 Und aus dem höchsten, dem pi3 wäre es gewesen in unserem Beispiel. 42:39.430 --> 42:40.450 Das hatte den Index 10. 42:40.570 --> 42:41.210 Das war p10. 42:41.550 --> 42:43.210 Das war das pi3. 42:43.830 --> 42:44.890 Daraus wird halt ein 3. 42:45.470 --> 42:48.950 Das heißt, diesen Variablennamen werfe ich komplett weg, sondern ich 42:48.950 --> 42:52.250 zähle nur noch die Variablen der Reihe nach durch in einer bestimmten 42:52.250 --> 42:54.770 Reihenfolge und ersetze sie durch ihre Nummern. 42:57.170 --> 43:01.250 Und dabei ist es auch gar nicht wichtig, dass ich wirklich genauso 43:01.250 --> 43:06.050 viele Variablen in meiner Menge habe, wie ich auch hinterher in der 43:06.050 --> 43:07.410 Aussagenlogischen Formel habe. 43:07.830 --> 43:11.350 Es reicht vollständig aus, wenn ich mindestens so viele habe. 43:12.410 --> 43:14.590 Da gibt es halt einige, die kommen halt nicht vor. 43:14.670 --> 43:17.210 Die werden halt dann auch auf irgendwas abgebildet, aber die kommen 43:17.210 --> 43:18.030 halt gar nicht vor. 43:19.310 --> 43:21.730 Das muss man sich halt jetzt noch mal in Ruhe klar machen, dass man 43:21.730 --> 43:26.690 hier einen schönen, sauberen mathematischen Mechanismus hat, der für 43:26.690 --> 43:31.430 eine beliebige Formel sagt, okay, du bist die erste Variable, du die 43:31.430 --> 43:34.090 zweite Variable, du die dritte und du die vierte Variable. 43:34.950 --> 43:39.790 Und egal, wie die Variablen heißen, wenn ich zwei Formeln habe, wo 43:39.790 --> 43:42.470 immer die erste und zweite und dritte und vierte Variable und so 43:42.470 --> 43:46.610 weiter, wo die Nummerierung konsistent miteinander ist, dann habe ich 43:46.610 --> 43:51.650 durch diese Form der Evaluierung der Werte der Aussagenlogischen 43:51.650 --> 43:55.270 Formeln plötzlich eine Äquivalenz solcher Formeln hergestellt. 43:55.550 --> 43:59.590 Dann ist plötzlich p0 und p0 Äquivalenz zu p2 und p2. 44:02.730 --> 44:08.330 Wenn ich eine Interpretation habe für eine Formel g, sodass der Wert 44:08.330 --> 44:12.190 der Formel von dieser Interpretation wahr ist, dann nenne ich diese 44:12.190 --> 44:18.850 Interpretation ein Modell der Formel g. Genauso kann ich eine 44:18.850 --> 44:24.030 Interpretation nennen ein Modell einer Menge von Formeln Gamma, wenn 44:24.030 --> 44:28.970 jede der Formeln aus der Menge Gamma mit der Interpretation i 44:28.970 --> 44:31.230 ausgewertet eben gleich wahr ist. 44:31.950 --> 44:35.150 Also eine Interpretation kann Modell sein einer Formel oder kann 44:35.150 --> 44:36.930 Modell sein einer Menge von Formeln. 44:38.990 --> 44:42.410 Und wenn ich jetzt so eine Menge von Formeln Gamma habe und ich habe 44:42.410 --> 44:47.750 eine Formel g und wenn jedes Modell von Gamma, also jede 44:47.750 --> 44:54.070 Interpretation, für die alle Formeln im Gamma zu wahr auswerten, wenn 44:54.070 --> 44:58.550 jedes dieser Modelle auch ein Modell von g ist, dann schreibt man 44:58.550 --> 45:04.650 dieses Strich gleich g. Formelmenge Gamma Strich gleich g. 45:08.920 --> 45:13.780 Man schreibt dann, wenn diese Formelmenge nur eine Formel enthält, h, 45:13.980 --> 45:20.640 dann lässt man die Mengenklammern weg und sagt dann das ganze g unter 45:20.640 --> 45:21.640 h. 45:22.900 --> 45:29.620 Und wenn diese Menge Gamma-Formeln leer ist, das heißt g für jede 45:29.620 --> 45:34.480 beliebige Interpretation wahr ist, dann schreiben wir halt einfach nur 45:34.480 --> 45:38.700 dieser Strich gleich g und lassen die leere Menge vorne weg. 45:40.460 --> 45:45.420 Wenn so eine Formel g für alle Interpretationen wahr ist, dann bekommt 45:45.420 --> 45:49.160 die einen ganz besonderen Namen, dann heißt das ganze eine Tautologie 45:49.160 --> 45:51.840 oder man nennt sie allgemeingültig. 45:54.040 --> 45:58.420 Das heißt, dieses Strich gleich g ist eine andere Art und Weise zu 45:58.420 --> 46:02.960 schreiben, g ist eine Tautologie, sprich g ist immer wahr, egal welche 46:02.960 --> 46:05.280 Interpretation ich dafür anwende. 46:05.380 --> 46:09.020 Wenn man zum Beispiel sowas hat wie p oder nicht p, kann man sich die 46:09.020 --> 46:11.060 Tabelle anschauen, ist offensichtlich immer wahr. 46:11.820 --> 46:17.740 Oder wenn man hat sowas wie wenn q dann p, ist auch immer wahr. 46:18.060 --> 46:20.080 Das sind so einfache Beispiele für Tautologie. 46:21.620 --> 46:25.520 Wenn ich jetzt eine Formel habe, g habe, die für mindestens eine 46:25.520 --> 46:30.900 Interpretation zu wahr auswertet, dann nenne ich so eine Formel 46:30.900 --> 46:31.520 erfüllbar. 46:34.460 --> 46:38.340 Zu zeigen, dass eine Formel erfüllbar ist, kann in bestimmten 46:38.340 --> 46:40.280 Anwendungen wichtig sein. 46:42.920 --> 46:45.140 Warum kann das wichtig sein? 46:45.680 --> 46:50.400 Das ist so etwas, das lernen Sie in der Mathematik häufig, wenn man 46:50.400 --> 46:53.340 beweist, dann kann man zwei Dinge beweisen, dann kann man beweisen, 46:53.900 --> 46:57.920 dass es zum Beispiel etwas gibt, dass irgendwas existiert. 46:57.980 --> 47:01.340 Wir haben zum Beispiel bewiesen, dass das leere Wort existiert oder 47:01.340 --> 47:02.480 Sie können Sätze beweisen. 47:03.120 --> 47:06.580 Hier bei der Aussagenlogik kann man jetzt zum Beispiel beweisen, dass 47:06.580 --> 47:11.620 es immerhin eine Interpretation gibt, dass so eine Formel wahr ist. 47:12.540 --> 47:15.080 Und da sagt man sich, ja gut, das ist jetzt theoretisch ja ganz schön, 47:15.180 --> 47:17.420 wenn man das vielleicht machen kann, aber gibt es da auch in der 47:17.420 --> 47:18.500 Praxis wichtige Sachen? 47:21.080 --> 47:22.520 Jetzt denken Sie ans Programmieren. 47:24.220 --> 47:26.880 Wenn Sie jetzt Programme schreiben, dann wollen Sie ja zum Beispiel in 47:26.880 --> 47:31.880 der Lage sein, sicherzugehen, dass das Programm auch richtig ist. 47:32.800 --> 47:35.940 Und relativ häufig kommen in der Programmierung aussagenlogische 47:35.940 --> 47:36.660 Formeln vor. 47:37.280 --> 47:42.960 Zum Beispiel dann, wenn Sie so bedingte Verzweigungen haben, wenn Sie 47:42.960 --> 47:46.300 so if-Abfragen haben oder wenn Sie while-Schleifen haben. 47:47.060 --> 47:50.840 Und dann haben Sie irgendwo Code, da gibt es eine if-Abfrage, da drin 47:50.840 --> 47:53.980 steckt irgendeine aussagenlogische Formel und wenn die wahr ist, dann 47:53.980 --> 47:55.940 machen Sie das und ansonsten machen Sie was anderes. 47:57.100 --> 48:01.440 Jetzt ist ein Aspekt, wenn Sie so Programme verifizieren, dann wollen 48:01.440 --> 48:05.420 Sie wissen, wird denn zum Beispiel jeder Programmcode ausgefüllt? 48:06.940 --> 48:12.080 Und wenn es zum Beispiel Programmcode gibt, der nie ausgeführt wird, 48:12.920 --> 48:15.920 dann ist das ein gutes Indiz dafür, dass da irgendwas sein könnte, das 48:15.920 --> 48:18.660 vielleicht nicht so ist wie gedacht, das vielleicht falsch sein 48:18.660 --> 48:18.920 könnte. 48:19.360 --> 48:22.520 Weil der Programmierer schreibt ja nicht irgendwas hin, was nie 48:22.520 --> 48:25.720 ausgeführt wird, sondern der wird sich ja irgendwas dabei gedacht 48:25.720 --> 48:26.000 haben. 48:27.280 --> 48:30.900 Und eine Möglichkeit unter bestimmten Bedingungen halt zu gucken, ob 48:30.900 --> 48:34.320 bestimmter Programmcode ausgeführt wird, ist sich halt zu überlegen, 48:34.460 --> 48:38.240 diese aussagenlogische Formel, die da drin steht, kann die überhaupt 48:38.240 --> 48:39.180 jemals wahr werden? 48:39.420 --> 48:43.100 Gibt es mindestens einen Fall, wo die wahr wäre, damit dieser Zweig 48:43.100 --> 48:43.860 ausgeführt wird? 48:44.620 --> 48:48.240 Wenn das nicht der Fall ist, dann sollte ich vielleicht nochmal 48:48.240 --> 48:50.000 darüber nachdenken, was ich da hingeschrieben habe. 48:50.060 --> 48:52.100 Im einfachsten Fall kann ich das einfach wegstreichen. 48:52.720 --> 48:55.140 Im Schlimmeren, und das ist der meisten häufiger Fall, habe ich 48:55.140 --> 48:57.640 irgendeinen Denkfehler drin, dass diese aussagenlogische Formel 48:57.640 --> 49:00.660 entweder falsch ist, oder ich irgendwas in der Semantik bei der 49:00.660 --> 49:01.940 Programmierung falsch gemacht habe. 49:02.600 --> 49:04.420 Das wäre so zum Beispiel ein Anwendungsfall. 49:05.440 --> 49:08.440 Ein anderer Anwendungsfall allgemein, wenn man mal diese Frage hat, 49:08.520 --> 49:10.080 existiert überhaupt etwas? 49:10.440 --> 49:11.720 Warum ist das überhaupt interessant? 49:12.680 --> 49:16.220 Kann zum Beispiel interessant sein, bei so Modellsimulationen oder 49:16.220 --> 49:19.220 wenn man irgendwas automatisch beweisen will, oder wenn man irgendwas 49:19.220 --> 49:21.020 automatisch berechnen will. 49:21.620 --> 49:24.500 Da haben wir an der Universität ein ganz großes Rechencluster für. 49:25.280 --> 49:29.000 Da steht ein Rechencluster mit ganz vielen Rechnern im Rechenzentrum 49:29.000 --> 49:33.060 irgendwo unten, gut gekühlt und mit viel Speicherplatz angeschlossen 49:33.060 --> 49:36.760 und großer Netzwerkverbindung und da kann man dann Rechenzeit darauf 49:36.760 --> 49:39.020 beantragen und bieten und dann kann man irgendwas machen. 49:39.740 --> 49:40.440 Physiker zum Beispiel. 49:40.520 --> 49:41.040 Wer ist Physiker? 49:42.660 --> 49:45.780 Sie werden das sicherlich unter Umständen, wenn Sie jetzt nicht völlig 49:45.780 --> 49:48.420 theoretische Physik machen, ganz häufig irgendwas simulieren. 49:49.200 --> 49:51.220 Wenn Sie dann irgendeine Theorie haben und dann gehen Sie hin und 49:51.220 --> 49:51.880 simulieren das. 49:52.880 --> 49:55.980 Dann müssen Sie sich da Rechenzeit beantragen auf dem Rechencluster. 49:56.080 --> 49:58.160 Dann stellen Sie also das, was Sie berechnen wollen, in so eine 49:58.160 --> 50:01.120 Warteschlange rein und wenn genügend Rechenzeit zur Verfügung ist und 50:01.120 --> 50:04.320 Sie an der Reihe sind, dann wird Ihr Programm ausgeführt und dann wird 50:04.320 --> 50:05.920 gerechnet und die Simulation berechnet. 50:06.960 --> 50:11.560 Und dann sind also schon solche Sachen platziert wie, wir wollten auch 50:11.560 --> 50:14.080 darauf rechnen, wir rechnen auch manchmal große Sachen und man wartet 50:14.080 --> 50:15.500 und man wartet und man wartet. 50:16.440 --> 50:18.880 Und es vergeht eine Woche und man bekommt immer noch keine Rechenzeit. 50:19.320 --> 50:21.600 Das gesamte Cluster ist komplett belegt. 50:22.540 --> 50:25.600 Dann halt wieder mal Physiker, die haben unbedingt viel Rechenzeit 50:25.600 --> 50:28.980 gebraucht, die haben halt den ganzen Rechencluster für sich reserviert 50:28.980 --> 50:31.540 und haben etwas rechnen lassen, eine Woche lang. 50:32.820 --> 50:34.400 Und wollten irgendein Ergebnis errechnen. 50:35.520 --> 50:38.200 Und während dieser Woche ist dann irgendwann mal einer auf die schlaue 50:38.200 --> 50:41.920 Idee zu kommen und hat sich überlegt, kann man das überhaupt 50:41.920 --> 50:42.360 berechnen? 50:43.200 --> 50:44.420 Existiert eine Lösung? 50:45.440 --> 50:47.600 Und dann hat er sich ein bisschen hingesetzt und ein bisschen gedacht, 50:48.360 --> 50:51.120 während da jede Menge Elektrizität verbrannt wurde und jede Menge 50:51.120 --> 50:54.820 Wärme erzeugt wurde und die gesamte Rest der Universität schon sauer 50:54.820 --> 50:56.500 war, weil sie auf Rechenzeit gewartet hat. 50:56.780 --> 50:59.280 Und er ist zum Ergebnis gekommen, das kann man gar nicht berechnen. 50:59.340 --> 51:01.460 Da gibt es gar keine Lösung für den, was wir da machen. 51:02.260 --> 51:04.660 Und bei sowas ist es dann manchmal ganz sinnvoll, wenn man sich erst 51:04.660 --> 51:08.760 überlegt, ob etwas existiert, zum Beispiel eine Lösung existiert und 51:08.760 --> 51:11.900 dann den Rechner anwirft und den Rest der Universität gegen sich 51:11.900 --> 51:13.780 aufbringt und nicht umgekehrt. 51:15.880 --> 51:18.820 Es ist halt nicht alles immer so ein kleines Java-Programm, das Sie 51:18.820 --> 51:20.000 bei sich auf dem Rechner schreiben. 51:20.120 --> 51:22.900 Wenn Sie jetzt dann hinterher in der Wissenschaft arbeiten, werden die 51:22.900 --> 51:25.520 Dinge manchmal größer und dann werden solche Fehler unter Umständen 51:25.520 --> 51:26.040 sehr teuer. 51:26.540 --> 51:28.740 Und da macht es manchmal Sinn, sich vorher ein bisschen mehr Gedanken 51:28.740 --> 51:29.200 zu machen. 51:31.480 --> 51:34.140 Hier nochmal ein paar Beispiele für Tautologien. 51:34.760 --> 51:39.920 Wir hatten diesen Doppelfeil als Abkürzung aus wenn g dann h und h 51:39.920 --> 51:47.580 dann g. Wenn ich jetzt für jedes, für jedes i mir anschaue, was ist 51:47.580 --> 51:54.100 denn der Wert aus wenn g dann h und wenn h dann g, dann kann ich das 51:54.100 --> 51:57.260 halt entsprechend wieder auslösen mit den bool'schen Funktionen, die 51:57.260 --> 51:57.720 wir kannten. 51:57.820 --> 52:03.700 Das ist dann und von wenn g dann h und wenn h dann g. Da muss ich also 52:03.700 --> 52:07.960 den Folgepfeil reinschreiben, das ist also der Folgepfeil dann weil i 52:07.960 --> 52:17.100 g, weil i h und dann Folgepfeil weil i h, weil i g. Wenn jetzt also g 52:17.100 --> 52:24.060 und h äquivalente Formeln sind, dann ist der Wert von g immer gleich 52:24.060 --> 52:25.540 der Wert von h. 52:25.620 --> 52:28.880 Das ist gerade die Definition von Äquivalenz. 52:29.980 --> 52:34.560 Wenn ich da oben also so äquivalente Formeln reinstecke in so einem 52:34.560 --> 52:39.840 Doppelfeil g und h und das ausrechne, dann passiert folgendes. 52:40.460 --> 52:42.620 Also ist immer der gleiche Wert. 52:44.080 --> 52:49.400 Jetzt rechne ich zurück und habe dann hinterher stehen, also da ist 52:49.400 --> 52:54.980 dieser Folgepfeil weil i g, weil i h und da oben der Folgepfeil weil i 52:54.980 --> 52:59.220 g, weil i g. Steht also links und rechts immer der gleiche Wert, weil 52:59.220 --> 53:02.800 nämlich g und h immer den gleichen Wert haben für jede Interpretation. 53:03.580 --> 53:07.460 Naja, und wenn man in der Tabelle nachschaut, guckt, wenn g dann g 53:07.460 --> 53:11.080 wertet sich immer zu war aus, egal ob g jetzt falsch oder wahr ist. 53:11.700 --> 53:14.860 Und dann habe ich da plötzlich stehen wie und we und das ist gleich 53:14.860 --> 53:15.120 wahr. 53:16.780 --> 53:22.880 Das heißt also, dieser Doppelfeil g Doppelfeil h, der wertet genau 53:22.880 --> 53:28.000 dann zu wahr aus, wenn g und h miteinander äquivalent sind. 53:29.040 --> 53:32.360 Und deswegen, wenn man manchmal ein bisschen sloppy ist, liest man 53:32.360 --> 53:35.980 diesen Doppelfeil eben gerade nicht als Implikation, sondern als die 53:35.980 --> 53:36.640 Äquivalenz. 53:44.290 --> 53:47.910 Das kann man halt auch entsprechend beweisen. 53:48.510 --> 53:51.550 Man kann halt den Satz beweisen, wenn g und h äquivalent miteinander 53:51.550 --> 53:57.370 sind, dann muss g Doppelfeil h eine Tautologie sein. 54:01.370 --> 54:06.230 Und genauso umgekehrt kann man zeigen, dass wenn g Doppelfeil h eine 54:06.230 --> 54:09.490 Tautologie ist, dann ist g Äquivalent h. 54:11.050 --> 54:13.630 Und da ist es jetzt ganz gut, dass man solche Lämmerter halt 54:13.630 --> 54:18.750 entsprechend mit wenn und dann und genau dann wenn ausdruckt und da 54:18.750 --> 54:21.450 nicht auch noch Pfeile malt, weil sie kennen das aus der Mathematik. 54:21.550 --> 54:25.770 Wenn sie da Sachen beweisen und mit genau dann wenn antieren, dann 54:25.770 --> 54:27.310 verwenden sie auch so einen Doppelfeil. 54:27.430 --> 54:28.810 Der hat in der Regel zwei Striche. 54:29.590 --> 54:31.590 Dann wird es hier nämlich ganz unübersichtlich werden. 54:31.910 --> 54:35.030 Weil streng genommen muss man dann jetzt unterscheiden zwischen diesem 54:35.030 --> 54:39.050 wenn dann Pfeil, den wir da erstmal in der allgemeinen natürlichen 54:39.050 --> 54:42.390 Sprache für Beweise verwenden und diesem Doppelfeil, den wir 54:42.390 --> 54:45.010 verwenden, der jetzt nur für die Aussagenlogik da ist. 54:47.190 --> 54:49.110 So was kann man wie gesagt beweisen. 54:52.790 --> 54:55.570 Hier haben wir schon mal die eine Richtung gemacht. 54:55.770 --> 54:59.370 Wir haben also diese eine Richtung, wenn g Äquivalent h ist, dann 54:59.370 --> 55:03.090 haben wir gezeigt, dass dann für jede Interpretation das Ganze zu wahr 55:03.090 --> 55:03.650 ausführt. 55:04.030 --> 55:05.790 Das heißt, die eine Richtung haben wir gemacht. 55:07.010 --> 55:09.450 Umgekehrte Richtung kann man halt entsprechend auch beweisen. 55:10.990 --> 55:11.210 Ja, 55:24.590 --> 55:26.070 da müsste eine Klammer sein. 55:29.190 --> 55:30.850 Ja, da müsste eine Klammer hin. 55:31.370 --> 55:33.910 Da fehlt eine Klammer. 55:33.970 --> 55:34.750 Das ist gut gesehen. 55:34.870 --> 55:35.590 Das muss ich noch... 55:35.590 --> 55:37.730 schreiben Sie mir eine E-Mail, sonst vergesse ich es und nächstes Jahr 55:37.730 --> 55:38.510 ist es wieder genauso. 55:40.510 --> 55:44.710 Da in der Tat hier, wir hatten gesagt, das und bindet stärker als die 55:44.710 --> 55:45.370 Implikation. 55:45.890 --> 55:49.710 Das heißt, hier müssten wir eigentlich die beiden Implikationen 55:49.710 --> 55:53.770 erstmal klammern, bevor wir sie mit einem und verbinden dürfen. 55:55.770 --> 55:56.270 Genau. 55:58.070 --> 55:58.750 Gut. 55:59.390 --> 56:02.930 Also, gibt es ein paar konkrete Beispiele, die man sich anschauen kann 56:02.930 --> 56:06.890 von Tautologien bei so kleinen, kleinen Formeln. 56:07.270 --> 56:11.810 Das Einfachste, das zu beweisen, ist zum Beispiel immer, wenn g und h 56:11.810 --> 56:14.870 relativ einfache Formeln sind, konkrete Formeln, dann kann ich einfach 56:14.870 --> 56:16.330 alle Interpretationen hinschreiben. 56:16.790 --> 56:20.770 Wenn ich das jetzt aber im allgemeinen Fall machen will, dann muss ich 56:20.770 --> 56:23.530 halt, kann ich das nicht mehr machen, kann ich nicht mehr alle 56:23.530 --> 56:26.230 Interpretationen hinschreiben, weil ich weiß ja gar nicht, wie viele 56:26.230 --> 56:30.170 Variablen in g und h vorkommen und ich weiß ja gar nicht, wie g und h 56:30.170 --> 56:33.270 sich unter Umständen auswerten. 56:34.750 --> 56:38.230 Dementsprechend, wenn man sowas beweisen will, muss man halt mit so 56:38.230 --> 56:39.730 anderen Dingen vorgehen. 56:40.450 --> 56:43.890 Also hier ganz viele Beispiele für Tautologien. 56:44.890 --> 56:50.290 Wenn g dann h, Doppelfeil, nicht g oder h ist eine Autotautologie, was 56:50.290 --> 56:53.830 wir halt wissen, weil wenn g dann h ist halt Äquivalenz und nicht g 56:53.830 --> 56:56.390 oder h und so weiter und so fort. 56:57.010 --> 56:59.830 Ganz viele einfache Beispiele, die kann man sich mal in Ruhe angucken 56:59.830 --> 57:04.270 und sich überlegen, was das denn jetzt konkret bedeutet. 57:06.270 --> 57:11.950 Es gibt auch noch andere Tautologien, anderer Bauart, also g 57:11.950 --> 57:16.190 impliziert g ist Tautologie, nicht g oder g ist eine Tautologie, dann 57:16.190 --> 57:20.210 g impliziert h impliziert g, hatten wir schon kennengelernt. 57:20.810 --> 57:23.310 Und dann hatten wir da noch, kann man das noch komplexer machen, kann 57:23.310 --> 57:26.430 man dann mit drei Variablen arbeiten und dann mit Implikationspfeilen 57:26.430 --> 57:29.690 arbeiten und bekommt dann eine Tautologie raus oder kann man dann noch 57:29.690 --> 57:33.110 ein nicht reinbringen in diese Pfeile und das sind dann auch 57:33.110 --> 57:34.850 entsprechend Tautologien. 57:36.770 --> 57:40.570 Und diese Art von Tautologien, die sind von einer bestimmten 57:40.570 --> 57:45.770 Interesse, wenn es jetzt nämlich darum geht, so Äquivalenzen zu 57:45.770 --> 57:46.270 beweisen. 57:47.870 --> 57:50.510 Und wenn man jetzt solche Sachen beweisen will, zum Beispiel solche 57:50.510 --> 57:54.330 komplizierten Tautologien, wo man nichts Konkretes weiß über die 57:54.330 --> 57:58.970 einzelnen Formeln oder wenn man beweisen will, dass wenn das eine 57:58.970 --> 58:03.510 gilt, dann muss auch das andere gelten, wenn man das hinterher für 58:03.510 --> 58:07.210 Programmiersprachen machen will oder für Programme, wenn man für 58:07.210 --> 58:10.630 Programme beweisen will, dass dieses Programm korrekt ist und das ist, 58:10.710 --> 58:14.390 was es machen soll, dann verwendet man da meistens etwas, das nennen 58:14.390 --> 58:15.290 wir ein Kalkül. 58:16.610 --> 58:19.350 Und Sie haben sich schon im Programmieren den Kalkül kennengelernt? 58:21.330 --> 58:22.190 Irgendeinen Kalkül? 58:22.810 --> 58:24.930 Haben Sie schon mal irgendwo jemals, hat schon mal jemand in der 58:24.930 --> 58:26.190 Schule einen Kalkül kennengelernt? 58:27.710 --> 58:30.470 Das ist etwas, das wird Ihnen hier in der Vorlesung zum Beispiel 58:30.470 --> 58:31.210 erspart preisen. 58:31.290 --> 58:32.070 Da gibt es immer das Nennen. 58:32.170 --> 58:34.410 Viele finden das toll, das sogenannte Lambda-Kalkül. 58:35.270 --> 58:37.630 Bei Programmiersprachen und Algorithmen ganz beliebt. 58:38.010 --> 58:40.750 Das werden Sie hier in dieser Vorlesung noch glücklicherweise kommen 58:40.750 --> 58:41.350 Sie drumherum. 58:41.750 --> 58:43.170 Das kommt dann in anderen Vorlesungen. 58:43.910 --> 58:47.530 Aber auch für die aussagenlogischen Formeln haben wir ein Kalkül. 58:48.130 --> 58:52.310 Und ein Kalkül allgemein als System für Beweise ist halt so definiert. 58:52.490 --> 58:56.890 Es gibt irgendein Alphabet A und es gibt syntaktisch konkret korrekte 58:56.890 --> 59:02.230 Formeln, die aus den Wörtern über diesem Alphabet A gebildet werden. 59:02.610 --> 59:05.690 Diese Wörter aus diesem Alphabet A sind die syntaktisch korrekt. 59:06.470 --> 59:10.390 Und auch ein Programm kann man als eine syntaktisch korrekte Formel 59:10.390 --> 59:11.050 aufgreifen. 59:11.410 --> 59:15.530 Weil auch ein Programm ist letztendlich ein Wort über einem Alphabet 59:15.530 --> 59:19.130 und das Alphabet sind halt die Kommandowörter und so weiter, die es in 59:19.130 --> 59:20.990 der Programmiersprache gibt. 59:21.630 --> 59:23.770 Dann gibt es etwas sowas wie Aktionen. 59:24.430 --> 59:26.570 Das sind Dinge, die gelten. 59:28.350 --> 59:33.030 Kennen Sie aus der Mathematik Aktionen? 59:33.190 --> 59:35.250 Das sind irgendwelche Dinge, die gelten. 59:35.850 --> 59:37.230 Von denen geht man aus, dass die gelten. 59:37.290 --> 59:39.590 Die kann man auch nicht beweisen, dass die unter Umständen gelten. 59:40.150 --> 59:44.450 Und dann hat man irgendwelche Schlussregeln, ein systematisches 59:44.450 --> 59:47.050 Vorgehen, wie ich dann Schlüsse aufziehen kann. 59:47.130 --> 59:52.750 Wie ich dann solche Beweise aus solchen Schlussregeln zusammensetzen 59:52.750 --> 59:53.030 kann. 59:53.910 --> 59:56.830 Und bei der Aussagenlogik haben wir da auch ein Kalkül. 59:56.890 --> 59:59.050 Das Aussagenkalkül für die Aussagenlogik. 59:59.810 --> 01:00:04.250 Das besteht halt aus dem Alphabet, der Aussagenlogik logischerweise. 01:00:04.930 --> 01:00:08.190 Dann habe ich die syntaktisch korrekten Formeln, aussagenlogischen 01:00:08.190 --> 01:00:08.550 Formeln. 01:00:08.650 --> 01:00:11.730 Das ist das vor allem, halt als Teilmenge aller Wörter. 01:00:12.410 --> 01:00:15.330 Und dann habe ich eine Menge an Aktionen. 01:00:16.570 --> 01:00:19.030 Und zwar genau bei uns drei Aktionen. 01:00:19.290 --> 01:00:26.190 Die sind halt auch Teilmenge aller Aktionen der aussagenlogischen 01:00:26.190 --> 01:00:26.630 Formeln. 01:00:27.570 --> 01:00:31.230 Und am Ende habe ich noch sowas wie eine Schlussregel. 01:00:31.330 --> 01:00:33.890 Und diese Schlussregel, die wir haben, die nennt sich der Modus 01:00:33.890 --> 01:00:34.870 ponens. 01:00:35.530 --> 01:00:41.470 Und dieser Modus ponens ist erstmal rein formal eine Teilmenge der 01:00:41.470 --> 01:00:45.130 aussagenlogischen Formeln mit drei Variablen. 01:00:49.680 --> 01:00:53.660 Und wenn man sich den jetzt anschaut, den Modus ponens und ein 01:00:53.660 --> 01:00:56.680 bisschen verknüpft mit den Tautologien und so, die wir gesehen haben, 01:00:57.240 --> 01:01:00.120 dann ergibt das Ganze auch irgendwie plötzlich einen Sinn. 01:01:01.280 --> 01:01:06.960 Wir nehmen uns, ja, was ist unklar? 01:01:09.540 --> 01:01:10.780 Zum Beispiel da oben. 01:01:12.840 --> 01:01:13.700 Bei Ihnen beiden. 01:01:17.490 --> 01:01:18.290 Bei Ihnen beiden. 01:01:18.370 --> 01:01:19.210 Was ist unklar? 01:01:20.770 --> 01:01:21.250 Nö, nö, nö. 01:01:21.290 --> 01:01:23.790 Wenn so leibhaft diskutiert wird, dann ist es wahrscheinlich für alle 01:01:23.790 --> 01:01:24.150 interessant. 01:01:24.370 --> 01:01:25.130 Also, was ist unklar? 01:01:26.450 --> 01:01:30.510 Ja, dann muss man sich nicht übersprechen, wenn es nicht richtig ist. 01:01:32.330 --> 01:01:35.330 Also, wir nehmen uns drei Aktionen her. 01:01:35.570 --> 01:01:37.370 Die haben Sie vorhin schon aufgelistet gesehen. 01:01:38.030 --> 01:01:38.950 Das sind Aktionen. 01:01:41.230 --> 01:01:42.710 Bei Ihnen da oben auch was unklar? 01:01:46.740 --> 01:01:47.960 So, jetzt mal Ruhe. 01:01:49.580 --> 01:01:50.760 Wir haben es bald hinter sich. 01:01:51.660 --> 01:01:53.880 Auch die in der letzten Reihe haben es bald hinter sich. 01:01:55.240 --> 01:01:55.980 Ganz ehrlich. 01:01:56.780 --> 01:01:57.120 Hallo? 01:02:02.090 --> 01:02:03.610 Auch Sie haben es jetzt hinter sich. 01:02:05.670 --> 01:02:07.410 Sie halten jetzt da oben mal Ruhe. 01:02:08.070 --> 01:02:08.870 Ist das angekommen? 01:02:09.870 --> 01:02:10.190 Gut. 01:02:13.230 --> 01:02:15.230 Gut, also, wir nehmen uns drei Aktionen her. 01:02:15.910 --> 01:02:17.710 Die hatten Sie vorhin schon auf der Liste gesehen. 01:02:18.350 --> 01:02:20.010 Diese drei Aktionen, die kriegen halt einen Namen. 01:02:20.190 --> 01:02:22.750 Aktionen alle eins, Aktionen alle zwei, Aktionen alle drei. 01:02:24.510 --> 01:02:27.410 Und dann nehmen wir uns den Modus Ponens her. 01:02:27.470 --> 01:02:29.470 Wir hatten gesagt, das ist schon so eine Teilmenge dieser 01:02:29.470 --> 01:02:31.850 aussagenlogischen Formel mit drei Variablen. 01:02:32.450 --> 01:02:36.050 Und das Ganze, ähm, nicht mit drei Variablen, also der Tupel, dreier 01:02:36.050 --> 01:02:37.470 Tupel aussagenlogischer Formel. 01:02:38.230 --> 01:02:42.290 Und so ein Tupel, dieses dreier Tupel aus aussagenlogischen Formeln, 01:02:42.390 --> 01:02:45.910 besteht also aus, wenn g, dann h, g und h. 01:02:48.110 --> 01:02:50.730 Manchmal schreibt man das halt nicht so als Menge, sondern manchmal 01:02:50.730 --> 01:02:54.530 schreibt man es einfach so mit diesem Strich oben, wenn g, dann h, g 01:02:54.530 --> 01:02:55.630 und dann h. 01:02:56.430 --> 01:02:58.050 Was soll das bedeuten? 01:02:58.690 --> 01:03:01.230 Naja, das ist hinterher, was da hinterher stehen soll. 01:03:01.370 --> 01:03:03.310 Ich habe irgendwie g. g gilt. 01:03:03.830 --> 01:03:05.770 Ich weiß irgendwie, g ist aus irgendwie abgeleitet. 01:03:06.730 --> 01:03:09.350 Und ich weiß, es gilt, wenn g, dann h. 01:03:10.410 --> 01:03:11.590 Naja, g gilt. 01:03:11.830 --> 01:03:13.370 Wenn g, dann h gilt. 01:03:14.090 --> 01:03:16.030 Dann gilt logischerweise auch h. 01:03:16.610 --> 01:03:18.310 Dann kann ich daraus auch h ableiten. 01:03:18.970 --> 01:03:23.390 Und mit dieser einfachen Regel und diesen drei Aktionen kann ich jetzt 01:03:23.390 --> 01:03:30.570 ganz schön formal so Beweise hinschreiben als so eine Kette von 01:03:30.570 --> 01:03:33.350 einzelnen Schritten, von so einzelnen Ableitungsschritten. 01:03:34.310 --> 01:03:39.430 Wenn man das Ganze formal anschaut, dann ist es so, wenn ich etwas 01:03:39.430 --> 01:03:41.770 ableiten will, dann habe ich immer eine Prämisse. 01:03:42.350 --> 01:03:43.650 Das ist wie bei einem bewahrten Satz. 01:03:43.710 --> 01:03:44.630 Ich habe Voraussetzungen. 01:03:44.770 --> 01:03:47.590 Irgendwas ist irgendwie und dann will ich zeigen, dass irgendwas 01:03:47.590 --> 01:03:48.310 anderes ist. 01:03:49.610 --> 01:03:52.650 Und ich will daraus also was ableiten. 01:03:52.750 --> 01:03:56.310 Also ich habe meine Prämissen, ich habe meine Aktionen und dann mache 01:03:56.310 --> 01:03:57.030 ich eine Ableitung. 01:03:57.570 --> 01:04:01.310 Und diese Ableitung ist so eine endliche Folge von aussagenlogischen 01:04:01.310 --> 01:04:01.770 Formeln. 01:04:02.170 --> 01:04:05.210 Die kann man halt als ein K-Tupel hinschreiben, G1 bis Gn. 01:04:05.790 --> 01:04:11.990 Und es soll bitteschön so sein, dass das letzte G, dieses Gn, das ist 01:04:11.990 --> 01:04:14.910 eben gerade das, diese Formel G, die ich herleiten möchte. 01:04:15.950 --> 01:04:20.650 Und alles, was davor steht, das kann eins von drei Dingen sein. 01:04:20.990 --> 01:04:22.070 Das kann ein Aktion sein. 01:04:22.430 --> 01:04:24.930 Ich kann davor irgendeine Aktion hinstellen, die gelten immer. 01:04:26.110 --> 01:04:30.870 Oder es kann eine Prämisse sein, die ich hinschreibe, weil Prämissen, 01:04:31.030 --> 01:04:33.250 das ist das, was ich vorausgesetzt habe, die gelten auch. 01:04:34.410 --> 01:04:40.910 Oder es kann so sein, dass ich halt zwei Indizes habe, I1 und I2, die 01:04:40.910 --> 01:04:43.030 sind kleiner als das aktuelle Gi. 01:04:43.850 --> 01:04:48.810 Und dann muss dieses Triple Gi1, Gi2, Gi, Teilmenge aus dem Modus 01:04:48.810 --> 01:04:50.290 ponens sein. 01:04:50.970 --> 01:04:53.330 Das heißt, ich habe also in meiner Ableitungskette irgendwas 01:04:53.330 --> 01:04:57.770 hingeschrieben, anhand dieser Regeln, und dann finde ich da irgendwo 01:04:57.770 --> 01:05:00.190 ein Wenn G, dann H. 01:05:00.930 --> 01:05:03.930 Irgendwo finde ich ein G, und die müssen nicht direkt nebeneinander 01:05:03.930 --> 01:05:04.210 stehen. 01:05:04.290 --> 01:05:07.370 Das G muss nicht vor dem Wenn G, dann H stehen, sondern die müssen 01:05:07.370 --> 01:05:08.790 halt nur irgendwie vorkommen. 01:05:10.510 --> 01:05:15.690 Und wenn die vorgekommen sind, wenn also das G und das Wenn G, dann H 01:05:15.690 --> 01:05:18.410 vorgekommen ist, dann kann ich halt das H hinschreiben. 01:05:18.470 --> 01:05:20.250 Oder halt allgemein das Gi. 01:05:21.050 --> 01:05:24.350 Und wenn ich also so eine Folge aufstellen kann, so eine Folge 01:05:24.350 --> 01:05:27.930 konstruieren kann, losgehend von den Prämissen, Aktionen hinschreiben, 01:05:28.070 --> 01:05:32.430 Prämissen hinschreiben, und mit dem Modus ponens neue Formeln 01:05:32.430 --> 01:05:35.630 hinschreiben, wenn ich da so eine Kette bilden kann, dass am ganzen 01:05:35.630 --> 01:05:39.050 Ende diese Formel G steht, die ich eigentlich ableiten will, dann 01:05:39.050 --> 01:05:43.010 nenne ich das Ganze eine Ableitung der Formel G aus dem Prämissen 01:05:43.010 --> 01:05:48.230 Gamma, und schreibe das halt mit diesem senkrechten Strich und dem 01:05:48.230 --> 01:05:49.330 Querstrich G. 01:05:49.730 --> 01:05:54.170 G ist aus Gamma im aussagenlogischen Kalkül abgeleitet worden. 01:05:58.240 --> 01:06:02.580 Wenn ich jetzt beweisen will, dass irgend so eine aussagenlogische 01:06:02.580 --> 01:06:07.720 Formel G allgemein gilt, ohne dass ich irgendwelche Voraussetzungen 01:06:07.720 --> 01:06:11.020 habe, dann muss ich das Ganze eben aus der leeren Menge abschreiben. 01:06:11.920 --> 01:06:15.420 Dann schreibt man halt nichts, senkrechter Strich, waagerechter 01:06:15.420 --> 01:06:16.560 Strich, G. 01:06:17.600 --> 01:06:21.880 Und man nennt G dann entsprechend ein Theorem eines Kalküls, in diesem 01:06:21.880 --> 01:06:23.660 Fall des aussagenlogischen Kalküls. 01:06:24.400 --> 01:06:26.320 Wo haben Sie dieses Zeichen vorhin schon mal gesehen? 01:06:27.000 --> 01:06:29.860 Es sah ein bisschen anders aus, aber letztendlich sieht es fast gleich 01:06:29.860 --> 01:06:31.800 aus und es hat auch einen Grund, warum es gleich aussieht. 01:06:33.300 --> 01:06:36.120 Wie hatten wir Tautologien notiert? 01:06:37.540 --> 01:06:45.780 Wenn wir jetzt zurückblicken, zurück zu unseren Tautologien, dann 01:06:45.780 --> 01:06:49.280 hatten wir gesagt, eine Tautologie ist allgemeingültig, da hatten wir 01:06:49.280 --> 01:06:51.420 einen senkrechten Strich und zwei waagerechten Striche. 01:06:53.180 --> 01:06:55.700 Wir hatten so die Tautologie definiert. 01:06:56.320 --> 01:07:01.560 Und jetzt sagen wir ein Theorem in diesem Kalkül, das schreiben wir 01:07:01.560 --> 01:07:04.620 halt so, dass wir jetzt den senkrechten Strich haben und nur noch 01:07:04.620 --> 01:07:06.140 einen waagerechten Strich entgegen. 01:07:07.260 --> 01:07:10.120 Dann wird das wohl irgendwas mit Tautologien zu tun haben, weil wir 01:07:10.120 --> 01:07:13.220 machen hier nichts ohne Grund und die Zeichen sehen auch nicht ohne 01:07:13.220 --> 01:07:15.320 Grund gleich aus. 01:07:18.930 --> 01:07:19.870 Einfaches Beispiel. 01:07:21.630 --> 01:07:26.810 Wenn P, dann P. Möchte ich herleiten und ich habe keine Prämissen. 01:07:28.750 --> 01:07:30.030 Und wie kann ich das machen? 01:07:30.150 --> 01:07:31.430 Das kann ich in diesem Kalkül machen. 01:07:31.550 --> 01:07:33.690 Ich muss als erstes mal so ein Axiom hinschrauben. 01:07:34.530 --> 01:07:37.290 Dann nehme ich mir durch scharfes Hinblicken und durch persönliche 01:07:37.290 --> 01:07:39.930 Genialität das Axiom 2. 01:07:40.390 --> 01:07:45.570 Und setze da überall das P rein und bekomme dann diesen Boost aus P, 01:07:45.750 --> 01:07:48.050 wenn P, dann P und so weiter und so fort raus. 01:07:49.030 --> 01:07:51.810 Und dann bin ich noch genialer und gucke hin und sage mir, okay, dann 01:07:51.810 --> 01:07:54.950 schreibe ich halt nochmal das Axiom 1 hin und setze da auch das P 01:07:54.950 --> 01:07:55.290 rein. 01:07:55.810 --> 01:07:59.950 Und dann steht da halt dieses, wenn P, dann P, dann P, dann P. Dann 01:07:59.950 --> 01:08:02.510 habe ich da zwei Axiome und jetzt kann ich, wenn ich die Augen 01:08:02.510 --> 01:08:07.110 zusammenkneifen, sehe, aha, ich habe da oben was stehen. 01:08:09.690 --> 01:08:14.870 Da steht dieses, was links von dem ersten Axiom steht. 01:08:15.690 --> 01:08:19.130 Also da alles, was links vom ersten Pfeil, von diesem mittleren Pfeil 01:08:19.130 --> 01:08:22.270 in der ersten Reihe steht, das steht da unten, das ist auch ein Axiom. 01:08:22.830 --> 01:08:24.890 Dann kann ich den Modus Pronens anbinden. 01:08:25.230 --> 01:08:29.950 Dann weiß ich also, mein G ist halt diese gesamte zweite Zeile und 01:08:29.950 --> 01:08:33.330 dann weiß ich da mein H rechts, das ist alles, was da rechts steht, 01:08:33.450 --> 01:08:37.150 dann kann ich das hinschreiben gemäß Modus Pronens. 01:08:38.330 --> 01:08:40.970 Okay, dann habe ich da schon mal was stehen, das jetzt nicht mehr so 01:08:40.970 --> 01:08:41.770 wild aussieht. 01:08:41.950 --> 01:08:45.050 Dann schreibe ich mir nochmal das Axiom 1 hin, aber setze jetzt nur 01:08:45.050 --> 01:08:49.370 noch einmal das P ein und nicht eine komplexere Formel für das P. Und 01:08:49.370 --> 01:08:51.950 das ist zufälligerweise wieder das, was links steht von diesem 01:08:51.950 --> 01:08:53.970 zentralen Implikationspfeil. 01:08:54.790 --> 01:08:58.270 Und dann kann ich wieder mit Hilfe des Modus Pronens daraus abfolgern, 01:08:58.330 --> 01:09:01.090 was rechts von diesem Implikationspfeil steht, und das ist gerade wenn 01:09:01.090 --> 01:09:04.070 P, dann P. Und das ist gerade das, was ich zeigen wollte. 01:09:05.090 --> 01:09:11.190 Das heißt, ich habe keine Prämissen gehabt, eine Menge der Prämissen 01:09:11.190 --> 01:09:11.670 war leer. 01:09:12.230 --> 01:09:16.410 Ich habe die Axiome nur verwendet, den Modus Pronens, und habe wenn P, 01:09:16.510 --> 01:09:17.430 dann P hergeleitet. 01:09:17.910 --> 01:09:21.510 Das heißt, wenn P, dann P ist ein Theorem. 01:09:22.650 --> 01:09:25.530 Und wir hatten gesehen, wenn P, dann P, hatten wir auch schon gesehen. 01:09:25.630 --> 01:09:27.950 Das war ein einfaches Beispiel für eine Tautologie. 01:09:29.030 --> 01:09:32.030 Und da kann man sich jetzt überlegen, aha, Tautologie und Theorem, die 01:09:32.030 --> 01:09:33.450 müssen wohl irgendwie was zu tun haben. 01:09:34.190 --> 01:09:35.790 Jetzt könnte man eine Vermutung äußern. 01:09:37.170 --> 01:09:42.850 Okay, alles das, was ich als Theorem darstellen kann in diesem Kalkül, 01:09:43.750 --> 01:09:46.270 das wird wohl eine aussagenlogische Tautologie sein. 01:09:47.670 --> 01:09:48.890 Das ist erstmal nur eine Vermutung. 01:09:49.010 --> 01:09:50.030 Ich sage noch nicht, dass das so ist. 01:09:50.070 --> 01:09:51.150 Das ist nur eine Vermutung. 01:09:51.730 --> 01:09:56.350 Und dann wäre es schön, auch sich zu überlegen, okay, kann ich denn 01:09:56.350 --> 01:10:02.310 jede Tautologie der Aussagenlogik, kann ich die vielleicht, kann ich 01:10:02.310 --> 01:10:07.090 von der vielleicht zeigen, dass die dann auch ein Theorem sein muss in 01:10:07.090 --> 01:10:08.690 diesem aussagenlogischen Kalkül? 01:10:11.050 --> 01:10:14.750 Das wäre ja schön, weil das würde bedeuten, dass ich mit diesem 01:10:14.750 --> 01:10:21.890 aussagenlogischen Kalkül jedes, jede Tautologie beweisen könnte und 01:10:21.890 --> 01:10:25.730 dass alles, was ein Theorem ist, dann automatisch auch eine Tautologie 01:10:25.730 --> 01:10:27.170 ist. 01:10:27.630 --> 01:10:32.910 Dann jede Tautologie darstellen, das heißt, es wäre vollständig und 01:10:32.910 --> 01:10:36.050 wenn jedes, was ein Theorem ist, auch eine Tautologie ist, dann wäre 01:10:36.050 --> 01:10:38.150 das Kalkül in der Beziehung dann korrekt. 01:10:40.830 --> 01:10:43.310 Jetzt kann man diese Beweise ein bisschen strukturieren. 01:10:43.410 --> 01:10:47.490 Man kann sich ein zweites Beispiel hernehmen, das man beweisen möchte. 01:10:47.650 --> 01:10:54.510 Das sei, wenn nicht P, dann P, dann P. Dann kann ich wieder hernehmen, 01:10:54.610 --> 01:10:56.930 okay, dann kann ich mir jetzt durch scharfes hingucken dieses 01:10:56.930 --> 01:11:01.570 aussagenlogische Reaktion A3 hernehmen, kann das hinschreiben, 01:11:01.670 --> 01:11:06.170 bisschen was reinschreiben und dann kann ich hinschreiben, wenn nicht 01:11:06.170 --> 01:11:10.510 P, dann nicht P. Das kann ich hinschreiben, das habe ich vorhin schon 01:11:10.510 --> 01:11:10.890 bewiesen. 01:11:11.330 --> 01:11:13.970 Wenn ich es vollständig machen müsste, müsste ich den gesamten Beweis 01:11:13.970 --> 01:11:15.930 von eben, von der vorherigen Folie, hinschreiben. 01:11:16.510 --> 01:11:18.990 Jetzt habe ich das aber separat geschrieben, damit es übersichtlicher 01:11:18.990 --> 01:11:21.550 wird und kann das einfach hinschreiben, weil ich weiß, das ist schon 01:11:21.550 --> 01:11:22.110 ein Theorem. 01:11:22.650 --> 01:11:26.070 Und dann kann ich den Modus Ponens wieder anbinden und habe dann 01:11:26.070 --> 01:11:29.610 wieder dieses, wenn nicht P, dann P, dann P hergenommen. 01:11:30.850 --> 01:11:34.230 Das ist das, was Sie auch bei den normalen mathematischen Beweisen 01:11:34.230 --> 01:11:36.590 machen, vielleicht nicht ganz so formalisiert, dass Sie halt auf so 01:11:36.590 --> 01:11:40.650 Lammertal und kleinere Sätze zurückgreifen und diese einführen und 01:11:40.650 --> 01:11:44.090 hier sind das eben Theoreme, die Sie an der Stelle entsprechend immer 01:11:44.090 --> 01:11:45.270 einsetzen können. 01:11:48.030 --> 01:11:53.690 Jetzt ist die Frage, können wir irgendwie diese Vermutungen von 01:11:53.690 --> 01:11:56.490 vorhin, die wir da hatten, auch vielleicht ein bisschen beweisen. 01:11:58.290 --> 01:12:06.150 Wenn also, wenn G dann H eine Tautologie wäre, ist dann auch H eine 01:12:06.150 --> 01:12:06.670 Tautologie? 01:12:06.670 --> 01:12:10.030 Das wäre so der erste Schritt in dieser Überlegung, damit wir dahin 01:12:10.030 --> 01:12:13.250 kommen, ob wir alle Theorien als Tautologie haben. 01:12:13.450 --> 01:12:16.670 Das wäre so ein erster Schritt, dass man sich überlegt, wenn G dann H, 01:12:16.850 --> 01:12:26.010 dann ist auch G, wenn also sowohl G als auch H, wenn sowohl G, wenn G 01:12:26.010 --> 01:12:29.810 dann H eine Tautologie ist, als auch G eine Tautologie, dann ist auch 01:12:29.810 --> 01:12:30.790 H eine Tautologie. 01:12:31.770 --> 01:12:33.050 Das kann man beweisen. 01:12:34.130 --> 01:12:38.690 Denn wenn G dann H ist Tautologie, dann gilt für jedes I, dass das 01:12:38.690 --> 01:12:40.290 Ganze zu wahr auswertet. 01:12:40.750 --> 01:12:45.990 Das heißt also, die boolsche Funktion von weil I von G und weil I von 01:12:45.990 --> 01:12:50.590 H und das Ganze reingesetzt in den Implikationsfall muss zu wahr 01:12:50.590 --> 01:12:51.850 auswerten. 01:12:51.850 --> 01:12:58.630 Da jetzt G eine Tautologie ist, ist weil I von G wahr. 01:12:58.910 --> 01:13:00.610 Das ist gerade die Definition einer Tautologie. 01:13:00.830 --> 01:13:03.270 Und zwar unabhängig davon, welche Interpretation ich ja nehme. 01:13:04.190 --> 01:13:07.490 Das heißt, was da in Wirklichkeit steht da oben ist halt die boolsche 01:13:07.490 --> 01:13:12.850 Funktion von diesem Implikationsfall von W und weil I von H. 01:13:12.850 --> 01:13:15.650 Und dann gucke ich jetzt halt rein in die Tabelle von dem 01:13:15.650 --> 01:13:19.710 Implikationsfall und dann weiß ich, wenn vorne der erste Wert W ist, 01:13:20.130 --> 01:13:23.530 dann ist der zweite Wert gerade derjenige Wert, der jetzt den 01:13:23.530 --> 01:13:26.830 kompletten Wahrheitswert der Aussagen zwischen Logik, Formel und 01:13:26.830 --> 01:13:27.290 Bestimmt. 01:13:27.510 --> 01:13:29.990 Das heißt, dann ist das Ganze auch den weil I von H. 01:13:29.990 --> 01:13:36.010 Das heißt also für jede Interpretation ist weil I von H wahr, weil 01:13:36.010 --> 01:13:40.250 eben weil I von G wahr ist. 01:13:40.750 --> 01:13:42.710 Also ist H eine Tautologie. 01:13:47.240 --> 01:13:50.800 Und das ist eben gerade diese Vermutung, die wir haben. 01:13:51.220 --> 01:13:55.340 Achso, und das Ganze nennt man halt, dass der Modus Ponens die 01:13:55.340 --> 01:13:57.080 Allgemeingültigkeit erhält. 01:13:57.080 --> 01:14:00.980 Das heißt, wenn ich also mithilfe vom Modus Ponens aus etwas 01:14:00.980 --> 01:14:09.360 Allgemeingültigem etwas schließe, wenn also, wenn G dann H eine 01:14:09.360 --> 01:14:12.780 Tautologie ist und G eine Tautologie ist, wenn ich also aus zwei 01:14:12.780 --> 01:14:17.280 Tautologien dann H schließe, H hinschreibe, dann ist H auch eine 01:14:17.280 --> 01:14:17.880 Tautologie. 01:14:17.880 --> 01:14:20.800 Das heißt, die Allgemeingültigkeit dessen, was ich vorher 01:14:20.800 --> 01:14:22.920 hingeschrieben habe, bleibt erhalten. 01:14:23.060 --> 01:14:26.600 Das, was ich neu hinschreibe, ist auch allgemeingültig, ist auch eine 01:14:26.600 --> 01:14:27.140 Tautologie. 01:14:29.320 --> 01:14:32.500 Alle Aktionen, die ich hingeschrieben habe, sind Tautologien. 01:14:32.600 --> 01:14:33.980 Die sind gerade so gewählt. 01:14:34.680 --> 01:14:38.200 Und der Modus Ponens gemäß dieses Lemmas erhält auch die 01:14:38.200 --> 01:14:39.380 Allgemeingültigkeit. 01:14:41.460 --> 01:14:46.500 Das heißt, aus diesen beiden einfachen Sätzen kann ich ganz schleich 01:14:46.500 --> 01:14:50.500 folgern, dass jedes Theorem, das ich im Aussagenlogischen Kalkül 01:14:50.500 --> 01:14:53.100 herleite, auch eine Tautologie ist. 01:14:53.600 --> 01:14:54.880 Die Aktionen sind Tautologien. 01:14:55.020 --> 01:14:56.080 Ich habe keine Prämissen. 01:14:56.600 --> 01:14:59.800 Der Modus Ponens zerstört mir nicht die Tautologie, sondern erhält 01:14:59.800 --> 01:15:00.020 sie. 01:15:00.360 --> 01:15:01.960 Ich wende nur Tautologien an. 01:15:02.060 --> 01:15:04.180 Ich wende nur den Modus Ponens an. 01:15:04.180 --> 01:15:07.800 Das heißt, alles, was ich herleite aus der leeren Menge der Prämissen, 01:15:08.100 --> 01:15:09.480 muss eine Tautologie sein. 01:15:11.280 --> 01:15:13.080 Umgekehrt kann man das auch beweisen. 01:15:13.240 --> 01:15:18.800 Umgekehrt kann man auch beweisen, dass alles, was eine Tautologie ist, 01:15:19.320 --> 01:15:23.360 auch im Aussagenkalkül beweisbar ist. 01:15:24.600 --> 01:15:27.680 Das werden wir hier an der Stelle aber nicht beweisen, weil der Beweis 01:15:27.680 --> 01:15:30.340 wäre schwierig. 01:15:31.120 --> 01:15:34.560 Aber insgesamt hat man dann halt das Theorem und kann sagen, für jede 01:15:34.560 --> 01:15:41.280 Formel g gilt, dass g eine Tautologie ist, genau dann, wenn g auch ein 01:15:41.280 --> 01:15:43.540 Theorem ist im Aussagenlogischen Kalkül. 01:15:44.500 --> 01:15:48.020 Damit zusammengefasst, wenn es so um Tautologien geht, ist dieses 01:15:48.020 --> 01:15:49.960 Kalkül vollständig und korrekt. 01:15:52.100 --> 01:15:57.300 Wenn man sich jetzt den Beweis anschaut, dann machen wir das nächste 01:15:57.300 --> 01:15:57.620 Woche. 01:15:58.380 --> 01:16:01.180 Wie gesagt, der ist ein bisschen aufwendiger, der braucht ein paar 01:16:01.180 --> 01:16:04.000 mehr Minuten Zeit, als ich die jetzt noch habe. 01:16:04.340 --> 01:16:07.920 Dann schauen wir uns dann also nächste Woche genau an, warum dieses 01:16:07.920 --> 01:16:12.480 Aussagenlogische Kalkül vollständig ist und richtig ist. 01:16:13.540 --> 01:16:15.200 Okay, dann schön. 01:16:15.360 --> 01:16:17.540 Wir sehen uns nächste Woche, das ist Freitag. 01:16:17.820 --> 01:16:18.500 Schönes Wochenende.