CONTENTS
Preface................................................. ix
PART I FOUNDATIONS..................................... 1
1 Preliminaries......................................... 3
1.1 Logic Formulas...................................... 3
1.2 Semantics of Formulas............................... 7
1.3 Models and Logical Consequence...................... 10
1.4 Logical Inference................................... 13
1.5 Substitutions....................................... 14
Exercises........................................... 16
2 Definite Logic Programs............................... 19
2.1 Definite Clauses.................................... 19
2.2 Definite Programs and Goals......................... 21
2.3 The Least Herbrand Model............................ 24
2.4 Construction of Least Herbrand Models............... 29
Exercises........................................... 31
3 SLD-Resolution........................................ 33
3.1 Informal Introduction............................... 33
3.2 Unification......................................... 37
3.3 SLD-Resolution...................................... 43
3.4 Soundness of SLD-resolution......................... 48
3.5 Completeness of SLD-resolution...................... 51
3.6 Proof Trees......................................... 53
Exercises........................................... 57
4 Negation in Logic Programming......................... 59
4.1 Negative Knowledge.................................. 59
4.2 The Completed Program............................... 61
4.3 SLDNF-resolution for Definite Programs.............. 65
4.4 General Logic Programs.............................. 67
4.5 SLDNF-resolution for General Programs............... 70
4.6 Three-valued Completion............................. 75
4.7 Well-founded Semantics.............................. 77
Exercises........................................... 84
5 Towards Prolog: Cut and Arithmetic.................... 87
5.1 Cut: Pruning the SLD-tree........................... 87
5.2 Built-in Arithmetic................................. 93
Exercises........................................... 97
PART II PROGRAMMING IN LOGIC............................ 99
6 Logic and Databases...................................101
6.1 Relational Databases................................101
6.2 Deductive Databases.................................103
6.3 Relational Algebra vs. Logic Programs...............104
6.4 Logic as a Query-language...........................107
6.5 Special Relations...................................109
6.6 Databases with Compound Terms.......................114
Exercises...........................................116
7 Programming with Recursive Data Structures............119
7.1 Recursive Data Structures...........................119
7.2 Lists...............................................119
7.3 Difference Lists....................................129
Exercises...........................................131
8 Amalgamating Object- and Meta-language................135
8.1 What is a Meta-language?............................135
8.2 Ground Representation...............................136
8.3 Nonground Representation............................141
8.4 The Built-in Predicate clause/2.....................143
8.5 The Built-in Predicates assert{a,z}/1...............144
8.6 The Built-in Predicate retract/1....................146
Exercises...........................................146
9 Logic and Expert Systems..............................149
9.1 Expert Systems......................................149
9.2 Collecting Proofs...................................153
9.3 Query-the-user......................................154
9.4 Fixing the Car (Extended Example)...................155
Exercises...........................................161
10 Logic and Grammars...................................163
10.1 Context-free Grammars..............................163
10.2 Logic Grammars.....................................166
10.3 Context-dependent Languages........................169
10.4 Definite Clause Grammars (DCGs)....................171
10.5 Compilation of DCGs into Prolog....................175
Exercises..........................................176
11 Searching in a State-space...........................179
11.1 State-spaces and State-transitions.................179
11.2 Loop Detection.....................................181
11.3 Water-jug Problem (Extended Example)...............182
11.4 Blocks World (Extended Example)....................183
11.5 Alternative Search Strategies......................185
Exercises..........................................186
PART III ALTERNATIVE LOGIC PROGRAMMING SCHEMES..........189
12 Logic Programming and Concurrency....................191
12.1 Algorithm = Logic + Control........................191
12.2 And-parallelism....................................193
12.3 Producers and Consumers............................194
12.4 Don't Care Nondeterminism..........................196
12.5 Concurrent Logic Programming.......................196
Exercises..........................................202
13 Logic Programs with Equality.........................203
13.1 Equations and $E$-unification......................204
13.2 More on $E$-unification............................205
13.3 Logic Programs with Equality.......................207
Exercises..........................................212
14 Constraint Logic Programming.........................213
14.1 Logic Programming with Constraints.................214
14.2 Declarative Semantics of CLP.......................215
14.3 Operational Semantics of CLP.......................216
14.4 Examples of CLP-languages..........................222
Exercises..........................................227
15 Query-answering in Deductive Databases...............229
15.1 Naive Evaluation...................................230
15.2 Semi-naive Evaluation..............................232
15.3 Magic Transformation...............................233
15.4 Optimizations......................................236
Exercises..........................................239
A Bibliographical Notes.................................241
A.1 Foundations.........................................241
A.2 Programming in Logic................................244
A.3 Alternative Logic Programming Schemes...............247
B Basic Set Theory......................................251
B.1 Sets................................................251
B.2 Relations...........................................252
B.3 Functions...........................................252
C Answers to Selected Exercises.........................253
Bibliography............................................263
Index...................................................277