Concept
Algebraic normal form
Overview
Algebraic normal form (ANF) is a representation of functions in boolean algebra. Formulas written in ANF are also known as ring sum normal form (RSNF or RNF), Zhegalkin polynomials (Russian: полиномы Жегалкина), or Positive Polarity (or parity) Reed–Muller expansions (PPRM). These terms describe a way of writing propositional logic formulas in one of three sub-forms:
The entire formula is purely true or false:
1
{\displaystyle 1}
0
{\displaystyle 0}
One or more variables are combined into a term by AND (
∧
{\displaystyle \land }
), then one or more terms are combined by XOR (
⊕
{\displaystyle \oplus }
) together into ANF. Negations are not permitted:
a
⊕
b
⊕
(
a
∧
b
)
⊕
(
a
∧
b
∧
c
)
{\displaystyle a\oplus b\oplus \left(a\land b\right)\oplus \left(a\land b\land c\right)}
The previous subform with a purely true term:
1
⊕
a
⊕
b
⊕
(
a
∧
b
)
⊕
(
a
∧
b
∧
c
)
{\displaystyle 1\oplus a\oplus b\oplus \left(a\land b\right)\oplus \left(a\land b\land c\right)}
Introduced by the Russian mathematician Ivan Ivanovich Zhegalkin in 1927, they are the polynomial ring over the integers modulo 2. The resulting degeneracies of modular arithmetic result in Zhegalkin polynomials being simpler than ordinary polynomials, requiring neither coefficients nor exponents. Coefficients are redundant because 1 is the only nonzero coefficient. Exponents are redundant because in arithmetic mod 2, x2 = x. Hence a polynomial such as 3x2y5z is congruent to, and can therefore be rewritten as, xyz.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
In this employment the algebraic letters are called the ‘arguments’ of the function, or sometimes they are called the ‘variables.’ Then, for instance, if an angle is represented by an algebraical letter, as standing for its numerical measure in terms of a given unit, Trigonometry is absorbed into this new algebra. Algebra thus develops into the general science of analysis in which we consider the properties of…
Alfred North Whitehead, Science and the modern world
States what Algebraic normal form is.
Thus there arises a classification of modes of formation, or in the language commonly used by mathematicians, a classification of Functions. Any number, considered as formed from any other number, is called a function of it; and there are as many kinds of functions as there are modes of formation. The simple functions are by no means numerous, most functions being formed by the combination of several of the…
John Stuart Mill, A System of Logic, Ratiocinative and Inductive
States what Algebraic normal form is.
The classification of equations by what is called their _degrees_, is, on the other hand, eminently natural, for this distinction rigorously determines the greater or less difficulty of their _resolution_. This gradation is apparent in the cases of all the equations which can be resolved; but it may be indicated in a general manner independently of the fact of the resolution. We need only consider that the most…
Auguste Comte, The philosophy of mathematics
States what Algebraic normal form is.
Related ideas
- Exclusive or
- Finite set
- Negation
- Truth value
- Logical conjunction
- Propositional logic
- Richard Dedekind
- Boolean algebra
- Venn diagram
- De Morgan's laws
- Logical disjunction
- Empty set
- Negation normal form
Place in the tradition
Part of Outline of logic.