E-Book Content
A Primer for Logic and Proof Holly P. Hirst and Jeffry L. Hirst Spring 20041 1 c °2002 by Jeffry L. Hirst and Holly P. Hirst. All rights reserved. ii Contents Introduction v 1 Propositional Calculus 1.1 Building Blocks . . . . . . . . . . . 1.2 Tautologies and Contradictions . . 1.3 Logical Equivalence . . . . . . . . . 1.4 Contrapositives and Converses . . 1.5 Analysis of Arguments . . . . . . . 1.6 A Proof System . . . . . . . . . . . 1.7 The Deduction Theorem . . . . . . 1.8 Generalizing L . . . . . . . . . . . 1.9 Soundness and Completeness of L . 1.10 Modifying L . . . . . . . . . . . . . 1.11 Assessing Propositional Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 8 10 10 12 15 18 20 22 24 26 2 Predicate Calculus 2.1 Building Blocks . . . . . . . . . . . . 2.2 Translations . . . . . . . . . . . . . . 2.3 A brief interlude: Truth . . . . . . . 2.4 Free variables . . . . . . . . . . . . . 2.5 Models . . . . . . . . . . . . . . . . . 2.6 Truth and Sentences . . . . . . . . . 2.7 Truth and free variables . . . . . . . 2.8 Logical validity . . . . . . . . . . . . 2.9 Formulas that aren’t logically valid . 2.10 Some logically valid formulas . . . . 2.11 Free for... . . . . . . . . . . . . . . . 2.12 A proof system for predicate calculus 2.13 Dealing with ∀ . . . . . . . . . . . . 2.14 Rule T . . . . . . . . . . . . . . . . . 2.15 The Deduction