A Logical Approach to Discrete Math

Front Cover
Springer Science & Business Media, Oct 22, 1993 - Computers - 516 pages
6 Reviews
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.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

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
503
Copyright

Other editions - View all

Common terms and phrases

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.

References to this book

All Book Search results »

Bibliographic information