Zhegalkin polynomial


Zhegalkin 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 polynomial ring over the integers modulo 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,. 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 elementary 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, 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 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. 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, 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 as an operation. This is not to say that the space is not closed under complementation or lacks top 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

There are various known methods generally used for the computation of the Zhegalkin polynomial.
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.

Example

Given the Boolean function, express it as a Zhegalkin polynomial. This function can be expressed as a column vector
This vector should be the output of left-multiplying a vector of undetermined coefficients
by an 8x8 logical matrix which represents the possible values that all the possible conjunctions of A, B, C can take. These possible values are given in the following truth table:
The information in the above truth table can be encoded in the following logical matrix:
where the 'S' here stands for "Sierpiński", as in Sierpiński triangle, and the subscript 3 gives the exponents of its size:.
It can be proven through mathematical induction and block-matrix multiplication that any such "Sierpiński matrix" is its own inverse.
Then the linear system is
which can be solved for :
and the Zhegalkin polynomial corresponding to is.

Using the canonical disjunctive normal form

Using this method, the canonical 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

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. Define a function ζ recursively by:
Note that
where is the binomial coefficient 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.
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 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, 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. 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.
As an aside, note that this method of calculation corresponds to the method of operation of the elementary cellular automaton called . For example, start such a cellular automaton with eight cells set up with the outputs of the truth table of the Boolean expression: 10101001. Then run the cellular automaton for seven more generations while keeping a record of the state of the leftmost cell. The history of this cell then turns out to be: 11000010, which shows the coefficients of the corresponding Zhegalkin polynomial.

The Pascal method

The most economical in terms of the amount of computation and expedient for constructing the Zhegalkin polynomial manually is the Pascal method.
We build a table consisting of columns and rows, where N is the number of variables in the function. In the top row of the table we place the vector of function values, that is, the last column of the truth table.
Each row of the resulting table is divided into blocks. In the first line, the block occupies one cell, in the second line — two, in the third — four, in the fourth — eight, and so on. Each block in a certain line, which we will call "lower block", always corresponds to exactly two blocks in the previous line. We will call them "left upper block" and "right upper block".
The construction starts from the second line. The contents of the left upper blocks are transferred without change into the corresponding cells of the lower block. Then, the operation "addition modulo two" is performed bitwise over the right upper and left upper blocks and the result is transferred to the corresponding cells of the right side of the lower block. This operation is performed with all lines from top to bottom and with all blocks in each line. After the construction is completed, the bottom line contains a string of numbers, which are the coefficients of the Zhegalkin polynomial, written in the same sequence as in the triangle method described above.

The summation method

According to the truth table, it is easy to calculate the individual coefficients of the Zhegalkin polynomial. To do this, sum up modulo 2 the values of the function in those rows of the truth table where variables that are not in the conjunction take zero values.
Suppose, for example, that we need to find the coefficient of the xz conjunction for the function of three variables. There is no variable y in this conjunction. Find the input sets in which the variable y takes a zero value. These are the sets 0, 1, 4, 5. Then the coefficient at conjunction xz is
Since there are no variables with the constant term,
For a term which includes all variables, the sum includes all values of the function:
Let us graphically represent the coefficients of the Zhegalkin polynomial as sums modulo 2 of values of functions at certain points. To do this, we construct a square table, where each column represents the value of the function at one of the points, and the row is the coefficient of the Zhegalkin polynomial. The point at the intersection of some column and row means that the value of the function at this point is included in the sum for the given coefficient of the polynomial. We call this table, where N is the number of variables of the function.
There is a pattern that allows you to get a table for a function of N variables, having a table for a function of variables. The new table is arranged as a 2 × 2 matrix of tables, and the right upper block of the matrix is cleared.

Lattice-theoretic interpretation

Consider the columns of a table as corresponding to elements of a Boolean lattice of size. For each column express number M as a binary number, then if and only if, where denotes bitwise OR.
If the rows of table are numbered, from top to bottom, with the numbers from 0 to, then the tabular content of row number R is the ideal generated by element of the lattice.
Note incidentally that the overall pattern of a table is that of a logical matrix Sierpiński triangle. Also, the pattern corresponds to an elementary cellular automaton called , starting with the leftmost cell set to 1 and all other cells cleared.

Using a Karnaugh map

The figure shows a function of three variables, P represented as a Karnaugh map, which the reader may consider as an example of how to convert such maps into Zhegalkin polynomials; the general procedure is given in the following steps:
In the same year as Zhegalkin's paper the American mathematician Eric Temple Bell published a sophisticated arithmetization of Boolean algebra based on Richard Dedekind's ideal theory and general modular arithmetic. The much simpler arithmetic character of Zhegalkin polynomials was first noticed in the west 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 over the next few years.