Mathematical Logic for Computer Science

✍ Scribed by Ben-Ari, Mordechai

• Publisher: Springer
• Year: 2012
• Tongue: English
• Leaves: 351
• Edition: 3
• Category: Library

✦ Synopsis

Mathematical Logic for Computer Scienceis a mathematics textbook with theorems and proofs, but the choice of topics has been guided by the needs of students of computer science. The method of semantic tableaux provides an elegant way to teach logic that is both theoretically sound and easy to understand. The uniform use of tableaux-based techniques facilitates learning advanced logical systems based on what the student has learned from elementary systems.

The logical systems presented are: propositional logic, first-order logic, resolution and its application to logic programming, Hoare logic for the verification of sequential programs, and linear temporal logic
for the verification of concurrent programs.

The third edition has been entirely rewritten and includes new chapters on central topics of modern computer science: SAT solvers and model checking.

✦ Table of Contents

Mathematical Logic for Computer Science......Page 3
Audience......Page 6
Supplementary Materials......Page 7
Acknowledgments......Page 8
Contents......Page 9
1.1 The Origins of Mathematical Logic......Page 14
1.2 Propositional Logic......Page 15
1.3 First-Order Logic......Page 16
1.4 Modal and Temporal Logics......Page 17
1.6 Summary......Page 18
References......Page 19
2.1 Propositional Formulas......Page 20
2.1.2 Formulas as Strings......Page 21
Precedence......Page 23
Polish Notation ......Page 24
2.1.4 Structural Induction......Page 25
2.1.5 Notation......Page 26
2.1.6 A Formal Grammar for Formulas ......Page 27
2.2.1 The Definition of an Interpretation......Page 29
2.2.2 Truth Tables......Page 30
Inclusive or vs. Exclusive or......Page 32
Implication......Page 33
2.3 Logical Equivalence......Page 34
2.3.1 The Relationship Between <-> and......Page 35
2.3.2 Substitution......Page 36
Absorption of Constants......Page 37
Defining One Operator in Terms of Another......Page 38
2.4.1 Unary and Binary Boolean Operators......Page 39
2.4.2 Adequate Sets of Operators......Page 40
2.5 Satisfiability, Validity and Consequence......Page 42
2.5.1 Decision Procedures in Propositional Logic......Page 43
2.5.2 Satisfiability of a Set of Formulas......Page 44
2.5.4 Theories ......Page 45
2.6.1 Decomposing Formulas into Sets of Literals......Page 46
2.6.2 Construction of Semantic Tableaux......Page 48
2.6.3 Termination of the Tableau Construction......Page 50
2.6.4 Improving the Efficiency of the Algorithm ......Page 51
2.7 Soundness and Completeness......Page 52
2.7.1 Proof of Soundness......Page 53
2.7.2 Proof of Completeness......Page 55
2.8 Summary......Page 57
2.10 Exercises......Page 58
References......Page 60
3.1 Why Deductive Proofs?......Page 61
3.2 Gentzen System G......Page 63
3.2.1 The Relationship Between G and Semantic Tableaux......Page 65
3.3.1 Axiom Schemes and Theorem Schemes ......Page 67
3.3.2 The Deduction Rule......Page 68
3.4 Derived Rules in H......Page 70
3.5 Theorems for Other Operators......Page 74
3.6 Soundness and Completeness of H......Page 76
3.7 Consistency......Page 78
3.8 Strong Completeness and Compactness ......Page 79
3.9.1 Hilbert Systems......Page 80
3.9.2 Gentzen Systems......Page 81
3.9.4 Subformula Property......Page 82
3.11 Further Reading......Page 83
3.12 Exercises......Page 84
References......Page 85
4.1 Conjunctive Normal Form......Page 86
Trivial Clauses......Page 88
Notation......Page 89
4.3 Resolution Rule......Page 91
4.4 Soundness and Completeness of Resolution ......Page 93
Semantic Trees......Page 94
Failure Nodes......Page 96
4.5 Hard Examples for Resolution ......Page 99
4.5.1 Tseitin Encoding......Page 102
4.8 Exercises......Page 103
References......Page 104
5.1 Motivation Through Truth Tables......Page 105
5.2 Definition of Binary Decision Diagrams......Page 107
5.3 Reduced Binary Decision Diagrams......Page 108
5.4 Ordered Binary Decision Diagrams......Page 112
5.5 Applying Operators to BDDs......Page 114
5.6.1 Restriction......Page 117
5.7 Summary......Page 119
References......Page 120
6.1 Properties of Clausal Form......Page 121
6.2 Davis-Putnam Algorithm......Page 125
6.3 DPLL Algorithm......Page 126
6.4.1 Encoding the Problem in Propositional Logic......Page 127
6.4.3 Solving the Problem with the DPLL Algorithm......Page 129
6.5.1 Branching Heuristics......Page 132
6.5.2 Non-chronological Backtracking......Page 133
6.5.3 Learning Conflict Clauses......Page 134
6.6.1 Solving the 4-Queens Problem with a Stochastic Algorithm......Page 135
6.7 Complexity of SAT ......Page 136
6.10 Exercises......Page 138
References......Page 139
7.1 Relations and Predicates......Page 140
7.2.1 Syntax......Page 142
7.2.2 The Scope of Variables......Page 143
7.3 Interpretations......Page 145
7.3.1 Closed Formulas......Page 146
7.3.2 Validity and Satisfiability......Page 147
7.3.3 An Interpretation for a Set of Formulas......Page 148
7.4 Logical Equivalence......Page 149
Commutativity and Distributivity......Page 150
Quantification over Implication and Equivalence......Page 151
7.5 Semantic Tableaux......Page 152
7.5.1 Examples for Semantic Tableaux......Page 153
7.5.2 The Algorithm for Semantic Tableaux......Page 157
7.6.1 Soundness......Page 159
7.6.2 Completeness......Page 160
7.9 Exercises......Page 162
References......Page 163
8.1 Gentzen System G......Page 164
Propositional Reasoning in First-Order Logic......Page 167
The Deduction Rule......Page 168
8.3 Equivalence of H and G......Page 169
8.4 Proofs of Theorems in H......Page 170
8.5 The C-Rule ......Page 172
8.8 Exercises......Page 174
References......Page 175
9.1.1 Functions and Terms......Page 176
9.1.2 Formal Grammar ......Page 177
9.1.3 Interpretations......Page 178
9.1.4 Semantic Tableaux......Page 179
9.2.1 Skolem's Theorem......Page 181
9.2.2 Skolem's Algorithm......Page 182
9.2.3 Proof of Skolem's Theorem......Page 184
Herbrand Universes......Page 186
Herbrand Bases......Page 187
9.4 Herbrand's Theorem ......Page 189
9.7 Exercises......Page 191
References......Page 192
10.1 Ground Resolution......Page 193
10.2 Substitution......Page 195
10.3 Unification......Page 197
10.3.1 The Unification Algorithm......Page 198
10.3.2 The Occurs-Check......Page 200
10.3.3 The Correctness of the Unification Algorithm ......Page 201
10.3.4 Robinson's Unification Algorithm ......Page 202
10.4 General Resolution......Page 203
10.5.1 Proof of Soundness......Page 206
10.5.2 Proof of Completeness......Page 207
10.8 Exercises......Page 210
References......Page 211
11.1 From Formulas in Logic to Logic Programming......Page 212
Refuting a Goal Clause......Page 213
Answer Substitutions......Page 214
Refutations as Computations......Page 215
11.2.1 Horn Clauses......Page 216
11.2.2 Correct Answer Substitutions for Horn Clauses......Page 217
11.2.3 SLD-Resolution......Page 218
Completeness of SLD-Resolution......Page 219
11.3.1 Possible Outcomes when Attempting a Refutation......Page 220
11.3.2 SLD-Trees......Page 221
11.4 Prolog......Page 223
11.4.1 Depth-First Search......Page 224
Arithmetic......Page 225
Cuts......Page 226
11.5 Summary......Page 227
11.7 Exercises......Page 228
References......Page 229
12.1.1 Two-Register Machines......Page 230
12.1.2 Church's Theorem......Page 231
12.2 Decidable Cases of First-Order Logic......Page 233
12.3 Finite and Infinite Models......Page 234
12.4 Complete and Incomplete Theories......Page 235
12.6 Further Reading......Page 236
References......Page 237
13.1 Introduction......Page 238
13.2.2 Semantics......Page 240
13.2.3 Satisfiability and Validity......Page 243
13.3 Models of Time......Page 244
Discreteness......Page 245
13.3.1 Proofs of the Correspondences ......Page 246
13.4 Linear Temporal Logic......Page 247
Inductive......Page 248
Distributivity......Page 249
Collapsing......Page 250
13.5.1 The Tableau Rules for LTL......Page 251
The Rule for X-Formulas......Page 252
Future Formulas......Page 253
13.5.2 Construction of Semantic Tableaux......Page 254
13.5.3 From a Semantic Tableau to a Hintikka Structure......Page 256
13.5.4 Linear Fulfilling Hintikka Structures......Page 259
13.5.5 Deciding Fulfillment of Future Formulas ......Page 260
13.6 Binary Temporal Operators ......Page 265
Semantic Tableaux with U......Page 266
13.7 Summary......Page 267
13.9 Exercises......Page 268
References......Page 269
14.1 Deductive System L......Page 270
Distributivity......Page 271
Transitivity of......Page 273
Commutativity......Page 274
Collapsing Sequences of Operators......Page 275
14.3 Soundness and Completeness of L ......Page 276
14.5 Summary......Page 278
References......Page 279
Chapter 15: Verification of Sequential Programs......Page 280
15.1 Correctness Formulas......Page 281
15.2 Deductive System HL......Page 282
15.3 Program Verification......Page 284
15.3.1 Total Correctness ......Page 285
15.4.1 Solution 1......Page 286
15.4.2 Solution 2......Page 287
15.5.1 Weakest Preconditions......Page 290
15.5.2 Semantics of a Fragment of a Programming Language......Page 291
15.5.3 Theorems on Weakest Preconditions......Page 294
15.6 Soundness and Completeness of HL ......Page 296
15.9 Exercises......Page 300
References......Page 302
Chapter 16: Verification of Concurrent Programs......Page 303
16.1 Definition of Concurrent Programs......Page 304
Atomic Operations......Page 305
16.2 Formalization of Correctness......Page 306
Peterson's Algorithm......Page 307
Correctness Properties......Page 308
Invariants......Page 309
Mutual Exclusion......Page 310
Progress......Page 311
Liveness......Page 312
16.4 Programs as Automata......Page 313
16.4.1 Modeling Concurrent Programs as Automata......Page 314
16.4.2 The State Space......Page 315
16.5.1 Algorithms for Searching the State Space......Page 317
16.5.2 On-the-Fly Searching......Page 318
16.6 Model Checking of Liveness Properties......Page 320
16.7 Expressing an LTL Formula as an Automaton......Page 321
16.8 Model Checking Using the Synchronous Automaton......Page 323
16.9.1 The Syntax and Semantics of CTL......Page 325
16.9.2 Model Checking in CTL......Page 326
16.10 Symbolic Model Checking *......Page 328
16.11 Summary......Page 329
16.13 Exercises......Page 330
References......Page 331
A.1 Finite and Infinite Sets......Page 332
A.2 Set Operators......Page 333
A.3 Sequences......Page 335
A.4 Relations and Functions......Page 336
Functions......Page 337
A.5 Cardinality......Page 338
Induction......Page 340
References......Page 341
Index of Symbols......Page 342
Name Index......Page 344
Subject Index......Page 346

✦ Subjects

Science;Computer Science;Philosophy;Logic;Mathematics;Nonfiction