Contents
ix
2.3.2 Substitutions into Tautologies 109
2.3.3 Logically Valid Inferences 109
2.3.4 Combinatorial Networks 112
2.3.5 Substituting Equivalent Subformulas 114
2.3.6 Simplifying Negations 115
2.4 Exercises 116
2.5 Normal Forms 121
2.5.1 Disjunctive Normal Form 122
2.5.2 Application: DNF and Combinatorial Networks 124
2.5.3 Conjunctive Normal Form 125
2.5.4 Application: CNF and Combinatorial Networks 127
2.5.5 Testing Satisfiability and Validity 127
2.5.6 The Famous 'P Af r Conjecture 129
2.5.7 Resolution Proofs: Automating Logic 129
2.6 Exercises 131
2.7 Predicates and Quantification 134
2.71 Predicates 135
2.72 Quantification 135
2.73 Restricted Quantification 136
2.74 Nested Quantifiers 137
2.75 Negation and Quantification 138
2.76 Quantification with Conjunction and Disjunction 139
2.77 Application: Loop Invariant Assertions 141
2.8 Exercises 143
2.9 Chapter Review 147
2.9.1 Summary 148
2.9.2 Starting to Review 149
2.9.3 Review Questions 150
2.9.4 Using Discrete Mathematics in Computer Science 151
CHAPTER 3
Relations
157
3.1 Binary Relations 157
3.1.1 n-ary Relations 162