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:
5-442: PPRM may refer to: Positive Polarity Reed-Muller : representation of a boolean function as a single algebraic sum (xor) of one or more conjunctions of one or more literals Greater Romania Party Topics referred to by the same term [REDACTED] This disambiguation page lists articles associated with the title PPRM . If an internal link led you here, you may wish to change
10-413: 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
15-502: 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
20-467: The feedback function in ANF. 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: NOT (logical negation) is XORing 1: AND (logical conjunction) is distributed algebraically OR (logical disjunction) uses either 1 ⊕ (1 ⊕ a)(1 ⊕ b) (easier when both operands have purely true terms) or
25-516: The link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=PPRM&oldid=805081428 " Category : Disambiguation pages Hidden categories: Short description is different from Wikidata All article disambiguation pages All disambiguation pages Positive Polarity Reed-Muller Formulas written in ANF are also known as Zhegalkin polynomials and Positive Polarity (or Parity) Reed–Muller expressions (PPRM). ANF
#416583