Zhegalkinový polynom - Zhegalkin polynomial

Zhegalkin (taky Žegalkin, Gégalkine nebo Shegalkin^[1]) polynomy tvoří jednu z mnoha možných reprezentací operací Booleova algebra. Představený ruským matematikem Ivan Ivanovič Zhegalkin v roce 1927 jsou polynomiální kruh přes celá čísla 2. Výsledné degenerace modulární aritmetika Výsledkem je, že Zhegalkinovy ​​polynomy jsou jednodušší než běžné polynomy a nevyžadují ani koeficienty, ani exponenty. Koeficienty jsou nadbytečné, protože 1 je jediný nenulový koeficient. Exponenti jsou nadbyteční, protože v aritmetickém módu 2 X² = X. Proto polynom jako 3X²y⁵z je shodný s, a proto jej lze přepsat jako, xyz.

Booleovský ekvivalent

Před rokem 1927 byla booleovská algebra považována za kalkul logické hodnoty s logickými operacemi spojení, disjunkce, negace atd. Zhegalkin ukázal, že všechny booleovské operace lze psát jako obyčejné číselné polynomy, přičemž logické konstanty 0 a 1 považujeme za celá čísla 2. Logická operace konjunkce je realizována jako aritmetická operace násobení xya logické exclusive-or jako aritmetické sčítání mod 2, (psáno zde jako X⊕y aby nedošlo k záměně s běžným používáním + jako synonyma pro inclusive - nebo inclusive). Logický doplněk ¬X je pak odvozen od 1 a ⊕ jako X⊕1. Vzhledem k tomu, že ∧ a ¬ tvoří dostatečný základ pro celou booleovskou algebru, což znamená, že všechny ostatní logické operace lze získat jako složené z těchto základních operací, vyplývá z toho, že polynomy běžné algebry mohou představovat všechny booleovské operace, což umožňuje provádět logické uvažování spolehlivě odvoláním na známé zákony elementární algebra bez rozptýlení rozdílů od středoškolské algebry, které vznikají disjunkcí místo sčítání mod 2.

Příkladem aplikace je reprezentace Boolean prahu 2 ze 3 nebo střední operace jako Zhegalkinův polynom xy⊕yz⊕zx, což je 1, pokud alespoň dvě z proměnných jsou 1 a 0 jinak.

Formální vlastnosti

Formálně a Zhegalkin monomial je výsledkem konečné množiny odlišných proměnných (tedy bez čtverce ), včetně prázdné sady, jejíž produkt je označen 1. Existují 2ⁿ možné monomály Zhegalkin v n proměnné, protože každý monomiál je plně specifikován přítomností nebo nepřítomností každé proměnné. A Zhegalkinový polynom je součet (exkluzivní nebo) sady monomiálů Zhegalkin, přičemž prázdná sada je označena 0. Přítomnost nebo nepřítomnost dané monomie v polynomu odpovídá koeficientu této monomie 1 nebo 0. Bytosti Zhegalkin lineárně nezávislé, rozpětí a 2ⁿ-dimenzionální vektorový prostor přes Galoisovo pole GF(2) (Pozn .: ne GF(2ⁿ), jehož množení je zcela odlišné). 2²ⁿ vektory tohoto prostoru, tj. lineární kombinace těchto monomiálů jako jednotkových vektorů, tvoří Zhegalkinovy ​​polynomy. Přesný souhlas s počtem Booleovské operace na n proměnné, které vyčerpávají n-ary operations on {0,1}, poskytuje přímý argument počítání pro úplnost Zhegalkinových polynomů jako booleovský základ.

Tento vektorový prostor není ekvivalentní s zdarma booleovská algebra na n generátory, protože chybí komplementace (bitová logická negace) jako operace (ekvivalentně, protože postrádá horní prvek jako konstantu). Tím nechci říci, že prostor není uzavřen doplňováním nebo postrádá vrchol ( vše-jeden vektor ) jako prvek, ale spíše to, že lineární transformace tohoto a podobně konstruovaných prostorů nemusí zachovat doplněk a vrchol. Ty, které je zachovávají, odpovídají booleovským homomorfismům, např. existují čtyři lineární transformace z vektorového prostoru Zhegalkinových polynomů nad jednu proměnnou nad žádnou, pouze dvě z nich jsou booleovské homomorfismy.

Metoda výpočtu

Existuje mnoho známých metod obecně používaných pro výpočet Zhegalkinova polynomu.

• Použití metody neurčitých koeficientů
• Vytvořením kanonická disjunktivní normální forma
• Pomocí tabulek
• Pascalova metoda
• Metoda sumace
• Pomocí mapy Karnaugh

Metoda neurčitých koeficientů

Pomocí metody neurčitých koeficientů je generován lineární systém skládající se ze všech n-tic funkce a jejich hodnot. Řešení lineárního systému dává koeficienty Zhegalkinova polynomu.

Příklad

Vzhledem k booleovské funkci ${displaystyle f (A, B, C) = {ar {A}} {ar {B}} {ar {C}} + {ar {A}} B {ar {C}} + A {ar {B} } {ar {C}} + ABC}$vyjádřit jako Zhegalkinův polynom. Tuto funkci lze vyjádřit jako vektor sloupce

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

Tento vektor by měl být výstupem násobení vlevo vektorem neurčených koeficientů

${displaystyle {vec {c}} = {egin {pmatrix} c_ {0} c_ {1} c_ {2} c_ {3} c_ {4} c_ {5} c_ {6} c_ {7} konec {pmatrix}}}$

o 8x8 logická matice což představuje možné hodnoty, které mohou nabývat všechny možné spojky A, B, C. Tyto možné hodnoty jsou uvedeny v následující tabulce pravdivosti:

${displaystyle {egin {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 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 0 & 1 & 0 && 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 0 & 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 & 1 & 1 & 0 & 1 & 0 & 1 & 0$.

Informace ve výše uvedené tabulce pravdy lze zakódovat do následující logické matice:

${Displaystyle S_ {3} = {Egin {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 1end {pmatrix}}}$

kde „S“ zde znamená „Sierpiński“, jako v Sierpińského trojúhelník a dolní index 3 udává exponenty své velikosti: ${displaystyle 2 ^ {3} jsou 2 ^ {3}}$.

Matematickou indukcí a násobením blokové matice lze dokázat, že každá taková „Sierpiński matice“ ${displaystyle S_ {n}}$ je jeho vlastní inverzní.^{[poznámka 1]}

Pak je lineární systém

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

pro které lze vyřešit ${displaystyle {vec {c}}}$:

${displaystyle {vec {c}} = S_ {3} ^ {- 1} {vec {f}} = S_ {3} {vec {f}} = {egin {pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 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 & 1end {pmatrix}} {egin {pmatrix} 1 0 1 0 1 0 0 1end {pmatrix}} = {egin {pmatrix} 1 1 1 1oplus 1 1oplus 1 1oplus 1oplus 1 1oplus 1oplus 1oplus 1end {pmatrix}} = {egin {pmatrix} 1 1 0 0 0 0 1 0end {pmatrix}}}$,

a Zhegalkinův polynom odpovídající ${displaystyle {vec {c}}}$ je ${displaystyle 1oplus Coplus AB}$.

Použití kanonické disjunktivní normální formy

Pomocí této metody se kanonická disjunktivní normální forma (plně rozšířený disjunktivní normální forma ) se vypočítá jako první. Potom jsou negace v tomto výrazu nahrazeny ekvivalentním výrazem za použití součtu mod 2 proměnné a 1. Znaky disjunkce se změní na přidání mod 2, závorky se otevřou a výsledný logický výraz se zjednoduší. Toto zjednodušení vede k polygenu Zhegalkin.

Pomocí tabulek

Výpočet Zhegalkinova polynomu pro ukázkovou funkci P metodou tabulky

Nechat ${displaystyle c_ {0}, ..., c_ {2 ^ {n} -1}}$ být výstupy pravdivostní tabulky pro funkci P z n proměnné, takže index indexu ${displaystyle c_ {i}}$'s odpovídá binárnímu indexování mintermů^{[poznámka 2]}. Definujte funkci ζ rekurzivně pomocí:

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

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

Všimněte si, že

${displaystyle zeta (c_ {0}, ..., c_ {m}) = igoplus _ {k = 0} ^ {m} {m zvolte k} _ {2} c_ {k}}$

kde ${displaystyle {m vyberte k} _ {2}}$ je binomický koeficient snížena modulo 2.

Pak

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

je i ^th koeficient Zhegalkinova polynomu, jehož literály v i ^th monomial jsou stejné jako literály v i ^th minterm, kromě toho, že negativní literály jsou odstraněny (nebo nahrazeny 1).

Transformace ζ je vlastní inverzní, takže ke výpočtu koeficientů lze použít stejný druh tabulky ${displaystyle c_ {0}, ..., c_ {2 ^ {n} -1}}$ vzhledem k koeficientům ${displaystyle g_ {0}, ..., g_ {2 ^ {n} -1}}$. Prostě nech

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

Pokud jde o tabulku na obrázku, zkopírujte výstupy tabulky pravdy (ve sloupci označeném P) do levého sloupce trojúhelníkové tabulky. Pak postupně vypočítejte sloupce zleva doprava aplikací XOR na každou dvojici svisle sousedících buněk, abyste buňku vyplnili hned napravo od horní buňky každé dvojice. Když je vyplněna celá trojúhelníková tabulka, pak horní řádek přečte koeficienty lineární kombinace, která po zjednodušení (odstranění nul) poskytne Zhegalkinův polynom.

Chcete-li přejít od Zhegalkinova polynomu k tabulce pravdivosti, je možné vyplnit horní řádek trojúhelníkové tabulky koeficienty Zhegalkinova polynomu (uvedení nuly pro všechny kombinace pozitivních literálů, které nejsou v polynomu). Poté postupně vypočítejte řádky shora dolů použitím XOR na každou dvojici vodorovně sousedících buněk, aby se buňka okamžitě naplnila do spodní části buňky nejvíce vlevo každého páru. Když je vyplněna celá trojúhelníková tabulka, může být její sloupec zcela vlevo zkopírován do sloupce P tabulky pravdy.

Kromě toho je třeba poznamenat, že tato metoda výpočtu odpovídá způsobu fungování základní buněčný automat volala Pravidlo 102. Například spusťte takový buněčný automat s osmi buňkami nastavenými s výstupy pravdivostní tabulky (nebo koeficienty kanonické disjunktivní normální formy) booleovského výrazu: 10101001. Pak spusťte buněčný automat dalších sedm generací při zachování záznam stavu buňky nejvíce vlevo. Historie této buňky se poté ukáže být: 11000010, která ukazuje koeficienty příslušného Zhegalkinova polynomu.^[2][3]

Pascalova metoda

Použití metody Pascal k výpočtu Zhegalkinova polynomu pro booleovskou funkci ${displaystyle {ar {a}} {ar {b}} {ar {c}} + {ar {a}} b {ar {c}} + {ar {a}} bc + ab {ar {c}} }$. Řádek v ruštině dole říká:
${displaystyle oplus}$ - bitová operace „Exkluzivní OR“

Nejekonomičtější z hlediska množství výpočtu a účelné pro ruční konstrukci Zhegalkinova polynomu je metoda Pascal.

Stavíme stůl skládající se z ${displaystyle 2 ^ {N}}$ sloupce a ${displaystyle N + 1}$ řádky, kde N je počet proměnných ve funkci. V horním řádku tabulky umístíme vektor hodnot funkcí, tj. Poslední sloupec tabulky pravdy.

Každý řádek výsledné tabulky je rozdělen do bloků (černé čáry na obrázku). V prvním řádku blok zaujímá jednu buňku, ve druhém řádku - dva, ve třetím - čtyři, ve čtvrtém - osm atd. Každý blok v určitém řádku, který budeme nazývat „spodní blok“, vždy odpovídá přesně dvěma blokům v předchozím řádku. Budeme jim říkat „levý horní blok“ a „pravý horní blok“.

Stavba začíná od druhého řádku. Obsah levých horních bloků se beze změny přenese do odpovídajících buněk dolního bloku (zelené šipky na obrázku). Poté se po pravém horním a levém horním bloku provede bitová operace „add modulo two“ a výsledek se přenese do odpovídajících buněk na pravé straně dolního bloku (červené šipky na obrázku). Tato operace se provádí se všemi řádky shora dolů a se všemi bloky v každém řádku. Po dokončení konstrukce obsahuje spodní řádek řetězec čísel, což jsou koeficienty Zhegalkinova polynomu, napsané ve stejném pořadí jako výše popsaná metoda trojúhelníku.

Metoda sčítání

Grafické znázornění koeficientů Zhegalkinova polynomu pro funkce s různým počtem proměnných.

Podle tabulky pravdivosti je snadné vypočítat jednotlivé koeficienty Zhegalkinova polynomu. Chcete-li to provést, sečtěte modulo 2 hodnoty funkce v těch řádcích tabulky pravdy, kde proměnné, které nejsou ve spojení (což odpovídá vypočtenému koeficientu), mají nulové hodnoty.

Předpokládejme například, že musíme najít koeficient xz konjunkce pro funkci tří proměnných ${displaystyle f (x, y, z)}$. Neexistuje žádná proměnná y v této souvislosti. Najděte vstupní sady, ve kterých je proměnná y bere nulovou hodnotu. Jedná se o množiny 0, 1, 4, 5 (000, 001, 100, 101). Pak koeficient ve spojení xz je

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

Protože s konstantním členem nejsou žádné proměnné,

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

U výrazu, který zahrnuje všechny proměnné, zahrnuje součet všechny hodnoty funkce:

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

Představme si graficky koeficienty Zhegalkinova polynomu jako součty modulo 2 hodnot funkcí v určitých bodech. K tomu vytvoříme čtvercovou tabulku, kde každý sloupec představuje hodnotu funkce v jednom z bodů a řádek je koeficientem Zhegalkinova polynomu. Bod v průsečíku nějakého sloupce a řádku znamená, že hodnota funkce v tomto bodě je zahrnuta do součtu pro daný koeficient polynomu (viz obrázek). Říkáme tomu stůl ${displaystyle T_ {N}}$, kde N je počet proměnných funkce.

Existuje vzor, ​​který vám umožní získat tabulku pro funkci N proměnné, které mají tabulku pro funkci ${displaystyle N-1}$ proměnné. Nová tabulka ${displaystyle T_ {N} +1}$ je uspořádán jako matice 2 × 2 z ${displaystyle T_ {N}}$ tabulky a pravý horní blok matice je vymazán.

Lattice-teoretická interpretace

Zvažte sloupce tabulky ${displaystyle T_ {N}}$ jako odpovídající prvkům a Booleova mříž velikosti ${displaystyle 2 ^ {N}}$. Pro každý sloupec ${displaystyle f_ {M}}$ expresní číslo M jako binární číslo ${displaystyle M_ {2}}$, pak ${displaystyle f_ {M} leq f_ {K}}$ kdyby a jen kdyby ${displaystyle M_ {2} vee K_ {2} = K_ {2}}$, kde ${displaystyle vee}$ označuje bitový OR.

Pokud jsou řádky tabulky ${displaystyle T_ {N}}$ jsou očíslovány, shora dolů, s čísly od 0 do ${displaystyle 2 ^ {N} -1}$, pak tabulkový obsah čísla řádku R je ideál generované prvkem ${displaystyle f_ {R}}$ mřížky.

Mimochodem si všimněte celkového vzoru tabulky ${displaystyle T_ {N}}$ je to a logická matice Sierpińského trojúhelník. Vzor také odpovídá základní buněčný automat volala Pravidlo 60, počínaje buňkou úplně vlevo nastavenou na 1 a všechny ostatní buňky vymazány.

Pomocí mapy Karnaugh

Převod Karnaughovy mapy na Zhegalkinův polynom.

Obrázek ukazuje funkci tří proměnných, P(A, B, C) představovaný jako a Karnaugh mapa, který může čtenář považovat za příklad toho, jak převést takové mapy na Zhegalkinovy ​​polynomy; obecný postup je uveden v následujících krocích:

• Uvažujeme všechny buňky mapy Karnaugha ve vzestupném pořadí podle počtu jednotek v jejich kódech. Pro funkci tří proměnných bude sekvence buněk 000–100–010–001–110–101–011–111. Každá buňka mapy Karnaugh je spojena s členem Zhegalkinova polynomu v závislosti na pozicích kódu, ve kterém jsou. Například buňka 111 odpovídá členu ABC, buňka 101 odpovídá členu AC, buňka 010 odpovídá členu B a buňka 000 odpovídá členu 1.
• Pokud je dotyčná buňka 0, přejděte do další buňky.
• Pokud je dotyčná buňka 1, přidejte odpovídající výraz do Zhegalkinova polynomu a poté obraťte všechny buňky na mapě Karnaugh, kde je tento výraz 1 (nebo patřící k ideál generovaný tímto výrazem v booleovské mřížce monomiálů) a přejděte do další buňky. Například pokud se při zkoumání buňky 110 v ní objeví jedna, pak se do Zhegalkinova polynomu přidá výraz AB a všechny buňky Karnaughovy mapy jsou invertovány, pro které A = 1 a B = 1. Pokud je jednotka v buňka 000, pak se k polynomu Zhegalkin přidá člen 1 a celá mapa Karnaugha se převrátí.
• Proces transformace lze považovat za dokončený, když se po další inverzi stanou všechny buňky mapy Karnaugh nulové nebo se nestarají.

Möbiova transformace

The Möbioův inverzní vzorec se týká koeficientů booleovské exprese součtu minut a Zhegalkinova polynomu. Toto je verze Möbiovyho vzorce s částečným řádem, nikoli teoretická čísla. Möbioův inverzní vzorec pro dílčí objednávky je:

${displaystyle g (x) = součet _ {y: yleq x} f (y) leftrightarrow f (x) = součet _ {y: yleq x} g (y) mu (y, x)}$^[4],

kde ${displaystyle mu (y, x) = (- 1) ^ {| x | - | y |}}$, |X| být Hammingova vzdálenost z X od 0. Od ${displaystyle -1equiv 1}$ v Zhegalkinově algebře se Möbiova funkce zhroutí na konstantu 1.

Sada dělitelů daného čísla X je také ideální objednávka vygenerovaná tímto číslem: ${displaystyle langle xangle}$. Protože součet je modulo 2, vzorec lze přepracovat jako

${displaystyle g (x) = igoplus _ {y: yin langle xangle} f (y) leftrightarrow f (x) = igoplus _ {y: yin langle xangle} g (y)}$

Příklad

Jako příklad zvažte případ se třemi proměnnými. Následující tabulka ukazuje vztah dělitelnosti:

Pak

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

Výše uvedený systém rovnic lze vyřešit pro Fa výsledek lze shrnout jako dosažitelný výměnou G a F v celém výše uvedeném systému.

V tabulce níže jsou uvedena binární čísla spolu s přidruženými monomeli Zhegalkin a booleovskými mintermy:

Booleova minterm	ABC	Zhegalkin monomial
${displaystyle {ar {A}} {ar {B}} {ar {C}}}$	000	1
${displaystyle {ar {A}} {ar {B}} C}$	001	C
${displaystyle {ar {A}} B {ar {C}}}$	010	B
${displaystyle {ar {A}} před naším letopočtem}$	011	před naším letopočtem
${displaystyle A {ar {B}} {ar {C}}}$	100	A
${displaystyle A {ar {B}} C}$	101	AC
${displaystyle AB {ar {C}}}$	110	AB
${displaystyle ABC}$	111	ABC

Zhegalkinové monomie jsou přirozeně uspořádány dělitelností, zatímco booleovské mintermy se tak přirozeně neuspořádávají samy; každý představuje exkluzivní osminu ze tří proměnných Vennův diagram. Uspořádání monomiálů se přenáší na bitové řetězce následovně: zadáno ${displaystyle a_ {1} a_ {2} a_ {3}}$ a ${displaystyle b_ {1} b_ {2} b_ {3}}$, tedy pár bitových tripletů ${displaystyle a_ {1} a_ {2} a_ {3} leq b_ {1} b_ {2} b_ {3} leftrightarrow a_ {1} leq b_ {1} klín a_ {2} leq b_ {2} klín a_ { 3} leq b_ {3}}$.

Korespondence mezi třemi proměnnými booleovskými součty minut a Zhegalkinovým polynomem je pak:

${displaystyle f (000) {ar ​​{A}} {ar {B}} {ar {C}} vee f (001) {ar ​​{A}} {ar {B}} Cvee f (010) {ar ​​{A }} B {ar {C}} vee f (011) {ar ​​{A}} BCvee f (100) A {ar {B}} {ar {C}} vee f (101) A {ar {B}} Cvee f (110) AB {ar {C}} vee f (111) ABC}$

${displaystyle qquad qquad equiv g (000) oplus g (001) Coplus g (010) Boplus g (011) BCoplus g (100) Aoplus g (101) ACoplus g (110) ABoplus g (111) ABC}$.

Výše uvedený systém rovnic lze shrnout jako a logická matice rovnice:

${displaystyle {egin {pmatrix} g (000) g (001) g (010) g (011) g (100) g (101) g (110) g (111) konec {pmatrix}) } = {Egin {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 && 1end {pmatrix}} {Egin {pmatrix} f (000) f (001) f (010) f (011) f (100) f (101) f (110) f (111) konec {pmatrix}}}$

který N. J. Wildberger volá Boole – Möbiovu transformaci.

Níže je zobrazen „XOR tabulkový kalkulátor „Forma transformace, která jde směrem k G na F:

${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}}$

Související práce

Ve stejném roce jako Zhegalkinův článek (1927) americký matematik Eric Temple Bell zveřejnil sofistikovanou aritmetizaci booleovské algebry založenou na Richard Dedekind Ideální teorie a obecná modulární aritmetika (na rozdíl od aritmetického modu 2). Mnohem jednodušší aritmetický charakter Zhegalkinových polynomů si poprvé všiml na západě (nezávisle na tom, v té době byla komunikace mezi sovětskými a západními matematiky velmi omezená) americký matematik Marshall Stone v roce 1936, kdy při psaní svého slavného pozoroval Kamenná dualita teorém, že údajně volná analogie mezi Booleovy algebry a prsteny by ve skutečnosti mohl být formulován jako přesná ekvivalence pro konečné i nekonečné algebry, což by ho vedlo k zásadní reorganizaci jeho práce v příštích několika letech.

Viz také

• Algebraická normální forma (ANF)
• Normální forma kruhového součtu (RSNF)
• Reed-Mullerova expanze
• Booleovská doména
• Funkce s booleovskou hodnotou

Poznámky

Reference

• Bell, Eric Temple (1927). „Aritmetika logiky“. Transakce Americké matematické společnosti. 29 (3): 597–611. doi:10.2307/1989098. JSTOR  1989098.
• Gindikin, S. G. (1972). алгебра логики в задачах [Algebraická logika] (v Rusku). Moskva, Rusko: Наука [Nauka] (Anglický překlad: Springer-Verlag 1985). ISBN  0-387-96179-8.
• Kámen, Marshalle (1936). "Teorie zastoupení pro booleovské algebry". Transakce Americké matematické společnosti. 40 (1): 37–111. doi:10.2307/1989664. ISSN  0002-9947. JSTOR  1989664.
• Жега́лкин [Zhegalkin], Ива́н Иванович [Ivan Ivanovič] (1927). „О технике вычислений предложений в символической логике“ [O technice výpočtu výroků v symbolické logice (Sur le calcul des propositions dans la logique symbolique)]. Matematicheskii Sbornik (v ruštině a francouzštině). Moskva, Rusko. 34 (1): 9–28. Mi  msb7433. Archivováno od původního dne 2017-10-12. Citováno 2017-10-12.