DIMACS TR: 97-79
Equational Theories of Boolean Functions
Authors: Oya Ekin, Stephan Foldes, Peter L. Hammer, and Lisa Hellerstein
ABSTRACT
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