Comparing the efficiency of normal form systems to represent Boolean functions

Miguel Couceiro 1 Pierre Mercuriali 2 Romain Péchoux 2
1 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
2 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : In this paper we compare various normal form representations of Boolean functions. We extend the study of [4], pertaining to the comparison of the asymptotic efficiency of representations that are produced by normal form systems (NFSs) that are factorizations of the clone Ω of all Boolean functions. We identify some properties, such as associativity, linearity, quasi-linearity and symmetry , that allow the efficiency of the corresponding NFSs to be compared in terms of the non-trivial connectives used. We illustrate these results by comparing well-known NFSs such as the DNF, CNF, Zhegalkin (Reed-Muller) polynomial (PNF) and Median (MNF) representations, thereby confirming the results of [4]. In particular, we show that the MNF is of equivalent complexity to, e.g., the Sheffer Normal Form (SNF), UNF and WNF (associated with 1 and 0-separating functions respectively) and thus that the latter are polynomially as efficient as any other NFS, and are strictly more efficient than the DNF, CNF, and Zhegalkin polynomial representations.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger
Contributeur : Romain Péchoux <>
Soumis le : vendredi 30 juin 2017 - 15:00:10
Dernière modification le : mardi 18 décembre 2018 - 16:48:02
Document(s) archivé(s) le : lundi 22 janvier 2018 - 21:20:23


comparing normal form systems ...
Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01551761, version 1


Miguel Couceiro, Pierre Mercuriali, Romain Péchoux. Comparing the efficiency of normal form systems to represent Boolean functions. 2017. 〈hal-01551761〉



Consultations de la notice


Téléchargements de fichiers