Language, proof, and logic

Title page......Page 1
Acknowledgements......Page 3
Contents......Page 5
The special role of logic in rational inquiry......Page 11
Why learn an artificial language?......Page 12
Consequence and proof......Page 14
Essential instructions about homework exercises......Page 15
To the instructor......Page 20
Web address......Page 25
1.1 Individual constants......Page 29
1.2 Predicate symbols......Page 30
1.3 Atomic sentences......Page 33
1.4 General first-order languages......Page 38
1.5 Function symbols......Page 41
1.6 The FO language of set theory......Page 47
1.7 The FO language of arithmetic......Page 48
1.8 Alternative notation......Page 50
2.1 Valid and sound arguments......Page 51
2.2 Methods of proof......Page 56
2.3 Formal proofs......Page 64
2.4 Constructing proofs in Fitch......Page 68
2.5 Demonstrating nonconsequence......Page 73
2.6 Alternative notation......Page 76
3 The Boolean Connectives......Page 77
3.1 Negation symbol......Page 78
3.2 Conjunction symbol......Page 81
3.3 Disjunction symbol......Page 84
3.4 Remarks about the game......Page 87
3.5 Ambiguity and parentheses......Page 89
3.6 Equivalent ways of saying things......Page 92
3.7 Translation......Page 94
3.8 Alternative notation......Page 99
4 The Logic of Boolean Connectives......Page 103
4.1 Tautologies and logical truth......Page 104
4.2 Logical and tautological equivalence......Page 116
4.3 Logical and tautological consequence......Page 120
4.4 Tautological consequence in Fitch......Page 124
4.5 Pushing negation around......Page 127
4.6 Conjunctive and disjunctive normal forms......Page 131
5 Methods of Proof for Boolean Logic......Page 137
5.1 Valid inference steps......Page 138
5.2 Proof by cases......Page 141
5.3 Indirect proof: proof by contradiction......Page 146
5.4 Arguments with inconsistent premises......Page 150
6 Formal Proofs and Boolean Logic......Page 152
6.1 Conjunction rules......Page 153
6.2 Disjunction rules......Page 158
6.3 Negation rules......Page 164
6.4 The proper use of subproofs......Page 173
6.5 Strategy and tactics......Page 177
6.6 Proofs without premises......Page 183
7 Conditionals......Page 186
7.1 Material conditional symbol......Page 188
7.2 Biconditional symbol......Page 191
7.3 Conversational implicature......Page 197
7.4 Truth-functional completeness......Page 200
7.5 Alternative notation......Page 206
8.1 Informal methods of proof......Page 208
8.2 Formal rules of proof for conditional and biconditional......Page 216
8.3 Soundness and completeness......Page 224
8.4 Valid arguments: some review exercises......Page 232
9 Introduction to Quantification......Page 237
9.1 Variables and atomic wffs......Page 238
9.2 The quantifier symbols......Page 240
9.3 Wffs and sentences......Page 241
9.4 Semantics for the quantifiers......Page 244
9.5 The four Aristotelian forms......Page 249
9.6 Translating complex noun phrases......Page 253
9.7 Quantifiers and function symbols......Page 261
9.8 Alternative notation......Page 265
10.1 Tautologies and quantification......Page 267
10.2 First-order validity and consequence......Page 276
10.3 First-order equivalence and DeMorgan\'s laws......Page 285
10.4 Other quantifier equivalences......Page 290
10.5 The axiomatic method......Page 293
11.1 Multiple uses of a single quantifier......Page 299
11.2 Mixed quantifiers......Page 303
11.3 The step-by-step method of translation......Page 308
11.4 Paraphrasing English......Page 310
11.5 Ambiguity and context sensitivity......Page 314
11.6 Translations using function symbols......Page 318
11.7 Prenex form......Page 321
11.8 Some extra translation problems......Page 325
12.1 Valid quantifier steps......Page 329
12.2 The method of existential instantiation......Page 332
12.3 The method of general conditional proof......Page 333
12.4 Proofs involving mixed quantifiers......Page 339
12.5 Axiomatizing shape......Page 348
13.1 Universal quantifier rules......Page 352
13.2 Existential quantifier rules......Page 357
13.3 Strategy and tactics......Page 362
13.5 Some review exercises......Page 371
14 More about Quantification......Page 374
14.1 Numerical quantification......Page 376
14.2 Proving numerical claims......Page 384
14.3 The, both, and neither......Page 389
14.4 Adding other determiners to FOL......Page 393
14.5 The logic of generalized quantification......Page 399
14.6 Other expressive limitationsof first-order logic......Page 407
15 First-order Set Theory......Page 415
15.1 Naive set theory......Page 416
15.2 Singletons, the empty set, subsets......Page 422
15.3 Intersection and union......Page 425
15.4 Sets of sets......Page 429
15.5 Modeling relations in set theory......Page 432
15.6 Functions......Page 437
15.7 The powerset of a set......Page 439
15.8 Russell\'s Paradox......Page 442
15.9 Zermelo Frankel set theory (ZFC)......Page 443
16 Mathematical Induction......Page 452
16.1 Inductive definitions and inductive proofs......Page 453
16.2 Inductive definitions in set theory......Page 461
16.3 Induction on the natural numbers......Page 463
16.4 Axiomatizing the natural numbers......Page 466
16.5 Proving programs correct......Page 468
17.1 Truth assignments and truth tables......Page 478
17.2 Compleness for propositional logic......Page 480
17.3 Horn sentences......Page 489
17.4 Resolution......Page 498
18.1 First-order structures......Page 505
18.2 Truth and satisfaction, revisited......Page 510
18.3 Soundness for FOL......Page 519
18.4 The completeness of the shape axioms......Page 522
18.5 Skolemization......Page 524
18.6 Unification of terms......Page 526
18.7 Resolution, revisited......Page 529
19 Completeness and Incompleteness......Page 536
19.1 The Completeness Theorem for FOL......Page 537
19.2 Adding witnessing constants......Page 539
19.3 The Henkin theory......Page 541
19.4 The Elimination Theorem......Page 544
19.5 The Henkin Construction......Page 550
19.6 The Lowenheim-Skolem Theorem......Page 556
19.7 The Compactness Theorem......Page 558
19.8 The Godel Incompleteness Theorem......Page 562
Propositional rules......Page 567
First-order rules......Page 569
Inference Procedures (Con Rules)......Page 571
Glossary......Page 572
General Index......Page 583
Exercise Files Index......Page 595