Zhegalkin polynomial

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Zhegalkin (also Žegalkin, Gégalkine or Shegalkin[1]) polynomials form one of many possible representations of the operations of Boolean algebra. Introduced by the Russian mathematician Ivan Ivanovich 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.

Boolean equivalent[edit]

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 xy 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 xyyzzx, which is 1 when at least two of the variables are 1 and 0 otherwise.

Formal properties[edit]

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 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.

Method of computation[edit]

Computing the Zhegalkin polynomial for an example function P by the table method

There are three known methods generally used for the computation of the Zhegalkin polynomial.

The method of indeterminate coefficients[edit]

Using the method of indeterminate coefficients, a linear system consisting of all the tuples of the function and their values is generated. Solving the linear system gives the coefficients of the Zhegalkin polynomial.

Using the canonical disjunctive normal form[edit]

Using this method, the canonical disjunctive normal form (a fully expanded disjunctive normal form) is computed first. Then the negations in this expression are replaced by an equivalent expression using the mod 2 sum of the variable and 1. The disjunction signs are changed to addition mod 2, the brackets are opened, and the resulting Boolean expression is simplified. This simplification results in the Zhegalkin polynomial.

Using tables[edit]

Let be the outputs of a truth table for the function P of n variables, such that the index of the 's corresponds to the binary indexing of the minterms. Define a function ζ recursively like so:

.

Note that

where the binomial coefficient is reduced modulo 2.

Then

is the i th coefficient of a Zhegalkin polynomial whose literals in the i th monomial are the same as the literals in the i th minterm, except that the negative literals are removed (or replaced by 1).

The ζ-transformation is its own inverse, so the same kind of table can be used to compute the coefficients given the coefficients . Just let

.

In terms of the table in the figure, copy the outputs of the truth table (in the column labeled P) into the leftmost column of the triangular table. Then successively compute columns from left to right by applying XOR to each pair of vertically adjacent cells in order to fill the cell immediately to the right of the top cell of each pair. When the entire triangular table is filled in then the top row reads out the coefficients of a linear combination which, when simplified (removing the zeroes), yields the Zhegalkin polynomial.

To go from a Zhegalkin polynomial to a truth-table, it is possible to fill out the top row of the triangular table with the coefficients of the Zhegalkin polynomial (putting in zeroes for any combinations of positive literals not in the polynomial). Then successively compute rows from top to bottom by applying XOR to each pair of horizontally adjacent cells in order to fill the cell immediately to the bottom of the leftmost cell of each pair. When the entire triangular table is filled then the leftmost column of it can be copied to column P of the truth table.

Related work[edit]

In the same year as Zhegalkin's paper (1927) the American mathematician Eric Temple Bell published a sophisticated arithmetization of Boolean algebra based on Richard 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.

See also[edit]

References[edit]

  1. ^ Steinbach, Bernd; Posthoff, Christian (2009). "Preface". Written at Freiberg, Germany. Logic Functions and Equations - Examples and Exercises (1st ed.). Dordrecht, Netherlands: Springer Science + Business Media B. V. p. xv. ISBN 978-1-4020-9594-8. LCCN 2008941076.