Algebraic normal form

{{Short description|Boolean polynomials as sums of monomials}}{{anchor|PPRM}}{{about|Boolean algebra|other uses|Normal form (disambiguation)}}{{more citations needed|date=July 2013}}

'''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''' ({{langx|ru|полиномы Жегалкина}})'','' or Positive Polarity (or parity) '''Reed–Muller expansions''' (PPRM).'''<ref name="Steinbach_2009" />''' These terms describe a way of writing propositional logic formulas in one of three sub-forms:

* The entire formula is purely true or false: ** <math>1</math> ** <math>0</math> * One or more variables are combined into a term by AND (<math>\and</math>), then one or more terms are combined by XOR (<math>\oplus</math>) together into ANF. Negations are not permitted: <math display="block"> a \oplus b \oplus \left(a \and b\right) \oplus \left(a \and b \and c\right) </math> * The previous subform with a purely true term: <math display="block"> 1 \oplus a \oplus b \oplus \left(a \and b\right) \oplus \left(a \and b \and c\right) </math>

Introduced by the Russian mathematician Ivan Ivanovich Zhegalkin in 1927,<ref name="Zhegalkin_1927">{{cite journal |script-title=ru:О технике вычислений предложений в символической логике |title=O Tekhnyke Vychyslenyi Predlozhenyi v Symbolytscheskoi Logykye |language=ru, fr |trans-title=On the technique of calculating propositions in symbolic logic (Sur le calcul des propositions dans la logique symbolique) |author-last=Жега́лкин [Zhegalkin] |author-first=Ива́н Ива́нович [Ivan Ivanovich] |author-link=Ivan Ivanovich Zhegalkin |journal=Matematicheskii Sbornik |location=Moscow, Russia |volume=34 |issue=1 |pages=9–28 |date=1927 |id={{mathnet|msb7433}} |url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=sm&paperid=7433&option_lang=eng |access-date=2017-10-12 |url-status=live |archive-url=https://web.archive.org/web/20171012193119/http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=sm&paperid=7433&option_lang=eng |archive-date=2017-10-12}}</ref> 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, ''x''2 = ''x''. Hence a polynomial such as 3''x''2''y''5''z'' 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,<ref name="Zhegalkin_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).<ref name="Bell_1927">{{cite journal |author-last=Bell |author-first=Eric Temple |author-link=Eric Temple Bell |title=Arithmetic of Logic |volume=29 |pages=597–611 |date=1927 |doi=10.2307/1989098 |number=3 |journal=Transactions of the American Mathematical Society |jstor=1989098 |doi-access=free}}</ref> 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<ref name="Stone_1936">{{cite journal |author-last=Stone |author-first=Marshall |author-link=Marshall Stone |title=The Theory of Representations for Boolean Algebras |journal=Transactions of the American Mathematical Society |volume=40 |pages=37–111 |date=1936 |issn=0002-9947 |doi=10.2307/1989664 |number=1 |jstor=1989664}}</ref> 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 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, span a 2''n''-dimensional vector space over the Galois field '''GF'''(2) (NB: not '''GF'''(2''n''), whose multiplication is quite different). The 22''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 {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 &or; ¬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: : ({{fontcolor|red|1 ⊕ x}}) ⊕ ({{fontcolor|green|1 ⊕ x ⊕ y}}) : {{fontcolor|red|1 ⊕ x}} ⊕ {{fontcolor|green|1 ⊕ x ⊕ y}} : 1 ⊕ 1 ⊕ x ⊕ x ⊕ y : y

NOT (logical negation) is XORing 1:<ref name="not-equiv">[http://www.wolframalpha.com/input/?i=simplify+1+xor+a WolframAlpha NOT-equivalence demonstration: ¬a = 1 ⊕ a]</ref> : {{fontcolor|red|¬}}{{fontcolor|green|(1 ⊕ x ⊕ y)}} : {{fontcolor|red|1 ⊕ }}{{fontcolor|green|(1 ⊕ x ⊕ y)}} : 1 ⊕ 1 ⊕ x ⊕ y : x ⊕ y

AND (logical conjunction) is distributed algebraically<ref name="and-equiv">[http://www.wolframalpha.com/input/?i=%28a+xor+b%29+and+%28c+xor+d%29+in+anf WolframAlpha AND-equivalence demonstration: (a ⊕ b)(c ⊕ d) = ac ⊕ ad ⊕ bc ⊕ bd]</ref> : ({{fontcolor|red|1}} ⊕ {{fontcolor|red|x}}){{fontcolor|green|(1 ⊕ x ⊕ y)}} : {{fontcolor|red|1}}{{fontcolor|green|(1 ⊕ x ⊕ y)}} ⊕ {{fontcolor|red|x}}{{fontcolor|green|(1 ⊕ x ⊕ y)}} : (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)<ref name="or-demorgans">From De Morgan's laws</ref> (easier when both operands have purely true terms) or a ⊕ b ⊕ ab<ref name="or-equiv">[http://www.wolframalpha.com/input/?i=simplify+a+xor+b+xor+%28a+and+b%29 WolframAlpha OR-equivalence demonstration: a + b = a ⊕ b ⊕ ab]</ref> (easier otherwise): : ({{fontcolor|red|1 ⊕ x}}) + ({{fontcolor|green|1 ⊕ x ⊕ y}}) : 1 ⊕ (1 ⊕ {{fontcolor|red|1 ⊕ x}})(1 ⊕ {{fontcolor|green|1 ⊕ x ⊕ y}}) : 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" |- |<math>f(x_1, x_2, \ldots, x_n) = \!</math> |<math>a_0 \oplus \!</math> |- | |<math>a_1x_1 \oplus a_2x_2 \oplus \cdots \oplus a_nx_n \oplus \!</math> |- | |<math>a_{1,2}x_1x_2 \oplus \cdots \oplus a_{n-1,n}x_{n-1}x_n \oplus \!</math> |- | |<math>\cdots \oplus \!</math> |- | |<math>a_{1,2,\ldots,n}x_1x_2\ldots x_n \!</math> |} :where <math>a_0, a_1, \ldots, a_{1,2,\ldots,n} \in \{0,1\}^*</math> fully describes <math>f</math>.

=== Recursively deriving multiargument Boolean functions === There are only four functions with one argument: * <math>f(x)=0</math> * <math>f(x)=1</math> * <math>f(x)=x</math> * <math>f(x)=1 \oplus x</math>

To represent a function with multiple arguments one can use the following equality: : <math>f(x_1,x_2,\ldots,x_n) = g(x_2,\ldots,x_n) \oplus x_1 h(x_2,\ldots,x_n)</math>, where :* <math>g(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n)</math> :* <math>h(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n) \oplus f(1,x_2,\ldots,x_n)</math>

Indeed, * if <math>x_1=0</math> then <math>x_1 h = 0</math> and so <math>f(0,\ldots) = f(0,\ldots)</math> * if <math>x_1=1</math> then <math>x_1 h = h</math> and so <math>f(1,\ldots) = f(0,\ldots) \oplus f(0,\ldots) \oplus f(1,\ldots)</math>

Since both <math>g</math> and <math>h</math> have fewer arguments than <math>f</math> it follows that using this process recursively we will finish with functions with one variable. For example, let us construct ANF of <math>f(x,y)= x \lor y</math> (logical or): * <math>f(x,y) = f(0,y) \oplus x(f(0,y) \oplus f(1,y))</math> * since <math>f(0,y)=0 \lor y = y</math> and <math>f(1,y)=1 \lor y = 1</math> * it follows that <math>f(x,y) = y \oplus x (y \oplus 1)</math> * by distribution, we get the final ANF: <math>f(x,y) = y \oplus x y \oplus x = x \oplus y \oplus x y</math>

== 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 <math>f(A,B,C) = \bar A \bar B \bar C + \bar A B \bar C + A \bar B \bar C + A B C</math>, express it as a Zhegalkin polynomial. This function can be expressed as a column vector <math display="block">\vec f = \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \end{pmatrix} . </math>

This vector should be the output of left-multiplying a vector of undetermined coefficients <math display="block"> \vec c = \begin{pmatrix} c_0 \\ c_1 \\ c_2 \\ c_3 \\ c_4 \\ c_5 \\ c_6 \\ c_7 \end{pmatrix}</math> 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: {| class="wikitable" style="padding-left: 1.5em;" !{{math|''A''}} !{{math|''B''}} !{{math|''C''}} ! !1 !{{math|''C''}} !{{math|''B''}} !{{math|''BC''}} !{{math|''A''}} !{{math|''AC''}} !{{math|''AB''}} !{{math|''ABC''}} |- |0 |0 |0 | rowspan="8" | |1 |0 |0 |0 |0 |0 |0 |0 |- |0 |0 |1 |1 |1 |0 |0 |0 |0 |0 |0 |- |0 |1 |0 |1 |0 |1 |0 |0 |0 |0 |0 |- |0 |1 |1 |1 |1 |1 |1 |0 |0 |0 |0 |- |1 |0 |0 |1 |0 |0 |0 |1 |0 |0 |0 |- |1 |0 |1 |1 |1 |0 |0 |1 |1 |0 |0 |- |1 |1 |0 |1 |0 |1 |0 |1 |0 |1 |0 |- |1 |1 |1 |1 |1 |1 |1 |1 |1 |1 |1 |} The information in the above truth table can be encoded in the following logical matrix: <math display="block"> S_3 = \begin{pmatrix} 1&0&0&0&0&0&0&0 \\ 1&1&0&0&0&0&0&0 \\ 1&0&1&0&0&0&0&0 \\ 1&1&1&1&0&0&0&0 \\ 1&0&0&0&1&0&0&0 \\ 1&1&0&0&1&1&0&0 \\ 1&0&1&0&1&0&1&0 \\ 1&1&1&1&1&1&1&1 \end{pmatrix}</math> where the 'S' here stands for "Sierpiński", as in Sierpiński triangle, and the subscript 3 gives the exponents of its size: <math>2^3 \times 2^3</math>.

It can be proven through mathematical induction and block-matrix multiplication that any such "Sierpiński matrix" <math>S_n</math> is its own inverse.<ref name="NB1" group="nb" />

Then the linear system is <math display="block"> S_3 \vec c = \vec f</math> which can be solved for <math>\vec c</math>:{{clarify|date=March 2024}} <math display="block"> \vec c = S_3^{-1} \vec f = S_3 \vec f = \begin{pmatrix} 1&0&0&0&0&0&0&0 \\ 1&1&0&0&0&0&0&0 \\ 1&0&1&0&0&0&0&0 \\ 1&1&1&1&0&0&0&0 \\ 1&0&0&0&1&0&0&0 \\ 1&1&0&0&1&1&0&0 \\ 1&0&1&0&1&0&1&0 \\ 1&1&1&1&1&1&1&1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 1 \oplus 1 \\ 1 \oplus 1 \\ 1 \oplus 1 \\ 1 \oplus 1 \\ 1 \oplus 1 \oplus 1 \\ 1 \oplus 1 \oplus 1 \oplus 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \end{pmatrix},</math> and the Zhegalkin polynomial corresponding to <math>\vec c</math> is <math>1 \oplus C \oplus AB</math>.

=== 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 === thumb|250x250px|Computing the Zhegalkin polynomial for an example function ''P'' by the table method Let <math>c_0, \dots , c_{2^n-1}</math> be the outputs of a truth table for the function ''P'' of ''n'' variables, such that the index of the <math>c_i</math>'s corresponds to the binary indexing of the minterms.<ref name="NB2" group="nb" /> Define a function ζ recursively by: <math display="block"> \zeta(c_i) := c_i</math> <math display="block"> \zeta(c_0, \dots , c_k) := \zeta(c_0, \dots , c_{k - 1}) \oplus \zeta(c_1, \dots , c_k). </math> Note that <math display="block"> \zeta(c_0, \dots , c_m) = \bigoplus_{k = 0}^m {m \choose k}_2 c_k </math> where <math display="inline">{m \choose k}_2</math> is the binomial coefficient reduced modulo 2.

Then <math display="block"> g_i = \zeta(c_0, \dots , c_i) </math> 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 <math>c_0, \dots , c_{2^n-1}</math> given the coefficients <math>g_0, \dots , g_{2^n-1}</math>. Just let <math display="block"> c_i = \zeta(g_0, \dots , g_i). </math>

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 [http://mathworld.wolfram.com/Rule102.html 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.<ref name="Suprun_1987">{{cite journal |title=Tablichnyy metod polinomial'nogo razlozheniya bulevykh funktsiy |language=ru |script-title=ru:Табличный метод полиномиального разложения булевых функций |trans-title=The tabular method of polynomial decomposition of Boolean functions |author-first=Valeriy P. [Валерий Павлович] |author-last=Suprun [Супрун] |journal=Kibernetika [Кибернетика] (Cybernetics) |date=1987 |number=1 |pages=116–117}}</ref><ref name="Suprun_2017">{{cite journal |title=Osnovy teorii bulevykh funktsiy |script-title=ru:Основы теории булевых функций |language=ru |trans-title=Fundamentals of the theory of Boolean functions |author-first=Valeriy P. [Валерий Павлович] |author-last=Suprun [Супрун] |journal=М.: Lenand [Ленанд] / URSS |date=2017 |page=208}}</ref>

=== The Pascal method === [[File:Построение_полинома_Жегалкина_методом_Паскаля.PNG|thumb|250x250px|Using the Pascal method to compute the Zhegalkin polynomial for the Boolean function <math>\bar a \bar b \bar c + \bar a b \bar c + \bar a b c + a b \bar c</math>. The line in Russian at the bottom says:

<math>\oplus</math> – bitwise operation "Exclusive OR"]] 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 <math>2^N</math> columns and <math>N + 1</math> 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 === thumb|250x250px|Graphic representation of the coefficients of the Zhegalkin polynomial for functions with different numbers of variables. 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 <math>f(x, y, z)</math>. 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

<math display="block">a_5 = f_0 \oplus f_1 \oplus f_4 \oplus f_5 = f(0,0,0) \oplus f(0,0,1) \oplus f(1,0,0) \oplus f(1,0,1) </math>

Since there are no variables with the constant term, <math display="block">a_0 = f_0.</math>

For a term which includes all variables, the sum includes all values of the function: <math display="block">a_{N - 1} = f_0 \oplus f_1 \oplus f_2 \oplus \dots \oplus f_{N-2} \oplus f_{N-1} </math>

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 <math>T_N</math>, 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 <math>N-1</math> variables. The new table <math>T_N + 1</math> is arranged as a 2 × 2 matrix of <math>T_N</math> tables, and the right upper block of the matrix is cleared.

==== Lattice-theoretic interpretation ==== Consider the columns of a table <math>T_N</math> as corresponding to elements of a Boolean lattice of size <math>2^N</math>. For each column <math>f_M</math> express number ''M'' as a binary number <math>M_2</math>, then <math>f_M \le f_K</math> if and only if <math>M_2 \vee K_2 = K_2</math>, where <math>\vee</math> denotes bitwise OR.

If the rows of table <math>T_N</math> are numbered, from top to bottom, with the numbers from 0 to <math>2^N - 1</math>, then the tabular content of row number ''R'' is the ideal generated by element <math>f_R</math> of the lattice.

Note incidentally that the overall pattern of a table <math>T_N</math> is that of a logical matrix Sierpiński triangle. Also, the pattern corresponds to an elementary cellular automaton called [http://mathworld.wolfram.com/Rule60.html Rule 60], starting with the leftmost cell set to 1 and all other cells cleared.

=== Using a Karnaugh map === thumb|250x250px|Converting a Karnaugh map to a Zhegalkin polynomial. 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:

* 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 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 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:<ref name="Möbius_2021">{{cite encyclopedia |title=Möbius inversion |encyclopedia=Encyclopedia of Mathematics |date=2021-02-17 |orig-date=2011-02-07 |url=http://encyclopediaofmath.org/index.php?title=M%C3%B6bius_inversion&oldid=50404 |access-date=2021-03-27 |url-status=live |archive-url=https://web.archive.org/web/20200716094655/https://encyclopediaofmath.org/wiki/M%C3%B6bius_inversion |archive-date=2020-07-16}}</ref> <math display="block"> g(x) = \sum_{y:y\le x} f(y) \leftrightarrow f(x) = \sum_{y:y\le x} g(y) \mu(y,x),</math> where <math>\mu(y,x) = (-1)^{|x| - |y|}</math>, |''x''| being the Hamming distance of ''x'' from 0. Since <math>-1 \equiv 1</math> 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 generated by that number: <math>\langle x \rangle</math>. Since summation is modulo 2, the formula can be restated as <math display="block"> g(x) = \bigoplus_{y:y\in \langle x\rangle} f(y) \leftrightarrow f(x) = \bigoplus_{y:y\in \langle x\rangle} g(y) </math>

=== Example === As an example, consider the three-variable case. The following table shows the divisibility relation: {| class="wikitable" !''x'' !divisors of ''x'' |- |000 |000 |- |001 |000, 001 |- |010 |000, 010 |- |011 |000, 001, 010, 011 |- |100 |000, 100 |- |101 |000, 001, 100, 101 |- |110 |000, 010, 100, 110 |- |111 |000, 001, 010, 011, 100, 101, 110, 111 |} Then <math display="block">\begin{align} g(000) &= f(000) \\[1ex] g(001) &= f(000) \oplus f(001) \\[1ex] g(010) &= f(000) \oplus f(010) \\[1ex] g(011) &= f(000) \oplus f(001) \oplus f(010) \oplus f(011) \\[1ex] g(100) &= f(000) \oplus f(100) \\[1ex] g(101) &= f(000) \oplus f(001) \oplus f(100) \oplus(101) \\[1ex] g(110) &= f(000) \oplus f(010) \oplus f(100) \oplus f(110) \\[1ex] g(111) &= f(000) \oplus f(001) \oplus f(010) \oplus f(011) \oplus f(100) \oplus f(101) \oplus f(110) \oplus f(111) \end{align}</math>

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: {| class="wikitable" !Boolean minterm !ABC !Zhegalkin monomial |- |<math>\bar A \bar B \bar C</math> |000 |1 |- |<math>\bar A \bar B C</math> |001 |C |- |<math>\bar A B \bar C</math> |010 |B |- |<math>\bar A B C </math> |011 |BC |- |<math>A \bar B \bar C</math> |100 |A |- |<math>A \bar B C</math> |101 |AC |- |<math>A B \bar C</math> |110 |AB |- |<math>A B C</math> |111 |ABC |} 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. The ordering of the monomials transfers to the bit strings as follows: given <math>a_1 a_2 a_3</math> and <math>b_1 b_2 b_3</math>, a pair of bit triplets, then <math>a_1 a_2 a_3 \le b_1 b_2 b_3 \leftrightarrow a_1 \le b_1 \wedge a_2 \le b_2 \wedge a_3 \le b_3</math>.

The correspondence between a three-variable Boolean sum-of-minterms and a Zhegalkin polynomial is then: <math display="block">\begin{align} &f(000) \bar A \bar B \bar C \vee f(001) \bar A \bar B C \vee f(010) \bar A B \bar C \vee f(011) \bar A B C \vee f(100) A \bar B \bar C \vee f(101) A \bar B C \vee f(110) A B \bar C \vee f(111) A B C \\[1ex] &\qquad \equiv g(000) \oplus g(001) C \oplus g(010) B \oplus g(011) BC \oplus g(100) A \oplus g(101) AC \oplus g(110) AB \oplus g(111) ABC. \end{align}</math>

The system of equations above may be summarized as a logical matrix equation:

<math display="block"> \begin{pmatrix} g(000) \\ g(001) \\ g(010) \\ g(011) \\ g(100) \\ g(101) \\ g(110) \\ g(111) \end{pmatrix} = \begin{pmatrix} 1 && 0 && 0 && 0 && 0 && 0 && 0 && 0 \\ 1 && 1 && 0 && 0 && 0 && 0 && 0 && 0 \\ 1 && 0 && 1 && 0 && 0 && 0 && 0 && 0 \\ 1 && 1 && 1 && 1 && 0 && 0 && 0 && 0 \\ 1 && 0 && 0 && 0 && 1 && 0 && 0 && 0 \\ 1 && 1 && 0 && 0 && 1 && 1 && 0 && 0 \\ 1 && 0 && 1 && 0 && 1 && 0 && 1 && 0 \\ 1 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \end{pmatrix} \begin{pmatrix} f(000) \\ f(001) \\ f(010) \\ f(011) \\ f(100) \\ f(101) \\ f(110) \\ f(111) \end{pmatrix} </math>

which N. J. Wildberger calls a Boole–Möbius transformation.

Below is shown the "XOR spreadsheet" form of the transformation, going in the direction of ''g'' to ''f'': {| class="wikitable" style="overflow-x: scroll;" !<math>f_{000}</math> !<math>f_{001}</math> !<math>f_{010}</math> !<math>f_{011}</math> !<math>f_{100}</math> !<math>f_{101}</math> !<math>f_{110}</math> !<math>f_{111}</math> |- !<math>g_{000}</math> |<math>g_{000} \oplus g_{001} </math> |<math>g_{000} \oplus g_{010} </math> |<math>g_{000} \oplus g_{010} \oplus g_{001} \oplus g_{011} </math> |<math>g_{000} \oplus g_{100} </math> |<math>g_{000} \oplus g_{100} \oplus g_{001} \oplus g_{101} </math> |<math>g_{000} \oplus g_{100} \oplus g_{010} \oplus g_{110} </math> |<math>g_{000} \oplus g_{100} \oplus g_{010} \oplus g_{110} \oplus g_{001} \oplus g_{101} \oplus g_{011} \oplus g_{111} </math> |- !<math>g_{001} </math> |<math>g_{001} \oplus g_{010} </math> |<math>g_{001} \oplus g_{011} </math> |<math>g_{001} \oplus g_{011} \oplus g_{010} \oplus g_{100} </math> |<math>g_{001} \oplus g_{101} </math> |<math>g_{001} \oplus g_{101} \oplus g_{010} \oplus g_{110} </math> |<math>g_{001} \oplus g_{101} \oplus g_{011} \oplus g_{111} </math> |- !<math>g_{010} </math> |<math>g_{010} \oplus g_{011} </math> |<math>g_{010} \oplus g_{100} </math> |<math>g_{010} \oplus g_{100} \oplus g_{011} \oplus g_{101} </math> |<math>g_{010} \oplus g_{110} </math> |<math>g_{010} \oplus g_{110} \oplus g_{011} \oplus g_{111} </math> |- !<math>g_{011} </math> |<math>g_{011} \oplus g_{100} </math> |<math>g_{011} \oplus g_{101} </math> |<math>g_{011} \oplus g_{101} \oplus g_{100} \oplus g_{110} </math> |<math>g_{011} \oplus g_{111} </math> |- !<math>g_{100} </math> |<math>g_{100} \oplus g_{101} </math> |<math>g_{100} \oplus g_{110} </math> |<math>g_{100} \oplus g_{110} \oplus g_{101} \oplus g_{111} </math> |- !<math>g_{101} </math> |<math>g_{101} \oplus g_{110} </math> |<math>g_{101} \oplus g_{111} </math> |- !<math>g_{110} </math> |<math>g_{110} \oplus g_{111} </math> |- !<math>g_{111} </math> |}

== Notes == {{reflist|group="nb"|refs=<ref group="nb" name="NB1">As base case, <math display="block"> S_0 := \begin{pmatrix} 1 \end{pmatrix}</math> <math display="block"> (S_0)^2 = \begin{pmatrix} 1 \end{pmatrix} = I_0 </math> where <math>I_n</math> is here taken to denote the identity matrix of size <math>2^n \times 2^n</math>. The inductive assumption is <math display="block"> (S_n)^2 = I_n .</math> Then the inductive step is: <math display="block"> S_{n+1} := \begin{pmatrix} S_n & O \\ S_n & S_n \end{pmatrix} \equiv \begin{pmatrix} 1 & 0 \\ 1 & 1\end{pmatrix} \otimes S_n,</math> where <math>\otimes</math> denotes the Kronecker product, <math display="block"> (S_{n+1})^2 = \begin{pmatrix} S_n & O \\ S_n & S_n \end{pmatrix} \begin{pmatrix} S_n & O \\ S_n & S_n \end{pmatrix} = \begin{pmatrix}S_n S_n \oplus O S_n & S_n O \oplus O S_n \\ S_n S_n \oplus S_n S_n & S_n O \oplus S_n S_n \end{pmatrix} = \begin{pmatrix} I_n & O \\ I_n \oplus I_n & I_n \end{pmatrix} = \begin{pmatrix}I_n & O \\ O & I_n\end{pmatrix} = I_{n+1},</math> or, in terms of the Kronecker product: <math display="block"> S_{n+1}^2 = (S_1 \otimes S_n) (S_1 \otimes S_n) = S_1^2 \otimes S_n^2 = I_1 \otimes I_n = I_{n+1}.</math> Q.E.D.</ref> <ref group="nb" name="NB2">A minterm is the Boolean counterpart of a Zhegalkin monomial. For an ''n''-variable context, there are <math>2^n</math> Zhegalkin monomials and <math>2^n</math> Boolean minterms as well. A minterm for an ''n''-variable context consists of an AND-product of ''n'' literals, each literal either being a variable in the context or the NOT-negation of such a variable. Moreover, for each variable in the context there must appear exactly once in each minterm a corresponding literal (either the assertion or negation of that variable). A truth table for a Boolean function of ''n'' variables has exactly <math>2^n</math> rows, the inputs of each row corresponding naturally to a minterm whose context is the set of independent variables of that Boolean function. (Each 0-input corresponds to a negated variable; each 1-input corresponds to an asserted variable.)     Any Boolean expression may be converted to sum-of-minterms form by repeatedly distributing AND with respect to OR, NOT with respect to AND or OR (through the De Morgan identities), cancelling out double negations (cf. negation normal form); and then, when a sum-of-products has been obtained, multiply products with missing literals with instances of the law of excluded middle that contain the missing literals; then — lastly — distribute AND with respect to OR again.     Note that there is a formal correspondence, for a given context, between Zhegalkin monomials and Boolean minterms. However, the correspondence is not logical equivalence. For example, for the context {''A'', ''B'', ''C''}, there is a formal correspondence between the Zhegalkin monomial ''AB'' and the Boolean minterm <math>A B \bar C</math>, but they are not logically equivalent. (For more of this example, see the second table in the section "Möbius transformation". The same set of bitstrings is used to index both the set of Boolean minterms and the set of Zhegalkin monomials.)</ref>}}

== Reed–Muller expansions and related research ==

The algebraic normal form described above uses positive polarity exclusively: each variable appears only in uncomplemented form. More generally, a '''fixed-polarity Reed–Muller (FPRM) expansion''' allows each variable to appear in either complemented or uncomplemented form, with the polarity fixed across all terms. Choosing different polarities yields 2''n'' distinct FPRM representations for a function of ''n'' variables. An '''exclusive-or sum-of-products (ESOP)''' expansion further generalizes by allowing mixed polarities within the same expression, where each product term may independently use complemented or uncomplemented literals. ESOP minimization—finding the representation with the fewest product terms—is an active area of research in logic synthesis and has applications in reversible and quantum circuit design.

Since 1993, the International Workshop on Boolean Problems (originally the Reed–Muller Workshop) has been held biennially, bringing together researchers working on Reed–Muller expansions, ESOP minimization, and related topics in switching theory and logic synthesis.<ref>{{cite web |title=Reed–Muller Workshop History |url=https://www.lsi-cad.com/RM/RM_history.html |access-date=2026-04-15}}</ref>

== References == <references>

<ref name="Steinbach_2009">{{cite book |author-first1=Bernd |author-last1=Steinbach |author-link1=:de:Bernd Steinbach |author-first2=Christian |author-last2=Posthoff |title=Logic Functions and Equations - Examples and Exercises |chapter=Preface |publisher=Springer Science + Business Media B. V. |date=2009 |edition=1st |isbn=978-1-4020-9594-8 |lccn=2008941076 |page=xv}}</ref>

</references>

== Further reading== * {{cite book |author-first=Ingo |author-last=Wegener |authorlink = Ingo Wegener|title=The complexity of Boolean functions |publisher=Wiley-Teubner |date=1987 |isbn=3-519-02107-2 |page=6 |url=http://ls2-www.cs.uni-dortmund.de/monographs/bluebook}} * {{cite web |title=Presentation |publisher=University of Duisburg-Essen |language=German |url=http://www.is.informatik.uni-duisburg.de/courses/infoa_ss03/slides/02-slides.pdf#page=34 |access-date=2017-04-19 |url-status=live |archive-url=https://web.archive.org/web/20170420000915/http://www.is.informatik.uni-duisburg.de/courses/infoa_ss03/slides/02-slides.pdf#page=34 |archive-date=2017-04-20}} * {{cite web |title=Reed-Muller Logic |work=Logic 101 |at=Part 3 |author-first=Clive "Max" |author-last=Maxfield |date=2006-11-29 |publisher=EETimes |url=http://www.eetimes.com/author.asp?section_id=216&doc_id=1274545 |access-date=2017-04-19 |url-status=live |archive-url=https://web.archive.org/web/20170419235904/http://www.eetimes.com/author.asp?section_id=216&doc_id=1274545 |archive-date=2017-04-19}} * {{cite book |author-last=Gindikin [Гиндикин] |author-first=Semen Grigorʹevich [Семен Г.] |url=https://archive.org/details/algebraiclogic0000gind |title=Algebraic logic |date=1972 |publisher=[[Nauka (publisher)|Наука [Nauka]]] |isbn=0-387-96179-8 |edition=1 |location=Moscow, Russia |language=ru |script-title=ru:алгебра логики в задачах |trans-title=Algebraic Logic |url-access=registration}} (288 pages) (NB. Translation: Springer-Verlag, 1985.[https://archive.org/details/algebraiclogic0000gind]) * {{cite book |author-last1=Perkowski |author-first1=Marek A. |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.4349&rep=rep1&type=pdf |title=A Survey of Literature on Function Decomposition |author-last2=Grygiel |author-first2=Stanislaw |date=1995-11-20 |publisher=Functional Decomposition Group, Department of Electrical Engineering, Portland University, Portland, Oregon, USA |version=Version IV |pages=21–22 |chapter=6. Historical Overview of the Research on Decomposition |citeseerx=10.1.1.64.1129}} (188 pages) * {{cite journal |author-link=Ivan Ivanovich Zhegalkin |date=1927 |title=O Tekhnyke Vychyslenyi Predlozhenyi v Symbolytscheskoi Logykye |script-title=ru:О технике вычислений предложений в символической логике |trans-title=On the technique of calculating propositions in symbolic logic (Sur le calcul des propositions dans la logique symbolique) |url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=sm&paperid=7433&option_lang=eng |url-status=live |journal=Matematicheskii Sbornik |language=ru, fr |location=Moscow, Russia |volume=34 |issue=1 |pages=9–28 |id={{mathnet|msb7433}} |archive-url=https://web.archive.org/web/20171012193119/http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=sm&paperid=7433&option_lang=eng |archive-date=2017-10-12 |access-date=2017-10-12 |author-last=Жега́лкин [Zhegalkin] |author-first=Ива́н Ива́нович [Ivan Ivanovich]}} * {{cite journal |author-link=Irving Stoy Reed |date=September 1954 |title=A Class of Multiple-Error Correcting Codes and the Decoding Scheme |journal=IRE Transactions on Information Theory |volume=IT-4 |pages=38–49 |author-first=Irving Stoy |author-last=Reed}} * {{cite journal |author-link=David Eugene Muller |date=September 1954 |title=Application of Boolean Algebra to Switching Circuit Design and to Error Detection |journal=IRE Transactions on Electronic Computers |volume=EC-3 |pages=6–12 |author-first=David Eugene |author-last=Muller}} * {{cite journal |date=1993 |title=Efficient graph-based computation and manipulation of functional decision diagrams |journal=Proceedings of the 4th European Conference on Design Automation |pages=278–282 |author-last1=Kebschull |author-first1=Udo |author-last2=Rosenstiel |author-first2=Wolfgang}} * {{cite web |author-last=Maxfield |author-first=Clive "Max" |date=2006-11-29 |title=Reed-Muller Logic |url=http://www.eetimes.com/author.asp?section_id=216&doc_id=1274545 |url-status=live |archive-url=https://web.archive.org/web/20170419235904/http://www.eetimes.com/author.asp?section_id=216&doc_id=1274545 |archive-date=2017-04-19 |access-date=2017-04-19 |work=Logic 101 |publisher=EETimes |at=Part 3}} * {{cite book |author-last1=Steinbach |author-first1=Bernd |author-link1=:de:Bernd Steinbach |title=Logic Functions and Equations - Examples and Exercises |author-last2=Posthoff |author-first2=Christian |date=2009 |publisher=Springer Science + Business Media B. V. |isbn=978-1-4020-9594-8 |edition=1st |page=xv |chapter=Preface |lccn=2008941076}} * {{cite book |author-last1=Perkowski |author-first1=Marek A. |title=A Survey of Literature on Function Decomposition |author-last2=Grygiel |author-first2=Stanislaw |date=1995-11-20 |publisher=Functional Decomposition Group, Department of Electrical Engineering, Portland University, Portland, Oregon, USA |version=Version IV |pages=21–22 |chapter=6. Historical Overview of the Research on Decomposition |citeseerx=10.1.1.64.1129}} (188 pages)

Category:Boolean algebra Category:Normal forms (logic)

ru:Полином Жегалкина