Need help?  •  Forgot your password?
This web site will be decommissioned in June 2019. Visit our new site here.

Language, Proof and Logic

Table of Contents (First 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 a completely rewritten and much improved version of The Language of First-order Logic. Introductory material is presented in a more systematic and accessible fashion. 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 first edition. You can also look at the the table of contents for the second edition.


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 instructor10
Web address15

I Propositional Logic17
1 Atomic Sentences19
1.1 Individual constants19
1.2 Predicate symbols20
1.3 Atomic sentences23
1.4 General first-order languages28
1.5 Function symbols (optional)31
1.6 The first-order language of set theory (optional)37
1.7 The first-order language of arithmetic (optional)38
1.8 Alternative notation (optional)40
2 The Logic of Atomic Sentences41
2.1 Valid and sound arguments41
2.2 Methods of proof47
2.3 Formal proofs55
2.4 Constructing proofs in Fitch59
2.5 Demonstrating nonconsequence64
2.6 Alternative notation (optional)67
3 The Boolean Connectives68
3.1 Negation symbol69
3.2 Conjunction symbol72
3.3 Disjunction symbol75
3.4 Remarks about the game78
3.5 Ambiguity and parentheses80
3.6 Equivalent ways of saying things83
3.7 translation85
3.8 Alternative notation (optional)90
4 The Logic of Boolean Connectives94
4.1 Tautologies and logical truth95
4.2 Logical and tautological equivalence107
4.3 Logical and tautological consequence111
4.4 Tautological consequence in Fitch115
4.5 Pushing negation around (optional)118
4.6 Conjunctive and disjunctive normal forms (optional)122
5 Methods of Proof for Boolean Logic128
5.1 Valid inference steps129
5.2 Proof by cases132
5.3 Indirect proof: proof by contradiction137
5.4 Arguments with inconsistent premises (optional)141
6 Formal Proofs and Boolean Logic143
6.1 Conjunction rules144
6.2 Disjunction rules149
6.3 Negation rules155
6.4 The proper use of subproofs164
6.5 Strategy and tactics168
6.6 Proofs without premises (optional)174
7 Conditionals177
7.1 Material conditional symbol179
7.2 Biconditional symbol182
7.3 Conversational implicature188
7.4 truth-functional completeness (optional)191
7.5 Alternative notation (optional)197
8 The Logic of Conditionals199
8.1 Informal methods of proof199
8.2 Formal rules of proof for implication and biconditional207
8.3 Soundness and completeness (optional)215
8.4 Valid arguments: some review exercises223

II Quantifiers225
9 Introduction to Quantification227
9.1 Variables and atomic wffs228
9.2 The quantifier symbols230
9.3 Wffs and sentences231
9.4 Semantics for the quantifiers234
9.5 The four Aristotelian forms239
9.6 translating complex noun phrases243
9.7 Quantifiers and function symbols (optional)251
9.8 Alternative notation (optional)255
10 The Logic of Quantifiers257
10.1 Tautologies and quantification257
10.2 First-order validity and consequence266
10.3 First-order equivalence and DeMorgan's laws275
10.4 Other quantifier equivalences (optional)280
10.5 The axiomatic method (optional)283
11 Multiple Quantifiers289
11.1 Multiple uses of a single quantifier289
11.2 Mixed quantifiers293
11.3 The step-by-step method of translation298
11.4 Paraphrasing English300
11.5 Ambiguity and context sensitivity304
11.6 translations using function symbols (optional)308
11.7 Prenex form (optional)311
11.8 Some extra translation problems315
12 Methods of Proof for Quantifiers319
12.1 Valid quantifier steps319
12.2 The method of existential instantiation322
12.3 The method of general conditional proof323
12.4 Proofs involving mixed quantifiers329
12.5 Axiomatizing shape (optional)338
13 Formal Proofs and Quantifiers342
13.1 Universal quantifier rules342
13.2 Existential quantifier rules347
13.3 Strategy and tactics352
13.4 Soundness and completeness (optional)361
13.5 Some review exercises (optional)361
14 More about Quantification (optional)364
14.1 Numerical quantification366
14.2 Proving numerical claims374
14.3The, both, and neither379
14.4 Adding other determiners to fol383
14.5 The logic of generalized quantification389
14.6 Other expressive limitations of first-order logic397

III Applications and Metatheory403
15 First-order Set Theory405
15.1 Naive set theory406
15.2 Singletons, the empty set, subsets412
15.3 Intersection and union415
15.4 Sets of sets419
15.5 Modeling relations in set theory422
15.6 Functions427
15.7 The powerset of a set (optional)429
15.8 Russell's Paradox (optional)432
15.9 Zermelo Frankel set theory zfc (optional)433
16 Mathematical Induction442
16.1 Inductive definitions and inductive proofs443
16.2 Inductive definitions in set theory451
16.3 Induction on the natural numbers453
16.4 Axiomatizing the natural numbers (optional)456
16.5 Proving programs correct (optional)458
17 Advanced Topics in Propositional Logic468
17.1 truth assignments and truth tables468
17.2 Completeness for propositional logic470
17.3 Horn sentences (optional)479
17.4 Resolution (optional)488
18 Advanced Topics in FOL495
18.1 First-order structures495
18.2 truth and satisfaction, revisited500
18.3 Soundness for fol509
18.4 The completeness of the shape axioms (optional)512
18.5 Skolemization (optional)514
18.6 Unification of terms (optional)516
18.7 Resolution, revisited (optional)519
19 Completeness and Incompleteness526
19.1 The Completeness Theorem for fol527
19.2 Adding witnessing constants529
19.3 The Henkin theory531
19.4 The Elimination Theorem534
19.5 The Henkin Construction540
19.6 The Löwenheim-Skolem Theorem546
19.7 The Compactness Theorem548
19.8 The Gödel Incompleteness Theorem552

Summary of Formal Proof Rules557
Propositional rules557
First-order rules559
Inference Procedures (Con Rules)561
Glossary562
General Index573
Exercise Files Index585