Paper Info
Title
Equational characterizations of Boolean function classes
Abstract
Several noteworthy classes of Boolean functions can be characterized by algebraic identities (e.g. the class of positive functions consists of all functions f satisfying the identity f( x )∨f( y )∨f( x ∨ y )=f( x ∨ y ) ). We give algebraic identities for several of the most frequently analyzed classes of Boolean functions (including Horn, quadratic, supermodular, and submodular functions) and proceed then to the general question of which classes of Boolean functions can be characterized by algebraic identities. We answer this question for function classes closed under addition of inessential (irrelevant) variables. Nearly all classes of interest have this property. We show that a class with this property has a characterization by algebraic identities if and only if the class is closed under the operation of variable identification. Moreover, a single identity suffices to characterize a class if and only if the number of minimal forbidden identification minors is finite. Finally, we consider characterizations by general first-order sentences, rather than just identities. We show that a class of Boolean functions can be described by an appropriate set of such first-order sentences if and only if it is closed under permutation of variables.
Year
DOI
Venue
2000
10.1016/S0012-365X(99)00132-6
Discrete Mathematics
Keywords
Field
DocType
equational characterization,boolean function class,first order,boolean function,satisfiability
Boolean function,Boolean network,Discrete mathematics,Combinatorics,Algebraic number,Parity function,Submodular set function,Product term,Complexity index,Boolean expression,Mathematics
Journal
Volume
Issue
ISSN
211
1-3
Discrete Mathematics
Citations 
PageRank 
References 
25
2.04
2
Authors
4
Name
Order
Citations
PageRank
Oya Ekin1695.34
Stephan Foldes217519.36
Peter L. Hammer31996288.93
Lisa Hellerstein4710121.90