Skip to Main content Skip to Navigation
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.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01551761
Contributor : Romain Péchoux <>
Submitted on : Friday, June 30, 2017 - 3:00:10 PM
Last modification on : Tuesday, December 18, 2018 - 4:48:02 PM
Document(s) archivé(s) le : Monday, January 22, 2018 - 9:20:23 PM

File

comparing normal form systems ...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01551761, version 1

Citation

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

Share

Metrics

Record views

272

Files downloads

303