Understanding Symbolic Logic

PREFACETheauthorhas triedtowrite a textbook suitedtotheneedsandpreferencesofthelargest possiblenumberof those whoteachsymbolic logic.Thebook presupposes no specialpreparationinlogicormathematics.Ittreatsa largevarietyof topicsandallowstheinstructorconsiderablelatitudeintheselection of topicstocover,andintheorderinwhichtocover them. Consequently,thebook lends itselftoadoptionincourses whose lengthsvaryfrom onequartertoa full academic year. (SeeTableof SuggestedCouJ·ses.)Theauthorhasendeavoredtoachieve clarity of exposi-tion, hopingthebook will alsobeusefultothose engagedinanindependentstudyof symbolic logic.Therearemanygood symbolic logic textbooks available.Ofthese each willbefound superiorinoneorseveral respectstotheothers.Theauthorfeltittobehisprimarypedagogical obligationtoimitate, sofarashewas able,thevarious excellences of thesebooks.Thuswhatnoveltythepresent book possesses springs fromnecessity,notdesign.Theauthorconfessestoaratherlooseandcavaliertreatmentofmeaning.Thebook exploits asharpanalytic-synthetic distinctionandpresentssynonymyasanintuitivelycleai-·relation.Theauthoris aware ofthedifficulties surroundingtheaforementioned distinc-tionandrelation,butheis unaware of less problematic surrogatesthathavecomparable pedagogicalandexpository value.Finally,theauthoracknowledges withgratitudehis personalindebtednesstomanycolleagues, students,andassociates who inmyriad ,wayscontributedtowhatevermeritsthisbool{has.Tonamethemall wouldbeimpossible,butspecial mer1tionmustbegiventoHerber.tE.HendryandJamesE.Roper.Pittsburgh, PennsylvaniaOctober,1969 Preface Table of Suggested Courses Explanation of Grading of Exercises Part ONE: Truth-Functional Logic 1. Preliminaries 1.0. Scope of Text 1.1. Symbolic Logic; the Logistic Method 2. Truth-functional Sentence Connectives (I) 2.0. Conjunction 2.1. Disjunction or Alternation 2.2. Negation 3. Exercises 4. Language Schema P 4.0. Vocabulary 4.1. Formation Rules 4.2. Use and Mention; Quotation Marks and Corners 5. Exercises 6. Semantics of Language Schema P 6.0. Semantics 6.1. Truth Tables 6.2. Interpreting Language Schema P 7. Exercises 8. Logical Truth and Analyticity 8.0. Logical Truth and Logical Falsehood 8.1. Analytic and Synthetic Sentences 9. Exercises 10. Abbreviation and Equivalence 10.0. Some Abbreviative Conventions 10.1. Equivalence 10.2. Tolerably Ambiguous Abbreviations 11. Exercises 12. Functional Completeness 12.0. Mutual Entailment, Equivalence, and Expressive Power 12.1. Functional Completeness of the Tilde, Wedge, and Dot 13. Truth-functional Sentence· Connectives (II) 13.0. Truth-functional Sentence Connectives; a Second Look 13.1. Redundancy of the Tilde, Wedge, and Dot 13.2. Sheffer's Stroke 14. Implication and Equivalence 14.0. The Conditional 14.1. The Biconditional 14.2. Implication; Consequence Relation 14.3. Short-cut Test for Validity and Implication 14.4. More Abbreviative Conventions 14.5. Equivalence and Implication 15. Exercises 16. Normal Forms; Duality 16.0. Normal Forms 16.1. Reduction to Normal Form 16.2. Simple Disjunctive Normal Form 16.3. Duality 17. Exercises 18. Boolean Equations; Electrical Circuits 18.0. Boolean Equations 18.1. Design of Electrical Circuits 19. Exercises 20. Application of Formalized Languages to the Logical Analysis of Natural Languages 20.0. Proving Correctness of Arguments 20.1. Proving Incorrectness of Arguments 20.2. Rendering Logical Structure Explicit 20.3. Bringing Logical Form to the Surface 20.4. The Semantics of Atomic Sentences 21. Exercises 22. Functional Incompleteness 22.0. Mathematical Induction 22.1. Strong Mathematical Induction 22.2. Functional Incompleteness of the Dot and Wedge 23. Exercises 24. Alternative Notations 24.0. Trivial Alternatives 24.1. Nontrivial Alternative: Polish Notation 25. Exercises Part TWO: Axiomatization of Truth-Functional Logic 26. Axiomatic System of Truth-Functional Logic 26.1. Basic Concepts of Axiomatics 27. Exercises 28. Metatheory of System P (I) 28.0. Consistency of System P 28.1. Independence of Axioms and Rules 28.2. Independence and Consistency 29. Exercises 30. Metatheory of System P (II) 30.0. The Deduction Theorem 30.1. Some Key Theorem Schemata 30.2. Maximal Consistent Classes 30.3. Completeness Theorem 30.4. Compactness Theorem and Concluding Remarks 31. Exercises Part THREE: Sentential Modal Logic 32. Truth Tables and Modal Logic 32.0. Motivation 32.1. Actual and Possible Truth-Value Outcomes 32.2. Language Schema M 32.3. Full and Partial Truth Tables 32.4. Fundamental Truth Tables Revisited 33. Exercises 34. Validity in LSM 34.0. Value Assignments; Plenary Sets of Truth Tables 34.1. Validity 34.2. Relation of LSP to LSM 34.3. Analytic Truth, Logical Truth, Entailment, Implication, and Equivalence 35. Exercises 36. Truth-Tabular Connectives 36.1. The Singulary Truth-Tabular Connectives 36.2. N-ary Truth-Tabular Connectives: Strict Implication 36.3. Strict Equivalence; Compatibility; the Star 37. Exercises 38. Functional Completeness; Reduction of Modal WFFs 38.0. Functional Completeness 38.1. Reduction of Modal Wffs 38.2. The Six Modalities 39. Exercises 40. Axiomatic Modal Logic 40.0. Primitive Basis of the System S5 40.1. Relationship to System P; Consistency of S5 40.2. Deduction Theorem; Key Theorem Schemata 40.3. Completeness Theorem for S5 40.4. The System S5' (Completeness) 40.5. The System S5' (Consistency) 41. Exercises Part FOUR: Quantification Theory 42. Atomic Analysis 42.0. Molecular Analysis versus Atomic Analysis 42.1. Singular Terms 42.2. Predicates and Circled Numerals 42.3. Transparent versus Opaque Predicates 42.4. Individual Variables and Predicate Variables 43. Exercises 44. Semantics of Atomic WFFs 44.0. Semantics of Individual Variables 44.1. Semantics of Predicate Variables 44.2. Semantics of Atomic Wffs 45. Exercises 46. Quantifiers 46.0. Existential and Universal Quantifiers 46.1. Grammar of LSQ 46.2. Free and Bound Variables 46.3. Interpretations; Minimal Interpretations 46.4. Inductive Definition of the Value of a Wff Under a Minimal Interpretation 46.5. Applying the Inductive Definition 47. Exercises 48. Model Theory 48.0. Models: Satisfiability and Validity 48.1. Inflation Theorem 48.2. Löwenheim Theorem; Spectrum Problem 48.3. Generalized Inflation Theorem; Löwenheim-Skolem Theorem 48.4. Implication and Truth-Functional Implication; Equivalence 49. Exercises 50. Logical Analysis of English Discourse 50.0. Logical Truth and the Empty Domain 50.1. Universes of Discourse of English Statements 50.2. Translating English into Q-Languages 51. Exercises 52. Quine's System of Natural Deduction (I) 52.0. Instances 52.1. Natural Deduction Systems versus Logistic Systems 52.2. Rule of Premiss 52.3. Rule of Truth Functions 52.4. Rule of Universal Instantiation 52.5. Rule of Existential Generalization 52.6. Rule of Conditionalization 52.7. The Five Soundness-Preserving Rules 53. Exercises 54. Quine's System of Natural Deduction (II) 54.0. Conservative Instances 54.1. Rule of Universal Generalization 54.2. Rule of Existential Instantiation 54.3. Rationale Behind Universal Generalization and Existential Instantiation 54.4. Finished Deductions; Proofs; Metatheorems 54.5. Proof of the Consistency Theorem 55. Exercises 56. Applying the Natural Deduction System 56.0. Deductive Strategies 56.1. Time-Savers 56.2. Identity 56.3. Postulate Systems; Calculus of Individuals 56.4. Completeness Theorem for System QI 57. Exercises 58. Proof of the Completeness Theorem for System Q 58.0. Corollaries of the Skolem-Gödel Theorem 58.1. Maximal, Consistent, ω-Complete Classes 58.2. Proof of the Lemma of Section 58.0 59. Quantification with Function Variables 59.0. Function Variables; Terms 59.1. Natural Deduction Rules for System QIF 59.2. Peano Arithmetic 60. Exercises 61. Decision Problems and Incompleteness 61.0. Decidability; Church's Thesis 61.1. Church's Theorem 61.2. Gödel Incompleteness Theorem 62. Special Cases of the Decision Problem 62.0. Special Cases 62.1. Syllogisms 62.2. Reduction of Decision Problems; Prenex Normal Forms 63. Exercises Appendixes A. Set Theory Introduction to Set Theory B. Semantic Tableaux Semantic Tableaux for Truth-Functional Logic Semantic Tableaux for Quantificational Logic C. Alternative Proof of the Completeness of System P D. Alternative Proof of the Compactness Theorem for System P E. Alternative Proof of the Completeness of System Q F. Alternative Approaches to the Semantics of Quantifiers G. Quantification Theory with Modality Kripke's 1959 Semantics; LSQ-M System Q-M; Natural Deduction System of Quantification Theory with Modality Alternative Semantics for Quantification Theory with Modality (KA) Alternative Semantics for Quantification, Theory with Modality (KB) H. Tense Logic I. Logistic System of Quantification Theory Index ABC DE F GHIJK LM NOP QR S T UV W Written as a textbook suited to the needs and preferences of the largest possible number of those who teach symbolic logic. Treats a large variety of topics and lends itself to adoption in courses whose lengths vary from one quarter to a full academic year. Book should also be useful to those engaged in an independent study of symbolic logic.