Das Polynom von Zhegalkin ist ein algebraisches Polynom, das es ermöglicht, jede boolesche Funktion mit einer Kombination aus logischen Operationen SOWOHL (logische Multiplikation) als auch (logische Addition) als auch NICHT (logische Negation) zu beschreiben. Die Konstruktion des Zhegalkin-Polynoms aus der Wahrheitstabelle ist einer der wichtigsten Schritte bei der Analyse logischer Funktionen.
Wahrheitstabelle ist eine Methode zur Darstellung einer Booleschen Funktion, mit der Sie Funktionswerte für alle möglichen Kombinationen von Eingabevariablen definieren können. Sie besteht aus von links nach rechts geordneten Spalten, die die Eingabevariablen darstellen, und aus der letzten Spalte, die den Funktionswert für diese Kombination von Eingabevariablen darstellt.
Um ein Zhegalkin-Polynom aus der Wahrheitstabelle zu erstellen, müssen Sie die folgenden Schritte ausführen:
- Schreiben Sie die boolesche Funktion als abgekürzte DNF (disjunktive Normalform) oder CNF (konjunktive Normalform) gemäß der Wahrheitstabelle. Um dies zu tun, müssen Sie Kombinationen von Eingabevariablen finden, bei denen die Funktion 1 ist. Diese Kombinationen bilden Konjunktionen, die unter Verwendung der Operation ODER zu DNF oder CNF kombiniert werden.
- Operation ersetzen ODER durch Addition (XOR) und die Operation und die Multiplikation (AND). Ersetzen Sie die Operation AUCH NICHT durch eine Addition mit einer Konstante.
- Ersetzen Sie die Variablen durch die Buchstaben des Alphabets. Jeder Variablen wird ein Buchstabe zugewiesen, z. B. X1, X2, X3 usw.
- Das Polynom des Schegalkins brennen in Form einer algebraischen Formel unter Verwendung der erhaltenen Werte aus den vorherigen Schritten. Dabei werden Kombinationen von Eingabevariablen und deren Negation als Multiplikatoren geschrieben, und das Polynom selbst wird unter Verwendung von Additions- und Multiplikationsoperationen erstellt.
Die Konstruktion des Zhegalkin-Polynoms aus der Wahrheitstabelle ermöglicht es, den Ausdruck einer booleschen Funktion zu reduzieren und in algebraischer Form darzustellen, was für weitere mathematische Operationen und die Analyse der Funktion nützlich ist.
Was ist ein Zhegalkin-Polynom?
Das Polynom von Jegalkin ist eine der Hauptformen der Funktionsdarstellung in der Booleschen Algebra. Es wird in verschiedenen Bereichen wie digitaler Elektronik, Kryptographie und Algorithmentheorie angewendet.
Der Prozess der Konstruktion des Zhegalkin-Polynoms basiert auf der Wahrheitstabelle der Funktion, wobei jede Kombination von Variablenwerten dem Wert der Funktion entspricht.
Das Zhegalkin-Polynom hat eine Reihe nützlicher Eigenschaften, einschließlich der Möglichkeit, Funktionsoperationen mit algebraischen Operationen an Polynomen durchzuführen.
Das Polynom von Zhegalkin ermöglicht es, komplexe boolesche Funktionen kompakt darzustellen und ihre Analyse zu vereinfachen. Es kann auch verwendet werden, um das Problem der Minimierung von booleschen Funktionen zu lösen.
Es ist wichtig zu beachten, dass das Zhegalkinpolynom eine einfache und effektive Möglichkeit ist, Funktionen in der Booleschen Algebra darzustellen, die in verschiedenen Bereichen von Wissenschaft und Technologie weit verbreitet ist.
Warum ein Polynom von Zhegalkin bauen?
Die Konstruktion des Zhegalkin-Polynoms reduziert die Komplexität von booleschen Funktionen und führt deren Analyse und Optimierung durch. Das Zhegalkinpolynom kann zur Bestimmung der minimalen Form einer booleschen Funktion sowie zur Durchführung verschiedener Operationen wie Synthese und Analyse von logischen Schaltungen, Erstellung von Algorithmen und Programmen, Gestaltung und Überprüfung von Schaltungen und vieles mehr verwendet werden.
Darüber hinaus ist die Konstruktion des Zhegalkin-Polynoms Teil des Prozesses, das Problem der Synthese boolescher Funktionen zu lösen. Wenn Sie das Polynom von Zhegalkin kennen, können Sie bestimmen, welche Kombination von Eingabevariablen zu einem hohen Funktionswert führt. Dies ermöglicht die Analyse und Optimierung von digitalen Geräten wie Computern, Mikrocontrollern, Schaltkreisen und anderen.
Daher ist die Struktur des Zhegalkin-Polynoms von großer praktischer Bedeutung und ist ein wesentlicher Bestandteil der Arbeit auf dem Gebiet der Booleschen Funktionen und der digitalen Logik.
Algorithmus für die Konstruktion des Polynoms von Zhegalkin
Schritte des Algorithmus zum Konstruieren eines Zhegalkin-Polynoms:
- Erstellen Sie eine Wahrheitstabelle der Funktion, einschließlich aller möglichen Kombinationen von Funktionseingabewerten.
- Fügen Sie die Funktionseingabewerte in die erste Spalte der Wahrheitstabelle ein.
- Legen Sie die zweite Spalte der Wahrheitstabelle in die Ausgabewerte der Funktion.
- Finden Sie die Zeilen der Wahrheitstabelle, in denen die Ausgabewerte der Funktion 1 sind.
- Für jede Zeile, in der der Ausgabewert 1 ist, können Sie die Eingabewertverknüpfungen mithilfe der Operation "oder" erstellen.
- Erstellen Sie das Polynom des Schegalkins, indem Sie alle Verknüpfungen aus dem vorherigen Schritt mit der Operation Multiplizieren mit dem Binärwert kombinieren.
Betrachten Sie zum Beispiel eine boolesche Funktion, die durch eine Wahrheitstabelle angegeben wird:
| Eingänge | Ausgang |
|---|---|
| 0 | 1 |
| 1 | 0 |
Das Polynom von Zhegalkin für diese Funktion wird sein:
Ausgang = (Eingang und nicht Eingang)
Schritt 1: Erstellen einer Wahrheitstabelle
Beginnen wir mit der Definition von Variablen in einem Ausdruck. Für jedes Vorkommen einer Variablen im Ausdruck erstellen wir eine Spalte in der Wahrheitstabelle. Die Anzahl der Zeilen in der Wahrheitstabelle wird durch die Formel 2^n bestimmt, wobei n die Anzahl der Variablen im Ausdruck ist.
Schreiben wir für jede Zeile in der Wahrheitstabelle die entsprechenden Variablenwerte auf. Die erste Zeile enthält alle Nullen, die zweite Zeile enthält alle Einheiten, die dritte Zeile hat die erste Variable auf Null und die restlichen Einheiten auf Eins und so weiter.
In der letzten Spalte der Wahrheitstabelle schreiben wir dann die Werte des Ausdrucks für jede Zeile mit den Regeln der logischen Operation, die im Ausdruck angegeben ist. Wenn der Ausdruck für eine gegebene Zeichenfolge wahr ist, schreiben wir 1, wenn falsch 0 ist.
Beispiel für eine Wahrheitstabelle für den Ausdruck A und B:
| A | B | A AND B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Die Wahrheitstabelle ist fertig und jetzt können wir mit dem nächsten Schritt fortfahren - dem Aufbau des Polynoms von Zhegalkin.
Schritt 2: Erstellen Sie ein Implikant
Um einen Implikanten zu erstellen, müssen Sie alle Zeilen der Wahrheitstabelle überprüfen und die Zeilen, bei denen die Funktion 1 ist, in eine separate Tabelle schreiben. Gruppieren Sie dann die Zeilen in Implikanten, indem Sie sie kombinieren, indem Sie Literale entfernen, die in allen Zeilen den Wert 1 haben. Auf diese Weise erhalten wir eine Reihe von Implikanten, die alle Funktionswerte vollständig abdecken.
| Eingabewert | Funktionswert |
|---|---|
| 0 0 0 | 0 |
| 0 0 1 | 0 |
| 0 1 0 | 1 |
| 0 1 1 | 1 |
| 1 0 0 | 0 |
| 1 0 1 | 1 |
| 1 1 0 | 0 |
| 1 1 1 | 1 |
Basierend auf dieser Tabelle können wir die folgenden Implikanten hervorheben:
Diese Implikanten decken alle Zeilen der Wahrheitstabelle vollständig ab, wobei die Funktion den Wert 1 annimmt. Jetzt können wir diese Implikanten verwenden, um ein Zhegalkin-Polynom zu konstruieren.
Schritt 3: Minimieren Sie das Implikant
Nachdem wir das Polynom von Zhegalkin nach der ursprünglichen Wahrheitstabelle aufgebaut haben, ist es notwendig, das Implikant zu minimieren, um die kompakteste Form des Polynoms zu erhalten.
Die Minimierung eines Implikanten besteht darin, mithilfe der folgenden Methoden identische oder ähnliche Implikanten zu kombinieren:
- Die Methode von Petrik besteht darin, Implikanten zu kombinieren, die die gleiche Anzahl signifikanter Variablen haben und sich nur an einer Position unterscheiden.
- Die Methode des Quain-Mac-Klaskys basiert auf der Suche nach Kreisimplikanten und deren Verarbeitung. Ein Kreisimplikant ist eine Menge von Implikanten, die an mehreren Positionen die gleichen 1 und 0 enthalten und sich nur an einer Position unterscheiden.
- Die Quain-Methode besteht darin, nicht-äquivalente Kreisimplikanten zu finden und zu verarbeiten.
Nachdem das Implikant minimiert wurde, erhalten wir die am besten optimierte Form des Polynoms von Zhegalkin, das aus einer minimalen Menge an Implikant besteht.
Beispiel für die Konstruktion eines Polynoms von Zhegalkin
Betrachten wir zur Verdeutlichung ein Beispiel für die Konstruktion eines Zhegalkin-Polynoms für die Funktion f(x)1, x2, x3) = 1, angegeben durch die Wahrheitstabelle:
| x1 | x2 | x3 | f(x1, x2, x3) |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
Schritt 1: Erstellen Sie eine Wahrheitstabelle mit binären Darstellungen von Variablen und Funktionswerten:
| x1 | x2 | x3 | f(x1, x2, x3) | x1x2x3 |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 000 |
| 0 | 0 | 1 | 1 | 001 |
| 0 | 1 | 0 | 0 | 010 |
| 0 | 1 | 1 | 0 | 011 |
| 1 | 0 | 0 | 0 | 100 |
| 1 | 0 | 1 | 1 | 101 |
| 1 | 1 | 0 | 0 | 110 |
| 1 | 1 | 1 | 0 | 111 |
Schritt 2: Ordnen Sie die Zeilen der Wahrheitstabelle in aufsteigender Reihenfolge der Werte der binären Darstellungen an. Wir erhalten die folgende Tabelle:
| x1x2x3 | f(x1, x2, x3) |
|---|---|
| 000 | 1 |
| 001 | 1 |
| 010 | 0 |
| 011 | 0 |
| 100 | 0 |
| 101 | 1 |
| 110 | 0 |
| 111 | 0 |
Die resultierende Tabelle ist eine Schegalkin-Tabelle für eine bestimmte Funktion.
Beispiel einer Wahrheitstabelle
Um den Prozess der Konstruktion des Polynoms von Zhegalkin zu veranschaulichen, betrachten wir die folgende Wahrheitstabelle:
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
In dieser Tabelle sind alle möglichen Kombinationen der Werte der Variablen A, B und C zusammen mit den entsprechenden Werten der Funktion F aufgeführt. Anhand dieser Werte können Sie ein Polynom von Zhegalkin konstruieren, das ein Ausdruck ist, der aus Konstitutionen besteht und die Ausgabefunktion bildet.
