# 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**.

Acknowledgements | v |

Introduction | 1 |

The special role of logic in rational inquiry | 1 |

Why learn an artificial language? | 2 |

Consequence and proof | 4 |

Instructions about homework exercises (essential!) | 5 |

To the instructor | 10 |

Web address | 15 |

I Propositional Logic | 17 |

1 Atomic Sentences | 19 |

1.1 Individual constants | 19 |

1.2 Predicate symbols | 20 |

1.3 Atomic sentences | 23 |

1.4 General first-order languages | 28 |

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 Sentences | 41 |

2.1 Valid and sound arguments | 41 |

2.2 Methods of proof | 47 |

2.3 Formal proofs | 55 |

2.4 Constructing proofs in Fitch | 59 |

2.5 Demonstrating nonconsequence | 64 |

2.6 Alternative notation (optional) | 67 |

3 The Boolean Connectives | 68 |

3.1 Negation symbol | 69 |

3.2 Conjunction symbol | 72 |

3.3 Disjunction symbol | 75 |

3.4 Remarks about the game | 78 |

3.5 Ambiguity and parentheses | 80 |

3.6 Equivalent ways of saying things | 83 |

3.7 translation | 85 |

3.8 Alternative notation (optional) | 90 |

4 The Logic of Boolean Connectives | 94 |

4.1 Tautologies and logical truth | 95 |

4.2 Logical and tautological equivalence | 107 |

4.3 Logical and tautological consequence | 111 |

4.4 Tautological consequence in Fitch | 115 |

4.5 Pushing negation around (optional) | 118 |

4.6 Conjunctive and disjunctive normal forms (optional) | 122 |

5 Methods of Proof for Boolean Logic | 128 |

5.1 Valid inference steps | 129 |

5.2 Proof by cases | 132 |

5.3 Indirect proof: proof by contradiction | 137 |

5.4 Arguments with inconsistent premises (optional) | 141 |

6 Formal Proofs and Boolean Logic | 143 |

6.1 Conjunction rules | 144 |

6.2 Disjunction rules | 149 |

6.3 Negation rules | 155 |

6.4 The proper use of subproofs | 164 |

6.5 Strategy and tactics | 168 |

6.6 Proofs without premises (optional) | 174 |

7 Conditionals | 177 |

7.1 Material conditional symbol | 179 |

7.2 Biconditional symbol | 182 |

7.3 Conversational implicature | 188 |

7.4 truth-functional completeness (optional) | 191 |

7.5 Alternative notation (optional) | 197 |

8 The Logic of Conditionals | 199 |

8.1 Informal methods of proof | 199 |

8.2 Formal rules of proof for implication and biconditional | 207 |

8.3 Soundness and completeness (optional) | 215 |

8.4 Valid arguments: some review exercises | 223 |

II Quantifiers | 225 |

9 Introduction to Quantification | 227 |

9.1 Variables and atomic wffs | 228 |

9.2 The quantifier symbols | 230 |

9.3 Wffs and sentences | 231 |

9.4 Semantics for the quantifiers | 234 |

9.5 The four Aristotelian forms | 239 |

9.6 translating complex noun phrases | 243 |

9.7 Quantifiers and function symbols (optional) | 251 |

9.8 Alternative notation (optional) | 255 |

10 The Logic of Quantifiers | 257 |

10.1 Tautologies and quantification | 257 |

10.2 First-order validity and consequence | 266 |

10.3 First-order equivalence and DeMorgan's laws | 275 |

10.4 Other quantifier equivalences (optional) | 280 |

10.5 The axiomatic method (optional) | 283 |

11 Multiple Quantifiers | 289 |

11.1 Multiple uses of a single quantifier | 289 |

11.2 Mixed quantifiers | 293 |

11.3 The step-by-step method of translation | 298 |

11.4 Paraphrasing English | 300 |

11.5 Ambiguity and context sensitivity | 304 |

11.6 translations using function symbols (optional) | 308 |

11.7 Prenex form (optional) | 311 |

11.8 Some extra translation problems | 315 |

12 Methods of Proof for Quantifiers | 319 |

12.1 Valid quantifier steps | 319 |

12.2 The method of existential instantiation | 322 |

12.3 The method of general conditional proof | 323 |

12.4 Proofs involving mixed quantifiers | 329 |

12.5 Axiomatizing shape (optional) | 338 |

13 Formal Proofs and Quantifiers | 342 |

13.1 Universal quantifier rules | 342 |

13.2 Existential quantifier rules | 347 |

13.3 Strategy and tactics | 352 |

13.4 Soundness and completeness (optional) | 361 |

13.5 Some review exercises (optional) | 361 |

14 More about Quantification (optional) | 364 |

14.1 Numerical quantification | 366 |

14.2 Proving numerical claims | 374 |

14.3The, both, and neither | 379 |

14.4 Adding other determiners to fol | 383 |

14.5 The logic of generalized quantification | 389 |

14.6 Other expressive limitations of first-order logic | 397 |

III Applications and Metatheory | 403 |

15 First-order Set Theory | 405 |

15.1 Naive set theory | 406 |

15.2 Singletons, the empty set, subsets | 412 |

15.3 Intersection and union | 415 |

15.4 Sets of sets | 419 |

15.5 Modeling relations in set theory | 422 |

15.6 Functions | 427 |

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 Induction | 442 |

16.1 Inductive definitions and inductive proofs | 443 |

16.2 Inductive definitions in set theory | 451 |

16.3 Induction on the natural numbers | 453 |

16.4 Axiomatizing the natural numbers (optional) | 456 |

16.5 Proving programs correct (optional) | 458 |

17 Advanced Topics in Propositional Logic | 468 |

17.1 truth assignments and truth tables | 468 |

17.2 Completeness for propositional logic | 470 |

17.3 Horn sentences (optional) | 479 |

17.4 Resolution (optional) | 488 |

18 Advanced Topics in FOL | 495 |

18.1 First-order structures | 495 |

18.2 truth and satisfaction, revisited | 500 |

18.3 Soundness for fol | 509 |

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 Incompleteness | 526 |

19.1 The Completeness Theorem for fol | 527 |

19.2 Adding witnessing constants | 529 |

19.3 The Henkin theory | 531 |

19.4 The Elimination Theorem | 534 |

19.5 The Henkin Construction | 540 |

19.6 The Löwenheim-Skolem Theorem | 546 |

19.7 The Compactness Theorem | 548 |

19.8 The Gödel Incompleteness Theorem | 552 |

Summary of Formal Proof Rules | 557 |

Propositional rules | 557 |

First-order rules | 559 |

Inference Procedures (Con Rules) | 561 |

Glossary | 562 |

General Index | 573 |

Exercise Files Index | 585 |