# A Logical Approach to Discrete Math

Springer Science & Business Media, Oct 22, 1993 - Computers - 516 pages
This 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 Index 477 Theorems of the Propositional Calculus Copyright

### 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.