Language, Proof and Logic
Table of Contents (Second Edition)
Language, Proof, and Logic is a textbook and software package, intended for use in undergraduate level logic courses. The text covers topics such as the boolean connectives, formal proof techniques, quantifiers, basic set theory, and induction. The last few chapters include material on soundness, completeness, and Godel's incompleteness theorems.
The book is appropriate for a wide range of courses, from first logic courses for undergraduates (philosophy, mathematics, and computer science) to a first graduate logic course.
This is the table of contents for the second edition. You can also look at the the table of contents for the first edition.
We have also prepared an errata for the second edition.
Table of contents
- Acknowledgementsv
- Introduction1
- The special role of logic in rational inquiry1
- Why learn an artificial language?2
- Consequence and proof4
- Instructions about homework exercises (essential!)5
- To the instructor11
- Web address16
- IPropositional Logic17
- 1Atomic Sentences19
- 1.1Individual constants19
- 1.2Predicate symbols20
- 1.3Atomic sentences23
- 1.4General first-order languages28
- 1.5Function symbols (optional)31
- 1.6The first-order language of set theory (optional)37
- 1.7The first-order language of arithmetic (optional)38
- 1.8Alternative notation (optional)40
- 2The Logic of Atomic Sentences41
- 2.1Valid and sound arguments41
- 2.2Methods of proof46
- 2.3Formal proofs54
- 2.4Constructing proofs in Fitch 58
- 2.5Demonstrating nonconsequence63
- 2.6Alternative notation (optional)66
- 3The Boolean Connectives67
- 3.1Negation symbol: ¬68
- 3.2Conjunction symbol: ∧71
- 3.3Disjunction symbol: ∨74
- 3.4Remarks about the game77
- 3.5Ambiguity and parentheses79
- 3.6Equivalent ways of saying things82
- 3.7Translation84
- 3.8Alternative notation (optional)90
- 4The Logic of Boolean Connectives93
- 4.1Tautologies and logical truth94
- 4.2Logical and tautological equivalence106
- 4.3Logical and tautological consequence110
- 4.4Tautological consequence in Fitch 114
- 4.5Pushing negation around (optional)118
- 4.6Conjunctive and disjunctive normal forms (optional)122
- 5Methods of Proof for Boolean Logic128
- 5.1Valid inference steps129
- 5.2Proof by cases132
- 5.3Indirect proof: proof by contradiction137
- 5.4Arguments with inconsistent premises (optional)141
- 6Formal Proofs and Boolean Logic143
- 6.1Conjunction rules144
- 6.2Disjunction rules149
- 6.3Negation rules156
- 6.4The proper use of subproofs165
- 6.5Strategy and tactics168
- 6.6Proofs without premises (optional)175
- 7Conditionals178
- 7.1Material conditional symbol: →180
- 7.2Biconditional symbol: ↔183
- 7.3Conversational implicature189
- 7.4Truth-functional completeness (optional)192
- 7.5Alternative notation (optional)198
- 8The Logic of Conditionals199
- 8.1Informal methods of proof199
- 8.2Formal rules of proof for → and ↔207
- 8.3Soundness and completeness (optional)215
- 8.4Valid arguments: some review exercises223
- 1Atomic Sentences19
- IIQuantifiers227
- 9Introduction to Quantification229
- 9.1Variables and atomic wffs230
- 9.2The quantifier symbols: ∀, ∃232
- 9.3Wffs and sentences233
- 9.4Semantics for the quantifiers237
- 9.5The four Aristotelian forms241
- 9.6Translating complex noun phrases245
- 9.7Quantifiers and function symbols (optional)253
- 9.8Alternative notation (optional)257
- 10The Logic of Quantifiers259
- 10.1Tautologies and quantification259
- 10.2First-order validity and consequence267
- 10.3First-order equivalence and DeMorgan's laws277
- 10.4Other quantifier equivalences (optional)282
- 10.5The axiomatic method (optional)286
- 10.6Lemmas291
- 11Multiple Quantifiers298
- 11.1Multiple uses of a single quantifier298
- 11.2Mixed quantifiers302
- 11.3The step-by-step method of translation307
- 11.4Paraphrasing English{paraphrasing English 309
- 11.5Ambiguity and context sensitivity313
- 11.6Translations using function symbols (optional)317
- 11.7Prenex form (optional)320
- 11.8Some extra translation problems324
- 12Methods of Proof for Quantifiers328
- 12.1Valid quantifier steps328
- 12.2The method of existential instantiation331
- 12.3The method of general conditional proof332
- 12.4Proofs involving mixed quantifiers338
- 12.5Axiomatizing shape (optional)347
- 13Formal Proofs and Quantifiers351
- 13.1Universal quantifier rules351
- 13.2Existential quantifier rules356
- 13.3Strategy and tactics361
- 13.4Soundness and completeness (optional)370
- 13.5Some review exercises (optional)370
- 14More about Quantification (optional)373
- 14.1Numerical quantification375
- 14.2Proving numerical claims383
- 14.3The, both, and neither388
- 14.4Adding other determiners to FOL392
- 14.5The logic of generalized quantification398
- 14.6Other expressive limitations of first-order logic406
- 9Introduction to Quantification229
- IIIApplications and Metatheory411
- 15First-order Set Theory413
- 15.1Naive set theory414
- 15.2The empty set, singletons and pairs419
- 15.3Subsets422
- 15.4Intersection and union424
- 15.5Ordered Pairs429
- 15.6Modeling relations in set theory431
- 15.7Functions436
- 15.8The powerset of a set (optional)439
- 15.9Russell's Paradox (optional)442
- 15.10Zermelo Frankel set theory (ZFC) (optional)444
- 16Mathematical Induction454
- 16.1Inductive definitions and inductive proofs455
- 16.2Inductive definitions in set theory463
- 16.3Induction on the natural numbers465
- 16.4Axiomatizing the natural numbers (optional)468
- 16.5Induction in Fitch 473
- 16.6Ordering the Natural Numbers (optional)475
- 16.7Strong Induction (optional)478
- 17Advanced Topics in Propositional Logic484
- 17.1Truth assignments and truth tables484
- 17.2Completeness for propositional logic486
- 17.3Horn sentences (optional)495
- 17.4Resolution (optional)504
- 18Advanced Topics in FOL511
- 18.1First-order structures511
- 18.2Truth and satisfaction, revisited516
- 18.3Soundness for FOL525
- 18.4The completeness of the shape axioms (optional)528
- 18.5Skolemization (optional)530
- 18.6Unification of terms (optional)532
- 18.7Resolution, revisited (optional)535
- 19Completeness and Incompleteness542
- 19.1The Completeness Theorem for FOL543
- 19.2Adding witnessing constants545
- 19.3The Henkin theory547
- 19.4The Elimination Theorem550
- 19.5The Henkin Construction556
- 19.6The Löwenheim-Skolem Theorem562
- 19.7The Compactness Theorem564
- 19.8The Gödel Incompleteness Theorem568
- Summary of Formal Proof Rules573
- Propositional rules573
- First-order rules575
- Induction rules577
- Inference Procedures (Con Rules)577
- Glossary579
- File Index590
- Exercise Index593
- General Index595
- 15First-order Set Theory413