Zhegalkin polynomial

Introduced by the Russian mathematician Ivan Ivanovich Zhegalkin in 1927,[2] they are the polynomial ring over the integers modulo 2.

Zhegalkin showed that all Boolean operations could be written as ordinary numeric polynomials, representing the false and true values as 0 and 1, the integers mod 2.

Logical conjunction is written as 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 ∨).

For example, the Boolean 2-out-of-3 threshold or median operation is written as the Zhegalkin polynomial xy⊕yz⊕zx.

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.

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.

It can be proven through mathematical induction and block-matrix multiplication that any such "Sierpiński matrix"

The disjunction signs are changed to addition mod 2, the brackets are opened, and the resulting Boolean expression is simplified.

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.

For example, start such a cellular automaton with eight cells set up with the outputs of the truth table (or the coefficients of the canonical disjunctive normal form) 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.

[3][4] The most economical in terms of the amount of computation and expedient for constructing the Zhegalkin polynomial manually is the Pascal method.

Each row of the resulting table is divided into blocks (black lines in the figure).

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 (red arrows in the figure).

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.

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 (that corresponds to the coefficient being calculated) take zero values.

Suppose, for example, that we need to find the coefficient of the xz conjunction for the function of three variables

Find the input sets in which the variable y takes a zero value.

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.

, then the tabular content of row number R is the ideal generated by element

The figure shows a function of three variables, P(A, B, C) 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: The Möbius inversion formula relates the coefficients of a Boolean sum-of-minterms expression and a Zhegalkin polynomial.

This is the partial order version of the Möbius formula, not the number theoretic.

The table below shows the binary numbers along with their associated Zhegalkin monomials and Boolean minterms: The Zhegalkin monomials are naturally ordered by divisibility, whereas the Boolean minterms do not so naturally order themselves; each one represents an exclusive eighth of the three-variable Venn diagram.

Below is shown the “XOR spreadsheet” form of the transformation, going in the direction of g to f: In 1927, in the same year as Zhegalkin's paper,[2] 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).

[6] 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[7] 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.