文档介绍：This page intentionally left blank
Boolean Functions
Written by prominent expertsin the field, thismonograph providesthe pre-
hensive and unified presentation of the structural, algorithmic, and applied aspects of
the theory of Boolean functions.
The book focuses on algebraic representations of Boolean functions, especially dis-
junctive and conjunctive normal form representations. It presents within this framework
the fundamental elements of the theory (Boolean equations and satisfiability problems,
prime implicants and associated short representations, dualization), an in-depth study
of special classes of Boolean functions (quadratic, Horn, shellable, regular, threshold,
read-once functionsand their characterization by functional equations),and two fruit-
ful generalizationsof the concept of Boolean functions(partially defined functionsand
pseudo-Boolean functions). Several topics are presented here in book form for the first
time.
Because of the unique depth and breadth of the unified treatment that it provides and
itsemphasisonalgorithmsand applications,thismonograph will have specialappeal
for researchers and graduate students in discrete mathematics, operations research,
computer science, engineering, and economics.
Dr. YvesCrama isProfessorof OperationsResearchand Production Management and
the former Director General of the HEC Management School of the University of
Liège, Belgium. He iswidely recognized asa prominent expert in the field of Boolean
functions, combinatorial optimization, and operations research, and he has coauthored
more than seventy papers and three books on these subjects. Dr. Crama is a member of
the editorial board of Discrete Applied Mathematics, Discrete Optimization, Journal
of Scheduling, and 4OR – The Quarterly Journal of the Belgian, French and Italian
Operations Research Societies.
The late Peter L. Hammer (1936–2006) was a Professor of Operations Research,
Mathematics, Computer Science, Management Scie