In Boolean algebra, the algebraic normal form (ANF), ring sum normal form (RSNF or RNF), ''

Zhegalkin normal form Zhegalkin (also Žegalkin, Gégalkine or Shegalkin) polynomials (russian: полиномы Жегалкина), also known as algebraic normal form, are a representation of functions in Boolean algebra. Introduced by the Russian mathematician Iva ...

'', or '' Reed–Muller expansion'' is a way of writing logical formulas in one of three subforms: * The entire formula is purely true or false: *:

1

0

* One or more variables are combined into a term by AND (

\and

), then one or more terms are combined by

XOR 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, , ...

(

\oplus

) together into ANF.

Negation In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and false ...

s are not permitted: :

a \oplus b \oplus \left(a \and b\right) \oplus \left(a \and b \and c\right)

* The previous subform with a purely true term: :

1 \oplus a \oplus b \oplus \left(a \and b\right) \oplus \left(a \and b \and c\right)

Formulas written in ANF are also known as

Zhegalkin polynomial Zhegalkin (also Žegalkin, Gégalkine or Shegalkin) polynomials (russian: полиномы Жегалкина), also known as algebraic normal form, are a representation of functions in Boolean algebra. Introduced by the Russian mathematician Iva ...

s and Positive Polarity (or Parity) Reed–Muller expressions (PPRM).

Common uses

ANF is a normal form, which means that two 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 The subjunctive (also known as conjunctive in some languages) is a grammatical mood, a feature of the utterance that indicates the speaker's attitude towards it. Subjunctive forms of verbs are typically used to express various states of unreality s ...

and disjunctive normal forms also require recording whether each variable is negated or not. Negation normal form is unsuitable for that purpose, since it doesn't use equality as its equivalence relation: a ∨ ¬a isn't reduced to the same thing as 1, even though they're equal. 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
/ref> : : : 1 ⊕ 1 ⊕ x ⊕ y : x ⊕ y AND (logical conjunction) is distributed algebraicallyWolframAlpha AND-equivalence demonstration: (a ⊕ b)(c ⊕ d) = ac ⊕ ad ⊕ bc ⊕ bd
/ref> : ( ⊕ ) : ⊕ : (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
/ref> (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 you only need 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: : :where

a_0, a_1, \ldots, a_ \in \^*

fully describes

f

Recursively deriving multiargument Boolean functions

There are only four functions with one argument: *

f(x)=0

f(x)=1

f(x)=x

f(x)=1 \oplus x

To represent a function with multiple arguments one can use the following equality: :

f(x_1,x_2,\ldots,x_n) = g(x_2,\ldots,x_n) \oplus x_1 h(x_2,\ldots,x_n)

, where :*

g(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n)

h(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n) \oplus f(1,x_2,\ldots,x_n)

Indeed, * if

x_1=0

then

x_1 h = 0

and so

f(0,\ldots) = f(0,\ldots)

* if

x_1=1

then

x_1 h = h

and so

f(1,\ldots) = f(0,\ldots) \oplus f(0,\ldots) \oplus f(1,\ldots)

Since both

g

and

h

have fewer arguments than

f

it follows that using this process recursively we will finish with functions with one variable. For example, let us construct ANF of

f(x,y)= x \lor y

(logical or): *

f(x,y) = f(0,y) \oplus x(f(0,y) \oplus f(1,y))

* since

f(0,y)=0 \lor y = y

and

f(1,y)=1 \lor y = 1

* it follows that

f(x,y) = y \oplus x (y \oplus 1)

* by distribution, we get the final ANF:

f(x,y) = y \oplus x y \oplus x = x \oplus y \oplus x y

Common uses

Performing operations within algebraic normal form

Converting to algebraic normal form

Formal representation

Recursively deriving multiargument Boolean functions

See also

References

Further reading