TY - JOUR

T1 - Equational characterizations of Boolean function classes

AU - Ekin, Oya

AU - Foldes, Stephan

AU - Hammer, Peter L.

AU - Hellerstein, Lisa

N1 - Funding Information:
∗Corresponding author. E-mail addresses: karasan@bilkent.edu.tr (O. Ekin), sfoldes@mba1981.hbs.edu (S. Foldes), hammer@ rutcor.rutgers.edu (P.L. Hammer), hstein@duke.poly.edu. (L. Hellerstein) 1Part of this author’s work was done at the National Autonomous University of Mexico (UNAM) in August 1997. Partially supported by RUTCOR and DIMACS. 2Partially supported by ONR grants N0001492J1375 and N0001492J4083 and by DIMACS. 3Partially supported by NSF Grant CCR-9501660, RUTCOR, and DIMACS. 4Partially supported by ONR grants N0001492J1375 and N0001492J4083 and by DIMACS. Part of this author’s work was done at RUTCOR.

PY - 2000/1/28

Y1 - 2000/1/28

N2 - 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) V f(y) V f(x V y) = f(x V 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.

AB - 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) V f(y) V f(x V y) = f(x V 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.

UR - http://www.scopus.com/inward/record.url?scp=0002328242&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0002328242&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(99)00132-6

DO - 10.1016/S0012-365X(99)00132-6

M3 - Article

AN - SCOPUS:0002328242

VL - 211

SP - 27

EP - 51

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -