Zhegalkin (also Žegalkin, Gégalkine or Shegalkin
) polynomials (russian: полиномы Жегалкина), also known as
algebraic normal form, are a representation of functions in
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
. Introduced by the Russian mathematician
Ivan Ivanovich Zhegalkin in 1927,
they are the
polynomial ring
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables ...
over the
integers modulo 2. The resulting degeneracies of
modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his boo ...
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''
2 = ''x''. Hence a polynomial such as 3''x''
2''y''
5''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 value
In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values (''true'' or '' false'').
Computing
In some progra ...
s with logical operations of
conjunction
Conjunction may refer to:
* Conjunction (grammar), a part of speech
* Logical conjunction, a mathematical operator
** Conjunction introduction, a rule of inference of propositional logic
* Conjunction (astronomy), in which two astronomical bodies ...
,
disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
,
negation, and so on. 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
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , , ...
as arithmetic addition mod 2, (written here as ''x''⊕''y'' to avoid confusion with the common use of + as a synonym for inclusive-or ∨). The logical complement ¬''x'' is then ''x''⊕1. Since ∧ and ¬ form a basis for Boolean algebra, all other logical operations are compositions of these basic operations, and so the polynomials of ordinary algebra can represent all Boolean operations, allowing Boolean reasoning to be performed using
elementary algebra
Elementary algebra encompasses the basic concepts of algebra. It is often contrasted with arithmetic: arithmetic deals with specified numbers, whilst algebra introduces variables (quantities without fixed values).
This use of variables entail ...
.
For example, the Boolean 2-out-of-3 threshold or
median operation is written as the Zhegalkin polynomial ''xy''⊕''yz''⊕''zx''.
Formal properties
Formally a ''Zhegalkin monomial'' is the product of a finite set of distinct variables (hence
square-free {{no footnotes, date=December 2015
In mathematics, a square-free element is an element ''r'' of a unique factorization domain ''R'' that is not divisible by a non-trivial square. This means that every ''s'' such that s^2\mid r is a unit of ''R''.
A ...
), 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
In the theory of vector spaces, a set of vectors is said to be if there is a nontrivial linear combination of the vectors that equals the zero vector. If no such linear combination exists, then the vectors are said to be . These concepts are ...
, span a 2
''n''-dimensional
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
over the
Galois field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
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 , 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 In mathematics, a free Boolean algebra is a Boolean algebra with a distinguished set of elements, called ''generators'', such that:
#Each element of the Boolean algebra can be expressed as a finite combination of generators, using the Boolean opera ...
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
There are various known methods generally used for the computation of the Zhegalkin polynomial:
*
Using the method of indeterminate coefficients
*
By constructing the canonical disjunctive normal form
*
By using tables
*
Pascal method
*
Summation method
In mathematics, a divergent series is an infinite series that is not convergent, meaning that the infinite sequence of the partial sums of the series does not have a finite limit.
If a series converges, the individual terms of the series must ...
*
Using a Karnaugh map
The method of indeterminate coefficients
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
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets.
Matrix representation ...
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
The Sierpiński triangle (sometimes spelled ''Sierpinski''), also called the Sierpiński gasket or Sierpiński sieve, is a fractal attractive fixed set with the overall shape of an equilateral triangle, subdivided recursively into smaller equi ...
, 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 (a fully expanded
disjunctive normal form
In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or (in philosophical logic) a ''cluster c ...
) 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
minterm
In Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form ( CDNF) or minterm canonical form and its dual canonical conjunctive normal form ( CCNF) or maxterm canonical form. Other canonical forms include ...
s.
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 (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.
As an aside, note that this method of calculation corresponds to the method of operation of the
elementary cellular automaton
In mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states (labeled 0 and 1) and the rule to determine the state of a cell in the next generation depends o ...
calle
Rule 102 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.
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 (black lines in the figure). 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 (green arrows 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). 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 (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
. 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 (000, 001, 100, 101). 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 (see figure). 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
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considere ...
generated by element
of the lattice.
Note incidentally that the overall pattern of a table
is that of a
logical matrix
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets.
Matrix representation ...
Sierpiński triangle
The Sierpiński triangle (sometimes spelled ''Sierpinski''), also called the Sierpiński gasket or Sierpiński sieve, is a fractal attractive fixed set with the overall shape of an equilateral triangle, subdivided recursively into smaller equi ...
. Also, the pattern corresponds to an
elementary cellular automaton
In mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states (labeled 0 and 1) and the rule to determine the state of a cell in the next generation depends o ...
calle
Rule 60 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''(''A'', ''B'', ''C'') represented as a
Karnaugh map
The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logi ...
, 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:
* We consider all the cells of the Karnaugh map in ascending order of the number of units in their codes. For the function of three variables, the sequence of cells will be 000–100–010–001–110–101–011–111. Each cell of the Karnaugh map is associated with a member of the Zhegalkin polynomial depending on the positions of the code in which there are ones. For example, cell 111 corresponds to the member ABC, cell 101 corresponds to the member AC, cell 010 corresponds to the member B, and cell 000 corresponds to member 1.
* If the cell in question is 0, go to the next cell.
* If the cell in question is 1, add the corresponding term to the Zhegalkin polynomial, then invert all cells in the Karnaugh map where this term is 1 (or belonging to the
ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considere ...
generated by this term, in a Boolean lattice of monomials) and go to the next cell. For example, if, when examining cell 110, a one appears in it, then the term AB is added to the Zhegalkin polynomial and all cells of the Karnaugh map are inverted, for which A = 1 and B = 1. If unit is in cell 000, then a term 1 is added to the Zhegalkin polynomial and the entire Karnaugh map is inverted.
* The transformation process can be considered complete when, after the next inversion, all cells of the Karnaugh map become zero, or a don't care condition.
Möbius transformation
The
Möbius inversion formula
In mathematics, the classic Möbius inversion formula is a relation between pairs of arithmetic functions, each defined from the other by sums over divisors. It was introduced into number theory in 1832 by August Ferdinand Möbius.
A large gener ...
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 Möbius inversion formula for partial orders is:
:
,
where
, , ''x'', being the
Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chan ...
of ''x'' from 0. Since
in the Zhegalkin algebra, the Möbius function collapses to being the constant 1.
The set of divisors of a given number ''x'' is also the
order ideal
In mathematical order theory, an ideal is a special subset of a partially ordered set (poset). Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different not ...
generated by that number:
. Since summation is modulo 2, the formula can be restated as
:
Example
As an example, consider the three-variable case. The following table shows the divisibility relation:
Then
:
:
:
:
:
:
:
:
The above system of equations can be solved for ''f'', and the result can be summarized as being obtainable by exchanging ''g'' and ''f'' throughout the above system.
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
A Venn diagram is a widely used diagram style that shows the logical relation between sets, popularized by John Venn (1834–1923) in the 1880s. The diagrams are used to teach elementary set theory, and to illustrate simple set relationships ...
. The ordering of the monomials transfers to the bit strings as follows: given
and
, a pair of bit triplets, then
.
The correspondence between a three-variable Boolean sum-of-minterms and a Zhegalkin polynomial is then:
:
:
.
The system of equations above may be summarized as a
logical matrix
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets.
Matrix representation ...
equation:
:
which
N. J. Wildberger calls a Boole–Möbius transformation.
Below is shown the “XOR
spreadsheet
A spreadsheet is a computer application for computation, organization, analysis and storage of data in tabular form. Spreadsheets were developed as computerized analogs of paper accounting worksheets. The program operates on data entered in c ...
” form of the transformation, going in the direction of ''g'' to ''f'':
Related work
In 1927, in the same year as Zhegalkin's paper,
the American mathematician
Eric Temple Bell
Eric Temple Bell (7 February 1883 – 21 December 1960) was a Scottish-born mathematician and science fiction writer who lived in the United States for most of his life. He published non-fiction using his given name and fiction as John Tain ...
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
Marshall Harvey Stone (April 8, 1903 – January 9, 1989) was an American mathematician who contributed to real analysis, functional analysis, topology and the study of Boolean algebras.
Biography
Stone was the son of Harlan Fiske Stone, who wa ...
in 1936
when he observed while writing up his celebrated
Stone duality theorem that the supposedly loose analogy between
Boolean algebras and
rings
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
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.
See also
*
Algebraic normal form (ANF)
*
Reed-Muller expansion
*
Boolean domain
In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include ''false'' and ''true''. In logic, mathematics and theoretical computer science, a Boolean domain is usually written as ...
*
Boolean-valued function
A Boolean-valued function (sometimes called 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, i.e. a generic two-element set, (for example B = ), whose elements are i ...
Notes
References
Further reading
* (288 pages) (NB. Translation:
Springer-Verlag
Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing.
Originally founded in 1842 ...
, 198
* {{cite book , title=A Survey of Literature on Function Decomposition , chapter=6. Historical Overview of the Research on Decomposition , version=Version IV , author-first1=Marek A. , author-last1=Perkowski , author-first2=Stanislaw , author-last2=Grygiel , publisher=Functional Decomposition Group, Department of Electrical Engineering, Portland University, Portland, Oregon, USA , date=1995-11-20 , citeseerx=10.1.1.64.1129 , pages=21–22 , url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.4349&rep=rep1&type=pdf (188 pages)
Boolean algebra
Logic