Zhegalkin polynom

Zhegalkin (även Žegalkin , Gégalkin eller Shegalkin ) polynom ( ryska : полиномы Жегалкина ), även känd som algebraisk normalform , är en representation av funktioner i boolesk algebra . Introducerade av den ryske matematikern Ivan Ivanovich Zhegalkin 1927, de är polynomringen över heltalen modulo 2 . De resulterande degenerationerna av modulär aritmetik resulterar i att Zhegalkin-polynom är enklare än vanliga polynom och kräver varken koefficienter eller exponenter. Koefficienter är redundanta eftersom 1 är den enda koefficienten som inte är noll. Exponenter är redundanta eftersom i aritmetik mod 2, x ² = x . Därför är ett polynom som 3 x ² y ⁵ z kongruent med, och kan därför skrivas om som, xyz .

Boolesk motsvarighet

Före 1927 hade boolesk algebra ansetts vara en kalkyl av logiska värden med logiska operationer av konjunktion , disjunktion , negation och så vidare. Zhegalkin visade att alla booleska operationer kunde skrivas som vanliga numeriska polynom, representerande de falska och sanna värdena som 0 och 1, heltal mod 2. Logisk konjunktion skrivs som xy , och logisk exklusiv - eller som aritmetisk addition mod 2, (skriven här som x ⊕ y för att undvika förväxling med den vanliga användningen av + som synonym för inklusive-eller ∨). Det logiska komplementet ¬ x är då x ⊕1. Eftersom ∧ och ¬ utgör en grund för boolesk algebra, är alla andra logiska operationer sammansättningar av dessa grundläggande operationer, och därför kan polynomen i vanlig algebra representera alla booleska operationer, vilket gör att boolesk resonemang kan utföras med hjälp av elementär algebra .

skrivs den booleska 2-av-3-tröskeln eller medianoperationen som Zhegalkin-polynomet xy ⊕ yz ⊕ zx .

Formella egenskaper

Formellt är en Zhegalkin-monomal produkten av en ändlig uppsättning distinkta variabler (därav kvadratfri ), inklusive den tomma mängden vars produkt betecknas 1. Det finns 2 ⁿ möjliga Zhegalkin-monomialer i n variabler, eftersom varje monomial är helt specificerad av närvaro eller frånvaro av varje variabel. Ett Zhegalkin-polynom är summan (exklusiv-eller) av en uppsättning Zhegalkin-monomer, med den tomma mängden betecknad med 0. En given monomials närvaro eller frånvaro i ett polynom motsvarar att monomiets koefficient är 1 respektive 0. Zhegalkin-monomialerna, som är linjärt oberoende , spänner över ett 2 ⁿ -dimensionellt vektorutrymme över Galois-fältet GF (2) (OBS: inte GF (2 ⁿ ), vars multiplikation är helt annorlunda). De 2 ^{2 n} vektorerna i detta utrymme, dvs de linjära kombinationerna av dessa monomial som enhetsvektorer, utgör Zhegalkin-polynomen. Den exakta överensstämmelsen med antalet booleska operationer på n variabler, som tar ut de n -ära operationerna på {0,1}, ger ett direkt räkneargument för att Zhegalkinpolynomen är fullständiga som en boolesk grund.

Detta vektorutrymme är inte ekvivalent med den fria booleska algebra på n generatorer eftersom den saknar komplementering (bitvis logisk negation) som en operation (likväl eftersom den saknar det översta elementet som en konstant). Detta betyder inte att utrymmet inte är stängt under komplement eller saknar topp ( all-one-vektorn ) som ett element, utan snarare att de linjära transformationerna av detta och liknande konstruerade utrymmen inte behöver bevara komplement och topp. De som bevarar dem motsvarar de booleska homomorfismerna, t.ex. finns det fyra linjära transformationer från vektorrymden för Zhegalkin-polynom över en variabel till den över ingen, varav endast två är booleska homomorfismer.

Beräkningsmetod

Det finns olika kända metoder som vanligtvis används för beräkning av Zhegalkin-polynomet:

• Med hjälp av metoden för obestämda koefficienter
• Genom att konstruera den kanoniska disjunktiva normalformen
• Genom att använda tabeller
• Pascal metod
• Summeringsmetod
• Använda en Karnaugh-karta

Metoden för obestämda koefficienter

Med metoden för obestämda koefficienter genereras ett linjärt system som består av alla tuplar av funktionen och deras värden. Att lösa det linjära systemet ger koefficienterna för Zhegalkinpolynomet.

Exempel

Givet den booleska funktionen $f(A,B,C)={\bar {A}}{\bar {B}}{\bar {C}}+{\bar {A}}B{\bar {C}}+A{\bar {B}}{\bar {C}} +ABC$ , uttryck det som ett Zhegalkin-polynom. Denna funktion kan uttryckas som en kolumnvektor

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

Denna vektor bör vara resultatet av vänstermultiplicering av en vektor med obestämda koefficienter

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

av en 8x8 logisk matris som representerar de möjliga värden som alla möjliga konjunktioner av A, B, C kan ta. Dessa möjliga värden anges i följande sanningstabell:

${\begin{array}{|c|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}}$ .

Informationen i ovanstående sanningstabell kan kodas i följande logiska matris:

$0&0&0&0\&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&1&0&0\\1&0&1&0&1&0&1&0\\\1&1&1&p&1}&1}&1&1&1&1&1}&1}$

där 'S' här står för "Sierpiński", som i Sierpiński triangel , och sänkt 3 ger exponenterna för dess storlek: $2^{3}\times 2^{3}$ .

Det kan bevisas genom matematisk induktion och blockmatrismultiplikation att varje sådan "Sierpiński-matris" $S_{n}$ är sin egen invers.

Då är det linjära systemet

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

som kan lösas för ${\vec {c}}$ :

${=S_{c}} ^{-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\\1&0&1&0&0&0&0&0\\\1&1&1&01&0&0&0&1&1&1&01&0&0&0 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}1\\0\\1\\0\\1\\\0\\0\\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}}$ ,

och Zhegalkin-polynomet som motsvarar ${\vec {c}}$ är $1\oplus C\oplus AB$ .

Använder den kanoniska disjunktiva normalformen

Med den här metoden beräknas den kanoniska disjunktiva normalformen (en helt expanderad disjunktiv normalform ) först. Sedan ersätts negationerna i detta uttryck av ett ekvivalent uttryck med mod 2 summan av variabeln och 1. Disjunktionstecknen ändras till addition mod 2, parenteserna öppnas och det resulterande booleska uttrycket förenklas. Denna förenkling resulterar i Zhegalkin-polynomet.

Använda tabeller

Beräknar Zhegalkin-polynomet för en exempelfunktion P med tabellmetoden

Låt $c_{0},...,c_{2^{n}-1}$ vara utdata från en sanningstabell för funktionen P av n variabler, så att indexet för $c_{i}$ 's motsvarar den binära indexeringen av mintermerna . Definiera en funktion ζ rekursivt genom att:

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

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

Anteckna det

$\zeta (c_{0},...,c_{m})=\bigoplus _{k= 0}^{m}{m \choose k}_{2}c_{k}$

där ${m \choose k}_{2}$ är binomialkoefficienten reducerad modulo 2.

Sedan

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

är den i: ^e koefficienten för ett Zhegalkin-polynom vars literaler i det i : ^te monomet är desamma som literalerna i den i: ^te mintermen, förutom att de negativa literalerna tas bort (eller ersätts med 1).

ζ-transformationen är sin egen invers, så samma typ av tabell kan användas för att beräkna koefficienterna $c_{0},...,c_{2^{n}-1}$ givet koefficienterna $g_{0},...,g_{2^{n}-1}$ . Bara låt

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

När det gäller tabellen i figuren, kopiera utdata från sanningstabellen (i kolumnen märkt P ) till kolumnen längst till vänster i den triangulära tabellen. Beräkna sedan successivt kolumner från vänster till höger genom att tillämpa XOR på varje par av vertikalt intilliggande celler för att fylla cellen omedelbart till höger om den översta cellen i varje par. När hela den triangulära tabellen är ifylld läser den översta raden ut koefficienterna för en linjär kombination som, när den förenklas (borttagning av nollorna), ger Zhegalkin-polynomet.

För att gå från ett Zhegalkinpolynom till en sanningstabell är det möjligt att fylla i den översta raden i den triangulära tabellen med koefficienterna för Zhegalkinpolynomet (att sätta in nollor för alla kombinationer av positiva bokstaver som inte finns i polynomet). Beräkna sedan successivt rader uppifrån och ned genom att applicera XOR på varje par av horisontellt intilliggande celler för att fylla cellen omedelbart till botten av cellen längst till vänster i varje par. När hela den triangulära tabellen är fylld kan kolumnen längst till vänster i den kopieras till kolumn P i sanningstabellen.

För övrigt, notera att denna beräkningsmetod motsvarar arbetsmetoden för den elementära cellulära automaten som kallas Regel 102 . Starta till exempel en sådan cellulär automat med åtta celler inställda med utdata från sanningstabellen (eller koefficienterna för den kanoniska disjunktiva normalformen) för det booleska uttrycket: 10101001. Kör sedan den cellulära automaten i ytterligare sju generationer samtidigt som en register över tillståndet för cellen längst till vänster. Historiken för denna cell visar sig då vara: 11000010, som visar koefficienterna för motsvarande Zhegalkin-polynom.

Pascalmetoden

Använder Pascal-metoden för att beräkna Zhegalkin-polynomet för den booleska funktionen ${\bar {a}}{\bar {b }}{\bar {c}}+{\bar {a}}b{\bar {c}}+{\bar {a}}bc+ab{\bar {c}}$ . Raden på ryska längst ner säger: $\oplus$ – bitvis operation "Exklusiv ELLER"

Den mest ekonomiska när det gäller mängden beräkning och ändamålsenlig för att konstruera Zhegalkin-polynomet manuellt är Pascal-metoden.

Vi bygger en tabell som består av $2^{N}$ kolumner och $N+1$ rader, där N är antalet variabler i funktionen. I den översta raden i tabellen placerar vi vektorn för funktionsvärden, det vill säga den sista kolumnen i sanningstabellen.

Varje rad i den resulterande tabellen är uppdelad i block (svarta linjer i figuren). I den första raden upptar blocket en cell, i den andra raden - två, i den tredje - fyra, i den fjärde - åtta och så vidare. Varje block i en viss rad, som vi kommer att kalla "nedre block", motsvarar alltid exakt två block i föregående rad. Vi kommer att kalla dem "vänster övre block" och "höger övre block".

Bygget startar från andra linjen. Innehållet i de vänstra övre blocken överförs utan förändring till motsvarande celler i det nedre blocket (gröna pilar i figuren). Därefter utförs operationen "addition modulo two" bitvis över de högra övre och vänstra övre blocken och resultatet överförs till motsvarande celler på höger sida av det nedre blocket (röda pilar i figuren). Denna operation utförs med alla linjer från topp till botten och med alla block i varje rad. Efter att konstruktionen är klar innehåller den nedersta raden en sträng av tal, som är koefficienterna för Zhegalkin-polynomet, skrivna i samma sekvens som i triangelmetoden som beskrivs ovan.

Summeringsmetoden

Grafisk representation av koefficienterna för Zhegalkinpolynomet för funktioner med olika antal variabler.

Enligt sanningstabellen är det lätt att beräkna de individuella koefficienterna för Zhegalkin-polynomet. För att göra detta, summera modulo 2 värdena för funktionen i de rader i sanningstabellen där variabler som inte är i konjunktionen (som motsvarar den koefficient som beräknas) tar nollvärden.

Antag till exempel att vi behöver hitta koefficienten för xz- konjunktionen för funktionen av tre variabler $f(x,y,z)$ . Det finns ingen variabel y i denna konjunktion. Hitta de indatamängder där variabeln y har ett nollvärde. Dessa är uppsättningarna 0, 1, 4, 5 (000, 001, 100, 101). är koefficienten vid konjunktion xz

$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)$

Eftersom det inte finns några variabler med den konstanta termen,

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

För en term som inkluderar alla variabler inkluderar summan alla värden för funktionen:

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

Låt oss grafiskt representera koefficienterna för Zhegalkinpolynomet som summor modulo 2 av värden på funktioner vid vissa punkter. För att göra detta konstruerar vi en kvadratisk tabell, där varje kolumn representerar värdet på funktionen vid en av punkterna, och raden är koefficienten för Zhegalkin-polynomet. Punkten i skärningspunkten mellan någon kolumn och rad betyder att värdet på funktionen vid denna punkt ingår i summan för den givna koefficienten för polynomet (se figur). Vi kallar denna tabell $T_{N}$ , där N är antalet variabler i funktionen.

Det finns ett mönster som låter dig få en tabell för en funktion av N variabler, med en tabell för en funktion av $N-1$ variabler. Den nya tabellen $T_{N}+1$ är arrangerad som en 2 × 2 matris av $T_{N}$ tabeller, och det övre högra blocket i matrisen rensas.

Gitterteoretisk tolkning

Betrakta kolumnerna i en tabell $T_{N}$ som motsvarande element i ett booleskt gitter med storleken $2^{N}$ . För varje kolumn $f_{M}$ uttrycker antalet M som ett binärt tal $M_{2}$ , sedan $f_{M}\leq f_{K}$ om och endast om $M_{2}\vee K_{2}=K_{2}$ , där $\vee$ anger bitvis ELLER.

Om raderna i tabell $T_{N}$ är numrerade, uppifrån och ned, med siffrorna från 0 till $2^{N}-1$ , då tabellinnehållet för radnummer R är idealet som genereras av elementet $f_{R}$ i gittret.

Notera för övrigt att det övergripande mönstret för en tabell $T_{N}$ är det för en logisk matris Sierpiński-triangel . Mönstret motsvarar också en elementär cellulär automat som kallas Regel 60 , som börjar med cellen längst till vänster inställd på 1 och alla andra celler rensade.

Använda en Karnaugh-karta

Konvertera en Karnaugh-karta till ett Zhegalkin-polynom.

Figuren visar en funktion av tre variabler, P ( A , B , C ) representerade som en Karnaugh-karta , som läsaren kan betrakta som ett exempel på hur man omvandlar sådana kartor till Zhegalkin-polynom; det allmänna förfarandet ges i följande steg:

• Vi betraktar alla celler på Karnaugh-kartan i stigande ordning efter antalet enheter i deras koder. För funktionen av tre variabler kommer cellsekvensen att vara 000–100–010–001–110–101–011–111. Varje cell på Karnaugh-kartan är associerad med en medlem av Zhegalkin-polynomet beroende på positionerna för koden där det finns sådana. Till exempel motsvarar cell 111 medlemmen ABC, cell 101 motsvarar medlemmen AC, cell 010 motsvarar medlemmen B och cell 000 motsvarar medlemmen 1.
• Om cellen i fråga är 0, gå till nästa cell.
• Om cellen i fråga är 1, lägg till motsvarande term till Zhegalkin-polynomet, invertera sedan alla celler i Karnaugh-kartan där denna term är 1 (eller tillhör idealet som genereras av denna term, i ett booleskt gitter av monomer) och gå till nästa cell. Till exempel, om, när man undersöker cell 110, en etta förekommer i den, läggs termen AB till Zhegalkin-polynomet och alla celler i Karnaugh-kartan inverteras, för vilka A = 1 och B = 1. Om enheten är i cell 000, sedan läggs en term 1 till Zhegalkin-polynomet och hela Karnaugh-kartan inverteras.
• Transformationsprocessen kan anses vara avslutad när, efter nästa inversion, alla celler i Karnaugh-kartan blir noll, eller ett tillstånd som inte bryr sig.

Möbiusförvandling

Möbius- inversionsformeln relaterar koefficienterna för ett booleskt sum-of-minterms-uttryck och ett Zhegalkin-polynom. Detta är den partiella ordningsversionen av Möbius-formeln, inte den talteoretiska. Möbius-inversionsformeln för partiella beställningar är:

$g(x)=\summa _{y :y\leq x}f(y)\leftrightarrow f(x)=\summa _{y:y\leq x}g(y)\mu (y,x)$ ,

där ${\displaystyle \mu (y,x)=(-1)^{|x|-|y|}} ,$ | x | är Hamming-avståndet för x från 0. Eftersom $-1\equiv 1$ i Zhegalkin-algebra, kollapsar Möbius-funktionen till att vara konstanten 1.

Mängden divisorer för ett givet tal x är också den ordningsideal som genereras av det talet: $\langle x\rangle$ . Eftersom summering är modulo 2 kan formeln räknas om som

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

Exempel

Som ett exempel, betrakta fallet med tre variabler. Följande tabell visar delbarhetsrelationen:

x	delare av x
000	000
001	000,001
010	000, 010
011	000, 001, 010, 011
100	000, 100
101	000, 001, 100, 101
110	000, 010, 100, 110
111	000, 001, 010, 011, 100, 101, 110, 111

Sedan

$g(000)=f(000)$

$g(001)=f(000)\oplus f(001)$

$g(010)=f(000)\oplus f(010)$

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

$=f(000)\oplus f(100)}$

$)$

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

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

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

Ovanstående ekvationssystem kan lösas för f , och resultatet kan sammanfattas som att det kan erhållas genom att byta ut g och f genom hela systemet ovan.

Tabellen nedan visar de binära talen tillsammans med deras associerade Zhegalkin-monomialer och booleska mintermer:

Boolean minterm	ABC	Zhegalkin monomial
${\bar {A}}{\bar {B}}{\bar {C}}$	000	1
${\bar {A}}{\bar {B}}C$	001	C
${\bar {A}}B{\bar {C}}$	010	B
${\bar {A}}BC$	011	före Kristus
$A{\bar {B}}{\bar {C}}$	100	A
$A{\bar {B}}C$	101	AC
$AB{\bar {C}}$	110	AB
$ABC$	111	ABC

Zhegalkin-monomialerna är naturligt ordnade efter delbarhet, medan de booleska mintermerna inte ordnar sig så naturligt; var och en representerar en exklusiv åttondel av Venn-diagrammet med tre variabler . Ordningen av monomialerna överförs till bitsträngarna enligt följande: givet $a_{1}a_{2}a_{3}$ och $b_{1} b_{2}b_{3}$ , ett par bittripletter, sedan ${\ 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}}$ .

Överensstämmelsen mellan en trevariabel booleska summa-of-minterms och ett Zhegalkinpolynom är då:

$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}}{\bar {C}}\vee f(101)A{\bar {B}}C\vee f(110 )AB{\bar {C}}\vee f(111)ABC$

$\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$ .

Ekvationssystemet ovan kan sammanfattas som en logisk matrisekvation :

${$

som NJ Wildberger kallar en Boole–Möbius-transformation.

Nedan visas formen "XOR- kalkylblad " för transformationen, som går i riktningen g till f :

$f_{000}$	$f_{001}$	$f_{010}$	$f_{011}$	$f_{100}$	$f_{101}$	$f_{110}$	$f_{111}$
$g_{000}$	$g_{000}\oplus g_{001}$	$g_{000}\oplus g_{010}$	$g_{000}\oplus g_{010}\oplus g_{001}\oplus g_{011}$	$g_{000}\oplus g_{100}$	$g_{000}\oplus g_{100}\oplus g_{001}\oplus g_{101}$	$g_{000}\oplus g_{100}\oplus g_{010}\oplus g_{110}$	$g_{000}\oplus g_{100}\01_0} g_oplus g_{001}\oplus g_{101}\oplus g_{011}\oplus g_{111}$
$g_{001}$	$g_{001}\oplus g_{010}$	$g_{001}\oplus g_{011}$	$g_{001}\oplus g_{011}\oplus g_{010}\oplus g_{100}$	$g_{001}\oplus g_{101}$	$g_{001}\oplus g_{101}\oplus g_{010}\oplus g_{110}$	$g_{001}\oplus g_{101}\oplus g_{011}\oplus g_{111}$
$g_{010}$	$g_{010}\oplus g_{011}$	$g_{010}\oplus g_{100}$	$g_{010}\oplus g_{100}\oplus g_{011}\oplus g_{101}$	$g_{010}\oplus g_{110}$	$g_{010}\oplus g_{110}\oplus g_{011}\oplus g_{111}$
$g_{011}$	$g_{011}\oplus g_{100}$	$g_{011}\oplus g_{101}$	$g_{011}\oplus g_{101}\oplus g_{100}\oplus g_{110}$	$g_{011}\oplus g_{111}$
$g_{100}$	$g_{100}\oplus g_{101}$	$g_{100}\oplus g_{110}$	$g_{100}\oplus g_{110}\oplus g_{101}\oplus g_{111}$
$g_{101}$	$g_{101}\oplus g_{110}$	$g_{101}\oplus g_{111}$
$g_{110}$	$g_{110}\oplus g_{111}$
$g_{111}$

Relaterat arbete

År 1927, samma år som Zhegalkins artikel, publicerade den amerikanske matematikern Eric Temple Bell en sofistikerad aritmetisering av boolesk algebra baserad på Richard Dedekinds idealteori och allmänna modulära aritmetik (i motsats till aritmetik mod 2). Den mycket enklare aritmetiska karaktären hos Zhegalkin-polynom uppmärksammades först i väst (oberoende av varandra var kommunikationen mellan sovjetiska och västerländska matematiker mycket begränsad under den eran) av den amerikanske matematikern Marshall Stone 1936 när han observerade när han skrev upp sin berömda stendualitetssats att den förment lösa analogin mellan booleska algebror och ringar skulle i själva verket kunna formuleras som en exakt ekvivalens som gäller för både finita och oändliga algebror, vilket leder till att han väsentligt omorganiserar sin uppsats under de närmaste åren.

Se även

• Algebraisk normalform (ANF)
• Reed-Muller expansion
• boolesk domän
• booleskt värderad funktion

Vidare läsning

•   Gindikin [Гиндикин], Semen Grigorʹevich [Семен Г.] (1972). Algebraisk logik алгебра логики в задачах [ Algebraisk logik ] (på ryska) (1 upplaga). Moskva, Ryssland: Наука [Nauka] . ISBN 0-387-96179-8 . (288 sidor) (OBS. Översättning: Springer-Verlag , 1985. [1] )
•   Perkowski, Marek A.; Grygiel, Stanislaw (1995-11-20). "6. Historisk översikt av forskningen om nedbrytning". En litteraturundersökning om funktionsnedbrytning . Version IV. Functional Decomposition Group, Institutionen för elektroteknik, Portland University, Portland, Oregon, USA. s. 21–22. CiteSeerX 10.1.1.64.1129 . (188 sidor)