Article (Scientific journals)
Composition of Post classes and normal forms of Boolean functions
COUCEIRO, Miguel; Foldes, Stephan; LEHTONEN, Erkko
2006In Discrete Mathematics, 306 (24), p. 3223-3243
Peer Reviewed verified by ORBi
 

Files


Full Text
CPCNFBF.pdf
Author postprint (456.39 kB)
Request a copy

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
function class composition; clones; Boolean functions; Post classes; class factorization; normal forms; DNF; CNF; Zhegalkin polynomial; Reed–Muller polynomial; formulas; efficient representations; complexity; median; ternary majority
Abstract :
[en] The class composition CK of Boolean clones, being the set of composite functions f(g1,...,gn) with f∈C, g1,...,gn∈K, is investigated. This composition CK 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.
Disciplines :
Mathematics
Identifiers :
UNILU:UL-ARTICLE-2010-132
Author, co-author :
COUCEIRO, Miguel ;  University of Tampere, Finland
Foldes, Stephan;  Tampere University of Technology, Finland
LEHTONEN, Erkko ;  Tampere University of Technology, Finland
Language :
English
Title :
Composition of Post classes and normal forms of Boolean functions
Publication date :
2006
Journal title :
Discrete Mathematics
ISSN :
0012-365X
eISSN :
1872-681X
Publisher :
Elsevier
Volume :
306
Issue :
24
Pages :
3223-3243
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBilu :
since 01 July 2013

Statistics


Number of views
74 (0 by Unilu)
Number of downloads
0 (0 by Unilu)

Scopus citations®
 
22
Scopus citations®
without self-citations
8
OpenCitations
 
15
OpenAlex citations
 
24
WoS citations
 
19

Bibliography


Similar publications



Contact ORBilu