Zhegalkin polynomial
Encyclopedia
Zhegalkin 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, x2 = x. Hence a polynomial such as 3x2y5z is congruent to, and can therefore be rewritten as, xyz.
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.
), including the empty set whose product is denoted 1. There are 2n 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 2n-dimensional vector space
over the Galois field GF(2) (NB: not GF(2n), whose multiplication is quite different). The 22n 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.
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.
Ivan Ivanovich Zhegalkin
Ivan Ivanovich Zhegalkin was a Russian mathematician...
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, x2 = x. Hence a polynomial such as 3x2y5z is congruent to, and can therefore be rewritten as, xyz.
Boolean equivalent
Prior to 1927 boolean algebra had been considered a calculus of logical 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, (written here as x⊕y to avoid 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-freeSquare-free polynomial
In mathematics, a square-free polynomial is a polynomial with no square factors, i.e, f \in F[x] is square-free if and only if b^2 \nmid f for every b \in F[x] with non-zero degree. This definition implies that no factors of higher order can exist, either, for if b3 divided the polynomial, then b2...
), including the empty set whose product is denoted 1. There are 2n 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 2n-dimensional vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
over the Galois field GF(2) (NB: not GF(2n), whose multiplication is quite different). The 22n 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. BellEric Temple Bell
Eric Temple Bell , was a mathematician and science fiction author born in Scotland who lived in the U.S. for most of his life...
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
Stone duality
In mathematics, there is an ample supply of categorical dualities between certain categories of topological spaces and categories of partially ordered sets. Today, these dualities are usually collected under the label Stone duality, since they form a natural generalization of Stone's representation...
theorem that the supposedly loose analogy between boolean algebras and rings
Ring (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
could in fact be formulated as an exact equivalence holding for both finite and infinite algebras, leading him to substantially reorganize his paper.
See also
- Ivan Ivanovich ZhegalkinIvan Ivanovich ZhegalkinIvan Ivanovich Zhegalkin was a Russian mathematician...
- Algebraic normal formAlgebraic normal formIn Boolean logic, the algebraic normal form is a method of standardizing and normalizing logical formulas. As a normal form, it can be used in automated theorem proving , but is more commonly used in the design of cryptographic random number generators, specifically linear feedback shift registers...
- Boolean algebra (logic)
- Boolean domainBoolean domainIn mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include false and true...
- Boolean function
- Boolean-valued functionBoolean-valued functionA boolean-valued function, in some usages is a predicate or a proposition, is a function of the type f : X → B, where X is an arbitrary set and where B is a boolean domain....