WEBVTT 00:05.550 --> 00:06.770 Schönen guten Tag. 00:06.990 --> 00:09.750 Lassen Sie uns weitermachen mit Prädikaten, logischen Formeln. 00:11.290 --> 00:16.950 Und dieses Kapitel wollen wir dann auch hoffentlich heute abschließen. 00:17.990 --> 00:23.250 Und nächste Woche kommen wir dann zu etwas, wo wir diese Formeln und 00:23.250 --> 00:28.230 insbesondere auch das, was wir uns heute angucken werden, benutzen 00:28.230 --> 00:28.570 werden. 00:31.210 --> 00:33.750 Also wir sind bei Prädikaten, logischen Formeln. 00:33.870 --> 00:37.450 Hier unten, das ist eine der letzten Folien vom letzten Mal, sehen Sie 00:37.450 --> 00:38.010 nochmal eine. 00:38.210 --> 00:40.410 Also es gibt erstens Terme. 00:41.370 --> 00:43.990 Die sind aus variablen Symbolen, Konstantensymbolen und 00:43.990 --> 00:45.670 Funktionssymbolen zusammengesetzt. 00:46.770 --> 00:48.890 Dann gibt es atomare Formeln. 00:50.230 --> 00:55.030 Das sind also Prädikatensymbole und dahinter steht eine Anzahl Terme. 00:55.910 --> 00:58.530 Die passende Anzahl für das Prädikatensymbol. 01:00.050 --> 01:06.050 Und es gibt insbesondere ein ausgezeichnetes Prädikatensymbol, 01:06.130 --> 01:09.010 Redaktionssymbol, was wir als Gleichheit mit einem Punkt drüber 01:09.010 --> 01:09.470 schreiben. 01:12.410 --> 01:16.010 Und das dann nicht... das hat zwei Argumente, aber die schreiben wir 01:16.010 --> 01:18.330 nicht dahinter in Klammern, sondern eins links davon, eins rechts 01:18.330 --> 01:20.590 davon, wie man das so gewohnt ist vom Gleichheitszeichen. 01:20.590 --> 01:25.950 Und es gibt die Quantoren, so ein umgedrehtes A für eine L-Quanto und 01:25.950 --> 01:26.990 ein umgedrehtes E. 01:27.210 --> 01:33.870 Also das hier ist zum Beispiel eine prädikatenlogische Formel und wir 01:33.870 --> 01:36.150 haben darüber geredet, was ist eine Interpretation. 01:36.950 --> 01:40.050 Da legt man also irgendwie so einen Grundbereich fest von Objekten, 01:40.110 --> 01:41.970 über die man vielleicht gerade reden möchte. 01:44.070 --> 01:47.790 Und man sagt für jedes Kontrastantensymbol, welches Objekt soll es 01:47.790 --> 01:48.230 bedeuten. 01:48.330 --> 01:51.610 Und man sagt für jedes Funktionssymbol, welche Abbildung soll es 01:51.610 --> 01:55.410 bedeuten auf den Elementen der Grundmenge, die man sich ausgesucht 01:55.410 --> 01:55.650 hat. 01:56.110 --> 01:57.590 Das muss also immer zusammenpassen. 01:58.690 --> 02:02.450 Und man sagt auch, wie soll jedes Relationssymbol interpretiert 02:02.450 --> 02:02.830 werden. 02:04.090 --> 02:08.150 Wobei dieses spezielle Gleichheitssymbol wird immer als Identität 02:08.150 --> 02:08.890 interpretiert. 02:09.010 --> 02:11.810 Da gibt es einfach keinen Spielraum. 02:12.710 --> 02:18.550 Aber alle anderen Relationssymbole können irgendwie interpretiert 02:18.550 --> 02:23.450 werden als entsprechende 1, 2, 3, wie vielstellige auch immer, 02:23.610 --> 02:24.370 Relationen. 02:25.650 --> 02:29.970 Und also zum Beispiel so ein zweistelliges Relationssymbol würde 02:29.970 --> 02:33.070 vielleicht interpretiert als, wenn wir als Grundbereich die 02:33.070 --> 02:34.550 natürlichen Zahlen haben, so etwas wie kleinergleich. 02:35.570 --> 02:39.990 Ein einstelliges Relationssymbol, das ist dann sozusagen so etwas, 02:40.350 --> 02:43.370 wird interpretiert durch eine Teilmenge einfach des Grundbereiches. 02:44.110 --> 02:48.150 Also das beschreibt irgendwie eine Eigenschaft, die ein Objekt haben 02:48.150 --> 02:48.970 kann oder nicht. 02:49.730 --> 02:51.530 Primzahl oder nicht zum Beispiel. 02:52.910 --> 02:56.170 Und diese Formel, die ich hier unten hingeschrieben habe, wenn Sie 02:56.170 --> 03:00.530 sich das angucken, die Struktur ist vorne irgendetwas. 03:02.350 --> 03:06.150 Und dann Implikationspfeil und dann in runden Klammern eine zweite 03:06.150 --> 03:08.390 Formel, Implikationspfeil, wieder die erste. 03:09.070 --> 03:13.610 Also es hat genau die Struktur, wie diese aussagenlogische Formel P 03:13.610 --> 03:18.850 impliziert, in Klammern Q impliziert P. Und von dieser 03:18.850 --> 03:22.410 aussagenlogischen Formel zum Beispiel hat man sich mal überlegt, da 03:22.410 --> 03:25.910 ist ganz egal, welche Wahrheitswerte P und Q haben, die ganze Formel 03:25.910 --> 03:26.590 ist immer wahr. 03:27.430 --> 03:31.910 Und folglich die prädikatenlogische Formel hier unten, egal wie Sie 03:31.910 --> 03:36.270 das interpretieren, egal ob das Rxy wahr ist oder falsch, egal ob 03:36.270 --> 03:40.090 diese allquantifizierte Formel wahr ist oder falsch, einfach aufgrund 03:40.090 --> 03:43.390 der Struktur, die ganze Formel wird immer wahr sein. 03:45.490 --> 03:49.090 Also Beobachtung 1, es gibt Formeln, die sind immer wahr in jeder 03:49.090 --> 03:52.570 Interpretation, die heißen jetzt auch bei prädikatenlogischen Formeln 03:52.570 --> 03:55.290 dann eben im Allgemeinen allgemeingültig. 03:56.530 --> 04:01.970 Und zum einen, Sie können jede Tautologie aus der Aussagenlogik 04:01.970 --> 04:04.550 nehmen, statt der Variablen schreiben Sie irgendwelche Formeln hin, 04:05.130 --> 04:06.910 schärflich ist eine allgemeingültige Formel. 04:06.910 --> 04:09.990 Aber es gibt eben auch allgemeingültige Formeln, die nicht die 04:09.990 --> 04:13.550 Struktur einer Tautologie haben, sondern weil das aus anderen Gründen 04:13.550 --> 04:15.170 sozusagen immer wahr ist. 04:20.890 --> 04:25.270 Und wir sagen, eine Interpretation ist ein Modell für eine Formel oder 04:25.270 --> 04:29.590 eine Menge von Formeln, wenn eben in dieser Interpretation die Formeln 04:29.590 --> 04:30.370 alle wahr sind. 04:32.170 --> 04:32.690 Gut. 04:33.650 --> 04:39.010 Und allgemeingültige Formeln sind welche, die sind eben immer wahr und 04:39.010 --> 04:43.590 dass eine Formel allgemeingültig ist, notieren wir hier auch wieder 04:43.590 --> 04:46.710 dieses Zeichen, was in der Aussagenlogik auch schon mal vorkam. 04:47.390 --> 04:49.970 Senkrechter Strich, zwei Waagerechte und dahinter eine Formel. 04:49.970 --> 04:50.670 Gut. 04:54.090 --> 04:54.230 Ja. 04:55.150 --> 05:01.350 Und jetzt... also jetzt gehe ich nochmal zurück. 05:01.550 --> 05:02.390 Nee, mache ich später. 05:04.010 --> 05:11.870 Jetzt kommen wir zu etwas, das ist zum einen nützlich, wenn man das 05:11.870 --> 05:15.190 machen würde, was ich dieses Semester weglasse, über Beweisbarkeit und 05:15.190 --> 05:16.730 den sogenannten Hilbert-Kalkül. 05:17.810 --> 05:20.890 Aber zum anderen ist das, was jetzt kommt, auch etwas, was wir eben 05:20.890 --> 05:24.470 wie gesagt nächste Woche brauchen werden, wenn wir beweisen wollen, 05:24.690 --> 05:28.510 dass gewisse Algorithmen das tun, was spezifiziert ist. 05:34.620 --> 05:39.340 Und zwar geht es um freie und gebundene Variablen-Vorkommen und 05:39.340 --> 05:40.800 sogenannte Substitutionen. 05:42.000 --> 05:44.880 Wenn Sie eine prädikatenlogische Formel hinschreiben, dann 05:44.880 --> 05:47.980 offensichtlich kann da an manchen Stellen ein Variablen-Symbol 05:47.980 --> 05:48.660 auftauchen. 05:49.740 --> 05:56.640 Nämlich in Termen dürfen Variablen-Symbole vorkommen und außerhalb von 05:56.640 --> 05:59.600 Termen gibt es auch noch eine Stelle, nämlich unmittelbar hinter All- 05:59.600 --> 06:00.740 oder Existenzquantor. 06:00.740 --> 06:06.620 Und was uns jetzt aber erstmal nur interessiert, sind diese ganzen 06:06.620 --> 06:10.020 Vorkommen von Variablen-Symbolen in Termen. 06:10.560 --> 06:12.440 Und die Terme stecken in atomaren Formeln. 06:13.260 --> 06:17.660 Aber es interessieren uns nicht die Stellen, wo ein Variablen-Symbol 06:17.660 --> 06:20.180 direkt hinter einem All- oder Existenzquantor steht. 06:23.400 --> 06:26.120 Eine Formel kann viele Terme enthalten. 06:27.440 --> 06:30.240 Also wenn ich Formel sage, meine ich immer prädikatenlogische Formel 06:30.240 --> 06:30.860 im Zweifelsfall. 06:32.380 --> 06:36.360 Und natürlich kann da an verschiedenen Stellen der gleiche Variable 06:36.360 --> 06:38.800 -Name x oder y oder was auch immer vorkommen. 06:39.080 --> 06:43.040 Also die gleiche Variable kann an mehreren Stellen in einer Formel 06:43.040 --> 06:43.580 vorkommen. 06:44.760 --> 06:46.840 Und da gibt es jetzt zwei Sorten. 06:46.960 --> 06:49.620 Jedes Vorkommen, das werden wir gleich geeignet definieren, heißt 06:49.620 --> 06:52.760 entweder ein freies Vorkommen oder ein gebundenes Vorkommen. 06:55.340 --> 06:59.380 Und dann, wenn man sich für jedes Vorkommen angeguckt hat, welche sind 06:59.380 --> 07:03.860 frei, welche sind gebunden, dann weiß man auch, was sind die 07:03.860 --> 07:07.020 Variablen, die mindestens einmal frei vorkommen und was sind die 07:07.020 --> 07:09.460 Variablen, die mindestens einmal gebunden vorkommen. 07:10.420 --> 07:16.020 Das sind dann diese Mengen fv aller frei, irgendwo mindestens einmal 07:16.020 --> 07:21.280 in g frei vorkommenden Variablen-Namen und bv die Menge aller gebunden 07:21.280 --> 07:22.200 vorkommenden Variablen. 07:22.460 --> 07:26.340 Und es kann durchaus sein, dass eine Variable in beiden Formen 07:26.340 --> 07:26.740 vorkommt. 07:26.860 --> 07:29.380 An einer Stelle ist es ein freies Vorkommen, an einer anderen ein 07:29.380 --> 07:30.060 gebundenes. 07:30.260 --> 07:31.220 Werden wir gleich sehen. 07:34.020 --> 07:36.440 Und das muss man jetzt irgendwie definieren. 07:36.440 --> 07:38.000 Und hier steht, wie es definiert ist. 07:39.880 --> 07:43.620 Man muss über jedes Vorkommen irgendeiner beliebigen 07:43.620 --> 07:45.160 prädikatenlogischen Formel reden. 07:45.660 --> 07:49.320 Also fangen wir bei den einfachsten Bausteinen an, bei den atomaren 07:49.320 --> 07:49.940 Formeln. 07:51.660 --> 07:56.920 Per Definitionem in einer atomaren Formel, also so Prädikatensymbol, 07:57.000 --> 07:59.520 runde Klammer auf, ein paar Terme, runde Klammer zu. 08:00.100 --> 08:01.380 Das sind die atomaren Formeln. 08:02.620 --> 08:05.700 Da haben Sie also nur hinten die Terme, wo die Variablen-Symbole 08:05.700 --> 08:06.580 vorkommen können. 08:07.060 --> 08:10.660 Und per Definitionem, alle diese Vorkommen sind freie Vorkommen. 08:12.820 --> 08:14.760 Und gebundene Vorkommen gibt es keine. 08:15.460 --> 08:18.360 Also die Menge der gebunden vorkommenden Variablen ist immer leer. 08:19.900 --> 08:23.000 Und die Menge der frei vorkommenden Variablen, das sind halt die, die 08:23.000 --> 08:27.120 an mindestens einer Stelle in irgendeinem von den Termen da stehen, 08:27.240 --> 08:29.080 hinter dem Prädikatensymbol. 08:29.080 --> 08:34.400 Und jedes Vorkommen ist ein freies Vorkommen. 08:34.800 --> 08:36.380 Es gibt keine gebundenen Vorkommen. 08:37.700 --> 08:39.860 So, da hat man es für die atomaren Formeln definiert. 08:40.320 --> 08:45.420 Und jetzt, weil man ja größere Formeln aus kleineren zusammensetzt, 08:46.620 --> 08:50.420 sieht man jetzt auch so, was ist ein freies, was ist ein gebundenes 08:50.420 --> 08:51.540 Vorkommen, weiter hoch. 08:52.160 --> 08:55.340 Wenn Sie eine Formel haben, die im Wesentlichen Negation einer anderen 08:55.340 --> 08:57.380 ist, da tut sich gar nichts. 08:58.280 --> 09:02.100 Jedes freie Vorkommen einer Variablen in H ist auch ein freies 09:02.100 --> 09:03.200 Vorkommen in Nicht-H. 09:03.640 --> 09:07.060 Und jedes gebundene Vorkommen in H ist auch ein gebundenes Vorkommen 09:07.060 --> 09:07.840 in Nicht-H. 09:08.760 --> 09:09.980 Also alles bleibt gleich. 09:12.580 --> 09:16.360 Jedes Vorkommen bleibt frei, wenn es schon frei war und bleibt 09:16.360 --> 09:17.680 gebunden, wenn es schon gebunden war. 09:18.340 --> 09:20.280 Und deswegen die Mengen der gebundenen bzw. 09:20.340 --> 09:21.820 freien Variablen sind auch gleich. 09:24.640 --> 09:29.080 Analog für den Fall, dass Sie so eine größere Formel haben, die aus 09:29.080 --> 09:32.860 zwei kleineren und einem Konnektiv dazwischen festgelegt ist. 09:34.440 --> 09:39.800 Per Definitionen einfach alles, was in H, jedes Vorkommen in H1, das 09:39.800 --> 09:43.940 frei ist und auch jedes Vorkommen in H2, das frei ist, ist auch ein 09:43.940 --> 09:45.840 freies Vorkommen in der größeren Formel. 09:45.840 --> 09:50.220 Und jedes gebundene Vorkommen in H1, jedes gebundene Vorkommen in H2 09:50.220 --> 09:52.840 ist auch ein gebundenes Vorkommen in der größeren Formel. 09:54.660 --> 09:56.860 Für und oder Implikation. 09:57.640 --> 10:01.740 Und deswegen die Menge der gebunden vorkommenden Variablen kriegen Sie 10:01.740 --> 10:05.200 durch Vereinigung der Variablen, die in H1 gebunden vorkommen, 10:05.680 --> 10:08.860 vereinigt mit der Menge der Variablen, die in H2 gebunden vorkommen. 10:08.860 --> 10:10.960 Und genauso für die freien Variablen. 10:11.080 --> 10:15.520 Freie Variablen in G sind die, die in H1 oder in H2 frei vorkommen. 10:15.840 --> 10:16.520 Oder in beiden. 10:18.100 --> 10:21.200 Ja und auch die einzelnen Vorkommen, freie Vorkommen bleiben freie, 10:21.280 --> 10:23.640 gebundene bleiben gebundene, wenn Sie da zu größeren Formeln 10:23.640 --> 10:24.080 übergehen. 10:26.060 --> 10:28.260 So und das Einzige, was jetzt noch fehlt, sind die Formeln mit dem 10:28.260 --> 10:29.100 Quantor vorne dran. 10:30.120 --> 10:32.720 Und das ist auch der einzige Fall, wo etwas Interessantes passiert, 10:33.320 --> 10:35.080 denn bis jetzt war das irgendwie alles banal. 10:35.940 --> 10:41.400 Wenn Sie eine Formel haben, der Formel vorne ein Quantor, Allquantor 10:41.400 --> 10:45.840 oder Existenzquantor, Variable XI und dann dahinter so eine Formel H, 10:47.140 --> 10:57.860 dann, also erstens, in der großen Formel G, alle Vorkommen dieser 10:57.860 --> 11:01.740 Variable XI, über die quantifiziert wird, alle Vorkommen, die in H 11:01.740 --> 11:07.820 noch frei sind, freie Vorkommen in H von XI, die sind in der größeren 11:07.820 --> 11:11.940 Formel mit Quantor davor nicht mehr frei, sondern das sind jetzt, die 11:11.940 --> 11:13.360 heißen jetzt gebundene Vorkommen. 11:14.600 --> 11:17.100 Und das ist auch die einzige Art und Weise, wie gebundene Vorkommen 11:17.100 --> 11:18.540 von Variablen entstehen können. 11:19.500 --> 11:23.940 In atomaren Formeln gibt es keine und bei den einfacheren Varianten 11:23.940 --> 11:26.800 hier entstehen auch keine gebundenen aus dem Nichts. 11:26.800 --> 11:30.580 Also das ist die einzige Stelle, wo gebundene Variablen entstehen 11:30.580 --> 11:30.980 können. 11:31.920 --> 11:34.880 Nämlich dadurch, dass sie freie Vorkommen in der Formel H haben und 11:34.880 --> 11:36.340 jetzt ein Quantor davor schreiben. 11:39.980 --> 11:44.340 Also gebundene Variablen, die in G vorkommen, also alle, die in H 11:44.340 --> 11:46.260 vielleicht schon gebunden sind, die bleiben gebunden. 11:47.540 --> 11:52.660 Und dazu kommt die Variable XI, falls sie vorher in H noch frei 11:52.660 --> 11:52.960 vorkamen. 11:52.960 --> 11:54.720 Wenn nicht, dann nicht. 11:56.000 --> 12:00.700 Wenn das XI gar nicht frei vorkommt in H, dann bindet dieser Quantor 12:00.700 --> 12:02.780 auch keine Variablen vorkommen, wie man sagt. 12:02.980 --> 12:04.160 Also da passiert dann nichts. 12:05.080 --> 12:15.760 Und aus der Menge der in H frei vorkommenden Variablen fliegt das XI, 12:15.760 --> 12:19.520 über das quantifiziert wird, raus, explizit weg. 12:22.060 --> 12:29.240 Und alle Vorkommen von XI, und zwar die noch freien Vorkommen in H 12:29.240 --> 12:31.060 waren, sind jetzt gebundene Vorkommen. 12:32.220 --> 12:35.120 Und alle anderen Vorkommen ändern sich nicht. 12:35.220 --> 12:37.780 Was vorher frei war in H, ist hinterher auch noch frei. 12:38.020 --> 12:41.320 Also wenn es nicht XI ist, sondern irgendein anderes XJ. 12:42.040 --> 12:44.760 Und was vorher schon gebunden war, ist hinterher immer noch gebunden. 12:45.440 --> 12:45.920 So. 12:48.280 --> 12:52.900 Und man redet jetzt dann davon, dass die Vorkommen der Variablen XI, 12:53.020 --> 12:57.000 über die jetzt hier quantifiziert wird, die in H noch frei sind, da 12:57.000 --> 13:00.020 sagt man, die sind irgendwie so im Wirkungsbereich dieses Quantors, 13:00.140 --> 13:01.400 der da jetzt vorne dran steht. 13:02.000 --> 13:04.480 Und man sagt dann auch, die freien Vorkommen werden durch diesen 13:04.480 --> 13:05.720 Quantor gebunden. 13:06.540 --> 13:10.480 Das ist genau die einzige Stelle, wo gebundene Variablenvorkommen 13:10.480 --> 13:11.220 entstehen können. 13:13.960 --> 13:16.900 Und eine Formel heißt geschlossen, wenn es überhaupt keine freien 13:16.900 --> 13:17.820 Variablen mehr gibt. 13:19.980 --> 13:20.540 Nirgends. 13:22.940 --> 13:29.140 Das kann passieren, entweder weil man überhaupt in den ganzen Termen 13:29.140 --> 13:31.340 auch schon gar keine freien Variablen hatte, alles nur 13:31.340 --> 13:33.260 Konstantensymbole, könnte ja sein. 13:34.180 --> 13:39.200 Und wenn doch, dann eben jedes Vorkommen muss in irgendeiner Teilform, 13:39.320 --> 13:42.620 da muss davor ein Quantor stehen, der diese freien Vorkommen bindet. 13:44.820 --> 13:45.780 So, Beispiele. 13:46.560 --> 13:50.700 Hier ist eine Formel, irgendetwas hingeschrieben einfach, damit man 13:50.700 --> 13:52.200 das sieht, was man sehen sollte. 13:52.860 --> 13:58.700 Also wir interessieren uns für die Vorkommen von Variablen irgendwo in 13:58.700 --> 13:59.260 Termen. 14:00.820 --> 14:03.580 Da gibt es also hier vier Vorkommen, da gibt es hier vorne bei dem 14:03.580 --> 14:07.140 ersten R von X und Y ein Vorkommen von X, ein Vorkommen von Y. 14:08.020 --> 14:11.440 Und da hinten in dem hinteren R von X und Y nochmal ein Vorkommen von 14:11.440 --> 14:12.540 X, ein Vorkommen von Y. 14:13.380 --> 14:16.900 Dieses X hinter dem Allquantor, das Y hinter dem Existenzquantor, das 14:16.900 --> 14:17.820 interessiert uns nicht. 14:20.820 --> 14:22.100 Und jetzt gucken wir uns die an. 14:22.200 --> 14:28.220 Das erste Vorkommen von X hier vorne, das ist ein gebundenes 14:28.220 --> 14:31.220 Vorkommen, denn das steht im Wirkungsbereich dieses Allquantors. 14:31.220 --> 14:35.020 Der erstreckt sich von hier ganz vorne bis ganz, ganz hinten. 14:35.160 --> 14:37.240 Also die zugehörigen Klammer zu bis dahinten. 14:38.780 --> 14:42.180 Ich weiß gar nicht, ob diese Setzung von Klammern irgendwie unsere 14:42.180 --> 14:44.880 Syntax offiziell hergibt, aber Sie wissen, was gemeint ist. 14:46.540 --> 14:49.820 Also das erste, dieses sechste Zeichen in der Formel, das ist das 14:49.820 --> 14:52.840 sechste Allquantor X, Klammer auf, 3, 4, 5, 6. 14:53.420 --> 14:56.420 Das ist ein gebundenes Vorkommen von X und ist im Wirkungsbereich des 14:56.420 --> 14:57.120 Allquantors. 14:58.700 --> 15:02.000 Dann gibt es noch ein Vorkommen von X dahinten, das ist, wenn ich 15:02.000 --> 15:03.160 richtig gezählt habe, das 15. 15:03.620 --> 15:04.720 Zeichen in der Formel. 15:05.660 --> 15:07.880 Und das ist auch ein gebundenes Vorkommen, das ist nämlich auch im 15:07.880 --> 15:09.280 Wirkungsbereich dieses Allquantors. 15:11.580 --> 15:13.860 Der Allquantor erstreckt sich über die ganze Formel. 15:17.570 --> 15:23.070 Und das sind die beiden einzigen Vorkommen von X und beide sind 15:23.070 --> 15:24.130 gebundene Vorkommen. 15:24.130 --> 15:28.250 Also erstens, X ist in der Menge der gebundenen Vorkommenden 15:28.250 --> 15:32.550 Variablen, das steht hier unten links in der letzten Zeile da. 15:32.630 --> 15:36.410 X gehört zu den gebundenen Vorkommenden Variablen, aber nicht frei, es 15:36.410 --> 15:38.290 fehlt bei den freien Vorkommenden Variablen. 15:38.850 --> 15:40.010 Nur gebundene Vorkommen. 15:40.850 --> 15:41.850 Wie ist es beim Y? 15:42.270 --> 15:44.870 Das erste ist hier das vordere Y. 15:45.970 --> 15:49.510 Das steht nicht im Wirkungsbereich irgendeines Quantors, davor steht 15:49.510 --> 15:53.130 nur ein für alle X, da steht nirgends ein für alle Y oder es gibt ein 15:53.130 --> 15:53.390 Y. 15:54.130 --> 15:58.290 Deswegen, dieses erste Vorkommen ist ein freies Vorkommen und deswegen 15:58.290 --> 16:01.950 gehört auch Y hier hinten zu den frei Vorkommenden Variablen. 16:03.550 --> 16:08.090 Und das zweite Y ist aber ein gebundenes Vorkommen, denn das ist im 16:08.090 --> 16:09.970 Wirkungsbereich dieses Existenzquantors. 16:12.550 --> 16:17.330 Also Y kommt hier hinten, das zweite Vorkommen ist ein gebundenes, 16:17.390 --> 16:20.550 also Y gehört zu den gebundenen Vorkommenden Variablen, aber auch zu 16:20.550 --> 16:21.590 den frei Vorkommenden. 16:21.590 --> 16:25.150 Sie sehen, eine Variable kann beides machen, einmal frei Vorkommen, 16:25.250 --> 16:26.530 einmal gebunden oder mehrfach. 16:31.190 --> 16:35.650 Das sind freie und gebundene Vorkommen von Variablen. 16:42.340 --> 16:45.060 Und wofür das wichtig ist, das werden Sie dann gleich noch merken, 16:45.160 --> 16:46.240 warum man da aufpassen will. 16:47.680 --> 16:57.840 So, und jetzt kommen wir zu sogenannten Substitutionen und das ist 16:57.840 --> 17:02.480 genau etwas, was wir dann das nächste Mal auch brauchen werden. 17:02.560 --> 17:03.580 Was ist eine Substitution? 17:04.320 --> 17:08.340 Eine Substitution ist eine Abbildung, die sagt einem, also erlaubt es 17:08.340 --> 17:12.060 einem zu sagen, ich möchte jede Variable ersetzen durch irgendeinen 17:12.060 --> 17:14.220 Term, der vielleicht komplizierter ist. 17:15.200 --> 17:18.100 Sie können eine Variable natürlich auch durch sich selbst ersetzen, 17:18.220 --> 17:19.340 das ist auch erlaubt. 17:19.480 --> 17:22.140 Und das ist auch typischerweise das, was für die meisten Variablen 17:22.140 --> 17:22.540 passiert. 17:22.740 --> 17:28.500 Also häufig will man nur über Substitutionen reden, wo kaum eine 17:28.500 --> 17:33.360 Variable angefasst wird außer einer und da alle freien Vorkommen 17:33.360 --> 17:35.660 dieser Variable sollen ersetzt werden durch einen Term. 17:36.400 --> 17:40.400 Aber im Allgemeinen, also jede Variable wird ersetzt durch irgendeinen 17:40.400 --> 17:40.740 Term. 17:41.640 --> 17:46.820 Das können Sie also im Wesentlichen beschreiben mit der Vereinbarung, 17:47.480 --> 17:50.320 wenn nichts explizit gesagt wird, die Variable wird einfach durch sich 17:50.320 --> 17:51.000 selber ersetzt. 17:51.400 --> 17:56.660 Durch so eine Menge von Paaren, Variable xij soll ersetzt werden durch 17:56.660 --> 17:59.260 irgendeinen Term, Sigma von xij. 17:59.260 --> 18:05.920 Und das schreibt man dann üblicherweise, warum auch immer, so Variable 18:05.920 --> 18:07.100 Schrägstrich Term. 18:11.200 --> 18:15.360 Und es ist auch üblich, eben die ganzen Fälle, wo eine Variable sich 18:15.360 --> 18:18.160 gar nicht ändert, die überall nur durch sich selbst ersetzt werden, 18:18.220 --> 18:19.520 das alles nicht mit hinzuschreiben. 18:19.940 --> 18:24.060 Und dann schreibt man hier sowas wie Sigma und dann im Index die Menge 18:24.060 --> 18:26.940 aller Substitutionen, die wirklich etwas ändern. 18:27.780 --> 18:32.580 Also Sigma und dann im Index x soll ersetzt werden durch c und y soll 18:32.580 --> 18:34.000 ersetzt werden durch f von x. 18:36.400 --> 18:40.440 Das ist also so eine Abbildung, die legt fest, x soll ersetzt werden 18:40.440 --> 18:45.460 durch c, y soll ersetzt werden durch f von x und übrigens alle anderen 18:45.460 --> 18:48.140 Variablen gar nicht, also durch sich selbst. 18:49.880 --> 18:52.600 Das ist die Konvention, wie das zu lesen ist. 18:55.500 --> 19:01.400 Und das heißt also Sigma von x, wenn Sigma diese Substitution ist, und 19:01.400 --> 19:05.320 ich spaße mir mal jetzt im Index dieses alles hinzuschreiben, für 19:05.320 --> 19:11.600 diese Substitution Sigma von x ist dann eben c, aus x, x wird ersetzt 19:11.600 --> 19:14.780 durch c, Sigma von y ist dann eben f von x. 19:14.780 --> 19:17.100 Das wird hier festgefordert, dass das immer so ist. 19:17.640 --> 19:21.500 Und für alle Variablen, die nicht x und nicht y sind, Sigma von z ist 19:21.500 --> 19:22.040 einfach z. 19:22.780 --> 19:23.640 Keine Änderung. 19:24.860 --> 19:27.900 So, also so ein Sigma legt erstmal fest, was passiert mit Variablen. 19:28.680 --> 19:34.140 Und jetzt können Sie das hochziehen auf Terme, atomare Formen in der 19:34.140 --> 19:36.400 mehr oder weniger naheliegenden Art und Weise. 19:37.340 --> 19:40.660 Also erstens für ganze Terme, die nicht nur ein einzelnes Variablen 19:40.660 --> 19:44.680 -Symbol sind, sondern vielleicht etwas komplizierteres f von x und c 19:44.680 --> 19:45.220 oder so. 19:46.280 --> 19:47.260 Was macht man da? 19:47.780 --> 19:51.920 Also wenn der Term nur eine Variable ist, naja, dann macht man halt 19:51.920 --> 19:53.540 das, was die Substitution vorschreibt. 19:54.200 --> 19:58.260 Wenn der Term ein Konstantensymbol ist, dann lässt man das 19:58.260 --> 20:01.640 Konstantensymbol einfach so, da kommen keine Variablen vor, die man 20:01.640 --> 20:02.280 ersetzen kann. 20:03.160 --> 20:06.340 Also Substitution angewendet auf ein Konstantensymbol ist wieder das 20:06.340 --> 20:07.120 Konstantensymbol. 20:07.780 --> 20:10.760 Und wenn Sie einen Term haben, da steht vorne ein Funktionssymbol und 20:10.760 --> 20:13.540 dann in Klammern ein paar Terme, dann schreiben Sie das 20:13.540 --> 20:15.980 Funktionssymbol ab und die Klammern auch. 20:16.660 --> 20:20.400 Und die Terme einzeln, da lassen Sie auf jeden Term die Substitution 20:20.400 --> 20:20.900 los. 20:22.900 --> 20:26.800 Und auf diese Art und Weise, das ist eine rekursive Definition oder 20:26.800 --> 20:30.380 induktive, damit haben wir keine Probleme mehr, wir wissen, wie es 20:30.380 --> 20:30.980 gemeint ist. 20:32.140 --> 20:35.520 Damit machen Sie dann aus so einer Substitution, die nur für Variablen 20:35.520 --> 20:39.880 festgelegt ist, eine Abbildung, die jetzt für ganze Terme, für alle 20:39.880 --> 20:41.140 Terme festgelegt ist. 20:41.900 --> 20:44.720 Also formal sollte man die Sicherheitshalber vielleicht erstmal Sigma 20:44.720 --> 20:45.480 -Strich nennen. 20:46.320 --> 20:50.520 Und nicht mehr Sigma, sonst steht hier Sigma von X ist Sigma von S. 20:51.160 --> 20:54.600 Sigma von X ist Sigma von X, das sieht irgendwie doof aus. 20:55.540 --> 20:58.400 Aber wenn wir also erstmal verstanden haben, was gemeint ist, dann 20:58.400 --> 21:00.820 lassen wir den Strich wieder weg und schreiben immer noch Sigma von S 21:00.820 --> 21:03.540 und meinen aber jetzt dann verallgemeinert auf Terme. 21:07.040 --> 21:11.080 Also die Substitutionen wie eben X ersetzen durch C, Y durch F von X, 21:11.280 --> 21:15.280 angewendet auf X gibt C, angewendet auf Y gibt F von X, angewendet auf 21:15.280 --> 21:21.280 den Termen G von Y und X gibt G abschreiben und Y ersetzen durch F von 21:21.280 --> 21:21.580 X. 21:22.480 --> 21:27.920 Also jedes Vorkommen von Y in dem Originalterm ersetzen durch F von X 21:27.920 --> 21:33.580 und jedes Vorkommen von X in dem Originalterm, das hintere hier, 21:34.140 --> 21:34.980 ersetzen durch C. 21:37.480 --> 21:40.180 Und bitte hier, das X in dem F von X wird nicht auch noch gleich 21:40.180 --> 21:42.140 nochmal substituiert oder irgendwie sowas. 21:42.140 --> 21:42.720 Nein. 21:43.960 --> 21:46.560 Nur die Vorkommen im Originalterm werden ersetzt. 21:47.420 --> 21:50.960 Und wenn Sie einen Term haben, wo weder X noch Y vorkommen, dann 21:50.960 --> 21:51.860 passiert eben nichts. 21:52.640 --> 21:54.180 Bleibt eben alles wie es vorher war. 21:55.120 --> 21:56.040 Kann auch passieren. 21:58.840 --> 22:04.360 Und bitte Vorsicht, wenn Sie da Ersetzungen für mehrere Variablen 22:04.360 --> 22:07.400 angegeben haben, die werden gleichzeitig durchgeführt, nicht 22:07.400 --> 22:09.160 hintereinander in irgendeinem Sinne. 22:09.720 --> 22:13.500 Also wenn Sie zum Beispiel die Substitution haben, die sagt, X 22:13.500 --> 22:18.840 ersetzen durch Y und Y ersetzen durch X und Sie wenden das an auf den 22:18.840 --> 22:23.220 Term F von X, Y, dann sagt die Definition, das ist, naja, 22:23.300 --> 22:26.460 Funktionssymbol abschreiben und die Substitution anwenden auf X und 22:26.460 --> 22:31.520 die Substitution anwenden auf Y und dann entsteht aus dem X das Y und 22:31.520 --> 22:32.860 aus dem Y das X. 22:35.480 --> 22:39.560 Und das ist aber deutlich unterschiedlich von dem, was Sie kriegen, 22:39.640 --> 22:43.800 wenn Sie erst überall meinetwegen Y durch X ersetzen und dann im 22:43.800 --> 22:45.740 entstehenden Term überall X durch Y. 22:46.260 --> 22:49.780 Da würden Sie aus F, X, Y würden Sie F, Y und Y kriegen. 22:49.780 --> 22:53.900 Und wenn Sie hier vorne die beiden vertauschen, erst alle X durch Y 22:53.900 --> 22:57.060 und dann alle Y durch X, dann würden Sie F von X, X kriegen. 22:57.140 --> 22:58.960 Das ist nicht das, was hier rauskommt. 22:59.720 --> 23:02.740 Also alles wird sozusagen gleichzeitig erledigt, alle Ersetzungen. 23:03.720 --> 23:08.440 So, dann haben wir es für Terme und dann hochziehen auf Formeln. 23:10.040 --> 23:12.460 Substitutionen in ganzen Prädikaten, logischen Formeln. 23:13.540 --> 23:16.940 Abgesehen von quantifizierten Formeln ist das alles ganz naheliegend. 23:17.320 --> 23:20.060 Also jetzt haben wir dann eine Abbildung, nennen wir die erstmal Sigma 23:20.060 --> 23:22.380 -2 -Strich und wenn wir sie definiert haben, nennen wir die auch 23:22.380 --> 23:23.460 wieder Sigma-2-Strich. 23:25.260 --> 23:30.380 Wenn Sie eine atomare Formel haben der Form T1 gleich T2, dann machen 23:30.380 --> 23:33.280 Sie halt die Substitutionen auf der linken und auf der rechten Seite. 23:36.080 --> 23:39.960 Wenn Sie eine atomare Formel haben der Form Prädikatensymbol und in 23:39.960 --> 23:41.960 runden Klammern ein paar Terme, dann schreiben Sie das 23:41.960 --> 23:46.460 Prädikatensymbol ab und machen die Substitutionen an allen Termen. 23:47.080 --> 23:50.640 Also hier dann jeder Term einzeln, alles substituiert. 23:51.720 --> 23:59.820 Und bei so Formeln Negation und oder Implikation, machen Sie einfach 23:59.820 --> 24:02.940 die Substitutionen in allen Teilformen, in der einen oder in den 24:02.940 --> 24:03.260 beiden. 24:05.340 --> 24:09.460 Und die Konnektive, das wird alles abgeschrieben, da ändert man nichts 24:09.460 --> 24:10.060 an der Struktur. 24:11.860 --> 24:15.980 Dann hat man das verallgemeinert auf Formeln ohne Quantoren und dann 24:15.980 --> 24:19.180 muss man auch sagen, was ist bei Formeln mit Quantoren und bis hierher 24:19.180 --> 24:21.860 war wieder alles banal und jetzt wieder bei Quantoren ist die einzige 24:21.860 --> 24:23.120 Stelle, wo es interessant wird. 24:25.720 --> 24:30.140 Und dazu brauchen wir noch ein bisschen Notation. 24:30.880 --> 24:35.740 Nämlich, wenn Sie eine Substitution haben, die für ein paar Variablen 24:35.740 --> 24:38.520 vorschreibt, dass sie durch irgendetwas anderes ersetzt werden sollen, 24:38.860 --> 24:39.540 möglicherweise. 24:41.860 --> 24:45.800 Und wenn die Menge der interessanten Substitutionen diese Menge groß S 24:45.800 --> 24:48.780 ist, die da im Index von dem Sigma steht, dann wollen wir jetzt noch 24:48.780 --> 24:52.600 einführen so eine Notation Sigma und im Index steht jetzt S minus X 24:52.600 --> 24:53.200 einfach. 24:54.560 --> 24:59.440 Und das soll sein fast das gleiche wie die originale Substitution 24:59.440 --> 25:03.920 Sigma S, mit einer Ausnahme, die Variable X wird jetzt doch nicht 25:03.920 --> 25:05.860 verändert, sondern wird immer gleich gelassen. 25:08.700 --> 25:13.680 Also, wenn Sie Sigma S minus X anwenden auf X, dann ist das garantiert 25:13.680 --> 25:16.800 immer X, auch wenn vielleicht die Originalsubstitution sagt, in S 25:16.800 --> 25:19.540 steht X ersetzen durch C oder so. 25:20.500 --> 25:23.660 Wenn da gesagt wird, das X lassen wir aber weg von der Substitution, 25:23.820 --> 25:26.120 dann wird es eben nicht mehr ersetzt durch was anderes. 25:26.980 --> 25:30.340 Aber alle anderen Variablen, Y ungleich X, die werden ganz normal 25:30.340 --> 25:32.420 ersetzt wie in der Originalsubstitution. 25:33.440 --> 25:38.980 Also Beispiel, die Substitution, von der wir ausgehen, sagt X ersetzen 25:38.980 --> 25:40.940 durch C, Y ersetzen durch X. 25:43.620 --> 25:46.980 Dann das Sigma minus X, also da habe ich mir jetzt gespart, diese 25:46.980 --> 25:48.320 ganze Menge nochmal hinzuschreiben. 25:48.520 --> 25:50.040 Ich habe ja gesagt, Sigma ist das Ding. 25:50.880 --> 25:55.300 Sigma minus X, hier steht es nochmal ausführlich, ist also diese Menge 25:55.300 --> 25:58.540 von Substitutionen und jetzt aber die für X weglassen, was übrig 25:58.540 --> 26:02.640 bleibt, ist halt die Substitution, die nur noch Y ändert, nämlich Y 26:02.640 --> 26:04.400 durch X ersetzen will überall. 26:07.210 --> 26:10.050 Und alles, ja genau, und X ändert. 26:10.550 --> 26:14.990 So, und wenn Sie jetzt eine Formel haben mit einem Quantor vorne dran 26:14.990 --> 26:19.590 und Sie wollen da überall Variablen substituieren durch Terme, dann 26:19.590 --> 26:24.010 machen Sie das in der Formel, die hinter dem Quantor steht, aber Sie 26:24.010 --> 26:27.790 lassen die Finger von allen Vorkommen der Variablen, über die 26:27.790 --> 26:28.630 quantifiziert wird. 26:30.630 --> 26:33.710 Also Substitutionen durchführen in so einer Formel für alle X 26:33.710 --> 26:38.210 irgendeine Formel H, den Quantor schreiben Sie ab und in H wird 26:38.210 --> 26:42.470 substituiert, wie das die Originalsubstitution vorsieht, mit einer 26:42.470 --> 26:44.950 Ausnahme, Finger weg von X. 26:45.130 --> 26:47.950 Also Sie wenden dann nicht mehr die Originalsubstitution Sigma S an, 26:48.050 --> 26:49.750 sondern Sigma S minus X. 26:51.070 --> 26:52.770 Und genauso bei Existenzquantor. 26:55.190 --> 27:00.630 Also gebundene Vorkommen von Variablen werden nicht substituiert. 27:01.230 --> 27:02.590 Das ist das, was da steht. 27:03.710 --> 27:07.290 Hinterm Quantor, Finger weg von der Variable, über die quantifiziert 27:07.290 --> 27:07.530 wird. 27:11.630 --> 27:14.830 Ja und auch letzten Endes dafür, jetzt wenn es definiert ist, 27:14.870 --> 27:17.690 schreiben wir auch wieder einfach Sigma und nicht Sigma 1, 2, 3, ich 27:17.690 --> 27:18.530 weiß nicht wie viel Strich. 27:18.530 --> 27:25.510 Hier ist nochmal ein Beispiel, irgendeine Formel S von X und für alle 27:25.510 --> 27:26.750 X R von X und Y. 27:27.150 --> 27:29.890 Also mit einem gebundenen Vorkommen, der Variablen X. 27:31.470 --> 27:36.410 So jetzt noch unabhängig davon, was jetzt genau gemeint ist, mit 27:36.410 --> 27:37.970 welcher Substitution gemeint ist. 27:37.970 --> 27:42.610 Die Definition von Substitution sagt, naja, also Substitution von so 27:42.610 --> 27:47.690 einer Formel und eine andere Formel ist einfach Substitution in der 27:47.690 --> 27:51.090 einen Teilformel machen, das Umzeichen abschreiben, Substitution in 27:51.090 --> 27:52.030 der anderen Formel. 27:52.830 --> 27:55.970 Und Substitution in der atomaren Formel machen heißt einfach 27:55.970 --> 27:59.990 Relationssymbol abschreiben und in dem Term, der da steht, hier ist es 27:59.990 --> 28:01.910 nur einer, die Substitution machen. 28:02.190 --> 28:04.030 Also da S von Sigma X. 28:04.890 --> 28:08.710 Und hier hinten bei der Substitution in dieser allquantifizierten 28:08.710 --> 28:13.510 Formel, die Definition sagt, Quanto abschreiben und dahinter in R X Y 28:13.510 --> 28:15.610 substituieren. 28:16.290 --> 28:20.710 So wie Sigma sagt, mit Ausnahme von der Variablen X, von der lassen 28:20.710 --> 28:21.210 wir die Finger. 28:21.650 --> 28:24.370 Also Sigma minus X wird hier hinten nur angewendet. 28:25.090 --> 28:28.770 Und dann haben Sie eine Substitution, Sigma minus X, die auf so eine 28:28.770 --> 28:32.030 atomare Formel angewendet wird, also Relationssymbol abschreiben, 28:32.170 --> 28:34.830 Substitution bei den Termen. 28:34.950 --> 28:39.210 So und hier jetzt Sigma minus X angewendet auf die Variable X. 28:39.850 --> 28:43.130 Naja, die Substitution soll jetzt eben X nicht mehr verändern, also 28:43.130 --> 28:44.930 dann steht da eben einfach X. 28:47.130 --> 28:52.070 Und bis hierher ist also alles richtig für jede beliebige 28:52.070 --> 28:52.750 Substitution. 28:54.730 --> 28:58.290 Also vorne das X ist ein freies Vorkommen, das soll substituiert 28:58.290 --> 28:58.610 werden. 28:59.130 --> 29:02.470 Das hintere X, das Vorkommen ist gebunden, das wird nicht 29:02.470 --> 29:03.210 substituiert. 29:03.610 --> 29:06.750 Und das Y ist ein freies Vorkommen, das soll substituiert werden. 29:07.610 --> 29:10.990 Und jetzt, wenn Sie meinetwegen wieder die Substitutionen mit X 29:10.990 --> 29:15.550 ersetzen durch C, Y durch F von X, dann Sigma minus X sagt also nur 29:15.550 --> 29:17.490 noch Y ersetzen durch F von X. 29:18.710 --> 29:23.290 Und wenn Sie dann einfach mit der Formel hier weitermachen und in X 29:23.290 --> 29:25.890 durch C substituieren, steht da halt C. 29:26.330 --> 29:27.670 Da steht also vorne S von C. 29:28.370 --> 29:32.850 Und hier hinten Y ersetzen durch F von X, dann steht hier für alle X, 29:32.910 --> 29:34.670 R, X, F von X. 29:36.010 --> 29:37.150 So geht das, ja. 29:38.230 --> 29:41.490 Ja, und jetzt passiert hier aber etwas, da hätte es sein können, dass 29:41.490 --> 29:45.730 jetzt vielleicht doch schon einer mal vorsichtig seinen Arm hebt und 29:45.730 --> 29:49.990 leichte Bedenken anmeldet, ob das denn so gewünscht ist oder nicht. 29:51.090 --> 29:54.030 Also bei diesem letzten Beispiel, das habe ich gerade so gewählt, dass 29:54.030 --> 29:58.830 hier etwas passiert, das will man des Öfteren nicht. 29:59.650 --> 30:04.030 Nämlich, Sie haben ja hier in der Originalformel hinten das Y stehen, 30:04.210 --> 30:09.530 ja, so freies Vorkommen in dieser Teilformel für alle X, R, X, Y. 30:10.710 --> 30:15.950 Und jetzt wird für Y ein Term F von X rein substituiert. 30:17.130 --> 30:21.910 Und das Y steht dummerweise im Wirkungsbereich eines Allquantors für 30:21.910 --> 30:25.810 das X und dann taucht da auf einmal ein X auf, das auch gebunden ist. 30:26.130 --> 30:29.170 An einer Stelle, wo vorher ein ungebundenes Y stand. 30:31.230 --> 30:34.890 Das kann man natürlich, also es ist ein Haupt, ja, es passiert 30:34.890 --> 30:40.450 einfach, so wie Substitutionen definiert sind, aber das ist etwas, was 30:40.450 --> 30:41.590 man manchmal nicht will. 30:42.670 --> 30:48.010 Und wenn ich mich recht erinnere, ist eine der Übungsaufgaben so ein 30:48.010 --> 30:50.030 Beispiel bauen, wo da was kaputt geht. 30:51.170 --> 30:54.690 Also für eine gewisse Definition von kaputt gehen. 30:57.990 --> 31:01.370 Also was man des Öfteren will, ist, dass sowas nicht passiert und weil 31:01.370 --> 31:06.130 man das öfter mal haben will, gibt man diesem Phänomen einen Namen. 31:07.510 --> 31:12.630 Wir sagen, wenn Sie eine Substitution haben und eine Formel G, dann 31:12.630 --> 31:17.910 wollen wir sagen, dass die Substitution kollisionsfrei ist, wenn das 31:17.910 --> 31:19.770 nicht passiert, was wir gerade gesehen haben. 31:20.390 --> 31:25.170 Also wenn die Substitution sagt, eine Variable XI soll durch etwas 31:25.170 --> 31:27.530 ersetzt werden, was etwas anderes ist als XI. 31:27.530 --> 31:32.590 Und in dem Term, der da vorgeschrieben wird als Ersatz für das XI, 31:32.710 --> 31:34.770 kommt irgendeine Variable XJ vor. 31:36.210 --> 31:42.290 Dann soll bitte jedes freie Vorkommen von dem XI, das war gerade unser 31:42.290 --> 31:48.170 Y, nicht im Wirkungsbereich so eines Quantens für das XJ stehen, 31:48.250 --> 31:51.090 sodass hinterher, wenn wir die Substitution machen, dieses XJ, was da 31:51.090 --> 31:53.030 reingesetzt wird, auf einmal gebunden ist. 31:55.270 --> 31:59.590 Also wenn XI durch etwas anderes ersetzt wird und in dem Term kommt 31:59.590 --> 32:04.590 ein XJ vor, dann sollen die freien Vorkommen, wo man die Substitution 32:04.590 --> 32:09.230 vornimmt, nicht so sein, dass das, was man da reinsetzt, das XJ 32:09.230 --> 32:10.710 hinterher auf einmal gebunden ist. 32:12.730 --> 32:16.230 Und das, was wir gerade hatten, war ein Beispiel für eine 32:16.230 --> 32:18.410 Substitution, die nicht kollisionsfrei ist. 32:18.410 --> 32:21.650 Also in dieser Teilformel für alle X, R, X, Y. 32:22.250 --> 32:26.790 Wenn Sie hier für Y das F von X einsetzen, dann haben Sie hier auf 32:26.790 --> 32:31.850 einmal diese Variable X, die da in dem Term, der rein substituiert 32:31.850 --> 32:35.110 wird, und dann ist das auf einmal im Wirkungsbereich dieses Quantors 32:35.110 --> 32:35.810 für alle X. 32:36.330 --> 32:38.770 Das ist nicht kollisionsfrei. 32:39.710 --> 32:43.770 Wenn da gestanden hätte, Y ersetzen durch F von Z, dann ist das 32:43.770 --> 32:44.650 kollisionsfrei. 32:44.950 --> 32:48.930 Dann steht halt hier hinten dann, wenn Sie substituieren, R von X und 32:48.930 --> 32:53.310 F von Z und das Z ist immer noch frei. 32:54.030 --> 32:56.430 Das ist das, was man möchte, öfter mal. 32:58.290 --> 33:02.750 Und das ist wirklich ein wichtiger Begriff, auch zum Beispiel nächste 33:02.750 --> 33:02.970 Woche. 33:03.910 --> 33:08.570 Man will des Öfteren Substitutionen, die in diesem Sinne harmlos sind, 33:08.890 --> 33:09.710 kollisionsfrei. 33:14.050 --> 33:20.110 Soviel zu freien und gebundenen Vorkommen von Variablen und 33:20.110 --> 33:21.130 Substitutionen. 33:22.270 --> 33:25.390 Und bei Substitutionen, also es werden immer nur freie Vorkommen 33:25.390 --> 33:28.610 substituiert, keine Vorkommen, die schon gebunden sind. 33:28.950 --> 33:30.010 Davon lässt man die Finger. 33:32.030 --> 33:35.950 Und jetzt kommen noch ein paar logisch äquivalente Formeln. 33:38.070 --> 33:40.250 Also es wird erstens definiert, was das ist. 33:40.330 --> 33:41.350 Das ist ganz einfach. 33:42.690 --> 33:46.690 Zwei Formeln sind logisch äquivalent, wenn sie die gleichen Modelle 33:46.690 --> 33:47.090 haben. 33:49.750 --> 33:53.010 Also egal, welche Interpretation Sie nehmen, egal, welche 33:53.010 --> 33:56.270 Variablenbelegung Sie nehmen, wenn Sie die beiden Formeln auswerten, 33:56.830 --> 33:59.510 entweder sind beide wahr oder es sind beide falsch. 34:01.670 --> 34:03.470 Die Formeln haben die gleichen Modelle. 34:06.290 --> 34:08.910 Den Begriff hatten wir, glaube ich, in der Aussagenlogik auch schon. 34:12.570 --> 34:17.010 Und wenn Sie zwei logisch äquivalente Formeln G und H haben, dann 34:17.010 --> 34:17.950 können Sie das folgende machen. 34:18.030 --> 34:20.890 Wenn Sie eine große Formel haben, da taucht irgendeine Formel G auf 34:20.890 --> 34:25.170 und Sie wissen, G ist logisch äquivalent zu H, dann können Sie die 34:25.170 --> 34:27.410 Formel G durch die Formel H ersetzen. 34:28.330 --> 34:33.270 Wenn Sie dann die entstehende große Formel angucken, egal welche 34:33.270 --> 34:36.090 Interpretation Sie angucken, an der Stelle, wo Sie was ersetzt haben, 34:36.310 --> 34:39.770 da wird immer beim Auswerten der gleiche Wahrheitswert entstehen. 34:40.090 --> 34:45.230 Die ganze Formel ändert nie ihren Wahrheitswert im Vergleich zu der 34:45.230 --> 34:46.010 ursprünglichen Formel. 34:46.010 --> 34:50.270 Wenn Sie in F G durch H ersetzen und G und H sind logisch äquivalent, 34:50.350 --> 34:53.990 dann F und die entstehende Formel F' sind auch logisch äquivalent. 34:54.630 --> 34:59.450 Und wenn die zwei Formeln logisch äquivalent sind, dann ist auch die 34:59.450 --> 35:03.710 zweiseitige Implikation, G impliziert H und H impliziert G, ist dann 35:03.710 --> 35:04.950 allgemeingültig. 35:05.350 --> 35:08.730 Denn entweder, wenn Sie es auswerten, beide sind falsch oder beide 35:08.730 --> 35:09.270 sind wahr. 35:09.950 --> 35:12.870 Andere Fälle gibt es nicht, wenn die logisch äquivalent sind und das 35:12.870 --> 35:13.510 ist dann immer wahr. 35:18.870 --> 35:22.050 Und hier sind jetzt noch so ein paar logisch äquivalente Formeln. 35:23.210 --> 35:25.950 Das kann man jedes Mal irgendwie nachrechnen oder so und so ein 35:25.950 --> 35:27.730 bisschen argumentieren, warum das denn so ist. 35:28.570 --> 35:32.610 Und die stehen jetzt vor allem deswegen hier, weil das auch Dinge 35:32.610 --> 35:35.910 sind, die man dann im alltäglichen Leben im Umgang mit so Formeln halt 35:35.910 --> 35:38.710 anwendet. 35:38.990 --> 35:44.610 Zum Beispiel, also jetzt im folgenden hier, G und H sind beliebige aus 35:44.610 --> 35:49.310 Prädikaten logische Formeln und X, I, J sind beliebige Variablen. 35:49.870 --> 35:54.950 Nicht für alle X, I, G ist logisch äquivalent zu Es gibt ein X, I 35:54.950 --> 35:55.710 nicht von G. 35:58.780 --> 36:01.940 Wenn Sie sich das überlegen, das klingt irgendwie plausibel. 36:02.280 --> 36:05.640 Und wenn Sie sozusagen anfangen, die Auswertungsfunktion auf die 36:05.640 --> 36:08.660 beiden Formeln oder auf die linke Formel nicht für alle X, I, G 36:08.660 --> 36:10.800 anzuwenden, dann merken Sie schon, was da passiert. 36:10.800 --> 36:15.280 Wenn nicht für alle X, I, G wahr ist, das ist genau dann der Fall, 36:15.380 --> 36:20.120 wenn Sie einen Wert D finden können, den Sie für die Variable X, I 36:20.120 --> 36:26.260 einsetzen und dann wird hinten G falsch und das heißt, nicht G wird 36:26.260 --> 36:29.600 wahr und dann gibt es so einen D, den Sie da einsetzen können und dann 36:29.600 --> 36:31.680 ist die Formel Es gibt ein X, I nicht G wahr. 36:32.220 --> 36:35.720 Also wenn etwas nicht für alle gilt, dann gibt es eins, für das es 36:35.720 --> 36:36.200 nicht gilt. 36:37.220 --> 36:39.740 Das ist plausibel und tatsächlich diese Formeln sind logisch 36:39.740 --> 36:40.360 äquivalent. 36:41.220 --> 36:45.200 Umgekehrt auch, wenn es nicht so ist, dass es ein X, I gibt, sodass 36:45.200 --> 36:48.920 irgendetwas gilt, dann gilt für alle, dass es nicht gilt. 36:51.680 --> 36:55.480 Also wenn Sie Formeln haben, dann können Sie so Negationszeichen so 36:55.480 --> 36:58.600 hin und her schieben und immer wenn Sie es an Quantoren 36:58.600 --> 37:02.180 vorbeischieben, dann wird aus dem Allquantoren Existenzquantoren 37:02.180 --> 37:02.880 umgekehrt. 37:04.360 --> 37:07.260 Und der Wahrheitsgehalt der Formel ändert sich aber nicht. 37:08.440 --> 37:14.760 So, dann wenn Sie mehrere Allquantoren haben und bitte Vorsicht, wir 37:14.760 --> 37:18.160 reden hier über den Fall, dass beides zum Beispiel Allquantoren sind, 37:18.260 --> 37:22.700 für alle X, I, für alle X, J, G oder umgekehrt erst für alle X, J, 37:22.820 --> 37:24.000 dann für alle X, I, G. 37:24.480 --> 37:26.680 Die beiden Formeln sind auch logisch äquivalent. 37:27.660 --> 37:31.780 Genauso, wenn Sie zwei Existenzquantoren haben oder drei, vier, fünf, 37:32.060 --> 37:35.580 aber eben von der gleichen Sorte, nur Existenzquantoren oder nur 37:35.580 --> 37:37.940 Allquantoren, die Reihenfolge ist egal. 37:38.080 --> 37:39.600 Können Sie vertauschen, wie Sie wollen. 37:40.820 --> 37:43.940 Was Sie nicht tun dürfen ist, wenn Sie eine Existenz- und ein 37:43.940 --> 37:45.840 Allquantor haben, die einfach vertauschen. 37:47.820 --> 37:50.860 Das sind im Allgemeinen nicht logisch äquivalente Formeln. 37:52.440 --> 37:58.300 Wenn Sie in Mathematik irgendwie gelernt haben, dass es sowas wie 37:58.300 --> 38:01.220 Stetigkeit und gleichmäßige Stetigkeit gibt. 38:02.120 --> 38:05.020 Wer hat diese beiden Begriffe in irgendeiner Mathematik-Vorlesung 38:05.020 --> 38:05.360 gehört? 38:05.520 --> 38:06.120 Unlängst? 38:07.040 --> 38:08.220 So ein paar, ja. 38:08.840 --> 38:11.480 Also dann haben Sie da auch genau diesen Unterschied gesehen. 38:11.720 --> 38:14.300 Die Reihenfolge, wo steht die Existenz, wo ist der Allquantor. 38:14.480 --> 38:15.660 Das macht einen Unterschied. 38:17.080 --> 38:22.720 Dann, wenn für alle X, Y, G und H gilt, dann ist auch für alle X, Y, G 38:22.720 --> 38:23.640 und für alle X, Y, H. 38:24.820 --> 38:28.540 Oder andere Möglichkeit, wenn Sie ein Existenzquantor haben und 38:28.540 --> 38:33.460 dahinter zwei Formeln, die durch oder verbunden sind, dann ist das 38:33.460 --> 38:36.640 auch äquivalent zu es gibt ein X, Y, G oder es gibt ein X, Y, H. 38:36.640 --> 38:40.620 Aber bitte Vorsicht, wenn Sie ein Allquantor haben und dahinter ein 38:40.620 --> 38:43.820 Oder oder wenn Sie ein Existenzquantor haben und dahinter ein Und, 38:44.520 --> 38:48.460 dann sind die beiden analogen Formeln, die entstehen, nicht logisch 38:48.460 --> 38:49.160 äquivalent. 38:49.360 --> 38:50.700 Das ist, glaube ich, auch eine Übungsaufgabe. 38:50.700 --> 38:51.820 So. 38:56.390 --> 39:00.810 Und dann gibt es noch eine Möglichkeit, Formeln umzubauen. 39:01.990 --> 39:05.950 Die ist auch ziemlich banal, aber manchmal nützlich. 39:06.890 --> 39:10.370 Nämlich, wenn Sie irgendwo eine Formel haben, da steht für alle X 39:10.370 --> 39:15.930 irgendetwas, dann ist das sozusagen Willkür, dass die Variable gerade 39:15.930 --> 39:16.730 X heißt. 39:17.830 --> 39:22.710 Die können Sie auch Y oder Z oder sonst wie nennen vorausgesetzt, die 39:22.710 --> 39:26.590 Variable ist nicht anderweitig schon wieder irgendwie in Benutzung 39:26.590 --> 39:26.990 sozusagen. 39:27.970 --> 39:31.290 Also, wenn Sie eine Formel haben, sagen wir mal, für alle X, Y, G, 39:31.830 --> 39:37.730 dann dürfen Sie die Variable X, Y überall in der ganzen Formel durch 39:37.730 --> 39:38.570 X, Y ersetzen. 39:38.570 --> 39:43.510 Also, Sie machen daraus die Formel für alle X, Y und dann hinten in G 39:43.510 --> 39:45.950 ersetzen Sie überall X, Y durch X, Y. 39:46.090 --> 39:49.710 Also Substitutionen X, Y durch X, Y ersetzen in ganz G. 39:51.470 --> 39:54.490 Vorausgesetzt, diese Variable X, Y, die dann da entsteht, ist nicht 39:54.490 --> 39:57.390 auf einmal wieder im Wirkungsbereich von irgendwelchen Quantoren über 39:57.390 --> 39:57.850 das X, Y. 39:58.790 --> 40:01.650 Also, diese Substitution muss kollisionsfrei sein. 40:02.750 --> 40:04.470 Sonst passieren Unglücke. 40:04.730 --> 40:09.050 Also, Sie können das syntaktisch trotzdem durchführen, aber Sie 40:09.050 --> 40:11.510 kriegen dann nicht zwei logisch äquivalente Formeln. 40:12.910 --> 40:16.590 Die sind nur logisch äquivalent, wenn die Substitution kollisionsfrei 40:16.590 --> 40:16.870 ist. 40:18.410 --> 40:22.830 Naja, und dann gibt es noch viele andere logisch äquivalente Formeln. 40:23.710 --> 40:27.110 Zu der einen oder anderen gibt es auch noch eine Hausaufgabe. 40:27.210 --> 40:29.870 Ich glaube, das ist eine von denen hier unten auf Folie 41. 40:34.980 --> 40:38.400 Hier vielleicht noch im zweiten Punkt. 40:40.160 --> 40:46.440 Wenn Sie eine Formel haben, für alle X, Y gilt G, dann salopp 40:46.440 --> 40:52.600 gesprochen folgt daraus, wenn Sie die Formel G nehmen, den Alquantor 40:52.600 --> 40:56.620 wegmachen und das X, Y durch irgendeinen Term ersetzen und halt alle 40:56.620 --> 41:02.200 Vorkommen von X, Y durch irgendeinen Term ersetzen, dann ist das in 41:02.200 --> 41:02.540 Ordnung. 41:02.700 --> 41:06.800 Also, wenn die allquantifizierte Formel wahr ist, dann die 41:06.800 --> 41:09.600 substituierte Formel ohne den Alquantor ist auch wahr. 41:12.660 --> 41:15.700 Für die Benutzung von den Gleichheitssymbolen, es gilt das 41:15.700 --> 41:18.160 naheliegende, kann man sich auch alles überlegen. 41:18.260 --> 41:20.280 Das ist aber so banal, da brauchen wir, glaube ich, nicht drüber 41:20.280 --> 41:20.640 reden. 41:21.420 --> 41:26.760 Und dann ist der wesentliche Punkt jetzt am Ende dieses Abschnitts. 41:28.180 --> 41:33.220 Ab sofort werden wir überall auch so, ich bin geneigt, das 41:33.220 --> 41:36.300 umgangssprachlich zu nennen, an allen möglichen Stellen einfach 41:36.300 --> 41:37.420 Quantoren zu schreiben. 41:37.580 --> 41:38.180 Punkt 1. 41:39.080 --> 41:43.720 Bis jetzt haben wir immer ausgeschrieben, für jedes X es gibt ein Y. 41:44.720 --> 41:48.460 Und außerdem machen wir das noch ein bisschen salopper, als wir es 41:48.460 --> 41:49.660 hier eingeführt haben. 41:50.820 --> 41:54.960 Es gibt viele Stellen, da müsste man eigentlich schreiben sowas wie, 41:55.360 --> 42:00.600 für jedes X, wenn X eine gewisse Eigenschaft hat, dann etwas gilt. 42:01.940 --> 42:09.300 Also zum Beispiel sowas, für jedes X, wenn X aus N Null ist, dann 42:09.300 --> 42:10.140 irgendetwas. 42:10.280 --> 42:15.200 Und dafür schreiben wir dann einfach kürzer sowas wie, für alle X aus 42:15.200 --> 42:16.680 N Null, es gilt etwas. 42:16.840 --> 42:19.600 Oder es gibt ein X aus N Null, es gibt etwas. 42:21.160 --> 42:26.040 Und bei dem es gibt, ist das die Abkürzung für, es gibt ein X, das die 42:26.040 --> 42:28.020 Eigenschaft hat und F gilt. 42:28.400 --> 42:31.800 Also bei dem es gibt ein X, die Abkürzung, das ist nicht die, wo da 42:31.800 --> 42:33.580 hinten auch ein Implikationspfeil steht. 42:34.500 --> 42:38.180 Das ist anders und das ist deswegen anders, damit immer noch das gilt, 42:38.240 --> 42:41.200 was wir gerade bei den normalen Formen gesehen haben, wenn sie 42:41.200 --> 42:45.220 Negationszeichen einem Quantor vorbeischieben, dann wird einfach aus 42:45.220 --> 42:47.600 dem Allquantor ein Existenzquantor und umgekehrt. 42:48.240 --> 42:51.860 Und damit das bei dieser saloppen Notation auch noch funktioniert, 42:53.480 --> 42:56.020 muss man das eben so festlegen, wie wir es festgelegt haben. 42:56.720 --> 43:00.000 Und das ist auch das Plausible, das Intuitive. 43:00.180 --> 43:01.840 Also da müssen Sie jetzt keine Angst haben, dass Sie das groß 43:01.840 --> 43:02.500 missverstehen. 43:05.640 --> 43:09.060 Und dazu kommt jetzt noch, dass wir dann insbesondere im nächsten 43:09.060 --> 43:13.700 Kapitel dann im Allgemeinen nicht nur so Formeln hinschreiben werden 43:13.700 --> 43:17.060 und so tun, als würden wir uns für den allgemeinen Fall interessieren, 43:17.500 --> 43:21.460 alle möglichen Interpretationen, sondern typischerweise es existieren 43:21.460 --> 43:24.780 nur ganz wenige, also vielleicht nur eine Interpretation. 43:25.920 --> 43:29.680 Und dann, wenn wir sowieso wissen, was gemeint ist, also zum Beispiel 43:29.680 --> 43:32.920 die nicht negativen ganzen Zahlen und wir wollen über Additionen 43:32.920 --> 43:36.120 reden, dann schreiben wir halt ja auch gleich ein Pluszeichen und 43:36.120 --> 43:40.460 nicht ein Funktionssymbol F und sagen irgendwo, das ist zweistellig 43:40.460 --> 43:42.740 und wir meinen übrigens Additionen. 43:43.300 --> 43:45.120 Sondern wir machen es jetzt einfach ganz locker. 43:46.420 --> 43:47.040 Gut. 43:49.020 --> 43:53.440 Und wie gesagt, es gab doch so einen Abschnitt über Beweisbarkeit, 43:55.060 --> 43:57.620 aber den lassen wir dieses Semester weg. 43:58.600 --> 44:04.800 Und damit sind wir genau am Ende dieses Kapitels und mit dem 44:04.800 --> 44:06.160 Vorlesungsteil fertig. 44:06.160 --> 44:09.840 Und dann gibt es jetzt weiter mit der großen Übung und nächste Woche 44:09.840 --> 44:13.540 fangen wir an mit Algorithmen. 44:13.940 --> 44:17.120 Und wie kann man da vielleicht beweisen, dass Sie das Richtige tun? 44:17.600 --> 44:17.980 Dankeschön. 44:18.600 --> 44:19.520 Schönen guten Morgen. 44:20.580 --> 44:24.180 Herzlich willkommen zu unserer achten Übung mittlerweile. 44:25.700 --> 44:30.020 Wir haben schon über die Hälfte, also über die Hälfte der Vorlesung 44:30.020 --> 44:30.540 ist vorbei. 44:33.540 --> 44:37.160 Dann heute geht es um Prädikatenlogik. 44:38.480 --> 44:42.400 Wir hatten noch am Anfang der Vorlesung gesehen, es gibt diese 44:42.400 --> 44:46.660 Aussagenlogik, wo man mit aussagenlogischen Kollektiven dann 44:46.660 --> 44:48.540 aussagenlogische Variablen verbindet. 44:49.240 --> 44:53.020 Und je nachdem wie diese Variablen belegt sind, dann ergibt sich ein 44:53.020 --> 44:54.260 Wahrheitswert für eine Formel. 44:55.360 --> 44:59.800 Hier haben wir was ähnliches, nur der Aufbau ist etwas komplizierter. 45:01.460 --> 45:04.540 Also fangen wir mal genau mit dem Aufbau an. 45:06.220 --> 45:07.900 Wie sieht die Syntax aus? 45:09.120 --> 45:12.480 Ich habe zuerst gewisse Terme. 45:12.660 --> 45:16.140 Also ein Term soll zum Beispiel, Sie können sich vorstellen, ich habe 45:16.140 --> 45:18.100 einen Wert da. 45:18.260 --> 45:23.600 Also wenn ich über natürliche Zahlen rede, dann soll x für eine Zahl 45:23.600 --> 45:28.640 stehen und c ist eine Konstante, die ich habe in diesen Zahlen. 45:29.640 --> 45:35.860 Und da habe ich auch Funktionen, also nicht nur... Funktionen, wenn 45:35.860 --> 45:39.620 ich gewisse Werte dieser Funktionen gebe, dann kriege ich wieder einen 45:39.620 --> 45:39.960 Wert. 45:40.500 --> 45:44.080 Also wenn ich zwei Zahlen rede, dann kriege ich wieder eine Zahl. 45:44.760 --> 45:47.440 Also diese Terme stehen alle für Werte da. 45:48.020 --> 45:50.440 Und bei diesen Funktionen können wir Argumente haben. 45:50.540 --> 45:55.520 Die Argumente sind wieder Terme und Terme können wieder Funktionswerte 45:55.520 --> 45:55.840 sein. 45:56.000 --> 46:00.560 Also ich kann zum Beispiel h für nichts und beim zweiten Argument, das 46:00.560 --> 46:01.900 steht in g für die y wieder. 46:02.740 --> 46:07.660 Das ist keine einfache Variable, sondern ein Funktionswert an der 46:07.660 --> 46:07.920 Stelle. 46:07.920 --> 46:09.720 Das ist auch erlaubt. 46:10.580 --> 46:14.400 Und das haben wir alles durch kontextfreie Grammatiken spezifiziert. 46:17.820 --> 46:20.760 Ich hatte schon letzte Woche gesagt, dass die nützlich waren. 46:23.300 --> 46:26.500 Wie ergibt sich eine praktikalische logische Formel? 46:26.620 --> 46:32.260 Also zuerst habe ich eine ganz einfache Formel, die nenne ich atomare 46:32.260 --> 46:32.760 Formeln. 46:33.620 --> 46:38.680 Und diese Formeln sind natürlich selbst Formeln und ergeben sich aus 46:38.680 --> 46:41.280 Relationen, die sich über diese Terme ausdrücken. 46:42.820 --> 46:46.800 Also wieder ist das alles durch eine kontextfreie Grammatik geregelt. 46:47.180 --> 46:51.020 Aber ich habe dann zum Beispiel die gleiche Relation, die ist immer 46:51.020 --> 46:51.560 dabei. 46:52.460 --> 46:55.440 Also ich kann immer ein Term ist gleich ein anderes Term schreiben. 46:56.020 --> 46:59.640 Da meine ich, dass die Werte dann gleich sind, wenn ich die 46:59.640 --> 47:01.240 entsprechend interpretiere. 47:01.940 --> 47:06.940 Oder ich habe eine abstrakte Relation, die kann auch einstellig sein. 47:07.080 --> 47:09.940 Und eine einstellige Relation in dem Fall ist nur ein Prädikat. 47:10.200 --> 47:16.540 Also zum Beispiel r von x gibt mir etwas, was für x gilt oder nicht. 47:17.900 --> 47:21.320 Also zum Beispiel ist das ein Element einer Teilmenge in der Domäne 47:21.320 --> 47:21.720 oder so. 47:21.900 --> 47:23.020 Das werden wir noch sehen. 47:24.080 --> 47:27.060 Oder diese Relation kann mehrstellig sein. 47:27.160 --> 47:29.520 Dann habe ich eine ganz normale Relation, wie wir sie auch 47:29.520 --> 47:30.560 kennengelernt haben. 47:32.000 --> 47:35.780 Und die Argumente für diese Relation sind einfach wieder Terme. 47:37.500 --> 47:44.760 Und dann daraus ergibt sich diese atomare Formel, die ich dann, ja ich 47:44.760 --> 47:48.620 könnte die als logische Variablen betrachten und die logisch 47:48.620 --> 47:49.080 verbinden. 47:49.340 --> 47:53.140 Also ich kann eine atomare Formel negieren oder verurteilen mit einer 47:53.140 --> 47:54.580 atomaren Formel und so weiter. 47:55.360 --> 47:56.440 Auch Implikation ist dabei. 47:56.440 --> 47:58.480 Aber es gibt noch diese zwei Quantoren. 47:58.860 --> 48:04.360 Also das ist einfach so, weil wir mehr aus Druck möchten, als nur 48:04.360 --> 48:06.920 atomare Formeln logisch verbinden. 48:06.980 --> 48:13.460 Wir möchten auch Aussagen treffen, die über alle Elemente in der 48:13.460 --> 48:14.880 Domäne sprechen. 48:15.480 --> 48:19.440 Oder zum Beispiel beim Existenzquantor, es gibt halt Elemente in der 48:19.440 --> 48:20.620 Domäne, die etwas erfüllen. 48:21.740 --> 48:24.980 Deswegen haben wir auch diese Quantoren da. 48:29.380 --> 48:31.780 Ich habe hier schon alles gesprochen. 48:32.840 --> 48:34.080 Und unten haben Sie noch Beispiele. 48:34.240 --> 48:37.540 Also die atomaren Formeln sind wieder predikativ-logische Formeln, wie 48:37.540 --> 48:37.760 gesagt. 48:38.380 --> 48:42.780 Aber man kann die auch mit diesen Quantoren und so weiter beliebig 48:42.780 --> 48:46.200 kombinieren und das alles durch eine kontextfreie Grammatik regeln. 48:51.240 --> 48:55.980 Diese Formeln sind nur Wörter, bis man sie eine Bedeutung gibt. 48:56.220 --> 48:58.080 Das war auch bei der Aussagenlogik so. 48:58.800 --> 49:03.500 Wir hatten einfach Formeln, das sind Wörter über ein Alphabet und die 49:03.500 --> 49:06.920 haben eine gewisse Struktur, die durch diese Grammatik vorgegeben 49:06.920 --> 49:07.260 wird. 49:07.540 --> 49:11.840 Aber die haben nur eine Bedeutung, wenn man auch die semantische Seite 49:11.840 --> 49:12.380 betrachtet. 49:12.500 --> 49:13.500 Das ist die Interpretation. 49:14.120 --> 49:18.160 Bei der Aussagenlogik, da haben wir diese Verrahmung, die Verrahmung 49:18.160 --> 49:20.940 haben wir Wahrheitswerte zugewiesen. 49:21.620 --> 49:25.740 Hier ist es ein bisschen anders, hier habe ich ein Universum oder auch 49:25.740 --> 49:27.720 eine Domäne, deswegen heißt das D. 49:27.720 --> 49:32.060 Und das ist eine nicht leere Menge, die irgendwelche Werte hat. 49:32.220 --> 49:35.300 Also wie gesagt, das kann zum Beispiel die natürlichen Zahlen sein. 49:36.360 --> 49:38.600 Und ich habe noch diese Abbildung I. 49:39.200 --> 49:43.520 Das gibt mir die Bedeutung der Konstanten und der Funktionen und der 49:43.520 --> 49:45.960 ganzen Relationssymbole, die ich da in der Formel habe. 49:46.580 --> 49:47.860 Was soll F bedeuten? 49:47.940 --> 49:49.340 Was soll R bedeuten? 49:49.840 --> 49:51.820 Wenn ich eine Konstante zähle, was soll das bedeuten? 49:52.480 --> 49:53.480 Wofür sollte das stehen? 49:54.720 --> 49:58.520 Zum Beispiel, ich habe eine Formel da, Quanto X und so weiter und da 49:58.520 --> 49:59.560 habe ich ein F stehen. 49:59.960 --> 50:01.280 Wofür sollte dieses F stehen? 50:03.060 --> 50:05.360 Das sagt mir das Sif von F. 50:06.940 --> 50:09.780 Zum Beispiel, wenn ich in der Domäne natürliche Zahlen mit einer Null 50:09.780 --> 50:13.460 habe und ich könnte zum Beispiel für F die Addition nehmen, dann meine 50:13.460 --> 50:19.300 ich, dass ich Y und Z addiere und es soll, also der Wert, der 50:19.300 --> 50:22.220 rauskommt, soll X sein, bei der Formel da. 50:22.880 --> 50:26.160 Wobei X, Y und Z dann dementsprechend quantifiziert sind. 50:28.500 --> 50:32.040 Aber die Domäne könnte auch etwas anderes sein, also gar nicht Zahlen, 50:32.140 --> 50:35.440 es könnten auch gar Wörter sein und das Sif von F könnte die 50:35.440 --> 50:36.440 Konkatenation sein. 50:36.440 --> 50:39.960 Also dann habe ich Y und Z konkateniert und dann ist die Reihenfolge 50:39.960 --> 50:40.820 auch wichtig. 50:42.200 --> 50:43.600 Das ist nicht kommutativ mehr. 50:45.760 --> 50:51.660 Also wenn ich F von Y, Z schreibe, ist das anders als wenn ich F Z, Y 50:51.660 --> 50:54.500 schreibe, wobei bei der Addition das nicht so ist. 50:57.300 --> 51:01.680 Dann habe ich diese Bedeutungen, aber wir brauchen noch etwas. 51:02.120 --> 51:03.600 Das ist diese Variablenbelegung. 51:04.120 --> 51:09.000 Ich muss auch sagen, was die Konstante, die Funktionen, die Relationen 51:09.000 --> 51:15.740 sind und die Werte, worüber ich spreche in der Formel, aber es fehlen 51:15.740 --> 51:19.140 noch die Werte für die Variablen selber. 51:19.140 --> 51:24.620 Also ich muss sagen, welche Werte diese Variablen annehmen und das ist 51:24.620 --> 51:27.260 die konkrete an der Stelle diese Variablenbelegung. 51:27.380 --> 51:34.940 Das ist einfach eine Abbildung, die sagt, welche Werte in der Domäne 51:34.940 --> 51:36.940 dann zugewiesen werden sollen. 51:38.620 --> 51:44.780 Und dann, wenn ich all diese drei Sachen mir betrachte und wenn ich 51:44.780 --> 51:49.500 die fest habe, dann kann ich die verwenden, um meine Formel zu 51:49.500 --> 51:52.700 evaluieren und daraus kommt ein Wahrheitswert, wie in der 51:52.700 --> 51:54.600 Aussagenlogik auch war. 51:55.640 --> 51:56.880 Das ist ein symbolischer Wahrheitswert. 51:57.000 --> 51:58.440 Das kann entweder wahr oder falsch sein. 51:59.100 --> 52:02.740 Und hier in dem Fall, für die drei Beispiele in der Mitte, da kann ich 52:02.740 --> 52:05.440 mir überlegen, was passiert. 52:06.060 --> 52:09.780 Und in dem Fall, das gilt für alle Variablenbelegungen, die ich habe. 52:09.780 --> 52:12.460 Und die Variablen sehen so aus. 52:14.820 --> 52:21.320 Egal, welches X ich habe, ich kann Y und Z finden, sodass die sich zu 52:21.320 --> 52:22.180 X addieren. 52:22.320 --> 52:26.240 Ich kann zum Beispiel Y gleich X und Z gleich 0 wählen. 52:26.560 --> 52:27.860 Dann passt das. 52:27.860 --> 52:30.660 Dann ist das wahr, diese Interpretation. 52:31.080 --> 52:33.840 Aber wenn ich die 0 nicht habe, dann kann ich nicht die 0 nehmen. 52:34.120 --> 52:37.780 Also wenn ich zum Beispiel X gleich 1 habe, dann kann ich nicht zwei 52:37.780 --> 52:41.900 Zahlen in den Plus finden, sodass sie sich zu 1 addieren. 52:41.960 --> 52:42.820 Das geht einfach nicht. 52:43.560 --> 52:47.560 Die werden zumindest so groß wie 1 sein und dann 1 plus 1 ist 2, das 52:47.560 --> 52:48.120 ist zu groß. 52:48.220 --> 52:51.480 Da kann ich nicht X als eine Addition ausdrücken. 52:51.980 --> 52:52.440 Das geht nicht. 52:54.100 --> 52:56.820 Bei der Konkretation, das passiert genauso wie bei der Readdition. 52:56.920 --> 53:01.340 Man könnte zum Beispiel für Y das leere Wort nehmen und Z gleich X. 53:01.860 --> 53:05.260 Und dann habe ich das leere Wort mit Z konkretisiert und dann ergibt 53:05.260 --> 53:05.920 sich das X. 53:06.280 --> 53:08.200 Also egal, welches Wort X ich habe. 53:13.160 --> 53:22.260 Dann können wir nicht nur Aussagenverwendung verwenden, um über 53:22.260 --> 53:27.420 mathematische Strukturen Aussagen zu treffen, sondern wir können auch 53:27.420 --> 53:33.900 abstraktere Aussagen formulieren und präzisieren. 53:33.900 --> 53:38.300 Zum Beispiel habe ich hier drei Mengen von Studenten, Vorlesungen und 53:38.300 --> 53:38.880 Professoren. 53:39.840 --> 53:41.760 Das ist einfach allgemein gemeint. 53:43.260 --> 53:46.220 Zum Beispiel Studenten, Vorlesungen, Professoren, KIT. 53:46.480 --> 53:47.260 Das könnte so sein. 53:47.260 --> 53:50.040 Und ich habe zwei Relationen B und U. 53:50.300 --> 53:54.220 Also B ist eine Relation, die besagt, dass ein Student eine Vorlesung 53:54.220 --> 53:59.840 besucht und U ist einfach, dass ein Professor eine Vorlesung oder 53:59.840 --> 54:01.780 Studenten unterrichtet. 54:02.260 --> 54:04.600 Der Professor kann sowohl eine Vorlesung als auch Studenten 54:04.600 --> 54:05.020 unterrichten. 54:05.640 --> 54:09.620 Und wenn ich zum Beispiel eine Aussage habe, jeder Student besucht 54:09.620 --> 54:13.540 eine Vorlesung, das kann ich in Prädikatenlogik ausdrucken. 54:13.780 --> 54:15.020 Wie kann ich das machen? 54:15.520 --> 54:17.940 Ich muss zum Beispiel zuerst quantifizieren. 54:18.040 --> 54:21.700 Ich nehme zum Beispiel ein Alquantor für alle X und dann, wenn das ein 54:21.700 --> 54:23.620 Student ist, dann besucht er diese Vorlesung. 54:23.700 --> 54:24.360 Wie sieht das aus? 54:24.440 --> 54:25.120 Das sieht so aus. 54:26.080 --> 54:27.320 Ich habe quantifiziert. 54:27.580 --> 54:31.780 Also für alle X, wenn X ein Student ist, dann daraus folgt, dass es 54:31.780 --> 54:35.940 ein Y gibt und Y ist eine Vorlesung und X besucht diese Vorlesung. 54:36.780 --> 54:38.120 So kann man das ausdrucken. 54:42.360 --> 54:43.720 Noch ein paar Beispiele. 54:44.780 --> 54:47.520 Studenten sind keine Professoren, Professoren sind keine Studenten. 54:47.780 --> 54:55.260 Also wenn X ein Student ist, dann ist er kein Professor und wenn X ein 54:55.260 --> 54:56.840 Professor ist, dann ist er kein Student. 54:57.760 --> 55:01.860 Und dann sind zwei Applikationen und dann kann ich die Methoden 55:01.860 --> 55:02.260 verbinden. 55:02.760 --> 55:03.280 So geht das. 55:05.960 --> 55:09.020 Übrigens, das könnten wir nicht in Aussagenlogik ausdrucken. 55:10.640 --> 55:16.060 Wie soll ich dann ausdrucken, dass ein Element ein Student sein kann? 55:16.240 --> 55:22.220 Das ist einfach eine Aussage, was ich in Aussagenlogik habe und ich 55:22.220 --> 55:24.780 kann keine Fährte damit verbinden. 55:24.980 --> 55:28.460 Deswegen brauchen wir die Prädikatenlogik an der Stelle. 55:29.420 --> 55:31.240 Also Aussagenlogik taugt dafür nicht. 55:31.940 --> 55:32.520 Wir verbinden nur, 55:35.640 --> 55:38.500 keine Vorlesung. 55:39.920 --> 55:46.680 Also das steht nicht in der Aussage für jede Person, weder Studenten 55:46.680 --> 55:49.560 oder so, sondern es steht nur, Studenten sind keine Professoren. 55:51.000 --> 55:53.280 Also man könnte das noch quantifizieren. 55:54.080 --> 55:56.100 Warum steht kein Quantor da vorne? 55:56.720 --> 55:58.080 Man könnte das auch quantifizieren. 56:00.240 --> 56:05.340 Also mir persönlich würde das auch die gleiche Bedeutung sein, nur es 56:05.340 --> 56:09.460 würde nicht eins zu eins sprechen, was ich da als Aussage habe. 56:10.720 --> 56:14.740 Aber es würde ja auch eine gültige Variante sein. 56:17.800 --> 56:24.980 Solche Aussagen sind gar nicht präzisiert. 56:25.420 --> 56:29.360 Wenn ich sage, das ist eine ganz herkömmliche Sprache, Studenten sind 56:29.360 --> 56:33.100 keine Professoren, deswegen möchte ich das zuerst formalisieren. 56:33.100 --> 56:55.310 Dann habe ich noch eine dritte Aussage. 56:56.010 --> 56:59.410 Wenn ein Professor eine Vorlesung unterrichtet, dann unterrichtet er 56:59.410 --> 57:02.530 auch alle Studenten, die sie besuchen. 57:04.070 --> 57:08.330 Wenn nichts ein Professor ist und es gibt eine Vorlesung und so 57:08.330 --> 57:11.490 weiter, also ich zeige zuerst die Formel, weil sonst wird das 57:11.490 --> 57:12.250 kompliziert. 57:12.250 --> 57:17.490 Also ich habe einen Professor X und ich habe eine Vorlesung Y und X 57:17.490 --> 57:23.510 unterrichtet diese Vorlesung Y und daraus folgt, dass für alle Z, also 57:23.510 --> 57:28.570 für alle Studenten Z, die diese Vorlesung Y besuchen, dann 57:28.570 --> 57:33.030 unterrichtet dieser Professor X diese Studenten Z. 57:33.790 --> 57:34.990 So kann ich das ausdrücken. 57:35.990 --> 57:38.390 Wie gesagt, es gäbe auch andere Möglichkeiten. 57:39.610 --> 57:44.310 Ich könnte das auch lebig umformulieren, sodass das ein Äquivalent 57:44.310 --> 57:45.630 sein könnte. 57:45.770 --> 57:48.890 Wir werden noch sehen, dass das möglich ist. 57:54.420 --> 57:58.880 Dann können wir diese Aussagen in der herkömmlichen Sprache 57:58.880 --> 57:59.900 modellieren. 58:00.060 --> 58:05.920 Wir können auch Mathematische Eigenschaften, wie wir sie vorher 58:05.920 --> 58:09.800 kennengelernt haben, modellieren, zum Beispiel Totalität und 58:09.800 --> 58:10.380 Eindeutigkeit. 58:11.780 --> 58:17.100 Also da habe ich eine BGM und eine Relation darauf, auf einem Kreuz M. 58:18.520 --> 58:22.420 Dann haben wir diese Eigenschaften gesehen, Links-Total, Rechts-Total, 58:22.540 --> 58:24.560 Links -Eindeutig, Rechts-Eindeutig und die kann ich auch in 58:24.560 --> 58:26.840 Prädikatenlogik ausdrucken. 58:26.840 --> 58:39.880 Ganz einfach, zum Beispiel Links-Total, da musste ich für alle 58:39.880 --> 58:47.180 Elemente links bei der Relation ein Y finden, sodass diese Y in der 58:47.180 --> 58:48.180 Relation mit X steht. 58:48.440 --> 58:49.840 Das ist dann so ausgedruckt. 58:49.840 --> 58:54.240 Also egal, welches Element X ich nehme, ich finde ein Y, sodass diese 58:54.240 --> 58:56.920 Y in der Relation mit X steht. 58:57.720 --> 59:01.380 Und bei Rechts-Total, da muss ich die Quantoren, also die Werte bei 59:01.380 --> 59:04.860 den Quantoren umdrehen, dann rede ich über alle Y, die rechts stehen. 59:05.640 --> 59:08.520 Da finde ich ein X, sodass das in der Relation mit Y steht. 59:10.060 --> 59:12.740 Und bei Links-Eindeutigkeit oder Rechts-Eindeutigkeit, da muss ich 59:12.740 --> 59:14.860 diese Gleichheit verwenden. 59:16.000 --> 59:19.320 Das ist auch üblich in der Mathematik, wenn etwas eindeutig sein kann, 59:19.580 --> 59:23.760 dann zeigen wir, wenn zwei Objekte diese Eigenschaft haben, dann sind 59:23.760 --> 59:24.260 sie gleich. 59:25.580 --> 59:29.220 So ist das im Allgemeinen so gemacht. 59:30.380 --> 59:31.560 Und hier ist es gleich so. 59:31.700 --> 59:35.600 Also wenn X in der Relation mit Y steht und C in der Relation mit Y, 59:35.760 --> 59:36.940 dann sind die X und C gleich. 59:37.260 --> 59:40.420 Also es war das selbe Element. 59:40.540 --> 59:42.140 Es könnten nicht verschiedene Elemente sein. 59:46.260 --> 59:51.200 Es gibt auch andere Schreibweisen, die üblicher sind, als nur in 59:51.200 --> 59:55.620 solchen Formen zu schreiben und sagen, die Interpretation ist so und 59:55.620 --> 59:56.300 so und so weiter. 59:56.740 --> 59:58.500 Sondern man schreibt einfach hin, was man meint. 59:58.660 --> 01:00:03.760 Also ich habe für alle X in der Menge M, dann gibt es ein Y in der 01:00:03.760 --> 01:00:06.040 Menge M, sodass X in der Relation mit Y steht. 01:00:06.440 --> 01:00:08.000 So ist das auch einfacher zu lesen. 01:00:12.160 --> 01:00:14.500 Und das haben Sie bestimmt auch gesehen, glaube ich. 01:00:17.380 --> 01:00:21.660 Wenn ich zwei, also vorher hatte ich noch angedeutet, es gibt diese 01:00:21.660 --> 01:00:26.940 Qualenzen, wenn ich zwei Formeln habe, dann sind sie nicht unbedingt 01:00:26.940 --> 01:00:27.500 gleich. 01:00:27.960 --> 01:00:31.120 Aber egal, welche Interpretation über alle Belegungen ich nehme, die 01:00:31.120 --> 01:00:34.440 können vielleicht gleiche Wahrheitswerte haben. 01:00:35.760 --> 01:00:39.320 Egal, wie die Interpretation, die Wahrheitsbelegung aussieht, dann 01:00:39.320 --> 01:00:41.080 sind die Wertungen auch gleich. 01:00:41.760 --> 01:00:43.380 Das hatten wir auch bei der Aussagenlogik. 01:00:43.520 --> 01:00:47.060 Egal, welche Interpretation ich habe, diese Formeln haben gleiche 01:00:47.060 --> 01:00:47.720 Wahrheitswerte. 01:00:48.720 --> 01:00:54.620 Und hier bei den Beispielen, da sehen Sie, auch was in der 01:00:54.620 --> 01:00:56.300 Aussagenlogik gelten würde. 01:00:56.620 --> 01:01:00.820 Eher vornichts, wenn ich das in der Aussage betrachte und das mit sich 01:01:00.820 --> 01:01:05.980 selber verundele, dann bleibt das Logische, bleibt das Äquivalent. 01:01:06.140 --> 01:01:07.840 Das war auch in der Aussagenlogik so. 01:01:08.500 --> 01:01:13.020 Aber hier mit diesen Quantoren, alles das, da haben wir auch 01:01:13.020 --> 01:01:16.680 verschiedene Möglichkeiten für Äquivalenzen. 01:01:16.800 --> 01:01:25.040 Zum Beispiel, wenn ich für alle x ständiger als für alle y habe, dann 01:01:25.040 --> 01:01:26.720 kann ich diese Quantoren auch vertauschen. 01:01:26.720 --> 01:01:31.820 Und ich kann hier, weil die zwei waren allquativisiert sind, sogar die 01:01:31.820 --> 01:01:34.740 Variablen in der Relationäre vertauschen. 01:01:36.200 --> 01:01:41.980 Das geht einfach, weil ich dann verschiedene Werte für x und y nehme. 01:01:42.880 --> 01:01:45.800 Das ist nicht so intuitiv, aber das geht. 01:01:46.680 --> 01:01:51.800 Und dann in Aufgabe 8.3 zeigen Sie, dass die zwei unteren Formeln, 01:01:52.080 --> 01:01:55.440 naja, die eine Richtung Äquivalenz sind. 01:01:57.460 --> 01:02:02.640 Und es gibt zwei Formeln ganz mit Äquivalenzen, das können Sie auch 01:02:02.640 --> 01:02:04.220 als Beispiel sehen. 01:02:06.600 --> 01:02:14.820 So, hier zeige ich, wenn man diese Quantoren umtauscht, bei einem 01:02:14.820 --> 01:02:20.100 Allquantor, dass die nichts an dem Wahrheitswert ausmachen, egal 01:02:20.100 --> 01:02:21.820 welche Interpretationen und Variablen belegen. 01:02:22.360 --> 01:02:27.100 Ich habe, wenn ich die Quantoren tausche, dann bleibt der 01:02:27.100 --> 01:02:27.940 Wahrheitswert gleich. 01:02:28.880 --> 01:02:30.560 Und warum gilt das? 01:02:31.180 --> 01:02:38.060 Ich muss diese Interpretationen mehr genau angucken, so wie in der 01:02:38.060 --> 01:02:39.140 Vorlesung definiert wurde. 01:02:39.580 --> 01:02:43.020 Also, ich nehme diese Formel da, und dann gibt es unter dieser 01:02:43.020 --> 01:02:46.420 Interpretationen di-beta, der hat einen Wahrheitswert. 01:02:46.420 --> 01:02:52.980 Und der Wahrheitswert ist wahr, wenn ich das Formel für alle y und f 01:02:52.980 --> 01:02:59.960 nehme und die wahr ist, egal wie ich x durch ein Element d in der 01:02:59.960 --> 01:03:00.860 Domäne ersetze. 01:03:01.700 --> 01:03:09.220 Das bedeutet diese beta dx, das sehen Sie unten, egal welche Variable 01:03:09.220 --> 01:03:09.720 ich habe. 01:03:09.720 --> 01:03:15.120 Also, wenn diese Variable die dx ist, dann nehme ich dieses Element d 01:03:15.120 --> 01:03:17.320 in der Domäne dafür als Wert. 01:03:18.140 --> 01:03:21.340 Und wenn das eine andere Variable ist, dann nehme ich, was mir beta 01:03:21.340 --> 01:03:21.740 sagt. 01:03:23.600 --> 01:03:28.820 Und wenn das so ist, dann ist das wahr, ansonsten ist der Wert dieser 01:03:28.820 --> 01:03:29.560 Formel falsch. 01:03:30.500 --> 01:03:36.940 Wenn es ein d gibt, so dass der Wahrheitswert dann für alle y und f 01:03:36.940 --> 01:03:37.840 nicht wahr ist. 01:03:38.680 --> 01:03:39.960 So ist das definiert. 01:03:42.840 --> 01:03:48.040 Dann müssen wir die Formel für alle y und f wieder nehmen und die 01:03:48.040 --> 01:03:50.920 weiter analysieren. 01:03:52.960 --> 01:03:55.320 Und hier mache ich eine Veränderung der Stelle. 01:03:55.480 --> 01:03:59.900 Also, entweder kann diese Formel für alle x, y und f wahr oder falsch 01:03:59.900 --> 01:04:00.140 sein. 01:04:00.140 --> 01:04:06.060 Und wenn das wahr ist, dann habe ich für alle Belegungen beta Strich, 01:04:06.140 --> 01:04:09.020 wobei ich x durch d ersetze und d ist beliebig. 01:04:09.620 --> 01:04:12.160 Dann ist die Formel für alle y und f wahr. 01:04:14.140 --> 01:04:18.740 Und dann muss ich das gleiche Spiel für alle y und f machen. 01:04:18.740 --> 01:04:23.020 Dann nehme ich noch eine andere Belegung, beta Strich, Strich. 01:04:23.640 --> 01:04:28.020 Und jetzt habe ich zwei beliebige Elemente d und e. 01:04:28.860 --> 01:04:32.900 Und für x setze ich d rein und für y setze ich e. 01:04:33.860 --> 01:04:38.480 Aber wir sind dann so geschaltet. 01:04:38.660 --> 01:04:40.720 Zuerst nehme ich das beta Strich. 01:04:42.280 --> 01:04:44.460 Ich spiele mal beta Doppelstrich, Entschuldigung. 01:04:45.100 --> 01:04:49.160 Da schaue ich mir zuerst, was für y gelten soll und wenn nicht, dann 01:04:49.160 --> 01:04:50.560 mache ich mit beta Strich weiter. 01:04:50.560 --> 01:04:56.120 Aber das passiert das gleiche, also weil x und y nicht gleich sind, 01:04:56.680 --> 01:05:01.700 wie ich diese betas definiert habe, dann ist das gleich so, wenn ich 01:05:01.700 --> 01:05:03.060 die andere Reihenfolge nehme. 01:05:03.060 --> 01:05:10.240 Wenn ich mir zuerst die Variablen anschaue, ist das gleich x, dann 01:05:10.240 --> 01:05:13.660 nehme ich den Wert d und dann fahre ich mit dem beta Strich weiter, 01:05:14.360 --> 01:05:21.020 wobei mir das beta Strich sagt, ist das diese Variable y, dann nehme 01:05:21.020 --> 01:05:24.240 ich den Wert e und wenn nicht, dann nehme ich, was mir beta sagt. 01:05:26.640 --> 01:05:31.500 Also man kann das umtauschen und wenn man das umtauschen kann, kann 01:05:31.500 --> 01:05:36.180 ich das jetzt wieder meine Schritte zurück machen und dann habe ich 01:05:36.180 --> 01:05:38.940 die Kontrollen in andere Reihenfolge. 01:05:39.340 --> 01:05:43.560 Also habe ich einfach die Definition zurück verwendet, dann habe ich 01:05:43.560 --> 01:05:47.660 zuerst über x quantifiziert und dann über y und das geht, weil ich 01:05:47.660 --> 01:05:50.480 diese Werte in der Belegung tauschen kann. 01:05:53.420 --> 01:06:00.500 Und für den anderen Fall, wo das falsch war, da muss man nicht 01:06:00.500 --> 01:06:06.960 beliebige Werte d und e nehmen, sondern man muss sich Gedanken machen, 01:06:07.180 --> 01:06:14.720 das ist falsch für ein gewisses d und dann ist die Formel f falsch für 01:06:14.720 --> 01:06:15.760 gewisse d und e. 01:06:17.660 --> 01:06:18.260 Entschuldigung. 01:06:19.520 --> 01:06:24.420 Und dann, ja, das geht dann genauso, ich kann die Belegungen in einer 01:06:24.420 --> 01:06:30.440 Reihenfolge schreiben und dann kann ich immer noch die Kontrollen 01:06:30.440 --> 01:06:30.740 tauschen. 01:06:31.940 --> 01:06:33.060 Deswegen gilt das. 01:06:34.940 --> 01:06:40.360 So, wir hatten, das war das thematologische Äquivalenz, dann habe ich 01:06:40.360 --> 01:06:45.620 auch ein paar Eigenschaften von Formeln, die auch ganz interessant 01:06:45.620 --> 01:06:46.980 sind. 01:06:49.260 --> 01:06:56.340 Zum Beispiel kann eine Formel allgemeingültig sein, das ist, egal 01:06:56.340 --> 01:06:59.440 welche Interpretationen und Variablenbelegungen ich habe, dann ist die 01:06:59.440 --> 01:07:00.040 Formel fach. 01:07:00.260 --> 01:07:04.220 Die gilt in jeder Interpretation, in jeder Variablenbelegung und zum 01:07:04.220 --> 01:07:06.900 Beispiel eine Variabel ist gleich sich selber. 01:07:07.240 --> 01:07:10.500 Also ein Wert ist gleich sich selber, das muss einfach so sein. 01:07:13.360 --> 01:07:17.640 Dagegen, es gibt auch erfüllbar, das heißt einfach nicht, dass jede 01:07:17.640 --> 01:07:23.240 Interpretation, jede Variablenbelegung, sondern es gibt gewisse, es 01:07:23.240 --> 01:07:26.540 gibt eine Interpretation und eine Variablenbelegung, die diese Formel 01:07:26.540 --> 01:07:27.260 zu wahr macht. 01:07:27.260 --> 01:07:32.700 Also zum Beispiel, was ist das, rechtstotal. 01:07:35.780 --> 01:07:39.480 Es gibt rechtstotale Relationen, das muss erfüllbar sein, aber nicht 01:07:39.480 --> 01:07:41.580 alle Relationen sind rechtstotal. 01:07:41.660 --> 01:07:44.200 Deswegen ist das auch nicht allgemeingültig. 01:07:45.820 --> 01:07:49.980 Und es könnte auch erfüllbar sein, ich könnte etwas haben, was egal 01:07:49.980 --> 01:07:52.620 welche Interpretationen und Variablenbelegungen ich habe, das ist 01:07:52.620 --> 01:07:53.340 nicht wahr. 01:07:53.340 --> 01:07:58.640 Und zum Beispiel, wenn eine Relation ein Äquivalent zu einer Relation 01:07:58.640 --> 01:07:58.920 ist. 01:07:59.200 --> 01:08:04.280 Also wenn die Relation gilt, dann muss sie nicht gelten. 01:08:04.460 --> 01:08:09.480 Also sie kann nicht an erster Stelle gelten haben und wenn sie nicht 01:08:09.480 --> 01:08:13.680 gilt, dann folgt es aus, dass sie auch gilt und deswegen kann sie auch 01:08:13.680 --> 01:08:16.400 nicht nicht gelten und dann, ja, das geht einfach nicht. 01:08:16.480 --> 01:08:17.560 Das ist alles widersprüchlich. 01:08:18.360 --> 01:08:21.740 Egal welche Interpretationen und Variablenbelegungen ich habe, das 01:08:21.740 --> 01:08:24.680 kann gar nicht wahr sein. 01:08:29.610 --> 01:08:33.990 Dann ein Beispiel für diese allgemeingültige Erfüllbarkeit. 01:08:34.870 --> 01:08:36.570 Also zum Beispiel habe ich diese Formel da. 01:08:37.510 --> 01:08:45.390 Wenn es ein x gibt, sodass R für x gilt, dann folgt daraus, dass für 01:08:45.390 --> 01:08:47.870 alle y das R gilt. 01:08:48.690 --> 01:08:51.710 Könnte das erfüllbar sein? 01:08:52.430 --> 01:08:52.790 Ja. 01:08:53.890 --> 01:08:55.230 Allgemeingültig könnte es nicht sein. 01:08:55.450 --> 01:08:59.090 Also wenn etwas für ein Element gilt, dann soll es für alle Elemente 01:08:59.090 --> 01:08:59.430 gelten. 01:08:59.990 --> 01:09:02.370 Das kann nicht im Allgemeinen geben. 01:09:03.630 --> 01:09:08.210 Also zuerst erfüllbar, man könnte zum Beispiel eine beliebige Domäne 01:09:08.210 --> 01:09:12.030 sogar nehmen und für die Relation R einfach die ganze Domäne. 01:09:12.230 --> 01:09:15.110 Also R besagt, dieses Element ist in der Domäne. 01:09:15.110 --> 01:09:20.590 Und dann gibt es zumindest ein Element in dieser Domäne. 01:09:20.730 --> 01:09:24.210 Also ist die erste Aussage, es gibt x, R von x ist wahr. 01:09:24.570 --> 01:09:28.010 Das ist wahr. 01:09:28.370 --> 01:09:33.230 Aber auch von der anderen Seite betrachtet, wenn ich mir R von y 01:09:33.230 --> 01:09:35.410 anschaue, das gilt für jedes Element. 01:09:35.590 --> 01:09:40.530 Also jedes Element d ist in dieser Domäne. 01:09:40.530 --> 01:09:44.810 Deswegen ist R von y wahr, egal wie ich die Werte für y nehme. 01:09:45.530 --> 01:09:47.370 Und dann ist die Quantifizierung davon wahr. 01:09:48.650 --> 01:09:55.330 Und wenn die Implikation der rechten Teil wahr ist, dann ist die 01:09:55.330 --> 01:09:56.310 Implikation immer wahr. 01:09:56.950 --> 01:09:58.110 So haben wir das auch gelernt. 01:09:58.410 --> 01:10:03.330 Egal, wenn da vorne etwas falsch ist, dann ist die Implikation sowieso 01:10:03.330 --> 01:10:07.170 wahr, weil die Phrase falsch ist. 01:10:07.170 --> 01:10:12.330 Und wenn etwas wahr steht, dann ist die Implikation wieder wahr. 01:10:12.930 --> 01:10:15.730 So haben wir das auch in der Ausgangslogik gesehen. 01:10:17.010 --> 01:10:20.510 Und eine andere Möglichkeit, hier bei der Stelle Füllbarkeit zu haben, 01:10:20.710 --> 01:10:25.170 würde ich für die Reaktion R einfach das leere Prädikat nehmen. 01:10:26.310 --> 01:10:31.030 Dann wäre die Voraussetzung immer falsch. 01:10:31.130 --> 01:10:32.670 Es gibt kein x oder R von x. 01:10:32.670 --> 01:10:38.650 Wenn die Voraussetzung falsch ist, dann ist die Implikation selber 01:10:38.650 --> 01:10:38.890 wahr. 01:10:40.230 --> 01:10:44.110 Ich finde, R von y ist ein bisschen schöner hier zu argumentieren. 01:10:46.750 --> 01:10:49.670 Wenn man die Nichtallgemeingültigkeit... 01:10:50.550 --> 01:10:53.290 Ja, ich könnte zum Beispiel... 01:10:53.290 --> 01:10:55.810 R von y ist einfach eine echte Teilmenge der Domäne. 01:10:55.990 --> 01:11:01.650 Dann gibt es ein x, das in der Domäne ist, zum Beispiel 1 hier bei den 01:11:01.650 --> 01:11:02.370 natürlichen Zahlen. 01:11:02.370 --> 01:11:05.410 Aber die Null ist nicht in der... 01:11:05.410 --> 01:11:06.610 Er füllt nicht die R. 01:11:09.310 --> 01:11:12.530 Ich von R sage einfach positive Zahlen. 01:11:13.510 --> 01:11:16.670 Und dann ist die Implikation falsch. 01:11:21.480 --> 01:11:24.720 Wenn man die Klammerung anders nimmt... 01:11:24.720 --> 01:11:29.540 Zuerst habe ich noch das R durch ct ersetzt. 01:11:29.880 --> 01:11:32.960 Aber das ist im Grunde genommen eine andere Klammerung. 01:11:34.060 --> 01:11:39.440 Es gibt die x, R von x, daraus folgt für alle y R von y. 01:11:39.920 --> 01:11:41.060 Hier habe ich eine andere Klammerung. 01:11:41.800 --> 01:11:45.200 Es gibt die ganz vorne und dann habe ich eine Implikation in der 01:11:45.200 --> 01:11:45.600 Klammer. 01:11:45.760 --> 01:11:46.640 Das ist anders. 01:11:47.860 --> 01:11:51.900 Und das macht einen großen Unterschied, weil diese Formel immer 01:11:51.900 --> 01:11:52.960 gemeingültig ist. 01:11:54.700 --> 01:11:57.700 Sie müssen sich schon Gedanken machen, wo sie die Klammer setzen. 01:11:57.840 --> 01:12:00.660 Das macht, insbesondere bei den Quantoren, das macht viel aus. 01:12:03.000 --> 01:12:08.420 Und hier ist das ein Paradoxon, weil es die Formel besagt, wenn es 01:12:08.420 --> 01:12:16.960 eine x gibt, es gibt eine Person x, wenn die trinkt, dann trinken alle 01:12:16.960 --> 01:12:17.700 Leute der Puppe. 01:12:18.560 --> 01:12:23.780 Und das gilt hier immer, egal welche Interpretation ich habe. 01:12:23.880 --> 01:12:27.040 Und das gilt einfach, weil diese Implikation nicht ist, was sie 01:12:27.040 --> 01:12:28.440 denken. 01:12:28.440 --> 01:12:31.760 Sie denken eher an das da. 01:12:31.940 --> 01:12:35.240 Also es gibt eine Person, wenn die trinkt, und die trinkt, und dann 01:12:35.240 --> 01:12:36.700 folgt daraus, dass alle Personen trinken. 01:12:37.240 --> 01:12:38.080 Aber hier ist das anders. 01:12:38.240 --> 01:12:42.360 Es gibt eine Person, und wenn diese Person, die Aussage ist, wenn 01:12:42.360 --> 01:12:44.940 diese Person trinkt, dann trinken alle Personen. 01:12:46.520 --> 01:12:47.400 Das ist was anderes. 01:12:48.540 --> 01:12:50.200 Das ist die Implikation da. 01:12:50.700 --> 01:12:55.920 Das ist nicht intuitiv, würde ich sagen. 01:12:57.520 --> 01:12:59.640 Dann ein Beweis dafür, warum es gilt. 01:12:59.780 --> 01:13:01.500 Also ich habe wieder zwei Fälle. 01:13:01.820 --> 01:13:05.560 Ich nehme zuerst diese Implikation, ich schreibe dafür einfach f'. 01:13:07.260 --> 01:13:12.920 Und der eine Fall ist, es gibt eine Person, die nicht trinkt. 01:13:13.760 --> 01:13:16.380 Also t von x ist falsch für dieses d. 01:13:17.740 --> 01:13:21.000 Dann habe ich bei der Implikation die Voraussetzung falsch, und dann 01:13:21.000 --> 01:13:22.760 muss die Formel wieder falsch sein. 01:13:23.620 --> 01:13:24.600 So ist das. 01:13:28.280 --> 01:13:29.040 Und andersrum. 01:13:30.580 --> 01:13:36.040 Also wenn ich keine Person habe, die nicht trinkt, dann müssen alle 01:13:36.040 --> 01:13:36.780 Personen trinken. 01:13:37.760 --> 01:13:43.140 Dann muss für jedes d, t von x, wenn ich in der Stelle xd einsetze, 01:13:43.280 --> 01:13:44.120 dann muss f' sein. 01:13:47.760 --> 01:13:54.300 Dann habe ich für alle x, t von x, x war in diesem Modell. 01:13:55.160 --> 01:13:59.900 Und jetzt muss ich noch x durch y benennen, damit ich zu meiner Formel 01:13:59.900 --> 01:14:00.660 f' komme. 01:14:00.820 --> 01:14:06.100 Und das geht, weil dieses x in dieser Formel für alle x und t von y 01:14:06.100 --> 01:14:06.800 frei ist. 01:14:07.080 --> 01:14:08.740 Das kommt nicht in dieser Formel vor. 01:14:10.280 --> 01:14:13.000 Das ist mehr als frei, das kommt gar nicht vor in der Formel. 01:14:13.000 --> 01:14:18.600 Und dann kann ich diese belegen und dann, also egal, diese belegen, 01:14:21.580 --> 01:14:24.880 dann ist damit der Freiheitswert auch gleich. 01:14:25.120 --> 01:14:29.680 Also wenn ich für alle y, t von y habe, dann ist für alle x, t von x 01:14:29.680 --> 01:14:31.700 auch dasselbe da. 01:14:32.940 --> 01:14:38.600 Dann bei der Implikation habe ich was, also t von x ist überhaupt, das 01:14:38.600 --> 01:14:41.420 ist frei, egal welches Wert für x ich nehme. 01:14:41.420 --> 01:14:47.060 Und die rechte Seite ist auch wahr, weil für alle... 01:14:47.060 --> 01:14:49.280 Das war einfach meine Voraussetzung für den Fall. 01:14:49.680 --> 01:14:52.460 Das sollte für alle... 01:14:52.460 --> 01:14:55.300 Das habe ich gerade gezeigt, der Freiheitswert dafür ist wahr. 01:14:55.740 --> 01:14:59.340 Implikation aus wahr vor wahr und Implikation ist wahr. 01:14:59.900 --> 01:15:00.420 So ist das. 01:15:05.050 --> 01:15:09.310 Dann haben wir gerade bewiesen, dass das allgemeingültig ist. 01:15:11.230 --> 01:15:14.110 An manchen Stellen möchte ich vielleicht doch sagen, dass etwas 01:15:14.110 --> 01:15:15.130 unerfüllbar ist. 01:15:16.050 --> 01:15:19.530 Und hier habe ich automatisch, wenn diese Formel allgemeingültig ist, 01:15:19.610 --> 01:15:21.330 dann ist die Negation davon unerfüllbar. 01:15:22.350 --> 01:15:23.310 Warum ist das so? 01:15:24.050 --> 01:15:28.690 Also Allgemeingültigkeit besagen, egal welche Interpretation und 01:15:28.690 --> 01:15:33.370 Voraussetzung ich nehme, dann ist der Freiheitswert dieser Formel, 01:15:33.370 --> 01:15:34.450 dieser Interpretation, wahr. 01:15:35.630 --> 01:15:39.410 Wenn ich mir die Negation davon betrachte, ist es einfach, dieser Wert 01:15:39.410 --> 01:15:39.830 negiert. 01:15:39.990 --> 01:15:41.850 Dann kommt er einfach falsch voraus. 01:15:43.870 --> 01:15:46.850 Egal welche Interpretation und Voraussetzung ich nehme, dann ist diese 01:15:46.850 --> 01:15:51.610 Formel nicht falsch und so war die Unerfüllbarkeit definiert. 01:15:51.910 --> 01:15:55.750 Ich finde keine Interpretation und Voraussetzung, die diese Formel 01:15:55.750 --> 01:15:56.770 wahr macht. 01:15:58.620 --> 01:16:03.720 Und dann kann man mit diesem Wissen zwei Dinge ausdrücken. 01:16:04.620 --> 01:16:08.900 Also, wenn ich Allgemeingültigkeit beweisen will, dann kann ich auch 01:16:08.900 --> 01:16:13.940 genauso gut die Unerfüllbarkeit der negierten Formel zeigen. 01:16:14.980 --> 01:16:17.400 Das ist eine Äquivalenz, die geht in beide Richtungen. 01:16:17.500 --> 01:16:21.760 Auch wenn ich eine negierte Formel habe und ich zeige, wie diese 01:16:21.760 --> 01:16:25.400 unerfüllbar war, dann zeige ich einfach, das F da drin ist 01:16:25.400 --> 01:16:25.720 allgemeingültig. 01:16:27.940 --> 01:16:33.680 Beide Möglichkeiten sind gerechtfertigt. 01:16:36.420 --> 01:16:40.700 Und wenn ich zeigen will, wie diese Formel erfüllbar ist, dann kann 01:16:40.700 --> 01:16:44.540 ich auch zeigen, dass die Negation dafür nicht allgemeingültig ist. 01:16:45.460 --> 01:16:47.120 Da muss man sich ein bisschen Gedanken machen. 01:16:48.220 --> 01:16:53.040 Erfüllbar heißt, es gibt eine Belegung, die das wahr macht und wenn 01:16:53.040 --> 01:16:56.480 ich die Negation habe, dann ist diese Belegung da falsch. 01:16:56.880 --> 01:17:02.780 Dann gibt es eine Belegung, die diese Formel falsch macht, dann kann 01:17:02.780 --> 01:17:04.100 das nicht allgemeingültig sein. 01:17:04.540 --> 01:17:06.800 Für diese Belegung ist die Formel falsch. 01:17:06.920 --> 01:17:12.400 Die kann nicht für alle Interpretationen der Belegung wahr sein, weil 01:17:12.400 --> 01:17:14.460 sie für diese scheitert. 01:17:16.840 --> 01:17:19.020 Deswegen hat man die Äquivalenz auch. 01:17:24.880 --> 01:17:28.440 Dann mal was zu einem anderen Thema. 01:17:29.720 --> 01:17:30.750 Ich habe ja auch Substitutionen. 01:17:32.100 --> 01:17:33.400 Das haben wir auch kennengelernt. 01:17:34.860 --> 01:17:40.940 Die operieren auf diese Formel und die ersetzen dann Varaben durch 01:17:40.940 --> 01:17:42.780 andere Terme. 01:17:43.260 --> 01:17:46.820 Zum Beispiel, ich nehme eine Varabel X und dafür schreibe ich ein Y 01:17:46.820 --> 01:17:51.280 oder ich nehme eine Varabel X und dafür schreibe ich ein F von XY oder 01:17:51.280 --> 01:17:51.640 sowas. 01:17:52.560 --> 01:17:53.580 Einfach Term ersetzen. 01:17:56.380 --> 01:17:59.400 Dann haben wir die Schreibweise kennengelernt. 01:18:00.820 --> 01:18:07.780 Sieht man unten eine Menge mit V'T, wenn ich die Varabel V durch den 01:18:07.780 --> 01:18:09.060 Term T ersetzen will. 01:18:09.480 --> 01:18:14.420 Ich kann auch das mehrfach kombinieren, wie Sie hier in dem dritten 01:18:14.420 --> 01:18:15.120 Punkt sehen. 01:18:17.180 --> 01:18:23.760 Zum Beispiel, ich habe Sigma von X-Y und dann habe ich X durch Y 01:18:23.760 --> 01:18:25.060 ersetzt und wenn ich den Term 01:18:28.100 --> 01:18:34.080 F von XY habe, dann raus ergibt sich F von XY. 01:18:34.420 --> 01:18:35.760 Ich habe X durch Y ersetzt. 01:18:36.860 --> 01:18:42.620 Aber man muss schon aufpassen, das ist nicht einfach, dass ich ... 01:18:46.160 --> 01:18:50.740 Was passiert dann, wenn ich X durch Y ersetze und Y durch X? 01:18:51.520 --> 01:18:55.660 Dann werde ich nur einmal ersetzen. 01:18:55.920 --> 01:19:01.280 Ich darf nicht dann X zu Y machen und dann Y zu X oder so, sondern ich 01:19:01.280 --> 01:19:04.260 muss gleichzeitig nur einmal substituieren. 01:19:05.040 --> 01:19:09.140 Wenn ich F von XY habe und diese Substitutionen anwende, dann muss ich 01:19:09.140 --> 01:19:12.380 X durch Y ersetzen und Y durch X, aber nur einmal. 01:19:14.640 --> 01:19:15.780 Das alles gleichzeitig. 01:19:17.560 --> 01:19:18.500 So ist das gemeint. 01:19:21.140 --> 01:19:26.580 Eine andere Bemerkung, wenn die Varabenbälle gebunden sind, wenn ich 01:19:26.580 --> 01:19:32.400 die quantifiziert habe, zum Beispiel, es gibt X, sodass F von XY 01:19:35.020 --> 01:19:42.200 irgendetwas danach, dann darf ich dieses X nicht durch etwas 01:19:42.200 --> 01:19:43.840 substituieren. 01:19:44.780 --> 01:19:46.700 Ich muss X durch Y substituieren. 01:19:46.780 --> 01:19:50.720 Ich darf nur X durch Y substituieren, wenn X frei in dieser Formel 01:19:50.720 --> 01:19:50.960 ist. 01:19:53.500 --> 01:19:55.300 Entsprechend ist es nicht quantifiziert. 01:19:58.760 --> 01:20:05.680 Und diese Substitutionen können bestimmte Effekte haben, je nachdem, 01:20:05.840 --> 01:20:06.500 wie die aussehen. 01:20:07.180 --> 01:20:11.860 Zum Beispiel habe ich hier eine Formel, es gibt Y, sodass die Relation 01:20:11.860 --> 01:20:17.400 XY gilt und ich habe meine S1, das ersetzt X durch Y. 01:20:18.520 --> 01:20:23.020 Und dann daraus macht sie dann, es gibt Y, sodass Y in der Relation 01:20:23.020 --> 01:20:25.440 mit Y steht und das hat nicht dieselbe Bedeutung. 01:20:27.920 --> 01:20:37.000 Wenn ich die Formel F nehme und die natürliche Zahl mit 0 und für R 01:20:39.380 --> 01:20:45.520 einsetze und Beta kann beliebig sein, egal welches X ich habe, dann 01:20:45.520 --> 01:20:50.880 gibt es eine Y, sodass X echt kleiner als Y ist. 01:20:51.120 --> 01:20:54.480 Ich kann zum Beispiel Y gleich X plus 1 nehmen. 01:20:55.940 --> 01:21:01.300 Aber die Formel S1 von F, die ist nicht wahr in diesem Modell. 01:21:01.520 --> 01:21:05.540 Also es gibt keine Zahl, sodass diese Zahl echt kleiner als ich selber 01:21:05.540 --> 01:21:05.820 ist. 01:21:06.060 --> 01:21:06.900 Das geht einfach nicht. 01:21:08.060 --> 01:21:10.840 Also diese Substitution hat was ausgemacht. 01:21:12.600 --> 01:21:17.660 Die hat die Formel die Wahrheitswerteformel geändert. 01:21:19.380 --> 01:21:24.540 Jetzt habe ich, es gibt aber auch andere Substitutionen, wobei das 01:21:24.540 --> 01:21:25.080 nicht passiert. 01:21:25.300 --> 01:21:30.900 Also ich kann X durch Z setzen und dann habe ich, es gibt Y oder R von 01:21:30.900 --> 01:21:31.660 ZY. 01:21:31.900 --> 01:21:35.580 Ich habe X durch Z umbenannt, aber X bedeutet dasselbe. 01:21:36.640 --> 01:21:38.120 In dem Modell ist das immer noch wahr. 01:21:38.960 --> 01:21:43.300 Und der Unterschied hier ist einfach diese Kollision. 01:21:43.620 --> 01:21:48.220 Also Sigma 1 erzeugt eine Kollision, der setzt X durch was schon 01:21:48.220 --> 01:21:52.860 gebunden war, wobei Sigma 2 das nicht macht. 01:21:53.100 --> 01:21:59.120 Also ich nehme das X und setze es durch Z. 01:22:00.040 --> 01:22:04.520 Sobald X und Z sind frei, dann passiert nichts. 01:22:04.800 --> 01:22:07.900 Dann bleibt das logische Äquivalent. 01:22:09.080 --> 01:22:10.740 Und man kann auch zeigen, dass es so ist. 01:22:10.980 --> 01:22:13.080 Also kollisionsfreie Substitutionen 01:22:17.280 --> 01:22:22.560 erhalten diese und die Verrahmenbelegung dann auch anpassen. 01:22:24.180 --> 01:22:29.520 Bei der Verrahmenbelegung, wenn ich zum Beispiel X durch F von XY 01:22:29.520 --> 01:22:33.600 setze, dann muss ich auch die Werte dementsprechend ändern, sodass das 01:22:33.600 --> 01:22:34.580 alles zusammenpasst. 01:22:36.340 --> 01:22:39.700 Mehr dazu finden Sie in der Vorlesung Formale Systeme zum Beispiel. 01:22:44.080 --> 01:22:49.680 Es gibt Substitutionen und Sie dürfen das nicht verwechseln mit 01:22:49.680 --> 01:22:50.480 Unbenennung. 01:22:50.840 --> 01:22:57.420 Also Substitution ist irgendwas, aber das ist nicht Unbenennung. 01:22:59.360 --> 01:23:03.840 Bei Substitutionen, wenn eine Verrahme gebunden ist, dann darf ich die 01:23:03.840 --> 01:23:04.700 nicht ersetzen. 01:23:06.040 --> 01:23:08.420 Bei Unbenennung, dann darf ich das machen. 01:23:11.200 --> 01:23:13.900 Was meine ich überhaupt hier mit Unbenennung? 01:23:14.020 --> 01:23:18.800 Also zum Beispiel, ich habe eine Formel F und Y soll bitte nicht frei 01:23:18.800 --> 01:23:24.020 in F vorkommen und das G ist einfach für alle X F. 01:23:24.260 --> 01:23:25.700 Dann habe ich X quantifiziert. 01:23:26.880 --> 01:23:31.000 Wobei diese FV hier die freien Verrahmen dieser Formel sind. 01:23:31.480 --> 01:23:37.860 Und dann nehme ich diese Substitution die X zu Y macht und dann, wenn 01:23:37.860 --> 01:23:45.640 ich X durch Y unbenenne, dann ergibt sich das die Formel Gestrich, die 01:23:45.640 --> 01:23:48.660 besagt für alle Y dann Sigma von F. 01:23:49.080 --> 01:23:53.020 Dann habe ich in F alles durch 01:23:56.060 --> 01:24:00.160 alle Vorkommen von X, die nicht gebunden sind natürlich, durch Y 01:24:00.160 --> 01:24:05.200 ersetzt und dann habe ich für diesen Quantor dann X durch Y unbenannt. 01:24:06.200 --> 01:24:07.760 Aber die Formel ist nicht gleich. 01:24:07.760 --> 01:24:10.780 Die ist nicht gleich die Substitution, wenn ich die Substitution 01:24:10.780 --> 01:24:11.720 auf... 01:24:11.720 --> 01:24:13.440 Entschuldigung, kleiner Fehler da. 01:24:13.860 --> 01:24:16.560 Also das meine ich, also Sigma von G ist nicht Gestrich. 01:24:17.680 --> 01:24:21.620 Wenn ich Sigma auf G anwende, dann kann ich X nicht ersetzen, weil X 01:24:21.620 --> 01:24:22.220 gebunden ist. 01:24:22.340 --> 01:24:24.160 Dann kommt nicht diese Formel Gestrich raus. 01:24:26.240 --> 01:24:28.880 Sigma substituiert einfach die freien Verrahmen. 01:24:30.340 --> 01:24:37.880 Und wenn ich mir diesen Wert von Gestrich anschaue, dann ist das V für 01:24:37.880 --> 01:24:46.220 alle egal welches D ich habe in der Domäne dann wenn ich das für Y 01:24:46.220 --> 01:24:48.840 einsetze dann ist die Formel Sigma von F wahr. 01:24:50.140 --> 01:24:50.500 Und dann 01:24:54.560 --> 01:24:59.620 kann ich diese direkte Belegung haben. 01:24:59.900 --> 01:25:05.700 Also ich nehme Y also da könnte ich auch F nehmen und was in der 01:25:05.700 --> 01:25:08.600 Stelle X stand, dann durch dieses D einsetzen. 01:25:08.840 --> 01:25:15.220 Also ich habe für Y D eingesetzt, dann könnte ich auch für X in der 01:25:15.220 --> 01:25:17.040 Formel F dann D einsetzen. 01:25:17.720 --> 01:25:18.380 Das steht unten. 01:25:21.360 --> 01:25:23.740 Dieser Wahrheitswert ist gleich. 01:25:24.320 --> 01:25:26.880 Die Auswertung da ist gleich. 01:25:27.360 --> 01:25:29.320 Und dann sind die zwei Formeln äquivalent. 01:25:29.880 --> 01:25:33.460 Also Gestrich und GEDID sind äquivalent. 01:25:35.760 --> 01:25:36.600 So ist das. 01:25:36.800 --> 01:25:43.080 Also diese Umbenähnung, wenn F dann keine freie Substitution hat, dann 01:25:44.040 --> 01:25:46.780 wenn ich das umbenähne, dann bleibt das Logisch-Äquivalent. 01:25:48.080 --> 01:25:49.900 So, dann wäre ich zum Ende gekommen. 01:25:50.080 --> 01:25:52.440 Ich bedanke mich für die Aufmerksamkeit und wünsche euch noch ein 01:25:52.440 --> 01:25:53.160 schönes Wochenende.