WEBVTT

00:10.360 --> 00:15.980
So, ja, hallo, ich begrüße euch herzlich zu dieser Vorlesung in diesem

00:15.980 --> 00:17.800
super klimatisierten Hörsaal.

00:19.020 --> 00:22.580
Ja, da draußen ist es extrem heiß, dagegen hier kann man sich

00:22.580 --> 00:26.580
entspannen und wir machen weiter mit dem Stoff.

00:26.720 --> 00:30.100
Das letzte Mal hatten wir das erste tabellarische Verfahren zur

00:30.100 --> 00:32.280
Minimierung von Schaltfunktionen kennengelernt.

00:32.280 --> 00:36.040
Das war das Kwan-McCluskey-Verfahren und wir haben gesehen, dass der

00:36.040 --> 00:40.240
Ausgangspunkt bei diesem Verfahren sind zunächst mal die Anstellen

00:40.240 --> 00:40.560
bzw.

00:41.060 --> 00:42.620
die Nullstellen einer Funktion.

00:43.800 --> 00:47.800
Und ich habe es auch betont das letzte Mal, dass alle diese Verfahren

00:47.800 --> 00:52.740
darauf basieren, dass man zwei Termine, zum Beispiel Min-Termine, wenn

00:52.740 --> 00:56.640
ich die disjunktive Minimalform bestimme, sucht, die sich in einer

00:56.640 --> 01:00.020
Variable unterscheiden oder zwei Produktterme, die sich in einer

01:00.020 --> 01:04.220
Variable unterscheiden und dann diese Produktterme zu einem kürzeren

01:04.220 --> 01:08.500
Term zusammenfasst, sprich zu einem größeren Block im KV-Diagramm.

01:09.840 --> 01:13.780
Und heute wollen wir ein weiteres Tabellarisches Verfahren

01:13.780 --> 01:16.920
kennenlernen für die Minimierung von Schaltfunktionen.

01:16.920 --> 01:19.560
Das ist das sogenannte Konsensusverfahren.

01:20.520 --> 01:24.300
Und der Ausgangspunkt hier von diesem Verfahren ist nicht jetzt die

01:24.300 --> 01:27.640
Darstellung der Funktion in der Funktionstabelle, also nicht die Min

01:27.640 --> 01:31.520
-Termi oder die Max-Termi wie bei dem Kwan-McCluskey, sondern der

01:31.520 --> 01:35.880
Ausgangspunkt ist die Darstellung der Funktion im Würfelkalkül.

01:35.880 --> 01:42.520
Das heißt, wir haben ja gesehen, dass wir Produktterme einer Funktion

01:42.520 --> 01:47.220
mithilfe von dieser Würfeldarstellung repräsentieren können.

01:47.920 --> 01:52.240
Das heißt, ein Produkt einer Funktion, ein Produktterm einer Funktion

01:52.240 --> 02:00.540
lässt sich beschreiben durch einen Würfel, wo praktisch für die

02:00.540 --> 02:05.180
Literali, die in diesem Produktterm bejaht auftauchen, wir eine Eins

02:05.180 --> 02:09.140
haben, die negierten Literali eine Null haben und solche Variablen,

02:09.700 --> 02:12.980
die im Produktterm gar nicht auftauchen, haben wir ein Don't-Care.

02:13.580 --> 02:20.540
Das heißt, für das Produktterm, wie wir wissen, x2, x3, x5 und x6

02:20.540 --> 02:25.120
können wir schreiben, wenn der x1 hier nicht auftaucht, können wir

02:25.120 --> 02:31.360
schreiben Don't-Care 1 0, weil x2 nicht negiert auftaucht, x3 negiert

02:31.360 --> 02:36.480
auftaucht, x4 taucht nicht auf und dann x5 negiert und x6 nicht

02:36.480 --> 02:36.840
negiert.

02:36.940 --> 02:40.200
Das kennen wir alles, das haben wir schon kennengelernt als eine

02:40.200 --> 02:43.180
Möglichkeit zur Darstellung von Schaltfunktionen.

02:43.180 --> 02:47.480
Und das Ganze lässt sich natürlich veranschaulichen im

02:47.480 --> 02:48.760
dreidimensionalen Fall.

02:48.900 --> 02:52.940
Das heißt, wenn wir Funktionen von drei Eingangsvariablen haben, dann

02:52.940 --> 02:56.060
können wir diese Würfeldarstellung auch im dreidimensionalen

02:56.060 --> 02:56.860
visualisieren.

02:57.820 --> 03:02.280
Wenn die Ecken hier sind eigentlich dann die Mintermi der Funktion,

03:02.400 --> 03:06.320
wenn die Funktion dort eine 1 hat, den Funktionswert 1 hat.

03:06.320 --> 03:12.820
Und wir sehen hier, dass zwei Ecken von diesem Würfel hier über eine

03:12.820 --> 03:14.740
Kante miteinander verbunden werden.

03:15.020 --> 03:18.480
Und man sieht hier, bei diesen zwei Ecken gibt es eine Variable, die

03:18.480 --> 03:20.220
komplementär belegt ist.

03:20.860 --> 03:24.900
Das heißt, wenn das hier jetzt x1, x2, x3 wäre hier für die blaue

03:24.900 --> 03:25.360
Kante.

03:25.360 --> 03:35.840
Also wenn wir die Reihenfolge hier x1, x2, x3 zugrunde legen, dann

03:35.840 --> 03:41.180
wäre hier, wie man sieht, die Variable x2 in dieser Ecke und in dieser

03:41.180 --> 03:44.300
Ecke, die werden jetzt komplementär belegt.

03:44.300 --> 03:49.360
Können wir zusammenfassen über diese Kante hier von dem Würfel zu

03:49.360 --> 03:52.440
einem Produktterm, der kurzer ist.

03:52.660 --> 03:57.720
Und dieses Produktterm wäre dann hier, also 0.k0, das wären natürlich

03:57.720 --> 04:01.520
dann jetzt x1 quer, x3 quer.

04:02.280 --> 04:10.960
Während wir hier natürlich x1 quer, x2, x3 quer und hier x1 quer, x2

04:10.960 --> 04:12.960
quer und x3 quer.

04:12.960 --> 04:16.820
Ja, das kennen wir alles und natürlich solche Kanten können wir

04:16.820 --> 04:19.380
nochmal zusammenfassen zu Flächen und so weiter und so fort.

04:20.260 --> 04:24.700
Und wir haben dort einige Definitionen eingeführt.

04:25.860 --> 04:36.640
Das Konsensusverfahren nutzt diese Darstellung von Funktionen für die

04:36.640 --> 04:37.200
Minimierung.

04:37.200 --> 04:41.260
Und das Prinzip ist hier auch nochmal angegeben.

04:41.780 --> 04:46.280
Wenn zwei Minterme einer Funktion einen größeren Unterraum aufspannen,

04:46.860 --> 04:51.260
dann kann dieser Unterraum als Würfel dargestellt werden.

04:51.500 --> 04:56.100
Also zum Beispiel Minterm 7 und Minterm 5 können hier als 1, dort quer

04:56.100 --> 04:57.340
1 dargestellt werden.

04:58.080 --> 05:01.120
Und wir haben dort einige Definitionen eingeführt, zum Beispiel, wann

05:01.120 --> 05:03.280
ein Würfel einen anderen Würfel überdeckt.

05:03.280 --> 05:07.560
Ja, das heißt hier in dem Beispiel, die Folien kennen wir, deshalb

05:07.560 --> 05:09.660
gehe ich auch so schnell drüber.

05:10.020 --> 05:14.520
Das heißt hier zum Beispiel Würfel A enthält B, weil da sieht man hier

05:14.520 --> 05:17.480
diese don't cares, die sind ja grösser als eine 0.

05:17.680 --> 05:20.720
Also dort kann sowohl eine 0 als auch eine 1 sein.

05:21.320 --> 05:30.340
Das heißt hier Würfel A ist natürlich 1, 0, 0 und 1, 0, 1 und 1, 1, 0

05:30.340 --> 05:31.660
und 1, 1, 1.

05:31.660 --> 05:36.240
Alle diese Belegungen sind durch Würfel A überdeckt.

05:37.480 --> 05:42.920
Und hier haben wir nur eine von denen, und zwar Würfel B ist 1, 0, 0.

05:43.100 --> 05:46.400
Das heißt Würfel B ist in A enthalten, bzw.

05:46.660 --> 05:47.500
A enthält B.

05:50.370 --> 05:58.710
So, und wir haben auch die Operation Schnitt zweier Würfel definiert.

05:58.710 --> 06:03.110
Das heißt, wenn wir A und B haben oder hier die Beispiele, dann sehen

06:03.110 --> 06:07.150
wir, dass die Variablen, die gleich sind, der Schnitt ist gleich.

06:07.510 --> 06:14.330
Und die Variablen, wo wir einmal hier A1 1 und B1 don't care, dann

06:14.330 --> 06:17.710
haben wir eine 1, don't care und 1 haben wir eine 1.

06:18.890 --> 06:22.690
Und man sieht hier auch 0 und don't care ist auch eine 0, don't care

06:22.690 --> 06:24.990
und don't care ist don't care, 0 und 0 ist 0.

06:24.990 --> 06:28.770
Und wir haben gesehen, dass die Schnittmenge nicht existiert, wenn

06:28.770 --> 06:31.770
zwei Würfel in einer Variable komplementär belegt sind.

06:32.790 --> 06:36.550
Das heißt, hier sehen wir, dass zum Beispiel die dritte Variable hier

06:36.550 --> 06:42.310
als 1 im Würfel A und 0 im Würfel B ist.

06:42.530 --> 06:47.470
Und deshalb existiert in dem Fall die Schnittmenge nicht von den zwei

06:47.470 --> 06:47.870
Würfeln.

06:47.870 --> 06:53.730
Die sind zwei disjunkte Würfel, da gibt es keine gemeinsame Menge

06:53.730 --> 06:54.230
dazwischen.

06:55.010 --> 06:58.490
Und das ist eigentlich der Knackpunkt für das Konsensusverfahren, wie

06:58.490 --> 06:59.270
wir sehen werden.

06:59.570 --> 07:03.530
Also wir werden beim Konsensusverfahren gleich sehen, dass wir genau

07:03.530 --> 07:05.950
daraus hier etwas machen.

07:06.170 --> 07:09.670
Und zwar, das sind zwei Komponenten im Würfel, die komplementär belegt

07:09.670 --> 07:15.210
sind, die man eventuell, wenn wir an Quine-McCluskey oder KV-Diagramm

07:15.210 --> 07:20.450
denken, diese zwei komplementär belegten Variablen oder zwei

07:20.450 --> 07:24.310
komplementär belegten Literalen zu einem don't care vielleicht

07:24.310 --> 07:24.750
verfügt.

07:24.890 --> 07:28.670
Das ist, was man hier nochmal sich vereinschaulichen kann.

07:29.010 --> 07:33.730
Also zum Beispiel, wenn wir jetzt eine Funktion hätten mit den Min

07:33.730 --> 07:38.390
-Termen, wie hier eingegeben, da können wir sehen, anhand von dem, was

07:38.390 --> 07:41.050
wir bis jetzt kennengelernt haben, wenn wir jetzt eine disjunktive

07:41.050 --> 07:45.370
Form der Funktion eingeben wollen, dann sehen wir, dass wir hier

07:45.370 --> 07:50.930
mehrere Prim-Implikanten der Funktion haben.

07:51.190 --> 07:55.870
Also zum Beispiel, wir haben AC-Quer und wir haben auf der anderen

07:55.870 --> 07:57.450
Seite natürlich BC.

07:58.210 --> 08:03.990
Und mit AC-Quer und BC können wir alle einstellende Funktionen

08:03.990 --> 08:05.330
überdecken, die wir sehen.

08:06.170 --> 08:09.890
Aber dieser Ausdruck, da kann man natürlich das auch nachweisen,

08:10.010 --> 08:15.310
schaltalgebraisch, ist gleich mit AC-Quer oder BC oder AB.

08:16.250 --> 08:20.350
Das heißt, dieser Gruni-Prim-Implikant, der entbehrlich ist natürlich,

08:20.610 --> 08:24.990
ändert nichts an dieser Gleichung, die wir jetzt hier aufgeschrieben

08:24.990 --> 08:25.230
haben.

08:25.230 --> 08:29.270
Also beide bulgische Ausdrücke sind Ausdrücke, mit denen man diese

08:29.270 --> 08:30.130
Funktion beschreibt.

08:30.990 --> 08:38.350
Und dieser Term AB nennt man jetzt den Konsensus-Term zu den Termen AC

08:38.350 --> 08:39.730
-Quer und BC.

08:40.630 --> 08:45.910
Und man sieht hier, dass in diesen zwei Termen die Variable C auf der

08:45.910 --> 08:50.490
einen Seite nicht negiert hier auftaucht und auf der anderen Seite und

08:50.490 --> 08:54.450
hier in dem einen Term negiert und in dem anderen Term nicht negiert

08:54.450 --> 08:55.070
auftaucht.

08:55.830 --> 09:02.210
Und der Term, der entsteht, wenn man so will, ist nichts anderes als

09:02.210 --> 09:06.790
das Produkt der Koeffizienten dieser komplementär belegten Variable.

09:07.450 --> 09:12.130
Der Koeffizient von C ist B und der Koeffizient von C-Quer ist A.

09:12.130 --> 09:16.590
Und der Konsensus-Term ist nichts anderes als A mal B oder A

09:16.590 --> 09:18.190
konjunktiv verknüpft mit B.

09:19.250 --> 09:23.810
So, das heißt, man kann das Ganze ein bisschen hier nochmal

09:23.810 --> 09:25.590
allgemeiner eingeben.

09:25.910 --> 09:30.010
Das Konsensus-Verfahren kann als eine Erweiterung von Koin-McCluskey.

09:30.110 --> 09:32.790
Wir werden gleich auch das nochmal genauer sehen.

09:33.590 --> 09:38.770
Und es gelten in der bulgen Algebra die sogenannten Konsensus-Regel.

09:38.770 --> 09:44.310
Das heißt, wenn ich hier eine Variable x, die einmal nicht negiert und

09:44.310 --> 09:48.370
einmal negiert in einem Ausdruck auftaucht und ich habe zwei beliebige

09:48.370 --> 09:56.310
Funktionen u und w, dann kann ich immer nachweisen oder ich kann

09:56.310 --> 10:03.230
beweisen und zeigen, dass x u oder x-Quer w ist gleich x u oder x-Quer

10:03.230 --> 10:04.690
w oder u w.

10:07.130 --> 10:12.610
Unten ist natürlich die duale Aussage dazu, also diese Konsensus-Regel

10:12.610 --> 10:16.710
in konjunktiver Form, wo ich auch eine Variable x habe, zwei

10:16.710 --> 10:24.910
Funktionen w und u und x oder w und x-Quer oder u ist das gleiche hier

10:24.910 --> 10:27.130
nochmal mit der Ergänzung u oder w.

10:27.130 --> 10:32.270
So, das heißt, wenn wir jetzt zurück mal blicken hier, das ist

10:32.270 --> 10:35.690
tatsächlich die Situation, die wir hier im KV-Diagramm haben.

10:35.890 --> 10:40.210
Das ist dieser entbehrliche Bremen-Implikant, den wir in diesem

10:40.210 --> 10:42.030
Beispiel haben.

10:42.870 --> 10:47.910
Jetzt kann man natürlich diese Regel auch bzw.

10:48.290 --> 10:49.810
zunächst mal zu Schreibweise.

10:49.810 --> 10:56.390
Man nennt das, also u und w nennt man jetzt den Konsensus-Term zu u x

10:56.390 --> 10:59.410
und w x-Quer bzw.

11:00.150 --> 11:05.110
u oder w ist der Konsensus-Term zu x oder w und x-Quer oder w.

11:05.830 --> 11:12.250
Und man schreibt, dass der Konsensus-Term u w ist gleich x u und dann

11:12.250 --> 11:16.250
mit diesem Zeichen Konsensus und dann ein Strich hier mit x-Quer w

11:16.250 --> 11:16.770
bzw.

11:17.030 --> 11:18.350
die duale Aussage dazu.

11:18.350 --> 11:22.890
Das heißt in unserem Beispiel vorher wäre unser Konsensus-Term nichts

11:22.890 --> 11:23.950
anderes als a b.

11:24.950 --> 11:27.910
Und diese Aussage, die kann man natürlich beweisen.

11:28.710 --> 11:33.750
Das heißt ganz allgemein, wir wollen beweisen, dass x u oder x-Quer w

11:33.750 --> 11:36.490
ist gleich x u oder x-Quer w oder u w.

11:37.460 --> 11:44.210
Und wenn wir jetzt zum Beispiel das Absorptionsgesetz mal hier an

11:44.210 --> 11:46.890
unser Absorptionsgesetz nachdenken,

11:54.340 --> 11:58.640
dann kann ich eigentlich für x, für die Variable x, ich kann

11:58.640 --> 12:09.260
schreiben, das ist x und x oder w und für x-Quer kann ich schreiben,

12:09.480 --> 12:13.800
das ist natürlich x-Quer und x-Quer oder u.

12:14.700 --> 12:20.900
Und jetzt setzen wir ein hier, also x u oder x-Quer w.

12:20.900 --> 12:28.520
Wir setzen für x, x und x oder w und das Ganze mit u.

12:29.780 --> 12:36.120
Oder x-Quer setzen wir für x-Quer, x-Quer und x-Quer oder u und das

12:36.120 --> 12:37.160
Ganze mit w.

12:38.340 --> 12:42.600
Und jetzt multiplizieren wir und natürlich hier Edempotenzgesetz.

12:42.920 --> 12:55.160
Also x x u ist x u oder x w u oder x-Quer w, also x-Quer x-Quer w, x x

12:55.160 --> 12:59.580
-Quer w oder x-Quer u w.

13:00.360 --> 13:06.620
So, wir sind unserem Ziel ein Stückchen näher angekommen, das heißt x

13:06.620 --> 13:09.680
u oder x-Quer w.

13:11.280 --> 13:16.700
Oder man sieht hier, wir haben, ich klammere mal, ein paar mal

13:16.700 --> 13:21.800
Kommutativgesetz und dann Distributivgesetz hier einsetzen, x oder x

13:21.800 --> 13:26.220
-Quer und wir wissen x oder x-Quer ist nichts anderes als 1.

13:26.420 --> 13:37.120
Das heißt, das ist x u oder x-Quer w oder u w und das ist, was wir

13:37.120 --> 13:38.360
beweisen wollten.

13:38.680 --> 13:44.100
Ja, das heißt x u oder x-Quer w ist nichts anderes als x u oder x-Quer

13:44.100 --> 13:45.560
w oder u w.

13:45.560 --> 13:50.220
Und natürlich der Beweis für die duale Aussage dazu erfolgt analog.

13:50.680 --> 13:54.680
Wir gehen hin und wir drehen alle Variablen, wie wir das wissen.

13:56.960 --> 14:01.060
Disjunktion, Konjunktion, negierte Variablen bleiben, wie sie sind und

14:01.060 --> 14:04.840
dann bekommen wir auch den Beweis für die duale Aussage dazu.

14:05.620 --> 14:08.800
Genau, das ist hier ein bisschen sauberer aufgeschrieben, aber genauso

14:08.800 --> 14:11.200
korrekt wie auf der Folie davor.

14:11.200 --> 14:14.160
So, das heißt, was bedeutet das?

14:14.280 --> 14:18.000
Das heißt, wir müssen jetzt hier anhand von dieser neuen Regel, die

14:18.000 --> 14:21.860
wir jetzt kennengelernt haben in der Bulschen Algebra, schauen, wie

14:21.860 --> 14:24.360
wir tatsächlich Bulsche Funktionen minimieren.

14:25.200 --> 14:28.900
So, das heißt zunächst mal die Schaltfunktionen und die

14:28.900 --> 14:32.660
Konsensusthermie, die müssen wir durch Würfel darstellen.

14:33.470 --> 14:39.280
Und wenn wir hier zwei Würfel haben, C1 und C2, dann gilt natürlich,

14:39.560 --> 14:49.240
dass der Konsensuswürfel aus den zwei die leere Menge ist.

14:49.540 --> 14:51.660
Ja, also es existiert kein Konsensuswürfel.

14:53.080 --> 14:55.770
Dann haben wir die folgende Situation.

14:57.330 --> 15:00.030
Hat jemand den Fehler entdeckt auf der Folie?

15:01.290 --> 15:04.350
Ja, deshalb hat es vielleicht keiner in den letzten 15 Jahren auch

15:04.350 --> 15:04.770
entdeckt.

15:05.190 --> 15:07.590
Aber vielleicht irre ich mich heute aufgrund der Hitze.

15:09.290 --> 15:14.870
So, also die Folie sagt, es seien zwei Würfel C1 und C2 gegeben und es

15:14.870 --> 15:21.570
gelte C1 Konsensuswürfel Bildung mit C2 ist ungleich die leere Menge.

15:21.570 --> 15:22.890
Das ist die Hitze.

15:23.950 --> 15:25.270
Ungleich die leere Menge.

15:25.410 --> 15:26.590
Ich dachte die leere Menge.

15:27.270 --> 15:32.510
Dann heißt diese Konsensuswürfel oder diese Operation oder das

15:32.510 --> 15:34.010
Ergebnis Konsensuswürfel.

15:34.370 --> 15:35.290
Was bedeutet das?

15:35.410 --> 15:39.230
Das bedeutet vergisst das, was ich gerade... vergisst meine

15:39.230 --> 15:39.910
Verwirrung.

15:40.890 --> 15:46.470
Das heißt, wir haben hier die zwei Produktthermie A quer C oder A C

15:46.470 --> 15:46.770
quer.

15:46.770 --> 15:52.570
Wir wissen im Würfelkalkül mit der Reihenfolge der Variablen A, B, C.

15:53.810 --> 15:55.590
Die Reihenfolge A, B, C.

15:57.710 --> 16:00.870
Können wir das darstellen als 1, dort quer 0.

16:01.690 --> 16:03.810
Und der zweite Würfel ist B, C.

16:04.110 --> 16:05.890
Das heißt dort quer 1, 1.

16:06.430 --> 16:10.350
Und unser Konsensuswürfel, was wir vorher herausgefunden haben, noch

16:10.350 --> 16:13.050
im KV-Diagramm, war nicht anderes als A, B.

16:13.050 --> 16:17.150
Also die Koeffizienten von dieser Variable, die in den zwei Termen

16:17.150 --> 16:18.570
komplementär belegt ist.

16:19.070 --> 16:22.350
Und man sieht hier, dass dieser Konsensuswürfel ist nichts anderes als

16:22.350 --> 16:23.810
1, 1, dort quer.

16:24.450 --> 16:28.850
Das heißt eigentlich, was uns jetzt fehlt, ist so eine Operation, mit

16:28.850 --> 16:33.550
der wir diese Konsensusbildung ohne die Unterstützung von diesem KV

16:33.550 --> 16:37.230
-Diagramm oder ohne eigentlich, dass wir die Produktthermie mal

16:37.230 --> 16:41.890
betrachten, dass wir so eine Regel haben, die uns so etwas erlaubt.

16:43.210 --> 16:46.850
Und wenn man das jetzt ein bisschen genauer hinguckt, wenn man genauer

16:46.850 --> 16:49.510
hier hinguckt, dann sieht man tatsächlich, dass die komplementär

16:49.510 --> 16:52.330
belegte Variable zu 1, dort quer geworden ist.

16:54.570 --> 16:58.910
Also wenn man jetzt hier in diesem Beispiel guckt, wie dieses A, B

16:58.910 --> 17:04.390
entsteht, das haben wir gesehen im KV-Diagramm, und der dazugehörige

17:04.390 --> 17:09.750
Würfel, da sieht man, dass zunächst mal an der Stelle, wo die

17:09.750 --> 17:15.090
Komponenten komplementär belegt sind, in den zwei Würfeln C1 und C2,

17:15.770 --> 17:16.810
haben wir ein dort quer.

17:18.050 --> 17:21.910
Aber an den anderen Stellen, was haben wir an den anderen Stellen?

17:23.330 --> 17:26.270
Was haben wir an der ersten Stelle und an der zweiten Stelle?

17:27.150 --> 17:31.350
Kann jemand von euch die Operation raten bzw.

17:31.710 --> 17:35.730
herausfinden, die man hier angewendet hat, damit man hier eine 1 und

17:35.730 --> 17:36.870
hier eine 1 bekommt?

17:38.790 --> 17:41.850
Also damit man hier eine 1 und hier eine 1 bekommt.

17:43.610 --> 17:45.630
Was hat man mit den zwei gemacht?

17:48.350 --> 17:51.750
Ja, wie bitte?

17:53.730 --> 17:58.590
Exklusiv oder, oder man hat Schnitt von diesem Teilwürfel gebildet.

17:59.710 --> 18:05.110
Ja, wir haben vorher gesehen, wir können ja Schnitt von zwei Würfeln

18:05.110 --> 18:10.050
bilden, und bei zwei Würfeln, wo ich eine 1 und dort quer habe, dann

18:10.050 --> 18:15.910
ist der Schnitt 1, auch 1 und, oder dort quer und 1 Schnitt 1 und die

18:15.910 --> 18:18.650
komplementär belegte Variable verfügen wir zu dort quer.

18:20.050 --> 18:23.670
Das heißt eigentlich, wir haben die Vorschrift, wie man solche

18:23.670 --> 18:29.230
Konsensuswürfel basierend auf oder Konsensuswürfel aus zwei Würfeln

18:29.230 --> 18:29.850
bilden kann.

18:30.470 --> 18:34.130
Jetzt kommt das Ganze hier mit Hilfe von einer mehrformalen

18:34.130 --> 18:34.830
Definition.

18:35.030 --> 18:40.030
Das heißt der Konsensuswürfel, das ist der rote hier.

18:44.630 --> 18:47.790
Das ist unser Konsensuswürfel in dem Beispiel AB.

18:49.170 --> 18:55.030
Das ist der größte Würfel, der weder in C1, also weder in AC quer,

18:55.250 --> 19:00.710
noch in BC existiert oder enthalten ist, aber in der Vereinigung

19:00.710 --> 19:01.690
dieser zwei Würfel.

19:01.950 --> 19:06.630
Das heißt, man sieht hier, der ist weder in C1 enthalten, das ist C1.

19:09.770 --> 19:11.530
Das war unser C1.

19:12.370 --> 19:13.890
Das ist AC quer.

19:15.130 --> 19:18.050
Der ist auch nicht in BC enthalten.

19:18.410 --> 19:23.670
Das ist unser C2 Würfel 2, aber der ist natürlich in der Vereinigung

19:23.670 --> 19:25.270
von diesen zwei Würfeln enthalten.

19:26.810 --> 19:35.510
Und dieser Konsensuswürfel existiert genau dann, wenn es in C1 und in

19:35.510 --> 19:40.050
C2 genau eine komplementär belegte Variable gibt oder existiert.

19:40.050 --> 19:43.690
Und diese komplementär belegte Variable können wir natürlich auch

19:43.690 --> 19:47.390
anhand von dem Diagramm hier sehen, denn die komplementär belegte

19:47.390 --> 19:54.830
Variable ist nichts anderes als die Variable C, die einmal 1 und

19:54.830 --> 19:58.010
einmal 0 in den zwei Würfeln auftaucht.

19:59.050 --> 20:01.670
Das heißt, das ist unser Konsensuswürfel.

20:02.370 --> 20:03.710
Wie konstruieren wir das?

20:03.710 --> 20:09.950
Wenn wir zwei Würfel haben und ein paar von komplementär belegten

20:09.950 --> 20:13.610
Variablen, also die Variablen E sind komplementär belegt, zum Beispiel

20:13.610 --> 20:21.190
C1I im Würfel 1 ist 0 und C2I im zweiten Würfel 1 oder umgekehrt, dann

20:21.190 --> 20:24.770
gehen wir hin und verfügen diese komplementär belegte Variable oder

20:24.770 --> 20:31.130
setzen wir die komplementär belegte Variable zu Don't Care und bilden

20:31.130 --> 20:37.410
wir anschließend aus den zwei entstehenden Würfeln hier durch diese

20:37.410 --> 20:39.290
Operation die Schnittmenge.

20:39.950 --> 20:42.270
Was bedeutet das anhand von einem Beispiel?

20:42.990 --> 20:44.910
Und zwar anhand von dem gleichen Beispiel.

20:45.110 --> 20:47.850
Wir haben die zwei Würfel A, C quer und B, C.

20:48.550 --> 20:52.150
Also 1, Don't Care 0 und Don't Care 1, 1.

20:52.830 --> 20:55.770
Das heißt, wir setzen zunächst mal für die komplementär belegte

20:55.770 --> 20:57.910
Variable in beiden Würfeln ein Don't Care.

20:58.850 --> 21:04.110
Dann bekommen wir sozusagen ein C1 Strich und C2 Strich.

21:04.250 --> 21:08.210
Da haben wir hier ein Don't Care und hier eine Don't Care, weil die

21:08.210 --> 21:10.790
Komponente hier komplementär belegt ist.

21:11.350 --> 21:15.310
Und dann bilden wir die Schnittmenge dieser zwei Würfel.

21:15.750 --> 21:19.910
Und die Schnittmenge von C1 Strich und C2 Strich ist nichts anderes

21:19.910 --> 21:22.630
als 1, 1 Don't Care.

21:22.630 --> 21:34.050
Und bei der Variablenreihenfolge A, B, C ist es nichts anderes als A,

21:34.090 --> 21:34.210
B.

21:36.410 --> 21:42.050
Also das heißt, die komplementär belegte Variable, genau eine

21:42.050 --> 21:44.790
Komponente ist komplementär belegt in zwei Würfeln.

21:45.170 --> 21:48.190
Man verfügt diese komplementär belegte Variable zu Don't Care und

21:48.190 --> 21:50.070
bildet die Schnittmenge von den zwei Würfeln.

21:50.070 --> 21:54.790
Jetzt schauen wir, wie wir das nutzen, oder bevor wir schauen, wie wir

21:54.790 --> 21:58.090
das nutzen zur Minimierung von Bool'schen Funktionen, nochmal zwei

21:58.090 --> 22:02.870
Betrachtungen und zwar zwei Sonderfälle von diesem Konsensusregel.

22:03.530 --> 22:08.690
Im ersten Sonderfall wollen wir annehmen, dass U die eine Funktion die

22:08.690 --> 22:10.190
andere Funktion impliziert.

22:12.110 --> 22:14.410
Geht es leiser da hinten?

22:15.290 --> 22:15.690
Danke.

22:16.610 --> 22:21.510
Also das heißt, das ist wahr, die Aussage U impliziert W für alle

22:21.510 --> 22:24.690
Belegungen der Variablen von U und B und W.

22:24.890 --> 22:27.810
Und das sind ja zwei Funktionen, wie wir vorher gesehen haben.

22:29.370 --> 22:34.710
Dann gilt das eigentlich, wenn U W ein Implikant von W ist, dann ist

22:34.710 --> 22:36.290
natürlich U W gleich U.

22:36.550 --> 22:40.030
Das heißt, wenn ich in dieser Gleichung hier einsetze, statt U W setze

22:40.030 --> 22:40.510
ich U.

22:40.510 --> 22:45.530
Und mit dem Absorptionsgesetz wissen wir, dass X U oder U ist auch U.

22:45.730 --> 22:49.790
Das heißt, wir bekommen hier, also mit dem Absorptionsgesetz hier

22:49.790 --> 22:52.750
verschwinden die zwei Termine, bleibt nur ein U.

22:53.030 --> 22:57.410
Und hier sieht man, dass der Konsensusterm absorbiert einen der

22:57.410 --> 22:58.630
erzeugenden Termine.

22:58.790 --> 23:03.250
Die erzeugenden Termine sind X U und X quer W und eins von denen, also

23:03.250 --> 23:04.450
X U verschwindet.

23:04.550 --> 23:07.250
Es bleibt nur U oder X quer U.

23:08.170 --> 23:12.410
Und somit haben wir viel erreicht, denn aus einem Implikanten entsteht

23:12.410 --> 23:15.450
ein kurzerer Implikant.

23:16.010 --> 23:19.110
Der zweite Sonderfall, wenn U gleich W ist.

23:19.370 --> 23:24.770
Also wenn U gleich W, dann können wir vor X U oder X quer W, X U oder

23:24.770 --> 23:26.210
X quer U einsetzen.

23:26.510 --> 23:28.390
Und das ist natürlich nichts anderes als U.

23:28.950 --> 23:29.950
Und was bedeutet das?

23:29.950 --> 23:35.370
Das bedeutet eigentlich, zwei Termine unterscheiden sich in einer

23:35.370 --> 23:38.850
Variable, in X, und diese Variable wird einfach weggekürzt.

23:39.150 --> 23:42.230
Das ist genau, was wir gemacht haben bei Konsensus, beziehungsweise

23:42.230 --> 23:44.910
bei den ganzen Huntingtonischen Aktionen.

23:44.970 --> 23:49.250
X oder X U quer ist gleich eins und eins und irgendetwas ist

23:49.250 --> 23:49.850
irgendetwas.

23:50.330 --> 23:54.170
Das heißt, die beiden erzeugenden Termine vom Konsensuswürfel, die

23:54.170 --> 23:57.690
verschmelzen hier zu einem kürzeren Term, und zwar zu U.

23:57.690 --> 24:02.110
Und das ist nichts anderes als die Zusammenfassungsregel des Guan

24:02.110 --> 24:04.490
-Klasky -Verfahrens, das wir bereits kennengelernt haben.

24:05.210 --> 24:10.590
So, jetzt schauen wir, wie wir all das benutzen können, um Bulsche

24:10.590 --> 24:12.610
Funktionen zu minimieren.

24:13.490 --> 24:16.690
Und das macht man dadurch, indem man eine...

24:17.330 --> 24:21.870
Wenn man eine Bulsche Funktion hat, dargestellt im Würfelkalkül, dann

24:21.870 --> 24:25.670
wissen wir, dann ist diese Funktion dargestellt als eine Menge von

24:25.670 --> 24:27.830
Würfeln oder eine Würfelüberdeckung.

24:28.930 --> 24:34.530
Und wenn wir für diese Würfelüberdeckung eine erschöpfende Bildung von

24:34.530 --> 24:39.610
Konsensuswürfeln machen, bis es keine weiteren Konsensuswürfel

24:39.610 --> 24:44.550
entstehen, dann haben wir die Menge aller Primimplikanten der

24:44.550 --> 24:44.970
Funktion.

24:44.970 --> 24:48.810
Und ich sage ganz explizit die Menge aller Primimplikanten der

24:48.810 --> 24:52.810
Funktion, weil die Würfeldarstellung der Funktion, die haben wir nur

24:52.810 --> 24:55.370
angewandt für die Darstellung von Produktthemen.

24:55.970 --> 24:58.850
Also für den konjunktiven Fall funktioniert das hier nicht.

24:59.770 --> 25:02.410
So, und das ist die Grundlage von dem Konsensusverfahren.

25:03.210 --> 25:04.130
Was bedeutet das?

25:04.250 --> 25:08.670
Das bedeutet in unserem Beispiel, diese zwei Primimplikanten erzeugen

25:08.670 --> 25:12.370
ein Konsensuswürfel, der hier ebenfalls ein Primimplikant.

25:12.370 --> 25:16.450
Und wenn wir jetzt versuchen, hier weitere Konsensuswürfel zwischen

25:16.450 --> 25:22.670
diesen drei Würfeln, also wir haben zunächst mal A²C und B²C, das sind

25:22.670 --> 25:26.350
irgendwelche zwei Würfel, die wir einfach beliebig auswählen, aber

25:26.350 --> 25:28.230
nicht die Mintermien der Funktion.

25:28.410 --> 25:31.890
Wir können auch mit den Mintermien der Funktion anfangen, aber das

25:31.890 --> 25:33.110
würde viel länger dauern.

25:33.110 --> 25:36.210
Ja, dann landen wir beim Klein-McCluskey.

25:36.370 --> 25:38.370
Das heißt hier, man fängt nicht mit den Mintermien, sondern mit

25:38.370 --> 25:42.710
irgendwelchen beliebigen Blöcken, die nicht unbedingt Primimplikanten

25:42.710 --> 25:43.350
sein müssen.

25:44.070 --> 25:49.610
Hier fangen wir mit A²C und B²C und da bilden wir einen

25:49.610 --> 25:52.910
Konsensuswürfel, der ist dann 1,1, don't care.

25:53.390 --> 25:56.690
Wenn wir jetzt versuchen, weitere Konsensuswürfel zu bilden zwischen

25:56.690 --> 26:00.630
diesen drei, dann entstehen keine oder es existieren keine weiteren.

26:01.370 --> 26:06.090
Und deshalb ist diese Menge von allen drei Würfeln die Menge aller

26:06.090 --> 26:07.450
Primimplikanten der Funktion.

26:09.870 --> 26:10.910
Habt ihr das verstanden?

26:12.930 --> 26:13.950
Wir schauen mal.

26:15.110 --> 26:17.110
Das könnt ihr zu Hause lesen.

26:18.490 --> 26:20.650
Das wäre jetzt so eine Funktion.

26:21.310 --> 26:24.670
Eine Funktion y sei durch ein KV-Diagramm angegeben.

26:25.030 --> 26:27.430
Das ist auch eine unvollständig definierte Funktion.

26:27.430 --> 26:29.250
Wie man sieht, man hat zwei don't cares.

26:30.270 --> 26:34.030
Und man sieht hier, dass man diese Funktion mit irgendeiner

26:34.030 --> 26:36.410
Würfelüberdeckung beschreiben kann.

26:37.010 --> 26:43.690
Und diese Würfelüberdeckung ist jetzt nichts anderes als C²B².

26:45.030 --> 26:47.620
C²B² ist natürlich der Block hier.

26:49.090 --> 26:50.150
Der Block hier.

26:51.250 --> 26:52.930
Das ist C²B².

26:53.790 --> 26:55.530
Und das ist das hier.

26:55.850 --> 27:00.770
Wenn wir hier die Variablenreihenfolge D, C, B, A haben, dann haben

27:00.770 --> 27:03.070
wir natürlich hier Würfel C²B².

27:04.010 --> 27:06.950
Dann haben wir hier noch ein Würfel.

27:07.410 --> 27:13.370
Und wohlgemerkt, das ist der Ausgangspunkt für das Konsensusverfahren.

27:14.750 --> 27:19.970
Da müssen irgendwelche Blöcke hier gefunden werden, die alle Einsen

27:19.970 --> 27:20.630
überdecken.

27:20.630 --> 27:24.230
Und natürlich, wenn wir unvollständige Funktionen haben und wir wollen

27:24.230 --> 27:27.430
die disjunktive Form bestimmen, dann müssen wir die don't cares zu

27:27.430 --> 27:28.190
Einzelnen verfügen.

27:28.390 --> 27:29.770
Das wissen wir vom letzten Mal.

27:30.450 --> 27:33.610
Und da sehen wir, das ist alles, was nicht in C ist.

27:35.830 --> 27:37.450
Das wäre der hier.

27:39.470 --> 27:41.470
Und das andere wäre das hier.

27:42.470 --> 27:45.490
Genau, das ist alles, was nicht in C ist, in B und in A.

27:45.610 --> 27:48.890
Deshalb don't care 0, 1, 1.

27:48.890 --> 27:54.650
Und dann noch ein Term hier, und zwar diese don't care müssen wir

27:54.650 --> 27:56.070
natürlich zu 1 verfügen.

27:57.250 --> 28:01.530
Das heißt, das ist der Minterm 4 und Minterm 4 ist nichts anderes als

28:01.530 --> 28:02.710
0, 1, 0, 0.

28:03.830 --> 28:06.410
Das ist so die Ausgangslage.

28:07.410 --> 28:08.850
Und man sieht hier den Unterschied.

28:08.850 --> 28:12.950
Wenn ich mit Quantum Clustering jetzt hier die Minimierung durchführen

28:12.950 --> 28:19.310
will, dann muss ich hier 7 Minterme aufschreiben.

28:19.770 --> 28:21.250
Das ist die erste quantische Tabelle.

28:21.730 --> 28:22.730
7 Minterme.

28:22.870 --> 28:24.390
Hier habe ich drei Würfel.

28:26.170 --> 28:27.230
Und zwar beliebig.

28:27.690 --> 28:31.450
Der hier, der grüne hier, ist kein Prämiplikant der Funktion.

28:31.670 --> 28:34.690
Man kann es mit bloßem Auge sehen, weil ich kann den natürlich

28:34.690 --> 28:38.050
vergrößern zu insgesamt A, C quer.

28:38.050 --> 28:42.390
Ja, zu diesem ganzen großen Block in der Mitte.

28:43.730 --> 28:49.190
Und ausgehend davon, also von einer beliebigen Anfangsüberdeckung der

28:49.190 --> 28:52.890
Funktion mit Hilfe von Würfeln, wollen wir jetzt alle Prämiplikanten

28:52.890 --> 28:53.330
bestimmen.

28:54.270 --> 28:59.310
Man geht hin, man schreibt diese Würfel, die drei Würfel, die wir hier

28:59.310 --> 29:02.870
ausgewählt haben, anhand von dem KV-Diagramm, bzw.

29:03.390 --> 29:05.850
vorgegeben sind durch die Beschreibung der Funktion.

29:06.550 --> 29:10.110
Man tut sie oder man schreibt sie in eine Tabelle.

29:11.010 --> 29:14.990
Die kriegen ihre Nummern, also Würfel 1, 2 und 3.

29:16.430 --> 29:18.830
Und dann hat man zwei Spalten hier.

29:19.470 --> 29:23.690
Einmal eine Spalte, in der man eingibt, aus welchen Würfeln ein neuer

29:23.690 --> 29:25.950
Konsensuswürfel entstanden ist.

29:26.190 --> 29:30.070
Und wenn ein Konsensuswürfel entsteht, der schon enthalten ist in der

29:30.070 --> 29:34.290
Menge von den existierenden Würfeln, dann streichen wir den, damit

29:34.290 --> 29:37.070
diese Liste nicht beliebig lang wird.

29:37.790 --> 29:43.450
Deshalb geben wir die Gründe für die Streichung von entstehenden

29:43.450 --> 29:47.910
Konsensuswürfeln, die bereits enthalten sind in der Menge, in der

29:47.910 --> 29:50.050
Überdeckung, in der letzten Spalte an.

29:50.850 --> 29:55.310
Und wir versuchen solange die Konsensuswürfel zu bilden, bis es keine

29:55.310 --> 29:55.850
mehr gibt.

29:56.990 --> 29:58.910
Das machen wir jetzt für das Beispiel.

30:00.110 --> 30:02.450
Das heißt, das sind hier alle drei Würfel.

30:02.690 --> 30:08.250
Wir fangen mit dem zweiten an und wir versuchen hier Konsensuswürfel

30:08.250 --> 30:10.610
mit allen Würfeln, die über dem liegen.

30:11.110 --> 30:12.950
Das heißt nur mit eins eigentlich.

30:13.610 --> 30:18.010
Und man sieht hier Würfel 1 und Würfel 2, die sind komplementär

30:18.010 --> 30:18.310
belegt.

30:18.430 --> 30:20.470
Ich habe dich gesehen, ich komme gleich auf dich zurück.

30:21.130 --> 30:25.790
Wir sehen hier, dass diese zwei Würfel komplementär belegt sind in der

30:25.790 --> 30:26.430
Variabli.

30:27.410 --> 30:29.110
Also genau in einer Variabli.

30:29.230 --> 30:33.190
Das heißt, ein Konsensuswürfel existiert und dieser Konsensuswürfel

30:33.190 --> 30:37.650
entsteht, indem ich diese Variabli b zu DontCare verfüge und dann

30:37.650 --> 30:39.170
schnittbilde.

30:39.670 --> 30:44.570
Das heißt, aus 2 und 1 bekomme ich auf jeden Fall ein DontCare hier

30:44.570 --> 30:50.970
und 0 und 0, Schnitt ist 0, DontCare, DontCare ist DontCare und 1 und

30:50.970 --> 30:52.270
DontCare 1 ist 1.

30:53.470 --> 30:55.030
So, das ist der erste Schritt.

30:55.370 --> 31:01.250
Also aus den zwei Würfeln, C1 und C2 oder 1 und 2 in dem Fall, ist ein

31:01.250 --> 31:02.610
neuer Würfel entstanden.

31:04.330 --> 31:09.230
Jetzt prüfen wir als nächstes, ob dieser neue Würfel in irgendeinem

31:09.230 --> 31:11.350
der vorhandenen Würfel enthalten ist.

31:11.350 --> 31:14.750
Wenn der enthalten ist, dann brauchen wir den nicht.

31:14.890 --> 31:20.290
Dann ist er nicht der möglichst große Block von 1, den wir suchen,

31:20.450 --> 31:26.690
sondern es gibt ein 1-Block, was schon bereits größer ist als R und

31:26.690 --> 31:29.870
somit scheidet R als Primimplikant der Funktion aus.

31:30.690 --> 31:35.070
So, und wir wissen, wie die Definition von Überdeckung definiert ist.

31:35.070 --> 31:39.930
Das heißt, er ist auf jeden Fall nicht enthalten in dem und er ist

31:39.930 --> 31:43.750
nicht enthalten in dem, eher umgekehrt eigentlich, die zwei sind

31:43.750 --> 31:45.630
enthalten in dem Neuen.

31:46.050 --> 31:48.590
Das heißt, wenn er nicht in keinem enthalten ist, dann kriegt er

31:48.590 --> 31:49.690
zunächst mal eine Nummer.

31:51.730 --> 31:55.890
Und jetzt prüfen wir als nächstes, ob eins der Würfel, die schon da

31:55.890 --> 31:58.670
sind, in dem neuen Würfel 4 enthalten ist.

31:58.670 --> 32:02.710
Und wie ich bereits gesagt habe, Nummer 2 ist natürlich hier

32:02.710 --> 32:04.030
enthalten, wie wir sehen.

32:04.330 --> 32:06.370
Das ist hier eine 1, hier eine Dornkehr.

32:07.110 --> 32:13.690
Und Nummer 1 ist nicht enthalten eigentlich in dem hier, weil die

32:13.690 --> 32:16.010
Dornkehrstelle nicht an der gleichen Stelle ist.

32:17.050 --> 32:18.310
So, was bedeutet das?

32:18.390 --> 32:22.150
Das bedeutet, Nummer 2 wird gestrichen, weil er schon in dem neuen

32:22.150 --> 32:24.190
Würfel 4 enthalten ist.

32:24.190 --> 32:27.450
Nun machen wir weiter, und zwar mit Nummer 3.

32:27.630 --> 32:31.350
Wir vergleichen Nummer 3 mit allen über ihm liegenden Würfeln.

32:32.010 --> 32:34.610
Und der Würfel über 3 ist nur 1.

32:34.970 --> 32:39.670
Und wir suchen, wir schauen, 1 und 3 sind komplementär belegt an der

32:39.670 --> 32:39.950
Stelle.

32:40.630 --> 32:42.310
Deshalb können wir einen Würfel bilden.

32:42.510 --> 32:45.930
Und dieser Würfel ist dann, die Stelle wird zur Dornkehr.

32:46.010 --> 32:49.870
Und dann bilden wir Durchschnitt, also 0 Dornkehr 0 0.

32:50.530 --> 32:54.390
Jetzt prüfen wir, ob dieser Würfel in einem existierenden Würfel

32:54.390 --> 32:55.570
enthalten ist.

32:56.110 --> 32:57.190
Ist er hier enthalten?

32:57.330 --> 32:58.430
Das ist nicht der Fall.

32:58.590 --> 32:59.590
Ist er hier enthalten?

33:01.390 --> 33:02.870
Das ist nicht der Fall.

33:03.050 --> 33:03.930
Ist er hier enthalten?

33:04.110 --> 33:04.890
Das ist nicht der Fall.

33:04.990 --> 33:06.170
Deshalb bekommt er eine Nummer.

33:07.990 --> 33:12.050
Als nächstes prüfen wir, ob eins der existierenden Würfel im neuen

33:12.050 --> 33:16.710
Würfel, Nummer 5, enthalten ist.

33:16.710 --> 33:21.590
Und man sieht beispielsweise, dass 3 in diesem neuen Würfel enthalten

33:21.590 --> 33:21.910
ist.

33:22.070 --> 33:23.410
Deshalb wird 3 gestrichen.

33:25.370 --> 33:29.530
Das heißt, mit der ersten Zusammenfassung mit den ursprünglichen

33:29.530 --> 33:30.930
Würfeln sind wir fertig.

33:31.230 --> 33:35.150
Aus den ursprünglichen drei Würfeln ist nur einer übrig geblieben.

33:35.750 --> 33:42.270
Es sind aber zwei Konsensuswürfel entstanden, 4 und 5, die nach wie

33:42.270 --> 33:45.230
vor Kandidaten für Primimplikanten der Funktion sind.

33:46.330 --> 33:49.690
Also, dann ziehen wir einen Strich und machen wir weiter mit dem

33:49.690 --> 33:50.430
nächsten Würfel.

33:50.590 --> 33:51.870
Und der nächste Würfel ist 4.

33:52.770 --> 33:55.870
Und wir vergleichen 4 mit allen überliegenden Würfeln.

33:56.270 --> 34:00.550
Die unterscheiden sich, also 1 und 4 unterscheiden sich nicht, also

34:00.550 --> 34:02.810
haben keine komplementär belegte Variablen.

34:03.350 --> 34:05.270
Deshalb existiert kein Konsensuswürfel.

34:06.090 --> 34:07.570
Also machen wir weiter mit 5.

34:07.670 --> 34:10.370
5 und 4 sind hier komplementär belegt.

34:10.370 --> 34:11.730
Die kann ich hier zusammenfassen.

34:12.510 --> 34:16.670
Und dann bekomme ich 0.0.0.0.

34:17.130 --> 34:20.550
Jetzt gucken wir, ob dieser Würfel in einem enthalten ist.

34:20.770 --> 34:24.350
Und wenn man hinschaut, dann sieht man, dass er tatsächlich hier in 1

34:24.350 --> 34:25.170
enthalten ist.

34:25.630 --> 34:29.770
Deshalb bekommt er überhaupt keine Nummer und wird aus der Liste

34:29.770 --> 34:31.270
sofort gestrichen.

34:32.830 --> 34:35.030
So, als letztes haben wir 5 mit 4.

34:35.030 --> 34:37.410
Dann müssen wir 5 mit 1 vergleichen.

34:37.650 --> 34:40.990
Und 5 mit 1 sind nicht an einer Stelle komplementär belegt.

34:41.170 --> 34:44.690
Das heißt, ich kann keine weiteren Konsensuswürfel bilden.

34:45.630 --> 34:48.410
Was ist jetzt übrig geblieben aus der ganzen Geschichte?

34:49.350 --> 34:51.650
Übrig geblieben sind drei Würfel.

34:52.650 --> 35:02.850
Und zwar Würfel 1, 4 und 5.

35:03.670 --> 35:08.930
Und was das Konsensusverfahren uns zeigt, das sind alle

35:08.930 --> 35:10.770
Primimplikanten der Funktion.

35:12.350 --> 35:16.150
Das heißt, wenn wir jetzt ein bisschen hinschauen, dann können wir

35:16.150 --> 35:20.390
natürlich die Menge aller Primimplikanten der Funktion als

35:20.390 --> 35:21.810
Würfelüberdeckung eingeben.

35:22.430 --> 35:26.290
Das ist natürlich b-quer, a-quer, also don't care 0, 0, don't care,

35:26.610 --> 35:29.750
don't care 0, don't care 1, 0, don't care 0, 0.

35:29.750 --> 35:33.690
Wenn wir das ein bisschen genauer angucken hier im KV-Diagramm, was

35:33.690 --> 35:34.490
haben wir bekommen?

35:36.670 --> 35:43.610
Die Variablenreihenfolge ist hier d, c, b, a.

35:44.850 --> 35:49.050
Und wir haben zunächst mal den ersten Würfel, das ist c-quer, b-quer.

35:49.950 --> 35:54.770
Und c-quer, b-quer ist nichts anderes als das hier.

35:56.610 --> 36:01.270
Ja, das war Würfel Nummer 1, das hatten wir schon in der

36:01.270 --> 36:02.690
Anfangsüberdeckung gehabt.

36:03.550 --> 36:06.590
Dann haben wir hier nichts anderes als c-quer, a.

36:06.790 --> 36:12.630
Und c-quer, a ist natürlich, wie wir das hier sehen, nicht nur die 1

36:12.630 --> 36:15.530
mit der don't care, sondern die 3 Einsen mit der don't care.

36:16.890 --> 36:27.650
Und der letzte Würfel hier, das ist d-quer, b-quer, a-quer.

36:28.690 --> 36:34.090
Und d-quer, b-quer, a-quer ist nicht nur dieses durch die Nullstelle

36:34.090 --> 36:38.990
gegebene Minterm, sondern zusammengefasst mit Minterm 0.

36:40.550 --> 36:45.530
Und wenn man das Ganze hier mal anschaut, das sind tatsächlich alle

36:45.530 --> 36:49.270
Primimplikanten der Funktion, die wir überhaupt...

36:49.270 --> 36:54.770
alle Primimplikanten der Funktion, also alle Primimplikanten der

36:54.770 --> 36:55.610
gegebenen Funktion.

36:56.930 --> 37:02.770
Und man sieht hier, wie bei jedem Verfahren, das wir mithilfe von dem

37:02.770 --> 37:07.830
Konsensusverfahren alle Primimplikanten bestimmt haben, aber nicht die

37:07.830 --> 37:09.250
minimale Form der Funktion.

37:09.710 --> 37:14.250
Das heißt, man muss eigentlich hingehen jetzt, um die minimale Form

37:14.250 --> 37:18.390
der Funktion zu bestimmen, und schauen, welche dieser Würfel oder

37:18.390 --> 37:24.890
diese Primimplikanten sind notwendig, zunächst mal unbedingt

37:24.890 --> 37:27.990
notwendig, um die Funktion zu überdecken, also die

37:27.990 --> 37:29.150
Kernprimimplikanten.

37:29.150 --> 37:33.790
Und man sieht zum Beispiel, dass Rot und Grün auf jeden Fall

37:33.790 --> 37:38.690
Kernprimimplikanten sind, weil diese Eins hier wird nur durch den

37:38.690 --> 37:43.050
Roten überdeckt, und diese Eins hier wird nur durch den Grünen

37:43.050 --> 37:43.550
überdeckt.

37:43.710 --> 37:47.870
Und den Blauen brauche ich überhaupt nicht, weil diese Eins habe ich

37:47.870 --> 37:50.510
sowieso durch den Roten überdeckt, also Minterm 0.

37:51.270 --> 37:54.050
Und Minterm 4 ist eigentlich kein richtiger Minterm.

37:54.050 --> 37:57.470
Das war ein Dontker, was wir zu eins verfügt haben, damit wir

37:57.470 --> 38:01.090
möglichst große Blöcke bilden können.

38:01.410 --> 38:04.910
Und ich muss das nicht überdecken, damit ich die Funktion realisiere.

38:05.590 --> 38:09.050
Das heißt eigentlich, die disjunktive Minimalform der Funktion besteht

38:09.050 --> 38:12.090
nur aus zwei von diesen drei Würfeln.

38:12.330 --> 38:17.610
Also nochmal die Betonung hier, das Konsensusverfahren bestimmt alle

38:17.610 --> 38:19.510
Primimplikanten der Funktion.

38:19.510 --> 38:23.450
Und der zweite Schritt der Minimierung, also die Bestimmung der

38:23.450 --> 38:26.010
Minimalform, muss man noch lösen.

38:26.170 --> 38:29.710
Hier haben wir das gelöst mithilfe vom KV-Diagramm, aber wir können es

38:29.710 --> 38:33.530
auch lösen mithilfe von der Überdeckungsstabelle und der Definition

38:33.530 --> 38:36.670
einer Überdeckungsfunktion, genau wie bei Quine McCluskey.

38:37.810 --> 38:39.690
So, jetzt komme ich zu deiner Frage.

38:39.690 --> 38:42.670
Es ist lange her, aber...

38:42.670 --> 38:44.690
Ich wollte wissen, ob die Wahl der...

38:48.570 --> 38:53.890
Genau, also seine Frage war, seine Frage ist eine sehr wichtige Frage.

38:55.370 --> 38:59.890
Genauso wichtig wie die Diskussion da hinten, genau, über was man

38:59.890 --> 39:01.370
heute Abend machen will wahrscheinlich.

39:01.810 --> 39:03.930
Nein, die sind nicht zufrieden mit meiner Lösung.

39:04.810 --> 39:05.990
Sie diskutieren noch.

39:06.950 --> 39:07.290
Okay.

39:09.550 --> 39:12.930
Danke, also der Kapi, danke für deine Unterstützung.

39:14.250 --> 39:16.090
Seine Frage ist sehr wichtig.

39:16.350 --> 39:20.650
Er hat gesagt, er wollte fragen, ob die Auswahl der

39:20.650 --> 39:24.810
Anfangsüberdeckung, also der ersten Würfel entscheidend ist, oder?

39:25.730 --> 39:30.110
So, das kann man wirklich beliebig machen, aber natürlich eine

39:30.110 --> 39:34.770
geschickte Auswahl von den Anfangswürfeln würde diese Tabelle, oder

39:34.770 --> 39:38.390
diese Anzahl der Vergleiche, die man machen muss, reduzieren.

39:39.210 --> 39:42.330
Du kannst mit einer beliebigen Anfangsüberdeckung anfangen.

39:43.370 --> 39:45.880
Also, wo du nicht weißt, ist es prämiplikant, nicht prämiplikant.

39:46.350 --> 39:49.490
Wenn du mit dem prämiplikanten anfängst, dann wirst du nicht in der

39:49.490 --> 39:55.150
Lage sein, einen einzigen Konsensuswürfel zu bilden, der nicht schon

39:55.150 --> 39:58.070
in deiner Würfelmenge enthalten ist.

39:58.070 --> 40:02.970
Und das ist eigentlich, wie man beweist, dass eine gegebene Menge von

40:02.970 --> 40:05.950
Würfeln die Menge der prämiplikanten ist.

40:06.090 --> 40:09.510
Das heißt, wenn ich eine gegebene Menge von Würfeln habe und ich

40:09.510 --> 40:13.650
schaffe es, keinen einzigen Konsensuswürfel zu bilden, dann ist diese

40:13.650 --> 40:19.410
Menge von Würfeln die prämiplikanten der Funktion.

40:24.990 --> 40:26.230
So, jetzt...

40:26.230 --> 40:30.610
Das Konsensusverfahren dient also zur Bestimmung aller prämiplikanten

40:30.610 --> 40:31.650
Überdeckungsprobleme.

40:32.530 --> 40:37.510
Muss anders, also zum Beispiel wie bisher mit der zweiten Quantsch

40:37.510 --> 40:39.310
-Hinterbelle gelöst werden.

40:39.450 --> 40:42.930
In dem Fall haben wir das im KV-Diagramm gemacht.

40:43.490 --> 40:47.190
Und jetzt kommen wir zu der Aussage, die ich gerade gemacht habe.

40:47.190 --> 40:52.390
Das heißt, wenn wir prüfen wollen, ob eine gegebene Überdeckung, also

40:52.390 --> 40:58.410
eine Menge von Würfeln, sämtliche prämiplikanten der Funktion enthält,

40:58.590 --> 41:02.210
dann bildet man zu jedem Würfelpaar den Konsensuswürfel.

41:02.810 --> 41:06.510
Falls jeder Konsensuswürfel schon in einem vorhandenen Würfel erfasst

41:06.510 --> 41:11.850
wird, dann enthält diese Überdeckung alle prämiplikanten der Funktion.

41:11.850 --> 41:14.990
Man sieht hier ein Beispiel.

41:15.830 --> 41:18.710
Das heißt, wenn ich so eine Funktion hier habe und ich gehe hin und

41:18.710 --> 41:28.390
ich schreibe die Anfangsüberdeckung dieser Funktion als 0.0.0.0.0.0

41:28.390 --> 41:33.090
und so weiter und so fort, dann sehe ich sofort eigentlich, dass

41:33.090 --> 41:36.050
überhaupt kein einziger Konsensuswürfel bildet.

41:36.630 --> 41:39.570
Das heißt, hier ist eine Funktion mit sechs Variablen.

41:39.570 --> 41:40.550
Da ist e dabei.

41:42.610 --> 41:52.290
Und wenn wir die Würfel hier, also das ist e, a, b, c, d, c, b, a.

41:52.730 --> 41:57.090
Das heißt, wir haben hier den Würfel don't care, null, don't care,

41:57.850 --> 41:59.430
don't care, don't care.

41:59.430 --> 42:04.170
Dann haben wir hier don't care, don't care, null, null, null.

42:04.850 --> 42:10.290
Nein, null, null für e.

42:11.530 --> 42:13.630
Und dann d taucht nicht auf.

42:13.990 --> 42:18.290
c ist null und b ist null und a taucht nicht auf.

42:18.450 --> 42:23.290
Und hier haben wir null, don't care, don't care, don't care, null.

42:23.510 --> 42:27.770
Das sind die drei Würfel, die durch diese Funktion vorgegeben sind.

42:27.770 --> 42:31.950
Und man sieht hier, ich kann eigentlich zwischen diesen drei Würfeln

42:31.950 --> 42:35.410
keinen einzigen Konsensuswürfel bilden, weil ich habe keine...

42:35.410 --> 42:39.890
Also es können keine zwei Komponenten in irgendwelche zwei Würfel

42:39.890 --> 42:41.770
existieren, die in einer...

42:42.370 --> 42:47.750
Es können keine zwei Würfel mit jeweils komplementär belegten

42:47.750 --> 42:51.190
Komponenten existieren, weil die zwei Würfel hier, die enthalten nur

42:51.190 --> 42:51.510
Nullen.

42:52.210 --> 42:55.970
Und das können wir sofort sehen, natürlich anhand der Funktion.

42:56.190 --> 42:59.310
Das heißt, nur negiert die Variablen tauchen hier auf.

42:59.410 --> 43:01.870
Deshalb kann ich überhaupt keinen Konsensuswürfel bilden.

43:02.450 --> 43:07.210
Somit ist die Funktion hier, ist die angegebene Funktion hier die

43:07.210 --> 43:10.230
Disjunktion aller Primimplikanten der Funktion.

43:10.870 --> 43:14.950
Aber nicht unbedingt die minimale Form, weil es kann sein, dass

43:14.950 --> 43:17.950
natürlich eins von diesen Primimplikanten entbehrlich ist.

43:19.590 --> 43:23.490
So, also Disjunktion aller Primimplikanten der Funktion, was nicht

43:23.490 --> 43:25.330
identisch mit der Minimalform ist.

43:26.290 --> 43:27.830
Okay, so viel dazu.

43:27.950 --> 43:28.550
Gibt es Fragen?

43:30.630 --> 43:33.310
Nein, dann machen wir noch das letzte Verfahren.

43:33.650 --> 43:36.910
Und das letzte Verfahren ist das sogenannte Nelson-Verfahren.

43:37.050 --> 43:40.350
Das kennt ihr im Prinzip, das ist ein algebraisches Verfahren.

43:41.030 --> 43:43.870
Und dieses algebraische Verfahren hat eine Besonderheit.

43:43.870 --> 43:47.810
Das klingt natürlich spannend, aber das habt ihr schon praktiziert,

43:47.990 --> 43:51.470
als ihr Buhl'sche Ausdrücke vereinfacht habt, dass wir zum Beispiel

43:51.470 --> 43:55.010
von einer konjunktiven Form der Funktion auf die disjunktive Form

43:55.010 --> 43:58.370
kommen oder von der disjunktiven Form auf die konjunktive Form kommen.

43:58.750 --> 44:02.010
Was bedeutet das, wenn wir die Minimalform bestimmen?

44:02.650 --> 44:08.250
Das bedeutet, dass wir die Primimplikanten aus den Nullstellen, also

44:08.250 --> 44:12.530
wir haben Summenprodukte und wir multiplizieren sie miteinander, dann

44:12.530 --> 44:15.530
kriegen wir natürlich Primimplikanten, Produkttermine.

44:16.590 --> 44:20.750
Das heißt, die Primimplikanten aus den Nullstellen und die

44:20.750 --> 44:22.870
Primimplikate aus den Einstellen.

44:23.590 --> 44:29.790
Also die Einsblöcke aus den Nullstellen und die Nullblöcke aus den

44:29.790 --> 44:30.370
Einstellen.

44:31.410 --> 44:34.850
Wenn man also die Primimplikanten der Funktion berechnet, so benötigt

44:34.850 --> 44:40.350
man irgendeine beliebige Menge an Implikaten, deren Konjunktion die

44:40.350 --> 44:41.170
Funktion beschreibt.

44:41.170 --> 44:45.030
Natürlich, wenn wir die disjunktive Form bestimmen wollen, dann müssen

44:45.030 --> 44:49.350
wir die Don't-care-zu-eins verfügen, dann diese Implikate nach und

44:49.350 --> 44:53.630
nach distribuieren und dann bekommen wir eine Disjunktion aller

44:53.630 --> 44:55.230
Implikanten der Funktion.

44:56.010 --> 44:59.050
Dabei dürfen wir diese wichtigen Regeln nicht vergessen.

44:59.410 --> 45:02.130
Wenn wir ausdistribuieren, multiplizieren, dann entstehen immer

45:02.130 --> 45:03.130
größere Termine.

45:03.790 --> 45:07.570
Das heißt, auf gar keinen Fall das Absorptionsgesetz vergessen.

45:07.570 --> 45:11.510
Das hilft unheimlich beim Kurzen der Termine.

45:12.570 --> 45:20.590
Dann das Ädernpotenzgesetz, die Komplementgesetze und natürlich das

45:20.590 --> 45:23.990
Huntingtonische Axiom bezüglich der neutralen Elemente.

45:24.730 --> 45:27.470
Das Ganze schauen wir auch anhand von einem Beispiel.

45:28.290 --> 45:34.870
Das heißt, wir haben hier eine Konjunktion von Summentermen und diese

45:34.870 --> 45:38.670
Summenterme, wir wissen im KV-Diagramm, die beschreiben Nullstellen

45:38.670 --> 45:39.430
der Funktion.

45:40.770 --> 45:44.710
Das heißt, das sind Nullstellen, irgendein Nullblock, das ist noch ein

45:44.710 --> 45:46.610
Nullblock und das ist noch ein Nullblock.

45:47.010 --> 45:50.130
Also das sind zwei Nullen, das sind hier vier Nullen und vier Nullen

45:50.130 --> 45:52.170
in einer Funktion mit vier Variablen.

45:53.170 --> 45:58.210
Das heißt, ausgehend aus den Nullstellen der Funktion bekommen wir so

45:58.210 --> 46:02.230
einen Ausdruck, was nichts anderes als Disjunktion von Produkttermen

46:02.230 --> 46:03.230
ist.

46:03.230 --> 46:06.790
Und die Behauptung von diesem Netzungsverfahren ist, dass diese

46:06.790 --> 46:09.810
Disjunktion von den Produkttermen nichts anderes ist als die

46:09.810 --> 46:12.250
Disjunktion aller Primimplikanten der Funktion.

46:12.390 --> 46:15.050
Das heißt, die Funktion hat vier Primimplikanten.

46:15.810 --> 46:21.470
Das ist x3 quer, x4 quer, x2 quer, x3 quer, x4 quer, x1 und so weiter

46:21.470 --> 46:21.950
und so fort.

46:22.550 --> 46:24.930
Und wie man das macht, ist, glaube ich, ziemlich einfach.

46:25.270 --> 46:27.510
Man multipliziert zunächst mal.

46:27.510 --> 46:32.270
Nicht vergessen hier, wenn man multipliziert, x3 quer und x3 kurz mal

46:32.270 --> 46:32.590
weg.

46:32.710 --> 46:35.730
Da braucht man sich nicht mehr drum zu kümmern, spart man ein bisschen

46:35.730 --> 46:36.250
Arbeit.

46:36.890 --> 46:39.630
Und dann kommt man auf so einen Ausdruck und dann sieht man hier zum

46:39.630 --> 46:42.710
Beispiel x3 und x3, das ist nur ein x3.

46:43.230 --> 46:45.610
Hier x3 quer und x3 kein weg.

46:47.310 --> 46:51.490
Dann sieht man hier, dass x2 quer und x2 null sind.

46:51.630 --> 46:53.190
Deshalb verschwindet der Term.

46:53.190 --> 46:57.650
Und dann sieht man eigentlich jetzt, was wenige sehen.

46:58.870 --> 47:10.330
Und zwar sieht man, dass der Term x2, x3 hier auftaucht.

47:12.110 --> 47:16.290
Und hier auftaucht und hier auftaucht und so weiter und so fort.

47:16.450 --> 47:19.690
Das heißt, der Term hier absorbiert alle diese Terme.

47:19.930 --> 47:22.250
Das ist die Anwendung von dem Absorptionsgesetz.

47:22.250 --> 47:24.790
Und deshalb bleibt nur dieser Term hier.

47:24.930 --> 47:29.130
Das heißt, der geht weg, der bleibt hier.

47:29.790 --> 47:33.050
x3, x4 quer und x2 quer haben wir.

47:34.470 --> 47:37.290
Das ist x2, x3, der wird absorbiert.

47:37.550 --> 47:40.510
x3 quer, x4 quer, x1 bleibt hier.

47:41.090 --> 47:43.410
Und das bleibt hier und x2, x3.

47:46.450 --> 47:49.970
So, jetzt gucken wir, was das eigentlich bedeutet.

47:49.970 --> 47:53.270
Das bedeutet, ja, die können wir streichen.

47:53.930 --> 47:57.230
Das bedeutet, das Verfahren liefert dann zunächst mal alle

47:57.230 --> 47:58.070
Primimplikanten.

47:59.370 --> 48:03.450
Und nach wie vor, oder genauso wie bei COIN McCluskey, wie bei

48:03.450 --> 48:06.470
Konsensus, müssen wir den zweiten Schritt der Minimierung machen.

48:07.050 --> 48:11.090
Das heißt, aus diesen Primimplikanten hier müssen wir wissen, welche

48:11.090 --> 48:17.150
sind Kernprimimplikanten, welche sind Wahlprimimplikanten und welche

48:17.150 --> 48:18.370
sind komplett entfernt.

48:19.170 --> 48:24.410
Das können wir bei Funktionen mit 4, 5 Variablen zum Beispiel im KV

48:24.410 --> 48:28.470
-Diagramm mal anschauen oder wir können es allgemein mithilfe von der

48:28.470 --> 48:32.730
Überdeckungstabelle oder der Überdeckungsfunktion feststellen.

48:33.650 --> 48:37.490
So, wir machen es hier nicht mit der zweiten COIN-Tabelle, weil das

48:37.490 --> 48:40.830
ist nur eine Funktion mit 4 Variablen, sondern im KV-Diagramm.

48:40.910 --> 48:46.150
Das heißt, aus dem KV-Diagramm, das war unser KV-Diagramm, das waren

48:46.150 --> 48:47.830
die Implikate, die wir hatten.

48:49.450 --> 48:51.010
Das war der Ausgangspunkt.

48:52.070 --> 49:00.490
Der Ausgangspunkt waren diese drei Implikate, also das war x2-quer

49:00.490 --> 49:08.290
oder x1-quer oder x3-quer.

49:08.970 --> 49:09.870
Das war der hier.

49:14.430 --> 49:15.690
Das war der eine hier.

49:15.690 --> 49:21.370
Dann hatten wir ein x4-quer oder x3-quer.

49:21.690 --> 49:22.710
Das war der hier.

49:24.670 --> 49:28.390
Und dann hatten wir den dritten Term in dieser Gleichung, wenn wir

49:28.390 --> 49:29.490
zwei Schritte machen.

49:30.230 --> 49:34.990
Dann hatten wir den dritten Term, der war x3-quer oder x2-quer oder x1

49:34.990 --> 49:35.650
-quer.

49:40.150 --> 49:43.750
Der dritte Term ist natürlich der erste, den ich hier erwähnt habe.

49:43.930 --> 49:44.850
Das ist der hier.

49:44.850 --> 49:50.970
Aber das sind die drei Summentermi, die der Ausgangspunkt für das

49:50.970 --> 49:52.270
Nelson -Verfahren waren.

49:52.830 --> 49:53.790
Und was haben wir bekommen?

49:54.390 --> 49:56.190
Wir haben vier Termi bekommen.

49:56.970 --> 50:00.270
Und diese vier Termi, die sind nichts anderes als die hier.

50:00.530 --> 50:05.510
Man sieht 1, Entschuldigung, 1, 2, 3, 4.

50:06.090 --> 50:12.530
Und man sieht jetzt, dass eigentlich dieser Premimplikant, also x4

50:12.530 --> 50:16.270
-quer, x3-quer und x1-quer entbehrlich ist.

50:16.630 --> 50:18.350
Das heißt, den brauche ich ja gar nicht.

50:21.290 --> 50:28.930
Und das Gleiche auch das hier, das ist ein vierter Term, ein vierter

50:28.930 --> 50:32.210
Premimplikant, was das Verfahren geliefert hat.

50:32.590 --> 50:36.150
Das ist auch nicht notwendig, um die Funktion, um die minimale Form

50:36.150 --> 50:37.250
der Funktion zu bestimmen.

50:37.250 --> 50:43.830
Weil x3 und x2 ist ein Kernpremimplikant, weil diese 1, diese 1, diese

50:43.830 --> 50:46.650
1 nur durch x3 und x2 überdeckt werden.

50:47.750 --> 50:56.530
Und x4-quer, x3-quer und x1-quer, also dieser horizontal liegende,

50:57.070 --> 50:59.370
hier ist auch ein Kernpremimplikant.

50:59.930 --> 51:03.130
Und wenn ich beide nehme, dann habe ich alle einstellende Funktionen

51:03.130 --> 51:03.590
überdeckt.

51:03.590 --> 51:05.610
Die don't-quer hier brauche ich nicht zu überdecken.

51:07.370 --> 51:12.190
Und somit sind die zwei hier nicht notwendig für die Minimalform der

51:12.190 --> 51:12.590
Funktion.

51:13.270 --> 51:19.650
So, das heißt, die dmf der Funktion, also die disjunktive Minimalform,

51:21.330 --> 51:25.550
ist dann nichts anderes als x3, x2.

51:26.650 --> 51:31.590
x3, x2, das war unser absorbierender Term, was wir vorher hatten.

51:31.590 --> 51:42.510
Oder x4-quer, x3-quer und x2-quer.

51:43.830 --> 51:47.810
Also das ist die disjunktive Form der Funktion, aber was das Nelson

51:47.810 --> 51:51.470
-Verfahren, der erste Schritt, geliefert hat, waren vier Termine.

51:51.610 --> 51:55.730
Das heißt, man sieht hier eigentlich, dass nur zwei davon notwendig

51:55.730 --> 51:58.570
sind, um die Funktion zu überdecken.

51:59.330 --> 52:04.930
Okay, so, das Duali-Verfahren erzeugt aus einer beliebigen Menge an

52:04.930 --> 52:09.410
Implikaten, deren Disjunktion die Funktion vollständig beschreibt, die

52:09.410 --> 52:11.670
Konjunktion à la prime implicati der Funktion.

52:11.830 --> 52:15.690
Das heißt, in dem Fall muss man natürlich die don't-quer zu Null

52:15.690 --> 52:19.530
verfügen und dann natürlich ausdistribuieren, die entsprechenden

52:19.530 --> 52:23.670
Gesetze benutzen und dann bekommt man auch hier die Konjunktion à la

52:23.670 --> 52:28.130
prime implicati und die konjunktive Minimalform bekommt man, indem man

52:28.130 --> 52:32.570
praktisch mithilfe der Quantsch-Tabelle, der zweiten Quantsch-Tabelle

52:32.570 --> 52:40.490
oder KV-Diagramm eine redundante Menge von Prim-Implikaten findet, die

52:40.490 --> 52:42.570
alle Nullstellen der Funktion überdecken.

52:43.910 --> 52:47.650
Als Zusammenfassung für all diese Verfahren, die wir kennengelernt

52:47.650 --> 52:52.010
haben, das heißt, wir wollen Bullshit-Funktionen oder Schaltfunktionen

52:52.010 --> 52:55.950
minimieren und diese Schaltfunktionen haben unabhängige Variablen.

52:56.690 --> 53:00.890
Wir haben drei Kategorien von Verfahren kennengelernt, tabellarisch,

53:01.070 --> 53:05.810
grafisch und algebraisch.

53:06.950 --> 53:11.370
Und je nachdem, wie groß die Anzahl der Variablen der Funktion ist,

53:11.530 --> 53:15.430
also wenn ich Funktionen mit Variablen, mit vier oder fünf

53:15.430 --> 53:19.650
Eingangsvariablen, dann kann ich das noch im KV-Diagramm gut

53:19.650 --> 53:23.150
handhaben, aber natürlich, wenn die Anzahl der Variablen zu groß ist,

53:23.770 --> 53:27.350
dann sind tabellarische Verfahren besser geeignet.

53:28.490 --> 53:31.710
Und bei der Minimierung müssen wir immer zwei Schritte lösen.

53:32.130 --> 53:36.170
Beim ersten Schritt müssen wir die Prim-Thermie der Funktion

53:36.170 --> 53:36.650
bestimmen.

53:38.390 --> 53:40.330
Das habe ich immer wieder betont.

53:40.530 --> 53:42.370
Das ist Schritt eins der Minimierung.

53:44.810 --> 53:48.770
Und Schritt eins der Minimierung heißt Prim-Thermie bestimmen, also

53:48.770 --> 53:52.770
die Prim-Implikanten, wenn ich die disjunktive Minimalform bestimmen

53:52.770 --> 53:56.250
will, und die Prim-Implikate, wenn ich die konjunktive Minimalform

53:56.250 --> 53:56.990
bestimmen will.

53:57.810 --> 54:00.890
Und dann muss ich das sogenannte Überdeckungsproblem lösen.

54:01.490 --> 54:03.470
Und das macht man immer im Schritt zwei.

54:04.750 --> 54:09.470
Und je nachdem, wie komplex oder wie groß die Anzahl der

54:09.470 --> 54:14.030
Eingangsvariablen der Funktion ist, kann man zum Beispiel KV-Diagramm

54:14.030 --> 54:18.850
hier wählen für Funktionen mit kleiner gleich 6 Eingangsvariablen.

54:19.850 --> 54:23.050
Den zweiten Schritt wiederum mit KV-Diagramm oder mit einer

54:23.050 --> 54:23.910
Überdeckungsstabelle.

54:24.890 --> 54:32.550
Wenn wir eine disjunktive Form der Funktion haben, und wir wollen die

54:32.550 --> 54:38.370
disjunktive Minimalform bestimmen, beziehungsweise eine beliebige

54:38.370 --> 54:41.230
konjunktive Form der Funktion, und wir wollen die konjunktive

54:41.230 --> 54:45.990
Minimalform, dann haben wir gesehen, dass wir mit den tabellarischen

54:45.990 --> 54:50.670
Verfahren, also Konsensus oder Quine-McCluskey hier, die Prim-Thermen

54:50.670 --> 54:51.530
bestimmen können.

54:52.310 --> 54:55.750
Den zweiten Schritt müssen wir auch über die Überdeckungsstabelle

54:55.750 --> 54:56.210
lösen.

54:57.310 --> 55:00.250
Und wenn wir eine disjunktive Form, und das ist die Besonderheit vom

55:00.250 --> 55:06.030
Nelson -Verfahren, wenn wir die disjunktive Form der Funktion haben,

55:06.170 --> 55:09.670
also eine Disjunktion von irgendwelchen Produktthermen, wir suchen die

55:09.670 --> 55:13.970
konjunktive Minimalform, oder die konjunktive Form haben und wir

55:13.970 --> 55:17.050
suchen die disjunktive Minimalform, dann kommen wir mit dem Nelson

55:17.050 --> 55:20.970
-Verfahren zunächst mal auf eine Disjunktion aller Prim-Implikanten

55:20.970 --> 55:22.930
oder Konjunktion aller Prim-Implikate.

55:23.410 --> 55:26.650
Und natürlich den zweiten Schritt müssen wir immer mithilfe von der

55:26.650 --> 55:30.510
Überdeckungsstabelle oder bei Funktionen mit kleiner Anzahl von

55:30.510 --> 55:33.310
Eingangsvariablen mithilfe vom KV-Diagramm lösen.

55:34.170 --> 55:40.090
Okay, damit will ich hier das Thema abschließen, es sei denn, es gibt

55:40.090 --> 55:40.930
irgendwelche Fragen.

55:45.320 --> 55:50.960
Gut, ganz kurz zum Vergleich von den unterschiedlichen Verfahren, das

55:50.960 --> 55:54.220
habe ich mehr oder weniger erwähnt, KV-Diagramm bei kleiner variablen

55:54.220 --> 55:59.840
Zahl ist natürlich sehr gut geeignet, vor allem wenn man die Aufgaben

55:59.840 --> 56:02.460
auf Papier und mit Stift lösen will.

56:02.460 --> 56:08.060
Das Konsensusverfahren ist sehr geeignet für den Rechner und passt

56:08.060 --> 56:10.860
seine Rechenzeit natürlich an die Anfangsüberdeckung.

56:11.020 --> 56:12.560
Das war deine Frage von vorher.

56:12.860 --> 56:16.400
Wenn die Anfangsüberdeckung nur aus den Min-Termen der Funktion

56:16.400 --> 56:21.400
besteht, dann braucht natürlich das Konsensusverfahren länger, als

56:21.400 --> 56:25.000
wenn die Anfangsüberdeckung aus irgendwelchen Zusammenfassungen von

56:25.000 --> 56:27.080
Einstellungen und Dortkehrs der Funktion besteht.

56:27.900 --> 56:32.800
Das heißt, die anfängliche Würfelmenge zum Beispiel bei dem

56:32.800 --> 56:37.540
Konsensusverfahren sollte aus möglichst wenigen großen Würfeln

56:37.540 --> 56:38.920
zusammengestellt werden.

56:40.860 --> 56:47.920
Gegenüber Quine-McCluskey hat das Konsensusverfahren den Vorteil, dass

56:47.920 --> 56:53.180
sie nur mit Würfeln zu arbeiten braucht, also eine eigentlich kürzere

56:53.180 --> 56:55.340
Liste verwendet.

56:55.340 --> 57:00.800
Und diese Liste haben wir gesehen, die wird immer durch laufende

57:00.800 --> 57:06.880
Streichungen von Würfeln, die entstehen, die schon in bereits

57:06.880 --> 57:10.020
existierenden enthalten sind, kurz gehalten.

57:11.400 --> 57:16.200
Aus Erfahrung zeigt sich, dass bei unvollständig definierten

57:16.200 --> 57:19.900
Funktionen das Nelson-Verfahren am schnellsten ist, weil die

57:19.900 --> 57:24.640
Anfangsüberdeckung vom Konsensusverfahren natürlich alle Dortkehrs

57:24.640 --> 57:27.880
berücksichtigen muss, was nicht der Fall ist, zum Beispiel beim Nelson

57:27.880 --> 57:28.420
-Verfahren.

57:29.300 --> 57:33.080
Bei ganz oder fast vollständigen Funktionen ist das Konsensusverfahren

57:33.080 --> 57:34.340
vorteilhaft.

57:36.820 --> 57:38.740
Und so weiter und so fort.

57:38.860 --> 57:42.440
Viele der aktuellen Ansätze, die basieren bei der Minimierung von

57:42.440 --> 57:46.720
Schaltfunktionen mit großer Anzahl von Variablen, basieren natürlich

57:46.720 --> 57:47.680
auf Heuristiken.

57:47.680 --> 57:53.160
Das heißt Heuristiken, die von Experten oder aus Erfahrungswissen

57:53.160 --> 57:58.300
kommen und mit denen man nicht unbedingt immer die minimale Lösung der

57:58.300 --> 58:03.700
Funktion bestimmt, sondern eine beste Lösung, die sehr ähnlich oder

58:03.700 --> 58:07.560
sehr nah an der minimalen Lösung ist, aber mit einem akzeptablen

58:07.560 --> 58:10.100
Rechen - und Speicherbedarf.

58:11.060 --> 58:17.180
So, jetzt haben wir bis jetzt alle diese Methoden angewandt, um eine

58:17.180 --> 58:19.240
einzige Boolsheet-Funktion zu realisieren.

58:19.540 --> 58:22.120
Normalerweise, wenn man eine Schaltung entwirft, dann hat man

58:22.120 --> 58:25.340
irgendwelche Eingangsvariablen in einem System und diese

58:25.340 --> 58:29.960
Eingangsvariablen, die will man nicht nur auf eine einzige Art und

58:29.960 --> 58:35.380
Weise miteinander verknüpfen, um nur ein Ausgangssignal zu erzeugen,

58:35.660 --> 58:38.020
sondern man will vielleicht mehrere Ausgangssignale.

58:38.020 --> 58:43.400
Das heißt, eigentlich hat man es immer mit mehreren Funktionen, gerade

58:43.400 --> 58:46.500
beim Entwurf von integrierten Schaltungen, gegeben.

58:47.400 --> 58:51.760
Eine Anzahl von Eingangsvariablen seien 100, zum Beispiel eines

58:51.760 --> 58:52.780
Mikroprozessors.

58:53.260 --> 58:57.220
Und man will jetzt nicht nur eine einzige Boolsheet-Funktion, nicht

58:57.220 --> 59:01.920
nur eine einzige Ausgangsvariable realisieren und minimieren, sondern

59:01.920 --> 59:07.680
man will auch 30 Funktionen, die alle von diesen unabhängigen

59:07.680 --> 59:09.880
Variablen abhängen, minimieren.

59:10.480 --> 59:17.280
Und da kann man sich vorstellen, dass sehr oft eine sogenannte

59:17.280 --> 59:21.760
Bündelminimierung, also dass man nach einer Lösung sucht, die

59:21.760 --> 59:28.600
kostengünstiger, um alle 30 Funktionen zu realisieren, oft besser bzw.

59:28.960 --> 59:34.340
billiger ist als die Realisierung der jeweiligen Minimalformen dieser

59:34.340 --> 59:35.440
30 Funktionen.

59:36.640 --> 59:37.540
Was bedeutet das?

59:37.660 --> 59:42.940
Das bedeutet eigentlich, alles, was wir bis jetzt kennengelernt haben

59:42.940 --> 59:45.880
für eine einzelne Funktion, müssen wir ein bisschen so anpassen.

59:46.040 --> 59:49.940
Das heißt, wir müssen nach irgendwelchen Themen suchen, die nicht

59:49.940 --> 59:55.060
unbedingt die größten Einsblöcke im KV-Diagramm der Funktion sind oder

59:55.060 --> 01:00:01.500
Nullblöcke, sondern wir müssen nach Blöcke suchen, die vielleicht in

01:00:01.500 --> 01:00:06.120
vielen Funktionen auftauchen, die wir gleichzeitig minimieren wollen.

01:00:07.060 --> 01:00:10.140
Das heißt, es wird versucht, hier mehrere Bool'sche Funktionen

01:00:10.140 --> 01:00:11.320
gemeinsam zu minimieren.

01:00:13.020 --> 01:00:15.800
Implikanten der Funktion, also die müssen nicht unbedingt

01:00:15.800 --> 01:00:20.220
Primimplikanten der Funktion, die kann man dann mehrfach ausnutzen.

01:00:21.380 --> 01:00:26.760
Und das Prinzip wollen wir nur im KV-Diagramm hier beschreiben.

01:00:27.140 --> 01:00:31.920
Und diese Themen, die von vielen Funktionen gleichzeitig benutzt

01:00:31.920 --> 01:00:35.480
werden für die Minimierung, nennt man sogenannte Koppelthemen.

01:00:36.240 --> 01:00:40.060
Und wie bereits erwähnt, die müssen nicht unbedingt Primimplikanten

01:00:40.060 --> 01:00:41.220
einer Funktion sein.

01:00:42.160 --> 01:00:44.760
So, betrachten wir mal ein Beispiel.

01:00:44.760 --> 01:00:48.240
Das heißt, wir haben hier zwei Funktionen U und V.

01:00:49.340 --> 01:00:51.600
Und wir wissen, wie wir diese zwei Funktionen minimieren.

01:00:52.260 --> 01:00:55.520
Das heißt, wenn wir zum Beispiel die Funktion U minimieren, dann ist

01:00:55.520 --> 01:00:59.960
das nichts anderes als A-Quer-C oder C-Quer-D.

01:01:01.120 --> 01:01:03.560
Ja, C-Quer-D oder A-Quer-C.

01:01:05.460 --> 01:01:07.300
Das hier und das hier.

01:01:07.440 --> 01:01:09.440
Das sind Primimplikanten der Funktion.

01:01:09.880 --> 01:01:12.620
Beide sind sogar Kernprimimplikanten, wie wir sehen.

01:01:12.620 --> 01:01:16.080
Und wir brauchen sie beide, um alle Einstellungen der Funktion zu

01:01:16.080 --> 01:01:16.480
überdecken.

01:01:17.240 --> 01:01:22.760
Die Funktion V, man sieht hier, man kann sie angeben, die disjunktive

01:01:22.760 --> 01:01:28.840
Minimalform als A-D, also dieser mittlere Block A-D, beziehungsweise C

01:01:28.840 --> 01:01:29.140
-D.

01:01:29.820 --> 01:01:34.220
Ja, und beide sind auch Kernprimimplikanten der Funktion und die

01:01:34.220 --> 01:01:36.140
überdecken alle Einstellungen der Funktion.

01:01:36.780 --> 01:01:41.180
Jetzt wollen wir die Funktion nicht separat minimieren, ja, weil man

01:01:41.180 --> 01:01:44.700
sieht hier, wenn ich die separat minimiere, dann brauche ich

01:01:44.700 --> 01:01:46.560
eigentlich vier Produktthermie.

01:01:48.000 --> 01:01:52.560
Also nicht zu vergessen, diese Produktthermie bedeuten eigentlich

01:01:52.560 --> 01:01:53.060
Undgatter.

01:01:53.880 --> 01:01:57.720
Das ist ein Undgatter hier, was ich hier brauche, das ist auch ein

01:01:57.720 --> 01:02:00.840
Undgatter, was ich hier brauche und nochmal beide verknüpft über ein

01:02:00.840 --> 01:02:01.080
Oder.

01:02:01.860 --> 01:02:05.480
Hier brauche ich auch zweimal Undgatter und ein Oder.

01:02:08.120 --> 01:02:12.900
So, jetzt gucken wir mal diese KV-Diagramme oder diese zwei Funktionen

01:02:12.900 --> 01:02:16.760
und suchen wir nicht nach Primimplikanten, sondern suchen wir nach

01:02:16.760 --> 01:02:20.780
Blöcke, die gemeinsam oder nach einzeln, die gemeinsam in beiden

01:02:20.780 --> 01:02:21.660
Funktionen sind.

01:02:22.540 --> 01:02:25.060
Und das sind natürlich die Min-Thermie 9 und 11.

01:02:26.140 --> 01:02:29.360
9 und 11 sind in beiden Funktionen.

01:02:29.360 --> 01:02:34.640
Das heißt, wenn ich diesen Block hier bilde, d, c, q, a,

01:02:37.980 --> 01:02:43.020
dann kann ich den nehmen, das ist auch ein Undgatter, dann kann ich

01:02:43.020 --> 01:02:46.480
den nehmen für die Realisierung der Funktion, das ist nur ein

01:02:46.480 --> 01:02:53.340
Undgatter, ja, ich kann den einmal nur hier nehmen und dann schaue ich

01:02:53.340 --> 01:02:57.160
nach, was muss ich noch eigentlich bei der jeweiligen, ich kann

01:02:57.160 --> 01:03:01.720
natürlich gucken, ob es noch andere gemeinsame Blöcke gibt, die ich

01:03:01.720 --> 01:03:04.360
zusammen nutzen kann, aber das ist nicht der Fall.

01:03:05.100 --> 01:03:10.200
Aber wenn ich hier 9 und 11 überdeckt habe, dann sieht man, dass ich

01:03:10.200 --> 01:03:15.980
eigentlich a²c noch brauche und sieht man, dass ich hier nur cd

01:03:15.980 --> 01:03:16.560
brauche.

01:03:16.800 --> 01:03:20.120
Das heißt, die Realisierung von diesen Funktionen mit den

01:03:20.120 --> 01:03:30.140
Koppelthermen würde dann nur drei Produkttherme oder drei Undgatter

01:03:30.140 --> 01:03:35.340
benötigen im Gegensatz zu vier Undgatter, die man bei einer separaten

01:03:35.340 --> 01:03:38.020
Minimierung der Funktion hier brauchen würde.

01:03:39.040 --> 01:03:43.760
So, man sieht hier einen Fall, wo dieser Koppeltherm nicht unbedingt

01:03:43.760 --> 01:03:45.340
Primimplikant der Funktion ist.

01:03:45.440 --> 01:03:50.660
Also dieser Koppeltherm hier, den wir gefunden haben, der ist weder

01:03:50.660 --> 01:03:53.840
Primimplikant der Funktion u noch der Funktion w.

01:03:54.780 --> 01:03:58.900
Aber wenn das der Fall ist, dann nennt man diese Koppelthermie

01:03:58.900 --> 01:04:00.140
Primkoppelthermie.

01:04:00.500 --> 01:04:05.040
Und da gucken wir mal hier diese Funktion u und v.

01:04:05.780 --> 01:04:08.880
Das sind zwei Funktionen, die eingegeben sind auf die Art und Weise,

01:04:09.080 --> 01:04:10.720
also mithilfe von den Einstellungen.

01:04:11.540 --> 01:04:21.360
Und man sieht hier z.B., dass der Block hier c, d-quer, c und a-quer,

01:04:21.860 --> 01:04:27.860
also d-quer, c und a-quer z.B.

01:04:28.220 --> 01:04:29.380
in beiden auftritt.

01:04:30.880 --> 01:04:37.200
Das ist nichts anderes als a-quer, d, c-quer, a-quer, d, c-quer.

01:04:37.200 --> 01:04:40.430
Und das sind natürlich Primimplikanten der jeweiligen Funktionen.

01:04:41.020 --> 01:04:43.100
Die treten in beiden Funktionen auf.

01:04:43.220 --> 01:04:46.840
Das heißt, ich brauche nur ein und-Gatter hier, um beide Thermie für

01:04:46.840 --> 01:04:48.400
beide Funktionen zu realisieren.

01:04:49.940 --> 01:04:53.700
Die anderen sieht man, da habe ich keine weiteren Koppelthermie, die

01:04:53.700 --> 01:04:55.440
ich eigentlich nutzen kann.

01:04:55.740 --> 01:04:57.500
Vielleicht die zwei hier in der Mitte.

01:04:57.760 --> 01:05:00.300
Aber da muss ich die eins und die eins hier realisieren.

01:05:00.440 --> 01:05:02.270
Ist nicht so günstig.

01:05:03.050 --> 01:05:07.810
Das heißt, man sieht hier, dass man hier auch diese Minimierung machen

01:05:07.810 --> 01:05:08.350
kann.

01:05:09.210 --> 01:05:13.870
Oder dass, wenn diese Koppelthermie Primimplikanten beider Funktionen

01:05:13.870 --> 01:05:18.470
sind, dass man sie Primkoppelthermie nennt.

01:05:20.150 --> 01:05:24.730
Okay, allgemeine Problematik, die man hier hat.

01:05:24.830 --> 01:05:28.010
Wir werden sehen bei der Realisierung von Funktionen mit

01:05:28.010 --> 01:05:32.170
programmierbarer Logik, dass wir tatsächlich nach diesen Koppelthermen

01:05:32.170 --> 01:05:32.850
immer suchen.

01:05:33.170 --> 01:05:37.250
Weil wenn wir sie einmal realisiert haben, dann können wir sie nutzen

01:05:37.250 --> 01:05:42.270
bei allen 30 Funktionen, die wir zum Beispiel minimieren oder

01:05:42.270 --> 01:05:43.090
realisieren wollen.

01:05:43.670 --> 01:05:47.450
Die allgemeine Problematik bei der Minimierung, die man hat, ist, dass

01:05:47.450 --> 01:05:50.890
die Anzahl der Primimplikanten oder Primimplikate einer Funktion

01:05:52.030 --> 01:05:55.530
exponentiell mit der Anzahl der Eingangsvariablen übersteigt.

01:05:55.530 --> 01:06:00.870
Also bis zu 3 hoch N durch N Primimplikanten bei N Eingangsvariablen.

01:06:02.130 --> 01:06:05.370
Und insbesondere das Überdeckungsproblem, also die

01:06:05.370 --> 01:06:09.890
Überdeckungsrebelle, die wir hier speziell für den Fall kennengelernt

01:06:09.890 --> 01:06:16.990
haben, das ist ein allgemeines Überdeckungsproblem, das ja MP

01:06:16.990 --> 01:06:18.190
vollständig ist.

01:06:18.450 --> 01:06:23.190
Das heißt, es besteht wenig Hoffnung, dass man einen Algorithmus

01:06:23.190 --> 01:06:28.170
findet, der das Problem in einer Zeit löst, die polynomial mit der

01:06:28.170 --> 01:06:30.010
Anzahl der Eingangsvariablen wächst.

01:06:30.690 --> 01:06:34.150
Das heißt meistens hier bei den Algorithmen hat man exponentielles

01:06:34.150 --> 01:06:37.410
Wachstum der Zeit, die notwendig ist zur Lösung.

01:06:38.070 --> 01:06:41.370
Und worauf man hier tatsächlich zurückgreift, wie ich bereits erwähnt

01:06:41.370 --> 01:06:45.430
habe, heuristische Verfahren, die nicht notwendigerweise minimale

01:06:45.430 --> 01:06:50.250
Lösungen mit akzeptablem Zeit- und Speicherbedarf erzeugen.

01:06:50.250 --> 01:06:54.570
Und die stehen aus Heuristiken und so weiter und so fort.

01:06:54.890 --> 01:06:59.730
Da will ich darüber nicht zu sprechen kommen, sondern ganz kurz auf

01:06:59.730 --> 01:07:02.790
welche Methoden gibt es solche heuristischen Verfahren zur

01:07:02.790 --> 01:07:03.350
Minimierung?

01:07:04.290 --> 01:07:08.570
Natürlich eine ganze Zahl von Methoden, ganz speziell jetzt hier der

01:07:08.570 --> 01:07:09.950
Espresso -Algorithmus.

01:07:10.410 --> 01:07:15.270
Das ist vielleicht der bekannteste Algorithmus, der seit Anfang der

01:07:15.270 --> 01:07:21.770
80er Jahre entwickelt wurde beim Entwurf von Very Large Scale

01:07:21.770 --> 01:07:24.750
Integrated Circuits, also VLSI.

01:07:26.170 --> 01:07:31.950
Und bei diesem Algorithmus, ganz kurz, ich weiß, es ist vielleicht

01:07:31.950 --> 01:07:36.710
nicht so spannend, aber ganz kurz, bei dem Algorithmus geht man von

01:07:36.710 --> 01:07:41.130
einer anderen Datenstruktur zur Repräsentation der Funktionen aus.

01:07:41.770 --> 01:07:44.210
Ja, also wir haben jetzt unterschiedliche Möglichkeiten zur

01:07:44.210 --> 01:07:47.450
Repräsentation der Funktionen und bei diesem Algorithmus wählt man

01:07:47.450 --> 01:07:48.570
noch eine andere.

01:07:49.290 --> 01:07:52.510
Und zwar, das ist die sogenannte Positional Cube Notation.

01:07:53.570 --> 01:07:58.630
Und hier wird ein Produktterm binär kodiert und als Vektor aus Nullen

01:07:58.630 --> 01:07:59.990
und Einsen dargestellt.

01:08:00.790 --> 01:08:06.010
Und der Vektor enthält alle Variablen, erhält man, indem man alle

01:08:06.010 --> 01:08:09.900
Literali des Produktterms Einsen kodiert, wie folgt.

01:08:10.700 --> 01:08:14.860
Das heißt, die Variable, die nicht negiert auftaucht, die wird mit 0,1

01:08:14.860 --> 01:08:17.020
kodiert in einem Produktterm.

01:08:17.100 --> 01:08:21.660
Die Variable, die negiert auftaucht, die wird mit 1,0 kodiert und die

01:08:21.660 --> 01:08:27.880
Variable, die gar nicht auftaucht im Produktterm, die wird mit 1,1

01:08:27.880 --> 01:08:28.280
kodiert.

01:08:29.480 --> 01:08:35.200
Das heißt, man hätte eigentlich für solche Produktterme A, B, C so

01:08:35.200 --> 01:08:36.120
eine Kodierung.

01:08:37.460 --> 01:08:42.000
1,0, 1,0, 1,0, weil alle Variablen nicht negiert auftauchen.

01:08:42.680 --> 01:08:47.200
A, Q, B, C, 1,0, 0,1, 0,1 und so weiter und so fort.

01:08:47.300 --> 01:08:50.920
Hier sieht man, taucht A nicht auf oder hier taucht C nicht auf,

01:08:51.000 --> 01:08:52.640
deshalb die 1,1 und 1,1.

01:08:53.260 --> 01:08:59.580
Wir wissen also, wir haben zwei zweistellige Kodierungen, um die

01:08:59.580 --> 01:09:01.960
Literali in einem Produktterm zu beschreiben.

01:09:01.960 --> 01:09:08.520
Und bei zwei haben wir noch eine Kodierung 0,0 und die würde man so

01:09:08.520 --> 01:09:12.720
interpretieren bei dem System, dass die entsprechende Variable bei 0,0

01:09:12.720 --> 01:09:14.380
einen ungültigen Wert hat.

01:09:14.640 --> 01:09:18.800
Das heißt, man hat hier auch die Möglichkeit, etwas zu Fehlerredundanz

01:09:18.800 --> 01:09:21.300
oder Fehlertoleranz zu realisieren.

01:09:22.140 --> 01:09:27.200
Was macht man dann mit dieser noch anderen Darstellungsweise von

01:09:27.200 --> 01:09:28.000
Produkttermen?

01:09:28.000 --> 01:09:32.980
Das heißt, die Produktterme sind Vektoren aus Nullen und Einsen.

01:09:33.540 --> 01:09:35.720
Die komplette Funktion ist irgendeine Matrix.

01:09:36.720 --> 01:09:41.860
Und da muss man natürlich jetzt irgendwelche Operationen ausführen, um

01:09:41.860 --> 01:09:50.680
aus dieser Matrix auf irgendeine Lösung, auf eine minimale Lösung der

01:09:50.680 --> 01:09:51.500
Funktion zu kommen.

01:09:51.740 --> 01:09:54.360
Nicht unbedingt die minimalste, weil das ein heuristischer

01:09:54.360 --> 01:09:56.480
Algorithmus, wie wir bereits gesagt haben.

01:09:57.280 --> 01:10:01.920
Und was man hier macht bei dem Espresso-Algorithmus ist tatsächlich,

01:10:02.520 --> 01:10:04.260
man definiert solche Operatoren.

01:10:04.540 --> 01:10:09.860
Das heißt, es gibt Operatoren und der Minimierungsablauf ist nichts

01:10:09.860 --> 01:10:14.200
anderes als die Anwendung von diesen Operatoren auf diese

01:10:14.200 --> 01:10:16.300
Datenstrukturen, die man definiert hat.

01:10:17.040 --> 01:10:21.520
Und natürlich die Heuristiken, die hier angewandt werden, ist in

01:10:21.520 --> 01:10:24.660
welcher Reihenfolge welche Operatoren da angewandt werden.

01:10:25.520 --> 01:10:28.120
Und das ist auch natürlich naheliegend.

01:10:28.260 --> 01:10:31.320
In welcher Reihenfolge fasse ich welche Minuterme zusammen?

01:10:32.040 --> 01:10:37.100
Ja, wenn ich überhaupt im KV-Diagramm oder irgendwo was mache.

01:10:37.520 --> 01:10:40.240
Natürlich im KUAN-McCluskey hatten wir eine systematische

01:10:40.240 --> 01:10:43.060
Vorgehensweise, wie man diese Vergleiche durchführt.

01:10:43.640 --> 01:10:48.860
Aber bei großen Funktionen können wir natürlich diese Systematik zwar

01:10:48.860 --> 01:10:53.700
anwenden, aber dann haben wir Lösungen, die unakzeptabel lang dauern

01:10:53.700 --> 01:10:54.160
bzw.

01:10:54.700 --> 01:10:57.180
viel Speicherplatz benötigen.

01:10:58.400 --> 01:11:01.980
So, wenn man also das erledigt hat, das heißt, es gibt alternative

01:11:01.980 --> 01:11:05.560
Methoden oder heuristische Algorithmen zur Minimierung von diesen

01:11:05.560 --> 01:11:09.920
Funktionen, kriegt man am Ende irgendeine Menge von Produktthermen

01:11:09.920 --> 01:11:13.440
oder von Summenthermen, die man natürlich in Hardware realisieren

01:11:13.440 --> 01:11:13.720
will.

01:11:14.380 --> 01:11:17.180
Und der letzte Schritt, was man hier machen muss, ist tatsächlich,

01:11:17.960 --> 01:11:23.340
diese abstrakten Terme, die man bekommt, auf konkrete Bausteine einer

01:11:23.340 --> 01:11:27.860
bestimmten Bausteinbibliothek abzubilden.

01:11:28.040 --> 01:11:32.200
Ich hatte schon oft das Beispiel, wenn ich als Ergebnis der

01:11:32.200 --> 01:11:38.800
Minimierung ein Produkttherm bekomme mit 17 Eingängen, also ein

01:11:38.800 --> 01:11:43.540
Produkttherm mit 17 Literalen, wo ich ein und mit 17 Eingängen

01:11:43.540 --> 01:11:47.000
brauche, aber ich habe sowas nicht in der zugrunde liegenden

01:11:47.000 --> 01:11:50.960
Bibliothek, dann muss ich natürlich diesen Produkttherm mithilfe von

01:11:50.960 --> 01:11:56.920
den zur Verfügung stehenden Gattern in meiner Bibliothek abbilden.

01:11:57.240 --> 01:12:03.220
Also zum Beispiel, keine Ahnung, viermal und-Gatter oder und-Gatter

01:12:03.220 --> 01:12:04.160
mit vier Eingängen.

01:12:04.380 --> 01:12:09.500
Wenn ich die hätte, dann nehme ich mal die vier und dann nochmal einen

01:12:09.500 --> 01:12:13.600
fünften mit dem siebzehnten Eingang und die anderen Eingänge, die

01:12:13.600 --> 01:12:15.880
bleiben wahrscheinlich frei.

01:12:16.040 --> 01:12:17.440
Da muss ich mir was überlegen.

01:12:17.720 --> 01:12:21.200
Bei und könnte ich dort eine 111 mal anlegen.

01:12:21.800 --> 01:12:25.540
Dann habe ich zum Beispiel vier und-Gatter mit vier Eingängen, die ich

01:12:25.540 --> 01:12:29.440
in meiner Bibliothek habe, wo die ersten 16 Variablen, die ich

01:12:29.440 --> 01:12:34.480
verordern, die ich mit und verknüpfen will, eingeschlossen sind.

01:12:34.800 --> 01:12:38.220
Die siebzehnte Variable an dem fünften und-Gatter und die letzten drei

01:12:38.220 --> 01:12:40.620
Eingänge mit Einsen.

01:12:42.180 --> 01:12:44.880
Könnte jeder mir folgen, wie das so aussieht, das Bild?

01:12:46.440 --> 01:12:47.000
Hoffentlich.

01:12:48.000 --> 01:12:50.720
Okay, gut, so viel dazu.

01:12:50.880 --> 01:12:51.540
Gibt es Fragen?

01:12:55.260 --> 01:12:57.740
Dann sind wir mit dem Thema Minimierung fertig.

01:12:58.740 --> 01:13:02.860
Und wir haben bis jetzt gesehen, dass diese Funktionen, die wir

01:13:02.860 --> 01:13:10.460
bekommen, am Ende eigentlich, dass wir sie auf zweistufige Art und

01:13:10.460 --> 01:13:11.320
Weise realisieren.

01:13:11.460 --> 01:13:14.220
Das heißt, entweder haben wir Produktthermen, die müssen wir mit oder

01:13:14.220 --> 01:13:18.300
verknüpfen, im Falle von disjunktiven Formen oder disjunktiven

01:13:18.300 --> 01:13:19.300
Minimalformen.

01:13:19.380 --> 01:13:23.080
Oder wir haben Summenthermen, die müssen wir mithilfe von und-Gatter

01:13:23.080 --> 01:13:25.720
zu Ausgangsvariablen verknüpfen.

01:13:25.980 --> 01:13:30.440
Also die zwei Kategorien von Gattern, die wir bis jetzt verwendet

01:13:30.440 --> 01:13:32.260
haben, waren die und- und oder-Gatter.

01:13:32.480 --> 01:13:36.240
Und wir haben ja zweistufige Realisierungen von den Schaltungen

01:13:36.240 --> 01:13:40.820
kennengelernt, die natürlich sehr günstig sind, was Signallaufzeiten

01:13:40.820 --> 01:13:45.280
vom Eingang zum Ausgang bei Änderungen der Ausgangsvariablen sind.

01:13:46.100 --> 01:13:51.400
So, nun wollen wir jetzt hier noch weitere spezielle Strukturen, also

01:13:51.400 --> 01:13:56.120
spezielle Schaltnetze kennenlernen, die man zur Realisierung von

01:13:56.120 --> 01:13:57.660
Bullshit -Funktionen einsetzen kann.

01:13:58.280 --> 01:14:05.240
Und diese speziellen Strukturen, die sind jetzt nicht die Gatter, die

01:14:05.240 --> 01:14:13.400
ich vorher erwähnt habe, sondern das sind zusammengesetzte

01:14:13.400 --> 01:14:18.540
Komponenten, also zum Beispiel sogenannte Multiplexer, beziehungsweise

01:14:18.540 --> 01:14:23.980
Decoder oder Demultiplexer, Speicherbausteine, mit denen man diese

01:14:23.980 --> 01:14:28.140
Schaltfunktionen implementieren kann und somit die Schaltnetze

01:14:28.140 --> 01:14:33.180
realisieren kann oder sogenannte programmierbare Logikbausteine wie

01:14:33.180 --> 01:14:35.700
PLA, FPLA und PAL.

01:14:37.120 --> 01:14:44.280
Das heißt, man hat jetzt hier eine einfachere und oft eine flexiblere

01:14:44.280 --> 01:14:46.940
Realisierung von der Bullshit-Funktionen.

01:14:47.460 --> 01:14:50.540
Und die Aufgabe, die wir bis jetzt gemacht haben, die Minimierung, wo

01:14:50.540 --> 01:14:53.780
wir versucht haben, immer die Anzahl der Gatter eigentlich zu

01:14:53.780 --> 01:15:00.140
reduzieren, um eine Funktion kostengünstig zu realisieren, die ist

01:15:00.140 --> 01:15:03.780
jetzt nicht mehr gegeben, sondern die Aufgabe der Minimierung ist,

01:15:04.080 --> 01:15:07.820
dass man die Menge von diesen komplexen Strukturen oder speziellen

01:15:07.820 --> 01:15:12.840
Strukturen oder speziellen komplexen Bausteinen reduzieren muss.

01:15:14.060 --> 01:15:18.080
So, und da werden wir einige dieser speziellen Strukturen oder

01:15:18.080 --> 01:15:19.500
Bausteine kennenlernen.

01:15:19.680 --> 01:15:24.660
Der erste Baustein ist ein Multiplexer, also ein MUX, das ist die

01:15:24.660 --> 01:15:29.260
Abkürzung, und das ist ein Baustein mit mehreren Eingängen und einem

01:15:29.260 --> 01:15:29.840
Ausgang.

01:15:30.960 --> 01:15:37.600
Wobei bei N-Steuerleitungen einer der zwei hoch N-Eingängen auf den

01:15:37.600 --> 01:15:38.980
Ausgang durchgeschaltet wird.

01:15:39.780 --> 01:15:44.160
Also eigentlich nur ein Ausgang, mehrere Eingänge und wir können mit

01:15:44.160 --> 01:15:47.580
Steuereingängen steuern, welcher Eingang auf den Ausgang

01:15:47.580 --> 01:15:48.680
durchgeschaltet wird.

01:15:49.580 --> 01:15:53.240
Und die haben eine spezielle Bezeichnung, also wenn wir zum Beispiel N

01:15:53.240 --> 01:16:01.760
-Steuerleitungen haben, dann haben wir zwei hoch N zu eins

01:16:01.760 --> 01:16:02.520
Multiplexer.

01:16:02.640 --> 01:16:07.300
Also mit N-Steuerleitungen können wir natürlich zwei hoch N-Eingängen

01:16:07.300 --> 01:16:12.340
selektieren und da wir nur einen Ausgang haben, ist die Bezeichnung

01:16:12.340 --> 01:16:13.500
dann zwei hoch N.

01:16:13.600 --> 01:16:18.440
Einer der zwei hoch N-Eingänge wird auf den Ausgang geschaltet.

01:16:18.700 --> 01:16:20.140
Also eins aus zwei hoch N.

01:16:20.740 --> 01:16:22.060
Das wollen wir gleich sehen.

01:16:23.120 --> 01:16:30.940
Das heißt, das ist zunächst mal eine Box und diese Box wollen wir eine

01:16:30.940 --> 01:16:33.860
2 zu 1 Box zunächst mal kennenlernen.

01:16:35.040 --> 01:16:39.620
Das heißt, N ist gleich 1, wir haben einen Steuereingang

01:16:45.790 --> 01:16:54.670
und wir wissen, dass wir einen Ausgang A haben und diesen

01:16:54.670 --> 01:16:57.030
Steuereingang will ich S nennen.

01:17:05.930 --> 01:17:06.670
Das nervt.

01:17:12.480 --> 01:17:16.080
Und wenn wir einen Steuereingang haben, dann bedeutet das, dass wir

01:17:16.080 --> 01:17:22.120
zwei Eingänge haben und diese Eingänge will ich E0 und E1 nennen.

01:17:23.600 --> 01:17:25.840
Und was sagt die Definition hier?

01:17:26.220 --> 01:17:32.000
Die Definition von diesem Multiplexer sagt, du hast hier einen

01:17:32.000 --> 01:17:36.040
Steuereingang und dieser Steuereingang beeinflusst, welcher Eingang

01:17:36.040 --> 01:17:38.120
auf den Ausgang geschaltet werden soll.

01:17:38.860 --> 01:17:42.500
Nehmen wir mal an, wir wollen jetzt zum Beispiel, wenn S gleich 0,

01:17:43.560 --> 01:17:47.580
wenn S gleich 0, wollen wir, dass E0 auf dem Ausgang erscheint.

01:17:48.260 --> 01:18:01.340
Also S gleich 0, da wollen wir, dass A gleich E0 sein ist und wenn S

01:18:01.340 --> 01:18:14.580
gleich 1, wollen wir, dass A1 auf dem Ausgang erscheint.

01:18:16.140 --> 01:18:17.820
E1 auf dem Ausgang erscheint.

01:18:18.580 --> 01:18:25.540
Und diese Werte, die die Steuervariable S annimmt hier, die habe ich

01:18:25.540 --> 01:18:26.860
jetzt kurz hier eingetragen.

01:18:27.020 --> 01:18:33.000
Das heißt, ich weiß, wenn mein Steuereingang 0 ist, dann ist der

01:18:33.000 --> 01:18:33.940
Eingang hier aktiv.

01:18:34.240 --> 01:18:37.180
Wenn mein Steuereingang 1 ist, dann ist der Eingang hier aktiv.

01:18:38.260 --> 01:18:41.840
Jetzt, wenn wir das hier haben, wer von euch kann mir jetzt sagen,

01:18:42.060 --> 01:18:44.600
welche Bulschi-Funktion realisieren wir eigentlich dadurch?

01:18:55.230 --> 01:18:55.670
Ja.

01:18:58.250 --> 01:19:00.890
Also ich suche die Bulschi-Funktion A.

01:19:02.130 --> 01:19:06.270
Ist gleich, du hast deine Hand hochgehoben, oder?

01:19:10.790 --> 01:19:11.450
Lauter.

01:19:13.510 --> 01:19:14.170
Äquivalenz.

01:19:16.490 --> 01:19:20.310
Kann sein, muss ich mal rechnen, aber es ist zu heiß, um das zu

01:19:20.310 --> 01:19:20.650
rechnen.

01:19:20.730 --> 01:19:23.710
Aber das ist nicht die Antwort, die ich erwarte.

01:19:25.530 --> 01:19:31.390
Naja, also wenn S gleich 0, dann E0 und wenn S gleich 1, E1, ist es

01:19:31.390 --> 01:19:33.810
dann nicht so etwas wie S1 quer?

01:19:34.490 --> 01:19:43.310
Ist es dann nicht S2 E0, weil eigentlich S2 A0 implikant der Funktion

01:19:43.310 --> 01:19:47.210
ist, oder S und E1.

01:19:51.330 --> 01:19:57.450
Also wenn S0 gleich 0 ist, dann verschwindet der zweite Term und dann

01:19:57.450 --> 01:20:02.030
bleibt E0 und wenn S1 gleich 1, verschwindet der erste Term und dann

01:20:02.030 --> 01:20:02.830
habe ich E1.

01:20:04.030 --> 01:20:06.650
Natürlich können wir die Funktion jetzt in einer Funktionstabelle

01:20:06.650 --> 01:20:12.770
aufstellen, mit drei Eingangsvariablen S und E0 und E1 und minimieren

01:20:12.770 --> 01:20:14.890
und schauen, ob wir auf den ersten Term kommen.

01:20:15.750 --> 01:20:18.950
So, aber das ist eigentlich die charakteristische Gleichung hier für

01:20:18.950 --> 01:20:20.770
dieses Element hier.

01:20:21.530 --> 01:20:25.430
Und das ist jetzt nur ein 2 zu 1 Multiplexer.

01:20:25.730 --> 01:20:29.690
Das ganze natürlich ist allgemein, weil wir haben gesagt, wir haben N

01:20:29.690 --> 01:20:33.490
Steuereingänge, das heißt wir gehen jetzt einen Schritt weiter und wir

01:20:33.490 --> 01:20:39.170
sagen, wir haben zwei Steuereingänge, S0 und S1 und wenn ich zwei

01:20:39.170 --> 01:20:43.230
Steuereingänge habe, dann kann ich vier Eingänge auf den Ausgang

01:20:43.230 --> 01:20:45.990
durchschalten.

01:20:46.310 --> 01:20:52.130
Also ich habe hier vier Eingänge, E0 bis E3 und ich habe hier auch

01:20:52.130 --> 01:20:57.130
Nummern aufgeschrieben und diese Nummern, die geben mir die Codierung,

01:20:57.330 --> 01:20:59.770
die an den Steuervariablen anliegt.

01:21:00.430 --> 01:21:06.210
Das heißt S0 gibt mir 00, S1 gibt mir 01, wobei S1 eine höhere

01:21:06.210 --> 01:21:11.410
Stellenwertigkeit hat, also S1, S0 und so weiter und so fort.

01:21:11.930 --> 01:21:19.750
Das heißt meine Funktionalität von diesem Baustein ist wie folgt, wenn

01:21:19.750 --> 01:21:26.150
S0 und S1 0 sind, dann wird am Ausgang E0 stehen.

01:21:27.130 --> 01:21:35.390
Wenn S1 eine 0 ist und S0 eine 1 ist und S1 eine 0 ist, das wäre der

01:21:35.390 --> 01:21:40.650
Eingang 1, wenn ich das hier als Dualzahl interpretiere, also S1, S0,

01:21:41.290 --> 01:21:42.950
der Eingang 1 ist am Ausgang.

01:21:43.530 --> 01:21:49.450
Wenn ich eine 1,0 hier habe, also S1 gleich 1 und S0 gleich 0, dann

01:21:49.450 --> 01:21:57.210
ist A gleich E2 und wenn ich an diesen Steuereingängen ein 1,1 habe,

01:21:57.370 --> 01:22:01.590
dann wird der dritte Eingang, also der Eingang mit der 3 hier auf den

01:22:01.590 --> 01:22:04.570
Ausgang geschaltet, also A ist gleich E3.

01:22:05.970 --> 01:22:07.170
Was bedeutet das?

01:22:07.230 --> 01:22:09.310
Wie kann ich dieses Verhalten hier auch beschreiben?

01:22:09.490 --> 01:22:11.350
Auf die gleiche Art und Weise von vorher.

01:22:12.970 --> 01:22:17.930
Also praktisch so die charakteristische Gleichung von so einem

01:22:17.930 --> 01:22:18.670
Multiplexer.

01:22:18.750 --> 01:22:20.850
Was kann ich hier schreiben für die Variable A?

01:22:24.070 --> 01:22:38.570
Für die Variable A ist natürlich S1 nicht und S0 nicht mit E0 oder S1

01:22:38.570 --> 01:22:53.650
quer S0 und E1 oder S1, S0, Quer und E2 oder S1, S0 und E3.

01:22:56.850 --> 01:23:01.230
Und das ist jetzt nicht ein Baustein, was aus dem Nichts gekommen ist,

01:23:01.390 --> 01:23:04.490
sondern das ist ein Baustein, was wir tatsächlich realisieren können

01:23:04.490 --> 01:23:07.190
mit Bausteinen, mit Gattern, die wir kennengelernt haben.

01:23:07.750 --> 01:23:10.870
Das heißt eigentlich, wir haben zwei Variablen, das sind unsere

01:23:10.870 --> 01:23:14.570
Steuervariablen und die eine Steuervariable heißt S0.

01:23:17.210 --> 01:23:22.890
Und wir sehen, wir brauchen oft die Negation von S0, deshalb auch hier

01:23:22.890 --> 01:23:24.390
die Negation von S0.

01:23:25.250 --> 01:23:32.810
Wir haben auch S1 und wir brauchen oft auch die Negation von S1,

01:23:32.930 --> 01:23:36.030
deshalb hier auch S1.

01:23:36.870 --> 01:23:38.350
Und was haben wir hier?

01:23:38.550 --> 01:23:44.950
Wir haben zunächst mal ein UND-Gatter, das ist nichts anderes als S0,

01:23:45.430 --> 01:23:50.730
S1 und E0.

01:23:51.790 --> 01:23:53.710
Also das ist der Eingang E0.

01:23:55.130 --> 01:24:08.990
Dann haben wir ein zweites UND-Gatter, das ist S1-Quer, S0, S1-Quer

01:24:08.990 --> 01:24:12.430
und E1.

01:24:13.090 --> 01:24:18.470
Dann haben wir ein drittes UND-Gatter, das ist natürlich S1,

01:24:22.010 --> 01:24:27.770
S0 -Quer und E2.

01:24:28.890 --> 01:24:43.810
Und wir haben ein drittes, was nichts anderes als S1, S0 und E2.

01:24:45.030 --> 01:24:47.370
Und das Ganze ist natürlich hier

01:24:52.670 --> 01:25:02.770
mit oder, danke dir, das ist natürlich E3 und wir bekommen hier unser

01:25:02.770 --> 01:25:03.170
A.

01:25:04.130 --> 01:25:11.230
Und dieser Block hier

01:25:16.630 --> 01:25:19.690
ist unser Multiplexer.

01:25:20.130 --> 01:25:26.670
Das ist ja ein 4 zu 1 Multiplexer, zwei Steuereingänge, vier Eingänge

01:25:26.670 --> 01:25:30.050
und je nachdem, wie wir die hier verschalten, bekommen wir eins dieser

01:25:30.050 --> 01:25:31.250
Eingänge auf den Ausgang.

01:25:32.590 --> 01:25:36.690
Das heißt, man sieht hier, warum man das auch komplexe Bausteine oder

01:25:36.690 --> 01:25:38.110
spezielle Strukturen nennt.

01:25:38.210 --> 01:25:41.750
Das heißt, man hat irgendein Muster hier und dieses Muster kann ich

01:25:41.750 --> 01:25:47.010
immer wieder benutzen, um solche Funktionen zu realisieren.

01:25:47.330 --> 01:25:49.910
Jetzt wollen wir gucken, wie man das tatsächlich macht.

01:25:50.230 --> 01:25:53.490
Wie man so eine Funktion mithilfe von einem Multiplexer realisiert.

01:25:53.610 --> 01:25:58.930
Nehmen wir mal an, wir hätten die Funktion F ist gleich A-Quer C oder

01:25:58.930 --> 01:26:01.130
B -Quer C oder A-B-C-Quer.

01:26:01.890 --> 01:26:05.090
Man stellt eine sogenannte Implementierungsstabilität und sagt, ich

01:26:05.090 --> 01:26:08.350
will zum Beispiel das B und C meine Steuereingänge.

01:26:09.190 --> 01:26:14.150
Das heißt, wenn ich eine Funktion mit N plus 1 Variablen habe, dann

01:26:14.150 --> 01:26:20.930
kann ich zum Beispiel N Variablen nehmen, um die unterschiedlichen

01:26:20.930 --> 01:26:22.970
Eingänge zu realisieren.

01:26:23.250 --> 01:26:29.170
Also hier drei Variablen, deshalb zwei als Steuereingänge.

01:26:29.930 --> 01:26:33.650
Und diese Steuereingänge, die brauchen ja diese Kombinationen, die wir

01:26:33.650 --> 01:26:34.590
vorher gesehen haben.

01:26:34.750 --> 01:26:36.950
Also 00, 01, 10, 11.

01:26:38.150 --> 01:26:39.090
Was bleibt hier?

01:26:39.210 --> 01:26:44.770
Es bleibt eine andere Variable, also die Restvariable der Funktion A.

01:26:45.450 --> 01:26:49.230
Und in dieser Implementierungsstabilität gehe ich jetzt hin und

01:26:49.230 --> 01:26:51.630
bestimme den Wert der Funktion

01:26:54.910 --> 01:26:56.430
für all diese Belegungen.

01:26:56.570 --> 01:27:02.910
Also wenn C und B gleich 0 sind, dann sehen wir C und B gleich 0.

01:27:03.070 --> 01:27:05.310
Das heißt, der ist 0, der ist 0 und der ist 0.

01:27:05.430 --> 01:27:07.950
Dann ist die Funktion unabhängig von A 0.

01:27:08.150 --> 01:27:11.890
Also bei A gleich 0 und bei A gleich 1 ist die Funktion 0.

01:27:12.490 --> 01:27:16.370
Und insgesamt kann ich sagen, ich habe eine Funktion G hier, die ist

01:27:16.370 --> 01:27:16.690
0.

01:27:18.450 --> 01:27:24.190
Wenn C gleich 0 und B gleich 1, C gleich 0, der wird 0 und der wird 0.

01:27:24.910 --> 01:27:30.810
B gleich 1, der wird nicht ganz 0, sondern der ist abhängig von A.

01:27:30.970 --> 01:27:33.390
Also wenn A gleich 0 ist, dann ist es 0.

01:27:33.390 --> 01:27:35.350
Wenn A gleich 1, dann ist es 1.

01:27:35.470 --> 01:27:40.890
Also insgesamt bei der Belegung der Eingangsvariablen C und B, habe

01:27:40.890 --> 01:27:43.730
ich eigentlich für diese Restfunktion A.

01:27:45.530 --> 01:27:52.090
Wenn C und B gleich 1, 0 sind, das heißt, C ist gleich 1.

01:27:52.950 --> 01:27:55.750
Aha, C ist gleich 1.

01:27:56.890 --> 01:27:59.510
C ist gleich 1, dann verschwindet der Term.

01:27:59.770 --> 01:28:02.050
B ist gleich 0, dann ist es 1.

01:28:02.230 --> 01:28:07.650
Also da habe ich auf jeden Fall eine 1, weil 1 oder irgendetwas ist 1.

01:28:07.870 --> 01:28:12.090
Also insgesamt hat die Funktion den Wert 1 und das gleiche auch für A

01:28:12.090 --> 01:28:12.810
gleich 1.

01:28:13.030 --> 01:28:15.230
Also insgesamt habe ich die konstante Funktion 1.

01:28:16.150 --> 01:28:19.390
Im letzten Fall können wir auf die gleiche Art und Weise sehen, dass

01:28:19.390 --> 01:28:24.830
die Funktion bei C, B gleich 1, 1, A gleich 0, 1 ist und bei A gleich

01:28:24.830 --> 01:28:25.790
1, 0 ist.

01:28:25.930 --> 01:28:30.370
Und somit ist eigentlich diese Restfunktion G nichts anderes als A

01:28:30.370 --> 01:28:30.490
quer.

01:28:31.610 --> 01:28:32.690
Was bedeutet das?

01:28:32.770 --> 01:28:37.130
Das bedeutet eigentlich bei der Belegung 0, 0 muss ich 0 hier am

01:28:37.130 --> 01:28:38.510
Ausgang durchschalten.

01:28:38.890 --> 01:28:43.970
Bei der Belegung der Steuervariablen 0, 1 muss ich A, bei 1, 0 muss

01:28:43.970 --> 01:28:46.170
ich 1 und bei 1, 1 A quer.

01:28:46.730 --> 01:28:51.070
Das heißt, wenn wir das in Multiplexer realisieren, dann sind das die

01:28:51.070 --> 01:28:55.990
zwei Variablen C und B und das sind die Eingänge und bei 0, 0, das ist

01:28:55.990 --> 01:28:56.410
der 0.

01:28:56.670 --> 01:28:58.510
Eingang, da müssen wir eine 0 tun.

01:28:59.390 --> 01:29:05.390
Bei 0, 1, das ist der Eingang der mit 1 hier, also die Belegung C, B,

01:29:05.550 --> 01:29:09.510
0, 1, deshalb der hier, da müssen wir eine A tun.

01:29:10.430 --> 01:29:19.050
Bei 1, 0 müssen wir eine 1 tun und bei 1, 1 müssen wir A quer tun.

01:29:19.910 --> 01:29:25.530
Das heißt, mit Hilfe von diesem 4 zu 1 Multiplexer können wir diese

01:29:25.530 --> 01:29:29.770
Funktion realisieren und zwar ist das nur eine Realisierung, bei der

01:29:29.770 --> 01:29:33.490
ich nur willkürlich jetzt gesagt habe, C und B sind meine

01:29:33.490 --> 01:29:34.330
Steuervariablen.

01:29:35.510 --> 01:29:39.090
Ich kann sagen, ich will A und B als Steuervariablen nehmen.

01:29:39.690 --> 01:29:43.650
Dann habe ich hier A und B, das gleiche Spiel und ich sehe, ich kriege

01:29:43.650 --> 01:29:45.790
hier C, C, C und C quer.

01:29:46.310 --> 01:29:49.710
Das heißt, die ersten drei Eingänge hier müssen mit C verbunden werden

01:29:49.710 --> 01:29:52.630
und der dritte Eingang muss mit C quer verbunden werden.

01:29:53.510 --> 01:29:56.410
Und auf die Art und Weise habe ich natürlich eine zweite Realisierung

01:29:56.410 --> 01:30:01.270
der Funktion, bei der die Steuervariablen hier anders sind als die

01:30:01.270 --> 01:30:03.090
Realisierung von vorher.

01:30:03.950 --> 01:30:08.550
Okay, ich glaube, ich muss aufhören, sonst werden viele Leute sauer

01:30:08.550 --> 01:30:08.790
hier.

01:30:09.730 --> 01:30:11.810
Ich bedanke mich heute für die Aufmerksamkeit.

01:30:12.050 --> 01:30:15.490
Am Donnerstag machen wir eine Übung und mit der Vorlesung machen wir

01:30:15.490 --> 01:30:16.950
weiter dann am nächsten Dienstag.

01:30:17.870 --> 01:30:21.030
Noch einen schönen heißen Tag und bis Dienstag.