Zhegalkinův polynom

Zhegalkinův polynom  je polynom nad polem , tedy polynom s koeficienty ve tvaru 0 a 1, kde konjunkce je brána jako součin a výlučné nebo jako sčítání . Polynom byl navržen v roce 1927 Ivanem Zhegalkinem jako vhodný prostředek pro reprezentaci booleovských logických funkcí . V zahraniční literatuře se zobrazení ve formě Zhegalkinova polynomu obvykle nazývá algebraická normální forma (ANF).

Zhegalkinova věta  je tvrzení o existenci a jedinečnosti reprezentace libovolné booleovské funkce ve formě Zhegalkinova polynomu [1] .

Zhegalkinův polynom je součet modulo dva párově odlišných součinů neinvertovaných proměnných, kde se žádná proměnná nevyskytuje v žádném součinu více než jednou, a také (pokud je to nutné) konstanta 1 [1] . Formálně může být Zhegalkinův polynom reprezentován jako

nebo více formalizované jako

Příklady Zhegalkinových polynomů:

Pozadí

Aby byl systém booleovských funkcí úplný, je podle Postova teorému nutné, aby obsahoval:

1. Alespoň jedna funkce, která neukládá 0.
2. Alespoň jedna funkce, která nezachovává 1.
3. Alespoň jedna nelineární funkce.
4. Alespoň jedna nemonotónní funkce.
5. Alespoň jedna neduální funkce.

Tento požadavek splňuje zejména systém funkcí (konjunkce, modulo dva sčítání, konstanta 1). Na jeho základě jsou postaveny Zhegalkinovy ​​polynomy.

Existence a jedinečnost reprezentace

Podle Zhegalkinovy ​​věty je každá booleovská funkce jednoznačně reprezentována jako Zhegalkinův polynom. Věta je dokázána následovně. Všimněte si, že existuje n proměnných booleovských funkcí . V tomto případě existuje přesně 2 n konjunkcí , protože každý z n možných faktorů do konjunkce buď vstupuje, nebo ne. V polynomu má každá taková konjunkce 0 nebo 1, to znamená, že v n proměnných jsou různé Zhegalkinovy ​​polynomy . Nyní stačí dokázat, že různé polynomy realizují různé funkce. Předpokládejme opak. Poté, když dva různé polynomy dáme rovnítko a jeden z nich převedeme na druhou část rovnosti, získáme polynom, který je shodně roven nule a má nenulové koeficienty. Pak uvažujme člen s jednotkovým koeficientem nejmenší délky, tedy s nejmenším počtem proměnných v něm obsažených (jakékoli, pokud jich je více). Dosazením jedniček na místa těchto proměnných a nul na místa zbytku dostaneme, že na této množině nabývá jednotkové hodnoty pouze tento člen, tedy nulová funkce na jedné z množin nabývá hodnoty 1. A rozpor. To znamená, že každá booleovská funkce je realizována Zhegalkinovým polynomem jedinečným způsobem.

Reprezentace funkce ve tvaru Zhegalkinova polynomu

S ekvivalentními transformacemi DNF

Ve srovnání s DNF nejsou v Zhegalkinově polynomu žádné operace OR a NOT. Zhegalkinův polynom lze tedy získat z DNF vyjádřením operací OR a NOT pomocí operací sčítání modulo dva a konstanty 1. K tomu se použijí následující vztahy:

Níže je uveden příklad převodu DNF na Zhegalkinův polynom:

Transformace jsou založeny na vztazích

S pomocí ekvivalentních transformací SDNF

SDNF má tu vlastnost, že pro jakékoli hodnoty vstupních proměnných se ne více než jeden člen výrazu změní na jednotu. Pro takové výrazy je operace disjunkce ekvivalentní operaci sčítání modulo dva .

Při transformaci SDNF na Zhegalkinův polynom stačí nahradit všechny disjunkce operacemi modulo dva sčítání a zbavit se inverzí pomocí ekvivalentní transformace

S Carnotovou mapou

Logická funkce tří proměnných , reprezentovaná jako Carnotova mapa , se převede na Zhegalkinův polynom v následujících krocích:

• Uvažujeme všechny buňky Karnaughovy mapy 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 Carnotovy mapy je spojena s členem Zhegalkinova polynomu v závislosti na pozicích kódu, ve kterých jsou jedničky. Například buňka 111 je člen ABC , buňka 101 je člen AC , buňka 010 je člen B a buňka 000 je člen 1.
• Pokud dotyčná buňka obsahuje 0, přejděte na další buňku.
• Pokud uvažovaná buňka obsahuje 1, přidáme odpovídající člen do Zhegalkinova polynomu, invertujeme všechny buňky v Carnotově mapě, kde je tento člen roven 1, a přejdeme k další buňce. Pokud například při zvažování buňky 110 je v ní jednotka, pak se k Zhegalkinovu polynomu přidá člen AB a všechny buňky Carnotovy mapy, kde A  = 1 a B  = 1, jsou invertovány. Pokud je buňka 000 rovná jednotě, pak se k Zhegalkinovu polynomu přidá člen 1 a převrátí se celá Carnotova mapa.
• Proces transformace lze považovat za dokončený, když se po další inverzi všechny buňky Karnaughovy mapy stanou nulovými.

Metoda trojúhelníku

Trojúhelníková metoda (často nazývaná Pascalova trojúhelníková metoda) umožňuje převést pravdivostní tabulku na Zhegalkinův polynom vytvořením pomocné trojúhelníkové tabulky v souladu s následujícími pravidly:

• Je vytvořena úplná pravdivostní tabulka, ve které jsou řádky ve vzestupném pořadí binárních kódů od 000 ... 00 do 111 ... 11.
• Je vytvořena pomocná trojúhelníková tabulka, ve které se první sloupec shoduje se sloupcem funkčních hodnot v pravdivostní tabulce.
• Buňka v každém následujícím sloupci se získá modulo 2 sečtením dvou buněk předchozího sloupce - stojících ve stejném řádku a řádku níže.
• Sloupce pomocné tabulky jsou číslovány v binárních kódech ve stejném pořadí jako řádky pravdivostní tabulky.
• Každý binární kód je spojen s jedním ze členů Zhegalkinova polynomu, v závislosti na pozicích kódu, ve kterých jsou jedničky. Například buňka 111 je člen ABC , buňka 101 je člen AC , buňka 010 je člen B , buňka 000 je člen 1 a tak dále.
• Pokud je v horním řádku libovolného sloupce jednotka, pak je v Zhegalkinově polynomu přítomen odpovídající člen.

Metoda trojúhelníku je založena na větě navržené V.P. Suprunem, která přímo nesouvisí s Pascalovým trojúhelníkem. V roce 1985 byla navržena metoda binárního trojúhelníku k transformaci vektoru hodnot dokonalé disjunktivní normální formy na vektor Zhegalkinových polynomických koeficientů pro libovolnou symetrickou booleovskou funkci. V roce 1987 byla metoda rozšířena na libovolnou booleovskou funkci. Všimněte si, že metoda trojúhelníku umožňuje sestrojit Reed-Mullerův polynom se zápornou polarizací jak pro symetrické funkce, tak pro libovolné .

Metoda FFT

Nejekonomičtější z hlediska množství výpočtů a vhodná pro ruční konstrukci Zhegalkinova polynomu je metoda rychlé Fourierovy transformace (FFT).

Sestavíme tabulku sestávající ze 2 N sloupců a N  + 1 řádků, kde N  je počet proměnných ve funkci. Do horního řádku tabulky umístíme vektor funkčních hodnot, tedy poslední sloupec pravdivostní tabulky.

Každý řádek výsledné tabulky rozdělíme na bloky (černé čáry na obrázku). V první řadě zabírá blok jednu buňku, ve druhé řadě dvě, ve třetí čtyři, ve čtvrté osm atd. Každý blok v nějakém řádku, kterému budeme říkat „spodní blok“, vždy odpovídá přesně dvěma blokům v předchozím řádku. Říkejme jim „levý horní blok“ a „pravý horní blok“.

Stavba začíná od druhého řádku. Obsah levých horních bloků se beze změn přenese do odpovídajících buněk spodního bloku (zelené šipky na obrázku). Poté se bit po bitu přes pravý horní a levý horní blok provede operace „sčítání modulo dva“ a získaný výsledek se přenese do odpovídajících buněk na pravé straně spodní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, zapsané ve stejném pořadí jako ve výše popsané trojúhelníkové metodě.

Sumační metoda

Pomocí pravdivostní tabulky lze snadno vypočítat jednotlivé koeficienty Zhegalkinova polynomu. Chcete-li to provést, musíte sečíst modulo 2 hodnoty funkce v těch řádcích tabulky, kde proměnné, které nejsou ve spojení, mají nulové hodnoty.

Předpokládejme například, že potřebujete najít koeficient na spojce xz pro funkci tří proměnných f ( x ,  y ,  z ). V této konjunkci není žádná proměnná y . Najdeme vstupní množiny, ve kterých proměnná y nabývá nulové hodnoty. Jedná se o sady 0, 1, 4, 5 (000, 001, 100, 101). Pak je koeficient na spojce xz roven

Protože ve volném členu nejsou žádné proměnné

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

Znázorněme graficky koeficienty Zhegalkinova polynomu jako součet modulo 2 hodnot funkcí v některých bodech. K tomu sestrojíme čtvercovou tabulku, kde každý sloupec představuje hodnotu funkce v jednom z bodů a řádek je koeficientem Zhegalkinova polynomu. Bod na průsečíku určitého sloupce a řádku znamená, že hodnota funkce v daném bodě je zahrnuta do součtu pro daný koeficient polynomu (viz obrázek). Nazvěme tuto tabulku T N , kde N  je počet funkčních proměnných.

Existuje vzor, ​​který vám umožňuje získat tabulku pro funkci N proměnných, která má tabulku pro funkci N  − 1 proměnných. Nová tabulka T N +1 je uspořádána jako matice 2 × 2 tabulek T N , přičemž pravý horní blok matice je vymazán.

Viz také

• Algebra Zhegalkin

Poznámky

1. ↑ 1 2 Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Přednášky o diskrétní matematice. - SPb., BHV-Petersburg, 2004. - ISBN 5-94157-546-7 , str. 110-111.
2. ↑ V. P. Suprun. Tabulková metoda polynomiálního rozvoje booleovských funkcí // Kybernetika. - 1987. - č. 1 . - S. 116-117 .
3. ↑ V. P. Suprun. Základy teorie booleovských funkcí. — M.: Lenand / URSS. - 2017. - 208 s.

Literatura

• Yablonsky SV Úvod do diskrétní matematiky. — M.: Nauka. — 1986
• Marchenkov S. S. Uzavřené třídy booleovských funkcí. — M.: Fizmatlit. — 2000
• Suprun VP Základy teorie booleovských funkcí. — M.: Lenand / URSS. — 2017.