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)
“Unlike the normal pattern, I know I have grown more liberal as I’ve grown older. I have become more convinced that there is room for improvement in the world.”
—Walter Wellesley (Red)
“It is my contention that civil disobedients are nothing but the latest form of voluntary association, and that they are thus quite in tune with the oldest traditions of the country.”
—Hannah Arendt (1906–1975)