Equational characterizations of Boolean function classes

Oya Ekin, Stephan Foldes, Peter L. Hammer, Lisa Hellerstein

    Research output: Contribution to journalArticlepeer-review

    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) 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.

    Original languageEnglish (US)
    Pages (from-to)27-51
    Number of pages25
    JournalDiscrete Mathematics
    Volume211
    Issue number1-3
    DOIs
    StatePublished - Jan 28 2000

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Discrete Mathematics and Combinatorics

    Fingerprint Dive into the research topics of 'Equational characterizations of Boolean function classes'. Together they form a unique fingerprint.

    Cite this