Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Romain Péchoux Connect in order to contact the contributor
Submitted on : Friday, June 30, 2017 - 3:00:10 PM
Last modification on : Thursday, August 4, 2022 - 5:18:46 PM
Long-term archiving on: : Monday, January 22, 2018 - 9:20:23 PM


comparing normal form systems ...
Files produced by the author(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⟩



Record views


Files downloads