Forme normale algébrique

En logique mathématique, la forme normale algébrique d'une fonction booléenne est une formule qui est un ou exclusif de conjonctions de variables propositionnelles ; par exemple 1 ⊕ a ⊕ b ⊕ ab ⊕ abc^[1] (1 correspond à la conjonction vide). Toute fonction booléenne admet une unique forme normale algébrique de taille minimale^[1].

Construction de la forme normale algébrique

Pour construire une formule normale algébrique, on part d'une forme normale disjonctive. On remplace ensuite la négation de a par (1 ⊕ a). On applique ensuite les règles de distributivité et d'absorption (a ⊕ a) = 0.

Notes et références

1. John E. Savage, Models of Computation : Exploring the Power of Computing, Addison-Wesley Longman Publishing Co., Inc., 1997, 672 p. (ISBN 978-0-201-89539-1, lire en ligne)