Ob ich via Kanonische
Normalformen wirklich die kürzeste Gleichung erwischt habe bleibt so lange
in Frage, bis zu sämtlichen Kombinationen einschließlich ihrer Negationen
alle Ersetzungen durchprobiert worden sind. Anschließend werden die
de Morgan'schen Theoreme
zur Gelichungszusammenfassung eingesetzt. Hier genau setzen die Karnaugh-Veitch-Diagramme an - sie zeigen von vornherein, ob es überhaupt
eine Vereinfachung gibt - und wenn ja, gewinne ich sofort die optimierte
Gleichung (bzw. eine davon, was meistens der Fall ist - es gibt von
vornherein meist mehrere gleichwertige optimierte Lösungsvarianten).
Das Karnaugh-Diagramm (Karnaugh-Veitch-Diagramm, KV-Diagramm) enthält in
gedrängter Form die Informationen der Wertetabelle.
Das Karnaugh-Diagramm hat bei n Eingangsvariablen 2n Felder (Bilder
unten). In die Felder wird 1 eingetragen, wenn der UND-Term der
Eingangsvariablen den Wert 1 der Schaltfunktion liefert. Die anderen Felder
erhalten den Wert 0, wobei das entscheidende die hexdezimal gesplittete
Anordnung der Zielfelder sowie ihre logische Zusammenfassung ist.
Die Bestimmung der reduzierten Schaltfunktion ist bei mehr als zwei
Eingangsvariablen mit Hilfe des Karnaugh-Diagramms meist einfacher als mit
schaltalgebraischen Mitteln.
Die Übungsaufgabe in Sachen
Logik zur Abiturvorbereitung 2021 sollte auch einmal einen vollständigen
sowie komplexen Charakter haben. Die kanonische Normalform ist die
einfachste und zuverlässigste Lösung - allerdings auch die mit dem
garantiert höchsten Aufwand. Nur sehr wenige Logikvorgaben bieten keine
Möglichkeit, weiter zusammengefasst zu werden
Wie bereits erwähnt, kann man
aus den Grundelementen UND, ODER und NICHT jeden beliebigen anderen
logischen Ausdruck zusammenstellen. Wir haben des weiteren gesehen, wie man
aus einer beliebigen Wahrheitstafel zu einer logischen Funktion kommt.
Angesichts der doch relativ aufwendigen und vor allem fehleranfälligen
Methode der Vereinfachung mit Hilfe der Boole'schen Algebra stellt sich
jedoch die Frage, ob es nicht einfachere Methoden gibt, eine möglichst
kompakte logische Funktion zu bestimmen. Eine dieser Methoden beruht auf
einer graphischen Darstellung der Wahrheitstafel und heißt
Karnaugh-Veitch-Diagramm (KV-Diagramm).
Im KV-Diagramm wird die Wahrheitstafel nur in etwas veränderter Form
aufgetragen. Das Diagramm hat die Form eines Schachbrettes, wobei jedes Feld
des Schachbrettes eine hexadezimale Nummer trägt, die der Bitkombination der
Wahrheitstafel entspricht. Die Felder sind so angeordnet, dass sich jedes
benachbarte Feld nur durch jeweils eine Variable unterscheidet. Je nachdem,
wie viele Eingangsvariablen vorhanden sind, ist das KV-Diagramm
unterschiedlich groß. Die Grenzen für 2 bis 6 Eingangsvariablen sind in
folgender Abbildung mit stärkeren Linien markiert.
...
und weil ich das jedes Jahr neu lernen muss, habe ich mir gedacht: "...
schreiben wir's doch mal ganz detailliert mit Beispiel auf!" ...
los geht's:
... es geht nicht um die Zusammenfassung auf logisch "1" oder "0",
sondern um die Zusammenfassung möglichst großer Blöcke (welche sich
auch überlappen dürfen, wenn dies Änderungen an den Eingängen bringt)
die Karnaugh-Tafel muss für jeden Ausgang getrennt erstellt werden
je größer die Anzahl der gesuchten "Ausgangslogiken" Null oder
Eins - desto unwahrscheinlich ist es, das die Zusammenfassung mittels
Karnaugh-Tafeln eine wirkliche Einsparung bringen
wenn man nur wenig Glück hat, wird die "zu erbringende Last" der
Logik nur auf andere Logikelemente verschoben
hat man Pech, dann wird die Karnaugh-Zusammenfassung selbst im
optimalen Falle der der optimalen "Blockbildung" unter Umständen
größer, als eine der minimalen Kanonischen Normalformen sein
Analyse der Anzahl der logischen Signale am jeweiligen Ausgang
(Mehrheit "0" oder "1" entscheiden über das Verfahren
Eintragen der logischen Ausgänge in die Tafel mit der korrekten
Eingangszahl
sind die Zeilenzahlen Hex nummeriert, können die
Ausgangsbelegungen direkt eingetragen werden
anschließend Blockbildung - Ziel ist es, möglichst wenige, aber
dafür große Blöcke zu bilden Fehlerhafte Blockbildung wirkt sich nicht
auf das Ergebnis aus - die Schaltung wird nur unnötig größer
... bei der Blockbildung dürfen die
Begrenzungen der Quadranten nicht überschritten werden
(... ist schon prägend, wenn man den ersten bis zum letzten Schritt
mal "alleine" durchgeht und dabei bemerkt - Vorsicht - in den
Spielregeln steckt noch mehr, und wenn Du dies nicht beachtest, suchst
Du Dich dumm und dämlich - gegeben zum 18.4.2021 um 15.57
Uhr!!!
Blöcke werden immer in Vielfachen von 2 aufgebaut - (... ein Block
von 2 × 2 ist ergo nicht möglich!)
ausgelesen werden nur die Eingänge, welche sich innerhalb eines
Blockes nicht ändern!!!
Die Verbindung zwischen KV-Diagramm und Wahrheitstafel ergibt sich wie
folgt: Jede Eingangsvariable wird mit einem Buchstaben, beginnend mit a, von
rechts nach links benannt. Jede Zeile der Wahrheitstafel entspricht nun
jenem Feld des KV-Diagramms, dessen hexadezimale Nummer der Bitkombination
der Eingangsvariablen entspricht.
Karnaugh-Veich-Diagramm für maximal 6
Eingangsvariable (hier a bis f)
Karnaugh-Veitch-Diagramm für n=5
Zeile
x4
x3
x2
x1
x0
y
HEX-Code
1.
0
0
0
0
0
00H
2.
0
0
0
0
1
01H
3.
0
0
0
1
0
02H
4.
0
0
0
1
1
03H
5.
0
0
1
0
0
04H
6.
0
0
1
0
1
05H
7.
0
0
1
1
0
06H
8.
0
0
1
1
1
07H
9.
0
1
0
0
0
08H
10.
0
1
0
0
1
09H
11.
0
1
0
1
0
0AH
12.
0
1
0
1
1
0BH
13.
0
1
1
0
0
0CH
14.
0
1
1
0
1
0DH
15.
0
1
1
1
0
0EH
16.
0
1
1
1
1
0FH
17.
1
0
0
0
0
10H
18.
1
0
0
0
1
11H
19.
1
0
0
1
0
12H
20.
1
0
0
1
1
13H
21.
1
0
1
0
0
14H
22.
1
0
1
0
1
15H
23.
1
0
1
1
0
16H
24.
1
0
1
1
1
17H
25.
1
1
0
0
0
18H
26.
1
1
0
0
1
19H
27.
1
1
0
1
0
1AH
28.
1
1
0
1
1
1BH
29.
1
1
1
0
0
1CH
30.
1
1
1
0
1
1DH
31.
1
1
1
1
0
1EH
32.
1
1
1
1
1
1FH
Vorgegebene Logiktabelle
x0
x0
x0
x0
x0
x0
x0
x0
0
1
1
0
0
1
1
0
x1
0
00H
01H
05H
04H
14H
05H
11H
10H
0
x3
x1
1
02H
03H
07H
06H
16H
17H
13H
12H
0
x3
x1
1
0AH
0BH
0FH
0EH
1EH
1FH
1BH
1AH
1
x3
x1
0
08H
09H
0DH
0CH
1CH
1DH
19H
18H
1
x3
0
0
1
1
1
1
0
0
x2
x2
x2
x2
x2
x2
x2
x2
0
0
0
0
1
1
1
1
x4
x4
x4
x4
x4
x4
x4
x4
Resultierende
Karnaugh-Veitch-Tafel für 5-Eingangs-Logiken
(richtig seit 18.11.2012)
Karnaugh-Veich-Diagramm für maximal 6
Eingangsvariable (hier a bis f)
Jede Zusammenfassung im Karnaugh-Diagramm soll möglichst viele Felder
enthalten. Die Zahl der Zusammenfassungen soll möglichst klein sein.
Jede Zusammenfassung (Block) bildet ein Glied der gesuchten Schaltfunktion.
Die Variablen, die innerhalb des Blocks ihren Zahlenwert nicht ändern,
werden miteinander durch die UND-Funktion verknüpft. Die sich ergebenden
Terme der Blöcke verknüpft man durch die ODER-Funktion. Diese
schaltalgebraische Gleichung ist die reduzierte Schaltfunktion. Die
Zusammenfassung der Felder mit dem Wert 1 im Karnaugh-Diagramm liefert die
reduzierte Schaltfunktion für die Ausgangsvariable s. Überwiegen im Diagramm
die Felder mit dem Wert 1, so ist es zweckmäßig durch Blockbildung der
Felder mit dem Wert 0 den Wert s der Ausgangsvariablen zu ermitteln. Durch
nochmaliges Negieren von s erhält man dann den Wert s der Ausgangsvariablen.
wenn benachbarte Felder eine 1 enthalten, werden sie zusammengefasst
diese Zusammenfassung darf keine Nullen enthalten
die Zusammenfassungen müssen Rechtecke sein
die Gruppen dürfen sich überlappen
eine Gruppe darf nicht vollständig von einer anderen Gruppe
umschlossen werden
die Anzahl der Felder die man zusammenfasst, muss einer Potenz der
Zahl 2 entsprechen, also 1, 2, 4, 8, 16, ...
die Zusammenfassung kann auch über die Ränder des Diagramms
hinausgehen, also z.B. Feld 3 und 7, oder 6 und 14
alle zusammengehörenden Felder sollten
über jeweils eine 2-Eingangs-AND-Logik geschalten werden können (solange
die Eingangsanzahl kleiner 5 ist - Einzelfelder benötigen hier bereits
eine 3-Eingangs-AND-Logik
Das Karnaugh-Veitch-Diagramm
ist primär nichts anderes, als eine andere (eigentlich sogar kürzere!)
Schreibweise der Wertetabelle einer logischen Funktion. Felder werden
eigentlich nur noch für die Ergebnisse der Funktion vorgesehen - und das
sind immer so viele, wie die Funktion maximale Schaltkombinationen hat.
Beispiel 1:
... irgendwie gegeben
Schaltbelegungstabelle (... eine Kombination von zufälligen
Minimaltermen (Mintermen))
Eingang d
x3 = 8
Eingang c
x2 = 4
Eingang b
x1= 2
Eingang a
x0 = 1
Ausgang y
HEX-Wert
0
0
0
1
1
01H
0
1
0
1
1
05H
1
0
1
1
1
0BH
1
1
1
0
1
0EH
alle übrigen
0
Übertragen Sie aus nebenstehender Wertetabelle die
Schaltkombinationen, die x = 1 liefern, in ein Karnaugh-Diagramm!
Lösung: Das Karnaugh-Diagramm hat 24 = 16 Felder Für die erste
Zeile der Wertetabelle a b c d sucht man im Diagramm das Feld, welches keine
a-Markierung (Felder 1 bis 8), welches b-Markierung (verbleiben Felder 3, 4,
7, 8), welches keine c-Markierunc (verbleiben Felder 4, 8) und welches
d-Markierunc (verbleibt Feld 8) enthält. Entsprechend überträg man die
restlichen Zeilen der Wertetabelle.
Jeder Zeile der Wertetabelle entspricht ein Feld im KV-Diagramm. Die
Streifen für die Variablen (a, b, c, d) können im KV-Diagramm auch anders
liegen, z. B. a mit d getauscht.
Wandeln Sie die für die vier Eingangsvariablen x0, x1,
x2,
x3
gegebene vollständige Wertetabelle der Schaltzustände (Tabelle oben
sowie Bild links) in ein Karnaugh-Diagramm um!
Lösung: Man zeichnet das Karnaugh-Diagramm mit 16 Feldern und
überträgt aus der Wertetabelle der Schaltzustände in das Diagramm die Werte
1 bei solchen Kombinationen der Eingangsvariablen, bei denen s = 1 wird.
Die Minimierung einer Schaltfunktion kann direkt dem Karnaugh-Diagramm
entnommen werden. Dazu fasst man benachbarte Felder, die jeweils den Wert 1
haben, zu Blöcken zusammen. Die Zusammenfassung muss immer so erfolgen, dass
ein Block 2, 4 oder 8 Felder enthält, die ein Rechteck oder ein Quadrat
bilden. Benachbarte Felder (siehe Zuordnung unter Punkt 4.) sind auch Felder der
letzten und der ersten Zeile und der letzten und der ersten Spalte. Die
einzelnen Felder dürfen auch in mehreren Zusammenfassungen vorkommen (siehe
Punkt 4).
4.
Zusammenfassung nach Bool'schen Regeln sowie den de Morgan'schen Theoremen
Logik zusammenfassen geht
ganz klassisch mit den Regeln der Bool'schen Alegbra - gibt's für jeden
Studenten in der universitären Grundlagen-Mathematik gratis und ist dort gut
verhasst, weil die Hälfte der Bewerber seit Jahren genau daran scheitert.
5.
Alternative Lösungen
Alternativ würde heute
niemand mehr derartigen Aufwand zur Realisierung selbst kleinerer Projekte
mit simplen Logikbauelementen projektieren - sowohl Entwicklung,
Leiterplattenfertigung, die Anzahl sowie die Menge Einzelbauelemente - und
letztendlich die Kosten würden jedem Endanwender raten: "... mach' das
irgendwie anders, aber nicht so!!!"
Hat schon diese Site viel mit Logik zu tun, so
kann's auf einer der folgenden damit noch happiger werden. Mich beeindruckt
dabei immer wieder, wie man unter dem unwissenden Volk (das bist Du, der Du
erarbeitend bis zu diesem Punkte gelangt bist, schon lange nicht mehr!) mit
den Wörtchen "und",
"oder"
und "nicht"
evtl. gespickt mit den Regeln der Schachtelung sowie Relationenalgebra Verwirrung stiften kann.Wer's nicht glaubt, löst die Aufgaben unter
dem dritten Verweis - aber bitte alle -
und das schnell ;-)
... dieser Text wurde nach den
Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal
beschlossen, an diesem Zirkus nicht mehr teilzunehemn ;-)
„Dieses Land braucht eine Steuerreform, dieses Land
braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“
Diddi Hallervorden, dt. Komiker und Kabarettist
Diese Seite
wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)
... das
ZIP-Archiv komplett auspacken und die .EXE-Datei starten
Dateidownload
im Word-Format
Download als ProfiLab 4.0-Datei
Dateidownload
im EXCEL-Format
...
zugehöriger Download im CorelDraw 11.0-Format
hier auch zu Download als CorelDraw 11.0 Datei
hier die
Original-CAD-Zeichnung dazu
