Zhegalkin Algebra

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 $\land$, and use of the binary sum operation for modulo 2 $\oplus$. The constant $0$ is introduced as $1 \oplus 1 = 0$.Zhegalkin, Ivan Ivanovich (1928). "The arithmetization of symbolic logic" (PDF). Matematicheskii Sbornik. 35 (3–4): 320. Retrieved 12 January 2024.
additional text. The negation operation is introduced by the relation $\neg x = x \oplus 1$. The disjunction operation follows from the identity $x \lor y = x \land y \oplus x \oplus y$.Yu. V. Kapitonova, S.L. Krivoj, A. A. Letichevsky. ''Lectures on Discrete Mathematics''. — SPB., BHV-Petersburg, 2004. — ISBN 5-94157-546-7, p. 110-111.

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

Basic identities

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

Thus, the basis of Boolean functions $\bigl\langle \wedge, \oplus, 1 \bigr\rangle$ is functionally complete.

Its inverse logical basis $\bigl\langle \lor, \odot, 0 \bigr\rangle$ 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, $\neg x = x \odot 0$ is the output of the negation operation, and $x \land y = x \lor y \odot x \odot y$ is the conjunction operation.

The functional completeness of the two bases follows from completeness of the basis $\$.

See also

* Zhegalkin polynomial

Notes

References

*
* {{eom, Zhegalkin_algebra

Boolean algebra