Misplaced Pages

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Zhegalkin algebra" – news · newspapers · books · scholar · JSTOR (August 2024) (Learn how and when to remove this message)

In mathematics, Zhegalkin algebra is a set of Boolean functions defined by the nullary operation taking the value ${\displaystyle 1}$, use of the binary operation of conjunction ${\displaystyle \land }$, and use of the binary sum operation for modulo 2 ${\displaystyle \oplus }$. The constant ${\displaystyle 0}$ is introduced as ${\displaystyle 1\oplus 1=0}$. The negation operation is introduced by the relation ${\displaystyle \neg x=x\oplus 1}$. The disjunction operation follows from the identity ${\displaystyle x\lor y=x\land 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

• ${\displaystyle x\land (y\land z)=(x\land y)\land z}$, ${\displaystyle x\land y=y\land x}$
• ${\displaystyle x\oplus (y\oplus z)=(x\oplus y)\oplus z}$, ${\displaystyle x\oplus y=y\oplus x}$
• ${\displaystyle x\oplus x=0}$
• ${\displaystyle x\oplus 0=x}$
• ${\displaystyle x\land (y\oplus z)=x\land y\oplus x\land z}$

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

Its inverse logical basis ${\displaystyle {\bigl \langle }\lor ,\odot ,0{\bigr \rangle }}$ is also functionally complete, where ${\displaystyle \odot }$ is the inverse of the XOR operation (via equivalence). For the inverse basis, the identities are inverse as well: ${\displaystyle 0\odot 0=1}$ is the output of a constant, ${\displaystyle \neg x=x\odot 0}$ is the output of the negation operation, and ${\displaystyle x\land y=x\lor y\odot x\odot y}$ is the conjunction operation.

The functional completeness of the these two bases follows from completeness of the basis ${\displaystyle \{\neg ,\land ,\lor \}}$.

See also

• Zhegalkin polynomial

References

• Zhegalkin, Ivan Ivanovich (1927). "On the technique of calculating propositions in symbolic logic" (PDF). Matematicheskii Sbornik. 34 (1): 9–28. Retrieved 12 January 2024.

Notes

1. Zhegalkin, Ivan Ivanovich (1928). "The arithmetization of symbolic logic" (PDF). Matematicheskii Sbornik. 35 (3–4): 320. Retrieved 12 January 2024., additional text.
2. 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.

Further reading

• https://encyclopediaofmath.org/Zhegalkin_algebra

• Boolean algebra