Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes

DOI10.1016/j.dam.2004.06.028zbMath1086.06015OpenAlexW1989659704MaRDI QIDQ2387440

Igor Edm. Zverovich

Publication date: 2 September 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.06.028

zbMATH Keywords

closed classeshereditary classes of Boolean functionsPost theorem

Mathematics Subject Classification ID

Boolean functions (06E30)

Related Items (22)

Parametrized arity gap ⋮ On a class of bases for Boolean functions ⋮ Characterization of zigzag De Morgan functions ⋮ Composition of Post classes and normal forms of Boolean functions ⋮ Descending chains and antichains of the unary, linear, and monotone subfunction relations ⋮ Join-irreducible Boolean functions ⋮ Reconstructing permutations from identification minors ⋮ Totally symmetric functions are reconstructible from identification minors ⋮ The arity gap of order-preserving functions and extensions of pseudo-Boolean functions ⋮ Galois theory for analogical classifiers ⋮ On a quasi-ordering on Boolean functions ⋮ Decompositions of functions based on arity gap ⋮ RECONSTRUCTING MULTISETS OVER COMMUTATIVE GROUPOIDS AND AFFINE FUNCTIONS OVER NONASSOCIATIVE SEMIRINGS ⋮ Clones with finitely many relative \({\mathcal R}\)-classes ⋮ ADDITIVE DECOMPOSABILITY OF FUNCTIONS OVER ABELIAN GROUPS ⋮ Minors of Boolean functions with respect to clique functions and hypergraph homomorphisms ⋮ ON THE EFFECT OF VARIABLE IDENTIFICATION ON THE ESSENTIAL ARITY OF FUNCTIONS ON FINITE SETS ⋮ Critical properties and complexity measures of read-once Boolean functions ⋮ A functional completeness theorem for De Morgan functions. ⋮ Equivalence of operations with respect to discriminator clones ⋮ CONTENT AND SINGLETONS BRING UNIQUE IDENTIFICATION MINORS ⋮ Generalizations of Świerczkowski's lemma and the arity gap of finite functions

Cites Work

• Inductive representations of Boolean functions and the finite generation of the Post classes
• Existence of finite bases in closed classes of Boolean functions
• Algebraic logic. Transl. from the Russian by Robert H. Silverman
• Post's functional completeness theorem
• Post's closed systems and the weak chromatic number of hypergraphs
• Post classes characterized by functional terms
• From logical gates synthesis to chromatic bicritical clutters
• On congruences in closed Post classes
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes