Algebraic normal form

Algebraic normal form

In Boolean logic, the algebraic normal form (ANF) is a method of standardizing and normalizing logical formulas. As a normal form, it can be used in automated theorem proving (ATP), but is more commonly used in the design of cryptographic random number generators, specifically linear feedback shift registers (LFSRs). A logical formula 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 polynomials" ( _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 feedback shift registers 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.

Look at other dictionaries:

  • Normal form — may refer to: Normal form (abstract rewriting) Normal form (databases) Normal form (game theory) Normal form (mathematics) In formal language theory: Beta normal form Chomsky normal form Greibach normal form Kuroda normal form Normal form… …   Wikipedia

  • Conjunctive normal form — In Boolean logic, a formula is in conjunctive normal form (CNF) if it is a conjunction of clauses, where a clause is a disjunction of literals. As a normal form, it is useful in automated theorem proving. It is similar to the product of sums form …   Wikipedia

  • Disjunctive normal form — In boolean logic, a disjunctive normal form (DNF) is a standardization (or normalization) of a logical formula which is a disjunction of conjunctive clauses. As a normal form, it is useful in automated theorem proving. A logical formula is… …   Wikipedia

  • Jordan normal form — In linear algebra, a Jordan normal form (often called Jordan canonical form)[1] of a linear operator on a finite dimensional vector space is an upper triangular matrix of a particular form called Jordan matrix, representing the operator on some… …   Wikipedia

  • Algebraic chess notation — is used to record and describe the moves in a game of chess. It is now standard among all chess organizations and most books, magazines, and newspapers. In English speaking countries, it replaced the parallel system of descriptive chess notation …   Wikipedia

  • Algebraic geometry — This Togliatti surface is an algebraic surface of degree five. Algebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It… …   Wikipedia

  • Algebraic structure — In algebra, a branch of pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties. The… …   Wikipedia

  • Algebraic curve — In algebraic geometry, an algebraic curve is an algebraic variety of dimension one. The theory of these curves in general was quite fully developed in the nineteenth century, after many particular examples had been considered, starting with… …   Wikipedia

  • Algebraic torus — In mathematics, an algebraic torus is a type of commutative affine algebraic group. These groups were named by analogy with the theory of tori in Lie group theory (see maximal torus). The theory of tori is in some sense opposite to that of… …   Wikipedia

  • Normal number — For the floating point meaning in computing, see normal number (computing). In mathematics, a normal number is a real number whose infinite sequence of digits in every base b[1] is distributed uniformly in the sense that each of the b digit… …   Wikipedia