Zhegalkin-Polynom - Zhegalkin polynomial

Zhegalkin (auch Žegalkin , Gégalkine oder Shegalkin ) Polynome sind eine Darstellung von Funktionen in Algebra Boolesche . Sie wurden 1927 vom russischen Mathematiker Ivan Ivanovich Zhegalkin eingeführt und sind der Polynomring über den ganzen Zahlen modulo 2 . Die resultierenden Entartungen der modularen Arithmetik führen dazu, dass Zhegalkin-Polynome einfacher als gewöhnliche Polynome sind und weder Koeffizienten noch Exponenten erfordern. Koeffizienten sind redundant, da 1 der einzige Koeffizient ungleich Null ist. Exponenten sind redundant, weil im arithmetischen Mod 2 x ² = x ist . Daher ist ein Polynom wie 3 x ² y ⁵ z kongruent zu xyz und kann daher als xyz umgeschrieben werden .

Boolesches Äquivalent

Vor 1927 galt die Boolesche Algebra als Berechnung logischer Werte mit logischen Operationen wie Konjunktion , Disjunktion , Negation usw. Zhegalkin zeigte, dass alle booleschen Operationen als gewöhnliche numerische Polynome geschrieben werden können, die die falschen und wahren Werte als 0 und 1, die ganzen Zahlen mod 2 darstellen. Die logische Konjunktion wird als xy und logisch exklusiv geschrieben - oder als arithmetische Addition mod 2 (geschrieben) hier als x ⊕ y , um Verwechslungen mit der allgemeinen Verwendung von + als Synonym für inklusive-oder ∨) zu vermeiden. Das logische Komplement ¬ x ist dann x ⊕1. Da ∧ und ¬ eine Basis für die Boolesche Algebra bilden, sind alle anderen logischen Operationen Zusammensetzungen dieser Grundoperationen, und daher können die Polynome der gewöhnlichen Algebra alle Booleschen Operationen darstellen, so dass das Boolesche Denken unter Verwendung der Elementaralgebra durchgeführt werden kann .

Zum Beispiel kann die Boolesche 2-out-of-3 Schwelle oder Medianoperation wird als Polynom geschrieben Zhegalkin xy ⊕ yz ⊕ zx .

Formale Eigenschaften

Formal ist ein Zhegalkin-Monom das Produkt einer endlichen Menge unterschiedlicher Variablen (daher quadratfrei ), einschließlich der leeren Menge, deren Produkt mit 1 bezeichnet wird. Es gibt 2 ⁿ mögliche Zhegalkin-Monome in n Variablen, da jedes Monom durch die vollständig spezifiziert ist Vorhandensein oder Nichtvorhandensein jeder Variablen. Ein Zhegalkin-Polynom ist die Summe (exklusiv-oder) einer Menge von Zhegalkin-Monomen, wobei die leere Menge mit 0 bezeichnet ist. Die Anwesenheit oder Abwesenheit eines gegebenen Monoms in einem Polynom entspricht dem Koeffizienten dieses Monoms von 1 bzw. 0. Die linear unabhängigen Zhegalkin-Monome überspannen einen 2 ^n- dimensionalen Vektorraum über dem Galois-Feld GF (2) (NB: nicht GF (2 ⁿ ), dessen Multiplikation sehr unterschiedlich ist). Die 2 ^{2 n} Vektoren dieses Raumes, dh die linearen Kombinationen dieser Monome als Einheitsvektoren, bilden die Zhegalkin-Polynome. Die genaue Übereinstimmung mit der Anzahl der Booleschen Operationen für n Variablen, die die n- fachen Operationen für {0,1} erschöpfen , liefert ein direktes Zählargument für die Vollständigkeit der Zhegalkin-Polynome als Boolesche Basis.

Dieser Vektorraum entspricht nicht der freien Booleschen Algebra auf n Generatoren, da ihm die Komplementation (bitweise logische Negation) als Operation fehlt (äquivalent, weil ihm das oberste Element als Konstante fehlt). Dies bedeutet nicht, dass der Raum nicht unter Komplementierung geschlossen ist oder oben (der All-One-Vektor ) als Element fehlt , sondern dass die linearen Transformationen dieses und ähnlich konstruierter Räume Komplement und Oberseite nicht bewahren müssen. Diejenigen, die sie bewahren, entsprechen den Booleschen Homomorphismen, z. B. gibt es vier lineare Transformationen vom Vektorraum der Zhegalkin-Polynome über eine Variable zu dem über keine, von denen nur zwei Boolesche Homomorphismen sind.

Berechnungsmethode

Es gibt verschiedene bekannte Methoden, die allgemein zur Berechnung des Zhegalkin-Polynoms verwendet werden:

• Verwendung der Methode unbestimmter Koeffizienten
• Durch die Konstruktion der kanonischen disjunktiven Normalform
• Durch die Verwendung von Tabellen
• Pascal-Methode
• Summationsmethode
• Verwenden einer Karnaugh-Karte

Die Methode der unbestimmten Koeffizienten

Unter Verwendung der Methode unbestimmter Koeffizienten wird ein lineares System erzeugt, das aus allen Tupeln der Funktion und ihren Werten besteht. Das Lösen des linearen Systems ergibt die Koeffizienten des Zhegalkin-Polynoms.

Beispiel

Drücken Sie die Boolesche Funktion als Zhegalkin-Polynom aus. Diese Funktion kann als Spaltenvektor ausgedrückt werden ${\ displaystyle f (A, B, C) = {\ bar {A}} {\ bar {B}} {\ bar {C}} + {\ bar {A}} B {\ bar {C}} + A {\ bar {B}} {\ bar {C}} + ABC}$

${\ displaystyle {\ vec {f}} = {\ begin {pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \ end {pmatrix}}}$ .

Dieser Vektor sollte die Ausgabe der Linksmultiplikation eines Vektors unbestimmter Koeffizienten sein

${\ displaystyle {\ vec {c}} = {\ begin {pmatrix} c_ {0} \\ c_ {1} \\ c_ {2} \\ c_ {3} \\ c_ {4} \\ c_ {5 } \\ c_ {6} \\ c_ {7} \ end {pmatrix}}}$

durch eine logische 8x8- Matrix, die die möglichen Werte darstellt, die alle möglichen Konjunktionen von A, B, C annehmen können. Diese möglichen Werte sind in der folgenden Wahrheitstabelle angegeben:

${\ displaystyle {\ begin {array} {| c | c | c | c | c | c | c | c | c | c | c |} A & B & C & \; \; \; \; \; \; \; ; \; & 1 & C & B & BC & A & AC & AB & ABC \\\ hline 0 0 0 && 1 0 0 0 0 0 0 0 \\ 0 0 1 && 1 & 1 & 0 0 0 0 0 0 \\ 0 & 1 & 0 && 1 0 & 1 & 0 0 0 0 0 \\ 0 & 1 & 1 && 1 & 1 & 1 & 1 & 0 0 0 0 \\ 1 0 0 && 1 0 0 0 1 0 0 0 \\ 1, 0 & 1 && 1 & 1 & 0 0 & 1 & 1 & 0 0 \\ 1 & 1 & 0 && 1 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 && 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \ end {array}}}$ .

Die Informationen in der obigen Wahrheitstabelle können in der folgenden logischen Matrix codiert werden:

${\ Display S_ {3} = {\ begin {pmatrix} 1 0 0 0 0 0 0 0 \\ 1 & 1 & 0 0 0 0 0 0 \\ 1, 0 & 1 & 0 0 0 0 0 \\ 1 & 1 & 1 & 1 & 0 0 0 0 \\ 1 0 0 0 1 0 0 0 \\ 1 & 1 & 0 0 & 1 & 1 & 0 0 \\ 1, 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \ end {pmatrix}}}$

wobei das 'S' hier für "Sierpiński" steht, wie im Sierpiński-Dreieck , und der Index 3 die Exponenten seiner Größe angibt : . ${\ displaystyle 2 ^ {3} \ times 2 ^ {3}}$

Durch mathematische Induktion und Blockmatrixmultiplikation kann bewiesen werden, dass jede solche "Sierpiński-Matrix" ihre eigene Umkehrung ist. ${\ displaystyle S_ {n}}$

Dann ist das lineare System

${\ displaystyle S_ {3} {\ vec {c}} = {\ vec {f}}}$

was gelöst werden kann für : ${\ displaystyle {\ vec {c}}}$

${\ displaystyle {\ vec {c}} = S_ {3} ^ {- 1} {\ vec {f}} = S_ {3} {\ vec {f}} = {\ begin {pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 \ 1 \ end {pmatrix}} = {\ begin {pmatrix} 1 \\ 1 \\ 1 \ oplus 1 \\ 1 \ oplus 1 \\ 1 \ oplus 1 \\ 1 \ oplus 1 \\ 1 \ oplus 1 \ oplus 1 \\ 1 \ oplus 1 \ oplus 1 \ oplus 1 \ end {pmatrix}} = {\ begin {pmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \ end {pmatrix}}}$ ,

und das entsprechende Zhegalkin-Polynom ist . ${\ displaystyle {\ vec {c}}}$${\ displaystyle 1 \ oplus C \ oplus AB}$

Verwendung der kanonischen disjunktiven Normalform

Mit dieser Methode wird zuerst die kanonische disjunktive Normalform (eine vollständig erweiterte disjunktive Normalform ) berechnet. Dann werden die Negationen in diesem Ausdruck durch einen äquivalenten Ausdruck unter Verwendung der Mod 2-Summe der Variablen und 1 ersetzt. Die Disjunktionszeichen werden in Additionsmod 2 geändert, die Klammern werden geöffnet und der resultierende Boolesche Ausdruck wird vereinfacht. Diese Vereinfachung führt zum Zhegalkin-Polynom.

Tabellen verwenden

Berechnung des Zhegalkin-Polynoms für eine Beispielfunktion P nach der Tabellenmethode

Sei die Ausgabe einer Wahrheitstabelle für die Funktion P von n Variablen, so dass der Index der 's der binären Indizierung der Intervalle entspricht . Definieren Sie eine Funktion ζ rekursiv durch: ${\ displaystyle c_ {0}, ..., c_ {2 ^ {n} -1}}$${\ displaystyle c_ {i}}$

${\ displaystyle \ zeta (c_ {i}): = c_ {i}}$

${\ displaystyle \ zeta (c_ {0}, ..., c_ {k}): = \ zeta (c_ {0}, ..., c_ {k-1}) \ oplus \ zeta (c_ {1} , ..., c_ {k})}$ .

Beachten Sie, dass

${\ displaystyle \ zeta (c_ {0}, ..., c_ {m}) = \ bigoplus _ {k = 0} ^ {m} {m \ wähle k} _ {2} c_ {k}}$

wo ist der Binomialkoeffizient modulo 2 reduziert . ${\ displaystyle {m \ wähle k} _ {2}}$

Dann

${\ displaystyle g_ {i} = \ zeta (c_ {0}, ..., c_ {i})}$

ist der i- ^te Koeffizient eines Zhegalkin-Polynoms, dessen Literale im i- ^ten Monom dieselben sind wie die Literale im i- ^ten Intervall, außer dass die negativen Literale entfernt (oder durch 1 ersetzt) ​​werden.

Die ζ-Transformation ist ihre eigene Umkehrung, so dass dieselbe Art von Tabelle verwendet werden kann, um die Koeffizienten unter Berücksichtigung der Koeffizienten zu berechnen . Lass einfach ${\ displaystyle c_ {0}, ..., c_ {2 ^ {n} -1}}$${\ displaystyle g_ {0}, ..., g_ {2 ^ {n} -1}}$

${\ displaystyle c_ {i} = \ zeta (g_ {0}, ..., g_ {i})}$ .

Kopieren Sie in Bezug auf die Tabelle in der Abbildung die Ausgaben der Wahrheitstabelle (in der mit P bezeichneten Spalte ) in die Spalte ganz links in der Dreieckstabelle. Berechnen Sie dann nacheinander Spalten von links nach rechts, indem Sie XOR auf jedes Paar vertikal benachbarter Zellen anwenden, um die Zelle unmittelbar rechts von der oberen Zelle jedes Paares zu füllen. Wenn die gesamte dreieckige Tabelle ausgefüllt ist, liest die obere Zeile die Koeffizienten einer linearen Kombination aus, die bei Vereinfachung (Entfernen der Nullen) das Zhegalkin-Polynom ergibt.

Um von einem Zhegalkin-Polynom zu einer Wahrheitstabelle zu gelangen, können Sie die obere Reihe der Dreieckstabelle mit den Koeffizienten des Zhegalkin-Polynoms ausfüllen (wobei Sie für alle Kombinationen positiver Literale, die nicht im Polynom enthalten sind, Nullen eingeben). Berechnen Sie dann nacheinander die Zeilen von oben nach unten, indem Sie XOR auf jedes Paar horizontal benachbarter Zellen anwenden, um die Zelle unmittelbar bis zum unteren Rand der Zelle ganz links in jedem Paar zu füllen. Wenn die gesamte dreieckige Tabelle gefüllt ist, kann die Spalte ganz links in die Spalte P der Wahrheitstabelle kopiert werden .

Beachten Sie im Übrigen, dass diese Berechnungsmethode der Funktionsweise des elementaren zellularen Automaten mit der Bezeichnung Regel 102 entspricht . Starten Sie beispielsweise einen solchen zellularen Automaten mit acht Zellen, die mit den Ausgaben der Wahrheitstabelle (oder den Koeffizienten der kanonischen disjunktiven Normalform) des Booleschen Ausdrucks 10101001 eingerichtet wurden. Führen Sie dann den zellularen Automaten sieben weitere Generationen lang aus, während Sie a beibehalten Aufzeichnung des Zustands der Zelle ganz links. Die Geschichte dieser Zelle stellt sich dann wie folgt heraus: 11000010, was die Koeffizienten des entsprechenden Zhegalkin-Polynoms zeigt.

Die Pascal-Methode

Verwenden der Pascal-Methode zur Berechnung des Zhegalkin-Polynoms für die Boolesche Funktion . Die Zeile in russischer Sprache unten lautet: - bitweise Operation "Exklusiv ODER" ${\ displaystyle {\ bar {a}} {\ bar {b}} {\ bar {c}} + {\ bar {a}} b {\ bar {c}} + {\ bar {a}} bc + ab {\ bar {c}}}$
${\ displaystyle \ oplus}$

Das wirtschaftlichste und zweckmäßigste Verfahren zur manuellen Konstruktion des Zhegalkin-Polynoms ist die Pascal-Methode.

Wir erstellen eine Tabelle, die aus Spalten und Zeilen besteht, wobei N die Anzahl der Variablen in der Funktion ist. In der oberen Zeile der Tabelle platzieren wir den Vektor der Funktionswerte, dh die letzte Spalte der Wahrheitstabelle. ${\ displaystyle 2 ^ {N}}$${\ displaystyle N + 1}$

Jede Zeile der resultierenden Tabelle ist in Blöcke unterteilt (schwarze Linien in der Abbildung). In der ersten Zeile belegt der Block eine Zelle, in der zweiten Zeile zwei, in der dritten vier, in der vierten acht und so weiter. Jeder Block in einer bestimmten Zeile, den wir "unteren Block" nennen, entspricht immer genau zwei Blöcken in der vorherigen Zeile. Wir werden sie "linker oberer Block" und "rechter oberer Block" nennen.

Der Bau beginnt in der zweiten Zeile. Der Inhalt der linken oberen Blöcke wird unverändert in die entsprechenden Zellen des unteren Blocks übertragen (grüne Pfeile in der Abbildung). Dann wird die Operation "Addition Modulo Zwei" bitweise über den rechten oberen und linken oberen Block ausgeführt und das Ergebnis auf die entsprechenden Zellen auf der rechten Seite des unteren Blocks übertragen (rote Pfeile in der Figur). Diese Operation wird mit allen Zeilen von oben nach unten und mit allen Blöcken in jeder Zeile ausgeführt. Nach Abschluss der Konstruktion enthält die untere Zeile eine Folge von Zahlen, die die Koeffizienten des Zhegalkin-Polynoms sind und in derselben Reihenfolge wie bei der oben beschriebenen Dreiecksmethode geschrieben wurden.

Die Summationsmethode

Grafische Darstellung der Koeffizienten des Zhegalkin-Polynoms für Funktionen mit unterschiedlicher Anzahl von Variablen.

Nach der Wahrheitstabelle ist es einfach, die einzelnen Koeffizienten des Zhegalkin-Polynoms zu berechnen. Fassen Sie dazu Modulo 2 die Werte der Funktion in den Zeilen der Wahrheitstabelle zusammen, in denen Variablen, die nicht in der Konjunktion stehen (die dem berechneten Koeffizienten entspricht), Nullwerte annehmen.

Nehmen wir zum Beispiel an, wir müssen den Koeffizienten der xz- Konjunktion für die Funktion von drei Variablen finden . In dieser Konjunktion gibt es keine Variable y . Suchen Sie die Eingabesätze, in denen die Variable y einen Nullwert annimmt. Dies sind die Sätze 0, 1, 4, 5 (000, 001, 100, 101). Dann wird der Koeffizient in Verbindung xz ist ${\ displaystyle f (x, y, z)}$

${\ displaystyle a_ {5} = f_ {0} \ oplus f_ {1} \ oplus f_ {4} \ oplus f_ {5} = f (0,0,0) \ oplus f (0,0,1) \ oplus f (1,0,0) \ oplus f (1,0,1)}$

Da es keine Variablen mit dem konstanten Term gibt,

${\ displaystyle a_ {0} = f_ {0}}$ .

Für einen Term, der alle Variablen enthält, enthält die Summe alle Werte der Funktion:

${\ displaystyle a_ {N-1} = f_ {0} \ oplus f_ {1} \ oplus f_ {2} \ oplus ... \ oplus f_ {N-2} \ oplus f_ {N-1}}$

Stellen wir die Koeffizienten des Zhegalkin-Polynoms grafisch als Summen modulo 2 von Funktionswerten an bestimmten Punkten dar. Dazu konstruieren wir eine quadratische Tabelle, in der jede Spalte den Wert der Funktion an einem der Punkte darstellt und die Zeile der Koeffizient des Zhegalkin-Polynoms ist. Der Punkt am Schnittpunkt einer Spalte und einer Zeile bedeutet, dass der Wert der Funktion an diesem Punkt in der Summe für den angegebenen Koeffizienten des Polynoms enthalten ist (siehe Abbildung). Wir nennen diese Tabelle , wobei N die Anzahl der Variablen der Funktion ist. ${\ displaystyle T_ {N}}$

Es gibt ein Muster, mit dem Sie eine Tabelle für eine Funktion von N Variablen erhalten können, die eine Tabelle für eine Funktion von Variablen enthält. Die neue Tabelle ist als 2 × 2- Tabellenmatrix angeordnet, und der rechte obere Block der Matrix wird gelöscht. ${\ displaystyle N-1}$${\ displaystyle T_ {N} +1}$${\ displaystyle T_ {N}}$

Gittertheoretische Interpretation

Betrachten Sie die Spalten einer Tabelle als Elemente eines Booleschen Gitters der Größe entsprechend . Drücken Sie für jede Spalte die Zahl M als Binärzahl aus , dann genau dann , wenn , wobei bitweises ODER bedeutet. ${\ displaystyle T_ {N}}$${\ displaystyle 2 ^ {N}}$${\ displaystyle f_ {M}}$${\ displaystyle M_ {2}}$${\ displaystyle f_ {M} \ leq f_ {K}}$${\ displaystyle M_ {2} \ vee K_ {2} = K_ {2}}$${\ displaystyle \ vee}$

Wenn die Tabellenzeilen von oben nach unten mit den Zahlen von 0 bis nummeriert sind , ist der tabellarische Inhalt der Zeilennummer R das Ideal, das durch das Element des Gitters erzeugt wird . ${\ displaystyle T_ {N}}$${\ displaystyle 2 ^ {N} -1}$${\ displaystyle f_ {R}}$

Beachten Sie im Übrigen, dass das Gesamtmuster einer Tabelle das eines Sierpiński-Dreiecks mit logischer Matrix ist . Das Muster entspricht auch einem elementaren zellularen Automaten namens Regel 60 , beginnend mit der Zelle ganz links auf 1 gesetzt und alle anderen Zellen gelöscht. ${\ displaystyle T_ {N}}$

Verwenden einer Karnaugh-Karte

Konvertieren einer Karnaugh-Karte in ein Zhegalkin-Polynom.

Die Abbildung zeigt eine Funktion von drei Variablen, P ( A , B , C ), dargestellt als Karnaugh-Karte , die der Leser als Beispiel für die Umwandlung solcher Karten in Zhegalkin-Polynome betrachten kann. Das allgemeine Verfahren wird in den folgenden Schritten beschrieben:

• Wir betrachten alle Zellen der Karnaugh-Karte in aufsteigender Reihenfolge der Anzahl der Einheiten in ihren Codes. Für die Funktion von drei Variablen beträgt die Zellsequenz 000–100–010–001–110–101–011–111. Jede Zelle der Karnaugh-Karte ist abhängig von den Positionen des Codes, in dem sich solche befinden, einem Mitglied des Zhegalkin-Polynoms zugeordnet. Beispielsweise entspricht die Zelle 111 dem Element ABC, die Zelle 101 dem Element AC, die Zelle 010 dem Element B und die Zelle 000 dem Element 1.
• Wenn die betreffende Zelle 0 ist, fahren Sie mit der nächsten Zelle fort.
• Wenn die fragliche Zelle 1 ist, fügen Sie den entsprechenden Term zum Zhegalkin-Polynom hinzu, invertieren Sie dann alle Zellen in der Karnaugh-Karte, in denen dieser Term 1 ist (oder zu dem durch diesen Term erzeugten Ideal gehört , in einem Booleschen Gitter aus Monomen) und gehen Sie zur nächsten Zelle. Wenn zum Beispiel bei der Untersuchung der Zelle 110 eine Eins darin erscheint, wird der Term AB zum Zhegalkin-Polynom hinzugefügt und alle Zellen der Karnaugh-Karte werden invertiert, für die A = 1 und B = 1. Wenn die Einheit in ist Zelle 000, dann wird dem Zhegalkin-Polynom ein Term 1 hinzugefügt und die gesamte Karnaugh-Karte wird invertiert.
• Der Transformationsprozess kann als abgeschlossen betrachtet werden, wenn nach der nächsten Inversion alle Zellen der Karnaugh-Karte Null werden oder es sich nicht um eine Bedingung handelt.

Möbius-Transformation

Die Möbius-Inversionsformel bezieht die Koeffizienten eines Booleschen Ausdrucks der Mintersummenausdrücke und eines Zhegalkin-Polynoms in Beziehung. Dies ist die Teilordnungsversion der Möbius-Formel, nicht die Zahlentheorie. Die Möbius-Inversionsformel für Teilordnungen lautet:

${\ displaystyle g (x) = \ sum _ {y: y \ leq x} f (y) \ linker rechter Pfeil f (x) = \ sum _ {y: y \ leq x} g (y) \ mu (y, x)}$ ,

wo , | x | Dies ist der Hamming-Abstand von x von 0. Da in der Zhegalkin-Algebra die Möbius-Funktion auf die Konstante 1 zusammenfällt. ${\ displaystyle \ mu (y, x) = (- 1) ^ {| x | - | y |}}$${\ displaystyle -1 \ equiv 1}$

Der Satz von Teilern einer gegebenen Anzahl x ist auch die Reihenfolge ideal durch diese Nummer generiert: . Da die Summation Modulo 2 ist, kann die Formel wie folgt angepasst werden ${\ displaystyle \ langle x \ rangle}$

${\ displaystyle g (x) = \ bigoplus _ {y: y \ in \ langle x \ rangle} f (y) \ leftrightarrow f (x) = \ bigoplus _ {y: y \ in \ langle x \ rangle} g (y)}$

Beispiel

Betrachten Sie als Beispiel den Fall mit drei Variablen. Die folgende Tabelle zeigt die Teilbarkeitsrelation:

Dann

${\ displaystyle g (000) = f (000)}$

${\ displaystyle g (001) = f (000) \ oplus f (001)}$

${\ displaystyle g (010) = f (000) \ oplus f (010)}$

${\ displaystyle g (011) = f (000) \ oplus f (001) \ oplus f (010) \ oplus f (011)}$

${\ displaystyle g (100) = f (000) \ oplus f (100)}$

${\ displaystyle g (101) = f (000) \ oplus f (001) \ oplus f (100) \ oplus (101)}$

${\ displaystyle g (110) = f (000) \ oplus f (010) \ oplus f (100) \ oplus f (110)}$

${\ displaystyle g (111) = f (000) \ oplus f (001) \ oplus f (010) \ oplus f (011) \ oplus f (100) \ oplus f (101) \ oplus f (110) \ oplus f (111)}$

Das obige Gleichungssystem kann für f gelöst werden , und das Ergebnis kann so zusammengefasst werden, dass es durch Austausch von g und f im gesamten obigen System erhältlich ist.

Die folgende Tabelle zeigt die Binärzahlen zusammen mit den zugehörigen Zhegalkin-Monomen und Booleschen Intervallen:

Boolescher Minterm	ABC	Zhegalkin-Monom
${\ displaystyle {\ bar {A}} {\ bar {B}} {\ bar {C}}}$	000	1
${\ displaystyle {\ bar {A}} {\ bar {B}} C}$	001	C.
${\ displaystyle {\ bar {A}} B {\ bar {C}}}$	010	B.
${\ displaystyle {\ bar {A}} BC}$	011	BC
${\ displaystyle A {\ bar {B}} {\ bar {C}}}$	100	EIN
${\ displaystyle A {\ bar {B}} C}$	101	AC
${\ displaystyle AB {\ bar {C}}}$	110	AB
${\ displaystyle ABC}$	111	ABC

Die Zhegalkin-Monome sind natürlich nach Teilbarkeit geordnet, während sich die Booleschen Intervalle nicht so natürlich selbst ordnen. Jedes repräsentiert ein exklusives Achtel des Venn-Diagramms mit drei Variablen . Die Reihenfolge der Monome wird wie folgt auf die Bitfolgen übertragen: gegeben und dann ein Paar Bittripletts . ${\ displaystyle a_ {1} a_ {2} a_ {3}}$${\ displaystyle b_ {1} b_ {2} b_ {3}}$${\ displaystyle a_ {1} a_ {2} a_ {3} \ leq b_ {1} b_ {2} b_ {3} \ leftrightarrow a_ {1} \ leq b_ {1} \ wedge a_ {2} \ leq b_ {2} \ wedge a_ {3} \ leq b_ {3}}$

Die Entsprechung zwischen einer dreivariablen Booleschen Summe von Intervallen und einem Zhegalkin-Polynom lautet dann:

${\ displaystyle f (000) {\ bar {A}} {\ bar {B}} {\ bar {C}} \ vee f (001) {\ bar {A}} {\ bar {B}} C \ vee f (010) {\ bar {A}} B {\ bar {C}} \ vee f (011) {\ bar {A}} BC \ vee f (100) A {\ bar {B}} {\ Balken {C}} \ vee f (101) A {\ bar {B}} C \ vee f (110) AB {\ bar {C}} \ vee f (111) ABC}$

${\ displaystyle \ qquad \ qquad \ equiv g (000) \ oplus g (001) C \ oplus g (010) B \ oplus g (011) BC \ oplus g (100) A \ oplus g (101) AC \ oplus g (110) AB \ oplus g (111) ABC}$ .

Das obige Gleichungssystem kann als logische Matrixgleichung zusammengefasst werden:

${\ displaystyle {\ begin {pmatrix} g (000) \\ g (001) \\ g (010) \\ g (011) \\ g (100) \\ g (101) \\ g (110) \ \ g (111) \ end {pmatrix}} = {\ begin {pmatrix} 1 && 0 && 0 && 0 && 0 && 0 && 0 && 0 \\ 1 && 1 && 0 && 0 && 0 && 0 && 0 && 0 \\ 1 && 0 && 1 && 0 && 0 && 0 && 0 && 0 \\ 1 && 1 && 1 && 1 && 0 && 0 && 0 && 0 \\ 1 && 0 && 0 && 0 && 1 && 0 && 0 && 0 \\ 1 && 1 && 0 && 0 && 1 && 1 && 0 && 0 \\ 1 && 0 && 1 && 0 && 1 && 0 && 1 && 0 \\ 1 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \ end {pmatrix}} {\ begin { pmatrix} f (000) \\ f (001) \\ f (010) \\ f (011) \\ f (100) \\ f (101) \\ f (110) \\ f (111) \ end {pmatrix}}}$

was NJ Wildberger eine Boole-Möbius-Transformation nennt.

Unten ist die Form der XOR- Tabelle der Transformation in Richtung von g nach f dargestellt :

${\ displaystyle f_ {000}}$	${\ displaystyle f_ {001}}$	${\ displaystyle f_ {010}}$	${\ displaystyle f_ {011}}$	${\ displaystyle f_ {100}}$	${\ displaystyle f_ {101}}$	${\ displaystyle f_ {110}}$	${\ displaystyle f_ {111}}$
${\ displaystyle g_ {000}}$	${\ displaystyle g_ {000} \ oplus g_ {001}}$	${\ displaystyle g_ {000} \ oplus g_ {010}}$	${\ displaystyle g_ {000} \ oplus g_ {010} \ oplus g_ {001} \ oplus g_ {011}}$	${\ displaystyle g_ {000} \ oplus g_ {100}}$	${\ displaystyle g_ {000} \ oplus g_ {100} \ oplus g_ {001} \ oplus g_ {101}}$	${\ displaystyle g_ {000} \ oplus g_ {100} \ oplus g_ {010} \ oplus g_ {110}}$	${\ displaystyle g_ {000} \ oplus g_ {100} \ oplus g_ {010} \ oplus g_ {110} \ oplus g_ {001} \ oplus g_ {101} \ oplus g_ {011} \ oplus g_ {111}}$
${\ displaystyle g_ {001}}$	${\ displaystyle g_ {001} \ oplus g_ {010}}$	${\ displaystyle g_ {001} \ oplus g_ {011}}$	${\ displaystyle g_ {001} \ oplus g_ {011} \ oplus g_ {010} \ oplus g_ {100}}$	${\ displaystyle g_ {001} \ oplus g_ {101}}$	${\ displaystyle g_ {001} \ oplus g_ {101} \ oplus g_ {010} \ oplus g_ {110}}$	${\ displaystyle g_ {001} \ oplus g_ {101} \ oplus g_ {011} \ oplus g_ {111}}$
${\ displaystyle g_ {010}}$	${\ displaystyle g_ {010} \ oplus g_ {011}}$	${\ displaystyle g_ {010} \ oplus g_ {100}}$	${\ displaystyle g_ {010} \ oplus g_ {100} \ oplus g_ {011} \ oplus g_ {101}}$	${\ displaystyle g_ {010} \ oplus g_ {110}}$	${\ displaystyle g_ {010} \ oplus g_ {110} \ oplus g_ {011} \ oplus g_ {111}}$
${\ displaystyle g_ {011}}$	${\ displaystyle g_ {011} \ oplus g_ {100}}$	${\ displaystyle g_ {011} \ oplus g_ {101}}$	${\ displaystyle g_ {011} \ oplus g_ {101} \ oplus g_ {100} \ oplus g_ {110}}$	${\ displaystyle g_ {011} \ oplus g_ {111}}$
${\ displaystyle g_ {100}}$	${\ displaystyle g_ {100} \ oplus g_ {101}}$	${\ displaystyle g_ {100} \ oplus g_ {110}}$	${\ displaystyle g_ {100} \ oplus g_ {110} \ oplus g_ {101} \ oplus g_ {111}}$
${\ displaystyle g_ {101}}$	${\ displaystyle g_ {101} \ oplus g_ {110}}$	${\ displaystyle g_ {101} \ oplus g_ {111}}$
${\ displaystyle g_ {110}}$	${\ displaystyle g_ {110} \ oplus g_ {111}}$
${\ displaystyle g_ {111}}$

Verwandte Arbeiten

1927, im selben Jahr wie Zhegalkins Arbeit, veröffentlichte der amerikanische Mathematiker Eric Temple Bell eine ausgefeilte Arithmetisierung der Booleschen Algebra auf der Grundlage von Richard Dedekinds idealer Theorie und allgemeiner modularer Arithmetik (im Gegensatz zur arithmetischen Mod 2). Der viel einfachere arithmetische Charakter von Zhegalkin-Polynomen wurde erstmals im Westen (unabhängig davon, dass die Kommunikation zwischen sowjetischen und westlichen Mathematikern in dieser Zeit sehr begrenzt war) 1936 vom amerikanischen Mathematiker Marshall Stone bemerkt, als er beim Schreiben seines berühmten Stone-Dualitätssatzes feststellte, dass Die vermeintlich lockere Analogie zwischen Booleschen Algebren und Ringen könnte tatsächlich als exakte Äquivalenz für endliche und unendliche Algebren formuliert werden, was ihn dazu veranlasst, seine Arbeit in den nächsten Jahren grundlegend neu zu organisieren.

Siehe auch

• Algebraische Normalform (ANF)
• Ring Summe Normalform (RSNF)
• Reed-Muller-Erweiterung
• Boolesche Domäne
• Boolesche Funktion

Anmerkungen

Verweise

Weiterführende Literatur

• Gindikin [Гиндикин], Semen Grigorʹevich [Семен Г.] (1972). алгебра логики в задачах [ Algebraische Logik ] (auf Russisch) (1. Aufl.). Moskau, Russland: Наука [Nauka] . ISBN   0-387-96179-8 . (288 Seiten) (NB. Übersetzung: Springer-Verlag , 1985. [1] )
• Perkowski, Marek A.; Grygiel, Stanislaw (1995-11-20). "6. Historischer Überblick über die Zersetzungsforschung". Ein Überblick über die Literatur zur Funktionszerlegung . Version IV. Functional Decomposition Group, Fakultät für Elektrotechnik, Portland University, Portland, Oregon, USA. S. 21–22. CiteSeerX   10.1.1.64.1129 . (188 Seiten)