“mcs”一2018/6/6一13：43一page ifⅲi一#3 Contents Proofs Introduction 3 0.1 References 4 1 What is a Proof?5 1.1 Propositions 5 P 1.2 Predicates 1.3 The Axiomatic Method 8 1.4 Our Axioms 9 1.5 Proving an Implication 11 1.6 Proving an“If and Only If'”l3 1.7 Proof by Cases 15 1.8 Proof by Contradiction 16 1.9 Good Proofs in Practice 17 1.10 References 19 2 The Well Ordering Principle 29 2.1 Well Ordering Proofs 29 2.2 Template for WOP Proofs 30 2.3 Factoring into Primes 32 2.4 Well Ordered Sets 33 3 Logical Formulas 47 3.1 Propositions from Propositions 48 3.2 Propositional Logic in Computer Programs 52 3.3 Equivalence and Validity 54 3.4 The Algebra of Propositions 57 3.5 The SAT Problem 62 3.6 Predicate Formulas 63 3.7 References 68 4 Mathematical Data Types 103 4.1Sets103 4.2 Sequences 108 4.3 Functions 109 4.4 Binary Relations 111 4.5 Finite Cardinality 115“mcs” — 2018/6/6 — 13:43 — page iii — #3 Contents I Proofs Introduction 3 0.1 References 4 1 What is a Proof? 5 1.1 Propositions 5 1.2 Predicates 8 1.3 The Axiomatic Method 8 1.4 Our Axioms 9 1.5 Proving an Implication 11 1.6 Proving an “If and Only If” 13 1.7 Proof by Cases 15 1.8 Proof by Contradiction 16 1.9 Good Proofs in Practice 17 1.10 References 19 2 The Well Ordering Principle 29 2.1 Well Ordering Proofs 29 2.2 Template for WOP Proofs 30 2.3 Factoring into Primes 32 2.4 Well Ordered Sets 33 3 Logical Formulas 47 3.1 Propositions from Propositions 48 3.2 Propositional Logic in Computer Programs 52 3.3 Equivalence and Validity 54 3.4 The Algebra of Propositions 57 3.5 The SAT Problem 62 3.6 Predicate Formulas 63 3.7 References 68 4 Mathematical Data Types 103 4.1 Sets 103 4.2 Sequences 108 4.3 Functions 109 4.4 Binary Relations 111 4.5 Finite Cardinality 115