Boolean Functions

Theory, Algorithms, and Applications

By: Yves Crama, Peter Hammer

Write A Review

Hardcover | 30 June 2011

At a Glance

Hardcover
710 Pages

Dimensions(cm)
23.5 x 16.3 x 5.2

Hardcover

RRP $301.00

$291.95

or 4 interest-free payments of $72.99 with

or

Aims to ship in 7 to 10 business days

Written by prominent experts in the field, this monograph provides the first comprehensive, 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 disjunctive and conjunctive normal form representations. This framework looks at 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 functions and their characterization by functional equations) and two fruitful generalizations of the concept of Boolean functions (partially defined functions and pseudo-Boolean functions). Several topics are presented here in book form for the first time. Because of the depth and breadth and its emphasis on algorithms and applications, this monograph will have special appeal for researchers and graduate students in discrete mathematics, operations research, computer science, engineering and economics.

Industry Reviews

'Because of the unique depth and breadth of the unified treatment that it provides and its emphasis on algorithms and applications, this monograph and its companion book [Boolean Models and Methods in Mathematics, Computer Science and Engineering] will have special appeal for a large circle of readers.' Sergiu Rudeanu, Zentralblatt MATH

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

More in Mathematical Logic

Modelling and Control of Dynamic Spatially Distributed Systems

Pharmaceutical Processes

Paperback

RRP $264.95

$234.95

11%
OFF

Completely Regular Semigroup Varieties : Applications and Advanced Techniques - Mario Petrich

$36.75

22%
OFF

Information-Oriented Logic : Implications of Natural-Language Sentences and All Logical Paradoxes Solved - Zbigniew Plotnicki

$168.75

Institution-independent Model Theory : Studies in Universal Logic - R?zvan Diaconescu

$289.95

Contributors	p. xiii
Preface	p. xv
Acknowledgments	p. xix
Notations	p. xxi
Foundations
Fundamental concepts and applications	p. 3
Boolean functions: Definitions and examples	p. 3
Boolean expressions	p. 8
Duality	p. 13
Normal forms	p. 14
Transforming an arbitrary expression into a DNF	p. 19
Orthogonal DNFs and number of true points	p. 22
Implicants and prime implicants	p. 24
Restrictions of functions, essential variables	p. 28
Geometric interpretation	p. 31
Monotone Boolean functions	p. 33
Recognition of functional and DNF properties	p. 40
Other representations of Boolean functions	p. 44
Applications	p. 49
Exercises	p. 65
Boolean equations	p. 67
Definitions and applications	p. 67
The complexity of Boolean equations: Cook's theorem	p. 72
On the role of DNF equations "	p. 74
What does it mean to "solve a Boolean equation"?	p. 78
Branching procedures	p. 80
Variable elimination procedures	p. 87
The consensus procedure	p. 92
Mathematical programming approaches	p. 95
Recent trends and algorithmic performance	p. 103
More on the complexity of Boolean equations	p. 104
Generalizations of consistency testing	p. 111
Exercises	p. 121
Prime implicants and minimal DNFs	p. 123
Prime implicants	p. 123
Generation of all prime implicants	p. 128
Logic minimization	p. 141
Extremal and typical parameter values	p. 159
Exercises	p. 165
Duality theory	p. 167
Basic properties and applications	p. 167
Duality properties of positive functions	p. 176
Algorithmic aspects: The general case	p. 183
Algorithmic aspects: Positive functions	p. 189
Exercises	p. 198
Special Classes
Quadratic functions	p. 203
Basic definitions and properties	p. 203
Why are, quadratic Boolean functions important?	p. 205
Special classes of quadratic functions	p. 207
Quadratic Boolean functions and graphs	p. 209
Reducibility of combinatorial problems to quadratic equations	p. 218
Efficient graph-theoretic algorithms for quadratic equations	p. 230
Quadratic equations: Special topics	p. 243
Prime implicants and irredundant forms	p. 250
Dualization of quadratic functions (Contributed by Oya Ekin Karasan)	p. 263
Exercises	p. 266
Horn functions	p. 269
Basic definitions and properties	p. 269
Applications of Horn functions	p. 273
False points of Horn functions	p. 277
Horn equations	p. 281
Prime implicants of Horn functions	p. 286
Properties of the set of prime implicants	p. 292
Minimization of Horn DNFs	p. 297
Duaiization of Horn functions	p. 306
Special classes	p. 309
Generalizations	p. 314
Exercises	p. 321
Orthogonal forms and sheUability	p. 326
Computation of orthogonal DNFs	p. 326
Shellings and sheUability	p. 330
Duaiization of shellable DNFs	p. 336
The lexico-exchange property	p. 338
Shellable quadratic DNFs and graphs	p. 346
Applications	p. 348
Exercises	p. 349
Regular functions	p. 351
Relative strength of variables and regularity	p. 351
Basic properties	p. 355
Regularity and left-shifts	p. 362
Recognition of regular functions	p. 365
Duaiization of regular functions	p. 369
Regular set covering problems	p. 377
Regular minorants and majorants	p. 380
Higher-order monotonicity	p. 391
Generalizations of regularity	p. 397
Exercises	p. 401
Threshold functions	p. 404
Definitions and applications	p. 404
Basic properties of threshold functions	p. 408
Characterizations of threshold functions	p. 413
Recognition of threshold functions	p. 417
Prime implicants of threshold functions	p. 423
Chow parameters of threshold functions	p. 428
Threshold graphs	p. 438
Exercises	p. 444
Read-once functions	p. 448
Introduction	p. 448
Dual implicants	p. 450
Characterizing read-once functions	p. 456
The properties of P₄-free graphs and cographs	p. 463
Recognizing read-once functions	p. 466
Learning read-once functions	p. 473
Related topics and applications of read-once functions	p. 476
Historical notes	p. 480
Exercises	p. 481
Characterizations of special classes by functional, equations	p. 487
Characterizations of positive functions	p. 487
Functional equations	p. 488
Characterizations of particular classes	p. 491
Conditions for characterization	p. 495
Finite characterizations by functional equations	p. 500
Exercises	p. 506
Generalizations
Partially defined Boolean functions	p. 511
Introduction	p. 511
Extensions of pdBfs and their representations	p. 514
Extensions within given function classes	p. 531
Best-fit extensions of pdBfs containing errors	p. 547
Extensions of pdBfs with missing bits	p. 551
Minimization with don't cares	p. 558
Conclusion	p. 561
Exercises	p. 562
Pseudo-Boolean functions	p. 564
Definitions and examples	p. 564
Representations	p. 570
Extensions of pseudo-Boolean functions	p. 578
Pseudo-Boolean optimization	p. 585
Approximations	p. 593
Special classes of pseudo-Boolean functions	p. 593
Exercises	p. 607
Graphs and hypergraphs	p. 609
Undirected graphs	p. 609
Directed graphs	p. 612
Hypergraphs	p. 614
Algorithmic complexity	p. 615
Decision problems	p. 615
Algorithms	p. 617
Running time, polynomial-time algorithms, and the class P	p. 618
The class NP	p. 619
Polynomial-time reductions and NP-completeness	p. 620
The class co-NP	p. 621
Cook's theorem	p. 622
Complexity of list-generation and counting algorithms	p. 624
JBool: A software tool	p. 627
Introduction	p. 627
Work interface	p. 628
Creating a Boolean function	p. 629
Editing a function	p. 632
Operations on Boolean functions	p. 633
Bibliography	p. 635
Index	p. 677
Table of Contents provided by Ingram. All Rights Reserved.

Boolean Functions

Theory, Algorithms, and Applications

At a Glance

Hardcover

Industry Reviews

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Mathematical Logic

Modelling and Control of Dynamic Spatially Distributed Systems

Pharmaceutical Processes

Completely Regular Semigroup Varieties

Applications and Advanced Techniques

The Language of Mathematics

The Stories behind the Symbols

Alcuin's Recreational Mathematics

River Crossings and other Timeless Puzzles

Sum Stories Equations and Their Origins

Equations and Their Origins

Partial Truths

How Fractions Distort Our Thinking

Information-Oriented Logic

Implications of Natural-Language Sentences and All Logical Paradoxes Solved

Proof Complexity Generators

London Mathematical Society Lecture Note Series

Deep Learning and Blockchain Technology for Smart and Sustainable Cities

Advances in Computational Collective Intelligence

Blockchain and Digital Twin Applications in Smart Agriculture

Advancements in Cybersecurity

Next-Generation Systems and Applications

Set Theory

An Introduction to Axiomatic Reasoning

Polygraphs

From Rewriting to Higher Categories

Institution-independent Model Theory

Studies in Universal Logic

Quantum Technology Applications, Impact, and Future Challenges

Quantum Technology Applications, Impact, and Future Challenges

Completely Regular Codes in Distance Regular Graphs

Chapman & Hall/CRC Monographs and Research Notes in Mathematics

AI and Blockchain in Smart Grids

Fundamentals, Methods, and Applications

MAGIC GARDEN OF GEORGE B AND OTHER LOGIC PUZZLES, THE

REFLECTIONS

THE MAGIC, MUSIC & MATH OF RAYMOND SMULLYAN

New Directions in Relevant Logic

Trends in Logic

Initial Algebras and Terminal Coalgebras

The Theory of Fixed Points of Functors

Weighted Morrey Spaces

Calderon-Zygmund Theory and Boundary Problems

BEGINNER'S FURTHER GUIDE TO MATHEMATICAL LOGIC, A

This product is categorised by