Skip to Main content Skip to Navigation
Conference papers

Sur l'efficacité des systèmes de formes normales de fonctions Booléennes

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 [3] pertaining to the comparison of the asymptotic efficiency of representations produced by normal form systems (NFSs). We identify some properties, such as as-sociativity, linearity, quasi-linearity and symmetry, that allow the efficiency of the corresponding NFSs to be compared. We illustrate these results by comparing well-known NFSs such as the DNF, CNF, polynomial (PNF) representations, as well as the Median Normal Form (MNF) and Sheffer Normal Form (SNF). We obtain in particular that NFSs generated by a single connective are polynomially as efficient as those generated by several connectives. As for the MNF, it is as efficient as any other NFS.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Pierre Mercuriali Connect in order to contact the contributor
Submitted on : Tuesday, December 5, 2017 - 1:56:23 PM
Last modification on : Wednesday, November 3, 2021 - 7:10:22 AM


Files produced by the author(s)


  • HAL Id : hal-01656033, version 1


Miguel Couceiro, Pierre Mercuriali, Romain Péchoux. Sur l'efficacité des systèmes de formes normales de fonctions Booléennes. LFA 2017 - 26èmes Rencontres Francophones sur la Logique Floue et ses Applications, Oct 2017, Amiens, France. pp.1-8. ⟨hal-01656033⟩



Les métriques sont temporairement indisponibles