Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Frage zum Nelson-Verfahren - Bestimmung der Primimplikate möglich?
Hallo zusammen,
ich hätte eine kleine Frage zum Nelson-Verfahren. Das Verfahren haben wir ja so kennengelernt, dass man zunächst alle don’t cares als Einsstellen annimmt und eine Nullblocküberdeckung bildet. Anschließend formt man diese Nullblocküberdeckung um und erhält eine Einsstellenüberdeckung. Das Nelson-Verfahren dient somit zur Ermittlung der PrimimplikaNten. 
Soweit so klar! Meine Frage wäre nun, ob man das Nelson-Verfahren auch zur Ermittlung der Primimplikate nutzen darf? Muss man dazu die don’t-cares als Nullstellen annehmen und dann zunächst die DNF bilden, welche dann zu einer KNF umgeformt wird?
Bei der Bestimmung von Primimplikaten mit dem Quine McCluskey-Verfahren, muss man wohl alle don’t-cares analog als Nullstellen annehmen? Stimmt das?
Vielen Dank für die Antwort!
froschigon
Prinzipiell sind Primimplikate Nullstellenüberdeckung. Primimplikante hingegen Einsstellen inklusive Dont cares. Soweit so gut und nichts Neues bisher.
Was tut denn das Nelson-Verfahren?
- Ver-ODERe alle Literale der Nullstellen, NEGIERE die Literale. ver-UND-e die Nullstellen. Also wenn eine Nullstelle in X4X3X2X1 liegt, dann wäre das (NICHT X4 + NICHT X3 + NICHT X2 + NICHT X1)(Zweite Nullstelle)(…)
WICHTIG: DCs werden als EINSSTELLEN behandelt und daher nicht mit einbezogen in die Terme. - Distribuiere die daraus entstehenden Terme aus.
- Wende die Regeln der Booleschen Algebra an, um die Terme zu minimieren.
Ein Verfahren, das die Einsstellen hingegen ermitteln würde, sähe so aus:
- Ver-UND-E alle Literale, ver-ODER-e die Einsstellen/DCs. HIER werden DCs berücksichtigt und wie Einsstellen gehandhabt, kommen also mit in die Terme rein. Also X4X3X2+X4X1X2…
- Wende wieder die Regeln der Booleschen Algebra an, um Terme zu minimieren.
Die Verfahren klingen auf den ersten Blick ähnlich, sind es aber nicht! Was du in Quine/McCluskey systematisch anwendest ist nichts anderes als das, was du hier im zweiten Verfahren eigentlich tust. Denn bei veroderten Einsstellen arbeitest du i.d.R. immer mit den gleichen Regeln um zu minimieren. Hast du z.B. X4X3X2X1+X4X3X2NICHTX1 dann lässt sich das zu X4X3X2 zusammenfassen.
Bei Quine/McCluskey schreibst du statt den ganzen ODER nur alle Terme in Klassen, die nach Anzahl der negierten Literale geordnet werden. Das ist lediglich etwas “übersichtlicher” als die andere Lösung, die ich dir vorgeschlagen habe, ist aber vom Ergebnis her genau das Gleiche wie im zweiten Verfahren auch.
Um also auf deine Fragen einzugehen:
1.) Nein, das Nelson-Verfahren ist explizit ausgelegt zur Nullblocküberdeckung.
2.) Auch falsch. Dont Cares werden bei Quine/McCluskey als Einsstellen angenommen.
Vielen Dank für deine Antwort!
Quine-McCluskey:
Um noch einmal kurz auf das Quine-McCluskey-Verfahren einzugehen, habe ich auf Wikipedia (Verfahren nach Quine und McCluskey – Wikipedia) recherchiert. Das Quine-McCl.-Verfahren kann (wie du gerade geschrieben hast) nur auf die Disjunktive Form angewendet werden. Es sei laut Wikipedia möglich die Konjunktive Form in eine distinktive Form umzuwandeln und dann das Quine-McCl.-Verf. anzuwenden und danach ggf. wieder eine Umwandlung von der DNF zurück in die KNF vorzunehmen.
Nun betrachte man das Beispiel auf Wikipedia: Konjunktive Normalform – Wikipedia
Hier liegt eine KF und eine DF vor. Würde man die KF negieren, erhält man ja eine DF, welche man mit dem Quine-McCluskey-Verfahren minimieren kann und dann durch Negation wieder in eine KNF verwandeln kann oder? So ist es doch über Umwege möglich die Primimplikate einer KF zu ermitteln oder ist das doch anders? Wie verhält es sich dann mit don’t cares? Ich denke diese werden bei einer KF nicht ebenfalls wieder zu den Einsstellen gezählt oder nicht?
Nelson-Verfahren:
Hierbei handelt es sich nicht um das Nelson-Verfahren sondern um ein Verfahren, welches genauso wie das Nelson-Verfahren Primimplikanten bestimmt oder? Im Endeffekt spart man sich nur den Schritt "2. Distribuiere die daraus entstehenden Terme aus.
", welcher ja gar nicht mehr nötig ist oder?
Gibt es auch ein Verfahren zur Bestimmung der Primimplikate mit Ausnahme des Symmetriediagramms?
Vielen Dank schon einmal!
froschigon
Wieso eine KNF negieren? Das, was du im 1. Schritt des Nelson-Verfahrens tust, nämlich die negierten Literale der 0-Stellen herausschreiben, IST bereits die KNF! Wenn du diese ausdistribuierst, dann kommst du auf die Primimplikanten, was ja auch Sinn und Zweck der ganzen Geschichte ist. Analog dazu könntest du auch die KMF ermitteln, indem du die Terme soweit es geht zusammenfasst. Was also nichts anderes heißt als: Möglichst große Nullblöcke bilden. Und zwar so, das effektiv alle Nullstellen mit der minimalen Anzahl an Termen abgedeckt sind.
Und wie gesagt, werden don’t cares als Einsstellen angenommen.
Übrigens zum Hintergrund dieser ganzen Geschichte: Bei den Minimalformen wollen wir möglichst wenige Gatter etc. verwenden für eine Ansteuerfunktion. Da Don’t Cares für diese keine Rolle spielen, kann man so möglichst einfach Terme minimieren, indem man kleinere Einserterme zu größeren Termen mit Don’t Cares zusammenfasst. Das Resultat sind weniger Gatter als wenn man z.B. nur die Einsstellen auffassen würde.
DMF und KMF sind logisch äquivalent (Kannst dir ja mal ausrechnen und eine Wahrheitstabelle aufstellen wenn du willst, sollte aber nun offensichtlich sein), aber natürlich ist der Weg dazu jeweils völlig anders, ebenso die Terme selbst.
yo, klar. Das was ich dir da gesagt habe ist eigtl das, was du formalisiert beim Quine-McCluskey-Verfahren anwendest. Quine-McCluskey macht das Ganze nur wesentlich einfacher als wenn du selbst per Hand alle Terme mit booleschen Regeln durcharbeiten würdest.
Nicht das ich wüsste… Also es kommt zumindest in der Vorlesung kein solches Verfahren dran. Obs darüber hinaus was gibt kann ich dir nicht sagen.
Du kannst das Prinzip der Dualität ausnutzen und so alle Verfahren auch jeweils umkehren.
Zur Bestimmung der Primimplikate würde QMC so lauten:
- Alle Don’t Cares als Nullstellen annehmen
- Wie gewohnt nach Anzahl der Literale und Negierungen in Klassen einsortieren
- Diese Klassen wiederholt reduzieren und bereits benutzte Terme als “nicht Primimplikat” markieren
- Alle nicht markierten Terme sind Primplikate
- Reine Don’t Care Überdeckungen streichen
Das Nelson-Verfahren für Primimplikate funktioniert auch dual:
- Alle Don’t Cares als Nullstellen annehmen
- Einsblocküberdeckung
- Aufstellen eines schaltalgebraischen Ausdrucks in disjunktiver Form
- Distributiv- und Absorptionsgesetz
- Reine Don’t Care Überdeckungen streichen
Beim Petrick-Verfahren musst du die Petrick-Variablen nun für die Primimplikate statt für die Primimplikanten erstellen. Das war’s!