## A Logical Approach to Discrete MathThis text attempts to change the way we teach logic to beginning students. Instead of teaching logic as a subject in isolation, we regard it as a basic tool and show how to use it. We strive to give students a skill in the propo sitional and predicate calculi and then to exercise that skill thoroughly in applications that arise in computer science and discrete mathematics. We are not logicians, but programming methodologists, and this text reflects that perspective. We are among the first generation of scientists who are more interested in using logic than in studying it. With this text, we hope to empower further generations of computer scientists and math ematicians to become serious users of logic. Logic is the glue Logic is the glue that binds together methods of reasoning, in all domains. The traditional proof methods -for example, proof by assumption, con tradiction, mutual implication, and induction- have their basis in formal logic. Thus, whether proofs are to be presented formally or informally, a study of logic can provide understanding. |

### Contents

Textual Substitution Equality and Assignment | 7 |

12 Textual substitution | 8 |

13 Textual substitution and equality | 11 |

14 Leibnizs rule and function evaluation | 13 |

15 Reasoning using Leibnizs rule | 14 |

16 The assignment statement | 16 |

Exercises for Chapter 1 | 21 |

Boolean Expressions | 25 |

117 Bags | 211 |

Exercises for Chapter 11 | 213 |

Mathematical Induction | 217 |

122 Inductive definitions | 222 |

123 Peano arithmetic | 227 |

124 Induction and wellfounded sets | 228 |

125 Induction for inductive definitions | 232 |

126 The correctness of loops | 236 |

22 Equality versus equivalence | 29 |

23 Satisfiability validity and duality | 31 |

24 Modeling English propositions | 32 |

Exercises for Chapter 2 | 38 |

Propositional Calculus | 41 |

32 Equivalence and true | 43 |

33 Negation inequivalence and false | 45 |

34 Disjunction | 49 |

35 Conjunction | 51 |

36 Implication | 56 |

Exercises for Chapter 3 | 62 |

Relaxing the Proof Style | 69 |

42 Additional proof techniques | 71 |

Exercises for Chapter 4 | 80 |

Applications of Propositional Calculus | 83 |

52 Combinational digital circuits | 90 |

Exercises for Chapter 5 | 104 |

Chapter 6 Hilbertstyle Proofs | 109 |

62 Natural deduction | 113 |

63 Additional proof formats | 118 |

64 Styles of reasoning | 120 |

Exercises for Chapter 6 | 122 |

Formal Logic | 125 |

72 Constructive logics | 130 |

Exercises for Chapter 7 | 134 |

Quantification | 139 |

82 Syntax and interpretation of quantification | 142 |

83 Rules about quantification | 147 |

84 Manipulating ranges | 152 |

Exercises for Chapter 8 | 155 |

Predicate Calculus | 157 |

91 Universal quantification | 158 |

92 Existential quantification | 163 |

93 English to predicate logic | 168 |

Exercises for Chapter 9 | 173 |

Predicates and Programming | 179 |

102 Reasoning about the assignment statement | 181 |

103 Calculating parts of assignments | 186 |

104 Conditional statements and expressions | 188 |

Exercises for Chapter 10 | 191 |

A Theory of Sets | 195 |

112 Operations on sets | 201 |

113 Theorems concerning set operations | 203 |

114 Union and intersection of families of sets | 208 |

115 The axiom of choice | 209 |

116 Illdefined sets and paradoxes | 210 |

Exercises for Chapter 12 | 243 |

A Theory of Sequences | 251 |

132 Extending the theory with new operations | 254 |

133 Extending the theory to use integers | 258 |

Exercises for Chapter 13 | 262 |

Relations and Functions | 265 |

142 Relations | 267 |

143 Functions | 279 |

144 Order relations | 285 |

145 Relational Databases | 294 |

Exercises for Chapter 14 | 299 |

A Theory of Integers | 303 |

152 Exploring minimum and maximum | 311 |

153 Exploring absolutes | 314 |

154 Divisibility common divisors and primes | 315 |

155 Common representations of natural numbers | 327 |

Exercises for Chapter 15 | 331 |

Combinatorial Analysis | 337 |

162 Properties of n choose r | 343 |

163 Examples of counting | 348 |

164 The pigeonhole principle | 355 |

Exercises for Chapter 16 | 357 |

Recurrence Relations | 363 |

172 Nonhomogeneous difference equations | 371 |

173 Generating functions | 375 |

Exercises for Chapter 17 | 383 |

Modern Algebra | 387 |

182 Group theory | 396 |

183 Boolean algebras | 412 |

Exercises for Chapter 18 | 417 |

A Theory of Graphs | 423 |

192 Three applications of graph theory | 430 |

193 Classes of graphs | 436 |

194 Subgraphs and morphisms | 437 |

195 Hamilton circuits | 439 |

196 Planar graphs | 445 |

197 Shortest paths and spanning trees | 449 |

Exercises for Chapter 19 | 458 |

Infinite Sets | 461 |

202 The cardinality of an infinite set | 462 |

203 Countable and uncountable sets | 466 |

Exercises for Chapter 20 | 470 |

References | 473 |

477 | |

Theorems of the Propositional Calculus | |

### Other editions - View all

### Common terms and phrases

addition algebra algorithm allows application argument Arithmetic assignment associative assume Axiom base beginning binary boolean expression bound calculus called Chapter choose circuit conjunct Consider construct contains defined Definition denote Distributivity edges elements English equal equational equivalent example Exercises exists false finite formal formula function give given graph Hence Historical note holds identity implication induction inference rules infinite integers inverse least logic loop manipulation mathematics means method multiple natural numbers notation operator pair path permutations positive possible predicate problem proof properties propositional Prove theorem Provided quantification range reasoning relation replaced requires rule satisfies sequence solution statement subset substitution Suppose Symmetry theory Transitivity tree true valid variables vertex vertices write zero

### Popular passages

Page 3 - It remains to discuss briefly what general requirements may be justly laid down for the solution of a mathematical problem. I should say first of all, this : that it shall be possible to establish the correctness of the solution by means of a finite number of steps based upon a finite number of hypotheses which are implied in the statement of the problem and which must always be exactly formulated.

Page 3 - It is an error to believe that rigor in the proof is the enemy of simplicity. On the contrary, we find it confirmed by numerous examples that the rigorous method is at the same time the simpler and the more easily comprehended. The very effort for rigor forces us to discover simpler methods of proof.