Algebra Zhegalkin

Zhegalkin-algebra är en uppsättning booleska funktioner där nolloperationen att ta en , den binära operationen av konjunktion och den binära operationen av summan modulo två definieras . Konstanten noll anges som . Negationsoperationen introduceras av relationen . Disjunktionsoperationen följer av identiteten [1] . $ett$ $\landa$ $\ plus$ $1\oplus 1=0$ $\neg x=x\oplus 1$ $x\lor y=x\land y\oplus x\oplus y$

Med hjälp av Zhegalkin-algebra kan vilken perfekt disjunktiv normalform som helst omvandlas unikt till ett Zhegalkin-polynom (Zhegalkins teorem).

Grundläggande identiteter

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

Basen för booleska funktioner är alltså en funktionellt komplett logisk grund . ${\bigl \langle }\wedge ,\oplus ,1{\bigr \rangle }$

Dess inversa logiska grund är också funktionellt komplett , där är inversen av XOR-operationen ( ekvivalens ). För denna grund är identiteterna också inversa: - härledning av en konstant enhet, - härledning av negationsoperationen , - operation av konjunktion . ${\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$

Den funktionella fullständigheten hos dessa två baser följer av basens fullständighet . $\{\neg ,\land ,\lor \}$

Se även

Zhegalkin polynom

Anteckningar

↑ Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Föreläsningar om diskret matematik. - SPb., BHV-Petersburg, 2004. - isbn 5-94157-546-7, s. 110-111