Zhegalkin polynomial

Zhegalkin (also Zegalkin or Gegalkine) polynomials form one of many possible representations of the operations of Boolean algebra. Introduced by the Russian mathematician I.I. Zhegalkin in 1927, they are the polynomials of ordinary high school algebra interpreted over the integers mod 2. The resulting degeneracies of modular arithmetic result in Zhegalkin polynomials being simpler than ordinary polynomials, requiring neither coefficients nor exponents. Coefficients are redundant because 1 is the only nonzero coefficient. Exponents are redundant because in arithmetic mod 2, "x"² = "x". Hence a polynomial such as 3"x"²"y"⁵"z" is congruent to, and can therefore be rewritten as, "xyz".

__TOC__

Boolean equivalent

Prior to 1927 Boolean algebra had been considered a calculus of logical truth values with logical operations of conjunction, disjunction, negation, etc. Zhegalkin showed that all Boolean operations could be written as ordinary numeric polynomials, thinking of the logical constants 0 and 1 as integers mod 2. The logical operation of conjunction is realized as the arithmetic operation of multiplication "xy", and logical exclusive-or as arithmetic addition mod 2, which we shall write here as "x"⊕"y" to avoid any confusion with the common use of + as a synonym for ∨ (inclusive-or). Logical complement ¬"x" is then derived from 1 and ⊕ as "x"⊕1. Since ∧ and ¬ form a sufficient basis for the whole of Boolean algebra, meaning that all other logical operations are obtainable as composites of these basic operations, it follows that the polynomials of ordinary algebra can represent all Boolean operations, allowing Boolean reasoning to be performed reliably by appealing to the familiar laws of high school algebra without the distraction of the differences from high school algebra that arise with disjunction in place of addition mod 2.

An example application is the representation of the Boolean 2-out-of-3 threshold or median operation as the Zhegalkin polynomial "xy"⊕"yz"⊕"zx", which is 1 when at least two of the variables are 1 and 0 otherwise.

Formal properties

Formally a "Zhegalkin monomial" is the product of a finite set of distinct variables (hence square-free), including the empty set whose product is denoted 1. There are 2^"n" possible Zhegalkin monomials in "n" variables, since each monomial is fully specified by the presence or absence of each variable. A "Zhegalkin polynomial" is the sum (exclusive-or) of a set of Zhegalkin monomials, with the empty set denoted by 0. A given monomial's presence or absence in a polynomial corresponds to that monomial's coefficient being 1 or 0 respectively. The Zhegalkin monomials, being linearly independent, span a 2^"n"-dimensional vector space over the Galois field GF(2) (NB: not GF(2^"n"), whose multiplication is quite different). The 2^2"n" vectors of this space, i.e. the linear combinations of those monomials as unit vectors, constitute the Zhegalkin polynomials. The exact agreement with the number of Boolean operations on "n" variables, which exhaust the "n"-ary operations on {0,1}, furnishes a direct counting argument for completeness of the Zhegalkin polynomials as a Boolean basis.

This vector space is not equivalent to the free Boolean algebra on "n" generators because it lacks complementation (bitwise logical negation) as an operation (equivalently, because it lacks the top element as a constant). This is not to say that the space is not closed under complementation or lacks top (the all-ones vector) as an element, but rather that the linear transformations of this and similarly constructed spaces need not preserve complement and top. Those that do preserve them correspond to the Boolean homomorphisms, e.g. there are four linear transformations from the vector space of Zhegalkin polynomials over one variable to that over none, only two of which are Boolean homomorphisms.

Related work

In the same year as Zhegalkin's paper (1927) the American mathematician E.T. Bell published a sophisticated arithmetization of Boolean algebra based on Dedekind's ideal theory and general modular arithmetic (as opposed to arithmetic mod 2). The much simpler arithmetic character of Zhegalkin polynomials was first noticed in the west (independently, communication between Soviet and western mathematicians being very limited in that era) by the American mathematician Marshall Stone in 1936 when he observed while writing up his celebrated Stone duality theorem that the supposedly loose analogy between Boolean algebras and rings could in fact be formulated as an exact equivalence holding for both finite and infinite algebras, leading him to substantially reorganize his paper.

References

* cite journal
last = Bell
first = Eric
authorlink = Eric Temple Bell
title = Arithmetic of Logic
journal = Transactions of the American Mathematical Society
volume = 29
pages = 597–611
date = 1927
doi = 10.2307/1989098
* cite book
last = Gindikin
first = S.G.
title = Algebraic Logic (Russian: алгебра логики в задачах)
publisher = Nauka (English translation Springer-Verlag 1985)
date = 1972
location = Moscow
id = ISBN 0-387-96179-8
* cite journal
last = Stone
first = Marshall
authorlink = Marshall Harvey Stone
title = The Theory of Representations for Boolean Algebras
journal = Transactions of the American Mathematical Society
volume = 40
pages = 37–111
date = 1936
id = ISSN|0002-9947
doi = 10.2307/1989664
* cite journal
last = Zhegalkin
first = Ivan Ivanovich
authorlink = Ivan Ivanovich Zhegalkin
title = On the Technique of Calculating Propositions in Symbolic Logic
journal = Matematicheskii Sbornik
volume = 43
pages = 9–28
date = 1927
id =

ee also

* Ivan Ivanovich Zhegalkin
* Algebraic normal form
* Boolean algebra (logic)
* Boolean domain
* Boolean function
* Boolean-valued function