DIMACS TR: 97-79

Equational Theories of Boolean Functions

Authors: Oya Ekin, Stephan Foldes, Peter L. Hammer, and Lisa Hellerstein


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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-79.ps.gz
DIMACS Home Page