Composition of Post classes and normal forms of Boolean functions

Miguel Couceiro, Stephan Foldes, Erkko Lehtonen

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

The class composition C {ring operator} K of Boolean clones, being the set of composite functions f (g1, ..., gn) with f ∈ C, g1, ..., gn ∈ K, is investigated. This composition C {ring operator} K is either the join C ∨ K in the Post Lattice or it is not a clone, and all pairs of clones C, K are classified accordingly. Factorizations of the clone Ω of all Boolean functions as a composition of minimal clones are described and seen to correspond to normal form representations of Boolean functions. The median normal form, arising from the factorization of Ω with the clone SM of self-dual monotone functions as the leftmost composition factor, is compared in terms of complexity with the well-known DNF, CNF, and Zhegalkin (Reed-Muller) polynomial representations, and it is shown to provide a more efficient normal form representation.

Original languageBritish English
Pages (from-to)3223-3243
Number of pages21
JournalDiscrete Mathematics
Volume306
Issue number24
DOIs
StatePublished - 28 Dec 2006

Keywords

  • Boolean functions
  • Class factorization
  • Clones
  • CNF
  • Complexity
  • DNF
  • Efficient representations
  • Formulas
  • Function class composition
  • Median
  • Normal forms
  • Post classes
  • Reed-Muller polynomial
  • Ternary majority
  • Zhegalkin polynomial

Fingerprint

Dive into the research topics of 'Composition of Post classes and normal forms of Boolean functions'. Together they form a unique fingerprint.

Cite this