Ich begrüße euch herzlich zur heutigen Vorlesung.
Wir machen weiter mit dem Stoff.
Und zwar das letzte Mal haben wir eine neue Möglichkeit kennengelernt,
Schaltfunktionen oder Bulschion-Schaltfunktionen zu beschreiben, und
zwar mithilfe von einem KV-Diagramm, was als eine Grundlage auch für
die Minimierung von diesen Funktionen auch dient.
Und wir wissen, wie solche KV-Diagramme konstruiert werden.
Das heißt, Ausgangspunkt sind zunächst mal zwei Felder, wo eine
einzige Variable, die Variable hat zwei Belegungen, 0 und 1, die sind
hier in diesen Feldern angegeben.
Vor zwei Variablen wissen wir, dass wir insgesamt vier Belegungen der
zwei Variablen haben.
Das heißt, wir haben ja vier Felder.
Das heißt, wir spiegeln zunächst mal um diese Achse hier, dann
bekommen wir zwei neue Felder, wo die neue Variable B den Wert 1 hat.
Natürlich in den ursprünglichen Feldern hier hat die Variable B den
Wert 0.
Und in diesen Feldern schreiben wir diese Indizes.
Die Indizes sagen uns etwas über die Belegung der Eingangsvariablen.
Das heißt, wenn wir hier B, A haben, B ist die zweite Variable, dann
haben wir hier 1, 0 und 1, 1.
Das heißt, das liegt in B und liegt nicht in A.
Und deshalb ist es eine 2.
Während hier, die liegen beide in A und in B, also im Hoheitsbereich
von A und in B.
Und deshalb die Belegung 1, 1 der Variablen.
1, 1 interpretiert als Dezimal, ist es eine 3.
Für eine dritte Variable spiegeln wir um die nächste Achse.
Also zum Beispiel, wir haben vorher jetzt um die horizontale Achse
gespiegelt.
Wir spiegeln um die vertikale Achse.
Bei drei Variablen haben wir acht Belegungen der Eingangsvariablen.
Das heißt, acht Felder.
Und entsprechend kann man hier natürlich die Belegungen der Variablen
anhand von diesen Indizes ablesen.
Und das ist immer ganz einfach.
Das heißt, wenn ich jetzt hier die 5 nehme, also Feld 5 liegt in C,
liegt nicht in B und liegt in A.
Also 1, 0, 1, das ist die 5.
Und das können wir auch für eine weitere Variable, also mit vier
Funktionen, mit vier Variablen, haben 16 unterschiedliche Belegungen
der Eingangsvariablen.
Auf die gleiche Art und Weise können wir die Nummern der Felder
bekommen, beziehungsweise wir wissen, dass diese Nummern aus den
Feldern entstehen.
Also die 8 hier entsteht zum Beispiel aus dem Feld, was durch die
Spiegelung zu dem Feld 8 geführt hat.
Das ist Feld 0.
Wir haben da gespiegelt und die 0, da ist das hier entstanden.
Und man sieht hier, man addiert immer ein Offset zu diesen Indizes und
dieses Offset ist immer 2 hoch N minus 1.
Das heißt, ich habe hier eine Funktion mit vier Variablen.
Mein N ist 4.
Ich addiere also ein Offset immer von 2 hoch 3, also 2 hoch N minus 1,
2 hoch 3 ist 8.
Und dann bekomme ich die Indizes in den neun Feldern.
Man sieht, 2 ist spiegelbildlich zu 10.
Also 2 plus 8 ist 10, 3 plus 8 ist 11, 7 plus 8 ist 15, 6 plus 8 ist
14, 4 spiegelbildlich zu der 12, 5 zu 13 und so weiter und so fort.
Und das ist natürlich sehr wichtig, weil wir haben ja gesehen, dass
die Minimierung darauf basiert, dass wir möglichst große Blöcke von
Einsen beziehungsweise auch von Nullen im KV-Diagramm finden.
Zu diesen großen Blöcken gehören natürlich Produktthermie oder
Summenthermie mit möglichst wenigen Laterali, also Kurzi,
Produktthermie oder Summenthermie.
Und das ist, was wir wollen.
Ja, das ist, was wir wollen bei der Minimierung.
So, nun können wir das Spiel weitermachen.
Eine Funktion mit fünf Variablen.
Da sieht man hier zum Beispiel die 24 ist spiegelbildlich zu der 8 und
wir addieren hier ein Offset von 2 hoch 4, also von 6 sehen.
Deshalb 8 plus 16, 24.
Man sieht hier, dass zum Beispiel die 27 spiegelbildlich zu der 11, 11
plus 16 ist 27 und so weiter und so fort.
Ganz wichtig bei der Minimierung sind natürlich solche Felder immer zu
identifizieren, die spiegelbildlich zueinander sind.
Ja, man kann hier sehen, zum Beispiel 1 und 5 sind spiegelbildlich
zueinander.
Das heißt, wenn ich hier zwei Einzelne habe, zwei Minthermie, Mintherm
1 und Mintherm 5, dann wissen wir, die können wir zusammenfassen zu
einem größeren Block, also zu einem Implikanten der Funktion, der
nichts anderes als b quer a ist.
Und das ist auch nochmal, ich schreibe es mal hier.
Also Mintherm 1 ist nichts anderes als c quer b quer a.
Und das sieht man, das liegt nicht in c, nicht in b, aber in a.
Mintherm 5, das liegt in c, das heißt ein c, das liegt nicht in a,
also ein b quer.
Und das liegt nicht in b und das liegt in a.
Ja, und man sieht hier, diese zwei Minthermie, die unterscheiden sich
in einer Variable c quer.
Und wenn ich diese zwei Termine disjunktiv miteinander verknüpfe, dann
kommt b quer a und b quer a ist nichts anderes als der Block hier.
Das heißt, der Block, der nicht in b ist, weil b ist unten und oben
ist nicht b, aber in a.
Also der Durchschnitt von nicht b und a ist mein Block hier.
Und das ist das komplette Prinzip, was wir nutzen.
Und natürlich, je größer diese KV-Diagramme werden, desto komplexer
wird es, diese spiegelbildlichen Felder zu identifizieren.
Das heißt z.B.
hier, wenn ich jetzt hier 1 und 3, die sind auf die gleiche Art und
Weise spiegelbildlich zueinander.
Aber wenn ich hier 1 und hier 1 und auch auf der anderen Seite hier
bei 19 und 17 auch 1 in habe, dann kann ich natürlich das zu einem,
wenn dort 1 in sind, Primimplikanten oder Implikanten der Funktion
zusammenfassen.
Und man kann es versuchen, hier einen Block bzw.
einen Term zu bilden, der das beschreibt.
Und man sieht hier, dieser grüne Block, der liegt komplett nicht in d.
Ja, also das ist oben, d ist unten, also d quer.
Der liegt auch nicht in c, deshalb ein c quer.
Der liegt sowohl in b als auch in b quer, passt nicht.
Der liegt sowohl in e als auch in e quer, aber in a.
Ja, das heißt, der Block, der hier zu diesem grünen oder der Term, der
zu der der Produktterm, der zu diesem grünen Block gehört, ist nichts
anderes als d quer, c quer, a.
Und wenn die, wenn ihr es nicht schafft, einen solchen Ausdruck zu
bilden, dann habt ihr falsch zusammengefasst im KV-Diagramm.
Ja, das heißt, wenn man jetzt hier auf die Idee kommen könnte oder
kommt, ja, zu sagen, lass uns mal hier, nehmen wir mal an, wir hätten
hier eine 1, 1, 1, 1, 1, 1 und jetzt kommt einer auf die schlaue Idee
und sagt, das will ich jetzt hier zusammenfassen.
Das können wir natürlich jetzt hier nicht auf die Art und Weise als
Produktterm beschreiben.
Auf der einen Seite wissen wir, dass Implikanten der Funktion 2 hoch K
einzeln haben.
Ja, das heißt, hier haben wir 6 einzeln, aber kein zweier Potenz.
Aber wenn man jetzt versucht, hier einen Ausdruck zu bilden, das ist
sowohl in e als auch nicht in e, das ist nicht in c, das ist in b,
aber in d und nicht in d, das passt nicht.
Also da kommt kein Ausdruck hier, was tatsächlich das Ganze hier
beschreibt.
So, und natürlich solche Zusammenfassungen sind entscheidend, wie ich
bereits gesagt habe.
Das heißt, man muss immer hier gucken, das heißt, wenn ich hier
überall Einsen oder Nullen habe, dann kann ich natürlich diese Blöcke
zusammenfassen, weil die sind symmetrisch zueinander bezüglich der
Symmetrie -Achse höchster Ordnung.
Und die Symmetrie-Achse höchster Ordnung ist die Achse, um die ich das
letzte Mal gespiegelt habe.
Und das letzte Mal haben wir um diese Achse hier gespiegelt, also von
4 auf 5.
Das heißt, die sind spiegelbildlich zueinander.
Jetzt nimmt man hier diese Felder hier in diesem 4er-KV-Diagramm, die
sind auch spiegelbildlich zueinander, weil das ist der Bereich b quer
und a quer.
Das ist alles, was nicht in b und nicht in a liegt.
Das heißt, in dem KV-Diagramm sind sie hier.
Und wenn ich jetzt hier bei den spiegelbildlichen Feldern auch eins
beispielsweise habe, die spiegelbildlich sind das dann die 20, 28, 16
und 24, dann habe ich auch einen Term, der nach wie vor b quer, a quer
heißt.
Das heißt, das ist alles, was nicht in b liegt, oben und unten, und
alles, was nicht in a liegt.
Das ist mein Implikant, wenn ich dort eins in hätte.
Auf das gleiche Prinzip, das ist hier a und b.
Und wenn die Felder hier zum Beispiel mit 1 belegt werden, also die
Funktionswerte bei solchen Belegungen 1 sind und die Funktionswerte
bei den Belegungen 19, 23, 27 und 31 auch 1 sind, dann kann ich das
zusammenfassen insgesamt zu einem Term b a.
Das heißt, dieser Orangeny-Teil ist nach wie vor b a hier im
erweiterten KV-Diagramm.
Okay, und das letzte Mal haben wir gesagt, okay, wie geht die
Minimierung vor?
Oder wie minimieren wir Funktionen im KV-Diagramm?
Wir tragen die Funktion in das KV-Diagramm, das ist ziemlich einfach.
Wir gehen zum Beispiel von der Funktionstabelle aus und wir wissen,
die Nummern im KV-Diagramm gehören zu den Belegungen, also zu den
Zeilen in der Funktionstabelle.
Oder wir können natürlich hingehen und sagen a quer, c quer, also das
ist alles, was nicht in a und nicht in c, das sind diese Felder und
das ist ein Implikant der Funktion bei dieser disjunktiven Form.
Deshalb kommen hier vier 1 hin.
ac, das ist alles, was in a und in c, das sind diese Felder hier, 5,
7, 13, 15 und da tragen wir hier die 1 hin.
Und a quer, b quer, das sind die Ecken, also das ist die 0, die 4, die
8 und 12 und dann tragen wir unsere Funktionen dort ein und versuchen
wir möglichst große 1-Blöcke in dem Fall zu bilden.
Und man sieht hier, ein 1-Block ist natürlich das hier, a quer, c
quer, der andere ist a, c, dann haben wir unsere Ecken, das sind a
quer, b quer und natürlich haben wir hier 4, 5, können wir
zusammenfassen mit 12, 13, das heißt, da bekommen wir c, b quer, das
ist alles, was in c, b quer ist.
Ja, da sieht man hier, da können wir die Primimplikanten ablesen und
man sieht an dem Beispiel, dass wir natürlich mehr Primimplikanten
haben, als jetzt in der disjunktiven Form hier angegeben ist.
Und somit haben wir den ersten Schritt der Minimierung gelöst.
Das heißt, wir haben alle Primimplikanten der Funktion bestimmt.
Der zweite Schritt ist, dass wir aus dieser Menge von Primimplikanten
eine irredundante Menge finden, mit der wir alle Einstellen der
Funktion überdecken.
Und da sehen wir, dass wir hier zwei Primimplikanten unbedingt
aufnehmen müssen in unserer Minimalform.
Das ist zum Beispiel der blaue und der grüne hier, weil 2 und 10, 7
und 15, die werden nur durch diese zwei Blöcke oder durch diese
Primimplikanten überdeckt.
Das heißt, die nennen wir Kernprimimplikanten.
Ja, und was bleibt übrig?
Es bleiben übrig nur die 4 und 12.
Und man sieht hier, um die 4 und 12 zu überdecken, habe ich zwei
Möglichkeiten.
Entweder nehme ich den roten Primimplikanten oder ich nehme den grauen
Primimplikanten.
Das heißt, die eine Minimalform, die ich bekomme, wenn ich den roten
nehme, ist A-Quer, C-Quer, AC, B-Quer, C und die andere, wenn ich den
grauen nehme, ist das dann A-Quer, C-Quer oder AC, die
Kernprimimplikanten und dann der andere hier.
Natürlich an der Stelle, ohne weitere Angaben, können wir nicht
entscheiden, welche dieser Minimalformen, das sind zwei disjunktive
Minimalformen, und wir wissen, Minimalformen sind nicht eindeutig wie
Normalformen.
Das heißt, ohne weitere Angaben können wir an der Stelle nicht sagen,
welche kostet günstiger.
Wenn wir sagen zum Beispiel, die Realisierung von einer Negation
kostet Geld, dann ist es klar, dass die Form hier insgesamt weniger
kostet als die Form hier, weil ich muss hier Negationen von A und B
bilden.
Aber das ist auch nicht immer so eindeutig, weil zum Beispiel hier,
ich muss die Negation von A bilden, aber die Negation von A muss ich
sowieso bilden, um A-Quer, C-Quer zu bestimmen.
Das heißt eigentlich, wenn die Kostenfunktion hier gleich ist, dann
wären die zwei wahrscheinlich auch gleich berechtigt oder würden
gleich viel kosten.
Okay, so viel dazu, das hatten wir das letzte Mal.
Nun wollen wir gucken, wie das Ganze funktioniert für die Bestimmung
von konjunktiven Minimalformen.
Die Vorgehensweise ist die gleiche.
Das heißt, wir betrachten jetzt statt der Einsen die Nullen und statt
große Einsblöcke im KV-Diagramm versuchen wir zu bilden, versuchen wir
möglichst große Nullblöcke zu bilden und dann die zu diesen
Nullblöcken gehörenden Implikate zu finden, also die Summenthermie zu
finden.
Und das wollen wir, das brauchen wir hier nicht, das wollen wir anhand
eines Beispiels.
Also auf der Folie davor war beschrieben, wie die Vorgehensweise ist,
aber ich glaube, das erklären wir anhand von dem Beispiel.
Das könnt ihr auch den Rest nachlesen.
Man sieht hier eine Funktion gegeben durch ihre Maxthermie, also durch
ihre Nullstellen.
Das sind 1, 3, 2, 10, 4, 6 und 14, 15.
Und da sieht man hier ein paar Einkreisungen von Blöcken, die man
bilden kann.
Also zum Beispiel 1 und 3, das ist Maxtherm 1.
Und von Maxtherm 1 wissen wir, wir schreiben alle Variablen, das ist
ein Summentherm.
Da haben wir ein D hier, das ist ein Summentherm D oder C oder B oder
A.
Und wir wissen, wenn die Variable jetzt hier die Belegung 1 ist, zum
Beispiel bei 1, die Belegung von A ist 1, deshalb muss A hier negiert
auftauchen.
B ist auch 1, deshalb muss B hier negiert auftauchen.
C ist 0, deshalb bleibt es C und D ist 0, deshalb bleibt es D.
Und Mintherm 3 ist auf die gleiche Art und Weise, also D oder C oder B
oder A.
Und wir wissen, dass hier das Ganze nicht in D und nicht in C ist,
deshalb D und C bleiben nicht negiert.
Das ist aber in B und in A, das ist nicht in C, also 0.
Habe ich einen Fehler irgendwo gemacht?
Ja, hier, keiner sagt was.
Okay, so und da sieht man hier, das sind zwei Minthermy.
Und was bedeutet das eigentlich, wenn wir sie zusammenfassen?
Das bedeutet eigentlich, wir verknüpfen sie miteinander konjunktiv.
Und man sieht hier diese zwei Minthermy, die unterscheiden sich in
einer Variable.
Das ist die Variable B.
Und das ist auch klar, weil die eine Null in B liegt und die andere
Null nicht in B liegt.
Und das können wir zusammenfassen zu einem größeren Block.
Ja, mithilfe von den Hamlingtonischen Axiomen, Inverselementen und so
weiter.
Zu einem Term, der heißt dann D oder C oder A quer.
Also wir streichen einfach diese Variable, die komplementär belegt
ist.
Wenn man das Ganze hier genauer anguckt, dann sieht man, dass wir
jetzt sowas hier bekommen haben.
Und das ist etwas, was nicht in D, also ist es oben und nicht in C,
weil es auf der linken Seite und in A.
Ja, deshalb ist es D oder C oder A quer.
Und das gleiche muss man natürlich mit allen möglichen spiegelbildlich
liegenden Nullen machen.
Wenn man das macht, dann kommt man auf sowas, das heißt die Maxthermy
hier 2, 6, 10 und 14.
Ich fasse die zwei zusammen zu einem Implikaten erster Ordnung.
Ich fasse die zwei zusammen zu einem Implikaten erster Ordnung auf die
gleiche Art und Weise.
Und dann sehen wir, sie unterscheiden sich in einer einzigen Variable.
Und zwar hier, die zwei liegen in C und die zwei liegen nicht in C.
Und deshalb habe ich ein Implikat oder ein Summenterm A oder B quer.
Das heißt, das ist alles, was in B ist und nicht in A und deshalb A
oder B quer.
Auf die gleiche Art und Weise A und 3, 1 und 3 haben wir gerade
gemacht.
Da bekommen wir A quer oder C oder D.
Dann sehen wir, dass 4 und 6 beispielsweise hier zusammengefasst
werden.
Die unterscheiden sich nur in der Variable B.
Das sind zwei Maxthermy, deshalb kommt hier ein Term A oder C quer
oder D.
Das heißt, die Variable, in der sich die zwei Maxthermy unterscheiden,
die wird gestrichen.
Und das ist B und deshalb taucht B hier nicht auf.
Dann 14 und 15, die sind auch spiegelbildlich zu der Linie hier oder
zu der Achse hier.
Die unterscheiden sich nur in der Variable A, weil 15 im Bereich A
liegt und 14 im Bereich nicht A.
Da kommt hier dieser Summenterm und dann sieht man, dass 2 und 3 auch
sich nur in einer Variable unterscheiden.
Also da kommt hier ein Summenterm, bei dem nur ein Literal fehlt und
zwar die Variable A, weil ich zwei Maxthermy zusammenfasse.
Und das liegt nicht in D, das liegt nicht in C und in B und deshalb
ist es B quer oder C oder D.
Wenn wir hier jetzt machen, dann müssen wir natürlich unsere
Minimalform bestimmen.
Das heißt, weitere Zusammenfassungsmöglichkeiten gibt es hier nicht.
Dann gehen wir auf die gleiche Art und Weise vor.
Das heißt zunächst mal die Kernprim Implikate, also solche Implikate,
die unbedingt aufgenommen werden müssen in der Minimalform.
Und das sind solche, durch die nur bestimmte Nullstellen überdeckt
werden.
Also man sieht hier zum Beispiel 1,3.
1,3 wegen der 1.
Die 1 wird nur von diesem hier überdeckt.
Deshalb müssen wir das hier auf jeden Fall aufnehmen.
So, man sieht hier wegen der 15 müssen wir diesen hier unbedingt mit
aufnehmen.
Das heißt, der hier ist unabdingbar.
Wegen der 4 hier müssen wir den hier auch aufnehmen.
Also 4 und 6, der ist auch unverzichtbar.
Und jetzt bleibt uns eigentlich, welche Nullen haben wir noch nicht
überdeckt?
Die 2 und die 10.
Und da sieht man, dass ich 2 und 10 eigentlich mit dem hier überdecken
kann.
Also mit dem Block hier kann ich 2 und 10 überdecken.
Man sieht auch gleichzeitig, dass dieser Primimplikat oder dieser
Nullblock, was aus der Zusammenfassung von 2 und 3 komplett irrelevant
ist, also komplett entbehrlich ist.
Ich muss auf jeden Fall A oder B quer nehmen, damit ich die restlichen
Nullstellen, die nicht durch Kernprimimplikate überdeckt werden,
aufnehmen.
Und wenn ich das mache, habe ich alle Nullstellen überdeckt.
Das heißt, der Implikat 1, 3, also A quer oder C oder D ist hier an
der Stelle entbehrlich.
Das wäre 2, 3, Entschuldigung, der hier.
So, was bedeutet das?
Das bedeutet, unsere konjunktive Minimalform ist natürlich die
Konjunktion aller dieser Summentherme.
Das heißt, von dem ersten, von allen vier hier und der hier ist
entbehrlich, also wird nicht benötigt und braucht man bei der
Realisierung nicht.
Gibt es Fragen dazu?
Somit solltet ihr in der Lage sein, Funktionen mithilfe von KV
-Diagrammen zu minimieren.
Und wie gesagt, die Vorgehensweise besteht aus zwei Schritten.
Einmal diese Zusammenfassungen und die Identifikation von Primthermen.
Und Primtherme heißen dann Primimplikanten im Falle von disjunktiver
Normalform oder Primimplikate im Falle von konjunktiver Minimalform.
Und wenn wir die ausgewählt haben, dann müssen wir den zweiten Schritt
der Minimierung machen und zwar aus dieser Menge von Primthermen eine
redundante Überdeckung der Funktion finden.
Also solche Blöcke zu identifizieren, die unbedingt mit aufgenommen
werden müssen und weitere, die notwendig sind, um die restlichen
Einstellen bzw.
Nullstellen der Funktion zu überdecken.
Gut, nun haben wir uns bis jetzt mit sogenannten vollständigen
Funktionen beschäftigt.
Was bedeutet das?
Das bedeutet, in der Funktionstabelle bzw.
im KV-Diagramm hatten wir nur Nullen oder Einsen.
Deshalb reicht es auch aus, wenn ich hier für diese Funktion nur die
Nullen im KV-Diagramm eingebe.
Implizit gilt, dass alle anderen Stellen oder dass die Funktion bei
allen anderen Belegungen hier den Wert 1 hat.
Aber es gibt auch sogenannte unvollständig oder partiell definierte
Funktionen.
Das heißt, das sind Funktionen, wo der Funktionswert nur für bestimmte
Eingangsbelegungen definiert ist und für die restlichen Belegungen
frei wählbar ist.
Das heißt, bei einer bestimmten Belegung der Eingangsvariablen ist mir
egal, was die Funktion hat.
Ob die Funktion den Wert 1 oder den Wert 0 hat.
Und natürlich, diese Belegungen wollen wir auch don't care benutzen.
Und jetzt liegt es auf der Hand, wenn wir im KV-Diagramm irgendwelche
Zusammenfassungen machen wollen.
Und wir haben so einen schönen Block zum Beispiel in der Mitte mit
drei Einsen und so einen don't care in der anderen Ecke.
Dann liegt es auf der Hand, wenn der Funktionswert an der Stelle egal
ist, dass wir den Funktionswert für diese Belegung, wo wir einen don't
care haben, zu 1 machen, damit wir einen möglichst größeren Einsblock
bilden können.
Das heißt, dadurch, dass wir diese don't cares frei wählen können oder
zu 0 oder 1 verfügen können, vereinfacht natürlich oder ermöglicht es
uns größere 0 oder 1 Blöcke zu bilden und somit kürzere Produkttherme
oder Summentherme.
Also Implikanten oder Implikate mit niedrigeren Realisierungskosten.
Und das wollen wir anhand von einem Beispiel sehen.
Und ich habe an unsere Beamer hier in diesem Hörsaal gedacht, wo ich
immer Probleme habe, den einen Beamer einzuschalten.
Der andere funktioniert immer einwandfrei, aber das dauert immer bis
der zweite funktioniert.
Und nehmen wir mal an, wir hätten diese zwei Beamer hier im Hörsaal,
also der linke Beamer und der rechte Beamer.
Und natürlich, wenn einer der linke und der rechte Beamer und wenn wir
hier ein Problem haben und zum Beispiel keiner von denen funktioniert,
dann müssen wir den Hausmeister anrufen.
Da wollte ich eine Bullshit-Funktion oder Schaltfunktion jetzt hier
bestimmen.
Wann sollen wir den Hausmeister anrufen, damit er das Problem
beseitigt?
So, wir nehmen an hier, wenn die Variable 0 ist, dann funktioniert der
Beamer nicht.
Und wenn die Variablen L und R 0 sind, dann funktioniert einer der
Beamer nicht.
Und wenn die Variable oder die Funktion H1 ist, dann müssen wir den
Hausmeister anrufen.
Und man sieht hier, wenn beide Beamer nicht funktionieren, also in der
ersten Zeile, dann müssen wir unbedingt den Hausmeister anrufen.
Sonst kann ich hier keine Vorlesung halten.
Das heißt, da wissen wir, der Funktionswert hier muss 1 sein.
Wir müssen den Hausmeister belästigen.
So, wenn beide Beamer funktionieren, einwandfrei, dann müssen wir den
Hausmeister nicht anrufen.
Deshalb hat die Funktion H den Wert 0.
Jetzt, wenn nur ein Beamer funktioniert, dann ist es frei wählbar, ob
wir jetzt den Hausmeister tatsächlich belästigen sollen oder nicht.
Also zum Beispiel sagen wir, das ist egal, wir können trotzdem die
Vorlesung halten, anrufen oder nicht anrufen, ist mir egal.
Deshalb sind das hier zwei Don't Caps.
Wenn wir jetzt diese Funktion ins KV-Diagramm eintragen, das ist eine
Funktion H von L und R.
Das heißt, R ist die erste Variable, L ist die zweite Variable.
Da sieht man, bei 0 haben wir eine 1, bei 3 haben wir eine 0.
Und an den anderen Stellen haben wir ein Don't Cap.
Wenn wir jetzt die disjunktive Normalform der Funktion hier bestimmen
wollen, dann ist es nur mit Term 1.
Also die DMF in dem Fall wäre nur mit Term 1.
Also H ist gleich L quer, R quer.
Und die konjunktive Minimalform, die wäre H ist gleich, also nur
Maximum 3.
Und Maximum 3, das ist nichts anderes als L quer oder R quer.
Jetzt stellen wir uns mal vor, wir haben diese zwei Don't Caps und wir
können sie jetzt zu 0 oder 1, wie wir wollen, verfügen.
Also beispielsweise, ich sage, naja, also da so viele Leute auf der
linken Seite sitzen, will ich den Hausmeister unbedingt anrufen, wenn
der linke Beamer ausfällt.
Oder wenn der rechte Beamer ausfällt, ist egal.
Nehmen wir mal beispielsweise hier, wenn der rechte Beamer ausfällt
und wenn der linke ausfällt und der rechte funktioniert, dann wollen
wir auch den Hausmeister anrufen.
In dem Fall, weil mehr Leute auf der Seite sitzen und die andere Seite
ist nicht so wichtig.
So, was bedeutet das?
Das bedeutet hier hätten wir eine 1.
Ja.
Und wenn ich hier eine 1 habe, dann bekomme ich natürlich von meiner
disjunktiven Minimalform H ist gleich L quer.
Und das auf jeden Fall minimaler als L quer, R quer.
Okay, ich kann auf die gleiche Art und Weise, wenn ich gesagt habe,
ich will den Hausmeister anrufen, wenn der linke Beamer ausfällt.
Okay, wenn der rechte ausfällt, dann brauche ich ihn nicht anzurufen,
dann kann ich die zweite Don't Cap zu 0 verfügen.
Und somit habe ich auch meine konjunktive Normalform, also H ist
gleich L quer.
Ja, also auf die Art und Weise, dadurch dass man die Möglichkeit hat,
bei diesen Don't Cap Stellen Funktionswert 0 oder 1 frei zu wählen,
kann man natürlich bessere Zusammenfassungen machen, weil hier habe
ich statt jetzt ein Minterm, statt ein Minterm hier, beziehungsweise
ein Maxterm hier, habe ich natürlich hier einen größeren Block bilden
können von 1 hin, beziehungsweise einen größeren Block von 0 hin.
Und dadurch bin ich auf einer kürzeren Form der Funktion gekommen.
Es gibt ein anderes Beispiel, Airbag-Steuerung.
Ihr kennt das, wenn die Airbags zünden, normalerweise wenn ein Unfall
passiert.
Und jetzt haben wir hier eine Funktion, die soll praktisch eine
Steuerung realisieren.
Wir haben einmal die Variable, es passiert ein Unfall, der Sitz ist
belegt im Auto oder nicht.
Und dann soll tatsächlich der Airbag zünden.
Eine Funktion mit zwei Eingangsvariablen, U und B.
Und wir wissen, wenn kein Unfall passiert, also da ist kein Unfall,
dann soll um Gottes Willen das Airbag nicht losgehen.
Das heißt, Z ist gleich 0, der Airbag soll nicht zünden.
Wenn ein Unfall passiert, also das ist hier ein Unfall, und wenn
jemand auf einem Sitz sitzt im Auto, dann soll auf jeden Fall das
Airbag hier losgehen.
Wenn der Sitz nicht belegt ist, zum Beispiel hier W gleich 0, dann ist
es uns egal, ob das Airbag jetzt zündet oder nicht zündet.
Das heißt, die Funktion, die wir hier haben, die kann man jetzt im KV
-Diagramm übertragen.
Man sieht hier 0,0 bei den ersten Belegungen, bei Belegung 2 haben wir
Don't Care und bei Belegung 3 haben wir 1,1.
Jetzt könnte man sagen, okay, ich will hier beispielsweise diese X zu
1 verfügen.
Also ich will, dass beispielsweise alle Airbags bei allen Sitzen
zünden, wenn ein Unfall passiert.
Dann habe ich hier eine 1 und somit kann ich natürlich hier meine Z
-Funktion statt mit dem Minterm 3, was nichts anderes ist als U, B,
mit U realisieren.
Das heißt, Z ist gleich U in dem Fall, weil ich die zwei Sachen hier
zusammenfassen kann, wenn ich diese Don't Care zu 1 verfüge.
Und während im anderen Fall, ohne das hier hätten wir Z ist gleich U
und B.
Das heißt eigentlich, man muss detektieren, dass ein Unfall passiert
ist und man muss noch zusätzliche Hardware haben, die auch detektiert,
dass ein Sitz belegt ist oder nicht.
Okay, das heißt, auf die gleiche Art und Weise sieht man die Vorteile
von diesen unvollständig definierten Funktionen.
Ganz allgemein habe ich das hier nochmal, das heißt die Funktion hier
mit einer Don't Care Belegung bei 3.
Wenn ich die 3 hier zu 0 verfüge, dann bekomme ich, wie man sieht hier
in der disjunktiven Form, die Disjunktion der zwei Minterm 1 und 2,
also a, b, q, oder a, q, b.
Und wenn ich x zu 1 tue, dann bekomme ich natürlich hier eine
Vervollständigung der Funktion, die heißt a oder b, was wesentlich
minimaler oder kürzer ist als die andere Vervollständigung.
Das sagt auch etwas darüber aus, dass natürlich eine geschickte Wahl,
ob man jetzt die Don't Care zu 0 oder zu 1 verfügt, natürlich das
Ergebnis der Minimierung stark beeinflusst.
Das heißt hier, wenn ich eine 0 hier tue, dann gewinne ich nicht so
viel, aber wenn ich hier eine 1 für x oder für Don't Care tue, dann
reduziere ich den Term wesentlich.
Okay, jetzt gucken wir mal das Ganze anhand von einem etwas
komplexeren Beispiel.
Das heißt, wir haben eine unvollständig definierte Funktion, die ist
gegeben durch dieses KV-Diagramm hier.
Das heißt, die hat die Minterm 0, 11, 9, 12, 13, die sind hier
eingetragen und die hat die Don't Care Stellen 2, 5, 7 und 8.
Das heißt, der Unterschied jetzt zu vorher, vorher konnte ich meine
Funktionen dadurch eingeben, bei vollständig definierten Funktionen
konnte ich meine Funktion eindeutig spezifizieren, indem ich sage, die
Funktion hat die Minterm 1, 2, 3, 7 oder die Maxterm 2, 6, 8,
irgendwas.
Bei unvollständig definierten Funktionen reicht das nicht aus.
Um eine unvollständig definierte Funktion eindeutig zu beschreiben,
muss ich entweder die Nullstellen und Einsstellen eingeben oder die
Nullstellen und Don't Care oder die Einsstellen und Don't Care.
Und hier haben wir die Einsstellen und Don't Care, das heißt, die
restlichen Belegungen der Funktion sollten dann natürlich eindeutig
Null sein.
Das heißt, hier haben wir überall Nullen.
So, und wenn wir jetzt hier diese Funktion minimieren wollen, ohne die
Don't Cares, dann sehen wir, wir müssen Einsen zusammenfassen.
Und da haben wir hier 11 und 9 zusammengefasst und 11 und 9 sind
nichts anderes als...
Das liegt nicht in C, das liegt in A und in D, also nichts anderes als
das hier.
Und dann können wir natürlich 12 und 13 zusammenfassen.
12 und 13, das ist nicht in B, in D und in C, das ist das hier.
Und natürlich können wir, was hier nicht eingegeben ist, können wir
die zwei hier zusammenfassen, weil die sind auch spiegelbildlich
zueinander.
Und wir haben die Eins hier.
Und diese Eins ist nichts anderes als das hier.
Das heißt, eigentlich die Funktion, wenn ich die Funktion realisiere,
nur die Einsstellen der Funktion realisiere, dann habe ich insgesamt
vier Primimplikanten.
Das sind die Roten und die Grünen.
Und man sieht hier, dass der eine Grün hier, also mit 9 und 13,
entferntlich ist.
Und deshalb taucht er hier nicht auf bei der Funktion.
Wenn ich jetzt sage, okay, diese Acht will ich jetzt zu Eins machen.
Ich mache die Acht hier zu Eins.
Ja, ich lösche mal das Ganze hier.
Und ich mache jetzt die Acht zu Eins.
Uppsala, zu einer grünen, zu einer kreativ grünen Eins.
So, dann was habe ich?
Ich habe nach wie vor den Term hier, weil das ist die 9, 13.
Ich habe jetzt BD, weil ich kann jetzt diese vier Block hier
zusammenfassen.
Das ist nicht B quer CD, sondern das ist B quer D.
Und für diesen Minterm hier kann ich die zwei nehmen.
Also das hier mit dieser Eins hier.
Und das ist nichts anderes als C quer, B quer, A quer.
Das heißt, man sieht hier die Funktion, die hat mindestens, besteht
aus drei Termen, aber in dem einen Produktterm habe ich eine Variable
weniger.
Jetzt gehen wir weiter und sagen, okay, nicht nur die Acht wollen wir
zu Eins verfügen, sondern Felder Acht und Zwei.
Das heißt, dieses Feld Zwei, ich mache es mal jetzt hier, soll eine
Eins sein.
Und dieses Feld hier soll auch eine Eins sein.
Dann haben wir nach wie vor den hier.
Dann haben wir den großen Block hier.
Und natürlich den hier.
Natürlich, der hier ist nach wie vor da, aber der ist jetzt in dem
Fall entbehrlich für die Realisierung einer minimalen Form.
Deshalb ist er hier nicht eingezeichnet im Diagramm.
Das heißt, ich bekomme B quer D oder A quer C quer D.
So, gibt es Fragen dazu?
Okay, das ist so eine Zusammenfassung von der grafischen Minimierung.
Das heißt, zunächst mal müssen wir wissen, wie wir eine Funktion im KV
-Diagramm...
Zunächst mal müssen wir wissen, wie wir ein KV-Diagramm überhaupt
malen können.
Malen sollte kein Problem sein.
Aber vielleicht auch die richtigen Indizes oder die Nummern der Felder
mal eintragen.
Dann tragen wir die Funktion in das KV-Diagramm und dann suchen wir
nach möglichst großen Blöcken von Einsen oder von Nullen.
Je nachdem, ob wir die DMF oder die KMF suchen, also disjunktive
Minimalform oder konjunktive Minimalform.
Und wenn wir die alle bestimmt haben, dann suchen wir die wichtigsten
unter denen.
Das sind sogenannte Kernprim-Termi, also Kernprim-Implikanten oder
Kernprim -Implikate.
Und eine weitere Menge von Implikanten, die natürlich die Funktion
komplett überdeckt.
Und wenn wir unvollständig definierte Funktionen haben, dann müssen
wir natürlich, je nachdem, was wir suchen, also wenn wir zum Beispiel
die disjunktive Minimalform suchen, dann müssen wir eine Menge von
diesen Don't-Care-Belegungen zu Eins verfügen, sodass wir größere
Blöcke bilden können.
Okay, das sind die zwei Schritte, die wir immer wieder bei jedem
Verfahren eigentlich zu lösen haben.
Das heißt, einmal die Prim-Termi bestimmen, Prim-Termi bestimmen, das
heißt, wir haben Produkt-Termi oder Summen-Termi mit möglichst wenigen
Lateralen.
Das bedeutet, das sind Gatter mit möglichst wenigen Eingängen.
Und im zweiten Schritt brauchen wir nicht unbedingt alle diese Gatter,
sondern alle diese Termi, sondern nur eine Menge davon, die die
Funktion überdeckt.
Und somit reduzieren wir die Anzahl der Gatter, die notwendig sind für
die Minimierung.
Okay, somit möchte ich das abschließen, die Grafische Minimierung, und
komme ich zu den tabellarischen Verfahren.
Und zwar zwei Verfahren wollen wir kennenlernen, einmal das Cohen
-McCluskey -Verfahren und einmal das Konsensusverfahren.
Zwei tabellarische Verfahren sind natürlich sehr geeignet für die
Implementierung im Rechner, im Gegensatz zu grafischen Verfahren, die
sehr gut geeignet sind zum Lösen oder zum Bearbeiten auf Papier.
So, und das Cohen-McCluskey-Verfahren arbeitet eigentlich nach dem
gleichen Prinzip.
Eigentlich alle Verfahren arbeiten nach einem ganz trivialen Prinzip.
Man sucht nach Termi, die sich in einer Variable unterscheiden und
streicht diese Variable.
Und das ist A oder A2 gleich 1, das kennen wir.
Das sind die huntingtonischen Axiome.
Das heißt, es kommt überhaupt kein Zusatzwissen hier, grundlegendes
Zusatzwissen, was ihr lernen müsst.
Alle Verfahren basieren darauf, dass wir Termi suchen, die sich in
zwei Variablen unterscheiden, A A2, B B2, und fassen sie zusammen.
Das ist alles, was hinter all diesen Verfahren steckt.
Was wir lernen hier sind systematische Vorgehensweisen, wie wir diese
Regeln der huntingtonischen Axiome oder der Bootschen Algebra
tatsächlich nutzen.
Das heißt, arbeitet nach dem gleichen Prinzip wie KV-Diagramm.
Und KV-Diagramm arbeitet nach dem gleichen Prinzip wie X oder X2
gleich 1 oder X und X2 gleich 0.
Ja, das kennen wir.
Das haben wir bei H3 und H4 bei den huntingtonischen Axiomen
festgelegt.
Der Unterschied ist der Ausgangspunkt.
Das heißt, was ist die Eingabe von diesem Verfahren?
Bei KV-Diagramm natürlich ein Bootscher Ausdruck oder die
Funktionsstabilität.
Und hier bei Quine-McCluskey ist tatsächlich die Funktionsstabilität
der Ausgangspunkt.
Und damit kann man sowohl die disjunktive Form als auch die
konjunktive Form berechnen.
Und bei disjunktiven Minimalformen arbeiten wir also mit den Min
-Termen und bei Konjunktiven mit den Max-Termen.
Also Funktionsstabilität ist klar, aber wenn wir jetzt die disjunktive
Form bestimmen, dann müssen wir solche Zeilen nehmen in der
Funktionsstabilität oder betrachten, wo die Funktion den Wert 1 hat,
im konjunktiven Fall, wo die Funktion den Wert 0 hat.
Und im Folgenden will ich das erläutern für den disjunktiven Fall.
In der Übung werden wir auch ein Beispiel sehen, wie das Verfahren zur
Bestimmung von der konjunktiven Minimalform funktioniert.
So, und das will ich anhand von einem Beispiel machen.
Und da sieht man hier, das ist eine Funktion mit fünf Variablen.
Also das sind 32 Felder im KV-Diagramm bzw.
32 Zeilen in der Funktionstabelle.
Das sind die Belegungen der Variablen mit den Nummern 0 bis 31 und mit
den Funktionswerten.
Und wir haben gesagt, wir wollen das Ganze jetzt für den disjunktiven
Fall betrachten.
Deshalb betrachten wir die Zeilen in der Tabelle, wo die Funktion den
Wert 1 hat.
Also die Min-Termi der Funktion.
Wenn die Funktion unvollständig definiert ist und wir nicht wissen,
wie diese Don't-Cares sind, verfügen wir alle Don't-Cares zu 1.
Ja, weil in der Funktionstabelle können wir nicht sehen, welches Don't
-Care irgendwie geschickt zu 1 und welches zu 0.
Deshalb müssen wir alle Don't-Cares zu 1 verfügen.
Wir müssen am Ende nur aufpassen, dass kein Term entsteht, kein Prim
-Implikant entsteht, der nur aus Don't-Cares besteht.
Weil der ist auch nicht nötig für die Realisierung der Funktion.
Das heißt also, das ist ein letzter Schritt, was wir dann prüfen im
Falle von unvollständig definierten Funktionen.
Aber bleiben wir bei vollständig definierten Funktionen.
Das heißt, wir gucken die Einstellungen der Funktionen und man geht
hin, wenn ich das kurz nur visualisieren darf, mithilfe von dem KV
-Diagramm, das sind die Einstellungen der Funktionen.
Und was man jetzt macht, wie wir das bis jetzt gemacht haben.
Wir sind hingegangen und wir haben gesagt, zwei Min-Termi, die sich in
einer Stelle, in einer Komponente oder in einer Variable
unterscheiden, kann ich zusammenfassen.
Also 2 und 4, 6 und 14, 14 und 12, 6 und 4.
Und dann merkt man irgendwann mal, ich kann die zwei hier zu einem
Größeren zusammenfassen.
Oh, ich kann die zwei hier zusammenfassen.
Ah, die eins und die hier kann ich zusammenfassen, aber die zusammen
kann ich mit denen hier nochmal zusammenfassen.
Oh, ich habe das gleiche nochmal hier.
Ah, dann kann ich das hier mit denen hier und mit denen hier
zusammenfassen.
Könnt ihr das folgen?
Das ist so das Prinzip.
Ich mache es vielleicht, weil es so schön war, oder nicht?
So, also wir fassen die hier zusammen, weil das sind zwei Min-Termi,
fassen die hier zusammen und die hier zusammen.
Und dann merken wir irgendwann mal, oh, das Ganze kann ich ja zu einem
Implikanten dritter Ordnung zusammenfassen.
Dann auf der anderen Seite mache ich hier, ah, die zwei sind
spiegelbildlich zueinander und vielleicht die zwei sind
spiegelbildlich zueinander.
Ah, ich kann sie doch zusammenfassen.
Schau mal, die eins hier mit der eins hier und die eins mit der eins,
das sind zwei Min-Termi, die sich in einer Variable unterscheiden.
Kann ich sie so zusammenfassen, beziehungsweise für die Leute, die die
Orientierung verlieren bei der Zusammenfassung hier, ich kann die zwei
zusammenfassen und die zwei zusammenfassen.
Und dann sehe ich, oh, aber die hier, der hier, jetzt werde ich ganz
schwarz, und der hier und der hier gehören ja zusammen.
Und dann macht man hier auch weiter und dann sieht man, ich kann,
welche Farbe haben wir noch?
So, dann sagt man, okay, die zwei kann ich zusammenfassen und die zwei
kann ich zusammenfassen und dann merkt man, ah, aber die gehören ja
zusammen.
Die kann ich nochmal zusammenfassen zu E quer, B quer, C.
Und das, was ich hier mache, was ich hier tatsächlich im KV-Diagramm
mache, soll tabularisch erfolgen.
Das Prinzip ist eindeutig, zwei Min-Termi, weil das ist der
Ausgangspunkt, die Min-Termi der Funktion in diesem tiefen Fall, kann
ich zusammenfassen, wenn sie sich in einer Variable unterscheiden.
Und was dieses Kwan-McCluskey-Verfahren macht, die gibt uns einen
systematischen Weg, wie wir das implementieren, wie wir das
tatsächlich in einem Rechner implementieren und realisieren.
Also nichts Neues eigentlich, was wir hier lernen, sondern ein Trick,
ein Kochrezept, wie wir dazu kommen.
Wie wir das, was ich im KV-Diagramm jetzt gerade erklärt habe,
tatsächlich mithilfe von der Tabelle machen.
Und man geht so vor, um das zu machen, was ich gerade gemacht habe,
und man sagt, man ordnet die Min-Termi der Funktion, also die Min
-Termi der Funktion, das sind die Zeilen mit den Einsen, man ordnet
sie nach Gewicht.
Und Gewicht ist die Anzahl der Einsen in der Belegung.
Das heißt hier, ich habe Min-Termi der Gewichtsklasse 1, Min-Term 1
und Min-Term 4, die haben nur eine 1 in der entsprechenden Belegung
der Eingangsvariablen.
Die Min-Termi 5, 6, 12, 10, 12 und 18 haben jeweils zwei Einsen.
Und die Min-Termi 13, 14, 22 und 26 haben jeweils drei Einsen.
Und Min-Term 30 hat vier Einsen.
Min-Term 0 hätte 0 Einsen, wäre natürlich die Gewichtsklasse 0.
Und jetzt, was haben wir gesagt?
Wir haben gesagt, wir suchen nach Termi, die sich nur in einer
Variable unterscheiden.
Und solche Termi, die sich nur in einer Variable unterscheiden, die
müssen in zwei benachbarten Gewichtsklassen liegen.
Das heißt, damit ich alle möglichen Vergleiche mache, brauche ich Min
-Term 2 auf gar keinen Fall mit dem hier zu vergleichen, mit 30.
Und man sieht das im KV-Diagramm.
Also Min-Term 30, wo war Min-Term 30?
29, 30 und das ist der 2.
Die sind überhaupt nicht spiegelbildlich zueinander.
Das heißt eigentlich, der erste Vergleich, wenn ich mit Min-Termi
anfange, muss ich nach Min-Termi suchen, die sich nur in einer
Variable unterscheiden.
Und das sind Min-Termi von zwei benachbarten Gewichtsklassen.
Das heißt, ich muss gucken, ob Min-Term 2 mit 5, 6, 10, 12 oder 18
zusammengefasst werden kann.
Weil dort habe ich eine Hoffnung.
Es ist nur eine Variable, die verschieden ist, aber welche, das ist
natürlich entscheidend.
Min-Term 4 auch mit allen und dann alle diese Min-Termi der
Gewichtsklasse 2 mit allen Min-Termen der Gewichtsklasse 3 und Min
-Termi der Gewichtsklasse 3 mit allen Min-Termen der Gewichtsklasse 4.
Das heißt, wie viele Vergleiche muss ich zu Beginn machen?
2 mal 5 plus 5 mal 4 plus 4 mal 1.
Das sind die initialen Min-Termi-Vergleiche, die ich machen muss.
Also 2 mal 5 plus 5 mal 4.
Da sind wir bei 30 plus 4 mal 1.
Also 30, 34 Vergleiche muss ich zunächst mal machen.
Und das machen wir jetzt.
Das steht hier, das brauchen wir jetzt nicht hier.
Das machen wir.
Das sind unsere Min-Termi, das sind die Gewichtsklassen und wir
wissen, Min-Termi sind Primimplikanten 0.
Ich habe sie hier in dieser Tabelle aufgezeichnet.
Das sind die Min-Termi der Gewichtsklasse 1, also Primimplikanten 0.
Und wir wissen schon, wir müssen nur Min-Termi benachbarte Klassen
miteinander vergleichen und schauen, ob wir sie zusammenfassen.
Und wenn wir sie zusammenfassen, dann streichen wir eine Variable.
Also es entsteht aus einem Implikanten 0.
Ordnung ein Implikant 1.
Ordnung, wo die eine Variable fehlt.
Und die tragen wir in einer neuen Tabelle.
Und in dieser neuen Tabelle wollen wir hier schreiben, zunächst mal,
welche Min-Termi wir zusammengefasst haben und wie diese Bezeichnung
oder Belegung der Eingangsvariablen aussieht.
Wir fangen an mit 2.
2 kann ich mit 5 zusammenfassen, eigentlich nicht.
Woran erkennt man das?
2 und 5 unterscheiden sich in drei Variablen eigentlich.
Weil bei 2 habe ich hier zum Beispiel ein b, also a quer, b und c
quer.
Und hier habe ich ein c, b quer und a.
Also man kann sich das nochmal veranschaulichen.
Die zwei Termi, die kann ich nie zusammenfassen.
Also die Variablenreihenfolge, was haben wir hier als
Variablenreihenfolge gewählt?
Ist egal, nehmen wir irgendeine.
Also e, d, c, b, a.
Und 2 wäre e quer, d quer, c quer, b a quer.
Und 5 wäre e quer, d quer, c, b quer, a.
Und man sieht hier, die zwei Termi, da gibt es keine einzige Variable,
wo die zwei sich unterscheiden.
Deshalb kann ich sie nicht zusammenfassen.
2, dann machen wir weiter.
2 und 6.
Man sieht, 2 und 6 unterscheiden sich nur an der Stelle hier.
In der Belegung der Variablen c, dann kann ich die Variable c
streichen.
Also ich kann schreiben, 2 und 6 kann ich zusammenfassen.
Und ich erhalte hier statt e quer, d quer, c quer, b a quer.
Und e quer, d quer, c quer, b a quer.
Ich erhalte e quer, d quer, b a.
Also das heisst, die Variable c ist weg.
So, dann mache ich weiter.
2 mit 10.
Ah, die unterscheiden sich in der Variable d.
Man sieht hier, die Variable d ist 0 hier und hier 1.
Das heisst, ich kann sie zusammenfassen.
Und diese Variable wird ja zu ein don't care verfügt.
Das heisst, ich habe hier eigentlich e quer, c quer, b a quer.
So, wir sind noch bei 2.
Also wir müssen, wie viele Vergleiche, wir müssen 10 Vergleiche
machen.
Und jetzt sind wir bei 2 und 12, sieht man, unterscheiden sich in mehr
als einer Variable.
Deshalb kann ich sie nicht zusammenfassen.
2 und 18 unterscheiden sich nur in der Variable hier.
Deshalb kann ich sie zusammenfassen zu don't care 0010.
Und dann bin ich zunächst mal fertig mit allen Vergleichen der 2 mit
denen hier.
Ich mache weiter mit der 4.
4 und 5 kann ich zusammenfassen, weil die unterscheiden sich an der
Stelle hier.
4 und 6 kann ich auch zusammenfassen, ohne hinzugucken.
Und jetzt 4 und 10 kann ich auf gar keinen Fall zusammenfassen, ohne
hinzugucken.
Weiß jemand, warum?
Wow, das ging aber schnell.
2 Mintermi sind Kandidaten für Zusammenfassung, wenn die Nummer der
Mintermi, die Differenz der Nummer der Mintermi ein 2er Potenz ist.
Das bedeutet, die sind nur Kandidaten.
Das heißt, wenn die Differenz ein 2er Potenz ist, dann müssen sie
nicht unbedingt zusammenfassbar sein.
Aber die sind zunächst mal Kandidaten dafür.
Und 4 und 10, da ist der Unterschied 6, das 2er Potenz, kann ich nicht
zusammenfassen.
4 und 12, Differenz 8, könnte hingehen.
Und da sieht man, die unterscheiden sich tatsächlich hier.
4 und 18, Differenz 14 brauche ich nicht.
Dann bin ich hier zunächst mal fertig mit dem Vergleichen.
Jetzt machen wir weiter mit denen hier, also 5 mit allen.
5 mit 3, ist Differenz 8, könnte gehen.
Und da sieht man, die unterscheiden sich an der Stelle hier.
5 und 14, Differenz ist 9, geht nicht.
5 und 22, Differenz ist 17, geht nicht.
5 und 26, Differenz 21, geht auch nicht.
Dann machen wir weiter mit 6.
6 und 13, geht nicht.
6 und 14, könnte gehen.
Und die unterscheiden sich tatsächlich an der Stelle hier, deshalb 6
und 14.
Dann 6 und 22, Differenz ist, glaube ich, ungefähr 16.
Die kann man auch zusammenfassen, wie man sieht, weil die
unterscheiden sich an der Stelle.
6 und 26, geht nicht.
Dann machen wir weiter mit 10.
10, 13, geht nicht.
10, 14, geht.
10, 22, geht nicht.
10, 26, könnte gehen.
Und man sieht tatsächlich, 10, 26, geht.
Dann machen wir weiter mit 12.
12, 13, geht.
12, 14, auch.
12, 22, nicht.
12, 16, auch nicht.
Dann machen wir weiter mit 18.
18, 13, nicht.
18, 14, könnte gehen.
Aber sie unterscheiden sich hier, wie man sieht.
18 und 14, das ist eine Zweierpotenz, der Unterschied.
Aber sie unterscheiden sich in drei Stellen.
1, 1, 0 und 0, 0, 1.
Das heißt, geht nicht.
Und 8, 26, da ist der Unterschied, wie viel?
18, 26, ist der Unterschied 8.
Und man sieht, sie unterscheiden sich an der Stelle hier.
Deshalb kann ich sie zusammenfassen.
Dann bin ich hier fertig.
Ah, okay, dann bin ich jetzt fertig.
So, jetzt machen wir weiter.
13 und 30, geht nicht.
14 und 30, könnte gehen, weil die Differenz ist 16.
Das heißt, sie unterscheiden sich, wie man sieht, hier an der ersten
Stelle.
Deshalb ist es Don't Care 1, 1, 0.
Und 14, 22 und 30 geht auch, wie man sieht.
Die unterscheiden sich an der Stelle.
Die Differenz ist auch 8.
Und 26 und 30 geht auch.
Deshalb bekomme ich hier auch ein 1, 1, Don't Care 1, 0.
So, jetzt meine Frage ist, gibt es jemanden hier, der nicht weiß, wie
diese Zusammenfassungen und diese Vergleiche so weit funktionieren?
Okay, aber was bedeutet das eigentlich für uns?
Das heißt, der Ausgangspunkt war MINTermi.
Und jetzt haben wir so viel zusammengefasst, aber wir wissen nicht, ob
wir alle MINTermi überhaupt zusammengefasst haben zur implikanten
Erste Ordnung.
Deshalb müssen wir das prüfen.
Und zwar immer, wenn wir diese Vergleiche machen, müssen wir MINTermi,
die wir zusammenfassen, abhacken.
Ja, also 2 und 6 habe ich schon.
2 und 10, also ich habe auch MINTerm 10 irgendwie zusammengefasst zu
einem größeren Block.
2 und 18 habe ich auch zusammengefasst.
4 und 5 habe ich zusammengefasst.
4 und 6, 6 ist schon weg.
4 und 12 habe ich zusammengefasst.
5 und 13 und 14 und 22.
Und ich habe 10 mit 26 zusammengefasst und ich habe 14 mit 30
zusammengefasst.
Also man sieht eigentlich, dass aus allen diesen MINTermi größere
Blöcke entstanden sind.
Ja, deshalb hacken wir sie ab.
Aber das bedeutet nicht, wenn wir jetzt einen MINTermi abhacken, dass
wir keine Vergleiche mehr mit diesem MINTermi machen.
Man sieht, wir haben alle Vergleiche gemacht und ich habe dieses
Abhacken später hier, also im Nachhinein gemacht.
Das heißt, die werden zwar abgehackt, die MINTermi, die zu größeren
Blöcken zusammengefasst werden können, aber die nehmen weiterhin an
den Vergleichen teil.
So, das sind jetzt alle Implikanten erster Ordnung und was machen wir
jetzt?
Das sind zwei MINTermi, die ich zusammengefasst habe, aber es kann
sein, dass manche von diesen zwei MINTermi-Blöcken, also Implikanten
erster Ordnung, zu vier Blöcken zusammengefasst werden können.
Deshalb machen wir das Gleiche.
Das heißt, wir versuchen jetzt hier aus Implikanten erster Ordnung
Implikanten zweiter Ordnung zu finden.
Also ein Blöcke, die nicht zwei Eins sind, zwei MINTermi
zusammenfassen, sondern vier MINTermi.
So, jetzt haben wir natürlich hier keine Nummern.
Ja, das würde uns helfen, wenn wir hier eine Nummer und Differenz...
Deshalb können wir jetzt diese erste Eselbrücke gar nicht benutzen, um
den Vergleich ein bisschen zu beschleunigen.
Aber eigentlich wissen wir schon viel.
Solche Termi, die wir jetzt zusammenfassen können, die müssen ein
Don't -Care an der gleichen Stelle haben und zusätzlich noch an einer
anderen Stelle komplementär belegsam.
Das heißt, wenn ich den ersten Term nehme, der fehlt C hier.
Ich brauche den nur zu vergleichen mit Termi, bei denen C fehlt.
Also zum Beispiel 10 und 14.
Da fehlt auch C, weil wir das zusammengefasst haben.
Also der hier mit 10, 14.
Da sieht man, ich habe ein Don't-Care bei C und hier habe ich ein
Don't -Care bei C.
Das sind zunächst mal Kandidaten.
Also zwei Implikanten erster Ordnung, die ich eventuell zu einem
Implikanten zweiter Ordnung unterscheide, wenn die in einer weiteren
Variable komplementär belegt ist.
Und zum Glück sind sie, weil hier habe ich eine 1.
Oder was heißt zum Glück?
In diesem Fall sind sie, weil hier habe ich eine 0 und hier eine 1.
Das heißt, ich kann 2, 6 und 10, 14 mit dem hier zusammenfassen zu
einem Implikanten zweiter Ordnung 0, Don't-Care, Don't-Care, 1, 0.
Jetzt machen wir weiter.
Den könnten wir zusammenfassen mit dem hier.
Und man sieht, die sind tatsächlich an der Stelle hier auch
komplementär belegt.
Also an der Stelle hier.
Deshalb kommen 2, 6, 8, 10 und 22.
Und das sind die Nummern der MinTermi im KV-Diagramm und das sind die
Termi.
Das wäre jetzt E quer, B, A quer.
Ja, so funktioniert das Ganze.
So, das heißt der RC mit dem hier und dann mit dem hier geht es nicht.
Jetzt kommen wir zu dem hier.
Den könnten wir eventuell mit denen hier zusammenfassen.
Schauen wir, die sind in mehreren Variablen komplementär belegt.
Hier in einer Variable komplementär belegt.
Also 2, 10 und 6, 14 eigentlich kann ich zusammenfassen.
Aber 2, 10, 6, 10, 4...
Ne, was habe ich gesagt?
Also der hier 2, 10, 6, 14, das ist eigentlich der gleiche wie der
hier.
Ja, das sind die gleichen MinTermi, die wir schon haben.
Deshalb tragen wir das hier nicht in der Tabelle oder wir tragen es
ein und wir streichen, wenn wir merken, es ist der gleiche Term.
Ja, das heißt, was hier tatsächlich kommt, es kommt hier ein Term.
2, 10, der verschwindet gleich.
2, 10 und was haben wir gesagt?
Und 6, 14, ja?
Und da sehen wir 2, 10, 6, 14, das ist nichts anderes als 0, Don't
care, 1, 0 und das ist der gleiche wie der hier.
Und das sind auch die gleichen Nummer der MinTermi.
Deshalb brauchen wir das hier nicht einzutragen bzw.
müssen wir wegstreichen, wenn wir merken, wir haben schon ein Term,
das äquivalent oder identisch ist.
So, und dann machen wir weiter mit den Vergleichen.
Das heißt, da kommt hier nichts raus.
2, 10 eventuell mit dem hier.
Und tatsächlich, es kommt jetzt hier eine Don't care, Don't care, 0,
1, 0.
Das heißt 2, 10 und 18, 26.
Und dann bin ich zunächst mal mit dem Vergleichen von dem ersten hier
mit allen anderen.
Entschuldigung, mit dem zweiten.
Jetzt der dritte hier, der kann mit dem verglichen werden.
Der dritte hier kann mit dem hier verglichen werden, zusammengefasst
werden.
Sie unterscheiden sich auch an einer Stelle.
Das heißt, es kommt hier 5, der hier, also der kann mit dem
zusammengefasst werden.
Und da kommt ein Don't care, Don't care, 0, Don't care, 1.
Und das ist der gleiche hier, der kommt hier nicht rein in der
Tabelle.
Das heißt, der nächste, der unterschiedlich ist und der nicht schon in
der Tabelle ist, ist 4, 5 und 12, 13.
Also der hier mit dem hier, das ist der einzige, den man hier
vergleichen kann.
Dann der hier können wir eventuell mit dem hier vergleichen.
Das ist 4, 6, 4, 6, die unterscheiden sich an der Stelle.
Da kommt ein 0, Don't care, 1, Don't care, 0.
Ja, 0, Don't care, 1, Don't care, 0.
Und somit sind wir fertig hier mit den Vergleichen.
Dann machen wir die hier mit denen.
Das heißt, die zwei, die können mit denen hier, also der erste mit dem
hier, und die unterscheiden sich in mehr als einer Variable, deshalb
kann ich sie nicht zusammenfassen.
Der hier, der unterscheidet sich nur in der Variable hier, da kommt
hier 4, 16, 22, 30.
Ja, also 4, 16, 22, 30.
Und dann, genau, da waren wir hier.
Der hier, der kann eventuell mit dem zusammengefasst werden.
Ja, und man sieht, sie unterscheiden sich an der Stelle.
Da kommt ein Don't care, Don't care, 1, 1, 0.
Ja, und 10, 14 und 26, 30 kommt das hier.
Und 18, 22, mit 26, 30, da sieht man hier, dass sie sich an der Stelle
hier unterscheiden, also ein Don't care haben und hier komplementär
belegt sind, deshalb kommt 1, Don't care, Don't care, 1, 0.
So, jetzt geht das Ganze weiter, aber wir müssen zunächst mal hier
wegstreichen, das, was wir zusammengefasst haben.
Und da brauche ich natürlich mal ein bisschen Unterstützung hier, aber
den haben wir zusammengefasst, den haben wir, 2, 10 haben wir auch
zusammengefasst, 2, 18 haben wir auch irgendwo, 4, 5 haben wir auch,
4, 6 haben wir auch, 4, 12 haben wir auch, dann 5, 13, 5, 13 haben
wir, 5, 13, 5, 13 haben wir auch und so weiter und so fort.
Wir werden gleich am Ende sehen, welche eigentlich alle wurden
zusammengefasst.
Ihr könnt mir glauben, das werden wir auch am Ende checken, aber keine
von denen nimmt also weiter, beziehungsweise keins von denen ist ein
Primimplikant der Funktion.
Jetzt gehen wir weiter hier und versuchen, hier Zusammenfassungen zu
machen.
Und da sieht man, das sind zwei Termine, die an der gleichen Stelle
Don't cares haben, also hier, da und da, die unterscheiden sich hier,
das heißt es kommt ein Block aus 8 Einzelnen, und der ist Don't care,
Don't care, Don't care 1, 0.
Weitere Zusammenfassungen, zum Beispiel der hier mit dem hier, kann
ich natürlich zusammenfassen, aber da kommt auch Don't care, Don't
care, Don't care 1, 0, das ist der gleiche.
Der hier kann ich nicht zusammenfassen, und der hier habe ich ja mit
dem zusammengefasst, also es sind keine weiteren Zusammenfassungen
möglich.
Wenn wir jetzt gucken, welche wir nicht abgehakt haben, das ist auf
jeden Fall der hier, den konnten wir mit keinem zusammenfassen.
Das ist auf jeden Fall der hier, den konnten wir nicht weiter
zusammenfassen.
Und das ist natürlich C, weil es gibt keine weiteren
Zusammenfassungen, und alle, die hier waren, die sind jetzt irgendwie
vertreten hier drin.
So, das heißt von allen Zusammenfassungen, die ich habe, gibt es nur
A, B und C als Blöcke, die ich nicht weiter zusammenfassen kann.
Das bedeutet, das sind eigentlich die möglichst großen Blöcke von
einzelnen für diese Funktion, die wir haben.
Das sind also unsere Primimplikanten.
Und die stehen jetzt nur in der Form hier, also 0°C, 1°C und so weiter
und so fort.
Wir wissen, damit wir die Primimplikanten bilden können, müssen wir
die entsprechenden Produkte daraus ableiten.
Das heißt, für A haben wir 0°C, 1°C, das ist E quer, C, B quer.
Für B, das ist E quer, C, A quer.
Und für C, das ist B, A.
Das heißt, wir haben hier den ersten Schritt der Minimierung fertig
gemacht und wir haben alle Primimplikanten der Funktion tabularisch
bestimmt.
Und das sind nur drei Primimplikanten.
So, das sind die Primimplikanten der Funktion.
Sind wir somit fertig?
Können wir jetzt die Dezumtive in Normalform hinschreiben oder fehlt
uns noch etwas?
Ja, aber die ist komplett definiert, die Funktion.
Also wir haben ja die Funktionstabelle vorher gesehen und in der
Funktionstabelle waren Nullen und Einsen.
Und jetzt habe ich drei Primimplikanten der Funktion durch diese
Zusammenfassungen gemacht und die Frage ist, ob ich jetzt die
Dezumtive in Minimalform eingeben kann.
Was ist das Ergebnis des ersten Schritts der Minimierung?
Man bestimmt die Menge aller Primthermie.
Ja, aber wir wissen eigentlich noch nicht, ob alle diese Primthermie
notwendig sind.
Vielleicht ist einer von denen überdeckt, alle eins in der Funktion
oder zwei von denen.
Das heißt, wir müssen jetzt tatsächlich wie im KV-Diagramm die
Kernprimthermie bestimmen, also Kernprimimplikanten und dann eine
Menge von zusätzlichen Primimplikanten, sodass wir alle einstellen in
der Funktion überdecken.
So, nun haben wir die Sache nicht so grafisch für uns wie beim KV
-Diagramm, sodass wir durch scharfes Hinschauen gucken, welche
Thermien sind Kernprimimplikanten und welche sind Wahlprimimplikanten
und welche sind komplett entbehrlich.
Deshalb müssen wir uns überlegen, wie wir das hier machen.
Und hierzu, also müssen wir jetzt den zweiten Schritt der Minimierung
machen.
Wir wollen eine minimale Anzahl von Implikanten finden, von
Primimplikanten finden, die die Funktion überdecken.
Und da wir nur tabularisch arbeiten, haben wir hier bei dem KV
-Verfahren die Möglichkeit, dass wir eine sogenannte zweite KV-Tabelle
anlegen oder aufschreiben, eine sogenannte Überdeckungstabelle, mit
der wir tatsächlich feststellen können, welche Primimplikanten Kern,
welche entbehrlich, welche notwendig sind, um überhaupt die Funktion
zu realisieren.
Wie das Ganze funktioniert, wollen wir uns mal anhand von diesem
Beispiel sehen.
Also die zweite KV-Tabelle, die wird wie folgt definiert.
Die hat jetzt hier eine erste Spalte.
Da stehen die Primimplikanten, die wir bestimmt haben.
Das sind A, B und C.
Das haben wir mithilfe der ersten KV-Tabelle bestimmt.
Und dann haben wir natürlich hier die Min-Thermie der Funktion.
Und wir schreiben hier in dieser Tabelle für jeden Min-Therm, durch
welchen Primimplikanten dieser Min-Therm überdeckt wird.
Und dann kommt man natürlich auf diese Tabelle mit diesen Kreuzen.
Aber woher bekommen wir die Informationen?
Natürlich aus der ersten Tabelle.
Aus der ersten Tabelle hatten wir viele Informationen drin.
Wir haben gesehen, dass das unsere Primimplikanten sind.
A überdeckt 4, 5, 12 und 13.
Deshalb kommen hier diese Kreuze an den Stellen 4, 5, 12, 13.
B überdeckt 4, 6, 12, 14.
Also 4, 6, 12, 14.
Und C überdeckt diese 8 Min-Thermie.
Und da kommen hier die 8 Kreuze.
Und natürlich kann man für jeden Min-Therm Realisierungskosten
eingeben.
Zum Beispiel die Realisierungskosten für diesen Term hier sind 3, für
den Primimplikanten A, für den Primimplikanten B.
Und die Realisierungskosten für C sind nur 2.
Klar, C ist viel kürzer, weil das ja nur B-A-Quer ist, wie wir gesehen
haben.
Nun haben wir diese Tabelle und jetzt wollen wir...
kann man eigentlich aus der Tabelle vieles ablesen.
Wir werden auch einen systematischen Weg sehen, wie man sowas macht,
wenn man nicht so direkt die Lösung aus der Tabelle ablesen kann.
Ich meine, aus der Tabelle kann ich eigentlich ablesen, dass Min-Therm
2 nur durch C überdeckt ist.
Und wenn ich einen Min-Therm habe, der nur durch einen Primimplikanten
überdeckt ist, dann ist dieser Primimplikant ein Kernprimimplikant.
Das heißt, ich muss eigentlich Primimplikant C auf jeden Fall
aufnehmen, weil Min-Therm 2, aber auch Min-Therm 18, 22, 26 und 30 nur
durch C überdeckt.
Und wenn ich C auf jeden Fall in meine Lösung aufnehme, dann habe ich
tatsächlich 2, 14, 18, 22, 26 und 18 überdeckt.
Das heißt, da brauche ich mich nicht mehr darum zu kümmern.
Mit C habe ich einen Großteil der Aufgabe erledigt.
Min -Therm 2 habe ich überdeckt, Min-Therm 6 habe ich überdeckt, Min
-Therm 10, Min-Therm 14, 18, 22, 26...
So, dann schaue ich noch schärfer hin und dann sehe ich eigentlich,
dass zum Beispiel Min-Therm 5 nur durch A überdeckt wird.
Ja, weil da ist nur dort ein Kreuz.
Min-Therm 5 wird nur durch A überdeckt, beziehungsweise auch Min-Therm
13.
Das heißt, ich muss A unbedingt aufnehmen, weil das ist ein
Kernprimimplikant.
Und wenn ich A aufnehme, dann habe ich die Min-Thermen 4, 5, 12, 13
überdeckt.
Und wenn ich jetzt hingucke, dann sehe ich mit den Min-Thermen A und C
habe ich mit den Primimplikanten A und C elementär mit der Funktion
überdeckt.
Das heißt eigentlich, die disjunktive Minimalform der Funktion ist
nichts anderes als A oder C.
So, jetzt gucken wir mal das Ganze so ein bisschen systematisch.
Das heißt, die Kernprimimplikanten, beziehungsweise ist geschrieben
jetzt, was ich gesagt habe.
Das war auch systematisch, was ich gesagt habe, aber es ist jetzt
schwarz auf weiß systematisch.
Die Kernprimimplikanten sind diejenigen, die für ein einzelnes X hier
in der Spalte verantwortlich sind.
Also C zum Beispiel ist ein Kernprimimplikant, A ist auch ein
Kernprimimplikant.
Und jetzt gehen wir hin und machen das, was ich gerade gemacht habe.
Mit C überdecken wir die hier, mit A überdecken wir die hier.
Und somit haben wir elementär mit der Funktion überdeckt.
Das heißt, A oder C und wir wissen, A ist B-quer, C ist E-quer und C
ist A-quer oder B.
Das heißt, die disjunktive Minimalform der Funktion ist gefunden
worden.
Und man sieht hier, wir haben durch die Zusammenfassungen zunächst mal
drei Primimplikanten gefunden.
Und erst im zweiten Schritt der Minimierung, also mithilfe der zweiten
Quantentabelle hier, konnten wir wissen, welche Primimplikanten
überhaupt notwendig sind, um die Funktion zu überdecken.
So, nun ist die Sache nicht immer so einfach wie in diesem Beispiel.
Deshalb kann man diese zweite Quantentabelle mithilfe von anderen
Mitteln bearbeiten.
Man definiert eine sogenannte Überdeckungsfunktion.
Also man stellt die Tabelle auf und definiert eine
Überdeckungsfunktion, die für jeden Primimplikanten eine Bulschi
-Funktion enthält.
Und diese Variable, also wx, kennzeichnet, ob jetzt der betreffende
Primimplikant in die vereinfachte Lösung für die Überdeckungsfunktion
aufgenommen wird oder nicht.
Was bedeutet das?
Das bedeutet, wir definieren jetzt für jeden Primimplikanten eine
Bulschi -Variable wx.
Das heißt, wir haben hier eine Bulschi-Variable wa, eine Bulschi
-Variable wa und eine Bulschi-Variable wb und eine Bulschi-Variable
wc.
Und diese Überdeckungsfunktion, die wir definieren, also ganz wichtig,
u umlaut f, die sagt uns eigentlich, welche Mintermien durch welche
Primimplikanten überdeckt werden.
Und wir fangen an, Minterm 2 ist überdeckt durch wc.
Ich muss alle Mintermien überdecken, deshalb muss ich natürlich jetzt
hier konjunktiv verknüpfen.
Um Minterm 4 zu überdecken, Minterm 4 ist überdeckt durch a oder c
oder b.
Minterm 5 ist überdeckt durch Primimplikant a.
Minterm 6 ist überdeckt durch b oder c.
Minterm 10 ist überdeckt durch c, also wc.
12 a oder b.
13 ist nur a.
14 ist b oder c.
Und dann die restlichen ist nur c, also wc, wc, wc und wc.
Das ist meine Überdeckungsfunktion.
Das heißt, die sagt mir eigentlich, durch welche Primimplikanten
welcher Minterm überdeckt wird.
Und was bedeutet eigentlich jetzt, die geringste Menge an
Primimplikanten zu finden, die alle Mintermien überdecken?
Das bedeutet nichts anderes, als diese Überdeckungsfunktion zu
minimieren.
Das ist eine Überdeckungsfunktion mit drei Eingangsvariablen w, a, w,
b, w, c.
Und die muss ich nur minimieren.
Zum Beispiel Schaltalgebraisch vereinfachen oder KV-Diagramm oder
Coimbe -Klasky.
Also ich definiere eine neue Funktion und damit ich die geringste
Anzahl von Primimplikanten finden kann, die notwendig sind, muss ich
diese Funktion minimieren.
Wir machen es jetzt Schaltalgebraisch.
Wenn wir hier ein bisschen vereinfachen und natürlich das
Absorptionsgesetz nicht vergessen, dann können wir hier
ausmultiplizieren.
Das ist was ich gemacht habe und dann kommen wir auf w, a, c.
Was bedeutet das?
Das bedeutet, diese Überdeckungsfunktion sagt uns jetzt, um all diese
Mintermien zu überdecken, musst du a oder c nehmen.
Also musst du a und c nehmen.
Und das ist beschrieben durch diesen konjunktiven Ausdruck w, a oder
w, c.
Das heißt eigentlich, die Minimalform, die wir gerade suchen, ist das,
was wir vorher auch gefunden haben, mithilfe von dieser Abarbeitung
der Tabelle.
Das heißt, man braucht die Tabelle in der Form nicht abzuarbeiten,
sondern man kann direkt so eine Überdeckungsfunktion aufstellen.
Aber natürlich, wenn ich die Tabelle zunächst mal vereinfache, wo es
klar ist, dass bestimmte Kernprimimplikanten aufgenommen werden
müssen, dann ist meine Überdeckungsfunktion nicht so komplex und da
muss ich nicht so viel minimieren.
So, nun gibt es noch weitere Tricks.
Und zwar nehmen wir mal an, wir haben die Überdeckungstabelle
aufgestellt.
Wir haben alle Kernprimimplikanten identifiziert.
Das heißt, solche Kernprimimplikanten oder Primimplikanten, die für
ein x in einer Spalte verantwortlich waren.
Und dann kommen wir auf so etwas.
Das ist eine Tabelle, die wir jetzt nicht mehr sehen können.
Also eine Teiltabelle, eine reduzierte Tabelle der
Überdeckungstabelle, wo wir nicht eine Zeile, eine Spalte haben mit
nur einer x.
Aber man kann hier solche Eigenschaften mal betrachten und kann man
die Tabelle nochmal vereinfachen.
Die erste Eigenschaft ist Spaltendominanz.
Das heißt, Spalten, die andere überdecken, können gestrichen werden.
Man sieht hier, das heißt, die x hier in der Spalte von Minterm i
überdecken die x in der Spalte von Minterm j.
Was bedeutet das?
Das bedeutet eigentlich, wenn ich sowieso Minterm i überdecken will,
wenn ich sowieso das habe, dann habe ich auch den anderen.
Das heißt, ich kann eigentlich das hier wegmachen.
Das heißt, Minterm j ist automatisch überdeckt, wenn ich Minterm mi
überdecke.
Beziehungsweise Minterm ms ist automatisch überdeckt, wenn ich Minterm
mu oder Minterm mw ist automatisch überdeckt, wenn ich Minterm mx
habe.
Das heißt, die sind schon da, da brauche ich mich nicht mehr darum zu
kümmern und deshalb kann ich diese Spalten wegstreichen.
Und ich kriege dann statt hier sechs Spalten drei Spalten in meiner
Überdeckungstabelle.
Es gibt auch die Zeilendominanz und zwar Zeilen in der
Überdeckungstabelle mit nur Einträgen, die andere Zeilen haben.
Also zum Beispiel A hat nur Einträge wie B und C hat nur Einträge wie
B und E hat nur Einträge wie D.
Geht es ein bisschen leiser hier hinten?
Danke.
Das heißt, alle diese Zeilen, die kann ich auch wegstreichen, weil man
sieht hier, wenn ich sowieso hier die Minterm mi überdecke, mi und mj
durch B, dann ist A eigentlich entbehrlich, brauche ich nicht, bringt
mir nichts mehr.
Also ist überhaupt nicht wert eigentlich für die Minimierung.
Das gleiche hier E.
Ich sehe durch den Primimplikanten E überdecke ich hier zwei Minterm
mi, mw und mx, die automatisch da sein müssen, wenn ich D nehme, weil
D muss ich sowieso nehmen wahrscheinlich, damit ich mj überdecke.
Das heißt, wir haben auf der einen Seite die Feststellung der
Kernprimimplikanten und die Streichung der Zeilen, der Spalten oder
der Mintermi, die durch Kernprimimplikanten überdeckt werden.
Dann kriegen wir eine reduzierte Tabelle.
Diese reduzierte Tabelle können wir noch weiter reduzieren mithilfe
der Regeln der Spalten- und Zeilendominanz.
Natürlich bei Zeilendominanz müssen wir hier aufpassen, dass wir keine
Zeilen streichen, die billiger sind als andere Zeilen, die Grund für
die Streichung waren.
Und wenn wir das haben und es bleibt noch etwas übrig von der
Überdeckungs -Tabelle, dann stellen wir die Überdeckungsfunktion auf
und minimieren wir sie.
So, das habe ich alles erklärt.
Wir sehen hier in dem Beispiel, wenn wir nur den ersten Schritt
machen, also Kernprimimplikanten identifizieren und die Mintermi
streichen, die dadurch überdeckt werden, dann haben wir unsere Lösung.
Da brauchen wir uns keine Gedanken weiter darüber zu machen.
Okay, so viel dazu.
Gibt es Fragen?
Okay, das nächste wäre das Konsensusverfahren, aber weil ihr so brav
wart heute und wir haben nur noch zweieinhalb Minuten und ich immer
wieder die Pause vergessen habe, die ich immer wieder versprochen habe
in der Mitte der Vorlesung, schlage ich mal vor, dass wir für heute
Schluss machen.
Donnerstag, wie ihr wisst, ist schon wieder mal ein Feiertag, leider.
Deshalb fällt die Vorlesung aus und wir machen weiter am nächsten
Dienstag.
Vielen Dank für die Aufmerksamkeit.