A Logical Approach to Discrete Math

Description

Front cover ......Page 1 Types Used in this Text ......Page 2 Texts and Monographs in Computer Science Series ......Page 3 Books in the Series ......Page 4 Title page ......Page 5 Copyright page ......Page 6 Dedication ......Page 7 Preface ......Page 9 Contents ......Page 15 0 Using Mathematics ......Page 19 1.1 Preliminaries ......Page 25 1.2 Textual substitution ......Page 26 1.3 Textual substitution and equality ......Page 29 1.4 Leibniz's rule and function evaluation ......Page 31 1.5 Reasoning using Leibniz's rule ......Page 32 1.6 The assignment statement ......Page 34 Exercises for Chapter 1 ......Page 39 2.1 Syntax and evaluation of boolean expressions ......Page 43 2.2 Equality versus equivalence ......Page 47 2.3 Satisfiability, validity and duality ......Page 49 2.4 Modeling English propositions ......Page 50 Exercises for Chapter 2 ......Page 56 3.1 Preliminaries ......Page 59 3.2 Equivalence and true ......Page 61 3.3 Negation, inequivalence, and false ......Page 63 3.4 Disjunction ......Page 67 3.5 Conjunction ......Page 69 3.6 Implication ......Page 74 Exercises for Chapter 3 ......Page 80 4.1 An abbreviation for proving implications ......Page 87 4.2 Additional proof techniques ......Page 89 Exercises for Chapter 4 ......Page 98 5.1 Solving word problems ......Page 101 5.2 Combinational digital circuits ......Page 108 Exercises for Chapter 5 ......Page 122 6.1 Hilbert-style proofs ......Page 127 6.2 Natural deduction ......Page 131 6.3 Additional proof formats ......Page 136 6.4 Styles of reasoning ......Page 138 Exercises for Chapter 6 ......Page 140 7.1 Formal logical systems ......Page 143 7.2 Constructive logics ......Page 148 Exercises for Chapter 7 ......Page 152 8.1 On types ......Page 157 8.2 Syntax and interpretation of quantification ......Page 160 8.3 Rules about quantification ......Page 165 8.4 Manipulating ranges ......Page 170 Exercises for Chapter 8 ......Page 173 9 Predicate Calculus ......Page 175 9.1 Universal quantification ......Page 176 9.2 Existential quantification ......Page 181 9.3 English to predicate logic ......Page 186 Exercises for Chapter 9 ......Page 191 10.1 Specification of programs ......Page 197 10.2 Reasoning about the assignment statement ......Page 199 10.3 Calculating parts of assignments ......Page 204 10.4 Conditional statements and expressions ......Page 206 Exercises for Chapter 10 ......Page 209 11.1 Set comprehension and membership ......Page 213 11.2 Operations on sets ......Page 219 11.3 Theorems concerning set operations ......Page 221 11.4 Union and intersection of families of sets ......Page 226 11.5 The axiom of choice ' ......Page 227 11.6 Ill-defined sets and paradoxes ......Page 228 11.7 Bags ......Page 229 Exercises for Chapter 11 ......Page 231 12.1 Induction over the natural numbers ......Page 235 12.2 Inductive definitions ......Page 240 12.3 Peano arithmetic ......Page 245 12.4 Induction and well-founded sets ......Page 246 12.5 Induction for inductive definitions ......Page 250 12.6 The correctness of loops ......Page 254 Exercises for Chapter 12 ......Page 261 13.1 The basic theory of sequences ......Page 269 13.2 Extending the theory with new operations ......Page 272 13.3 Extending the theory to use integers ......Page 276 Exercises for Chapter 13 ......Page 280 14.1 Tuples and cross products ......Page 283 14.2 Relations ......Page 285 14.3 Functions ......Page 297 14.4 Order relations ......Page 303 14.5 Relational Databases ......Page 312 Exercises for Chapter 14 ......Page 317 15.1 Integral domains ......Page 321 15.2 Exploring minimum and maximum ......Page 329 15.3 Exploring absolutes ......Page 332 15.4 Divisibility, common divisors, and primes ......Page 333 15.5 Common representations of natural numbers ......Page 345 Exercises for Chapter 15 ......Page 349 16.1 Rules of counting ......Page 355 16.2 Properties of n choose r ......Page 361 16.3 Examples of counting ......Page 366 16.4 The pigeonhole principle ......Page 373 Exercises for Chapter 16 ......Page 375 17.1 Homogeneous difference equations ......Page 381 17.2 Nonhomogeneous difference equations ......Page 389 17.3 Generating functions ......Page 393 Exercises for Chapter 17 ......Page 401 18.1 The structure of algebras ......Page 405 18.2 Group theory ......Page 414 18.3 Boolean algebras ......Page 430 Exercises for Chapter 18 ......Page 435 19.1 Graphs and multigraphs ......Page 441 19.2 Three applications of graph theory ......Page 448 19.3 Classes of graphs ......Page 454 19.4 Subgraphs and morphisms ......Page 455 19.5 Hamilton circuits ......Page 457 19.6 Planar graphs ......Page 463 19.7 Shortest paths and spanning trees ......Page 467 Exercises for Chapter 19 ......Page 476 20.1 Finite versus infinite sets ......Page 479 20.2 The cardinality of an infinite set ......Page 480 20.3 Countable and uncountable sets ......Page 484 Exercises for Chapter 20 ......Page 488 References ......Page 491 Index ......Page 495 Books in the Series ......Page 517 Theorems of the propositional and predicate calculi ......Page 520 Back cover ......Page 530