Algebra Zhegalkin

Zhegalkin-algebra on joukko Boolen funktioita, joille määritellään ykkösen ottamisen nollaoperaatio, konjunktion binäärioperaatio ja summan modulo kaksi binäärioperaatio . Vakio nolla syötetään muodossa . Negaatiooperaation esittelee relaatio . Disjunktiooperaatio seuraa identiteetistä [1] . $yksi$ $\maa$ $\oplus$ $1\oplus 1=0$ $\neg x=x\oplus 1$ $x\lor y=x\land y\oplus x\oplus y$

Zhegalkin-algebraa käyttämällä mikä tahansa täydellinen disjunktiivinen normaalimuoto voidaan muuttaa yksiselitteisesti Zhegalkinin polynomiksi (Zhegalkinin lause).

Perusidentiteetit

$x\land (y\land z)=(x\land y)\land z$ , $x\land y=y\land x$
$x\oplus (y\oplus z)=(x\oplus y)\oplus z$ , $x\oplus y=y\oplus x$
$x\oplus x=0$
$x\oplus 0=x$
$x\land (y\oplus z)=x\land y\oplus x\land z$

Siten Boolen funktioiden perusta on toiminnallisesti täydellinen looginen perusta . ${\bigl \langle }\wedge ,\oplus ,1{\bigr \rangle }$

Sen käänteinen looginen perusta on myös toiminnallisesti täydellinen , missä on XOR-operaation käänteisarvo ( ekvivalenssi ). Tämän perusteella identiteetit ovat myös käänteisiä: - vakioyksikön johtaminen, - negaatiooperaation johtaminen , - konjunktion operaatio . ${\displaystyle {\bigl \langle }\lor ,\odot ,0{\bigr \rangle ))$ $\odot$ $0\odot 0=1$ $\neg x=x\odot 0$ $x\land y=x\lor y\odot x\odot y$

Näiden kahden perustan toiminnallinen täydellisyys seuraa pohjan täydellisyydestä . $\{\neg ,\land ,\lor \}$

Katso myös

Zhegalkinin polynomi

Muistiinpanot

↑ Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Diskreetin matematiikan luentoja. - SPb., BHV-Petersburg, 2004. - isbn 5-94157-546-7, s. 110-111