Skip to Main content Skip to Navigation
Journal articles

On the efficiency of normal form systems for representing Boolean functions

Miguel Couceiro 1 Erkko Lehtonen 2, 3 Pierre Mercuriali 4 Romain Péchoux 4
1 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
4 MOCQUA - Designing the Future of Computational Models
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : A normal form system (NFS) for representing Boolean functions is thought of as a set of stratified terms over a fixed set of connectives. For a fixed NFS A, the complexity of a Boolean function f with respect to A is the minimum of the sizes of terms in A that represent f. This induces a preordering of NFSs: an NFS A is polynomially as efficient as an NFS B if there is a polynomial P with nonnegative integer coefficients such that the complexity of any Boolean function f with respect to A is at most the value of P in the complexity of f with respect to B. In this paper we study monotonic NFSs, i.e., NFSs whose connectives are increasing or decreasing in each argument. We describe the monotonic NFSs that are optimal, i.e., that are minimal with respect to the latter preorder. We show that these minimal monotonic NFSs are all equivalent. Moreover, we address some natural questions, e.g.: does optimality depend on the arity of connectives? Does it depend on the number of connectives used? We show that optimal monotonic NFSs are exactly those that use a single connective or one connective and the negation. Finally, we show that optimality does not depend on the arity of the connectives.
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/hal-02153506
Contributor : Miguel Couceiro <>
Submitted on : Thursday, December 12, 2019 - 7:01:28 PM
Last modification on : Tuesday, October 13, 2020 - 11:14:02 AM

File

TCS_HAL_CLMP.pdf
Files produced by the author(s)

Identifiers

Citation

Miguel Couceiro, Erkko Lehtonen, Pierre Mercuriali, Romain Péchoux. On the efficiency of normal form systems for representing Boolean functions. Theoretical Computer Science, Elsevier, 2020, 813, pp.341-361. ⟨10.1016/j.tcs.2020.01.009⟩. ⟨hal-02153506v2⟩

Share

Metrics

Record views

139

Files downloads

288