Equational Theories of Boolean Functions
Oya Ekin, Stephan Foldes, Peter L. Hammer, Lisa Hellerstein · 1997
Several noteworthy classes of Boolean functions are characterized by algebraic identities. For a given DNF-specified class, such characteristic identities exist if and only if the class is closed under the operation of forming Boolean minors by variable identification. A single identity suffices to characterize a class if and only if the number of forbidden identification minors minimal in a specified sense is finite. If general first-order sentences are allowed instead of identities only, then essentially all classes can be described by an appropriate set of sentences. 1 Introduction Classes of Boolean functions may be specified in different ways. For example, consider the class of positive functions. (Formal definitions will be given in a moment.) Positive functions can be described in at least the following ways: (a) functions with a disjunctive normal form containing no negated variables, (b) functions f such that 8x; y x y ) f(x) f(y) (c) functions f such that 8x; y f(x) ...