Composition of Post classes and normal forms of Boolean functions
type: Item
instance of: scholarly article
title: Composition of Post classes and normal forms of Boolean functions
zbMATH Open document ID: 1110.06017
author: Miguel Couceiro
author: Stephan Foldes
author: Erkko Lehtonen
published in: Discrete Mathematics
publication date: 2006-12-14T00:00:00Z
full work available at URL: https://basepub.dauphine.fr/handle/123456789/10177
review text: From the introduction: ``The plan of the paper is as follows. In Section 2 we restate a lemma on the associativity of function class composition, and state and prove a general sufficient condition for the composition of clones to be a clone. In Section 3 we completely classify those pairs of Boolean clones whose class composition is a clone (Section 3.1), and those pairs whose composition is not a clone (Section 3.2), and we summarize this classification in the two theorems of Section 3.3 -- from the direct point of view of compositions in Theorem 2 and from the reverse point of view of decompositions or factorizations of a given clone in Theorem 3. In Section 4 we consider certain factorizations of the clone \(\Omega\) of all Boolean functions which correspond to normal form representations of functions such as disjunctive normal form (DNF), conjunctive normal form (CNF), and Zhegalkin or Reed-Muller polynomial representations. We conclude by showing that the representation using the ternary median (majority) function, based on the factorization of \(\Omega\) with the clone \(SM\) of self-dual monotone functions as the leftmost factor, is asymptotically more efficient than the more classical DNF, CNF and polynomial representations which use Boolean lattice or Boolean ring operations.''
reviewed by: Sergiu Rudeanu
Mathematics Subject Classification ID: 06E30
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 5080066
zbMATH Keywords: function class composition
zbMATH Keywords: clones
zbMATH Keywords: Boolean functions
zbMATH Keywords: Post classes
zbMATH Keywords: class factorization
zbMATH Keywords: normal forms
zbMATH Keywords: DNF
zbMATH Keywords: CNF
zbMATH Keywords: Zhegalkin polynomial
zbMATH Keywords: Reed-Muller polynomial
zbMATH Keywords: efficient representations
zbMATH Keywords: complexity
zbMATH Keywords: median
zbMATH Keywords: ternary majority
MaRDI profile type: Publication
OpenAlex ID: W2039921034
cites work: Median algebras
cites work: A ternary operation in distributive lattices
cites work: Q4419472
cites work: Function classes and relational constraints stable under compositions with cloness
cites work: Q4510394
cites work: Post classes characterized by functional terms
cites work: Ternary Boolean algebra
cites work: Q5806867
cites work: Median Algebra
cites work: Q5588600
cites work: Q4354427
cites work: The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
cites work: Q3834101
cites work: Postulates For Distributive Lattices
cites work: Q3807200
cites work: Q3141898
cites work: Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes
DOI: 10.1016/J.DISC.2006.06.014
description: scientific article; zbMATH DE number 5080066