Concept

Algebraic normal form

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). 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. 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 ⊕ 1 ⊕ x ⊕ x ⊕ y y NOT (logical negation) is XORing 1: 1 ⊕ 1 ⊕ x ⊕ y x ⊕ y AND (logical conjunction) is distributed algebraically ( ⊕ ) ⊕ (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) (easier when both operands have purely true terms) or a ⊕ b ⊕ ab (easier otherwise): () + () 1 ⊕ (1 ⊕ )(1 ⊕ ) 1 ⊕ x(x ⊕ y) 1 ⊕ x ⊕ xy 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.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related courses (4)
CS-101: Advanced information, computation, communication I
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
CS-550: Formal verification
We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to u
MATH-115(b): Advanced linear algebra II
L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et de démontrer rigoureusement les résultats principaux du sujet.
Show more
Related lectures (22)
Planes and Cylinders: Ray Intersections and Implementations
Covers the implementation of ray intersections with planes, cylinders, and spheres.
Presburger Arithmetic and Quantifier Elimination
Covers Presburger arithmetic, quantifier elimination, and the transformation of formulas into disjunctive normal form.
Jordan Form: Decomposition and Properties
Covers the decomposition of a matrix into Jordan blocks and the process of finding the Jordan form.
Show more
Related publications (7)

A Hybrid Method for Spectral Translation Equivalent Boolean Functions

Giovanni De Micheli, Mathias Soeken, Eleonora Testa

The equivalence of Boolean functions with respect to five invariance (aka translation) operations has been well considered with respect to the Rademacher-Walsh spectral domain. In this paper, we introduce a hybrid approach that uses both the Reed-Muller an ...
IEEE2019

Functional analysis of Bicc1 and novel interacting proteins in renal tubule cell metabolism and polycystic kidneys

Lucía Carolina Leal Esteban

Genetic disorders known as ciliopathies develop polycystic kidneys, including autosomal dominant and autosomal recessive polycystic kidney diseases (ADPKD and ARPKD). Several signaling pathways including the cAMP/PKA pathway are implicated in driving cyst ...
EPFL2017

Majority Logic Representation and Satisfiability

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù

Majority logic is a powerful generalization of common AND/OR logic. Original two-level and multi-level logic networks can use majority operators as primitive connective, in place of AND/ORs. In such a way, Boolean functions have novel means for compact rep ...
2014
Show more
Related concepts (7)
Karnaugh map
The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 logical diagram aka Marquand diagram but with a focus now set on its utility for switching circuits. Veitch charts are also known as Marquand–Veitch diagrams or, rarely, as Svoboda charts, and Karnaugh maps as Karnaugh–Veitch maps (KV maps).
Zhegalkin polynomial
Zhegalkin (also Žegalkin, Gégalkine or Shegalkin) polynomials (полиномы Жегалкина), also known as algebraic normal form, are a representation of functions in Boolean algebra. 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.
Tautology (logic)
In mathematical logic, a tautology (from ταυτολογία) is a formula or assertion that is true in every possible interpretation. An example is "x=y or x≠y". Similarly, "either the ball is green, or the ball is not green" is always true, regardless of the colour of the ball. The philosopher Ludwig Wittgenstein first applied the term to redundancies of propositional logic in 1921, borrowing from rhetoric, where a tautology is a repetitive statement.
Show more

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.