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
| 1 | |
| 6 | |
Modern Algebra | 18 |
Exercises for Chapter 2 | 38 |
Applications of Propositional Calculus | 82 |
Hilbertstyle Proofs | 109 |
Formal Logic | 125 |
Quantification 139 | 138 |
A Theory of Sets | 195 |
A Theory of Sequences | 251 |
Relations and Functions | 265 |
A Theory of Integers | 303 |
Combinatorial Analysis | 337 |
Recurrence Relations | 363 |
A Theory of Graphs | 422 |
Exercises for Chapter 19 | 458 |
Other editions - View all
Common terms and phrases
algebra algorithm argument Arithmetic assignment Assumption Axiom binary binary operator boolean expression called circuit conjunct Consider constructive contains defined denote Distributivity dummy edges eliminate English equal equational equivalent evaluated example Exercises existential quantification false finite following theorem formal formula Golden rule graph Hence heuristic Hilbert Hint Historical note idempotent identity implemented inductive hypothesis inference rules input integers inverse iteration Leibniz loop manipulation mathematical induction mathematics Metatheorem minimal element Modus ponens mutual implication natural deduction natural numbers negation notation One-point rule one-to-one operands operator pair parentheses permutations pigeonhole principle postcondition precondition predicate logic proof properties propositional calculus propositional logic prove the following Prove theorem range real numbers reflexive relation replaced satisfies sequence statement subset Superman symbols Symmetry textual substitution theory Transitivity true truth table universal quantification valid vertex vertices zero