Table of Contents

Foreword ix
Preface xi
Acknowledgements xvi

I Logic and Logic Programming 1

1. A brief introduction to clausal logic 3

1.1 Answering queries 5
1.2 Recursion 7
1.3 Structured terms 11
1.4 What else is there to know about clausal logic? 15

2. Clausal logic and resolution: theoretical backgrounds 17

2.1 Propositional clausal logic 18
2.2 Relational clausal logic 25
2.3 Full clausal logic 30
2.4 Definite clause logic 35
2.5 The relation between clausal logic and Predicate Logic 38
Further reading 41

3. Logic Programming and Prolog 43

3.1 SLD-resolution 44
3.2 Pruning the search by means of cut 47
3.3 Negation as failure 52
3.4 Other uses of cut 58
3.5 Arithmetic expressions 60
3.6 Accumulators 63
3.7 Second-order predicates 66
3.8 Meta-programs 68
3.9 A methodology of Prolog programming 74
Further reading 77

II Reasoning with structured knowledge 79

4. Representing structured knowledge 83

4.1 Trees as terms 84
4.2 Graphs generated by a predicate 88
4.3 Inheritance hierarchies 90
Further reading 97

5. Searching graphs 99

5.1 A general search procedure 99
5.2 Depth-first search 103
5.3 Breadth-first search 106
5.4 Forward chaining 110
Further reading 115

6. Informed search 117

6.1 Best-first search 117
6.2 Optimal best-first search 124
6.3 Non-exhaustive informed search 127
Further reading 128

III Advanced reasoning techniques 129

7. Reasoning with natural language 131

7.1 Grammars and parsing 132
7.2 Definite Clause Grammars 134
7.3 Interpretation of natural language 139
Further reading 145

8. Reasoning with incomplete information 147

8.1 Default reasoning 148
8.2 The semantics of incomplete information 154
8.3 Abduction and diagnostic reasoning 159
8.4 The complete picture 166
Further reading 169

9. Inductive reasoning 171

9.1 Generalisation and specialisation 173
9.2 Bottom-up induction 178
9.3 Top-down induction 184
Further reading 191

Appendices 193

A. A catalogue of useful predicates 195

A.1 Built-in predicates 195
A.2 A library of utility predicates 197

B. Two programs for logical conversion 201

B.1 From Predicate Logic to clausal logic 201
B.2 Predicate Completion 206

C. Answers to selected exercises 211

C.1 A brief introduction to clausal logic 211
C.2 Clausal logic and resolution: theoretical backgrounds 213
C.3 Logic Programming and Prolog 218
C.4 Representing structured knowledge 226
C.5 Searching graphs 226
C.6 Informed search 227
C.7 Reasoning with natural language 228
C.8 Reasoning with incomplete information 230
C.9 Inductive reasoning 231

Index 232

Back