WEBVTT 00:00.830 --> 00:01.930 So, schönen guten Morgen. 00:02.010 --> 00:05.230 Ich begrüße Sie zur Vorlesung Grundlageninformatik 2. 00:06.150 --> 00:08.770 Ich freue mich, dass Sie am Mittwochmorgen hier auch erschienen sind. 00:10.410 --> 00:14.270 Dann schauen wir mal, was wir beim letzten Mal gemacht haben. 00:15.490 --> 00:18.250 Da ging es nochmal um das Thema Komplexität. 00:18.530 --> 00:21.790 Hier rausche ich jetzt mal ganz schnell durch die Folien, die wir hier 00:21.790 --> 00:21.910 hatten. 00:22.050 --> 00:22.990 Da waren viele verschiedene. 00:23.450 --> 00:24.810 Da kann ich ganz schnell durchgehen. 00:25.010 --> 00:29.030 Wir hatten uns ja mit Turing-Maschinen, Turing-Berechenbarkeit 00:29.030 --> 00:31.290 beschäftigt, mit universellen Turing-Maschinen. 00:32.170 --> 00:35.350 Und letztes Mal waren wir dann, nachdem wir noch kurz auf das 00:35.350 --> 00:39.070 Halteproblem nochmal geguckt hatten, wiederholend, haben wir dann 00:39.070 --> 00:42.510 anschließend uns beschäftigt mit Komplexität. 00:43.510 --> 00:48.770 Wir hatten Komplexitätsklassen betrachtet und kamen dann zur 00:48.770 --> 00:53.150 Definition der Klassen P und NP. 00:53.910 --> 00:56.850 Auch das war schon die Stunde davor passiert. 00:56.850 --> 01:00.150 Und ich hatte sie darauf hingewiesen, dass eben die Frage ist, 01:00.250 --> 01:05.070 inwieweit tatsächlich Nichtdeterminismus in Bezug auf Berechnungen ein 01:05.070 --> 01:07.270 prinzipieller Unterschied ist. 01:07.490 --> 01:10.930 Also, dass man von Polynomiel auf Nichtpolynomiel kommt. 01:11.330 --> 01:13.070 Das ist aber bis heute nicht klar. 01:14.610 --> 01:18.250 Und ich hatte Ihnen dann dazu etwas erzählt, über Methoden, wie man 01:18.250 --> 01:22.590 versucht, das zu charakterisieren, über Reduzierbarkeit von Problemen. 01:22.650 --> 01:25.790 Wir hatten uns den Begriff der NP-Schwere angeschaut. 01:25.790 --> 01:32.050 Also, ein Problem ist NP-schwer, wenn halt jedes Problem aus NP auf 01:32.050 --> 01:34.830 dieses Problem Polynomiel reduziert werden kann. 01:35.610 --> 01:38.810 Und daraus kam dann der Begriff der NP-Vollständigkeit. 01:38.970 --> 01:42.050 Ein Problem, das nicht nur NP-schwer ist, sondern auch in einer Menge 01:42.050 --> 01:42.750 NP drin. 01:44.370 --> 01:48.790 Und Beispiele sind das Erfüllbarkeitsproblem, der Aussagenlogik und 01:48.790 --> 01:50.410 das Perfecting-Salesperson-Problem. 01:51.670 --> 01:56.190 Übrigens, hier bei dieser Frage Erfüllbarkeitsproblem der 01:56.190 --> 02:00.830 Aussagenlogik, da steht ja drin, konjunktive Normalform. 02:01.710 --> 02:05.790 Also, wenn Sie nur Formeln in disjunktiver Normalform hätten, müssen 02:05.790 --> 02:08.770 Sie sich überlegen, wie aufwendig es dann wäre, für eine Formel in 02:08.770 --> 02:12.890 disjunktiver Normalform zu überprüfen, ob sie erfüllbar ist oder 02:12.890 --> 02:13.410 nicht. 02:14.230 --> 02:19.670 Dann werden Sie sich interessante Dinge überlegen können mit dieser 02:19.670 --> 02:20.110 Frage. 02:20.710 --> 02:25.950 Ich hatte dann Ihnen erzählt, da hatten wir uns weiter beschäftigt mit 02:25.950 --> 02:27.970 weiteren Klassen, mit den Klassen oben drüber. 02:28.810 --> 02:33.870 NP-Space, EXP-Time, EXP-Space, wobei ich noch einige ausgelassen habe, 02:33.970 --> 02:36.290 die jeweils den Nichtdeterminismus betreffen. 02:37.230 --> 02:41.150 Und wir hatten dann uns ein konkretes Beispiel betrachtet, die 02:41.150 --> 02:44.410 Reduktion von Dreisat auf Clique. 02:47.290 --> 02:51.550 Das Clique-Problem, um Ihnen zu zeigen, wie man solch eine 02:51.550 --> 02:53.270 Transformation tatsächlich macht. 02:54.150 --> 02:57.350 Wir hatten gesehen, man kann also zu jeder Formel, erstmal das Clique 02:57.350 --> 03:01.810 -Problem war klar, zu jeder aussagenlogischen Formel, in diesem Fall 03:01.810 --> 03:08.130 in der Form Dreisat, das heißt drei Literale pro Klausel und eben in 03:08.130 --> 03:10.310 konjunktiver Normalform. 03:10.310 --> 03:13.470 Also in jeder disjunktiven Klausel nur drei Literale. 03:14.030 --> 03:17.350 Da konnten wir sehen, wir können daraus einen Graphen konstruieren, in 03:17.350 --> 03:20.610 dem gerade die Variablen oder die Literale miteinander verbunden sind, 03:20.690 --> 03:24.830 die gleichzeitig erfüllbar sind, sodass dann die Existenz einer M 03:24.830 --> 03:30.650 -Clique bei M-Klauseln gerade eine Erfüllbarkeit impliziert. 03:31.310 --> 03:33.930 Und dadurch hatten wir also die Reduktion dann hinbekommen. 03:34.510 --> 03:40.030 Und wir hatten anschließend gesehen, wie man Entscheidungsprobleme, 03:40.110 --> 03:42.610 Optimierungsprobleme und Konstruktionsprobleme aufeinander beziehen 03:42.610 --> 03:42.890 kann. 03:43.090 --> 03:45.650 Dass es reicht, Entscheidungsprobleme zu betrachten. 03:46.510 --> 03:49.630 Dann ein bisschen Konsequenzen, wie man eigentlich mit diesen Dingen 03:49.630 --> 03:50.150 umgeht. 03:50.890 --> 03:55.190 Und schließlich, wie man mit NP-vollständigen Problemen umgeht. 03:55.450 --> 03:59.090 Man kann sie ja nicht ignorieren, nicht beiseite legen, sondern muss 03:59.090 --> 04:00.650 sie pragmatisch lösen. 04:01.290 --> 04:02.470 Und eben z.B. 04:02.930 --> 04:03.490 approximativ. 04:03.490 --> 04:07.330 Dafür gibt es viele verschiedene Ansätze, mit denen man das sinnvoll 04:07.330 --> 04:07.850 machen kann. 04:08.050 --> 04:12.710 Es gibt auch sehr mächtige Werkzeuge, mit denen man durchaus relativ 04:12.710 --> 04:17.510 viele Problemstellungen von NP-vollständigen Problemen exakt lösen 04:17.510 --> 04:17.830 kann. 04:19.510 --> 04:22.910 Aber darüber hören Sie noch einiges in Operations Research. 04:25.830 --> 04:30.790 Aber generell sind sie im schlechtesten Fall, nach derzeitiger 04:30.790 --> 04:32.810 Kenntnis, nicht polynomiell zu lösen. 04:32.810 --> 04:33.850 Deswegen sehr schwierig. 04:34.250 --> 04:38.270 Und deswegen muss man eben approximativ dann das machen. 04:38.590 --> 04:40.770 Das war dann der erste Teil theoretischer Aspekte. 04:41.030 --> 04:44.430 Und wir haben anschließend angefangen mit dem zweiten Teil. 04:44.790 --> 04:51.790 Mit dem Teil Technische Informatik, Architektur von Rechensystemen. 04:52.870 --> 04:57.810 Und haben auch hier schon die ersten Folien uns angeschaut, die ersten 04:57.810 --> 04:59.130 Dinge kurz betrachtet. 04:59.130 --> 05:03.490 Ich habe Ihnen erzählt, wiederholend, was eine Bool'sche Algebra ist. 05:03.570 --> 05:05.730 Das kennen Sie schon aus Grundlagen der Informatik 1. 05:06.570 --> 05:12.250 Mit den vier Aktionen, dann daraus folgende Eigenschaften, Gesetze, 05:12.510 --> 05:15.150 die man ableiten kann aus diesen vier Aktionen. 05:15.850 --> 05:19.670 Und eben typische Sachen wie Assoziativgesetze, De Morgan'sche Regeln, 05:20.090 --> 05:21.610 Absorptionsgesetze usw. 05:22.630 --> 05:25.770 Wesentlich ist eben, dass alle diese Eigenschaften, die man hier 05:25.770 --> 05:27.030 sieht, immer dual gelten. 05:27.030 --> 05:31.850 Dual in dem Sinne, dass man Produkt durch Plus ersetzt und die Null 05:31.850 --> 05:32.650 durch die Eins. 05:33.390 --> 05:39.070 Und dann hat man also für die beiden Operationen Bool'sche Summe und 05:39.070 --> 05:43.030 Bool'sches Produkt die Gleichwertigkeit in Bezug auf alle diese 05:43.030 --> 05:43.830 Eigenschaften. 05:45.010 --> 05:48.430 Und das ist jetzt die erste Folie, die wir heute genauer betrachten. 05:48.890 --> 05:54.110 Wir wollen jetzt sehen, wie man damit Funktionen, wie man Bool'sche 05:54.110 --> 05:55.450 Funktionen definieren kann. 05:55.450 --> 06:00.570 Das Ziel dieser Beschäftigung mit Bool'schen Ausdrücken, Bool'schen 06:00.570 --> 06:03.650 Funktionen, Bool'schen Algebren ist, dass wir Schaltnetze und 06:03.650 --> 06:08.210 Schaltwerke beschreiben wollen in einer Art, sodass wir argumentieren 06:08.210 --> 06:11.570 können, wie sie konstruiert werden sollen. 06:11.670 --> 06:13.270 Es geht um die Konstruktion von Hardware. 06:14.130 --> 06:16.270 Dazu fangen wir eben an, damit wir sagen, was ist eine Bool'sche 06:16.270 --> 06:16.810 Funktion. 06:17.970 --> 06:21.230 Die einfachste Bool'sche Menge ist eine Menge mit zwei Elementen, 06:21.310 --> 06:22.450 einfach nur Null und Eins. 06:22.450 --> 06:25.250 Und die nennen wir immer die Bool'sche Menge. 06:26.950 --> 06:30.230 Das ist also hier das B mit dem Strich davor. 06:32.630 --> 06:38.070 Eine Bool'sche Funktion ist eine Funktion, die N-Argumente, N-Werte 06:38.070 --> 06:43.770 aus Null und Eins, abbildet auf einen Wert, Null oder Eins. 06:43.930 --> 06:45.150 Das ist eine Bool'sche Funktion. 06:46.690 --> 06:50.550 Ein Bool'scher Term, Bool'scher Ausdruck, ist das nächste, was wir 06:50.550 --> 06:51.010 definieren. 06:51.010 --> 06:54.030 Wir wollen Funktionen beschreiben können und können das zum Beispiel 06:54.030 --> 06:55.330 über Bool'sche Ausdrücke machen. 06:56.490 --> 07:01.770 Dazu braucht man zunächst mal eine Menge von Variablen, Bool'sche 07:01.770 --> 07:06.070 Variablen, die wir hier A1 bis A1 bezeichnen. 07:06.330 --> 07:09.270 Dann brauchen wir eine Menge von Symbolen. 07:10.650 --> 07:15.590 Das sind Null, Eins, Mal, Plus, Strich, Klammer auf, Klammer zu. 07:15.590 --> 07:20.850 Und die Menge der Variablen und der Symbole sind des Jungt. 07:22.130 --> 07:25.410 Dann definieren wir, was ein Bool'scher Term ist, ganz ähnlich zu dem, 07:25.530 --> 07:28.770 wie wir reguläre Ausdrücke definiert haben oder wie Sie in der 07:28.770 --> 07:35.130 Grundlageninformatik I auch schon formale Modelle kennengelernt haben. 07:35.710 --> 07:40.490 Also diese konstanten Null und Eins und jede Variable A ist ein 07:40.490 --> 07:41.130 Bool'scher Term. 07:42.670 --> 07:48.550 Und wenn A und B Bool'sche Terme sind, dann auch A Strich, A mal B und 07:48.550 --> 07:51.050 A plus B, jeweils in Klammern geschrieben. 07:52.050 --> 07:55.330 Also das sind praktisch nur Zeichenfolgen zunächst mal, die man in 07:55.330 --> 07:57.030 endlich vielen Schritten konstruieren kann. 07:57.470 --> 08:00.050 Das sieht zunächst mal genauso aus, wie das, was wir kennengelernt 08:00.050 --> 08:02.530 haben bei der Konstruktion von regulären Ausdrücken. 08:03.010 --> 08:04.490 Die sahen eigentlich völlig genauso aus. 08:04.630 --> 08:12.490 Ich stelle gerade fest, ich habe vergessen, die Werkzeuge aufzurufen. 08:13.230 --> 08:15.490 Das muss ich eigentlich mal schnell nachholen. 08:16.310 --> 08:17.190 Ganz kurz. 08:20.550 --> 08:30.210 Dazu muss ich kurz hier rein, da rein und die Werkzeuge aufrufen. 08:43.310 --> 08:48.670 Dauert einen kleinen Augenblick und dann ist schon alles erledigt. 08:50.830 --> 08:54.390 Ganz einfach, Terme in einer einfachen Art und Weise. 08:54.770 --> 08:56.610 Sie wissen, wie ein regulärer Ausdruck aussah. 08:56.810 --> 08:57.950 Das ist einfach Standard. 08:58.830 --> 09:02.170 Die Bedeutung solcher Terme ergibt sich dadurch, dass man sie 09:02.170 --> 09:07.690 interpretiert in irgendeiner Menge mit bestimmten Interpretationen 09:07.690 --> 09:11.510 dieser Operation Bool'sche Summe, Bool'sches Produkt und Bool'sches 09:11.510 --> 09:11.990 Komplement. 09:13.010 --> 09:17.530 Das Wesentliche ist, dass man jede Bool'sche Funktion durch einen 09:17.530 --> 09:19.890 Bool'schen Ausdruck beschreiben kann. 09:20.290 --> 09:27.770 Jeder Bool'sche Ausdruck mit N verschiedenen Variablen definiert durch 09:27.770 --> 09:31.090 Belegung der Variablen mit Werten aus B genau eine endstellige 09:31.090 --> 09:31.830 Bool'sche Funktion. 09:32.350 --> 09:43.090 Also wenn Sie hier aufschreiben A plus B mal C das wäre ein Bool'scher 09:43.090 --> 09:51.430 Ausdruck und wenn Sie jetzt A, B und C belegen mit irgendwelchen 09:51.430 --> 09:58.150 Werten F ist gleich diesem Ausdruck dann würden Sie hier 0, 0, 0 09:58.150 --> 10:04.910 hinschreiben 0, 0, 1, 0, 1, 0 und so weiter und Sie könnten hier 10:04.910 --> 10:08.550 jeweils wenn Sie sich das anschauen, A plus B mal C Sie müssten 10:08.550 --> 10:14.110 wissen, wie die Operationen definiert sind und wenn das also auf B 10:14.110 --> 10:17.530 interpretiert wird dann ist das 10:20.810 --> 10:26.530 Sie müssen halt entsprechend die Operationen haben und dann wäre das 10:26.530 --> 10:34.670 hier A oder B mal C und das ist da ein Strich Also in dem Fall wäre A 10:34.670 --> 10:42.810 oder B, das wäre 0 das wäre auf jeden Fall 0 in dem Fall und wenn hier 10:42.810 --> 10:47.730 in dem Fall wäre B 1 dann wäre das hier 1 mal C Strich da wäre das 10:47.730 --> 10:51.790 hier 1, da wäre es auch 0 und so weiter Sie können durch Belegung 10:51.790 --> 10:56.850 dieser Variablen mit Werten und durch Interpretation auf der 10:56.850 --> 11:00.570 Bool'schen Algebra, die nur über zwei Elementen gebildet wird und in 11:00.570 --> 11:03.910 dem Fall auch noch Interpretation von Bool'scher Summe, Bool'schem 11:03.910 --> 11:07.970 Produkt und Bool'schem Komplement als logische Operationen können Sie 11:07.970 --> 11:14.810 hier dann aus dem Ausdruck eine Wertetabelle ableiten Okay, das also 11:14.810 --> 11:18.090 ganz kurz zu diesen Funktionen Sie kennen das im Prinzip aus 11:18.090 --> 11:22.130 Grundlagen der Informatik 1 und Sie kennen auch diese verschiedenen 11:22.130 --> 11:25.630 Darstellungen von Funktionen Das hier wäre also eine typische 11:25.630 --> 11:31.590 Bool'sche Funktion Hier in dem Fall für das exklusive oder Wobei das 11:31.590 --> 11:37.090 exklusive oder könnte man eigentlich auch anders darstellen Das ist ja 11:37.090 --> 11:42.330 keine Bool'sche Operation, das XOR sondern Sie könnten dazu einen 11:42.330 --> 11:46.710 Ausdruck hinschreiben Der Ausdruck in dem Fall wäre entweder in 11:46.710 --> 11:51.310 disjunktiver Normalform oder in konjunktiver Normalform aufgeschrieben 11:51.310 --> 11:55.370 Also entweder, was sind disjunktive, konjunktive Normalformen Nur noch 11:55.370 --> 11:59.050 mal zur Erinnerung für Sie Disjunktive Normalform hieß, dass ich 11:59.050 --> 12:04.630 einfach eine Disjunktion schreibe aller 1-Zeilen in der Wertetabelle 12:05.160 --> 12:10.530 und die 1-Zeilen in der Wertetabelle, also die Funktion ist 1 wenn 12:10.530 --> 12:17.450 eine dieser Zeilen jeweils gilt und entweder gilt also dann das a' mal 12:17.450 --> 12:25.530 b a' mal b, also a' muss 1 sein und b muss 1 sein das heißt a ist 0, b 12:25.530 --> 12:33.470 ist 1 und dann kommt eine 1 raus oder a mal b' das ist diese Zeile, a 12:33.470 --> 12:40.350 mal b' und das heißt, wir machen eine Disjunktion aller 1-Zeilen mit 12:40.350 --> 12:44.370 den Belegungen jeweils, die dann genau die Literale angeben in dieser 12:44.370 --> 12:48.350 disjunktiven Normalform Bei der konjunktiven Normalform sagen wir, 12:48.510 --> 12:56.990 keine der 0-Zeilen gilt keine der 0-Zeilen gilt, heißt alle diese es 12:56.990 --> 13:04.390 gilt nicht diese Zeile bei der konjunktiven Normalform es gilt nicht 13:04.390 --> 13:09.210 diese Zeile und nicht diese Zeile und wenn die beiden nicht gelten, 13:09.370 --> 13:15.590 dann heißt es gilt also nicht a' ich könnte es anders hinschreiben ich 13:15.590 --> 13:26.010 könnte folgendes hinschreiben nicht die erste Zeile halt, es gilt es 13:26.010 --> 13:38.430 gilt hier a mal b a' mal b' gilt nicht und da muss ich a' und b' 13:38.630 --> 13:43.870 hinschreiben Entschuldigung, ich muss hier bei den Regeln bleiben, die 13:43.870 --> 13:46.410 hier stehen a' plus b' 13:49.470 --> 14:03.550 nein noch mal also a' mal b', die beiden gelten nicht und Produkt mit 14:03.550 --> 14:09.650 a mal b, auch das gilt nicht so, das sind die beiden Zeilen, beide 14:09.650 --> 14:14.810 Zeilen gelten nicht deswegen überall Konjunktion und wenn ich hier a' 14:15.030 --> 14:19.550 mal b' hinschreibe, dann über das De Morgan'sche Gesetz mache ich dann 14:19.550 --> 14:25.070 gerade daraus a plus b und hier, wenn also das Kompliment von a mal b 14:25.070 --> 14:32.230 ist a' plus b' dann haben sie genau die konjunktive Normalform die 14:32.230 --> 14:35.650 eben sich über daraus ergibt logisch, dass sie sagen, keine der 14:35.650 --> 14:40.650 Nullzeilen gilt also der Ausdruck ist 1, wenn keine der Nullzeilen 14:40.650 --> 14:43.770 gilt und das ist genau die Beschreibung, die wir hier jetzt uns 14:43.770 --> 14:47.410 aufgeschrieben haben das heißt, ich habe dann eine Konjunktion von 14:47.410 --> 14:54.350 Disjunktionen ja, also dadurch haben wir eben eine konjunktive 14:54.350 --> 14:57.950 Normalform von Disjunktionen bei der disjunktiven Normalform haben wir 14:57.950 --> 15:02.030 eine Disjunktion von Konjunktionen das kennen sie im Prinzip alles aus 15:02.030 --> 15:05.610 Grundlageninformatik 2 sie können dann auch noch diese Ausdrücke 15:05.610 --> 15:10.150 minimieren dafür gibt es Verfahren, wie man das machen kann auf die 15:10.150 --> 15:12.570 ich aber hier nicht eingehe, das geht über diese Vorlesung hinaus 15:12.570 --> 15:16.550 Binary Decision Diagrams sind jetzt eine Art solche Funktionen zu 15:16.550 --> 15:19.110 beschreiben, die sie noch nicht kennengelernt haben aber eine ganz 15:19.110 --> 15:25.350 wichtige Art, wie man Funktionen charakterisiert man nennt sie auch 15:25.350 --> 15:30.370 reduzierter Funktionsgraf eine grafische Beschreibung des Wertes einer 15:30.370 --> 15:33.990 Funktion oder einer Funktionsdefinition 15:37.090 --> 15:44.830 das heißt hier hätten sie ein einfaches Binary Decision Diagram dieser 15:44.830 --> 15:50.270 Graf gibt ihnen eine Funktion an auf die Art und Weise, dass sie hier 15:50.270 --> 15:56.710 den Wert 0 bekommen wenn a 0 ist und b 0 haben sie die 0 wenn a 0 ist 15:56.710 --> 16:01.150 und b 1 kommen sie zu 1 wenn a 1 ist und b 1 kommen sie zu 0 und so 16:01.150 --> 16:05.710 weiter das heißt, das ist genau die XOR-Funktion gleiche Funktion, die 16:05.710 --> 16:09.250 hier steht jetzt haben sie also drei Arten, wie eine Funktion 16:09.250 --> 16:12.970 beschrieben ist und alle drei Arten sind sehr sinnvoll die brauchen 16:12.970 --> 16:16.070 sie für verschiedene Fragestellungen und wir werden uns das im 16:16.070 --> 16:19.550 weiteren genauer angucken also hier die unten, das Binary Decision 16:19.550 --> 16:23.490 Diagram brauchen sie für Simulationen, wenn sie einen Schaltkreis 16:23.490 --> 16:27.510 simulieren wollen dann brauchen sie solche Darstellungen, weil die 16:27.510 --> 16:32.510 sehr effizient eingesetzt werden können wenn sie einen Schaltkreis, 16:32.570 --> 16:36.070 ein Schaltnetz tatsächlich erstellen wollen wenn sie den bauen wollen, 16:36.490 --> 16:40.490 brauchen sie einen symbolischen Ausdruck und naja, eine Wertetabelle 16:40.490 --> 16:46.850 zum Beispiel in sogenannten Field Programmable Gate Arrays da stellen 16:46.850 --> 16:50.790 sie Funktionen über Wertetabellen dar und realisieren die dann 16:50.790 --> 16:55.230 tatsächlich über solche Tabellen unterschiedliche Arten, die alle ihre 16:55.230 --> 16:58.730 Berechtigung haben ihren Sinn haben und eingesetzt werden, je nachdem 16:58.730 --> 17:01.270 in welchem Zusammenhang sie gebraucht werden. 17:02.150 --> 17:04.030 So, und jetzt werden wir uns das noch genauer angucken, weil Sie das 17:04.030 --> 17:09.490 noch nicht kennen diese Art Binary Decision Diagrams Warum geht man 17:09.490 --> 17:10.170 überhaupt daran? 17:10.670 --> 17:14.910 Die Schalttabellen sind natürlich immer sehr groß Wenn Sie n Variablen 17:14.910 --> 17:19.490 haben, haben Sie zwei hoch n Zeilen da drin und das heißt, das wird 17:20.090 --> 17:23.950 für eine Funktion mit n Variablen dann haben Sie n exponentielle 17:23.950 --> 17:28.870 Platz, um die Funktion aufzuschreiben Das ist für große Funktionen 17:28.870 --> 17:33.730 halt dann sehr groß Die kanonische disjunktive Normalform und die 17:33.730 --> 17:37.510 kanonische konjunktive Normalform also aus dem, wenn man die bulischen 17:37.510 --> 17:40.430 Ausdrücke hernimmt sind die natürlich sehr großen, sind die 17:40.430 --> 17:44.150 kanonischen bei denen in jeder Klausel alle Variablen auftauchen 17:44.150 --> 17:49.590 müssen sind unnötig groß aber wenn man sie vereinfacht, auch dann 17:49.590 --> 17:53.630 bleiben häufig noch sehr große Ausdrücke übrig und das heißt, wenn Sie 17:53.630 --> 17:57.170 einen Wert berechnen wollen einer Funktion, und Sie haben einen sehr 17:57.170 --> 18:01.230 großen Ausdruck der zum Teil eben sogar exponentiell sein kann in der 18:01.230 --> 18:07.490 Anzahl der Variablen und zwar bei sehr praktischen Funktionen dann 18:07.490 --> 18:11.710 haben Sie einen sehr hohen Aufwand, um diesen Ausdruck auszuwerten 18:11.710 --> 18:14.870 weil der Aufwand, um einen Ausdruck auszuwerten immer linear ist in 18:14.870 --> 18:20.480 der Länge dieses Ausdrucks und deswegen versucht man das besser 18:20.480 --> 18:27.640 hinzubekommen und wie gesagt, die Kosten der Auswertung sind linear in 18:27.640 --> 18:30.800 der Größe der Formel und deswegen sucht man eine andere Art, dies 18:30.800 --> 18:33.740 darzustellen und deswegen die reduzierten Funktionsgrafen oder Binary 18:33.740 --> 18:38.260 Decision Diagrams die wir uns im Weiteren genauer angucken werden also 18:38.260 --> 18:42.700 die braucht man beim rechnergeschützten Schaltungsentwurf und 18:42.700 --> 18:46.140 Schaltungsentwurf, Hardware-Entwurf ist ein sehr wichtiger Bereich für 18:46.140 --> 18:49.980 die Industrie leider hat man in Deutschland, es versäumt diese 18:49.980 --> 18:53.780 Industrie wirklich in Deutschland zu halten weil man zu den 18:53.780 --> 18:57.680 Zeitpunkten, als man dort sehr viel getan hat gemeint hat, dass andere 18:57.680 --> 19:01.460 Technologien wichtiger sind die wir heute gerade abschaffen wollen da 19:01.460 --> 19:05.120 hat man das falsche Pferd gesetzt es ist zwar einiges gemacht worden 19:05.120 --> 19:09.660 zu Schaltnetzentwurfen, Schaltwerken aber die Industrie dazu hat man 19:09.660 --> 19:13.600 ins Ausland verkauft das ist jetzt überwiegend im asiatischen Bereich 19:13.600 --> 19:22.560 in Deutschland sind wir da leider nicht so aktiv gewesen man kann 19:22.560 --> 19:26.240 diese reduzierten Funktionsgrafen generell als Datenstruktur sehr 19:26.240 --> 19:28.800 sinnvoll einsetzen deswegen geht es auch über diesen Bereich der 19:28.800 --> 19:33.680 bool'schen Funktionen hinaus und etwas was dem ganzen zugrunde liegt 19:33.680 --> 19:36.200 jetzt für bool'sche Funktionen, man kann das eben auch für andere 19:36.200 --> 19:40.160 Funktionen machen aber für bool'sche Funktionen ist eine Erkenntnis 19:40.160 --> 19:45.400 die hier dargestellt ist in diesem Kasten wenn wir uns eine beliebige 19:45.400 --> 19:50.620 Funktion anschauen eine bool'sche Funktion dann können wir diese 19:50.620 --> 19:58.460 Funktion die in diesem Fall n Variablen x1 bis xn hier hat f von x1 19:58.460 --> 20:02.020 bis xn können wir darstellen als 20:05.180 --> 20:11.480 wir können die darstellen als eine Summe von zwei Termen, und zwar 20:11.480 --> 20:20.280 bilden wir das Produkt von x1, die erste Variable, mal f von 1, x2 bis 20:20.280 --> 20:20.800 xn. 20:20.940 --> 20:27.780 Das heißt, wir betrachten den Wert der Funktion für x1 gleich 1. 20:28.680 --> 20:30.320 Das ist eine andere Funktion. 20:31.380 --> 20:34.940 Für x1 gleich 1 können wir einen anderen Ausdruck hinschreiben. 20:34.940 --> 20:38.000 Und den multiplizieren wir mit x1. 20:38.140 --> 20:48.960 Also wenn x1 1 ist, dann ist x1 mal f von 1, x2 bis xn, gleich f von 20:48.960 --> 20:50.280 1, x2 bis xn. 20:50.360 --> 20:51.940 Dann ist aber auch x1 gleich 1. 20:52.520 --> 20:55.740 Die andere Möglichkeit ist, dass x1 gleich 0 ist. 20:55.740 --> 21:00.800 Wenn x1 gleich 0 ist, dann haben wir also den Term hier f von 0, x2 21:00.800 --> 21:01.420 bis xn. 21:02.400 --> 21:04.640 Und den multiplizieren wir mit x1'. 21:04.640 --> 21:10.900 Wenn also x1 gleich 0 ist, ist x1' gleich 1. 21:11.720 --> 21:16.400 Das heißt dann, für x1 gleich 0 ist das hier der Wert unserer 21:16.400 --> 21:17.300 Funktion. 21:20.000 --> 21:25.340 Diese Darstellung ist sicherlich so gültig, dass wir eine Funktion auf 21:25.340 --> 21:26.860 diese Art und Weise darstellen können. 21:26.960 --> 21:30.440 Wir unterscheiden die beiden Fälle x1 gleich 1 und x1 gleich 0, 21:31.260 --> 21:36.340 betrachten jeweils die sich daraus ergebenden Funktionen f an der 21:36.340 --> 21:40.540 Stelle x1 gleich 1 und f an der Stelle x1 gleich 0 und multiplizieren 21:40.540 --> 21:47.360 die jeweils mit dem aktuellen Wert der Variablen x1 beziehungsweise 21:47.360 --> 21:53.460 x1' und bilden die Summe aus diesen beiden Termen. 21:53.920 --> 21:58.680 Und wenn wir das grafisch darstellen, heißt das, wir betrachten uns 21:58.680 --> 22:01.420 den Wert unserer Variablen x1. 22:01.980 --> 22:08.880 Wenn der 0 ist, dann ist die Funktion, der Funktionswert f von 0, x2 22:08.880 --> 22:12.540 bis xn, abhängig von den Werten von x2 bis xn. 22:12.540 --> 22:17.260 Wenn der 1 ist, ist der Wert der Funktion f von 1, x2 bis xn. 22:18.600 --> 22:22.140 Und das sieht zunächst mal aus, als wäre das nur eine kompliziertere 22:22.140 --> 22:23.360 Darstellung dieser Funktion. 22:24.840 --> 22:28.680 Auch bei diesem Beispiel sieht es zunächst mal so aus, als wäre das 22:28.680 --> 22:30.760 umständlicher. 22:30.940 --> 22:33.100 Hier ist ein konkretes Beispiel angegeben. 22:33.560 --> 22:35.940 Das hier ist unser Ausdruck, den wir haben. 22:35.940 --> 22:40.040 a c plus b mal a strich plus b strich c. 22:40.960 --> 22:48.660 Wenn wir jetzt sagen, wir betrachten das Ganze für a gleich 1, dann 22:48.660 --> 22:55.220 müssen wir also a multiplizieren mit der Funktion, das ist also die 22:55.220 --> 22:59.660 Funktion f an der Stelle 0, b c. 22:59.660 --> 23:05.100 Wenn wir uns das Ding hier betrachten und da ist das a gleich 0, 0 mal 23:05.100 --> 23:11.760 c ist 0, 0 plus b ist b. 23:13.600 --> 23:18.480 Entschuldigung, wir haben hier a ist 1. 23:19.780 --> 23:22.700 Ich war gerade dadurch irritiert. 23:22.700 --> 23:25.220 Wir betrachten jetzt zunächst mal den Wert a gleich 1. 23:26.100 --> 23:32.340 Wenn a gleich 1 ist, einmal c ist c, plus b, das ist also c plus b, 23:32.600 --> 23:38.400 mal a ist 1, dann ist a strich gleich 0, dann bleibt b strich c übrig. 23:39.180 --> 23:42.780 Also das ist der Term für f von 1. 23:43.880 --> 23:49.780 Das hier wäre also, dieses hier in dem Fall ist f von 1, b c. 23:49.780 --> 23:51.540 Das multiplizieren wir mit a. 23:52.640 --> 23:59.100 Und dieser Term hier muss jetzt sein f von 0, b c. 23:59.500 --> 24:07.420 f von 0, b c, also wenn a 0 ist, in dem Fall wäre also hier 0 mal c 24:07.420 --> 24:10.980 gleich 0, plus b ist b. 24:12.560 --> 24:17.640 Und hier steht dann, wenn das a gleich 0 ist, steht hier a strich, das 24:17.640 --> 24:18.340 ist dann 1. 24:19.300 --> 24:23.300 1 plus irgendetwas ist immer 1, das heißt, es bleibt nur das b übrig, 24:23.420 --> 24:24.560 deswegen steht hier nur das b. 24:26.060 --> 24:31.060 Also das sind einfach Anwendungen der Gesetze der burschen Algebren 24:31.060 --> 24:33.040 zur Vereinfachung dieser Terme. 24:33.800 --> 24:36.060 Und dann kommt eben genau dieser Term dort raus. 24:36.060 --> 24:40.340 Und wenn wir den anders aufschreiben würden, dann würden wir eben hier 24:40.340 --> 24:51.320 entsprechend hinschreiben, dann dieses c plus b mal b strich c in dem 24:51.320 --> 24:51.680 Fall. 24:52.420 --> 24:56.120 Und hier würde einfach nur b stehen. 24:56.480 --> 24:59.880 Und hier oben drin, in dem Fall, würde a drin stehen. 24:59.880 --> 25:06.220 Das wäre also der Baum, der sich ergibt, wenn wir diesen Ausdruck, 25:06.400 --> 25:08.240 diese Funktion aufspalten. 25:09.560 --> 25:13.700 So kann man also eine Funktion aufspalten. 25:13.760 --> 25:16.180 Man kann das auch etwas anders machen, indem man einfach eine andere 25:16.180 --> 25:19.280 Darstellung dieser Funktion sich hernimmt. 25:20.500 --> 25:22.100 Man kann das rekursiv anwenden. 25:22.100 --> 25:24.460 Natürlich kann man jetzt hier das hier weitermachen, sich hier 25:24.460 --> 25:26.200 anschauen, wenn ich den Wert von b... 25:26.900 --> 25:29.420 Also wenn ich jetzt das hier weitermachen würde, hier steht ja nur b 25:29.420 --> 25:30.280 drin in dem Fall. 25:30.760 --> 25:34.580 Da könnte ich jetzt mit 0 und 1 sagen, hier würde ich also auf 0 25:34.580 --> 25:37.740 gehen, da würde ich auf 1 gehen, dann wäre ich da schon fertig. 25:38.300 --> 25:43.040 Hier müsste ich, wenn b gleich 0 oder b gleich 1 ist, noch 25:43.040 --> 25:44.660 entsprechend weiter aufspalten. 25:45.100 --> 25:49.500 Also hier würde ich entsprechend noch weiter aufspalten auf weitere 25:49.500 --> 25:50.580 Terme. 25:50.580 --> 25:52.540 Das kann man alles rekursiv weiter so fortführen. 25:53.040 --> 25:56.420 Man kann auch ein bisschen anders vorgehen und man nimmt eine andere 25:56.420 --> 25:57.000 Darstellung. 25:57.660 --> 26:01.080 Man nimmt die Wertetabelle und baut aus der Wertetabelle einen Baum. 26:02.040 --> 26:04.660 Wie kann ich aus der Wertetabelle einen Baum bauen? 26:04.960 --> 26:05.780 Ganz einfach. 26:06.460 --> 26:10.780 Ich habe hier also eine Funktion angegeben, das ist hier in dem Fall 26:10.780 --> 26:13.580 die Übertragsfunktion eines binären Addierers. 26:14.360 --> 26:17.420 Ich hatte schon einmal Ihnen etwas über einen binären Addierer 26:17.420 --> 26:23.740 erzählt, als wir Turing-Maschinen haben betrachtet. 26:23.840 --> 26:27.980 Da haben wir immer eine binäre Zahl um 1 erhöht. 26:32.600 --> 26:36.300 Das hat uns schon mal mit den binären Zahlen kurz beschäftigt. 26:37.240 --> 26:42.160 Sie wissen, wenn ich also zwei Zahlen addiere, hier 0, 1, 1, 0 und da 26:42.160 --> 26:47.220 irgendwas drauf addiere, 0, 0, 0, 1 zum Beispiel. 26:47.420 --> 26:48.840 Oder da kommt kein Übertrag. 26:49.240 --> 26:52.280 Nehmen wir hier noch eine 1 hin. 26:53.140 --> 26:58.540 Dann habe ich in diesem Fall eine Zahl a, eine Zahl b. 27:01.240 --> 27:05.180 Und dann kommt eben noch der Übertrag hinzu aus jeder Stelle. 27:05.360 --> 27:06.280 Der ist zu Anfang 0. 27:06.440 --> 27:09.240 In dem Fall wäre 1, dann wäre wieder 1, wieder 1. 27:09.400 --> 27:13.040 Und ich hätte hier am Ende als Summa ein 1 stehen und davor hätte ich 27:13.040 --> 27:15.200 in dem Fall 0, 0, 0 stehen. 27:15.660 --> 27:18.860 Das sind also die Übertragswerte, die muss ich berechnen. 27:18.860 --> 27:24.540 Und der Übertrag ist 1, wenn ich mindestens zwei Einsen habe in diesen 27:24.540 --> 27:28.700 drei Werten a, i, b, i und Übertrag. 27:28.840 --> 27:31.220 Also a, b und Übertrag in dem Fall. 27:32.380 --> 27:37.960 Und mindestens zwei Einsen, das haben Sie in dieser Zeile, in der, in 27:37.960 --> 27:38.680 der und in der. 27:39.880 --> 27:46.300 Das heißt mindestens zwei der Variablen a, b und ü sind 1. 27:46.300 --> 27:52.300 Jetzt kann ich aus der Wertetabelle ganz einfach diesen Baum bauen, 27:52.420 --> 27:56.120 indem ich einfach schaue, wenn a gleich 0 oder 1 ist, gehe ich auf b, 27:56.780 --> 27:58.900 schaue da 0 oder 1, ü 0 oder 1. 27:59.000 --> 28:03.700 Und ich habe jetzt über diesen Baum auf jedem Pfad genau eine dieser 2 28:03.700 --> 28:09.680 hoch n Kombinationen der Werte der Variablen a, b und ü. 28:09.680 --> 28:14.340 Und für jeden Pfad in diesem Baum bis zu einem Blatt schaue ich halt 28:14.340 --> 28:17.260 einfach in die Tabelle und schreibe den entsprechenden Wert da rein. 28:18.680 --> 28:22.820 Und so habe ich also aus der Wahrheitstabelle oder aus der 28:22.820 --> 28:27.420 Wertetabelle meiner Funktion einen Baum gebaut. 28:27.420 --> 28:36.680 Das ist noch kein Binary Decision Diagram, sondern ein reduzierter, 28:36.680 --> 28:38.280 das wäre der volle Funktionsgraf. 28:38.400 --> 28:40.140 Das ist kein reduzierter Funktionsgraf. 28:41.060 --> 28:45.580 Ein reduzierter Funktionsgraf entsteht daraus oder dadurch, dass ich 28:45.580 --> 28:49.280 jetzt sage, ich verschmelze identische Teilgrafen. 28:50.000 --> 28:53.620 Also zum Beispiel habe ich hier ganz viele Nullen. 28:54.920 --> 29:00.160 Ich muss ja dann für nicht 4 verschiedene Knoten abspeichern, sondern 29:00.160 --> 29:01.780 die Null speichere ich nur einmal ab. 29:02.900 --> 29:08.000 Genauso speichere ich hier die Einsen nur einmal ab als einen Knoten. 29:08.540 --> 29:11.260 Da habe ich einen Nullknoten, einen Einsknoten, das reicht ja. 29:12.140 --> 29:17.900 Und dann kann man weitermachen und man eliminiert einen Knoten, falls 29:17.900 --> 29:20.220 beide Kanten auf denselben Nachfolger zeigen. 29:20.300 --> 29:21.260 Sehen Sie mal hier zum Beispiel. 29:21.400 --> 29:27.800 Dadurch, dass ich die beiden Knoten zusammenfasse, dann gehen von 29:27.800 --> 29:31.500 diesem Knoten Ü zwei Kanten beide auf die Null. 29:32.380 --> 29:35.480 Dann ist offensichtlich der Wert von der Variable Null in dem Fall 29:35.480 --> 29:35.920 irrelevant. 29:36.540 --> 29:39.180 Das heißt, die kann ich genauso gut rausstreichen, diesen Knoten. 29:40.340 --> 29:45.160 Also, falls beide Kanten auf denselben Nachfolger zeigen, kann ich 29:45.160 --> 29:48.900 etwas eliminieren, kann ich also diesen Knoten eliminieren. 29:50.900 --> 29:55.560 Und identische Teilgrafen ist also etwas allgemeiner, als nur 29:55.560 --> 29:58.720 identische Knoten zu vereinigen. 30:00.140 --> 30:04.640 Ich kann mir also auch anschauen, gibt es irgendwelche Teilgrafen, die 30:04.640 --> 30:05.400 identisch sind. 30:05.520 --> 30:07.100 Auch die brauche ich nur einmal abzuspeichern. 30:07.940 --> 30:10.100 Und das werden wir auf der nächsten Folie genauer machen. 30:11.000 --> 30:18.140 Wenn man das dann anwendet, diese beiden Regeln, von unten bis nach 30:18.140 --> 30:22.020 oben, also hier der zum Beispiel, in dem Fall gehen beide auf Eins. 30:22.420 --> 30:23.920 Den Knoten kann ich auch rausstreichen. 30:26.500 --> 30:30.360 Und wenn Sie sich das hier anschauen, ich habe hier, der eine Knoten 30:30.360 --> 30:33.360 geht auf die Null, der andere geht auf die Eins, der geht auf die 30:33.360 --> 30:34.680 Null, der andere auf die Eins. 30:35.140 --> 30:38.880 Diese beiden Teilgrafen hier, die kann ich identifizieren. 30:39.780 --> 30:40.360 Die sind gleich. 30:41.320 --> 30:42.460 Die kann ich auch zusammenfassen. 30:42.540 --> 30:43.700 Das machen wir auf der nächsten Folie. 30:44.360 --> 30:47.160 Also, ich kann auf diese Art und Weise den Grafen verkleinern. 30:48.140 --> 30:52.380 Und wenn man das eben gemacht hat, bis man keine weiteren 30:52.380 --> 30:56.180 Vereinfachungen mehr hinbekommt, dann bekommt man ein Binary Decision 30:56.180 --> 30:56.600 Diagram. 30:57.600 --> 31:01.720 Also, Anwendung dieser beiden Regeln, bis sich keine Vereinfachung 31:01.720 --> 31:07.020 mehr ergibt, liefert den reduzierten Funktionsgrafen. 31:07.580 --> 31:08.960 Das ist das Binary Decision Diagram. 31:10.780 --> 31:14.640 Eine Sache, die man sich überlegen muss, ist, dass die Reihenfolge der 31:14.640 --> 31:17.700 Variablen durchaus relevant ist dabei. 31:18.240 --> 31:23.100 Je nachdem, welche Variablenreihenfolge ich betrachte, bekomme ich 31:23.100 --> 31:26.360 unterschiedliche Binary Decision Diagrams oder kann ich 31:26.360 --> 31:28.280 unterschiedliche Binary Decision Diagrams bekommen. 31:28.980 --> 31:32.360 Das kann abhängen davon, in welcher Reihenfolge man das macht. 31:33.480 --> 31:36.900 Und deswegen ist das durchaus ein Entwurfsproblem. 31:37.520 --> 31:41.940 Was ist die günstigste Reihenfolge, um ein möglichst kleines Binary 31:41.940 --> 31:43.280 Decision Diagram zu bekommen? 31:44.020 --> 31:46.840 Das ist sofort wieder ein Optimierungsproblem. 31:47.000 --> 31:51.660 Sie können sich vorstellen, so ein Problem, bei dem man abhängig von 31:51.660 --> 31:55.180 einer Reihenfolge eine Lösung bekommt, riecht nach einem 31:55.180 --> 31:56.100 Permutationsproblem. 31:56.100 --> 32:01.320 Und das ist ähnlich wie das Travelling Salesperson Problem ein NP 32:01.320 --> 32:02.100 -schweres Problem. 32:03.380 --> 32:08.180 Das sieht man sehr schnell, dass das schon wieder Entwurfsprobleme 32:08.180 --> 32:08.480 bringt. 32:09.000 --> 32:12.260 Wenn ich eine bestmögliche Darstellung einer Funktion durch ein Binary 32:12.260 --> 32:16.200 Decision Diagram haben möchte, habe ich sofort ein NP-vollständiges 32:16.200 --> 32:16.480 Problem. 32:17.180 --> 32:20.980 Aber das ist eigentlich gar nicht das wesentliche Thema in diesem 32:20.980 --> 32:21.460 Augenblick. 32:21.780 --> 32:26.260 Sondern wir wollen ja sehen, wie wir erstmal solche Regeln anwenden 32:26.260 --> 32:26.600 können. 32:26.740 --> 32:30.560 Hier wird das, was ich gerade skizziert habe, an dem ersten Beispiel 32:30.560 --> 32:33.080 nochmal grafisch dargestellt. 32:33.780 --> 32:37.540 Wir unterscheiden jetzt hier eben die 0-Knoten und die 1-Knoten. 32:37.580 --> 32:38.480 Die fassen wir zusammen. 32:39.300 --> 32:41.100 Dann haben wir also diesen Graphen. 32:42.040 --> 32:44.520 Das ist die erste Vereinfachung. 32:44.520 --> 32:54.680 Und dann sehen wir, dass die beiden Teilgrafen, die auf dieses Ü 32:54.680 --> 32:59.220 gehen, jeweils identisch sind. 32:59.460 --> 33:02.120 Führen mit 0 auf 0, mit 1 auf 1. 33:02.220 --> 33:05.780 Dann kann ich die zusammenfassen und genauso kann ich eben diese hier 33:05.780 --> 33:07.120 rausstreichen. 33:07.800 --> 33:09.560 Dann habe ich den Graphen, der hier unten steht. 33:09.560 --> 33:12.120 Sie sehen, der ist deutlich kleiner. 33:13.020 --> 33:16.840 Dieser Graph hier ist deutlich kleiner als dieser hier. 33:17.080 --> 33:20.180 Reicht aber völlig aus, um diese Funktion darzustellen. 33:21.120 --> 33:26.600 Wenn Sie jetzt noch mehr solche Variablen hätten, könnte es sein, dass 33:26.600 --> 33:32.060 Sie dann eine sehr kleine Struktur haben. 33:32.060 --> 33:35.860 Es ist tatsächlich so, dass Sie viele Beispiele haben, wo das binäre 33:35.860 --> 33:39.980 Entscheidungsdiagramm linearen Platz braucht in der Anzahl der 33:39.980 --> 33:43.220 Variablen, um eine solche Funktion darzustellen. 33:43.740 --> 33:48.420 Während eben die Wertetabelle oder auch der bursche Ausdruck dazu 33:48.420 --> 33:52.020 exponentiellen Platz braucht in der Anzahl der Variablen. 33:52.320 --> 33:56.800 Das heißt, durch ein binäres Entscheidungsdiagramm können Sie sehr 33:56.800 --> 33:59.340 viel Effizienzgewinne erzielen. 33:59.340 --> 34:00.520 Aber nicht immer. 34:00.640 --> 34:01.720 Vielleicht noch ganz kurz zurück. 34:03.560 --> 34:08.760 Es ist so, dass Herr König auch hier sein X-Wizard weiterentwickelt 34:08.760 --> 34:09.140 hat. 34:10.480 --> 34:23.520 Sie können also genau diesen Baum anschauen. 34:24.140 --> 34:26.260 Das ist der, den wir hier gerade eben betrachtet haben. 34:26.260 --> 34:30.180 Und es gibt hier eine Operation, vereinfache einen Schritt weiter. 34:30.380 --> 34:34.840 Wenn ich darauf gehe, dann werden zwei Knoten gezeigt, die man 34:34.840 --> 34:35.900 zusammenfassen kann. 34:36.580 --> 34:38.720 Also immer sehr schrittweise gemacht. 34:39.340 --> 34:41.940 Und dann haben Sie im nächsten Schritt die beiden zusammengefasst. 34:42.040 --> 34:42.780 Hier sehen Sie das. 34:43.340 --> 34:46.460 Und dann werden die nächsten beiden unten hier zusammengefasst, ganz 34:46.460 --> 34:47.040 strikt. 34:47.920 --> 34:51.040 Schichtweise werden hier erstmal alle Nullen zusammengefasst. 34:51.700 --> 34:58.040 Dann haben Sie hier also alle Nullen zusammen. 34:58.300 --> 35:00.200 Dann werden die Einsen zusammengefasst. 35:01.160 --> 35:03.560 Und Sie sehen immer den Graph, der sich daraus ergibt. 35:04.600 --> 35:08.400 Und jetzt kommt die nächste Regel, dass Sie hier einen Knoten haben. 35:08.800 --> 35:13.100 Und für beide Werte gehe ich auf den gleichen Nachfolgerknoten. 35:13.140 --> 35:14.520 Dann kann ich den rausstreichen. 35:15.800 --> 35:21.880 Dann wird hier die Regel angewandt, dass die beiden Knoten C 35:21.880 --> 35:27.900 identifiziert werden können, weil sie die gleichen Nachfolgerknoten 35:27.900 --> 35:28.600 jeweils führen. 35:29.120 --> 35:30.880 Dann werden die zu einem zusammengefasst. 35:31.020 --> 35:34.820 Und dann kommt hier nochmal die Regel, dass Sie einen Knoten haben, 35:35.020 --> 35:38.380 dessen beide Nachfolger auf den gleichen Knoten zeigen. 35:38.520 --> 35:40.820 Dann kann auch der rausgestrichen werden. 35:41.180 --> 35:42.180 Und dann ist man fertig. 35:42.180 --> 35:45.940 Das, was Sie gerade auf der Folie gemacht haben, können Sie also hier 35:45.940 --> 35:54.840 für unterschiedliche Funktionen an solchen Beispielen durchführen. 35:56.020 --> 36:04.420 Das ist auch ein schönes Werkzeug, um mit solchen Funktionen oder mit 36:04.420 --> 36:06.900 solchen binären Entscheidungsdiagrammen und der Konstruktion dieser 36:06.900 --> 36:09.720 binären Entscheidungsdiagramme etwas mehr Übung zu bekommen. 36:11.260 --> 36:11.860 Okay. 36:12.840 --> 36:13.700 Weiteres Beispiel. 36:15.300 --> 36:20.700 Diese Funktion, die wir hier angeben, das XOR von drei Werten, ist 36:20.700 --> 36:24.300 gerade die Summenfunktion des binären Addierers. 36:25.080 --> 36:27.000 Hier habe ich jetzt C als Übertrag genannt. 36:27.160 --> 36:29.640 Hätte ich vorher eigentlich auch das Ü durch ein C ersetzen können. 36:29.780 --> 36:30.500 C für Carry. 36:31.860 --> 36:36.100 Und wenn wir uns die Summenfunktion anschauen, dann bekommen wir 36:36.100 --> 36:37.660 ausgehend von der Wertetabelle 36:41.160 --> 36:43.500 diese Graphen, diesen binären Baum. 36:44.700 --> 36:49.300 Und hier, Sie erinnern sich, bei der XOR-Funktion ist es so, dass die 36:49.300 --> 36:54.360 1 ist, wenn Sie eine ungerade Anzahl von Einsen haben bei den 36:54.360 --> 36:54.660 Argumenten. 36:55.420 --> 36:57.160 Also eine Eins oder drei Einsen. 36:57.280 --> 36:58.300 Ansonsten ist es 0. 36:58.980 --> 37:06.620 Also wenn wir hier irgendeinen Pfad betrachten, hier den Pfad zum 37:06.620 --> 37:08.100 Beispiel, da haben wir eine Eins. 37:08.240 --> 37:09.300 Also kommt eine Eins raus. 37:09.840 --> 37:12.180 Wenn wir da unten eine Eins gehabt hätten, gehen wir auf die Null. 37:12.560 --> 37:14.640 Auch hier fassen wir die Knoten zusammen. 37:14.820 --> 37:17.180 Wir haben also hier die Null- und Einsknoten zusammengefasst. 37:17.800 --> 37:21.320 Und dann schaut man wieder, welche Graphen sind hier identisch. 37:21.320 --> 37:25.940 Und Sie stellen fest, also hier von dem C aus gehen Sie mit 0 auf 0, 37:26.040 --> 37:26.980 mit 1 auf 1. 37:28.500 --> 37:33.820 Und dieser Knoten ganz rechts, der hier, geht auch mit 0 auf 0, mit 1 37:33.820 --> 37:34.260 auf 1. 37:34.380 --> 37:37.160 Also können Sie diesen hier und den zusammenfassen. 37:37.940 --> 37:41.600 Und außerdem, wenn Sie die anderen beiden betrachten, die haben auch 37:41.600 --> 37:42.640 identisches Verhalten. 37:42.880 --> 37:45.660 Also den hier und den hier können Sie auch zusammenfassen. 37:46.510 --> 37:54.100 Und dann kommt daraus genau dieser Graph, bei dem Sie jetzt jeweils 37:54.100 --> 37:55.840 zwei Cs zusammengefasst haben. 37:56.100 --> 37:58.080 Die Bs können Sie nicht mehr zusammenfassen. 37:58.840 --> 38:02.180 Und Sie haben damit also ein binäres Entscheidungsdiagramm für diese 38:02.180 --> 38:06.080 Funktion von drei Variablen, die gerade die XOR-Funktion angibt. 38:08.000 --> 38:11.740 Wenn Sie beliebig viele Variablen haben, also die Paritätsfunktion 38:11.740 --> 38:15.700 daraus machen für N Variablen, haben Sie hier eine solche lineare 38:15.700 --> 38:18.280 Kette, die Sie einfach sofort führen können. 38:19.000 --> 38:22.440 Also hier noch einmal, wenn Sie D dazu hätten, noch einmal genau eine 38:22.440 --> 38:26.300 solche Schicht einbauen, dann haben Sie das binäre 38:26.300 --> 38:28.900 Entscheidungsdiagramm für vier Variablen. 38:29.820 --> 38:31.480 Das ergibt also eine sehr einfache Struktur. 38:33.660 --> 38:39.840 Also das BDD für die XOR-Funktion hat genau zwei n plus 1 Knoten. 38:40.640 --> 38:45.160 Die disjunktive Normalform oder auch die konjunktive Normalform genau 38:45.160 --> 38:49.900 dieser XOR-Funktion hat aber exponentielle Größe. 38:51.560 --> 38:55.540 Sie haben dort, wenn Sie das als Ausdruck darstellen, einen Ausdruck, 38:55.640 --> 38:58.600 der hat exponentielle Größe in der Anzahl der Variablen. 38:59.540 --> 39:02.720 Und das heißt, Sie haben hier einen exponentiellen Unterschied für die 39:02.720 --> 39:04.000 Kosten der Funktionsauswertung. 39:04.080 --> 39:07.400 Wenn Sie den Ausdruck nehmen würden, um die Funktion auszuwerten, 39:08.680 --> 39:11.360 müssten Sie den vollständig durchlaufen. 39:11.960 --> 39:15.660 Das ist exponentieller Aufwand in der Anzahl der Variablen, weil der 39:15.660 --> 39:16.780 Ausdruck so groß ist. 39:17.220 --> 39:20.120 Wenn Sie das binäre Entscheidungsdiagramm nehmen, dann brauchen Sie 39:20.120 --> 39:23.480 nur einmal hier durchzulaufen und Sie sind fertig. 39:26.260 --> 39:31.900 In einem binären Entscheidungsdiagramm ist die Auswertung immer in 39:31.900 --> 39:35.260 linearer Zeit zu machen, weil Sie nur einen Pfad durch alle Variablen 39:35.260 --> 39:36.100 durchlaufen müssen. 39:36.740 --> 39:41.540 Die Größe des binären Entscheidungsdiagramms kann eventuell größer 39:41.540 --> 39:45.420 sein als linear oder kann auch exponentiell sein in der Anzahl der 39:45.420 --> 39:45.980 Variablen. 39:45.980 --> 39:50.400 Also wenn Sie jetzt hier einen solchen Baum hätten, in dem fast 39:50.400 --> 39:52.440 nichts, also nach dieser, das geht immer. 39:52.880 --> 39:56.160 Aber wenn Sie dann nichts weiter reduzieren könnten, hätten Sie immer 39:56.160 --> 39:58.680 noch exponentielle Größe in der Anzahl der Variablen. 39:59.320 --> 40:04.240 Aber der Aufwand für die Auswertung ist immer linear, weil Sie immer 40:04.240 --> 40:07.940 nur einen Pfad durch Ihren Graphen durchlaufen müssen. 40:08.280 --> 40:09.980 Der hat immer lineare Länge. 40:12.520 --> 40:16.460 Also Funktionsauswertung ist mit solchen binären 40:16.460 --> 40:19.860 Entscheidungsdiagrammen immer in linearer Zeit möglich. 40:20.220 --> 40:24.400 Und bei den anderen Darstellungen brauchen Sie dafür einfach deutlich 40:24.400 --> 40:25.220 mehr Zeit. 40:26.560 --> 40:31.060 Und deswegen ist das also ein wesentliches Werkzeug. 40:31.060 --> 40:32.960 Kurz ein paar Bemerkungen noch. 40:33.600 --> 40:38.280 Hier bei den BDDs, die ich Ihnen gezeigt habe, da ist auf jedem Weg 40:38.280 --> 40:42.200 von der Wurzel zu den Blättern die Reihenfolge der Variablen gleich. 40:42.320 --> 40:44.960 Ich hatte erst gesagt, es ist wichtig, welche Reihenfolge man nimmt. 40:45.560 --> 40:47.120 Ich habe das immer von links nach rechts gemacht. 40:47.320 --> 40:50.600 Erste, zweite, dritte, vierte Variable in der Darstellung der 40:50.600 --> 40:51.100 Funktion. 40:51.940 --> 40:53.800 Man kann jede andere Reihenfolge nehmen. 40:54.040 --> 40:56.560 Und dann könnte man sich auch noch überlegen, es muss ja nicht auf 40:56.560 --> 40:58.460 jedem Pfad die gleiche Reihenfolge sein. 40:58.940 --> 41:01.680 Wenn es aber so ist, wenn man das so macht, dann hat man sogenannte 41:01.680 --> 41:06.460 geordnete oder ordered binary decision diagrams, OBDDs. 41:08.920 --> 41:10.940 Das heißt, das ist wieder eine spezielle Art. 41:11.180 --> 41:14.520 Man könnte also auch noch versuchen, auf den einzelnen Pfaden andere 41:14.520 --> 41:15.500 Reihenfolgen zu nehmen. 41:15.580 --> 41:19.040 Auch das würde wieder das Entwurfsproblem etwas schwieriger machen. 41:20.440 --> 41:25.780 Und das ist hier eben eine Frage, welche Reihenfolge führt zum 41:25.780 --> 41:26.540 kleinsten BDD. 41:26.540 --> 41:31.580 Dann wäre die Frage, ob ich für jede Funktion ein binary decision 41:31.580 --> 41:34.320 diagram mit polynomialem Aufwand finden kann. 41:34.460 --> 41:35.520 Das ist leider nicht der Fall. 41:37.700 --> 41:42.400 Wenn Sie zwei Zahlen multiplizieren, also Sie wollen hier zwei Zahlen 41:42.400 --> 41:47.080 multiplizieren, machen das so auf die übliche Art und Weise, dass Sie 41:47.080 --> 41:53.480 die jeweils mit der Schulmethode, mit den einzelnen Ziffern 41:53.480 --> 41:56.560 multiplizieren und dann hier entsprechend aufaddieren. 41:57.340 --> 42:05.040 Die mittleren Bits, die Sie hier haben, wenn Sie sich den Boolean 42:05.040 --> 42:10.840 -Ausdruck anschauen, also wenn Sie sich die Funktion anschauen, um die 42:10.840 --> 42:14.920 mittleren Bits zu berechnen, dann braucht das binary decision diagram 42:14.920 --> 42:18.680 für diese mittleren Bits auch einen exponentiellen Aufwand. 42:18.680 --> 42:22.020 Das heißt, die Größe des binary decision diagrams ist dann 42:22.020 --> 42:25.060 exponentiell in der Anzahl der Variablen. 42:28.340 --> 42:33.640 Die Zeit, um das Bit auszurechnen, wenn Sie das BDD haben, ist 42:33.640 --> 42:37.660 natürlich dann linear in der Anzahl der Bits. 42:38.080 --> 42:42.540 Aber wie gesagt, das ist ein Beispiel für eine sehr praktische 42:42.540 --> 42:47.820 Funktion, bei der Sie eben leider keinen BDD mit polynomiellem Aufwand 42:47.820 --> 42:48.740 finden können. 42:49.840 --> 42:53.480 Aber, wie gesagt, für CAD-Anwendung ganz wichtig. 42:53.840 --> 42:56.860 Wichtigste Datenstruktur für Simulationswerkzeuge. 42:57.520 --> 43:00.660 Und wenn Sie also Schaltungen entwerfen, die simulieren wollen, dann 43:00.660 --> 43:03.960 nimmt man das Datenstrukturen BDDs. 43:04.900 --> 43:08.820 Und dafür gibt es viel Literatur, viele Überlegungen, wie man das 43:08.820 --> 43:10.120 effizient machen kann. 43:11.160 --> 43:11.880 Entschuldigung. 43:13.340 --> 43:15.740 Und wir hatten Ihnen Bücher angegeben. 43:16.240 --> 43:19.220 Ein Buch von Eschermann, da steht einiges drin über BDDs. 43:20.160 --> 43:20.420 Okay. 43:21.280 --> 43:22.780 Jetzt noch ein paar Bemerkungen dazu. 43:23.180 --> 43:26.400 Ich hatte schon gesagt, das ist eine wichtige algebraische Struktur. 43:26.780 --> 43:28.820 Ganz allgemein. 43:29.580 --> 43:32.480 Poolsche Algebren verallgemeinern viele verschiedene Dinge. 43:34.360 --> 43:37.860 Insbesondere verallgemeinern sie eben, oder sind sie ein Werkzeug, um 43:37.860 --> 43:39.660 Schaltnetze, Schaltwerke zu beschreiben. 43:39.660 --> 43:43.000 Haben aber in vielen anderen Bereichen auch Relevanz. 43:43.120 --> 43:44.960 Sie können damit Mengenstrukturen beschreiben. 43:45.380 --> 43:49.020 Sie können Poolsche Räume definieren, Poolsche Verbände und Ähnliches. 43:49.160 --> 43:50.700 Gibt es viele interessante Theorien darüber. 43:51.160 --> 43:52.320 Können Sie sich alles durchlesen. 43:52.780 --> 43:54.460 Das kann ich in dieser Vorlesung nicht machen. 43:55.000 --> 43:58.940 Typische Interpretation von Poolschen Algebren ist zum Beispiel, eine 43:58.940 --> 44:02.840 Sache ist die Aussagenlogik, eine andere Interpretation wäre die 44:02.840 --> 44:06.540 Mengenalgebra oder das, was uns jetzt interessiert, die Schaltalgebra. 44:07.800 --> 44:11.520 Und das betrachten wir jetzt im folgenden Schaltalgebra. 44:11.740 --> 44:13.880 Wir wollen Richtung Schaltnetze, Schaltwerke gehen. 44:14.440 --> 44:19.400 In diesem Fall sind die Poolschen Elemente bei Schaltnetzen, oder sind 44:19.400 --> 44:21.780 in diesem Fall Schaltelemente. 44:22.320 --> 44:23.440 Was sind Schaltelemente? 44:23.560 --> 44:27.860 Das sind Elemente, die zwei verschiedene Zustände annehmen können. 44:28.580 --> 44:32.880 Also irgendein Schalter, oder ein Relais, oder eine Diode, oder ein 44:32.880 --> 44:34.000 Transistor oder Ähnliches. 44:34.000 --> 44:37.480 Transistor kann leitend oder nicht leitend sein, Schalter kann ein 44:37.480 --> 44:38.580 oder aus sein und Ähnliches. 44:38.680 --> 44:40.380 Das sind bistabile Schaltelemente. 44:40.560 --> 44:42.720 Schaltelemente, die zwei verschiedene Werte annehmen können. 44:43.440 --> 44:47.820 Sie können auch eine Schaltalgebra machen mit mehrwertiger Logik. 44:47.980 --> 44:52.360 Nicht nur zwei verschiedene Zustände, sondern 4, 6, 5 oder 8 oder 17 44:52.360 --> 44:52.920 oder was immer. 44:53.360 --> 44:55.260 Geht auch, ist aber nicht effizient. 44:57.080 --> 45:01.080 Zweiwertige Logik liefert die effizienteste Darstellung von 45:01.080 --> 45:02.000 Funktionen. 45:02.680 --> 45:04.640 Kann man beweisen, machen wir aber nicht. 45:05.780 --> 45:08.920 Also, ich habe bistabile Schaltelemente mit zwei verschiedenen 45:08.920 --> 45:09.160 Zuständen. 45:09.700 --> 45:12.800 Offen, geschlossen, nicht leitend, leitend oder Ähnliches. 45:13.520 --> 45:18.780 Und ich kann jetzt diesen Zuständen einfach Schaltwerte 0 und 1 45:18.780 --> 45:19.020 zuordnen. 45:19.980 --> 45:22.720 Ob das jetzt offen oder geschlossen ist, oder leitend oder nicht 45:22.720 --> 45:24.100 leitend, ist mir jetzt erstmal egal. 45:24.600 --> 45:28.260 Und ich sage, das sind einfach nur zwei verschiedene Schaltzustände. 45:29.440 --> 45:33.880 Und damit habe ich also eine Buche Menge 0 und 1. 45:34.540 --> 45:36.540 Das sind dann Schaltkonstanten in dem Fall. 45:37.280 --> 45:41.560 Und das kann ich jetzt darstellen als ein Schaltelement, das entweder 45:41.560 --> 45:46.780 offen sein kann oder es kann geschlossen sein. 45:47.580 --> 45:50.600 Und so ein Schaltelement, das wird dann eben mit dem Schaltwert 0 oder 45:50.600 --> 45:51.440 1 dargestellt. 45:51.580 --> 45:56.000 Das könnte ich sagen, wenn ich hier vorne den Wert 1 anlege, hier ein 45:56.000 --> 46:00.300 Signal rein schicke, Strom anlege, dann würde in dem Fall hier immer 0 46:00.300 --> 46:03.540 rauskommen, oder bei dem Schaltelement würde hier beim Zustand, 46:03.720 --> 46:09.280 Zustand hier wäre 0, da würde 0 rauskommen, wenn ich den Zustand 1 46:09.280 --> 46:12.620 habe an der Stelle, dann ist das geschlossen, dann kommt rechts 1 46:12.620 --> 46:13.000 raus. 46:13.980 --> 46:18.740 Das wäre also der Schaltwert, das ist der hier, der ist 0 oder 1. 46:19.490 --> 46:25.380 Bei so einem Schaltelement, wenn dieses Schaltelement den Wert 1 hat, 46:26.060 --> 46:28.300 dann würde ich also praktisch einen Wert hier durchreichen. 46:28.780 --> 46:32.500 Das sehen wir gleich auf der nächsten Folie, wenn wir jetzt sagen, wie 46:32.500 --> 46:35.380 wir Schaltungen tatsächlich realisieren. 46:36.660 --> 46:42.440 Zunächst mal eine Schaltvariable ist also eine Variable, die nur 46:42.440 --> 46:43.680 endlich viele Werte annehmen kann. 46:43.820 --> 46:46.100 Wir haben also binäre Schaltvariablen. 46:47.700 --> 46:50.640 Buhl'sche Funktionen, haben wir vorher definiert, sind Funktionen von 46:50.640 --> 46:51.500 B hoch N nach B. 46:52.220 --> 46:54.200 Die nennen wir jetzt einfach binäre Schaltfunktionen. 46:55.060 --> 46:57.180 Wir beziehen sie auf solche Schaltelemente. 46:57.760 --> 47:00.780 Und eine Schaltung wäre einfach eine technische Realisierung einer 47:00.780 --> 47:02.600 binären Schaltfunktion. 47:03.040 --> 47:05.800 Also eine technische Realisierung so einer Buhl'schen Funktion, die 47:05.800 --> 47:07.200 wir jetzt Schaltfunktion nennen. 47:07.840 --> 47:13.120 Dann haben wir Schaltungen, die immer den Wert 0 haben. 47:13.260 --> 47:15.080 Das wäre also so eine Schaltkonstante 0. 47:15.080 --> 47:18.820 Es könnte niemals, wenn Sie hier vorne einen Wert anlegen, der kann 47:18.820 --> 47:20.800 niemals rauskommen, hier kommt immer eine 0 raus. 47:23.380 --> 47:28.520 Und die Interpretation ist in dem Fall eben, bei so Schaltbildern 47:28.520 --> 47:31.300 links liege stets eine 1 an, rechts ergibt sich der Wert der 47:31.300 --> 47:32.860 Schaltung, wie ich das hier angedeutet habe. 47:33.560 --> 47:37.540 Schaltkonstante 1, wenn Sie hier eine 1 anlegen, dann kommt hier 47:37.540 --> 47:38.560 rechts immer eine 1 raus. 47:38.660 --> 47:39.460 Leitet immer durch. 47:39.880 --> 47:41.080 Kann nie unterbrochen werden. 47:41.620 --> 47:42.880 Das wäre die Schaltkonstante 1. 47:43.800 --> 47:48.760 Und wenn ich also kein konstantes Element habe, kann ich eben 47:48.760 --> 47:51.420 unterscheiden zwischen Wert 1 und Wert 0. 47:53.100 --> 47:55.480 Und dann wollen wir diese Elemente verknüpfen können. 47:56.140 --> 47:59.700 Wir hatten Buhl'sches Produkt, Buhl'sche Summe, Buhl'sches Komplement. 48:00.240 --> 48:03.480 Machen daraus jetzt die Konjunktion, Disjunktion und das Komplement. 48:04.380 --> 48:10.600 Und dann wäre das die Konjunktion von zwei Schaltelementen, diese 48:10.600 --> 48:15.600 beiden Schaltelemente A und B werden also auch durch Konjunktionen 48:15.600 --> 48:16.780 beschrieben, A und B. 48:16.960 --> 48:20.380 Jetzt ersetzen wir das Plus, interpretieren das Plus durch eine 48:20.380 --> 48:27.460 Disjunktion, das übliche Disjunktionszeichen, das Produkt durch ein 48:27.460 --> 48:32.480 Konjunktionszeichen und das Strich wird hier durch ein überstrichenes 48:32.480 --> 48:36.320 Quersymbol, also A-quer wäre das im Prinzip. 48:36.320 --> 48:39.700 Wobei ich dieses Quer meistens nicht verwenden werde, weil das 48:39.700 --> 48:41.060 schwierig zu schreiben ist. 48:41.200 --> 48:45.420 Wenn Sie das auf einer Powerpointfolie schreiben wollen, ist das etwas 48:45.420 --> 48:46.460 schwierig darzustellen. 48:47.200 --> 48:50.700 Deswegen werden Sie da oft an der Stelle trotzdem den Strich sehen. 48:51.480 --> 48:54.420 Disjunktion entsprechend wäre eine Parallelschaltung. 48:58.340 --> 49:02.180 Während hier bei der Serienschaltung und der Reihenschaltung der Wert 49:02.180 --> 49:08.620 eben nur durch kann, wenn beide den Wert 1 haben, wenn also hier bei 49:08.620 --> 49:12.740 beiden 1 steht, dann würde entsprechend hier der Strom durchlaufen. 49:12.920 --> 49:16.280 Sie hätten hier eine 1 und nur dann kann das rechts 1 sein, deswegen 49:16.280 --> 49:17.440 die Reihenschaltung. 49:18.020 --> 49:22.080 Bei der Parallelschaltung reicht es, wenn einer dieser beiden den Wert 49:22.080 --> 49:22.660 1 hat. 49:22.880 --> 49:27.300 Deswegen ist klar, das ist eine Disjunktion der beiden 49:27.300 --> 49:28.140 Schaltvariablen. 49:28.140 --> 49:31.980 Das Komplement wäre eine sogenannte Ruhekontaktschaltung. 49:32.180 --> 49:36.060 Das wäre also ein Wert, wenn Sie hier das A auf 1 machen, dann geht 49:36.060 --> 49:38.180 das Ding hier nach oben, dann haben Sie hier eine Verbindung. 49:38.660 --> 49:45.480 Wenn Sie den Wert 0 haben, gehen Sie hier hoch, dann haben Sie hier 49:45.480 --> 49:46.000 eine Verbindung. 49:46.140 --> 49:49.380 Wenn Sie den Wert 1 haben, dann ist das Ding gerade, dann haben Sie 49:49.380 --> 49:50.120 keine Verbindung. 49:50.700 --> 49:53.080 Da wäre also die Funktion A auf A quer. 49:53.760 --> 49:57.400 Sie negieren den Wert der Schaltvariablen A. 49:57.400 --> 50:01.900 Wenn also hier vorne eine 1 anliegt und hier liegt eine 0 an, dann 50:01.900 --> 50:04.780 kommt in dem Fall das A quer raus, nämlich auch eine 1. 50:05.960 --> 50:07.800 Weil Sie dann diese Verbindung hier haben. 50:08.920 --> 50:15.700 Das ist die übliche Art, wie man Verknüpfungen von solchen 50:15.700 --> 50:16.900 Schaltelementen machen kann. 50:17.180 --> 50:24.560 Sie sehen, das ist nur eine Interpretation des Burschenprodukts, der 50:24.560 --> 50:30.440 Burschensumme und des Burschenkomplements durch Schaltungen. 50:30.940 --> 50:33.260 Verknüpfungen von Schaltelementen. 50:34.000 --> 50:38.120 Damit können Sie jetzt Funktionen realisieren. 50:42.040 --> 50:47.600 Wenn man sich diese Interpretation anguckt, sieht man sofort, das sind 50:47.600 --> 50:51.680 natürlich genau solche Operationen, wie wir sie vorher auch schon 50:51.680 --> 50:52.560 angeguckt haben. 50:53.080 --> 51:00.540 Wir wissen, dass die Interpretation von Burschenprodukt, Burschensumme 51:00.540 --> 51:05.280 und Burschenkomplement durch Konjunktion, Disjunktion und logischen 51:05.280 --> 51:08.560 Komplement, dass das auch eine Bursche Algebra ergibt. 51:08.780 --> 51:11.080 Also ist diese Schaltalgebra auch eine Bursche Algebra. 51:11.920 --> 51:13.480 Das ist relativ schnell zu sehen. 51:14.280 --> 51:17.840 Jetzt schauen wir uns mal an, wie viele solche Schaltfunktionen es 51:17.840 --> 51:18.640 eigentlich geben kann. 51:18.720 --> 51:22.120 Wenn wir nur zwei Elemente haben, zwei Variablen, wie viele 51:22.120 --> 51:23.880 verschiedene Funktionen können wir angeben? 51:24.480 --> 51:32.480 Natürlich wissen wir, bei n Variablen haben wir 2 hoch n verschiedene 51:32.480 --> 51:33.100 Belegungen. 51:34.500 --> 51:37.520 Also 2 hoch n Belegungen der Variablen. 51:38.820 --> 51:41.180 Und wie viele Funktionen kann es geben? 51:42.000 --> 51:46.880 Für jede dieser Belegungen, für jede Zeile, kann ich entweder eine 0 51:46.880 --> 51:47.820 oder eine 1 schreiben. 51:48.400 --> 51:54.200 Das heißt, ich habe 2 hoch 2 hoch n Funktionen. 51:56.220 --> 52:01.200 Das heißt also, für zweistellige Schaltfunktionen habe ich 2 hoch 2 52:01.200 --> 52:06.320 verschiedene Belegungen, diese 4 verschiedenen Belegungen, und 2 hoch 52:06.320 --> 52:10.300 4 verschiedene Funktionen, also 16 verschiedene Funktionen. 52:10.420 --> 52:12.100 Und die schauen wir uns jetzt der Reihe nach an. 52:13.440 --> 52:16.280 Die erste Möglichkeit wäre, alles auf 0 zu setzen. 52:16.900 --> 52:18.040 Dann haben Sie die 0-Funktion. 52:18.920 --> 52:21.760 Das nächste wäre, eine Konjunktion zu machen. 52:22.960 --> 52:27.660 Da haben wir nur eine 1, wenn beide Werte 1 sind. 52:28.660 --> 52:31.900 Und ich schreibe hier jeweils hin, die kanonische disjunktive 52:31.900 --> 52:32.700 Normalform. 52:34.480 --> 52:38.620 Kanonische disjunktive Normalform heißt, alle Variablen tauchen auf, 52:39.580 --> 52:46.920 und jeweils, ich schreibe also auf die Konjunktion, kanonische 52:46.920 --> 52:49.880 disjunktive Normalform, ich schreibe auf die Disjunktion aller 1 52:49.880 --> 52:50.260 -Zeilen. 52:50.800 --> 52:54.980 Also, in diesem Fall habe ich nur eine 1-Zeile, und da stehen a und b 52:54.980 --> 52:59.640 jeweils mit 1 drin, das heißt a und b ist in diesem Fall die 52:59.640 --> 53:03.060 kanonische disjunktive Normalform für die Konjunktion. 53:04.080 --> 53:07.680 Dann haben wir die nächste Funktion, da steht an dieser Stelle eine 1. 53:08.460 --> 53:10.300 Das wäre a und b quer. 53:11.180 --> 53:15.400 Dann haben wir die Funktion, da stehen 2 Einsen hier unten. 53:15.400 --> 53:20.040 Also sind das 2 Einszeilen, die eine Zeile hat a und b quer drin 53:20.040 --> 53:21.280 stehen, die andere a und b. 53:22.820 --> 53:28.060 Nächste Funktion, da steht wieder nur eine 1, also a quer und b ist 53:28.060 --> 53:30.000 diese eine 1, die dort steht. 53:31.060 --> 53:35.020 Dann haben wir mal wieder 2 Einsen, hier haben wir also diese Zeile, 53:35.140 --> 53:40.000 das ist a quer und b, und diese Eins hier, da haben wir a und b. 53:40.680 --> 53:43.280 So, alles irgendwelche Funktionen. 53:43.360 --> 53:46.160 Dann kommt hier eine Funktion, die kennen wir schon, das ist das Dixor 53:46.160 --> 53:46.640 -Funktion. 53:47.540 --> 53:53.580 Die beiden Einszeilen sind diese beiden a quer und b oder a und b 53:53.580 --> 53:53.920 quer. 53:55.640 --> 53:57.540 Und entsprechend geht es weiter. 53:58.300 --> 54:01.820 Jetzt haben wir schon 3 Einsen drin, entsprechend 3 Terme für diese 3 54:01.820 --> 54:03.700 Zeilen mit den entsprechenden Belegungen. 54:05.800 --> 54:09.120 Und in dem Fall sehen wir, das ist die Disjunktion. 54:10.080 --> 54:16.620 Diese Funktion in dem Fall ist 1, wenn ein Argument den Wert 1 hat. 54:17.900 --> 54:23.280 Und Sie sehen eben, dass die Disjunktion aufgeschrieben als kanonische 54:23.280 --> 54:29.280 disjunktive Normalform auf die Art und Weise beschrieben wird. 54:29.280 --> 54:34.660 Also die haben 3 Zeilen, die eine 1 enthalten, also gerade wenn ein 54:34.660 --> 54:41.620 Argument 1 ist, a quer und b, a und b quer oder a und b. 54:42.100 --> 54:44.100 Wenn beide 1 sind, ist der Wert ja auch 1. 54:47.160 --> 54:52.820 Und entsprechend hier oben nochmal, wenn jetzt die erste Zeile nur 54:52.820 --> 54:57.760 eine 1 hat, alle anderen 0, dann haben Sie die Negation der Oder 54:57.760 --> 55:02.820 -Funktion, das nennt man auch Pierce-Funktion, a quer und b quer. 55:02.820 --> 55:10.140 Das heißt, wenn beide 0 sind, hat diese Funktion den Wert 1 und sie 55:10.140 --> 55:15.280 hat den Wert 0, wenn mindestens eine Variante den Wert 1 hat. 55:16.120 --> 55:18.140 Genau das Gegenteil der Oder-Funktion. 55:18.940 --> 55:23.000 Dann haben Sie die Funktion, die gerade das Gegenteil der XOR-Funktion 55:23.000 --> 55:23.440 ist. 55:23.980 --> 55:27.360 Sie haben hier eine Funktion, die keinen besonderen Namen hat. 55:27.360 --> 55:31.180 Dann haben Sie hier eine Funktion, das ist gerade die Implikation, b 55:31.180 --> 55:32.000 folgt a. 55:33.420 --> 55:39.300 Das ist also a quer und b quer oder a und b quer oder a und b. 55:39.780 --> 55:47.240 3 mal eine 1 und nur falsch, wenn a falsch ist und b 1. 55:47.340 --> 55:49.860 Also aus etwas Wahrem können Sie nichts Falsches folgern. 55:50.760 --> 55:53.280 Alle anderen haben den Wert 1. 55:53.280 --> 55:56.520 Dann haben Sie hier wieder eine Funktion, die keinen besonderen Namen 55:56.520 --> 55:56.880 hat. 55:57.640 --> 56:00.680 Dann haben Sie hier die Funktion, die jetzt gerade die Implikation a 56:00.680 --> 56:01.580 folgt b ist. 56:02.700 --> 56:07.300 Und schließlich dann die Funktion f14, Schäffer-Funktion, das nennt 56:07.300 --> 56:10.460 das Gegenteil der Konjunktion. 56:11.800 --> 56:15.340 Also das ist die negierte Konjunktion, das nennt. 56:16.840 --> 56:21.460 Und entsprechend haben wir dann noch als letzte Funktion die 1 56:21.460 --> 56:22.060 -Funktion. 56:22.060 --> 56:28.780 Bei der 1-Funktion sind alle Zeilen gleich 1, also müssen Sie die 56:28.780 --> 56:33.580 Disfunktion aller Belegungen der Variablen hinschreiben. 56:34.640 --> 56:38.560 Also Sie können natürlich, wenn Sie das jetzt hinschreiben würden in 56:38.560 --> 56:44.900 der anderen Variante, dann hätten Sie, Sie könnten es vereinfachen und 56:44.900 --> 56:46.940 würden dann auf die 1 kommen in dem Fall. 56:46.940 --> 56:50.780 Wenn Sie diese Funktion vereinfachen wollten, würden Sie die einfach 56:50.780 --> 56:52.580 durch die 1 beschreiben. 56:52.740 --> 56:58.080 Aber so als kanonische, disjunktive Normalform gibt es einen solchen 56:58.080 --> 56:58.860 großen Ausdruck. 56:59.280 --> 57:04.380 Das nur als ein Beispiel dafür, wie viele verschiedene Funktionen das 57:04.380 --> 57:04.720 da gibt. 57:04.820 --> 57:09.260 Das ist ein kleines Beispiel, aber auch, wie man solche Funktionen 57:09.260 --> 57:11.640 jeweils durch bool'sche Ausdrücke beschreibt. 57:12.320 --> 57:16.140 Insbesondere, wenn man eben sagt, ich möchte eine spezielle Normalform 57:16.140 --> 57:17.020 dabei einhalten. 57:18.040 --> 57:19.720 Okay, das also zu diesen Funktionen. 57:19.740 --> 57:22.780 Einige davon kennen Sie und die wird man im weiteren auch verwenden. 57:23.320 --> 57:27.020 Ich habe sie hier noch einmal dargestellt, damit sie im PDF-Ausdruck 57:27.020 --> 57:28.060 auch dann vorhanden ist. 57:30.600 --> 57:35.820 Und dann schauen wir uns schon das nächste Thema an, nämlich die 57:35.820 --> 57:37.640 Verknüpfungsbasen. 57:39.240 --> 57:41.420 Vielleicht machen wir an dieser Stelle eine ganz kurze Pause. 57:42.120 --> 57:44.360 Es hat sich ja eingebürgert, es hat mich keiner darauf hingewiesen 57:44.360 --> 57:45.660 heute, dass ich eine Pause machen soll. 57:45.960 --> 57:46.700 Ich mache sie trotzdem. 57:54.440 --> 57:55.140 Jetzt zählt er. 57:55.740 --> 58:01.780 Also, nachdem ich Ihnen jetzt erzählt habe, interessante Erkenntnisse 58:01.780 --> 58:06.260 über die Unterschiede zwischen dem Erfüllbarkeitsproblem für 58:06.260 --> 58:10.260 disjunktive und konjunktive Normalformen, von dem jetzt alle 58:10.260 --> 58:12.560 profitieren, die hier gesessen haben, und die, die heute nicht zur 58:12.560 --> 58:17.020 Vorlesung gekommen sind, müssen sich das selber überlegen, werden wir 58:17.020 --> 58:23.220 jetzt weitermachen und werden uns mit Verknüpfungsbasen beschäftigen. 58:25.660 --> 58:32.260 Also, Verknüpfungsbasen hat damit zu tun, wie kann ich diese 16 58:32.260 --> 58:34.920 verschiedenen Funktionen eigentlich darstellen, wenn ich die 58:34.920 --> 58:38.040 realisieren möchte, wie viele Komponenten brauche ich dafür. 58:39.180 --> 58:47.740 Und wir wissen, wir können jede solche Funktion über Variablen 58:47.740 --> 58:51.620 beschreiben und drei verschiedene Operationen, nämlich Konjunktion, 58:51.840 --> 58:55.000 Disjunktion und Komplement. 58:57.560 --> 59:04.540 Das ist eine Verknüpfungsbasis, weil wir jede Funktion allein mit den 59:04.540 --> 59:06.620 Verknüpfungen aus dieser Menge darstellen können. 59:09.460 --> 59:16.460 Interessant ist, dass man sich sehr einfach überlegen kann, dass ich 59:16.460 --> 59:17.940 nur zwei Operationen brauche. 59:17.940 --> 59:22.780 Nur die Konjunktion und das Komplement oder nur die Disjunktion und 59:22.780 --> 59:23.340 das Komplement. 59:26.440 --> 59:28.640 Und wieso ist das so? 59:29.780 --> 59:33.300 Also, ich habe nur die Konjunktion und das Komplement zur Verfügung 59:33.940 --> 59:40.220 und ich möchte jetzt aber auch gerne A oder B darstellen können. 59:41.220 --> 59:44.960 Die Funktion muss sich ja darstellen können. 59:45.700 --> 59:54.640 Die ist aber gerade gleich A quer und B quer und das Ganze gequert. 59:57.280 --> 01:00:07.180 Das ist nach dem Morganscher Regel Komplement einer Konjunktion, eine 01:00:07.180 --> 01:00:12.540 Disjunktion der komplementierten Elemente und A quer und B quer sind 01:00:12.540 --> 01:00:13.400 jeweils A und B. 01:00:14.460 --> 01:00:19.280 Und Sie sehen, ich habe hier nur mit Konjunktion und Komplement die 01:00:19.280 --> 01:00:20.400 Disjunktion dargestellt. 01:00:20.400 --> 01:00:25.140 Das heißt, ich brauche die Disjunktion nicht als Baustein, als 01:00:25.140 --> 01:00:27.580 Verknüpfung, um jede Funktion darstellen zu können. 01:00:27.680 --> 01:00:31.460 Ich kann alles mit Konjunktion und Komplement machen oder anders ganz 01:00:31.460 --> 01:00:33.980 symmetrisch mit Disjunktion und Komplement. 01:00:34.480 --> 01:00:35.360 Die beiden reichen. 01:00:35.980 --> 01:00:42.560 Das Interessante ist, die Funktion NOR oder auch die Funktion NAND, 01:00:42.560 --> 01:00:46.820 also die Negation der Disjunktion oder die Negation der Konjunktion, 01:00:47.500 --> 01:00:48.940 die reichen alleine schon aus. 01:00:51.080 --> 01:00:56.260 Ich kann also jede dieser 16 Funktionen oder auch wenn Sie mehr 01:00:56.260 --> 01:01:00.660 Variablen haben, entsprechend auch die Funktion von mehr Variablen 01:01:00.660 --> 01:01:06.420 darstellen, indem ich nur eine Verknüpfung nehme, nur das NOR oder nur 01:01:06.420 --> 01:01:06.980 das NAND. 01:01:10.820 --> 01:01:17.660 Und das ist also offensichtlich auch ein interessantes Ergebnis. 01:01:17.820 --> 01:01:19.680 Ich will das aber gar nicht weiter vertiefen. 01:01:19.900 --> 01:01:24.740 Sie können sich sehr leicht überlegen, wie man also mit dem NOR die 01:01:24.740 --> 01:01:27.520 anderen Funktionen tatsächlich darstellen kann. 01:01:29.860 --> 01:01:33.440 Ähnliche Anwendung von Regeln, wie ich das gerade eben gemacht habe. 01:01:33.440 --> 01:01:38.260 Und daraus folgt eben, dass eine einzelne Verknüpfung zur Darstellung 01:01:38.260 --> 01:01:40.800 aller zweistelligen Schaltfunktionen ausreichend ist. 01:01:41.500 --> 01:01:46.420 Das heißt, Sie bräuchten im Prinzip nur einen Baustein, bei dem Sie 01:01:46.420 --> 01:01:50.760 hier zwei Eingänge haben, dort dann zum Beispiel die NOR-Funktion 01:01:50.760 --> 01:01:53.400 hinschreiben und da kommt ein Ausgang raus. 01:01:54.320 --> 01:01:57.880 Und Sie könnten mit solchen Bausteinen jede Schaltung darstellen. 01:01:59.600 --> 01:02:05.720 Also wäre eine Art, wie man Schaltungen bauen kann, indem man einen 01:02:05.720 --> 01:02:09.220 einzigen Baustein realisiert, von dem ganz viele hat und die 01:02:09.220 --> 01:02:10.180 entsprechend verknüpft. 01:02:11.040 --> 01:02:16.320 Sie brauchen aber eventuell dafür sehr viele Verknüpfungsglieder. 01:02:16.820 --> 01:02:20.740 Das heißt, der Aufwand für das Aufbauen einer Schaltung wäre eventuell 01:02:20.740 --> 01:02:21.260 recht hoch. 01:02:21.260 --> 01:02:25.560 Sie hätten aber eine sehr homogene Struktur. 01:02:25.820 --> 01:02:28.020 Alle Bauelemente wären identisch. 01:02:28.480 --> 01:02:30.460 Sie müssten nur etwas kompliziert verknüpft werden. 01:02:31.760 --> 01:02:34.680 Also das ganz kurz zu diesen Verknüpfungsbasen. 01:02:35.400 --> 01:02:39.700 Und jetzt kommen wir zu den grundlegenden Schaltungen, die wir 01:02:39.700 --> 01:02:44.580 betrachten, wenn wir Schaltungen aufbauen. 01:02:44.580 --> 01:02:50.840 Und da werden wir jetzt wieder die drei verschiedenen Schaltungen oder 01:02:50.840 --> 01:02:55.080 Verknüpfungen, Konjunktion, Disjunktion und Komplement betrachten. 01:02:56.140 --> 01:03:08.040 Und zwar betrachten wir hier diese Schaltungen. 01:03:08.040 --> 01:03:16.480 Erstmal das Nicht-Gatter, das Negationsglied. 01:03:17.080 --> 01:03:22.040 Und das wird einfach dargestellt in einer symbolischen Form, sodass 01:03:22.040 --> 01:03:23.980 wir hier einen Eingang haben. 01:03:24.560 --> 01:03:28.920 Und dahinter steht so ein Kringel, der deutet an, dass wir den Wert 01:03:28.920 --> 01:03:29.800 komplementieren. 01:03:30.340 --> 01:03:32.280 Also das ist das Zeichen für ein Komplement. 01:03:32.280 --> 01:03:35.300 Oder die Eins kann man auch weglassen, da steht dann nur dieser 01:03:35.300 --> 01:03:38.160 Kringel drin, der soll andeuten, hier komplementieren wir den Wert. 01:03:39.820 --> 01:03:40.380 Negationsglied. 01:03:40.440 --> 01:03:44.480 Das war vorher diese Ruhe-Kontakt-Schaltung bei der Schaltalgebra. 01:03:45.440 --> 01:03:49.680 Dann können wir ein Oder-Gatter definieren, ein Disjunktionsglied. 01:03:50.320 --> 01:03:52.520 Zwei Eingänge, eine Disjunktion. 01:03:52.520 --> 01:03:58.300 Und größer gleich eins soll bedeuten, hier kommt eine Eins raus, wenn 01:03:58.300 --> 01:04:01.460 mindestens ein Eingang den Wert eins hat. 01:04:01.560 --> 01:04:02.500 Größer gleich eins. 01:04:03.240 --> 01:04:09.500 Die Disjunktion und die Konjunktion heißt eben beide, hier steht das 01:04:09.500 --> 01:04:14.500 Und -Element drin, das Und-Zeichen auf eine etwas andere Art und 01:04:14.500 --> 01:04:14.840 Weise. 01:04:14.840 --> 01:04:18.620 Und das soll gerade jetzt das A und B sein. 01:04:18.780 --> 01:04:22.480 Also wenn beide Elemente eins sind, dann ist auch der Ausgang eins. 01:04:23.560 --> 01:04:26.100 Jetzt sehen Sie hier unterschiedliche Darstellungen. 01:04:26.740 --> 01:04:34.340 Das sind die nach Standard vorgeschriebenen Darstellungen dieser 01:04:34.340 --> 01:04:34.620 Gatter. 01:04:35.740 --> 01:04:39.060 Und dann sehen Sie hier andere Darstellungen, die man früher verwendet 01:04:39.060 --> 01:04:39.280 hat. 01:04:40.280 --> 01:04:43.600 Dazu möchte ich Ihnen eine kleine Begründung schreiben oder 01:04:43.600 --> 01:04:46.180 Motivation, warum das so ist. 01:04:49.180 --> 01:04:52.240 Weil das Ganze interessant ist, wie sich Standards entwickeln. 01:04:53.580 --> 01:04:56.220 Die hier auf der rechten Seite, das waren die, die man früher 01:04:56.220 --> 01:04:56.960 verwendet hat. 01:04:57.580 --> 01:05:03.200 Da hat man Schaltungen gemalt mit einem Stift, mit der Hand, auch mit 01:05:03.200 --> 01:05:06.660 irgendwelchen Schablonen und hat solche Elemente gemalt. 01:05:06.660 --> 01:05:11.800 Und da war eben die Negation dieses Symbol, der Disjunktion hatte 01:05:11.800 --> 01:05:13.880 diese Form, Konjunktion hatte diese Form. 01:05:14.860 --> 01:05:18.780 Und Sie haben an der Form grafisch schon sehen können, welche 01:05:18.780 --> 01:05:22.760 Bedeutung dieses Symbol hat. 01:05:23.240 --> 01:05:26.700 Wenn Sie sich das hier anschauen, da haben Sie überall rechteckige 01:05:26.700 --> 01:05:28.720 Kästen, solche Quadrate. 01:05:29.140 --> 01:05:32.200 Und da drin steht irgendetwas und das müssen Sie anschauen, um zu 01:05:32.200 --> 01:05:36.060 sehen, welche Bedeutung dieser Kasten hat. 01:05:36.880 --> 01:05:38.320 Warum macht man sowas? 01:05:38.420 --> 01:05:40.500 Warum verändert man einen etablierten Standard? 01:05:42.140 --> 01:05:47.500 Weil man etwa um diese Zeit oder schon etwas davor festgestellt hat, 01:05:47.560 --> 01:05:54.540 es gibt Geräte, bei denen man in der Lage ist, mit einem Stift zu 01:05:54.540 --> 01:05:56.580 schreiben auf einem Blatt Papier. 01:05:57.280 --> 01:06:04.340 Man konnte dieses Gerät in zwei Richtungen bewegen, rechts nach links 01:06:04.340 --> 01:06:05.940 oder oben nach unten. 01:06:08.280 --> 01:06:12.500 Aber man konnte keine Kreisbögen malen. 01:06:13.320 --> 01:06:19.560 Man konnte Rechtecke malen, man konnte Symbole schreiben, also eine 01:06:19.560 --> 01:06:21.180 kleine Null oder irgend so etwas. 01:06:22.080 --> 01:06:28.580 Jede Zahl konnte man damit schreiben, jedes Zeichen konnte man damit 01:06:28.580 --> 01:06:33.260 schreiben, man konnte aber nicht solche beliebigen Kreisbögen malen. 01:06:34.460 --> 01:06:36.140 Zumindest konnten das nicht alle Geräte. 01:06:36.280 --> 01:06:41.220 Man hat einen Standard gesucht, wie man automatisiert in der Lage ist, 01:06:41.520 --> 01:06:42.660 Schaltungen zu beschreiben. 01:06:43.500 --> 01:06:48.180 Und weil man das auf allen Geräten, die damals technisch verfügbar 01:06:48.180 --> 01:06:53.940 waren, realisieren wollte, musste man sich auf einen Standard einigen, 01:06:54.000 --> 01:06:55.540 der überall realisierbar ist. 01:06:55.620 --> 01:06:59.420 Und das war der, der hier links angegeben ist, mit einfachen Kästen, 01:06:59.860 --> 01:07:04.420 wo man nur in zwei Richtungen etwas bewegen muss und dann noch die 01:07:04.420 --> 01:07:08.740 Notwendigkeit, solche Zeichen zu schreiben. 01:07:08.740 --> 01:07:13.240 Diese Fähigkeit haben die also alle gehabt, aber eben nicht die 01:07:13.240 --> 01:07:15.780 Fähigkeit, solche beliebigen Kästen zu malen. 01:07:15.820 --> 01:07:19.780 Oder solche beliebigen Kreisbögen zu malen, die man hier braucht. 01:07:20.720 --> 01:07:23.860 Deswegen hat sich ein Standard entwickelt, der eigentlich intuitiv gar 01:07:23.860 --> 01:07:28.980 nicht so angenehm ist, weil ich nicht optisch sofort sehe, was die 01:07:28.980 --> 01:07:29.900 Funktion ist. 01:07:30.580 --> 01:07:35.420 Aber es war halt der, der technisch in dem Augenblick sinnvoll war und 01:07:35.420 --> 01:07:39.040 bis heute ist der sinnvoll, obwohl wir heute problemlos beliebige 01:07:39.040 --> 01:07:45.340 Kurven malen könnten, zeichnen könnten, in einer automatisierten Form. 01:07:46.240 --> 01:07:49.500 Trotzdem hat sich dieser Standard bisher gehalten, zumindest bei uns 01:07:49.500 --> 01:07:50.140 in Deutschland. 01:07:51.000 --> 01:07:53.020 Ist ja auch eine DIN, Deutsche Industrienorm. 01:07:53.500 --> 01:07:56.240 Die Amerikaner haben das nicht übernommen. 01:07:56.360 --> 01:07:59.280 Die haben also ihre eigene Art, wie man Schaltungen darstellt. 01:08:00.140 --> 01:08:03.100 Sowas ist natürlich auch ein Problem, wenn die Arten, wie man 01:08:03.100 --> 01:08:05.600 Schaltungen beschreibt oder wie man die darstellt, unterschiedlich 01:08:05.600 --> 01:08:07.520 sind, kann das auch zu Problemen führen. 01:08:09.180 --> 01:08:11.880 Das sind jedenfalls die elementaren Gatter, die wir verwenden. 01:08:13.080 --> 01:08:16.180 Es gibt natürlich weitere sogenannte Gatter, Schalt-Gatter. 01:08:17.640 --> 01:08:20.780 Jetzt kann ich daraus einen NOR-Gatter bauen, indem ich einen ODER 01:08:20.780 --> 01:08:22.860 -Gatter nehme und dahinter einfach einen Kringel male. 01:08:22.860 --> 01:08:27.940 Dann habe ich also diese Pierce-Funktion, die ja ausreichen würde, um 01:08:27.940 --> 01:08:31.000 alle Funktionen darzustellen. 01:08:31.600 --> 01:08:35.500 Ein NAND-Gatter, die Schäffer-Funktion, kann ich so darstellen. 01:08:35.620 --> 01:08:38.500 Und ein XOR-Gatter kann ich auch darstellen. 01:08:39.760 --> 01:08:42.600 Da schreibe ich auf einmal 2k plus 1 rein. 01:08:43.140 --> 01:08:44.580 Warum 2k plus 1? 01:08:44.580 --> 01:08:47.620 Ich hatte gesagt, das ist im Prinzip die Paritätsfunktion. 01:08:47.780 --> 01:08:54.120 Diese hat den Wert 1, wenn die Anzahl der Einsen an den Eingängen 01:08:54.120 --> 01:08:55.220 ungerade ist. 01:08:56.000 --> 01:09:03.700 Wenn ich also nur zwei Elemente habe, dann ist das K in dem Fall 0. 01:09:04.100 --> 01:09:07.820 Dann ist es also 1, wenn einer dieser beiden 1 ist. 01:09:09.000 --> 01:09:13.940 Und wenn ich mehr Eingänge habe, dann steht hier, ich muss eine 01:09:13.940 --> 01:09:15.520 ungerade Zahl von Einsen haben. 01:09:16.280 --> 01:09:24.400 Jetzt kann ich natürlich diese XOR-Funktion auch als Ausdruck 01:09:24.400 --> 01:09:28.120 hinschreiben, indem nur die anderen Operationen auftreten. 01:09:29.160 --> 01:09:31.040 Das XOR ist ja keine elementare Operation. 01:09:32.080 --> 01:09:33.820 Jetzt habe ich einen solchen Ausdruck. 01:09:35.060 --> 01:09:39.360 Und aus dem Ausdruck kann ich jetzt eine Schaltung ableiten. 01:09:40.560 --> 01:09:45.640 Ich muss also zwei Konjunktionen betrachten. 01:09:45.960 --> 01:09:48.160 Das sind die beiden Konjunktionen, die stehen hier. 01:09:48.940 --> 01:09:50.180 Zwei Konjunktionen. 01:09:51.320 --> 01:09:55.120 Der eine Eingang ist negiert, das steht da, und zwar das B. 01:09:55.740 --> 01:09:59.180 Da ist das B negiert, in dem Fall ist das A negiert. 01:10:00.340 --> 01:10:05.080 Und die beiden Ergebnisse dieser Konjunktionen, die muss ich 01:10:05.080 --> 01:10:09.680 disjunktiv zusammenführen und habe dann am Ausgang die XOR-Funktion. 01:10:10.300 --> 01:10:13.400 Und Sie sehen, ich kann also aus dem Ausdruck, aus dem bool'schen 01:10:13.400 --> 01:10:17.900 Ausdruck, der die Funktion beschreibt, direkt die Schaltung 01:10:17.900 --> 01:10:18.260 konstruieren. 01:10:19.680 --> 01:10:22.880 Also wenn ich eine Schaltung konstruieren möchte, werde ich immer 01:10:22.880 --> 01:10:29.020 einen bool'schen Ausdruck verwenden, um die Funktion zu beschreiben. 01:10:30.380 --> 01:10:31.840 Dann baue ich die Schaltung. 01:10:32.320 --> 01:10:34.180 Für Simulationen verwende ich einen BDD. 01:10:36.280 --> 01:10:39.560 Für die Schaltungen verwende ich einen bool'schen Ausdruck. 01:10:40.760 --> 01:10:43.480 Und dieses 2K plus 1, nochmal, hatte ich schon gesagt, 01:10:43.600 --> 01:10:47.180 Paritätsfunktion, ungerade Anzahl von Eingängen soll eine 1 haben. 01:10:49.000 --> 01:10:54.380 Generell können Sie also beliebige Schaltelemente sich überlegen, 01:10:54.480 --> 01:10:55.440 können die aufbauen. 01:10:55.440 --> 01:11:00.680 Das dient halt dazu, um beliebige Schaltungen zu beschreiben, die 01:11:00.680 --> 01:11:01.460 bauen zu können. 01:11:02.140 --> 01:11:06.620 Hier sehen Sie auch eine Darstellung, das wäre also jetzt eine 01:11:06.620 --> 01:11:16.680 Schaltung, bei der Sie 1, 2, 3, 4 NAND-Elemente hätten. 01:11:16.820 --> 01:11:19.720 Sie hätten hier einen Kringel davor, das ist ein UND-Element, Sie 01:11:19.720 --> 01:11:24.220 sehen in einer anderen Art der Beschreibung dargestellt, entsprechend 01:11:24.220 --> 01:11:25.740 mit den Eingängen hier verbunden. 01:11:26.420 --> 01:11:30.100 So ein Bauelement könnte so eine Schaltung dann tatsächlich 01:11:30.100 --> 01:11:31.120 realisieren. 01:11:31.220 --> 01:11:34.060 Das ist das, was uns jetzt interessiert im Folgenden, wie kann ich 01:11:34.060 --> 01:11:35.740 Schaltungen tatsächlich bauen. 01:11:36.720 --> 01:11:44.460 Und damit man damit genauer umgehen kann, liefere ich Ihnen auch noch 01:11:44.460 --> 01:11:45.360 ein Werkzeug. 01:11:46.320 --> 01:11:50.980 Ah, jetzt habe ich hier das falsch gemacht. 01:11:51.800 --> 01:11:53.360 Ich wollte ja gar nicht... 01:11:54.140 --> 01:11:57.240 Ich wollte ja hier nur raufklicken. 01:12:02.120 --> 01:12:04.060 Ich wollte nur hier raufklicken können. 01:12:04.720 --> 01:12:09.820 Jetzt kommt das Werkzeug, was ich zu Anfang mal erwähnt habe, das 01:12:09.820 --> 01:12:10.660 Logiflash. 01:12:11.500 --> 01:12:17.920 Ein Werkzeug, um Schaltungen darzustellen, Schaltungen zu beschreiben. 01:12:18.840 --> 01:12:25.640 Sie haben hier viele Möglichkeiten, solche Schaltungen zu beschreiben 01:12:25.640 --> 01:12:30.100 oder solche Schaltungen zu erzeugen. 01:12:30.620 --> 01:12:32.660 Wie macht man das mit dem Logiflash? 01:12:33.400 --> 01:12:36.240 Entweder lädt man sich das direkt rein. 01:12:36.880 --> 01:12:44.140 Das stand also gerade eben auf der Folie, das ist die Schaltung, die 01:12:44.140 --> 01:12:47.440 den Namen Vorlesung XOR hat. 01:12:48.200 --> 01:12:49.860 Sie sehen, da ist diese Schaltung. 01:12:51.440 --> 01:12:54.340 Das ist eine einfache Art, vorgefertigte Schaltungen zu nehmen. 01:12:55.100 --> 01:12:56.320 Wie entsteht so etwas? 01:12:57.720 --> 01:13:00.540 Ich möchte also irgendwelche Eingänge, die brauche ich. 01:13:00.620 --> 01:13:02.000 Wie kriege ich solche Eingänge dahin? 01:13:02.380 --> 01:13:03.440 Ich gehe auf Button. 01:13:04.620 --> 01:13:09.020 Wenn ich hier vorne dieses Dreieck reingehe, dann sehen Sie, ich habe 01:13:09.020 --> 01:13:11.600 hier verschiedene Möglichkeiten, die ich auswählen kann. 01:13:11.600 --> 01:13:12.880 Ich möchte jetzt einen Button haben. 01:13:13.480 --> 01:13:14.760 Dann klicke ich einfach hier rein. 01:13:15.780 --> 01:13:17.280 Ich muss den auswählen, den Button. 01:13:17.620 --> 01:13:23.160 Dann klicke ich hier rein und habe jetzt hier zwei solche Button 01:13:23.160 --> 01:13:23.600 reingeschrieben. 01:13:24.380 --> 01:13:27.460 Jedes Mal reinklicken, wenn ich das hier ausgewählt habe, erzeugt ein 01:13:27.460 --> 01:13:28.240 solches Symbol. 01:13:29.020 --> 01:13:33.100 Dann brauche ich ein Negationsglied. 01:13:34.560 --> 01:13:36.540 Ein Negationsglied, diese beiden hier. 01:13:36.620 --> 01:13:37.260 Wie bekomme ich die? 01:13:37.360 --> 01:13:38.920 Das ist nicht so einfach zu finden. 01:13:38.920 --> 01:13:45.220 Hier unten unter Miscellaneous sehen Sie, da gibt es einen Logic 01:13:45.220 --> 01:13:47.380 Analyzer oder einen Inverter. 01:13:47.500 --> 01:13:53.160 Ich wähle hier den Inverter aus und habe den jetzt hier. 01:13:53.500 --> 01:13:55.300 Einmal und nochmal. 01:13:59.500 --> 01:14:05.560 Jetzt brauche ich zweimal ein Konjunktionsglied, ein AND. 01:14:05.560 --> 01:14:08.240 Auch da gibt es also unterschiedliche Sachen. 01:14:08.380 --> 01:14:10.500 Ich kann eine unterschiedliche Anzahl von Inputs dafür bekommen. 01:14:11.740 --> 01:14:13.560 Mir reicht es aber in dieser Art und Weise. 01:14:13.940 --> 01:14:16.360 Hier zwei solche UND-Gatter. 01:14:17.060 --> 01:14:21.160 Und ich brauche noch ein ODER-Gatter und ich will noch eine Lampe 01:14:21.160 --> 01:14:21.880 haben am Ende. 01:14:23.760 --> 01:14:24.740 So, jetzt habe ich auch die Lampe. 01:14:25.600 --> 01:14:29.160 Und dann klicke ich das hier oben an. 01:14:29.640 --> 01:14:31.800 Ich möchte jetzt diese irgendwie verbinden. 01:14:32.620 --> 01:14:33.200 Wie mache ich das? 01:14:33.280 --> 01:14:34.780 Erstmal kann ich jetzt hier rauf gehen. 01:14:35.560 --> 01:14:38.340 Wenn ich also das hier oben angeklickt habe, dann kann ich die jetzt 01:14:38.340 --> 01:14:39.740 hier beliebig hin und her bewegen. 01:14:41.620 --> 01:14:48.460 Und jetzt gehe ich hier auf diesen Pin rauf und verbinde den einfach 01:14:48.460 --> 01:14:49.960 mit dem Eingang. 01:14:50.040 --> 01:14:50.680 Schon verbunden. 01:14:51.540 --> 01:14:55.540 Und den zweiten verbinde ich mit dem Eingang. 01:14:55.640 --> 01:14:56.340 Auch schon verbunden. 01:14:56.340 --> 01:15:03.060 Dann muss ich ja offensichtlich den verbinden mit dem Eingang. 01:15:03.740 --> 01:15:06.900 Und den hier habe ich mit dem verbunden. 01:15:07.500 --> 01:15:09.600 Auf einmal ist der gelb und nicht schwarz. 01:15:10.260 --> 01:15:11.240 Warum ist der gelb? 01:15:12.480 --> 01:15:14.700 Der ist gelb, weil das sofort interpretiert wird. 01:15:15.500 --> 01:15:19.380 Es kommt hier etwas rein, da ist kein Wert dran, das ist 0. 01:15:20.240 --> 01:15:22.280 Die Negation macht daraus eine 1. 01:15:22.500 --> 01:15:25.460 Das heißt, die gelbe Leitung deutet an. 01:15:26.340 --> 01:15:28.920 Die ist jetzt aus der 0 eine 1 geworden. 01:15:29.800 --> 01:15:34.680 Der zweite Eingang, der hier reinkommt, der kommt direkt aus diesem 01:15:34.680 --> 01:15:35.520 zweiten hier. 01:15:35.680 --> 01:15:37.160 Da muss ich also hier irgendwie rauf. 01:15:37.640 --> 01:15:47.660 Da kann ich mit Steuerung hier rauf gehen und kann jetzt zum Beispiel 01:15:47.660 --> 01:15:49.680 die beiden verbinden miteinander. 01:15:49.680 --> 01:15:58.800 Und ich kann jetzt genauso hier rauf gehen und gehe bis hier hin und 01:15:58.800 --> 01:16:02.100 laufe jetzt hier weiter rüber und habe die verbunden. 01:16:02.340 --> 01:16:06.580 Jetzt verbinde ich noch kurz diese beiden. 01:16:09.740 --> 01:16:10.500 So. 01:16:10.500 --> 01:16:12.300 Verbinde die noch miteinander. 01:16:12.900 --> 01:16:13.940 Da muss ich richtig ran. 01:16:14.660 --> 01:16:15.200 So. 01:16:16.580 --> 01:16:23.260 So habe ich ganz schnell gezeigt, wie ich eine Schaltung aufbauen kann 01:16:23.260 --> 01:16:24.820 mit diesem Werkzeug. 01:16:25.540 --> 01:16:29.860 Sie können hier sehr komplexe Schaltungen aufbauen und auch 01:16:29.860 --> 01:16:30.130 simulieren. 01:16:31.620 --> 01:16:35.340 Jetzt kann ich also zum Beispiel sagen, ich setze das hier auf 1. 01:16:36.060 --> 01:16:39.100 Und Sie sehen, wenn ich das auf 1 setze, dann sind die Leitungen hier 01:16:39.100 --> 01:16:42.180 vorne alle gelb, weil ich jetzt hier eine 1 drin habe. 01:16:42.180 --> 01:16:45.860 Da oben ist eine 0, noch eine 0, dann bleibt es hier eine 0. 01:16:46.040 --> 01:16:51.740 Aber über diesen Weg habe ich jetzt aus dem negierten B und aus der 1 01:16:51.740 --> 01:16:53.820 beide Eingänge auf 1 gesetzt. 01:16:53.940 --> 01:16:56.380 Hier kommt eine 1 raus und deswegen leuchtet die Lampe. 01:16:57.000 --> 01:17:00.040 Wenn ich das B auch auf 1 setze, geht die Lampe wieder aus. 01:17:00.760 --> 01:17:04.980 Und wenn ich das A auf 0 setze, dann ist die Lampe wieder an. 01:17:05.620 --> 01:17:07.280 Und das ist hier natürlich genau das Gleiche. 01:17:08.660 --> 01:17:12.460 So können Sie also eine Schaltung sofort simulieren und sehen, welche 01:17:12.460 --> 01:17:15.660 Werte dann jeweils an den Ausgängen dort rauskommen. 01:17:15.860 --> 01:17:17.460 Das also zu diesem Werkzeug Logiflash. 01:17:18.360 --> 01:17:23.420 Ein sehr schönes Werkzeug, erst entstanden aus einem Förderprojekt im 01:17:23.420 --> 01:17:26.380 Rahmen des Förderprogramms Neue Medien in der Bildung. 01:17:26.480 --> 01:17:29.940 Vor einigen Jahren hatten wir die Wissenswerkstatt Rechensysteme und 01:17:29.940 --> 01:17:32.800 eine Gruppe hat dieses Werkzeug entwickelt, das jetzt an vielen 01:17:32.800 --> 01:17:36.660 Stellen in Deutschland in solchen Vorlesungen wie dieser verwendet 01:17:36.660 --> 01:17:36.880 wird. 01:17:37.940 --> 01:17:43.660 Okay, das also zu diesem Werkzeug und das ist die XOR-Funktion. 01:17:44.140 --> 01:17:47.180 Jetzt kann ich natürlich noch weitere Gatter definieren. 01:17:47.280 --> 01:17:50.440 Ich kann mehrstellige Gatter definieren, indem ich einfach 01:17:50.440 --> 01:17:53.000 entsprechend das Symbol dort lasse. 01:17:53.280 --> 01:17:56.960 Größer gleich 1, das heißt nach wie vor mindestens ein Eingang muss 1 01:17:56.960 --> 01:17:57.140 sein. 01:17:57.220 --> 01:17:59.180 Dann habe ich hier die Dissunktion. 01:18:02.320 --> 01:18:07.300 Oder eben wenn ich das Unzeichen reinschreibe, hätte ich entsprechende 01:18:07.300 --> 01:18:07.880 Konjunktion. 01:18:09.700 --> 01:18:10.900 Das wollte ich jetzt nicht. 01:18:11.480 --> 01:18:15.520 Und das kann ich genauso gut dann mit entsprechenden Schaltungen in 01:18:15.520 --> 01:18:16.440 dem Logiflash zeichnen. 01:18:17.240 --> 01:18:21.200 Ich kann auch eine solche Schaltung, wenn ich jetzt sage, ich habe 01:18:21.200 --> 01:18:31.340 jetzt 4 Eingänge, ich kann natürlich das auch mit 3 jeweils größer 01:18:31.340 --> 01:18:34.260 gleich 1 hier reinschreiben, hier auch größer gleich 1. 01:18:34.560 --> 01:18:38.320 Dann habe ich das gleiche gebaut, nur mit zweistelligen Gattern, aber 01:18:38.320 --> 01:18:42.400 eben dann mit 3 zweistelligen Dissonktionen kann ich dann eben eine 01:18:42.400 --> 01:18:44.340 vierstellige Dissonktion realisieren. 01:18:45.540 --> 01:18:50.340 Auf diese Art und Weise baut man eben dann Schaltnetze auf aus solchen 01:18:50.340 --> 01:18:51.160 Schaltgattern. 01:18:51.160 --> 01:18:54.980 Und das ist das Thema, was wir am Montag betrachten werden, wie ich 01:18:54.980 --> 01:18:59.380 Schaltnetze aufbaue, die dann etwas größer werden und dann 01:18:59.380 --> 01:19:02.220 aufwändigere Funktionen tatsächlich realisieren können. 01:19:02.640 --> 01:19:03.540 Okay, das war es für heute. 01:19:03.700 --> 01:19:04.900 Vielen Dank für die Aufmerksamkeit. 01:19:05.300 --> 01:19:06.360 Wir sehen uns am Montag wieder.