A Primer for Logic and Proof

By addebook • Jul 14th, 2008 • Category: Mathematics

A Primer for Logic and Proof (Lecture Notes)

Contents

1 Propositional Calculus 1
1.1 Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Tautologies and Contradictions . . . . . . . . . . . . . . . . . . . 8
1.3 Logical Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Contrapositives and Converses . . . . . . . . . . . . . . . . . . . 10
1.5 Analysis of Arguments . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 A Proof System . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.7 The Deduction Theorem . . . . . . . . . . . . . . . . . . . . . . . 18
1.8 Generalizing L . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.9 Soundness and Completeness of L . . . . . . . . . . . . . . . . . . 22
1.10 Modifying L . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.11 Assessing Propositional Calculus . . . . . . . . . . . . . . . . . . 26

2 Predicate Calculus 29
2.1 Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 Translations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3 A brief interlude: Truth . . . . . . . . . . . . . . . . . . . . . . . 35
2.4 Free variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.5 Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.6 Truth and Sentences . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.7 Truth and free variables . . . . . . . . . . . . . . . . . . . . . . . 42
2.8 Logical validity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.9 Formulas that aren’t logically valid . . . . . . . . . . . . . . . . . 45
2.10 Some logically valid formulas . . . . . . . . . . . . . . . . . . . . 46
2.11 Free for… . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.12 A proof system for predicate calculus . . . . . . . . . . . . . . . . 51
2.13 Dealing with 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.14 Rule T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.15 The Deduction Theorem . . . . . . . . . . . . . . . . . . . . . . . 55
2.16 Adding 9x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.17 Removing 9x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.18 Proof strategies in predicate calculus . . . . . . . . . . . . . . . . 60

3 Transition to Informal Proofs 63
3.1 The Theory of Equality . . . . . . . . . . . . . . . . . . . . . . . 64
3.2 Formal Number Theory . . . . . . . . . . . . . . . . . . . . . . . 66
3.3 More about induction . . . . . . . . . . . . . . . . . . . . . . . . 69
3.4 Inductive Pitfalls . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.5 Proofs by Contradiction . . . . . . . . . . . . . . . . . . . . . . . 75
3.6 Other Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

4 Alternation of Quantifers – Sequences 83
4.1 Sequences, Bounds and Convergence . . . . . . . . . . . . . . . . 84
4.2 More on Convergence and Boundedness . . . . . . . . . . . . . . 89
4.3 A Note on Divergent Sequences . . . . . . . . . . . . . . . . . . . 91

Free download Links

http://mihd.net/ybad53
http://rapidshare.com/files/76301466/lopro.rar