Zhegalkin algebra

Short description: Boolean algebra concept

In mathematics, Zhegalkin algebra is a set of Boolean functions defined by the nullary operation taking the value $1$, use of the binary operation of conjunction $\wedge$, and use of the binary sum operation for modulo 2 $\oplus$. The constant $0$ is introduced as $1\oplus 1=0$. The negation operation is introduced by the relation $\mathrm{\neg }x=x\oplus 1$. The disjunction operation follows from the identity $x\vee y=x\wedge y\oplus x\oplus y$.

Using Zhegalkin Algebra, any perfect disjunctive normal form can be uniquely converted into a Zhegalkin polynomial (via the Zhegalkin Theorem).

Basic identities

• $x\wedge (y\wedge z)=(x\wedge y)\wedge z$, $x\wedge y=y\wedge 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\wedge (y\oplus z)=x\wedge y\oplus x\wedge z$

Thus, the basis of Boolean functions $⟨\wedge ,\oplus ,1⟩$ is functionally complete.

Its inverse logical basis $⟨\vee ,\odot ,0⟩$ is also functionally complete, where $\odot$ is the inverse of the XOR operation (via equivalence). For the inverse basis, the identities are inverse as well: $0\odot 0=1$ is the output of a constant, $\mathrm{\neg }x=x\odot 0$ is the output of the negation operation, and $x\wedge y=x\vee y\odot x\odot y$ is the conjunction operation.

The functional completeness of the two bases follows from completeness of the basis $\{\mathrm{\neg },\wedge ,\vee \}$.

See also

• Zhegalkin polynomial

References

• Zhegalkin, Ivan Ivanovich (1927). "On the technique of calculating propositions in symbolic logic". Matematicheskii Sbornik 34 (1): 9–28. https://www.mathnet.ru/links/aab9b6eb71347d550c0aa45b1709e588/sm7433.pdf. Retrieved 12 January 2024. 
• Hazewinkel, Michiel, ed. (2001), "Zhegalkin algebra", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Main_Page