This text attempts to change the way logic and discrete mathematics are taught. While many books treat logic simply as another topic of study, this book treats logic as a basic tool to be applied in essentially every other area. The book is organized so that selected chapters can either be studied together or used as a reference. The core of the book consists of textual substitution, equality and assignment, Boolean expressions, propositional calculus, quantification and predicate calculus. The remaining chapters can be selected according to individual course outlines.
Author(s): David Gries, Fred B. Schneider
Series: Texts and Monographs in Computer Science
Publisher: Springer
Year: 1993
Language: English
Pages: 527
Front cover......Page 1
Back cover......Page 2
Types Used in this Text......Page 4
Texts and Monographs in Computer Science Series......Page 5
Books in the Series......Page 6
Title page......Page 7
Copyright page......Page 8
Dedication......Page 9
Preface......Page 11
Contents......Page 17
0 Using Mathematics......Page 21
1.1 Preliminaries......Page 27
1.2 Textual substitution......Page 28
1.3 Textual substitution and equality......Page 31
1.4 Leibniz's rule and function evaluation......Page 33
1.5 Reasoning using Leibniz's rule......Page 34
1.6 The assignment statement......Page 36
Exercises for Chapter 1......Page 41
2.1 Syntax and evaluation of boolean expressions......Page 45
2.2 Equality versus equivalence......Page 49
2.3 Satisfiability, validity and duality......Page 51
2.4 Modeling English propositions......Page 52
Exercises for Chapter 2......Page 58
3.1 Preliminaries......Page 61
3.2 Equivalence and true......Page 63
3.3 Negation, inequivalence, and false......Page 65
3.4 Disjunction......Page 69
3.5 Conjunction......Page 71
3.6 Implication......Page 76
Exercises for Chapter 3......Page 82
4.1 An abbreviation for proving implications......Page 89
4.2 Additional proof techniques......Page 91
Exercises for Chapter 4......Page 100
5.1 Solving word problems......Page 103
5.2 Combinational digital circuits......Page 110
Exercises for Chapter 5......Page 124
6.1 Hilbert-style proofs......Page 129
6.2 Natural deduction......Page 133
6.3 Additional proof formats......Page 138
6.4 Styles of reasoning......Page 140
Exercises for Chapter 6......Page 142
7.1 Formal logical systems......Page 145
7.2 Constructive logics......Page 150
Exercises for Chapter 7......Page 154
8.1 On types......Page 159
8.2 Syntax and interpretation of quantification......Page 162
8.3 Rules about quantification......Page 167
8.4 Manipulating ranges......Page 172
Exercises for Chapter 8......Page 175
9 Predicate Calculus......Page 177
9.1 Universal quantification......Page 178
9.2 Existential quantification......Page 183
9.3 English to predicate logic......Page 188
Exercises for Chapter 9......Page 193
10.1 Specification of programs......Page 199
10.2 Reasoning about the assignment statement......Page 201
10.3 Calculating parts of assignments......Page 206
10.4 Conditional statements and expressions......Page 208
Exercises for Chapter 10......Page 211
11.1 Set comprehension and membership......Page 215
11.2 Operations on sets......Page 221
11.3 Theorems concerning set operations......Page 223
11.4 Union and intersection of families of sets......Page 228
11.5 The axiom of choice '......Page 229
11.6 Ill-defined sets and paradoxes......Page 230
11.7 Bags......Page 231
Exercises for Chapter 11......Page 233
12.1 Induction over the natural numbers......Page 237
12.2 Inductive definitions......Page 242
12.3 Peano arithmetic......Page 247
12.4 Induction and well-founded sets......Page 248
12.5 Induction for inductive definitions......Page 252
12.6 The correctness of loops......Page 256
Exercises for Chapter 12......Page 263
13.1 The basic theory of sequences......Page 271
13.2 Extending the theory with new operations......Page 274
13.3 Extending the theory to use integers......Page 278
Exercises for Chapter 13......Page 282
14.1 Tuples and cross products......Page 285
14.2 Relations......Page 287
14.3 Functions......Page 299
14.4 Order relations......Page 305
14.5 Relational Databases......Page 314
Exercises for Chapter 14......Page 319
15.1 Integral domains......Page 323
15.2 Exploring minimum and maximum......Page 331
15.3 Exploring absolutes......Page 334
15.4 Divisibility, common divisors, and primes......Page 335
15.5 Common representations of natural numbers......Page 347
Exercises for Chapter 15......Page 351
16.1 Rules of counting......Page 357
16.2 Properties of n choose r......Page 363
16.3 Examples of counting......Page 368
16.4 The pigeonhole principle......Page 375
Exercises for Chapter 16......Page 377
17.1 Homogeneous difference equations......Page 383
17.2 Nonhomogeneous difference equations......Page 391
17.3 Generating functions......Page 395
Exercises for Chapter 17......Page 403
18.1 The structure of algebras......Page 407
18.2 Group theory......Page 416
18.3 Boolean algebras......Page 432
Exercises for Chapter 18......Page 437
19.1 Graphs and multigraphs......Page 443
19.2 Three applications of graph theory......Page 450
19.3 Classes of graphs......Page 456
19.4 Subgraphs and morphisms......Page 457
19.5 Hamilton circuits......Page 459
19.6 Planar graphs......Page 465
19.7 Shortest paths and spanning trees......Page 469
Exercises for Chapter 19......Page 478
20.1 Finite versus infinite sets......Page 481
20.2 The cardinality of an infinite set......Page 482
20.3 Countable and uncountable sets......Page 486
Exercises for Chapter 20......Page 490
References......Page 493
Index......Page 497
Books in the Series......Page 519
Theorems of the propositional and predicate calculi......Page 523
