Boolean Functions: Theory, Algorithms, and Applications (Encyclopedia of Mathematics and its Applications 142)

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Dedication......Page 7
Contents......Page 9
Contributors......Page 15
Preface......Page 17
Acknowledgments......Page 21
Notations......Page 23
Part I: Foundations......Page 25
1.1 Boolean functions: Definitions and examples......Page 27
1.2 Boolean expressions......Page 32
1.3 Duality......Page 37
1.4 Normal forms......Page 38
1.5 Transforming an arbitrary expression into a DNF......Page 43
1.6 Orthogonal DNFs and number of true points......Page 46
1.7 Implicants and prime implicants......Page 48
1.8 Restrictions of functions, essential variables......Page 52
1.9 Geometric interpretation......Page 55
1.10.1 Definitions and examples......Page 57
1.10.2 DNFs and prime implicants of positive functions......Page 59
1.10.3 Minimal true points and maximal false points......Page 62
1.11 Recognition of functional and DNF properties......Page 64
1.12.1 Representations over GF(2)......Page 68
1.12.2 Representations over the reals......Page 69
1.12.3 Binary decision diagrams and decision trees......Page 70
1.13 Applications......Page 73
1.13.1 Propositional logic and artificial intelligence......Page 74
1.13.2 Electrical and computer engineering......Page 76
1.13.3 Game theory......Page 79
1.13.4 Reliability theory......Page 82
1.13.5 Combinatorics......Page 84
1.13.6 Integer programming......Page 86
Question for thought......Page 90
1.14 Exercises......Page 89
2.1 Definitions and applications......Page 91
2.2 The complexity of Boolean equations: Cook's theorem......Page 96
2.3 On the role of DNF equations......Page 98
2.4 What does it mean to ``solve a Boolean equation''?......Page 102
2.5 Branching procedures......Page 104
2.5.1 Branching rules......Page 106
Davis-Putnam rules......Page 108
Relaxation schemes......Page 110
2.6 Variable elimination procedures......Page 111
2.7 The consensus procedure......Page 116
2.8.1 Integer linear programming......Page 119
2.8.2 Nonlinear programming......Page 124
2.8.3 Local searchheuristics......Page 126
2.9 Recent trends and algorithmic performance......Page 127
2.10.1 Complexity of equation-solving procedures......Page 128
2.10.2 Random equations......Page 130
2.10.3 Constraint satisfaction problems and Schaefer ’s theorem......Page 132
2.11.1 Counting the number of solutions......Page 135
2.11.2 Generating all solutions......Page 136
2.11.3 Parametric solutions......Page 137
2.11.4 Maximum satisfiability......Page 139
2.12 Exercises......Page 145
3.1 Prime implicants......Page 147
3.1.1 Applications to propositional logic and artificial intelligence......Page 148
3.1.2 Short prime implicants......Page 149
3.2.1 Generation from the set of true points......Page 152
3.2.2 Generation from a DNF representation: The consensus method......Page 154
Variable depletion......Page 159
Term disengagement......Page 161
3.2.3 Generation from a DNF representation: Complexity......Page 162
3.3 Logic minimization......Page 165
3.3.1 Quine-McCluskey approach: Logic minimization as set covering......Page 167
3.3.2 Local simplifications of DNFs......Page 170
3.3.3 Computational complexity of logic minimization......Page 174
3.3.4 Efficient approximation algorithms for logic minimization......Page 180
3.4.1 Number of prime implicants......Page 183
3.4.2 Extremal parameters of minimal DNFs......Page 185
3.4.3 Typical parameters of Boolean functions and their DNFs......Page 186
3.5 Exercises......Page 189
4.1.1 Dual functions and expressions......Page 191
4.1.2 Normal forms and implicants of dual functions......Page 193
4.1.3 Dual-comparable functions......Page 194
4.1.4 Applications......Page 198
4.2.1 Normal forms and implicants of dual functions......Page 200
4.2.2 Dual-comparable functions......Page 202
4.2.3 Applications......Page 203
4.3.1 Definitions and complexity results......Page 207
4.3.2 Dualization by sequential distributivity......Page 210
4.4.1 Some complexity results......Page 213
4.4.2 A quasi-polynomial dualization algorithm......Page 216
4.4.3 Additional results......Page 220
Question for thought......Page 223
4.5 Exercises......Page 222
Part II: Special Classes......Page 225
5.1 Basic definitions and properties......Page 227
5.2 Why are quadratic Boolean functions important?......Page 229
5.3.1 Classes......Page 231
5.3.2 Characterizations by functional relations......Page 232
5.4.1 Graphmodels of quadratic functions......Page 233
5.4.2 The matched graph......Page 234
5.4.3 The implication graph......Page 236
5.4.4 Conflict codes and quadratic graphs......Page 240
5.5.1 Introduction......Page 242
5.5.2 Bipartite graphs......Page 243
5.5.5 Forbidden-color graphbipartition......Page 244
5.5.6 Totally unimodular matrices withtwo nonzero entries per column......Page 245
5.5.7 The Konig-Egerváry property for graphs......Page 247
5.5.8 Single-bend wiring......Page 248
5.5.9 Max-quadratic functions and VLSI design......Page 250
5.5.10 A level graphdrawing problem......Page 251
5.5.11 A final look into complexity......Page 253
5.6.1 Introduction......Page 254
5.6.2 Labeling algorithm (L)......Page 255
5.6.3 Alternative Labeling algorithm (AL)......Page 258
5.6.4 Switching algorithm (S)......Page 259
5.6.5 Strong Components algorithm (SC)......Page 263
5.6.6 An experimental comparison of algorithms for quadratic equations......Page 265
5.7.1 The set of solutions of a quadratic equation......Page 267
5.7.2 Parametric solutions......Page 270
5.7.4 On-line quadratic equations......Page 273
5.8.1 Introduction......Page 274
5.8.2 A transitive closure algorithm for finding all prime implicants......Page 275
5.8.3 A restricted consensus method and its application to computing the transitive closure of a digraph......Page 279
5.8.4 Irredundant normal forms and transitive reductions......Page 285
5.9.1 Introduction......Page 287
5.9.2 The dualization algorithm......Page 288
5.10 Exercises......Page 290
6.1 Basic definitions and properties......Page 293
6.2.1 Propositional rule bases......Page 297
6.2.2 Functional dependencies in databases......Page 298
6.2.3 Directed graphs,hypergraphs,and Petri nets......Page 299
6.2.4 Integer programming and polyhedral combinatorics......Page 300
6.3 False points of Horn functions......Page 301
6.3.1 Deduction in AI......Page 303
6.4.1 Horn equations and the unit literal rule......Page 305
6.4.2 Pure Horn equations and forward chaining......Page 308
6.5 Prime implicants of Horn functions......Page 310
6.6 Properties of the set of prime implicants......Page 316
6.7 Minimization of Horn DNFs......Page 321
6.7.1 Minimizing the number of terms......Page 322
6.7.2 Minimizing the number of literals......Page 325
6.7.3 Minimization of the number of source sides......Page 326
6.8 Dualization of Horn functions......Page 330
6.9.1 Submodular functions......Page 333
6.9.2 Bidual Horn functions......Page 335
6.9.3 Double Horn functions......Page 336
6.9.4 Acyclic Horn functions......Page 337
6.10.1 Renamable Horn expressions and functions......Page 338
6.10.2 Q-Horn functions......Page 341
6.10.3 Extended Horn expressions......Page 343
6.10.4 Polynomial hierarchies built on Horn expressions......Page 344
6.11 Exercises......Page 345
7.1 Computation of orthogonal DNFs......Page 350
7.2.1 Definition......Page 354
7.2.2 Orthogonalization of shellable DNFs......Page 355
7.2.3 Shellable DNFs versus shellable functions......Page 359
7.3 Dualization of shellable DNFs......Page 360
7.4.1 Definition......Page 362
7.4.2 LE property and leaders......Page 363
7.4.3 Recognizing the LE property......Page 364
7.4.4 Dualization of functions having the LE property......Page 369
7.5 Shellable quadratic DNFs and graphs......Page 370
7.6 Applications......Page 372
Questions for thought......Page 373
8.1 Relative strength of variables and regularity......Page 375
8.2 Basic properties......Page 379
8.3 Regularity and left-shifts......Page 386
8.4 Recognition of regular functions......Page 389
Strength preorder and Winder matrix......Page 390
Efficient comparison of variables......Page 391
8.5 Dualization of regular functions......Page 393
8.6 Regular set covering problems......Page 401
8.7 Regular minorants and majorants......Page 404
8.7.1 Largest regular minorant withrespect to a given order......Page 406
8.7.2 Smallest regular majorant withrespect to a given order......Page 410
8.7.3 Regular minorization and set covering problems......Page 412
8.8 Higher-order monotonicity......Page 415
8.9.1 Weakly regular functions......Page 421
8.9.2 Aligned functions......Page 422
8.9.3 Ideal functions......Page 423
8.9.4 Relations among classes......Page 424
8.10 Exercises......Page 425
9.1 Definitions and applications......Page 428
9.2 Basic properties of threshold functions......Page 432
9.3 Characterizations of threshold functions......Page 437
9.4.1 A polynomial-time algorithm for positive DNFs......Page 441
9.4.2 A compact formulation......Page 443
9.4.3 The general case......Page 445
9.5 Prime implicants of threshold functions......Page 447
9.6 Chow parameters of threshold functions......Page 452
9.6.1 Chow functions......Page 453
9.6.2 Chow parameters and separating structures......Page 454
9.6.3 Computing the Chow parameters......Page 459
9.7 Threshold graphs......Page 462
9.8 Exercises......Page 468
10.1 Introduction......Page 472
10.2 Dual implicants......Page 474
10.2.1 Implicants and dual implicants......Page 475
10.2.2 The dual subimplicant theorem......Page 476
10.3 Characterizing read-once functions......Page 480
10.4 The properties of P4-free graphs and cographs......Page 487
10.5 Recognizing read-once functions......Page 490
Testing normality......Page 492
Complexity analysis......Page 493
10.6 Learning read-once functions......Page 497
Complexity......Page 499
10.7.1 The readability of a Boolean function......Page 500
10.7.3 Positional games......Page 501
10.8 Historical notes......Page 504
10.9 Exercises......Page 505
Questions for thought......Page 509
11.1 Characterizations of positive functions......Page 511
11.2 Functional equations......Page 512
11.3.2 Linear functions and related classes......Page 515
11.3.3 Quadratic and degree k functions......Page 517
11.4 Conditions for characterization......Page 519
11.5 Finite characterizations by functional equations......Page 524
11.6 Exercises......Page 530
Part III: Generalizations......Page 533
12.1 Introduction......Page 535
12.2.1 Definitions......Page 538
12.2.2 Support sets of variables......Page 539
12.2.3 Patterns and theories of pdBfs......Page 542
12.2.4 Roles of theories and cotheories......Page 546
12.2.5 Decision trees......Page 550
12.3.1 Positive extensions......Page 555
12.3.2 Monotone (unate)extensions......Page 556
12.3.4 Horn extensions......Page 559
12.3.5 Threshold extensions......Page 562
12.3.6 Decomposable extensions......Page 563
12.3.7 k -convex extensions......Page 569
12.4 Best-fit extensions of pdBfs containing errors......Page 571
12.5 Extensions of pdBfs with missing bits......Page 575
12.5.1 Three types of extensions......Page 576
12.5.2 Complexity results......Page 578
12.6 Minimization with don't cares......Page 582
12.7 Conclusion......Page 585
12.8 Exercises......Page 586
13.1 Definitions and examples......Page 588
Mathematics......Page 589
Computer science and engineering......Page 590
Operations research......Page 592
13.2.1 Polynomial expressions,pseudo-Boolean normal forms and posiforms......Page 594
13.2.2 Piecewise linear representations......Page 597
13.2.3 Disjunctive and conjunctive normal forms......Page 598
13.3 Extensions of pseudo-Boolean functions......Page 602
13.3.1 The polynomial extension......Page 603
13.3.2 Concave and convex extensions......Page 605
13.3.3 The Lovász extension......Page 607
13.4.1 Local optima......Page 609
13.4.2 An elimination algorithm for global optimization......Page 611
The polynomial extension......Page 612
Linearization and concave extensions......Page 613
13.4.4 Posiform transformations and conflict graphs......Page 614
13.6 Special classes of pseudo-Boolean functions......Page 617
13.6.1 Quadratic functions and quadratic 0-1 optimization......Page 618
13.6.2 Monotone functions......Page 620
13.6.3 Supermodular and submodular functions......Page 623
13.6.4 Unimodular functions......Page 628
13.6.5 Threshold and unimodal functions......Page 630
13.7 Exercises......Page 631
Question for thought......Page 632
A.1 Undirected graphs......Page 633
A.1.2 Paths and connectivity......Page 634
A.1.3 Special classes of graphs......Page 635
A.2.1 Directed paths and connectivity......Page 636
A.2.3 Transitive closure and transitive reduction......Page 637
A.3 Hypergraphs......Page 638
B.1 Decision problems......Page 639
B.2 Algorithms......Page 641
B.3 Running time, polynomial-time algorithms, and the class P......Page 642
B.4 The class NP......Page 643
B.5 Polynomial-time reductions and NP-completeness......Page 644
B.6 The class co-NP......Page 645
B.7 Cook's theorem......Page 646
B.8 Complexity of list-generation and counting algorithms......Page 648
C.1 Introduction......Page 651
C.2.1 Menu bar......Page 652
C.3.1 Function syntax and presentation......Page 653
C.3.2 Creation modes......Page 654
C.3.3 Saving a function......Page 655
C.4.2 Modifying the variable set......Page 656
C.5.4 Testing properties of a function......Page 657
Bibliography......Page 659
Index......Page 701