Algebra Zhegalkin

A Zhegalkin algebra olyan logikai függvények halmaza, amelyeken az egyet vevő null művelet , a konjunkció bináris művelete és a modulo kettes összeg bináris művelete definiálva van . A nulla állandó értéke . A tagadási műveletet a reláció vezeti be . A diszjunkciós művelet az [1] azonosságból következik . $egy$ $\föld$ $\oplus$ $1\oplus 1=0$ $\neg x=x\oplus 1$ $x\lor y=x\land y\oplus x\oplus y$

A Zhegalkin-algebra segítségével bármilyen tökéletes diszjunktív normálalakot egyedileg alakíthatunk Zhegalkin-polinommá (Zhegalkin-tétel).

Alapvető identitások

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

Így a logikai függvények alapja egy funkcionálisan teljes logikai bázis . ${\bigl \langle }\wedge ,\oplus ,1{\bigr \rangle }$

Az inverz logikai alapja funkcionálisan is teljes , ahol az XOR művelet inverze ( ekvivalencia ). Erre az alapra az azonosságok is inverzek: - konstans egység származtatása, - negációs művelet levezetése , - konjunkció művelete . ${\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$

E két bázis funkcionális teljessége a bázis teljességéből következik . $\{\neg ,\land ,\lor \}$

Lásd még

Zhegalkin polinom

Jegyzetek

↑ Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Előadások a diszkrét matematikáról. - SPb., BHV-Petersburg, 2004. - isbn 5-94157-546-7, 110-111.