Algebra Zhegalkin

Zhegalkin-algebraen er et sæt boolske funktioner, på hvilke nuloperationen ved at tage en , den binære operation af konjunktion og den binære operation af sum modulo to er defineret . Konstanten nul indtastes som . Negationsoperationen introduceres af relationen . Disjunktionsoperationen følger af identiteten [1] . $en$ $\jord$ $\plus$ $1\oplus 1=0$ $\neg x=x\oplus 1$ $x\lor y=x\land y\oplus x\oplus y$

Ved at bruge Zhegalkin-algebraen kan enhver perfekt disjunktiv normalform omdannes entydigt til et Zhegalkin-polynomium (Zhegalkins teorem).

Grundlæggende 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$

Grundlaget for booleske funktioner er således et funktionelt komplet logisk grundlag . ${\bigl \langle }\wedge ,\oplus ,1{\bigr \rangle }$

Dets omvendte logiske grundlag er også funktionelt komplet , hvor er det omvendte af XOR-operationen ( ækvivalens ). Til dette grundlag er identiteterne også inverse: - afledning af en konstant enhed, - afledning af negationsoperationen , - drift af 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 funktionelle fuldstændighed af disse to baser følger af fuldstændigheden af grundlaget . $\{\neg ,\land ,\lor \}$

Se også

Zhegalkin polynomium

Noter

↑ Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Forelæsninger om diskret matematik. - SPb., BHV-Petersburg, 2004. - isbn 5-94157-546-7, s. 110-111