Zhegalkin algebra explained

In mathematics, Zhegalkin algebra is a set of Boolean functions defined by the nullary operation taking the value

, use of the binary operation of conjunction

\land

⊕

. The constant

is introduced as

1 ⊕ 1=0

.^[1] The negation operation is introduced by the relation

\negx=x ⊕ 1

. The disjunction operation follows from the identity

x\lory=x\landy ⊕ x ⊕ y

.^[2]

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\landz)=(x\landy)\landz

x\landy=y\landx

x ⊕ (y ⊕ z)=(x ⊕ y) ⊕ z

x ⊕ y=y ⊕ x

x ⊕ x=0

x ⊕ 0=x

x\land(y ⊕ z)=x\landy ⊕ x\landz

Thus, the basis of Boolean functions

l\langle\wedge, ⊕ ,1r\rangle

Its inverse logical basis

l\langle\lor,\odot,0r\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\odot0=1

is the output of a constant,

\negx=x\odot0

is the output of the negation operation, and

x\landy=x\lory\odotx\odoty

The functional completeness of the these two bases follows from completeness of the basis

\{\neg,\land,\lor\}

Zhegalkin . Ivan Ivanovich . On the technique of calculating propositions in symbolic logic. Matematicheskii Sbornik . 1927 . 34 . 1 . 9–28 . 12 January 2024.

https://www.mathnet.ru/links/296149770c6a650e09ce139cb352ca3c/sm7400.pdf Zhegalkin, Ivan Ivanovich (1928). "The arithmetization of symbolic logic" (PDF). Matematicheskii Sbornik. 35 (3–4): 320. Retrieved 12 January 2024.
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.