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