Das war's für heute.
Bis zum nächsten Mal.
KV-Diagramm und Terme. Vom KV-Diagramm zum Term und andersherum.
Das Carnot-Feitsch-Diagramm, kurz KV-Diagramm, ist ein grafisches Optimierungsverfahren für
bullshit Terme, das sich insbesondere zur manuellen Optimierung für drei oder vier Variabeln eignet.
Bei weniger Variabeln kriegt man es in der Regel auch mit Buccia Algebra direkt hin und
bei mehr als vier Variabeln wird es manuell schon wieder eng, aufgrund der räumlichen
Nachbarschaftsverhältnisse, die man sich als Mensch nur schwer vorstellen kann.
Die grundsätzliche Idee ist die, dass in einer Tabellenform, also grafisch, Terme
getragen werden und
diese können entfallen, wenn sich die Variablenbelegung nur in dieser einen Variablen unterscheidet.
Und das sieht man zumindest bei drei oder vier Variablen sehr viel einfacher,
als man das per Buccia-Algebra ausrechnen kann.
Natürlich ist das möglich per Buccia-Algebra, aber das K-V-Diagramm ist da schon einfacher.
Wie wird ein K-V-Diagramm jetzt konstruiert?
Systematisch. Es gibt hier mehrere Varianten. Das sieht man direkt am ersten
Fall, wenn man nur eine Variable hat, hat man entsprechend zwei Felder, weil immer
die Variable selbst und die Negation, also x1 nicht, die für gewöhnlich dann
nicht hingeschrieben wird, notiert werden. Jetzt könnten Sie auch das Feld
hier mit x1 belegen und da, wo jetzt x1 dran steht, für x1 nicht
resolvieren. Das hat dann
eine andere Aufteilung zufolge. Grundsätzlich erhält man das nächst komplexere KV-Diagramm
immer durch Umklappen an den Horizontalen und dann Umklappen an den Vertikalen. Das soll
heißen, wir gehen mal vom KV-Diagramm für eine Variable aus, dann wird das einmal gespiegelt
bei einer x-Achse sozusagen, erhält man das hier, klappt das vertikal um, dann hat man
die Variante für 3 Variablen, dann klappt man wieder horizontal um, da hat man das für
4 und so weiter. Die beiden gängigsten Varianten sind die für 3 und 4 Variablen, meistens hat
man Übungsprobleme vorliegen, die auf 4 Variablen bezogen sind.
Das KV-Diagramm ist eigentlich sehr intuitiv und leicht umzusetzen, solange man sich bei
drei oder vier Variablen bewegt.
Das einzige Problem und auch das, was dafür sorgt, dass es ab vier Variablen, bei mehr
als vier Variablen schwieriger wird, sind die Nachbarschaften.
Benachbarte Elemente in einer Tabelle sind benachbart nach wie vor, allerdings, da
man es hier mit räumlichen Strukturen bezüglich der Nachbarschaften zu tun hat,
ist es relativ schnell schwer vorstellbar.
Was relativ häufig vorkommt, sind die sogenannten Randnachbarschaften.
Wenn alle vier Ecken belegt sind, dann kann man die auch zu einem Viererblock zusammenfassen,
genauso wie die Eckfelder hier mal mit Grün markiert.
Also dieses...
grüne Feld ist mit dem grünen Feld hier benachbart oder die grauen beiden grauen
Felder ebenfalls. Es kann helfen sich das als sogenannter Buhlscher Würfel vorzustellen.
Diese grauen Striche deuten die Nachbarschaften an. Das heißt, wenn sie
hier ein Würfel haben, dann sind die grauen Flächen jeweils für
Nachbarschaften stehend. Und deswegen wird auch klar, warum hier diese
Flächen...
zueinander benachbart sind. Wenn Sie sich hier den Schnitt durch den Würfel vorstellen und das 2D-mäßig aufklappen, dann hat der braune Knoten hier, die beiden, den grünen und den türkisen zum Nachbarn, den grünen sehen Sie direkt, aber der türkise ist aufgrund des Schneidevorgangs jetzt auf der anderen Seite.
Aber wenn Sie den wieder zusammenkleben sozusagen und einen Würfel haben, dann liegt Braun und Türkis zusammen.
Deswegen haben Sie diese Randnachbarschaften. Also das ist nicht so leicht mit der Vorstellung,
deswegen hat auch das KV-Diagramm gewisse Grenzen. Schauen wir uns das erste Beispiel an.
Wie kommt man vom Term zum KV-Diagramm, vom KV-Diagramm zum Term und wie kriegen wir die Minimierung hin?
Ausgehend von der distruktiven Normalform.
Erhält jeder unverknüpfte Teilterm einen Eintrag mit 1 in irgendeiner Zelle.
Das heißt, man klappert systematisch die Variablen ab.
Ich empfehle, wie folgt, vorzugehen.
Man geht systematisch bezüglich der Felder, ich nenne das Reduktionsverfahren vor,
soll heißen X1.
Taucht in den beiden Spalten hier auf. Die Spalte und die Spalte. Das heißt, man kann
über die vier Zellen hier ein Finger draufhalten oder darüber bewegen.
X2 nicht. X2 nicht ist in dieser Zeile. Das heißt, aus den vier Feldern werden
die beiden hier schon mal gestrichen und man kreist jetzt nur noch um die
beiden Kandidatenfelder. Man schränkt die Menge der möglichen Felder also
excessiver ein.
Jetzt haben wir hier noch x_3 nicht. x_3 ist hier. x_3 nicht ist in dem Bereich. Das heißt, es bleibt nur die Zelle übrig.
Erste Einschränkung. Aus acht Zellen wurden die vier hier.
Zweite Einschränkung. Aus den Vieren wurden die zwei Felder. Und aus den zwei Feldern durch die letzte Einschränkung ist dann unser Ziel übrig geblieben.
Hier ist also die eins für den linken Teilterm.
Der rechte Teilterm, der Klamann-Term, gleiches Verfahren. x1 sind die Felder und x2 nicht,
auch wieder die untere Zeile entfällt, und x3 bleibt nur diese Zelle übrig,
die kriegt nur eins spendiert und so weiter. Sollten wir die Situation haben,
dass wir den Term...
für den die eins steht oder diesen hier rekonstruieren müssen, gehen sie einfach rückwärts vor.
Nehmen wir uns mal den Term her.
Da lesen sie
für jede Variable den Term ab, der da eben in der Zeile bzw. Spalte steht.
Hier ist es x1
und x2 nicht und x3. Fertig.
Gut, wie geht es jetzt weiter?
Was die Optimierung angeht. Man trägt die Terme ja zunächst ein, um sie dann zu vereinfachen. Das ist ja der ganze
Sinn des Carnot-Falch-Diagramms.
Immer maximal große Blöcke bilden, wobei Blöcke nur in Größen einer Zweierpotenz erlaubt sind. Sprich 2, 4, 8, 16, 32, 64er Blöcke.
Und immer maximal große Blöcke bilden, sonst kriegen sie nicht zwangsläufig ein minimales Ergebnis.
Dabei die Ränder beachten.
Gut, hier sind nur zwei Einsen vorhanden. Da bildet sich der zweier Block einfach und entfällt eine Variable entfällt, wenn sie sowohl in negierter als auch in nicht-negierter Form vorkommt.
Gucken wir uns das an. X1 kommt in beiden Einsfeldern vor, muss notiert werden.
X2 haben wir hier in der unteren Zeile.
In der für uns relevanten Zahl steht durchgängig X2 nicht.
Wird als X2 nicht notiert.
Die 1 ist X3, die Nachbarschafts 1 ist X3 nicht.
Das heißt wir haben X3 und X3 nicht. Die Variable kommt in negierter und in nicht negierter Form vor.
Fliegt also raus.
Sprich man kann den Term
vereinfachen zu diesem.
Der ist so übersichtlich, das kriegen wir
auch mit Butcher Algebra durch scharfes Hinschauen noch hin.
Wie würde man da vorgehen?
Wir würden x1 und x2 nicht aus dem Term rausschreiben
und aus dem Term auch, sprich ausklammern
und dann bleibt
hier übrig
x3 nicht und x3
und die
Unverknüpfung von einer Variable mit seiner Negation ist immer 0, kann also entfallen.
Hier haben wir das zweite Beispiel.
Es werden immer maximal große Einsmengen gebildet und es sind nur Zweierpotenzen erlaubt
als Elemente, sprich zwei Elemente, vier Elemente, acht, 16, 32, 64 und so weiter.
Das heißt, sie können jetzt nicht hier so einen sechser Block bilden.
Weil es keine Zweierpotenz ist.
Gut, schauen wir uns die Minimierungsoption hier mal an.
Fangen wir mit dem großen Block an.
Immer möglichst große Blocke bilden.
Das wurde hier gemacht.
4 Einsen, 2 hoch 2 ist 4, also eine Zweierpotenz wurden erfasst.
Und jetzt schaut man sich an, welche
Variablen wie vorkommen. Und taucht eine Variable sowohl negiert als auch nicht
negiert vor, dann fliegt sie raus. x1 ist hier aufgetragen. Wir haben in dem 1er
Block sowohl x1 als auch x1 nicht. Deswegen entfällt x1. x2 steht in dem
Bereich, also die beiden Zeilen.
Alle Einsen des Blockes sind mit x2 versehen, muss also da bleiben. Okay, da haben wir notiert.
x3 ist in den beiden Spalten vorrätig.
In beiden Spalten, wo unsere Einsen stehen, haben wir nur x3.
Nicht auch x3 nicht, also bleibt x3 stehen. x4 steht in den beiden Zeilen hier.
Eine
Reihe von Einsen wird mit x4 belegt.
Die Variable kommt also sowohl in negierter als auch in nicht negierter Form vor und entfällt deswegen.
Das heißt, die Minimierung des Blocks hier ergibt sich zu x2 und x3.
Okay, schauen wir uns diesen hier an.
Zweier Block x1, x1 nicht, entfällt, taucht nicht auf.
Dann haben wir x2.
Dann haben wir x5.
Dann haben wir x10.
Taucht nur in der Form x2 nicht auf. Steht da. Okay. x3 haben wir in der Spalte und in der Spalte.
Beide Einsen tauchen nur in der x3 nicht Form auf. Haben wir notiert. x4 ist in der Zeile und in der.
Das heißt die beiden zahlen.
Für uns ist ja die oberste relevant, taucht nur mit x4 nicht auf, alles klar.
Also x2 nicht und x3 nicht und x4 nicht. Dieser Block, der linke mit zwei 1s versehene.
x1 taucht nur in der Spalte x1 nicht auf, ist erhalten.
x2 taucht hier als x2 auf und hier als x2 nicht entfällt, also alles klar.
x3 taucht nur hier auf, in der Spalte, als x3 nicht. Gut. x4 nicht und x4 nicht, also nur als x4 nicht. Auch gut.
Trickreich ist dann hier wieder die Randnachbarschaft. Erstmal muss man sie als solche erkennen und dann aufpassen, dass man die richtigen Variablen erwischt.
Schauen wir uns das an. x1 nicht.
Und rechter Rand auch x1 nicht, deswegen x1 nicht notieren. x2 taucht hier auf.
Der hier hat x2 nicht, der hier hat auch x2 nicht, also notieren. x3, der rechte Rand
hat x3, der linke Rand hat x3 nicht, entfällt also. x4, der
rechte rand hat x4 und die gleiche zeile auch x4, wir notieren x4. alles klar. was
hier nicht eingetragen ist, ist der zweier block, der hier noch übrig bleibt.
wir müssen ja die ganze eins menge erfassen. was passiert da? x1 bleibt
halten, also x1 und x2 und
x3 nicht, x4 entfällt.