Preface 

xv  
Note to the Student 

xvii  


1  (87) 

Statements, Symbolic Representation, and Tautologies 


2  (19) 

Connectives and Truth Values 


2  (6) 


8  (2) 

Logical Connectives in the Real World 


10  (1) 


11  (3) 


14  (7) 


21  (14) 


21  (3) 

Derivation Rules for Propositional Logic 


24  (3) 

Deduction Method and Other Rules 


27  (2) 


29  (2) 


31  (4) 

Quantifiers, Predicates, and Validity 


35  (14) 

Quantifiers and Predicates 


35  (3) 


38  (3) 


41  (2) 


43  (6) 


49  (14) 

Derivation Rules for Predicate Logic 


49  (2) 


51  (1) 

Existential Instantiation 


51  (1) 


52  (1) 

Existential Generalization 


53  (1) 


54  (4) 


58  (1) 


59  (1) 


60  (3) 


63  (11) 


64  (2) 

Horn Clauses and Resolution 


66  (3) 


69  (3) 


72  (1) 


72  (2) 


74  (14) 


75  (1) 


76  (3) 


79  (3) 


82  (2) 


84  (3) 


87  (1) 

Proofs, Recursion, and Analysis of Algorithms 


88  (98) 


89  (11) 

Theorems and Informal Proofs 


89  (1) 


90  (1) 


91  (1) 


92  (1) 


93  (2) 


95  (1) 


96  (1) 


97  (1) 


98  (2) 


100  (18) 

First Principle of Induction 


100  (2) 

Proofs by Mathematical Induction 


102  (5) 

Second Principle of Induction 


107  (5) 


112  (6) 

More on Proof of Correctness 


118  (11) 


118  (3) 


121  (3) 


124  (5) 


129  (18) 

Recursively Defined Sequences 


129  (3) 


132  (2) 

Recursively Defined Operations 


134  (1) 

Recursively Defined Algorithms 


135  (5) 


140  (7) 


147  (22) 

Linear FirstOrder Recurrence Relations 


147  (1) 

Expand, Guess, and Verify 


147  (2) 


149  (7) 

Linear SecondOrder Recurrence Relations 


156  (5) 

DivideandConquer Recurrence Relations 


161  (3) 


164  (5) 


169  (17) 


169  (3) 

Analysis Using Recurrence Relations 


172  (2) 

Upper Bound (Euclidean Algorithm) 


174  (1) 


175  (6) 


181  (2) 


183  (3) 

Sets, Combinatorics, Probability, and Number Theory 


186  (99) 


187  (24) 


187  (2) 

Relationships Between Sets 


189  (2) 


191  (1) 

Binary and Unary Operations 


192  (2) 


194  (2) 


196  (3) 

Countable and Uncountable Sets 


199  (3) 


202  (9) 


211  (14) 


212  (3) 


215  (1) 

Using the Principles Together 


216  (2) 


218  (2) 


220  (5) 

Principle of Inclusion and Exclusion; Pigeonhole Principle 


225  (8) 

Principle of Inclusion and Exclusion 


225  (5) 


230  (1) 


231  (2) 

Permutations and Combinations 


233  (19) 


233  (2) 


235  (3) 


238  (1) 

Permutations and Combinations with Repetitions 


239  (7) 


246  (6) 


252  (14) 

Introduction to Finite Probability 


252  (2) 

Probability Distributions 


254  (2) 


256  (1) 


257  (3) 

Average Case Analysis of Algorithms 


260  (1) 


261  (5) 


266  (6) 


266  (1) 

Binomial Theorem and Its Proof 


267  (2) 

Applying the Binomial Theorem 


269  (1) 


270  (2) 


272  (13) 

Fundamental Theorem of Arithmetic 


272  (4) 


276  (1) 


277  (2) 


279  (2) 


281  (2) 


283  (2) 

Relations, Functions, and Matrices 


285  (116) 


286  (25) 


286  (3) 


289  (2) 


291  (2) 


293  (2) 


295  (6) 


301  (10) 


311  (8) 


316  (3) 


319  (12) 

EntityRelationship Model 


319  (1) 


320  (3) 


323  (3) 

Null Values and ThreeValued Logic 


326  (2) 


328  (1) 


329  (2) 


331  (31) 


332  (5) 


337  (1) 


337  (1) 


338  (1) 


339  (1) 


339  (2) 


341  (2) 


343  (2) 


345  (3) 


348  (1) 

Order of Magnitude of Functions 


349  (3) 

More on Analysis of Algorithms 


352  (2) 


354  (8) 


362  (20) 


363  (3) 


366  (1) 


366  (6) 

Hashing for Password Encryption 


372  (1) 

Miscellaneous Applications 


373  (1) 


373  (2) 

Generating and Decomposing Integers 


375  (1) 

Modular Arithmetic Designs 


376  (2) 


378  (4) 


382  (19) 


382  (2) 


384  (4) 


388  (2) 


390  (6) 


396  (3) 


399  (2) 


401  (74) 

Graphs and Their Representations 


402  (31) 


402  (3) 


405  (2) 


407  (3) 


410  (3) 


413  (5) 

Computer Representation of Graphs 


418  (1) 


418  (2) 


420  (3) 


423  (10) 

Trees and Their Representations 


433  (18) 


433  (2) 


435  (2) 

Binary Tree Representation 


437  (1) 

Tree Traversal Algorithms 


438  (4) 


442  (2) 


444  (7) 


451  (11) 


452  (2) 

Lower Bounds on Searching 


454  (1) 


455  (2) 


457  (2) 


459  (3) 


462  (13) 

Problem and Trial Solution 


462  (2) 

Huffman Encoding Algorithm 


464  (2) 


466  (2) 

Applications of Huffman Codes 


468  (1) 


469  (3) 


472  (2) 


474  (1) 


475  (59) 

Directed Graphs and Binary Relations; Warshall's Algorithm 


476  (14) 

Directed Graphs and Binary Relations 


477  (2) 


479  (4) 


483  (4) 


487  (3) 

Euler Path and Hamiltonian Circuit 


490  (9) 


490  (5) 

Hamiltonian Circuit Problem 


495  (1) 


496  (3) 

Shortest Path and Minimal Spanning Tree 


499  (14) 


499  (6) 

Minimal Spanning Tree Problem 


505  (2) 


507  (6) 


513  (11) 


513  (2) 


515  (3) 


518  (1) 


519  (2) 


521  (3) 

Articulation Points and Computer Networks 


524  (10) 


524  (1) 

The Idea Behind the Algorithm 


525  (1) 


526  (3) 


529  (2) 


531  (1) 


532  (2) 

Boolean Algebra and Computer Logic 


534  (58) 

Boolean Algebra Structure 


535  (17) 


536  (1) 

Definition and Properties 


537  (4) 

Isomorphic Boolean Algebras 


541  (1) 


541  (3) 

Isomorphism as Applied to Boolean Algebra 


544  (2) 


546  (6) 


552  (22) 


552  (1) 


552  (1) 


553  (1) 


554  (1) 


554  (2) 


556  (2) 


558  (2) 

Programmable Logic Arrays 


560  (2) 


562  (2) 


564  (1) 

Constructing Truth Functions 


565  (1) 


566  (8) 


574  (18) 


574  (1) 


575  (1) 

Maps for Three and Four Variables 


576  (2) 


578  (4) 

QuineMcCluskey Procedure 


582  (4) 


586  (4) 


590  (1) 


591  (1) 

Modeling Arithmetic, Computation, and Languages 


592  (93) 


593  (25) 


593  (7) 

Basic Results About Groups 


600  (3) 


603  (3) 


606  (6) 


612  (6) 


618  (28) 


618  (1) 

Examples of FiniteState Machines 


619  (3) 


622  (2) 

Regular Sets and Kleene's Theorem 


624  (2) 


626  (1) 


626  (1) 


627  (5) 

Sequential Networks and FiniteState Machines 


632  (4) 


636  (10) 


646  (20) 


647  (4) 

Turing Machines as Set Recognizers 


651  (2) 

Turing Machines as Function Computers 


653  (2) 


655  (2) 

Decision Problems and Uncomputability 


657  (1) 

Examples of Decision Problems 


658  (1) 


659  (1) 


660  (3) 


663  (3) 


666  (19) 


672  (3) 

Formal Languages and Computational Devices 


675  (1) 


676  (3) 


679  (3) 


682  (2) 


684  (1) 
Appendix A Derivation Rules for Propositional and Predicate Logic 

685  (2) 
Appendix B Summation Notation 

687  (3) 
Appendix C The Logarithm Function 

690  (3) 
Answers to Practice Problems 

693  (34) 
Answers to Selected Exercises 

727  (62) 
Answers to SelfTests 

789  (8) 
Index 

797  