Logic as a Tool (eBook)

Valentin Goranko is an associate professor at the Department of Applied Mathematics and Computer Science of the Technical University of Denmark. He has had over 25 years of University teaching and research experience: in particular, he has taught several courses partly based on the proposed book.

1 Understanding Propositional Logic 9

1.1 Propositions and logical connectives. Truth-tables and tautologies. 9

1.2 Propositional logical consequence. Logically correct inferences 28

1.3 Logical equivalence. Negation normal form of propositional formulae. 39

1.4 Addendum: Inductive definitions. Structural induction and recursion 46

2 Deductive Reasoning in Propositional Logic 59

2.1 Deductive systems: an overview 59

2.2 Axiomatic systems for propositional logic 65

2.3 Semantic tableaux 72

2.4 Natural deduction 83

2.5 Normal forms. Propositional resolution. 92

2.6 Addendum: The Boolean satisfiability problem and NP-completeness. 101

2.7 Addendum: Completeness of the propositional deductive systems 104

3 Understanding First-order Logic 113

3.1 First-order structures and languages. Terms and formulae of first-order logic. 114

3.2 Semantics of first-order logic 127

3.3 Basic grammar and use of first-order languages 143

3.4 Logical validity, consequence and equivalence in first-order logic 156

3.5 Syllogisms 173

4 Deductive Reasoning in First-order Logic 181

4.1 Axiomatic system for first-order logic 182

4.2 Semantic Tableaux for First-order Logic 190

4.3 Natural Deduction for first-order logic 204

4.4 Prenex and clausal normal forms 211

4.5 Resolution for first-order logic 218

4.6 Addendum: Soundness and completeness of the deductive systems for first-order logic 234

5 Applications: Mathematical Proofs and Automated Reasoning 245

5.1 Logical reasoning and mathematical proofs 246

5.2 Logical reasoning on sets, functions and relations 255

5.3 Mathematical induction and Peano Arithmetic 271

5.4 Applications: automated reasoning and logic programming 278

6 Answers and solutions to selected exercises 289

6.1 Answers and solutions: Section 1.1 289

6.2 Answers and solutions: Section 1.2 292

6.3 Answers and solutions: Section 1.3 294

6.4 Answers and solutions: Section 2.2 296

6.5 Answers and solutions: Section 2.3 298

6.6 Answers and solutions: Section 2.4 307

6.7 Answers and solutions: Section 2.5 312

6.8 Answers and solutions: Section 3.1 318

6.9 Answers and solutions: Section 3.2 321

6.10 Answers and solutions: Section 3.3 323

6.11 Answers and solutions: Section 3.4 325

6.12 Answers and solutions: Section 3.5 330

6.13 Answers and solutions: Section 4.1 331

6.14 Answers and solutions: Section 4.2 333

6.15 Answers and solutions: Section 4.3 350

6.16 Answers and solutions: Section 4.4 352

6.17 Answers and solutions: Section 4.5 354

6.18 Answers and solutions: Section 5.1 363

6.19 Answers and solutions: Section 5.2 364

6.20 Answers and solutions: Section 5.3 368

6.21 Answers and solutions: Section 5.4 371

"Classical logic is hard but rewarding--helping with clarity in programming, business decisions, and whatever life throws at you...." (MagPi, Jan 17)