Algebraic normal form (ANF) is a representation of functions in boolean algebra. Formulas written in ANF are also known as ring sum normal form (RSNF or RNF), Zhegalkin polynomials (), or Positive Polarity (or parity) Reed–Muller expansions (PPRM). These terms describe a way of writing propositional logic formulas in one of three sub-forms:
The entire formula is purely true or false:
One or more variables are combined into a term by AND (), then one or more terms are combined by XOR () together into ANF. Negations are not permitted: The previous subform with a purely true term:
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.
History Prior to 1927, Boolean algebra had been considered a calculus of logical values with logical operations of conjunction, disjunction, 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 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.
For example, the Boolean 2-out-of-3 threshold or median operation is written as the Zhegalkin polynomial xy⊕yz⊕zx.
In 1927, 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 (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 over the next few years.
Formal properties
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.
Common uses ANF is a canonical form, which means that two logically equivalent formulas will convert to the same ANF, easily showing whether two formulas are equivalent for automated theorem proving. Unlike other normal forms, it can be represented as a simple list of lists of variable names—conjunctive and disjunctive normal forms also require recording whether each variable is negated or not. Negation normal form is unsuitable for determining equivalence, since on negation normal forms, equivalence does not imply equality: a ∨ ¬a is not reduced to the same thing as 1, even though they are logically equivalent.
Putting a formula into ANF also makes it easy to identify linear functions (used, for example, in linear-feedback shift registers): a linear function is one that is a sum of single literals. Properties of nonlinear-feedback shift registers can also be deduced from certain properties of the feedback function in ANF.
Performing operations within algebraic normal form There are straightforward ways to perform the standard Boolean operations on ANF inputs in order to get ANF results.
XOR (logical exclusive disjunction) is performed directly: () ⊕ () ⊕ 1 ⊕ 1 ⊕ x ⊕ x ⊕ y y
NOT (logical negation) is XORing 1:WolframAlpha NOT-equivalence demonstration: ¬a = 1 ⊕ a
1 ⊕ 1 ⊕ x ⊕ y x ⊕ y
AND (logical conjunction) is distributed algebraicallyWolframAlpha AND-equivalence demonstration: (a ⊕ b)(c ⊕ d) = ac ⊕ ad ⊕ bc ⊕ bd ( ⊕ ) ⊕ (1 ⊕ x ⊕ y) ⊕ (x ⊕ x ⊕ xy) 1 ⊕ x ⊕ x ⊕ x ⊕ y ⊕ xy 1 ⊕ x ⊕ y ⊕ xy
OR (logical disjunction) uses either 1 ⊕ (1 ⊕ a)(1 ⊕ b)From De Morgan's laws (easier when both operands have purely true terms) or a ⊕ b ⊕ abWolframAlpha OR-equivalence demonstration: a + b = a ⊕ b ⊕ ab (easier otherwise): () + () 1 ⊕ (1 ⊕ )(1 ⊕ ) 1 ⊕ x(x ⊕ y) 1 ⊕ x ⊕ xy
Converting to algebraic normal form Each variable in a formula is already in pure ANF, so one only needs to perform the formula's Boolean operations as shown above to get the entire formula into ANF. For example: x + (y ⋅ ¬z) x + (y(1 ⊕ z)) x + (y ⊕ yz) x ⊕ (y ⊕ yz) ⊕ x(y ⊕ yz) x ⊕ y ⊕ xy ⊕ yz ⊕ xyz
Formal representation ANF is sometimes described in an equivalent way: {| cellpadding="4"
where fully describes .
Recursively deriving multiargument Boolean functions There are only four functions with one argument:
To represent a function with multiple arguments one can use the following equality: , where
Indeed, if then and so if then and so
Since both and have fewer arguments than it follows that using this process recursively we will finish with functions with one variable. For example, let us construct ANF of (logical or):
since and it follows that by distribution, we get the final ANF:
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 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 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: 10001000000000111000000010101000000111111000010010001000101110011001101010101011111111111 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 (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
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 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, this method of calculation corresponds to the method of operation of the elementary cellular automaton called 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.