Hallo, ich begrüße euch herzlich zur heutigen Vorlesung.
Wir werden heute die Minimierungsverfahren, die wir kennengelernt
haben letzte Woche, anhand von Aufgaben nochmal vertiefen, bevor wir
zum nächsten Thema hier mit dem Stoff in der Vorlesung gehen.
Wir haben gesehen, dass wir unterschiedliche Verfahren zur Minimierung
bürgerlicher Funktionen haben.
Das sind die grafischen Verfahren, das sind tabellarische Verfahren
wie das Klein-McCluskey-Konsensusverfahren, aber auch algebraische
Verfahren.
Wir haben das sogenannte Nelson-Verfahren kennengelernt.
Und als letztes hatten wir das letzte Mal auch die Möglichkeit
gesehen, wie man mehrere Funktionen gemeinsam minimiert.
Das heißt, man sucht nicht die Prim-Thermie einer einzelnen Funktion,
sondern man sucht sogenannte Koppel-Thermie, beziehungsweise auch
Koppel -Prim-Thermie mehrerer Funktionen, um die gesamte
Realisierungskosten von einem Funktionsbündel zu minimieren.
Allgemein wissen wir, dass die Minimierung einer Buhlchen-Funktion in
zwei Schritten erfolgt.
Zunächst mal mit Hilfe von den Verfahren, die auf der Folie vorher
waren, bestimmen wir alle Prim-Thermie der Funktion.
Das heißt, alle Prim-Implikanten der Funktion, beziehungsweise Prim
-Implikate der Funktion.
Anschließend müssen wir eine irredundante Überdeckung finden, also
eine geeignete Auswahl, eine Menge von Prim-Thermien, sodass alle
Einstellen, beziehungsweise alle Nullstellen der Funktion überdeckt
werden.
Sprich, wir müssen das sogenannte Überdeckungsproblem lösen.
Und die Vorgehensweise kann man hier sehen, anhand von diesem
Diagramm.
Das heißt, bei Funktionen mit bis zu sechs Eingangsvariablen, könnte
man natürlich das Problem noch auf anschauliche Art und Weise mit
Hilfe von KV-Diagrammen lösen.
Das heißt, zunächst mal die Prim-Thermien mit Hilfe von KV-Diagrammen
bestimmen und das Überdeckungsproblem entweder durch eine
Überdeckungstabelle oder durch Hinschauen diese Auswahl treffen.
Bei tabellarischen Verfahren, also geeignet für Funktionen mit mehr
als sechs Eingangsvariablen, ist die Aufgabe, aus einer disjunktiven
Form die disjunktive Minimalform, beziehungsweise aus einer
konjunktiven Form die konjunktive Minimalform der Funktionen zu
bestimmen.
Da haben wir das Konsensusverfahren kennengelernt und das Quine
-McCluskey -Verfahren, mit deren Hilfe wir die Prim-Thermien
bestimmen.
Anschließend mit Hilfe der zweiten Quine-Thermien-Tabelle bzw.
mit Hilfe der Überdeckungstabelle können wir eine geeignete Auswahl
der Prim-Thermien treffen.
Beim Nelson-Verfahren waren die Verhältnisse ein bisschen anders.
Das heißt, aus einer disjunktiven Form der Funktion haben wir eine
konjunktive Minimalform bestimmt, beziehungsweise aus einer
konjunktiven Form eine disjunktive Minimalform.
Das Nelson-Verfahren liefert durch Ausdistribuieren und Ausnutzung von
Gesetzen der Boltzschen-Algebra eine Konjunktion aller Prim-Implikate,
beziehungsweise eine Disjunktion aller Prim-Implikanten.
Das bedeutet, man muss, um die Minimalform zu bestimmen, nochmal das
Überdeckungsproblem lösen, zum Beispiel mit Hilfe von einer
Überdeckungs -Tabelle.
Das Ganze wollen wir vertiefen anhand von Aufgaben heute.
Bevor ich damit anfange, kurz eine Wiederholung zur Darstellung von
Funktionen im KV-Diagramm.
Wir wissen, der Ausgangspunkt ist ein Rechteck, wo die rechte Hälfte
für die Variable A und die linke Hälfte für die Variable B ist.
Für zwei Variablen haben wir vier Belegungen.
Das heißt, wir erweitern das Diagramm durch Spiegelung um die
horizontale Achse.
Dann haben wir vier Felder.
In den Feldern tragen wir die Indizes, das heißt, das sind die
Belegungen der Variablen interpretiert als eine Dezimalzahl.
Und das Spiel können wir fortsetzen für drei Variablen,
beziehungsweise für vier Variablen, für fünf Variablen.
Und wir wissen, das Minimieren im KV-Diagramm bedeutet nichts anderes,
als der Versuch, möglichst große Blöcke zu bilden, also von Nullen
beziehungsweise von Einsen.
Blöcke, die symmetrisch zueinander sind, bezüglich der Symmetrieachse
Höchste Ordnung.
Das heißt, hier diese Achse, die Felder 4, 20, 6, 22, 14, 30 und 12,
28, die ist die Achse, um die wir zuletzt gespiegelt haben, das heißt
die Symmetrieachse Höchste Ordnung.
Und man sieht, dass diese Felder hier symmetrisch zueinander liegen
und in der Tat kann man dieses Feld hier ablesen.
Das ist alles, was nicht in D, nicht in C ist und nicht in D, aber in
A.
Und dann kann man somit ein Produkttherm bilden.
Wenn das nicht klappt, dann hat man irgendwas Falsches zusammengefasst
im KV-Diagramm.
Weitere Beispiele, wenn wir hier beispielsweise Einsen in diesen zwei
Spalten haben, dann sieht man, das ist das Feld, alles was in A liegt
und nicht in C.
Das gleiche Spiel können wir hier sehen.
Wir wissen, das ist B quer, A quer.
Also das sind die Felder, die weder in A noch in B sind.
Übertragen auf ein KV-Diagramm hier bedeutet, dass die Felder so
aussehen.
Das heißt, diese Felder hier, das ist immer der Bereich, wo A 0 ist
und B 0 ist.
B ist in der Mitte 1, also oben und unten 0.
A ist hier und hier 1, das heißt in den restlichen Feldern 0.
Deshalb ist dieses Blaue, der blaue Bereich oder die blauen Felder
sind B quer, A quer.
Und so weiter und so fort.
Das war B und A.
Und B und A, ein Teil davon wäre hier.
Aber wenn wir nur das hier nehmen, dann sehen wir, das ist B und A und
E quer.
Wenn wir also B und A bilden, dann würde das bedeuten, das sind die
Quadrate hier auf der linken und auf der rechten Seite.
Und wir können das auch für 6, für weitere Variablen hier machen, wie
ich das vorletzte Mal hier erklärt habe.
Das heißt, das wäre die Variable D.
Das ist die Variable, wenn wir hier einen Schritt zurück gehen, in der
Mitte war die Variable C.
Ja, das ist die Variable C.
Und das ist die Variable hier E.
Und dann haben wir hier durch die Spiegelung eine neue Variable, die
heißt F.
Und wir wissen, dass wir die Indizes auch automatisch bilden können.
Zum Beispiel hier, wenn ich suche, welche Nummer hier einzutragen ist,
dann sehe ich, 19 ist spiegelbildlich zu dem hier.
Der Index hier, Index neu, ist gleich Index alt.
Plus 2 hoch N minus 1.
N in dem Fall haben wir ein KV-Diagramm mit 6 Eingangsvariablen.
A, B, C, D, E, F.
N ist gleich 6, daraus folgt der Index, der neue Index hier, ist
gleich der alte, 19 plus 2 hoch 6 minus 1, also ist gleich 19 plus 32.
Das ist ungefähr so 51.
Das heißt hier tragen wir 50, 51.
Und das gleiche Spiel kann man machen, man sieht hier die Felder, die
sind spiegelbildlich zueinander, das heißt es ist hier Nummer 40, also
8 plus 32, 41 und so weiter und so fort.
So, das wissen wir aber alles.
Wir wollen damit Buhl'sche Funktionen minimieren und fangen wir mal
jetzt an mit den Aufgaben, gegeben seien zwei Buhl'sche Funktionen, F1
und F2, von vier Eingangsvariablen, D, C, B und A.
Und wir sollen sie vereinfachen, zunächst mal durch schaltalgebraische
Umformung, was wir am Anfang der Vorlesung kennengelernt haben, und
anschließend mit Hilfe von KV-Diagrammen.
Schaltalgebraische Umformungen, das sollte ja ein Kinderspiel für alle
hier sein, das heißt ich fange z.B.
an hier auszudistribuieren, B d-quer oder B c-quer oder B b oder C d
-quer oder C c-quer oder C b und das Ganze multipliziert mit d oder c
-quer oder b oder a.
Und bevor wir jetzt einen weiteren Schritt machen, sollen wir mal
gucken, was kann man hier kürzen.
Das ist eigentlich entscheidend, wir wissen c und c-quer ist null, wir
wissen b und b ist gleich b und wir wissen laut Absorptionsgesetz,
dass jetzt dieser Term b jeden weiteren Term absorbiert, der b
enthält.
Das heißt, alle diese Terme, wo b auftaucht, werden von b absorbiert,
sodass am Ende hier nichts anderes bleibt als b oder c d-quer
multipliziert mit d oder c oder b oder a.
Jetzt nochmal das gleiche Spiel, das heißt, das ist ein b-d oder b-c
oder b-b oder b-a oder c-d-quer-d oder c-d-quer-c oder c-d-quer-b oder
c...
Warum seid ihr so ruhig?
So, das gleiche Spiel hier.
Wir wissen, dass das hier null ist, das ist gleich null.
Und wir wissen, dass wir hier ein b haben.
Das heißt, alle Terme, die ein b haben, werden auch davon absorbiert.
Ja, das ist hier.
Am Ende bleibt also nichts anderes als...
Wie bitte?
Das hier?
Das da?
Ah, Entschuldigung, ja, das ist ein c-quer, ja.
Oh mein Gott, oh mein Gott, oh mein Gott, oh mein Gott.
Das macht aber mein Leben ein bisschen einfacher, glaube ich.
Das ist b-c-quer.
Das ist auch ein c-quer, das ist noch besser.
Ja, das heißt, der Term hier ist gleich auch null, weil wir haben c
und c-quer.
Stimmt das jetzt?
Genau.
Also insgesamt bleibt hier übrig nichts anderes als b oder c-d-quer-a.
Ja, somit haben wir eigentlich diese Funktion mithilfe von den
Mitteln, die wir bis jetzt kennengelernt haben, inverses Element,
Absorptionsgesetz und so weiter und so fort, minimiert.
Jetzt gucken wir mal, wie wir das hier mithilfe von KV-Diagramm
machen.
Wie geht man hier vor?
So, gegeben ist die Funktion in konjunktiver Form.
Das heißt, alle diese Summentermi der Funktion, also b oder c, d-quer
oder c-quer oder b, die sind Implikate der Funktion.
Was bedeutet das?
Das bedeutet eigentlich, dass ich jetzt die Felder hier im KV-Diagramm
suche, wo b oder c ist.
Das heißt, das ist alles, was nicht in b und nicht in c ist, da sollte
dort eine Null sein.
Und nicht b und nicht c sind diese zwei Felder.
Das nächste Feld ist d-quer, c-quer und b.
Das heißt, alles was in d und in c, d und c, das sind die Felder 12,
13, 14, 15 und nicht b, das heißt, das sind die Felder hier, da kommen
auch Nullen rein.
Und der letzte Term, das ist der Max-Term, d oder c-quer oder b oder
a, also alles was nicht in d ist, nicht in d, aber in c, nicht in b
und nicht in a, das ist die Null hier.
Somit habe ich jetzt diese Funktion in das KV-Diagramm übertragen.
Das ist eine vollständig definierte Funktion, das heißt, die
restlichen Felder sind hier Einsen.
Und wenn wir die Funktion jetzt hier versuchen zu minimieren, dann
versuchen wir möglichst große Blöcke von Einsen zu bilden.
Das ist zunächst mal ein Block und dann sehen wir, dass wir hier auch
diese Zusammenfassung machen.
Das heißt, wenn ich die Funktion hier aufschreibe, f1 von d, c, b, a,
ist nichts anderes als b oder der Term hier, das ist alles was nicht
in d, c und a ist.
Also nicht in d, c und a und das ist genau, was wir vorher auf der
Folie bekommen haben.
So, für die zweite Funktion, die Funktion ist eingegeben in
destruktiver Form und wir wollen diese Funktion zunächst mal
schaltalgebraisch minimieren.
Dann sieht man hier beispielsweise, dass wir hier d, c haben und hier
d, c, einmal mit a und einmal mit a quer.
Das heißt, die kann ich mal ausklammern, a oder a quer.
Und dann sieht man hier, dass wir hier auch einmal b, c haben und hier
auch b, c.
Das heißt, ich kann b, c ausklammern, dann bleibt d oder d quer.
Wir wissen, d oder d quer, a oder a quer sind eins und eins und
irgendetwas ist irgendetwas.
Das heißt, es bleibt hier d, c oder b, c.
Und jetzt versuchen wir das Ganze hier mit Hilfe von KV-Diagramm zu
machen.
Mit Hilfe von KV-Diagramm, da müssen wir jetzt hier diese ganzen Terme
eintragen.
c, d, a, also c, d und a, das sind hier, da kommen hier Einsen.
Die Produktterme sind also in dem Fall Implikanten der Funktion.
Die zwei Felder hier und dann haben wir b, c, d.
b und c sind hier und d, das sind also die Eins und die Eins.
Und dann a quer, c, d, c und d ist die Hälfte hier, also die Felder
12, 13, 14, 15 und 12.
Somit haben wir unsere Funktion in das KV-Diagramm eingetragen.
Wenn wir hier versuchen zu minimieren, dann versuchen wir möglichst
große Einsblöcke zu bilden.
Zum Beispiel sowas und dann hier wissen wir, dass die hier auch ein
Implikant der Funktion und dann sehen wir, wenn wir jetzt hier die
disjunktive Minimalform hier aufschreiben, dann wissen wir, dass diese
zwei Terme Kernprim-Implikanten sind, weil 12 und 13 nur durch den
grünen überdeckt werden und 6 und 7 durch den roten.
Das heißt eigentlich, die Funktion ist nichts anderes als c, b oder d,
c.
Also d, c war hier grün und das hier war ja rot.
Natürlich kann man die Funktion hier die konjunktive Minimalform
eingeben, weil wir wissen ja, dass die restlichen Felder hier Nullen
sind.
Und wenn wir hier die konjunktive Minimalform eingeben, das wäre eine
Vereinfachung, also f2, konjunktive Minimalform, dann könnte man die
hier auch aufschreiben, wenn man will.
Weil an der Stelle haben wir nichts gesagt über die Kosten der
Realisierung von Produkttermen oder Summentermen.
Das ist eigentlich der Block hier,
der Block hier und dann der Block hier.
Und der Block hier ist nichts anderes als c, c multipliziert mit, das
ist der erste Summenterm, multipliziert mit alles, was nicht in b und
nicht in d, also d oder b.
Und man sieht hier eigentlich, das ist das gleiche wie vorher, wie
hier in dem Beispiel, wo ich c ausgeklammert habe.
Einmal haben wir ein Summenterm, bestehend nur auf c, das ist der
Block hier und einmal Summenterm, bestehend aus den 0, 1, 4, 5, also d
oder b.
Okay, so viel dazu.
Ich glaube, das ist ja gar nicht so kompliziert und schwierig, sondern
kann jeder von euch hier machen.
Wir wollen das Ganze anhand von einem weiteren Beispiel vertiefen, und
zwar gegeben sei eine vollständig definierte Funktion.
Die Funktion ist definiert durch ihre 1-Stellen bzw.
durch die Mintermi.
Das ist eine Funktion mit 5 Eingangsvariablen e, d, c, b, a und mit
den Mintermen 0 bis 28 und wir suchen die disjunktive Minimalform und
die konjunktive Minimalform der Funktion, und zwar grafisch mithilfe
von dem KV-Diagramm.
Was muss man als erstes machen?
Man muss natürlich diese Mintermi zunächst einmal hier eintragen und
das ist sehr dankbar, wenn man das KV-Diagramm hat und die Indizes in
den Feldern, dann kann man das blind machen, d.h.
hier habe ich Minterm 0, 1, 3, 4, 6, 7, 8, 9, 12, 14,
15, 16, 17, 19, 20, 24, 25 und die 28.
Jetzt haben wir alle 1-Stellen eingetragen.
Der Rest, da die Funktionen vollständig definiert sind, sind
eigentlich die 0-Stellen der Funktion.
Und was machen wir jetzt?
Wir versuchen möglichst große Zusammenfassungen von Nullen und
Einzelnen zu machen.
Und klar, man sieht hier vielleicht mit bloßen Augen, dass die hier
symmetrisch zueinander liegen, d.h.
die kann ich hier zusammenfassen.
Man sieht vielleicht, dass man die hier zusammenfassen kann, zu einem
C -A-E-Q-R.
Man sieht z.B., dass man die zwei hier einzeln zusammenfassen kann und
die sind spiegelbildlich symmetrisch zu dem hier, d.h.
die zwei gehören ja zusammen.
Man sieht, dass die Ecken, alle diese Ecken hier in dem 4er KV
-Diagramm vorhanden sind, bzw.
in dem KV-Diagramm für 4 Variablen bzw.
für 5 Variablen und die alle kann ich dann zusammenfassen zu alles,
was wir B-Quer oder A-Quer nennen.
So, und so weiter und so fort.
Jetzt bleiben hier diese Einzelnen hier, da kann der eine auf die Idee
kommen, ah ja, ich kann diese Einzelnen hier so zusammenfassen.
Das sind hier die zwei Einzelnen, die kann ich zusammenfassen mit
denen hier.
Wenn man schärfer hinguckt, dann sieht man, dass spiegelbildlich dazu
auch die Einzelnen hier vorhanden sind.
Also ich kann sie auch zusammenfassen zu einem Term.
Also 16 und 24 sind Felder, wenn man das Ganze so dreidimensional
betrachtet, die sind benachbart zueinander bzw.
0 und 16 und 8 und 24.
Und deshalb kann ich diese Zusammenfassung hier machen.
Was kann ich noch zusammenfassen?
Man sieht es vielleicht nicht so gut, aber ich kann z.B.
3 und 7 zusammenfassen.
Es ist mehr oder weniger ein Spiel, also übt das mal ein bisschen.
Aber jetzt wollen wir es ein bisschen genauer machen.
Das sind die Einzelnen hier und jetzt versuchen wir mal
zusammenzufassen.
Sieht man klar, das ist hier, die habe ich auch richtig gemacht, das
ist alles, was nicht in E ist, aber in C und B, also E-Quer, C, B.
Dann kann ich natürlich die hier zusammenfassen, das ist alles, was
nicht in E ist, in C und nicht in A.
Dann können wir natürlich diese zwei Einzelnen zusammenfassen,
spiegelbildlich dazu die hier.
Da kommt hier also ein Feld, wie man sieht, das ist alles, was nicht
in D ist und nicht in C, aber in A.
Ja, ist es schnell oder ist es okay, das so zu machen?
Das kennt jeder jetzt von euch.
Oder gibt es jemanden, der mir nicht folgen kann hier?
Okay, das ist nicht der Fall, super.
Dann machen wir weiter und zwar diese Einzelnen hier, das ist wie
gesagt alles, was nicht in C ist und nicht in B, das heißt C-Quer, B
-Quer.
Dann können wir natürlich die zwei hier einzeln, wir haben aber
gesehen, dass wir die mit den Ecken zusammenfassen können und das ist
alles, was nicht in B und nicht in A.
Und der letzte Term, der schwer zu sehen war, das waren die drei und
sieben, das ist der hier.
Und der hier ist alles, was nicht in D ist und nicht in E, aber in B
und in A.
Das heißt, man sieht hier, der hat nur zwei Minterm, deshalb fehlt nur
ein Lateral in dem Produktterm.
So, dann haben wir eigentlich alle und jetzt wollen wir die
destruktive Minimalform bestimmen.
Das heißt, der erste Schritt, was wir machen müssen, ist zu gucken,
welche dieser Primimplikanten Kernprimimplikanten sind.
Also, das sind solche Implikanten oder Felder, durch die ein Minterm
oder nur durch die ein Minterm überdeckt wird.
Und dann sehen wir, dass dieses hellblaue auf jeden Fall ein
Kernprimimplikant ist, weil die Eins und die Eins nur durch den
überdeckt wird.
Dass dieser Orangene auch wegen der Eins hier ein Kernprimimplikant
und dass der Grüne auch ein Kernprimimplikant ist,
sind dann diese hier.
Und jetzt müssen wir die kleinste Menge finden, mit der wir die
restlichen Einstellen, die nicht durch die Kernprimimplikanten
überdeckt werden, überdecken.
Das ist der vierte hier.
Also, nochmal, das ist einmal der Blaue wegen der Eins hier, einmal
der Hellblaue wegen der Eins hier, einmal der Grüne wegen der Eins und
einmal der Orangene wegen der Eins.
Jetzt der nächste Schritt ist zu gucken, welche weiteren Termine
notwendig sind, um die Funktion zu überdecken.
Wenn wir die Blauen hier haben, dann haben wir diese Einsen überdeckt.
Also, wenn wir B-Quer, A-Quer haben, dann haben wir eigentlich diese
Eins, diese Eins, diese Eins, diese Eins, die haben wir überdeckt.
Wenn wir Hellblau nehmen, dann haben wir zusätzlich diese Einsen hier
noch dazu überdeckt.
Wenn wir den Grünen nehmen, dann haben wir die vier Einsen hier
überdeckt.
Wenn wir den, wie heißt der, den Orangenen, dann haben wir nochmal die
zwei Einsen überdeckt.
So, das heißt, eigentlich das Lösen des Überdeckungsproblems bedeutet
jetzt, wir müssen weitere Primimplikanten aufnehmen, sodass
Einsstellen, die nicht durch die Kernprimimplikanten überdeckt werden,
auch überdeckt sind.
Und man guckt hier, durch die Kernprimimplikanten sind alle Einstellen
der Funktion überdeckt.
Das heißt, die restlichen Primimplikanten, die wir bestimmt haben, die
sind entperrlich.
Die brauchen wir nicht für eine Realisierung dieser Funktion.
Also die restlichen hier, die sind entperrlich und somit die
disjunktive Minimalform ist die Disjunktion der Kernprimimplikanten.
Also können wir hinschreiben.
So, gibt es Fragen dazu?
Das ist nicht der Fall.
Dann wollen wir jetzt die konjunktive Minimalform bestimmen.
Wir haben hier die Einsen eingetragen, die restlichen Felder hier sind
also mit Nullen belegt.
Ich habe sie hier nicht eingetragen, damit das Diagramm nicht so
überfüllt wird.
Hier habe ich die Nullstellen eingetragen und was wir machen ist das
gleiche.
Wir versuchen möglichst große Nullblöcke zu bilden.
Und man sieht hier zunächst mal die Felder hier.
Das ist alles was in E, C und B, also das ist E-Quer oder C-Quer oder
B -Quer.
Dann können wir natürlich die vier Nullen hier zusammenfassen.
Das ist alles, das ist E-Quer oder C-Quer oder A-Quer.
Dann können wir die vier hier zusammenfassen.
Das ist D-Quer, E-Quer, B-Quer, also oder B-Quer.
Und dann können wir beispielsweise die Nullen hier zusammenfassen.
Das ist alles was in B, aber nicht in C und nicht in A.
Also in konjunktiver Form heißt es dann C-Quer oder B-Quer oder A
-Quer.
Und dann sieht man hier beispielsweise, dass wir hier die zwei Nullen
und die zwei Nullen zusammenfassen können.
Und das ist nichts anderes als E-Quer oder B-Quer oder A-Quer.
Man sieht zusätzlich, dass wir hier diese Nullen, die sind auch
symmetrisch zueinander.
Und das ist alles, was nicht in C, aber in A und nicht in B ist.
Das heißt C-Quer oder B-Quer oder A-Quer.
Und jetzt, was man noch zusammenfassen kann, zum Beispiel diese zwei
Nullen.
Aber man sieht hier, dass dazu auch nochmal hier zwei Nullen in den
spiegelbildlichen Feldern.
Also die kann ich hier zusammenfassen zu einem Implikaten, der nicht
in D, aber in B und nicht in C ist.
Also D-Quer oder C-Quer oder B-Quer.
Und was müssen wir als nächstes machen, um zu bestimmen, welche
Kernprimimplikate sind.
Und die Kernprimimplikate, das ist der grüne, zunächst mal hier wegen
der Null hier oben, weil nur durch diesen grünen wird diese Null
überdeckt.
Das ist dann hier der lila, weil diese Nullen hier nur durch lila
überdeckt werden.
Und das ist zusätzlich der blaue, also der hellblaue, weil dieser Null
nur durch hellblau überdeckt wird.
So, wenn wir jetzt hier alle diese nehmen, dann haben wir die Null
überdeckt, die Null überdeckt, die Null, die Null, die Null und die
Null.
Und dann haben wir diese Nullen hier überdeckt.
Das heißt, unser Überdeckungsproblem bedeutet jetzt aus dem Rest ein
Primimplikat zu wählen, der die restlichen Nullen, die nicht durch
Kernprimimplikate überdeckt werden, überdeckt.
Und man sieht es, die restlichen Nullen sind eigentlich dieses
Orangene hier.
Das heißt, wenn man den Orangenen, also E quer oder C quer oder B quer
dazu nimmt, dann hat man alle Nullstellen der Funktion überdeckt.
Das heißt, wir haben die Kernprimimplikanten plus den Orangenen und
somit sind alle Nullstellen überdeckt.
Und damit ist das die konjunktive Minimalform der Funktion.
Gibt es Fragen dazu?
Gut, das ist nicht der Fall, deshalb betrachte ich mal das Thema
Minimierung mit KV-Diagrammen an der Stelle für abgeschlossen.
Das wird noch im Tutorium vertieft oder geübt.
Die Leute, die etwas nicht verstanden haben, die sollen sich bei mir
melden oder bei den Tutoren, damit das vom Tisch ist, weil das ist
eine Sache, die wir auch für andere Aufgaben in der Vorlesung
brauchen.
Das zweite Verfahren oder das erste tabellarische Verfahren, was wir
kennengelernt haben, das letzte Mal, ist das sogenannte Kwan-McCluskey
-Verfahren.
Also für Funktionen mit mehr als sechs Eingangsvariablen, weil sonst
wird das KV-Diagramm überhaupt nicht mehr übersichtlich.
Und der Ausgangspunkt dieses Verfahrens sind immer die Min-Thermy oder
die Max-Thermy der Funktion.
Das heißt, Ausgangspunkt sind die Min-Thermy, wenn ich die disjunktive
Minimalform bestimme.
Die tragen wir in die sogenannte R-Sequential Tabelle, angeordnet nach
Gewicht, also nach Anzahl der Einsen, die bei den Belegungen der
Variablen auftreten.
Und dann versuchen wir, Ausdrücke, die sich nur in einer Variable
unterscheiden, zusammenzufassen.
Das sind zwei Ausdrücke oder zwei Min-Thermy, die spiegelbildlich
zueinander im KV-Diagramm liegen.
Und das machen wir mit allen Min-Thermy, die wir haben.
Das heißt, wenn wir etwas zusammengefasst haben, dann die Min-Thermy,
die schmeißen wir nicht raus, sondern die nehmen an weiteren
Vergleichen teil.
Und das wiederholen wir so lange, bis wir keine weiteren
Zusammenfassungen machen können.
Das haben wir, wie gesagt, in der Vorlesung kennengelernt.
Und am Ende entstehen Implikanten bestimmter Kartenordnungen, die
nicht mehr zusammengefasst werden können.
Und die sind dann unsere Prim-Thermy der Funktion.
In dem Fall, wenn wir von den Min-Thermen anfangen, sind das dann die
Prim -Implikanten der Funktion.
Das Ganze will ich anhand von zwei Beispielen durchführen.
Einmal zur Bestimmung der disjunktiven Minimalform.
Fangen wir mal an mit der disjunktiven Minimalform.
Das sind die Variablen, also d, c, b, a, Min-Thermy 0 bis 0.
Das sind die Funktionen mit Hilfe von Quine-McCluskey.
Das ist, was das Verfahren im ersten Schritt liefert.
Und anschließend wollen wir alle möglichen disjunktiven Minimalformen
bestimmen.
Also, das ist der zweite Schritt der Minimierung.
Wir müssen das sogenannte Überdeckungsproblem lösen.
So, wie fängt man an?
Erster Schritt, die Min-Thermy nach Gewicht, also Anzahl der Einsen in
der zugehörigen Belegung der Eingangsvariablen sortieren und in die R
-Sequency -Tabelle eintragen.
Das sind unsere Min-Thermy.
Min-Therm 0 hat Gewicht 0, weil in der Belegung der Variablen gibt es
keine Eins.
Alle Variablen sind negiert.
Min-Therm 2 und Min-Therm 8 haben Gewicht 1.
Was man sieht hier in der Belegung ist nur eine Eins.
Min-Therm 5, 6, 9 und 12 haben jeweils zwei Einsen in der Belegung der
Eingangsvariablen.
Deshalb sind sie in der Gewichtsklasse 2.
Und in der Gewichtsklasse 3 sind dann die Min-Thermy 7 und 13, weil es
hier drei Einsen sind.
Und in der Gewichtsklasse 4 ist Min-Therm 15.
Was bedeutet das?
Bei den Verfahren geht man so, dass man zunächst einmal Min-Thermy
hier miteinander vergleicht und guckt, ob man sie zusammenfasst.
Und wir wissen, wann können wir zwei Min-Thermy zusammenfassen?
Wir können zwei Min-Thermy zusammenfassen, wenn sie komplementär in
einer Variable belegt sind.
Was bedeutet das eigentlich bezüglich der Vergleiche, die wir hier
ausführen müssen?
Das bedeutet eigentlich, wir brauchen nur Min-Thermy von zwei
benachbarten Gewichtsklassen miteinander zu vergleichen.
Nur dort müssen wir gucken, ob etwas zusammengefasst werden muss oder
nicht.
Weil wenn man sieht, ich kann Min-Therm 0 auf gar keinen Fall mit Min
-Therm 15 zusammenfassen, die unterscheiden sich in vier Variablen.
Min-Therm 0 mit Min-Therm 12 unterscheiden sich auch in zwei
Variablen.
Das heißt, diese Vergleiche sind gar nicht notwendig.
Das ist der Grund, warum man diese Min-Thermy nach Gewicht hier
sortiert.
Man sieht, wenn man das hier betrachtet, dass die Anzahl der
Vergleiche 0 mit 2 und 8 vergleichen muss.
2 und 8 mit allen in der Gewichtsklasse 2, also ich habe dann 8
Vergleiche.
Alle in der Gewichtsklasse 2 mit allen in der Gewichtsklasse 3,
nochmal 8 Vergleiche.
Und dann alle in der Gewichtsklasse 3 mit dem in der Gewichtsklasse 4.
Das heißt, insgesamt habe ich hier 20 Vergleiche, die ich durchführen
muss, damit ich hier mögliche Zusammenfassungen von Min-Thermen prüfen
kann.
Bei N Min-Thermen ist die maximale Anzahl von Vergleichen 0,5 mal N-1.
Machen wir das so, wir haben unsere Min-Thermen hier eingetragen und
wir wissen, wir fangen mit dem Min-Thermen mit dem geringsten Gewicht
und vergleichen den mit allen Min-Thermen in der nächsten
Gewichtsklasse.
Das heißt 0 und 2 und die tragen wir, wie wir wissen, aus Min-Thermen,
also aus Implikanten 0 der Ordnung entstehen Implikanten 1 der
Ordnung, tragen wir hier in dieser Tabelle, wobei wir hier statt die
Nummer, wir tragen dann die Nummer der Min-Thermen, aus denen jetzt
der neue Implikant 1 der Ordnung entstanden ist.
So, fangen wir mal an, 0 mit 2, da sieht man, die sind an der Stelle
hier komplementär belegt, das heißt die komplementär belegte Stelle
wird zu DontCare verfügt und es entsteht hier ein Implikant 0 der
Ordnung 00 DontCare 1, das ist die komplementär belegte Stelle.
0 und 8 sind an der letzten Stelle komplementär belegt, also es
entsteht hier DontCare 00.
Somit sind wir fertig mit der Vergleichung von Min-Thermen 0 mit den
Min -Thermen 2 und 8.
Jetzt geht es weiter hier, 2 mit allen in der Gewissklasse 2 und 8 mit
allen.
Jetzt gucken wir mal, 2 und 5, die sind, wie man sieht, hier an drei
Stellen komplementär belegt, also kann ich nicht zusammenfassen.
2 und 6 sieht man, dass sie nur an der dritten Stelle hier
komplementär belegt, das heißt die kann ich zusammenfassen, 2 und 6,
es entsteht hier 0 DontCare 1 0, also die komplementär belegte Stelle,
die wird ja zu DontCare.
Und man sieht hier, durch jetzt die Zusammenfassung von einem
Implikanten Gewicht 1 und Gewicht 2, da wir ja die komplementär
belegte Stelle wegstreichen sozusagen, entsteht ein Implikant mit dem
Gewicht 1.
Also hier, da haben wir nur ein 1 jetzt bekommen, deshalb entsteht
jetzt hier die Klasse von Implikanten in erster Ordnung mit Gewicht 1.
So, 2 mit 6, 2 mit 9 sehen wir, dass sie sich an mehreren Stellen
unterscheiden, an der ersten, an der zweiten, an der vierten, also
geht nicht.
2 und 12 geht auch nicht, weil die unterscheiden sich an drei Stellen.
Dann machen wir weiter mit 8.
8 und 5 geht nicht, weil die unterscheiden sich an drei Stellen.
8 und 6 geht auch nicht, weil sie unterscheiden sich an drei Stellen.
8 und 9 sieht man, sie unterscheiden sich an der Stelle hier, das
heißt sie kann ich zusammenfassen zu 1 0 0 DontCare.
Und 8 und 12 sieht man hier, die unterscheiden sich an der dritten
Stelle, das heißt es kommt hier 1 DontCare 0 und dann sind wir hier
fertig mit den Vergleichen.
Jetzt geht es weiter, 5 mit 7, also die hier mit 7 und mit 13.
5 mit 7, da sehen wir, die unterscheiden sich an der Stelle, also die
kann ich zusammenfassen.
5 und 13, die unterscheiden sich an der letzten Stelle, die kann ich
zusammenfassen.
6 und 7, die unterscheiden sich an der ersten Stelle, die kann ich
auch zusammenfassen.
6 und 13, ich kann ohne hinzugucken sofort sagen, die kann ich nicht
zusammenfassen.
Weiß jemand warum?
6 und 13, 41 und 46 kann ich nicht zusammenfassen.
Alle MinTerms, die ich zusammenfassen kann, das gefällt dir nicht
oder?
Du schüttelst den Kopf.
Alle MinTerms, die ich zusammenfassen kann mit dem gelben Pulli meine
ich.
Genau, dich ja.
Danke.
Alle MinTerms, die überhaupt Kandidaten für Zusammenfassung sind, die
müssen eigentlich von der Nummer her, die Differenz muss ein zweier
Potenz sein.
Das heißt, wenn ich sage hier, wo waren wir eigentlich?
5 und 13, haben wir jetzt 6 und 7, wo war ich jetzt?
6 und 7, jetzt 6 und 13.
Der Unterschied ist 7 zwischen den zwei MinTerms.
Die Differenz ist 7.
Das heißt, die kann man überhaupt nicht zusammenfassen.
Wenn die Differenz ein zweier Potenz ist, dann sind die MinTerms
Kandidaten für eine Zusammenfassung.
Das ist also ein notwendiger, aber nicht einreichender Bedienung für
die Zusammenfassung.
Das heißt, 6 und 13 kann ich nicht zusammenfassen, mache ich weiter.
9 und 7, die Differenz ist 2, also 9 und 7, die Differenz ist 2 für
die Zusammenfassung.
Aber man sieht hier, 9 und 7, die unterscheiden sich an mehreren
Stellen, kann ich nicht zusammenfassen.
9 und 13, Differenz 4a könnte sein und tatsächlich unterscheiden sie
sich an der Stelle, also 9 und 13.
12 und 7 brauche ich nicht zu betrachten, weil Differenz 5 und man
sieht hier, die unterscheiden sich an der Stelle hier, also somit bin
ich fertig.
Und die sind komplementär belegt an der Stelle, das heißt, die kann
ich zusammenfassen.
Und 13 und 15, Differenz 2, also mögliche Kandidaten und in der Tat
kann man sie zusammenfassen hier.
Somit sind wir fertig mit allen Vergleichen.
Und alle Minterme, die wir zusammengefasst haben, hacken wir ab jetzt
in der Tabelle, weil die sind keine Primterme der Funktion, aber wie
man gesehen hat, wir haben immer wieder mit diesen Mintermen mögliche
Zusammenfassungen gemacht.
Jetzt machen wir weiter hier mit dieser Tabelle und zwar müssen wir
wiederum Termi von benachbarten Gewissklassen schauen, ob wir sie
zusammenfassen können und wir tragen sie hier in einer neuen Tabelle,
das heißt, wir bilden aus Implikanten erster Ordnung Implikanten
zweiter Ordnung.
Und wie macht man das eigentlich?
Muss man auch alle möglichen Vergleiche hier machen, Zeile für Zeile
oder gibt es irgendwelche Restriktionen, auf die man achten muss?
Weiß es jemand?
So, diese Implikanten erster Ordnung, da fehlt immer eine Variable
drin.
Das müsst ihr so verstehen.
Hier fehlt die Variable b, hier fehlt die Variable d, hier fehlt die
Variable c, hier fehlt die Variable b, hier fehlt die Variable a.
Das heißt, damit ich zwei Termi überhaupt zusammenfassen kann, müssen
sie eine Dornenquer an der gleichen Stelle haben und müssen sie
weiterhin in einer Variable komplementär belegt sein.
Und wenn man das beachtet, dann spart man so viel Arbeit.
Das heißt, wenn ich jetzt zusammenfassen kann, dann gucke ich, welcher
von denen hier hat eine Dornenquer an der zweiten Stelle?
Keiner.
Also ich kann 0,2 mit keinem hier zusammenfassen.
Welcher von denen hat eine Dornenquer an der letzten Stelle?
Auch keiner.
Das heißt, ich kann hier keine Zusammenfassung zwischen denen machen.
Dann mache ich hier weiter.
Hier 2,6.
Der hat eine Dornenquer an der zweiten Stelle.
Also möglicher Kandidat ist 9 und 13, aber wir sehen, die sind an der
ersten und an der zweiten Stelle komplementär belegt.
Also an mehr als einer Stelle und sogar hier.
Also an drei Stellen sind sie komplementär belegt, deshalb kann ich
sie nicht zusammenfassen.
Dann mache ich hier weiter mit 9,8,9.
Ist an der Stelle hier komplementär belegt.
Könnte eventuell mit dem hier zusammengefasst werden, aber die sind an
drei Stellen komplementär belegt.
8,9 mit 12,13.
Da sieht man, dass sie hier tatsächlich an der dritten Stelle
komplementär belegt sind, sonst Dornenquer an der gleichen Stelle.
Also ich kann 8,9,12,13 zusammenfassen zu einem implikanten zweiter
Ordnung, der heißt 1,0 Dornenquer.
8,9,12,13.
Jetzt machen wir weiter mit dem hier.
Den hier können wir maximal zusammenfassen mit dem hier.
Und das ist tatsächlich der Fall, weil die unterscheiden sich an der
Stelle.
Also das ist 8,12,9,13.
Und wie man sieht, ist das der gleiche, den wir vorher gemacht haben.
Und das erkennt man auch, weil das sind die MINT-Thermie 8,9,12,13
oder 8,12,9,13.
Das ist das gleiche.
Also eigentlich diese MINT-Thermie, die man so bekommt, die gleich
sind, muss man ja hier nicht in die Tabelle aufnehmen.
So, jetzt sind wir hier fertig.
Jetzt gucken wir mal die mit denen.
Also mit 7,15 können wir eventuell den hier zusammenfassen und die
sind tatsächlich hier komplementär belegt.
Dann sonst nichts.
Und der hier können wir maximal mit 5,7 zusammenfassen.
In der Tat sind die an der Stelle hier komplementär belegt.
Und nochmal der gleiche Effekt.
Das heißt, das sind eigentlich identische Implikanten zweiter Ordnung.
Deshalb brauchen wir sie nicht zweimal aufzunehmen in der Tabelle.
Und wenn man das Ganze hier anguckt, dann sieht man, dass es keine
weiteren Zusammenfassungsmöglichkeiten gibt.
Das heißt, welche haben wir hier zusammengefasst?
Die haben wir hier zusammengefasst, deshalb sind sie keine Primthermie
der Funktion.
Der Rest, alles was stehen geblieben ist, sind Primthermie der
Funktion.
Das heißt 0 und 2, 0 und 8, 2 und 6, 6 und 7 und die Neuen, die wir
hier bekommen haben, 8, 9, 12, 13, das ist E, und 5, 7, 13, 15.
Das heißt, wir haben alle Primthermie der Funktion bestimmt und die
sind jetzt die Primthermie in der sogenannten Würfel-Kalkul
-Darstellung hier angegeben.
Das heißt, was wir machen müssen ist, zu diesen Primthermen, die wir
bestimmt haben, die entsprechenden Produktthermie zu generieren.
Und man sieht, dass bei der variablen Reihenfolge D, C, B, A, dass A
nichts anderes ist als D quer, C quer, A quer, B nichts anderes ist
als C quer, B quer, A quer, C, D quer, B, A quer, D ist D quer, C, B
und E ist nichts anderes als D, B quer und F ist nichts anderes als C,
A.
Also, wir haben jetzt den ersten Schritt der Minimierung erledigt.
Wir haben alle Primthermie der Funktion bestimmt.
Seine Frage war, vielen Dank für die Frage, seine Frage war, wie
erkenne ich jetzt, welche restlichen Thermie die Primthermie sind.
Die Primthermie sind solche Thermie, die wir überhaupt, also die an
Zusammenfassungen nicht mehr teilgenommen haben.
Ja, so, das heißt hier, wenn man einen Schritt weiter geht, dann würde
man versuchen, die hier mit denen hier zusammenzufassen, aber wie man
sieht, hier haben wir dort an der ersten und dritten Stelle und hier
an der zweiten und vierten, also können wir nicht mehr zusammenfassen.
Deshalb war das das Ende.
Das heißt, das sind die Primthermie höchste Ordnung, die wir hier
bekommen haben, E und F.
Und wenn man das Ganze hier betrachtet, 8 und 9 haben wir
zusammengefasst hier, 8 und 12 haben wir auch hier zusammengefasst, 5
und 7 haben wir hier zusammengefasst, 5 und 13 auch, 9 und 13 hier
haben wir verwendet, 12 und 13 haben wir auch oben verwendet.
Deshalb müssen wir sie abhaken von der Tabelle.
Das gleiche haben wir hier vorher gemacht, das heißt kein Minterm ist
Primimplikant und diese hier sind, also die Thermie hier, die
Implikanten erster Ordnung, die abgehakt sind, die sind auch keine
Primthermie.
Die restlichen sind dann die Primthermie der Funktion.
Ja, bitte.
Natürlich, natürlich.
Also seine Frage war, nochmal vielen Dank für diese Frage, weil viele
Leute unterschätzen das.
Ich meine, es geht nicht darum, dass man das auf Papier macht, sondern
vielleicht mal im Rechner implementiert.
Seine Frage war, und wenn man sowas im Rechner implementiert, dann
muss man natürlich alle diese Details, die er fragt, kennen.
Seine Frage ist, könnte es sein, dass in der ersten Tabelle hier einer
der Minthermie Primimplikant der Funktion ist, oder?
Und natürlich, also wenn ich einen Minterm habe, den ich mit keinem
anderen zusammenfassen kann, dann ist er auch Primtherm der Funktion.
1, 2, 3, 6 Stück und der nächste Schritt der Minimierung ist zu
gucken, welche dieser Primthermie sind notwendig, um alle
Einstellungen der Funktion zu bestimmen.
Das heißt, wir müssen das sogenannte Überdeckungsproblem lösen.
Im KV-Diagramm konnten wir das sehen, durch scharfes Hinschauen.
Hier wissen wir nicht, welche sind Primthermie.
Kann jemand von euch das sagen?
Also ich bin ein bisschen erfahren, ich kann es euch sagen, zum
Beispiel.
Jetzt, wenn wir hier mal gucken,
zum Beispiel hier, diese 5, die wird von keinem anderen hier
überdeckt, weder von A, noch von B, noch von C, noch von D.
Also Mintherm 5, deshalb F ist ein Kernprimimplikant und so weiter und
so fort.
Aber das ist zu kompliziert an der Stelle.
Dazu haben wir die zweite Quantsch-Tabelle kennengelernt, mit der wir
das systematisch machen können.
So, das heißt, wir müssen die sogenannte Überdeckungstabelle
aufstellen.
Das sind die Primimplikanten, die wir bekommen haben.
A bis F, das sind die Minthermie der Funktion 0 bis 15 und wir tragen
überall dort, wo ein Mintherm von einem Primimplikant überdeckt wird,
haben wir ein Kreuz.
Und woher bekommen wir die Information?
Naja, aus der Tabelle, aus dieser Tabelle.
A überdeckt die Minthermie 0 und 2, B 0 und 8, C 2 und 6, D 6 und 7, E
überdeckt 8, 9, 12, 13 und F überdeckt 5, 7, 13, 15.
Das habe ich hier nur in der Tabelle eingetragen.
Also hier 4 Stück durch E, 4 Stück durch F, 0 und 2 durch A, 0 und 8
durch A und so weiter und so fort.
So, wie bearbeiten wir jetzt die Überdeckungstabelle?
Wir suchen zunächst mal die Kernprimimplikanten.
Das sind solche in der Tabelle, die für nur ein Kreuz in einer Spalte
verantwortlich sind.
Und welche sind das?
Wenn wir gucken, wir sehen hier in der Spalte 5 haben wir nur ein
Kreuz.
Hier haben wir zwei Kreuze, hier haben wir zwei Kreuze, hier haben wir
zwei, hier zwei.
9, 12 haben wir jeweils nur eins.
Das heißt eigentlich E ist ein Kernprimimplikant, hier in der 5.
F ist ein Kernprimimplikant.
Das ist natürlich klar, weil der Minterm 5, wie ich vorher gesagt
habe, wird nur durch F belegt.
Was machen wir damit?
Um die zu bearbeiten, suchen wir zunächst mal die Kernprimimplikanten
und streichen alle von ihnen überdeckten Minterme.
Und dann nutzen wir Regeln der Dominanz, Spalten- und Zahlendominanz,
um die resultierende, reduzierte Tabelle zu vereinfachen.
Und dann werten wir die reduzierte Tabelle aus.
Das werden wir gleich sehen.
Das heißt, wir haben hier unsere Tabelle.
Was sind die Kernprimimplikanten?
Das ist F, wir streichen alle davon überdeckten Minterme.
Wir sehen, wenn wir F haben, dann haben wir vier Minterme überdeckt.
Und E war auch ein Kernprimimplikant und dann streichen wir alle diese
Minterme.
Das heißt, wie man sieht hier, mit den zwei Kernprimimplikanten hier,
habe ich die Minterme 5, 7, 8, 9, 12, 13, 15 überdeckt.
Um alle Minterme der Funktion zu überdecken, das heißt die restlichen,
sind dann die Minterme 0, 2 und 6.
Und da muss ich jetzt aus den Primimplikanten A, B, C und D eine
Auswahl treffen, um diese restlichen drei Minterme zu überdecken.
Und das sieht man mit bloßem Auge hier an dieser Tabelle.
Also um diese restlichen drei Minterme zu überdecken, kann ich
entweder A und C nehmen oder A und D nehmen oder ich kann C und B
nehmen.
Das ist klar, ich muss die drei Minterme treffen.
Hat es jeder verstanden?
Das kommt nachher jetzt natürlich erklärt, aber die Lösung sieht man
mit bloßem Auge jetzt.
Ich habe drei Minterme 0, 2 und 6 und ich habe vier Primimplikanten.
Wenn ich A nehme, dann habe ich 0 und 2 überdeckt.
Ich muss also nur noch 6 überdecken.
Das kann ich nehmen, indem ich C nehme, also A und C oder A und D.
Beziehungsweise ich kann B und C nehmen und dann habe ich alle drei
überdeckt.
Und das kommt als Ergebnis raus jetzt nachher bei uns.
Das heißt, diese reduzierte Tabelle hat nur die Minterme 0, 2 und 6
und die vier Primimplikanten A bis D.
Und die können wir natürlich versuchen nochmal zu reduzieren mithilfe
von Regeln der Spalten- und Zeilendominanz.
Was bedeutet Spaltendominanz?
Das bedeutet, Spalten, die andere überdecken, können wir wegstreichen.
So, hier ein Beispiel.
Das heißt, die Spalte hier, die überdeckt die hier, deshalb können wir
sie wegstreichen.
Und die Spalte hier, L, überdeckt die hier, deshalb können wir sie
auch wegstreichen.
Das ist ein bisschen versetzt, die Zeichnung, aber ich glaube, das ist
klar, was gemeint ist.
Zeilendominanz, Zeilen mit nur Einträgen, die eine andere Zeile hat,
können auch gestrichen werden, falls sie nicht billiger sind.
So, das heißt hier, die Zeile A hat nur Einträge, die die Zeile B hat,
deshalb können sie gestrichen werden, wenn sie nicht billiger ist.
Und die Zeile C hat auch nur Einträge, die die Zeile B hat und deshalb
können sie auch gestrichen werden, wenn sie nicht billiger ist.
So, die Zeile E genauso.
Also das ist jetzt hier ein allgemeines Beispiel und nicht die
Aufgabe.
Man sieht hier, die Mintermien sind mit J, I, J, K, L, M, N
gekennzeichnet und nicht unsere Mintermien in dem Beispiel.
So, jetzt gehen wir mal zurück zu unserem Beispiel und gucken wir mal,
ob wir solche Sachen haben.
Kann man natürlich machen, aber wir wissen, dass wir für diese
reduzierte Tabelle, die ziemlich klein ist, natürlich kann ich jetzt
mit Zeilendominanz B streichen oder D streichen, aber wir wollen das
mithilfe von dieser Überdeckungsfunktion machen.
Das heißt, wir stellen die Überdeckungsfunktion auf.
Die Überdeckungsfunktion wird so aufgestellt, dass man sagt, welche
Möglichkeiten habe ich, um Minterm Null zu überdecken.
Und Minterm Null kann ich überdecken mit A oder B.
Das heißt, wir haben für jeden Prim Implikanten eine Variable Omega
oder WA und WB.
Und man sieht hier, Minterm Null kann überdeckt werden mit A oder B.
Minterm Zwei kann überdeckt werden mit A oder C.
Und Minterm Sechs kann überdeckt werden mit C oder D.
Das ist jetzt eine konjunktive Form dieser Überdeckungsfunktion.
Wir multiplizieren alles aus, ein paar mal Absorptionsgesetz anwenden
und dann kommen wir auf eine Überdeckungsfunktion, die heißt WAWC oder
WAWD oder WBWC.
Das bedeutet, um diese drei Minterm mit diesen vier Prim Implikanten
zu überdecken, nehme ich entweder A und C oder A und D oder B und C.
Das ist, was ich vorher gesagt habe.
Das heißt, die disjunktive Minimalform der Funktionen ist zunächst mal
A und F, die wir zunächst mal bestimmt haben,
oder diese Varianten hier.
Das heißt, insgesamt haben wir drei unterschiedliche DMFs hier, also
drei disjunktive Minimalformen der Funktionen.
Und zwar die erste ist E oder F oder A, C, A, D, bzw.
B, C.
Und ich habe hier für B, wie man sieht, das ist C-quer, B-quer, A
-quer, bzw.
für C ist es D-quer, B, A-quer.
Um jetzt die Minimalform hier angeben zu können, brauchen wir
natürlich konkrete Angaben zu Kostenfunktionen, Realisierungskosten
der einzelnen Minitermien.
Ohne diese Kostenfunktion können wir an der Stelle nicht sagen, welche
der drei disjunktiven Minimalformen hier die billigste ist.
So viel dazu.
Gibt es Fragen?
Gut, jetzt wollen wir mal mit Hilfe von dem gleichen Verfahren, mit
dem Koin-McCluskey-Verfahren, die konjunktive Minimalform einer
Funktion bestimmen.
Um ein bisschen weniger Schreibarbeit hier zu haben und damit wir die
Zeit nutzen, will ich unsere Funktion nehmen, also die Funktion, die
wir gerade minimiert haben mit Koin-McCluskey.
Ich will jetzt die Negation dieser Funktion nehmen.
Das heißt, diese Funktion wird dann an den Stellen hier ein 0 haben,
statt eine 1.
Und ich will die konjunktive Minimalform für die Funktion f²
bestimmen, nur damit wir Arbeit sparen.
Also ihr könnt euch vorstellen, dass eine Funktion g, das ist die
Funktion g, und g ist gleich f² und wir wollen die konjunktive
Minimalform dieser Funktion bestimmen.
Die Vorgehensweise ist die gleiche wie vorher.
Wir ordnen die Maxthermien nach Gewicht und so weiter und so fort,
machen die Vergleiche.
Am Ende bekommen wir Thermien, die wir nicht weiter zusammenfassen
können und das sind unsere Primimplikate.
Das heißt, genau wie vorher bei der Bestimmung der Primimplikanten,
würden wir auch hier solche Primimplikate bekommen.
Der wird a sein und der wird heißen d oder c oder a.
Der zweite wird b sein und der wird heißen c oder b oder a.
Und der dritte c wird heißen d oder b² oder a².
Und d, also Primimplikat d, wird dann d oder c² oder b² heißen.
Und e wird auch ein Kernprimimplikat sein, das ist d² oder b.
Und f wird auch ein Kernprimimplikat sein, das ist c² oder a².
Das heißt, die Vorgehensweise ist die gleiche.
Die Tabelle von vorher, die gleichen Zusammenfassungen, weil ich ja
die gleichen Maxthermien genommen habe, die gleichen Nummern.
Und am Ende, wenn ich jetzt hier diese Summenthermie bilde, wie man
sieht hier, für a werde ich nicht d², c² oder a², sondern d oder c
oder a und hier und so weiter und so fort.
Der nächste Schritt ist natürlich, Überdeckungsfunktionen
aufzustellen.
Die Gleichungen werden gleich sein, aber für die Primimplikate, nicht
für die Primimplikanten.
Das heißt, ich komme am Ende zu einer Überdeckungsfunktion, die
genauso aussieht und wir haben für die disjunktive Minimalform dies
hier bekommen.
Also für die konjunktive Minimalform werden wir folgende Lösung
bekommen.
Also konjunktive Minimalform f² von d, c, b, a ist gleich d² oder b
und c² oder a².
Also die sind Kernprimimplikanten.
Und d oder c oder a, d oder b² oder a und hier d oder c oder a, d oder
c² oder b² und c oder b oder a und d oder b² oder a.
Also insgesamt auch drei konjunktive Minimalformen der Funktion.
Okay, ganz schnell erledigt.
Das heißt, wenn ihr wollt, es macht keinen Sinn, die Aufgabe zu lösen.
Das sind die gleichen Nummern der Maxthermie wie die Minthermie vorher
in der Aufgabe und deshalb wird hier die Lösung kommen.
So, nächste Aufgabe.
Wir wollen gucken, wie wir eigentlich unvollständig definierte
Funktionen auch mithilfe von Quine McCluskey minimieren können.
Weil die meisten Funktionen, die man oder viele Funktionen, die man
hat, auch mit vielen Eingangsvariablen, die im Rechner mithilfe von
tabellarischen Verfahren minimiert werden, die könnten auch oder sind
unvollständig definiert.
Und gegeben sei eine Funktion f von fünf Eingangsvariablen, die hat
die Minthermie 12, 13 bis 30 und hat zwei Don't Cares an der Stelle 17
und 18.
Wir wollen alle Primimplikanten der Funktion mithilfe von Quine
McCluskey bestimmen und wir wollen eine disjunktive Minimalform
eingeben.
Also, falls es mehrere gibt, eine reicht.
Wie geht man vor?
Quine McCluskey, disjunktive Minimalform, wir haben zwei Don't Cares.
Wir wissen, wenn wir zwei Don't Cares haben, müssen wir so verfügen im
KV -Diagramm zu 0 oder 1, dass wir möglichst größere Zusammenfassungen
oder Blöcke bilden.
Aber das ist ein tabellarisches Verfahren, deshalb wissen wir
eigentlich nicht, wo wir eine 0 oder wo wir eine 1, also welche Don't
Care -Stelle zu 0 und welche zu 1 verfügen.
Wir wollen aber die DMF bilden, deshalb verfügen wir beide zu 1.
Das heißt, beide betrachten wir als Minthermie und die nehmen wir auf
hier, wie man sieht, die 17 und 18, die sind jetzt Minthermie der
Gewißklasse 2.
Wir haben keine Minthermie der Gewißklasse 0 und 1.
Das sind unsere Implikanten in erster Ordnung und jetzt machen wir
unsere Zusammenfassungen.
Wenn wir diese Zusammenfassungen angucken, dann sehen wir, dass die
Minthermie 12, 13, 14, 15, 29 und 30 hier teilgenommen haben an
Zusammenfassungen, deshalb können wir sie wegstreichen.
Machen wir weiter mit der Tabelle hier, dann sehen wir, dass diese
zwei eigentlich Primimplikanten der Funktion sind.
Wir haben sie hier nicht zusammengefasst, deshalb sind sie
Primimplikanten der Funktion.
Aber nicht zu vergessen, das waren unsere Don't Care-Stellen, die 17
und 18.
Jetzt machen wir weiter, fassen wir zusammen, dann bekommen wir hier
Implikanten zweiter Ordnung und gucken,
das ist doppelt, streichen wir, die restlichen sind A, B und C.
Das sind die Primimplikanten der Funktion.
Und zwei, die wir gar nicht zusammengefasst haben, sind eigentlich 17
und 18.
Also 17 und 18 sollten wir eigentlich auch jetzt hier als
Primimplikanten betrachten, aber wir wissen, dass das die Don't Care
-Stellen sind.
Und separat dürfen wir sie nicht in die Minimum-Primimplikanten, die
A, B und C.
Da können wir hier die Produktthermie bilden.
Alle Primimplikanten sind Kernprimimplikanten, wie man sieht, weil
hier zum Beispiel die 15 nur durch A überdeckt wird und hier die 29
nur durch C überdeckt und die 30 nur durch B.
Die Freistellen wurden mit keinem Miniterm zusammengefasst, wir dürfen
sie also nicht in die Minimalform aufnehmen.
Das heißt, die disjunktive Minimalform ist nichts anderes als die
Disjunktion dieser Primimplikanten von A, B und C.
Um das Ganze ein bisschen zu veranschaulichen, wollen wir mal die
Situation im KV-Diagramm angucken.
Das sind die Minitermien der Funktion und das sind die Don't Cares, 17
und 18.
Und was wir bekommen haben, wir haben A bekommen, B und C.
Das waren die Primimplikanten, die wir bekommen haben und die zwei da
oben, die Don't Care Stellen, die haben wir mit keinem anderen
Miniterm zusammengefasst.
Deshalb sind sie eigentlich hier, kommen sie oder tauchen sie in der
Minimalform nicht auf oder dürfen sie in der Minimalform nicht
auftauchen.
Okay, gibt es Fragen hierzu?
Das heißt, wenn wir unvollständig definierte Funktionen, wir wollen
die disjunktive Minimalform bestimmen, dann müssen wir die Don't Care
Stellen zu Einzelnen verfügen, die Vergleiche durchführen und am Ende
nur prüfen, ob wir einen Primimplikanten bekommen haben, der nur aus
Don't Cares besteht, den dürfen wir in die Minimalform dann nicht
aufnehmen.
Okay, nächste Aufgabe.
Dieses Überdeckungsproblem, was wir vorher gesehen haben oder was wir
lösen müssen, ist nicht jetzt ein Problem, was jetzt speziell für die
technische Informatik da ist, sondern das ist ein generelles
Optimierungsproblem, wo man eine Menge M hat und eine Menge S von
Teilmengen von M, also M1 bis Mn.
Man hat eine Kostenfunktion, die jeder Teilmenge Mi von S die Kosten
Ki zuordnet.
Und das Problem ist immer, dass man eine Teilmenge T von S bestimmt,
sodass die Vereinigung aller Mi aus T die Menge M ergibt, das heißt
die Menge M vollständig überdeckt wird, alle Nullstellen bzw.
Einstellen der Funktion und die gesamten Realisierungskosten minimal
sind.
So, nochmal zurück zu Überdeckungsproblemen oder ein Beispiel, wie die
Überdeckungstabelle zusammenspielt mit dem KV-Diagramm und warum wir z
.B.
Kernprim -Implikanten solche sind, die nur für ein Kreuz in einer
Spalte verantwortlich sind, will ich kurz anhand von einem Beispiel
hier zeigen.
Das heißt, wenn wir jetzt dieses KV-Diagramm mit den eingetragenen
Einsen hier angucken, dann sehen wir, das sind die Mindtermine 0 bis
15 hier.
Beispielsweise ist das hier eine mögliche Zusammenfassung von Einsen
und das spiegelt sich in der Überdeckungsstabelle wie folgt, das
heißt, wenn ich das hier weiß, dann muss ich hier Kreuz bei 0, 1, 4
und 5 eintragen.
Dann 1, 5 und 9 und 13, dann muss ich hier bei 1, 5, 9 und 13 etwas
eintragen.
Für den Nächsten muss ich dann markieren, welche Mindtermine überdeckt
jetzt D und A bzw.
welche Mindtermine überdeckt D, C, B, das sind die Mindtermine 4 und 5
und welche Mindtermine überdeckt C, B, A quer, das sind 6 und 14 und
welche Mindtermine überdeckt D quer, C, A quer, also das sind die
Mindtermine 4 und 6.
Das ist eigentlich die Überdeckungsstabelle, die zu diesem KV-Diagramm
gehört.
Und jetzt versuchen wir, eine redundante Überdeckung zu finden.
Wir sehen hier, dass der erste hier ein Kernprim implikant ist, weil
der hat nur ein X oder ein Kreuz in dieser Spalte, in der 0.
Spalte.
Das heißt, im KV-Diagramm sieht man das auch, dass diese Mindtermine 0
nur durch D quer, B quer überdeckt wird.
Und wenn wir den hier aufnehmen in die Minimalform, dann wissen wir,
das gleiche gilt zunächst mal für 11.
Man sieht hier, diese 11 wird nur durch diesen Primimplikanten, also
D, A überdeckt, deshalb ist es ein Kernprimimplikant.
Wenn man die hier aufnehmen muss, dann bedeutet das, wir haben die
hier weggestrichen, weil 1, 4 und 5 schon durch diesen Term bereits
überdeckt werden.
Und wenn ich den hier aufnehme, dann sind 9, 13 und 15 auch überdeckt.
Das heißt, deshalb streichen wir die hier oder markieren wir sie mit
5.
Und was übrig bleibt, erkennt man auch hier im KV-Diagramm, sind die
Mindtermine 6 und 14.
6 und 14 und um 6 und 14 zu überdecken, habe ich 1, 2, 3, 4
Möglichkeiten oder 4 Primtermine.
Und das sehen wir, 6 und 14, wenn ich die überdecken will, dann
brauche ich eigentlich...
Entschuldigung, die Zeile ist verschoben.
Aber man sieht, dass jetzt hier für 6 und 14 eigentlich ein einziger
Primterm notwendig ist, um das zu überdecken.
Ja, die Zeile ist verschoben, also Spaltendominanz.
Hier haben wir keine, aber die Zeilen sind hier verschoben in dem
Beispiel.
Das Zweite, was man hier betrachten kann, ist Zeilendominanz.
Zeilendominanz, das bedeutet, die Zeile und die Zeile kann man
wegstreichen.
Also die Mindtermine 6 und 14 kann man mit dem Primimplikanten CB aqua
hier überdecken.
Das heißt, alle Zeilen sind verschoben.
Entschuldigung, muss ich mal korrigieren.
Aber das heißt, 6 und 14 werden mit Hilfe von dem hier, das ist nichts
anderes als C aqua B überdeckt.
Gut.
Okay, das nächste tabellarische Verfahren, das wir kennengelernt
haben, war das Konsensusverfahren, was wir das letzte Mal
kennengelernt haben.
Und die Grundidee ist hier, dass man diese Konsensusregel nutzt.
Kann jemand von euch diese Regel hier beweisen?
Ich halte sie für algebraisch.
Aber das wurde ja letzte Woche besprochen, oder?
Kann sich jemand von euch daran erinnern?
Du kannst dich daran erinnern?
Kannst du es beweisen?
Nein?
Interessiert euch das, dass wir das beweisen, oder gar nicht?
Es ist euch egal, oder wie?
Sollen wir, oder nicht?
Okay.
Ja, wie geht man vor?
Stellt euch mal vor, das ist eine Aufgabe in der Klausur, ihr sollt
das beweisen.
Nächste Aufgabe, oder?
Okay.
Dabei ist es so einfach eigentlich.
Und es wäre schade, wenn man...
Also immer eigentlich, warum ich diese Sache hier bringe, immer wenn
es nicht geht, dann gibt es ein Gesetz, das soll euer Lieblingsgesetz
werden.
Ist zumindest mein Lieblingsgesetz, das Absorptionsgesetz.
Immer wenn man nicht weiterkommt, dann denkt mal bitte an das
Absorptionsgesetz.
Na ja, wie komme ich jetzt von der Seite, von der x u oder x quer w,
auf die andere Seite?
Ja, ich kann vielleicht folgendes probieren.
Was kann ich für x schreiben eigentlich?
Für x kann ich schreiben, das ist x und x oder w, oder?
Und für x quer kann ich schreiben, das ist x quer, x quer oder u.
Ja, das ist Absorptionsgesetz.
Ja, jetzt machen wir nur Einsätzen eigentlich.
Einsätzen.
x u oder x quer w ist gleich.
Für x setze ich x und x oder w mal u.
Oder für x quer setze ich x quer, x quer oder u mal w.
Soll ich weitermachen?
Okay, anscheinend ja.
Das ist also x x u oder x w u oder x quer x quer w oder x quer u w.
Das ist also x u oder x quer w.
Ja, weil wir wissen ja, das ist x x, das ist also x u.
Das ist hier x quer w.
Und die restlichen Termine sehen wir, dass wir, oder?
Ich hasse das.
Oder ich kann u w ausklammern, x oder x quer.
Und wir wissen, dass es gleich eins ist.
Also, x u oder x quer w.
Mein Gott, ich merke, dass es spannend für euch ist, wenn ihr so ruhig
seid.
Das ist echt gut.
Also muss man nur Beweise mal bringen hier und dann seid ihr ruhig.
Okay, so, aber das haben wir bewiesen.
Das sieht man hier nochmal schwarz auf weiß.
Aber das ist nicht die Sache.
Wir wollen gucken, wie wir das hier nutzen, diese Regel, um Bullshit
-Funktionen zu minimieren.
Ausgangspunkt ist eine beliebige Überdeckung der Funktion.
Zum Beispiel diese Würfelüberdeckung.
Wir haben eine Funktion von fünf Eingangsvariablen.
Das ist eine Anfangsüberdeckung der 1-Stellen, gegeben durch sechs
Würfel, wie man hier sieht.
Und wir suchen alle Primimplikanten der Funktion und die disjunktive
Minimalform der Funktion.
Wie geht das?
Nochmal eine Tabelle, weil das ein tabellarisches Verfahren ist.
Das sind unsere Würfel.
Wir nummerieren sie.
Und dann haben wir zwei weitere Spalten, in denen wir zunächst mal für
neue Würfel, also wir müssen jetzt versuchen, Konsensuswürfel der
Anfangsüberdeckung zu bilden.
Also aus der Anfangsüberdeckung müssen wir durch Vergleiche oder
Zusammenfassungen aller Würfel durchschöpfen, die sozusagen
Konsensusbildung hier diese Vergleiche durchführen.
Und dann schreiben wir in dieser Spalte hier, aus welchen dieser
Würfel hier neue Würfel entstehen.
Und wenn wir irgendeinen Würfel wegstreichen, weil er bereits
vorhanden ist oder überdeckt wird durch einen Würfel, der in der
Überdeckung durch einen vorhandenen Würfel überdeckt ist, dann müssen
wir streichen.
Und deshalb geben wir hier an, aus welchem Grund dieser neue Würfel
zum Beispiel gestrichen wurde.
So, und wie geht man vor?
Man fängt mit Nummer zwei und man vergleicht den mit allen
übereinliegenden Würfeln, um nur systematisch an die Sache
heranzugehen.
Und bei dem Kwan-McCluskey-Verfahren, was ja der Spezialfall, wie wir
gesehen haben, oder wie wir wissen aus der Vorlesung, aus dem
Spezialfall des Konsensusverfahrens, haben wir nach zwei Stellen
gesucht in den MINT-Thermen, die an einer Stelle komplementär belegt
sind.
Hier müssen wir einen Konsensuswürfel bilden.
Und wann existiert ein Konsensuswürfel zwischen zwei Würfeln?
Oder wie ist ein Konsensuswürfel definiert?
Das ist der großmögliche Würfel, der weder in C1 noch in C2, aber in
der Vereinigung dieser Würfel enthalten ist.
Und wie bilden wir den?
Wir suchen zwei Würfel, die an einer Stelle komplementär belegt sind.
Diese komplementär belegte Stelle verfügen wir zu DontCare.
Und sonst bilden wir den Durchschnitt der zwei Würfel, wie wir das
definiert haben.
Das heißt, zwei und eins, wir sehen, die sind an keiner Stelle
komplementär belegt.
Da existiert kein Konsensuswürfel.
Machen wir mit dem nächsten, drei und eins.
Da sehen wir, die sind an der Stelle hier komplementär belegt.
Diese Stelle wird dann zu DontCare verfügt.
Und dann bilden wir einen Durchschnitt zwischen den zwei Würfeln, drei
und eins.
Die Stelle hier wird DontCare.
Dann bekommen wir DontCare.
Vielleicht soll ich das markieren, nur am Anfang, damit die Leute
verstehen, wie das funktioniert.
Also diese zwei Stellen sind komplementär belegt.
Deshalb verfügen wir das zu einem DontCare.
Und dann bilden wir einen Durchschnitt zwischen allen weiteren.
Das heißt, wir bekommen hier einen neuen Würfel.
Der heißt DontCare, DontCare, DontCare 00.
Der nächste Schritt ist, wir prüfen, ob dieser neue Würfel in einem
vorhandenen Würfel enthalten ist.
Wenn das der Fall ist, dann bekommt er keine neue Nummer hier.
Und man sieht hier, der ist nicht in dem hier enthalten, ist eher
umgekehrt.
Der ist auch hier nicht enthalten.
Der ist hier auch nicht enthalten.
Das heißt, er bekommt eine Nummer.
Das ist die Nummer 7.
Und da sehen wir zum Beispiel, dass Nummer 1
auch im neu entstandenen Würfel enthalten ist.
Deshalb wird auch Nummer 3 hier weggestrichen.
Und das ist ein Unterschied zum Koin-McCluskey-Verfahren.
Das heißt, diese zwei Würfel, die wir weggestrichen haben, die nehmen
nicht weiter teil an Vergleichen.
Das heißt, somit wird diese Liste der Vergleiche kürzer.
Das heißt, wir machen jetzt weiter.
Wir hätten mit 3 weitermachen sollen, aber 3 ist jetzt nicht mehr da.
Deshalb machen wir jetzt weiter mit 4.
4 und 2, die sind nicht an einer Stelle komplementär belegt.
Also es gibt keinen Konsensuswürfel.
4 und 1, 1 ist schon weg.
Also müssen wir nicht vergleichen.
Nur 4 und 2, also geht nicht.
Der nächste 5.
5 mit 4, die sind an zwei Stellen komplementär belegt.
Also kein Konsensuswürfel.
Es existiert kein Konsensuswürfel.
Und 5 mit 2 sind an zwei Stellen auch komplementär belegt.
Das heißt auch kein Konsensuswürfel.
Machen wir dann weiter mit 6.
6 und 5 sind, wie man sieht, an der mittleren Stelle komplementär
belegt.
Die will ich nochmal hier markieren.
Das heißt, die wird zu Don't Care.
Und dann bilden wir über alle anderen Stellen den Durchschnitt.
Und wir wissen, Durchschnitt 1, 1 ist 1.
1, Don't Care ist 1.
Don't Care, 1 ist 1.
Und 1, Don't Care ist auch 1.
Also, wir bekommen einen Würfel, der heißt 1, 1, Don't Care, 1, 1.
Jetzt prüfen wir, ob dieser neue Würfel in irgendeinem der Würfel hier
enthalten ist.
Wir sehen hier, an keiner Stelle gibt es ein Don't Care an der
mittleren Stelle.
Also ist in keinem enthalten.
Deshalb bekommt er eine neue Nummer in der Tabelle, die Nummer 8.
Jetzt prüfen wir, ob einer der vorhandenen, noch nicht weggestrichenen
Würfel im neuen enthalten ist.
Und dann sehen wir, gibt es einen, der in dem enthalten ist?
Der nicht, der nicht.
Ja, gibt nicht.
Deshalb machen wir weiter und zwar mit dem nächsten Vergleich.
Der nächste Vergleich ist 6.
6 mit 4, wie man sieht.
Die 6 mit 4 sind hier an der Stelle komplementär belegt.
Das heißt, wir bekommen hier den Würfel Don't Care 1, 0, Don't Care 1.
Ist dieser Würfel irgendwo enthalten?
Das ist nicht hier enthalten, weil hier haben wir eine 0, hier eine 1.
Der ist eher größer als der hier.
Und der ist auch nicht hier enthalten, weil aus dem gleichen Grund.
Hier haben wir 0, 1, hier haben wir 1.
Das heißt, er bekommt eine Nummer 9.
Und jetzt prüfen wir, ob einer der vorhandenen Würfel in 9 enthalten
ist.
Und dann sehen wir gleich, dass 9 und 6 eigentlich in 9 enthalten
sind.
Äh, 4 und 6 in dem enthalten ist, deshalb streichen wir sie.
Also, wir haben jetzt 6 hier mit dem hier.
6 mit 4 verglichen.
6 haben wir jetzt weggestrichen, deshalb brauchen wir nichts mehr mit
2 zu vergleichen.
Und sind zunächst mal mit dem Vergleich hier weiter.
Wir machen weiter mit dem Nächsten.
Und der Nächste ist die Nummer 7.
Nummer 7 mit dem drüberliegenden, noch nicht gestrichenen Würfel, das
ist 5.
Also, 5 und 7, die sind hier an der Stelle komplementär belegt.
Wir fassen sie zusammen.
Die Stelle wird zu Don't Care und der Rest ist dann Durchschnitt, wie
man hier sieht.
Dann kommt sowas hier raus.
Ist das in einem der vorhandenen Würfel enthalten?
Das ist nicht der Fall.
Dann kommt die Nummer 10.
Jetzt prüfen wir, ist irgendeiner von denen, die vorhanden ist, in 10
enthalten.
Das ist, Entschuldigung, in 10 enthalten.
Dann müssen wir eigentlich nach Würfeln suchen, die an der 2.
und 4.
Stelle ein Don't Care haben.
Und das haben wir nicht.
Also gibt es keine weiteren Streichungen.
So, 7 und 2 sind nicht an einer Stelle komplementär belegt.
Deshalb machen wir weiter mit 8 und 7.
8 und 7 sind an zwei Stellen komplementär belegt.
8 und 5 sind an keiner Stelle komplementär belegt.
8 und 2 sind aber an der Stelle komplementär belegt.
Die können wir jetzt zusammenfassen.
Und wir gucken hier, der hier, was ist das eigentlich?
Das ist 1, 1, 0, Don't Care, 1.
Ist der in einem hier enthalten?
Ja, der ist in dem hier enthalten, in 9.
Weil hier haben wir ein Don't Care, hier nur eine 1.
Deshalb kriegt er keine Nummer.
Das heißt, der wird weggestrichen.
Er bekommt keine Nummer hier in der Tabelle.
Und dann machen wir weiter mit 8 und 2.
Jetzt der nächste ist 9.
9 und 8 gibt es keine Zusammenfassung.
Aber 9 und 7, die sind hier komplementär belegt.
Dann bekommen wir den hier.
Ist der irgendwo enthalten?
Aha, das sind solche Würfel, die an der ersten und letzten Stelle
Don't Care haben.
Zum Beispiel 2, hier haben wir Don't Care, hier haben wir 1.
Also der ist enthalten in 2, bekommt auch keine Nummer.
So, dann machen wir weiter.
9 mit 7 haben wir verglichen.
Jetzt 9 mit 5.
9 mit 5 sind hier komplementär belegt.
Dann bekommen wir den hier.
Und der ist eigentlich identisch mit 8.
Deshalb bekommt er auch keine Nummer.
Wir müssen versuchen, die Tabelle so kurz wie möglich zu halten.
Er bekommt keine Nummer.
Das letzte war 9 mit 5.
Jetzt 9 mit 2 gibt es keinen Konsensuswürfel.
Somit sind wir hier fertig.
Und jetzt geht es weiter mit 10.
10 mit 9 sind an 2 Stellen komplementär belegt.
10 mit 8 nur an einer Stelle komplementär belegt.
Aha, dann bekommen wir den hier.
Und der hier, müssen wir entscheiden, ob er eine Nummer bekommen soll
oder nicht.
Ist er irgendwo enthalten?
Ah, wo ist er enthalten?
Ah, der ist hier enthalten.
Weil der hat dann Don't Care hier und hier Don't Care, aber hier 1.
Also der ist enthalten in 5, deshalb bekommt er keine Nummer.
Also dann 10 mit 8 haben wir.
10 mit 7 gibt es keine komplementär belegte Stelle.
10 mit 2 können wir nochmal zusammenfassen, weil das eine komplementär
belegte Stelle ist.
Und wir bekommen sowas, aber wenn man scharf hinguckt, dann sieht man,
dass sowas eigentlich in 7 enthalten ist.
Weil 7 hat hier einen Don't Care und hier haben wir eine 1, also
bekommt er keine Nummer.
Deshalb wird er weggestrichen und somit müssen wir keine weiteren
Vergleiche machen.
Alle Würfel, die noch hier stehen sind, in der Tabelle, die sind dann
die Prim Termi, die Prim Implikanten der Funktion.
Und die können wir ablesen.
Das ist hier nichts anderes als C-Quer, B-Quer.
Das ist nichts anderes als E, C, B.
Das ist B-Quer, A-Quer und so weiter und so fort.
Das heißt, wir haben hier 6 Prim Implikanten der Funktion bestimmt.
Das war der erste Satz, um die Disjunktive Minimalform der Funktion zu
bestimmen.
Wie machen wir das?
Mit der Überdeckungs-Tabelle.
Aber bei der Überdeckungs-Tabelle haben wir zunächst einmal die Prim
Implikanten und haben hier die Min Termi.
Aber wo sind unsere Min Termi, die Funktion hat?
Das heißt, damit wir die Überdeckungs-Tabelle aufstellen können,
müssen wir die Frage beantworten, welche Min Termi überdeckt der Prim
Implikant C-Quer, B-Quer.
Weiß jemand von euch, welche Min Termi dieser Prim Implikant
überdeckt?
Oder wie man das findet?
Also bei diesen Prim Implikanten haben wir drei Variablen
weggestrichen.
A, D und E.
Die sind nicht da.
Und wir wissen, dass bei allen Min Termen, die der Term C-Quer, B-Quer
überdeckt, C und B Null sind.
Die Belegung.
Das heißt eigentlich, dieser Würfel hier, der überdeckt all diese Min
Termi.
Ich kann diese dort herstellen, zu Null und Eins verfügen.
Wenn man die grünen Zeilen hier anguckt, das sind die
unterschiedlichen Belegungen von A, D und E.
Und die gehen von Null bis Sieben.
Und wenn ich das habe, dann weiß ich, dass dieser Prim Implikant der
Min Termi Null, Eins, Acht, Neun, Sechzehn, Siebzehn, Sechzehn plus
Acht sind ungefähr Vierundzwanzig und Fünfundzwanzig überdeckt.
Also ich kann diese Informationen bekommen und wenn ich das habe, dann
kann ich meine Überdeckungstabelle aufstellen.
Dann weiß ich, der hier, der überdeckt die hier, der hier überdeckt
der hier und so weiter und so fort.
Und das ist das gleiche Spiel.
Das gleiche Spiel, indem ich zunächst mal gucke, was sind Kernprim
Implikanten.
Kernprim Implikanten sind solche, die nur für ein Kreuz verantwortlich
sind.
Zum Beispiel hier die Fünfundzwanzig wird nur von dem hier überdeckt
oder die Siebzehn, wie man hier sieht.
Dann gucken wir mal weiter, wo haben wir nur einen einzelnen Kreuz in
der Tabelle.
Hier haben wir nur ein Kreuz in der Tabelle.
Das heißt zunächst mal, der hier ist ein Kernprim Implikant und dann
streichen wir Aliment Termi.
Der hier ist auch ein Kernprim Implikant, weil die Zwölf nur von dem
überdeckt wird.
Streichen wir Aliment Termi und der hier ist auch ein Kernprim
Implikant.
Was bedeutet das?
Es bedeutet, ich habe jetzt Aliment Termi bis auf Zweiundzwanzig,
Dreißig und Einunddreißig.
Und wie man sieht hier, Zweiundzwanzig, Dreißig und Einunddreißig kann
ich mit dem hier überdecken.
Das wäre die einfachste Variante.
Das heißt, die DMF ist nichts anderes als C-Quer, B-Quer oder B-Quer,
A -Quer oder D-C-Quer, A-Quer oder E-C-B.
E-C-B hier, wie man sieht, überdeckt die Zweiundzwanzig, Einunddreißig
und Dreißig.
Das sind also die übrigen Mintermi, die durch Kernprim Implikant nicht
überdeckt wurden.
Gibt es Fragen dazu?
Gut, wir haben noch drei Aufgaben, aber ich glaube, wir müssen an der
Stelle aufhören.
Und zwar habe ich noch eine Aufgabe zum Nelson-Verfahren und eine
Aufgabe zur Bundelminimierung.
Die sind so einfach eigentlich, weil wir haben ja auch dazu Aufgaben
in der Vorlesung behandelt.
Deshalb werde ich den kompletten Foliensatz mit den zwei Aufgaben,
also zum Nelson-Verfahren und zur Bundelminimierung, auch heute im
Netz stellen, damit das Thema Minimierungsverfahren abgeschlossen ist,
sodass wir am Mittwoch mit einem neuen Thema hier in der Vorlesung
anfangen können.
Für heute bedanke ich mich für die Aufmerksamkeit und wünsche euch
einen schönen Nachmittag.