- Algebraic normal form
In
Boolean logic , the algebraic normal form (ANF) is a method of standardizing and normalizing logical formulas. As anormal form , it can be used inautomated theorem proving (ATP), but is more commonly used in the design of cryptographicrandom number generator s, specificallylinear feedback shift register s (LFSRs). A logicalformula is considered to be in ANF if and only if it is a single algebraic sum (XOR ) of a constant a_0 and one or more conjunctions of the function arguments. ANF is also known as "Zhegalkin polynomial s" ( _ru. полиномы Жегалкина) and as "Positive Polarity (or Parity) Reed-Muller" expression.Putting a formula into ANF makes it easy to identify
linear functions, as is needed for linear feedback in LFSRs: a linear function is one that is a sum of literals. Properties of nonlinear feedbackshift register s can also be deduced from certain properties of the feedback function in ANF.The general ANF can be written as:where a_0, a_1, ldots, a_{1,2,ldots,n} in {0,1}^* fully describes f.
For each function f there is a unique ANF. There are only four functions with one argument: f(x)=0, f(x)=1, f(x)=x, f(x)=1+x (all of them are given in the ANF). 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) + x_1 h(x_2,ldots,x_n), where g(x_2,ldots,x_n) = f(0,x_2,ldots,x_n) and h(x_2,ldots,x_n) = f(0,x_2,ldots,x_n) + 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) + f(0,ldots) + f(1,ldots). Since both g and h have less 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) + x(f(0,y)+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 + x (y + 1); by opening the parentheses we get the final ANF: f(x,y) = y + x y + x = x + y + x y.
ee also
*
Boolean function
*Conjunctive normal form
*Disjunctive normal form
*Logical graph
Wikimedia Foundation. 2010.