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 and one or more conjunctions of the function arguments. ANF is also known as "Zhegalkin polynomials" (Russian: полиномы Жегалкина) 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 fully describes .
For each function there is a unique ANF. There are only four functions with one argument:, (all of them are given in the ANF). To represent a function with multiple arguments one can use the following equality:, where and . Indeed, if then and so ; if then and so . Since both and have less 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 opening the parentheses we get the final ANF: .
Famous quotes containing the words algebraic, normal and/or form:
“I have no scheme about it,—no designs on men at all; and, if I had, my mode would be to tempt them with the fruit, and not with the manure. To what end do I lead a simple life at all, pray? That I may teach others to simplify their lives?—and so all our lives be simplified merely, like an algebraic formula? Or not, rather, that I may make use of the ground I have cleared, to live more worthily and profitably?”
—Henry David Thoreau (1817–1862)
“A few ideas seem to be agreed upon. Help none but those who help themselves. Educate only at schools which provide in some form for industrial education. These two points should be insisted upon. Let the normal instruction be that men must earn their own living, and that by the labor of their hands as far as may be. This is the gospel of salvation for the colored man. Let the labor not be servile, but in manly occupations like that of the carpenter, the farmer, and the blacksmith.”
—Rutherford Birchard Hayes (1822–1893)
“I am quite serious when I say that I do not believe there are, on the whole earth besides, so many intensified bores as in these United States. No man can form an adequate idea of the real meaning of the word, without coming here.”
—Charles Dickens (1812–1870)