A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
This article needs additional citations for verification. (July 2013) |
In Boolean algebra, the algebraic normal form (ANF), ring sum normal form (RSNF or RNF), Zhegalkin normal form, or Reed–Muller expansion is a way of writing propositional logic formulas in one of three subforms:
- The entire formula is purely true or false:
- One or more variables are combined into a term by AND (), then one or more terms are combined by XOR () together into ANF. Negations are not permitted:
- The previous subform with a purely true term:
Formulas written in ANF are also known as Zhegalkin polynomials and Positive Polarity (or Parity) Reed–Muller expressions (PPRM).[1]
Common uses
ANF is a canonical form, which means that two logically equivalent formulas will convert to the same ANF, easily showing whether two formulas are equivalent for automated theorem proving. Unlike other normal forms, it can be represented as a simple list of lists of variable names—conjunctive and disjunctive normal forms also require recording whether each variable is negated or not. Negation normal form is unsuitable for determining equivalence, since on negation normal forms, equivalence does not imply equality: a ∨ ¬a is not reduced to the same thing as 1, even though they are logically equivalent.
Putting a formula into ANF also makes it easy to identify linear functions (used, for example, in linear-feedback shift registers): a linear function is one that is a sum of single literals. Properties of nonlinear-feedback shift registers can also be deduced from certain properties of the feedback function in ANF.
Performing operations within algebraic normal form
There are straightforward ways to perform the standard boolean operations on ANF inputs in order to get ANF results.
XOR (logical exclusive disjunction) is performed directly:
- (1 ⊕ x) ⊕ (1 ⊕ x ⊕ y)
- 1 ⊕ x ⊕ 1 ⊕ x ⊕ y
- 1 ⊕ 1 ⊕ x ⊕ x ⊕ y
- y
NOT (logical negation) is XORing 1:[2]
- ¬(1 ⊕ x ⊕ y)
- 1 ⊕(1 ⊕ x ⊕ y)
- 1 ⊕ 1 ⊕ x ⊕ y
- x ⊕ y
AND (logical conjunction) is distributed algebraically[3]
- (1 ⊕ x)(1 ⊕ x ⊕ y)
- 1(1 ⊕ x ⊕ y) ⊕ x(1 ⊕ x ⊕ y)
- (1 ⊕ x ⊕ y) ⊕ (x ⊕ x ⊕ xy)
- 1 ⊕ x ⊕ x ⊕ x ⊕ y ⊕ xy
- 1 ⊕ x ⊕ y ⊕ xy
OR (logical disjunction) uses either 1 ⊕ (1 ⊕ a)(1 ⊕ b)[4] (easier when both operands have purely true terms) or a ⊕ b ⊕ ab[5] (easier otherwise):
- (1 ⊕ x) + (1 ⊕ x ⊕ y)
- 1 ⊕ (1 ⊕ 1 ⊕ x)(1 ⊕ 1 ⊕ x ⊕ y)
- 1 ⊕ x(x ⊕ y)
- 1 ⊕ x ⊕ xy
Converting to algebraic normal form
Each variable in a formula is already in pure ANF, so one only needs to perform the formula's boolean operations as shown above to get the entire formula into ANF. For example:
- x + (y ⋅ ¬z)
- x + (y(1 ⊕ z))
- x + (y ⊕ yz)
- x ⊕ (y ⊕ yz) ⊕ x(y ⊕ yz)
- x ⊕ y ⊕ xy ⊕ yz ⊕ xyz
Formal representation
ANF is sometimes described in an equivalent way:
- where fully describes .
Recursively deriving multiargument Boolean functions
There are only four functions with one argument:
To represent a function with multiple arguments one can use the following equality:
- , where
Indeed,
- if then and so
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk