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 $322.00

$277.75

14%OFF

or 4 interest-free payments of $69.44 with

or

Ships in 5 to 7 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

Orders over $79.00 qualify for free shipping.

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

Current Trends in Automated Reasoning - Erika Bach

$40.75

18%
OFF

Unequal

The Maths of When Things Do and Don't Add Up

Hardcover

RRP $39.99

$31.75

21%
OFF

Cryptocurrency Forensics and Investigation using Open Source Intelligence Techniques (OSINT)

Volume I

Paperback

RRP $94.99

$85.75

10%
OFF

Cryptocurrency Forensics and Investigation using Open Source Intelligence Techniques (OSINT)

Volume I

Hardcover

RRP $231.00

$202.75

12%
OFF

Fuzzy Logic in Revolutionizing Renewable Energy : Jenny Stanford Series on Fuzzy Theory Frontiers Vol. 2 - Bhupinder Singh

$233.75

Introduction to Mathematical Logic : Discrete Mathematics and Its Applications - Elliott Mendelson

$187.75

The Times Fiendish Su Doku Book 19 : 200 Challenging Su Doku Puzzles - The Times Mind Games

$137.75

25%
OFF

Reading, Writing, and Proving : A Closer Look at Mathematics - Pamela Gorkin

$69.99

Fuzzy Logic

An Introductory Text

Hardcover

$469.75

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

Current Trends in Automated Reasoning

Automated Theorem Proving

Theory and Practice

Handbook of Automated Reasoning

Current Trends in Automated Theorem Proving

Automated Deduction

From Theory to Applications

Advances in Automated Reasoning

The Language of Mathematics

The Stories behind the Symbols

Unequal

The Maths of When Things Do and Don't Add Up

Cryptocurrency Forensics and Investigation using Open Source Intelligence Techniques (OSINT)

Volume I

Cryptocurrency Forensics and Investigation using Open Source Intelligence Techniques (OSINT)

Volume I

Fuzzy Logic in Revolutionizing Renewable Energy

Jenny Stanford Series on Fuzzy Theory Frontiers Vol. 2

Introduction to Modern Cryptography

Chapman & Hall/Crc Cryptography and Network Security

Introduction to Mathematical Logic

Discrete Mathematics and Its Applications

Introduction to Modern Cryptography

Revised Third Edition

Strongly Minimal Sets and Categoricity in Continuous Logic

The Times Fiendish Su Doku Book 19

200 Challenging Su Doku Puzzles

The Times Ultimate Killer Su Doku Book 18

200 of the Deadliest Su Doku Puzzles

Ignorance

What We Do Not Know, Cannot Know, Must Not Know, and Refuse to Know

Cause, Effect, and Everything in Between

An Introduction to Causal Inference

Reading, Writing, and Proving

A Closer Look at Mathematics

Lectures on the Philosophy of Mathematics

Computable Structure Theory

Beyond the Arithmetic

How to Prove It

A Structured Approach

Fuzzy Logic

An Introductory Text

This product is categorised by