Logic Programming and Prolog (2ed) - U.Nilsson J.Maluszynski.pdf

(1955 KB) Pobierz
bok.dvi
LOGIC, PROGRAMMING AND
PROLOG (2ED)
Ulf Nilsson and Jan Maluszynski
2000, Ulf Nilsson and Jan Maluszynski. The book may be downloaded
and printed for personal use only provided that the text (1) is not altered in any way,
and (2) is accompanied by this copyright notice. The book may also be copied and
distributed in paper-form for non-prot use only. No other form of distribution or
storage is permitted. In particular, it is not allowed to store and distribute the book
electronically.
This book was previously published by John Wiley & Sons Ltd. The book was origi-
nally published in 1990 with the second edition published in 1995. The copyright was
reverted back to the authors in November 2000.
For further information about updates and supplementary material please check out
thebookweb-siteat
http://www.ida.liu.se/~ulfni/lpp
or contact the authors at ulfni@ida.liu.se and janma@ida.liu.se .
Copyright c
Contents
Preface
ix
I Foundations
1
1 Preliminaries 3
1.1 LogicFormulas ............................... 3
1.2 SemanticsofFormulas ........................... 7
1.3 ModelsandLogicalConsequence ..................... 10
1.4 LogicalInference .............................. 13
1.5 Substitutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Exercises .................................. 16
2 Denite Logic Programs 19
2.1 DeniteClauses............................... 19
2.2 Denite Programs and Goals . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 TheLeastHerbrandModel ........................ 24
2.4 ConstructionofLeastHerbrandModels ................. 29
Exercises .................................. 31
3 SLD-Resolution 33
3.1 InformalIntroduction ........................... 33
3.2 Unication ................................. 37
3.3 SLD-Resolution............................... 43
3.4 Soundness of SLD-resolution . . . . . . . . . . . . . . . . . . . . . . . 48
3.5 CompletenessofSLD-resolution...................... 51
3.6 ProofTrees ................................. 53
Exercises .................................. 57
v
vi
Contents
4 Negation in Logic Programming 59
4.1 NegativeKnowledge ............................ 59
4.2 The Completed Program . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.3 SLDNF-resolution for Denite Programs . . . . . . . . . . . . . . . . . 65
4.4 General Logic Programs . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.5 SLDNF-resolution for General Programs . . . . . . . . . . . . . . . . . 70
4.6 Three-valuedCompletion ......................... 75
4.7 Well-founded Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Exercises .................................. 84
5 Towards Prolog: Cut and Arithmetic 87
5.1 Cut:PruningtheSLD-tree ........................ 87
5.2 Built-inArithmetic............................. 93
Exercises .................................. 97
II Programming in Logic
99
6 Logic and Databases 101
6.1 RelationalDatabases............................ 101
6.2 DeductiveDatabases............................ 103
6.3 Relational Algebra vs. Logic Programs . . . . . . . . . . . . . . . . . . 104
6.4 LogicasaQuery-language......................... 107
6.5 SpecialRelations .............................. 109
6.6 DatabaseswithCompoundTerms .................... 114
Exercises .................................. 116
7 Programming with Recursive Data Structures 119
7.1 RecursiveDataStructures......................... 119
7.2 Lists..................................... 119
7.3 DierenceLists............................... 129
Exercises .................................. 131
8 Amalgamating Object- and Meta-language 135
8.1 WhatisaMeta-language?......................... 135
8.2 GroundRepresentation .......................... 136
8.3 NongroundRepresentation......................... 141
8.4 The Built-in Predicate clause /2...................... 143
8.5 The Built-in Predicates assert
/1................... 144
8.6 The Built-in Predicate retract /1...................... 146
Exercises .................................. 146
f
a,z
g
9 Logic and Expert Systems 149
9.1 ExpertSystems............................... 149
9.2 CollectingProofs.............................. 153
9.3 Query-the-user ............................... 154
9.4 FixingtheCar(ExtendedExample) ................... 155
Exercises .................................. 161
68360166.001.png
Contents
vii
10 Logic and Grammars 163
10.1Context-freeGrammars .......................... 163
10.2LogicGrammars .............................. 166
10.3Context-dependentLanguages....................... 169
10.4DeniteClauseGrammars(DCGs).................... 171
10.5CompilationofDCGsintoProlog..................... 175
Exercises .................................. 176
11 Searching in a State-space 179
11.1State-spacesandState-transitions..................... 179
11.2LoopDetection............................... 181
11.3Water-jugProblem(ExtendedExample)................. 182
11.4BlocksWorld(ExtendedExample) .................... 183
11.5AlternativeSearchStrategies ....................... 185
Exercises .................................. 186
III Alternative Logic Programming Schemes
189
12 Logic Programming and Concurrency 191
12.1 Algorithm = Logic + Control . . . . . . . . . . . . . . . . . . . . . . . 191
12.2And-parallelism............................... 193
12.3ProducersandConsumers......................... 194
12.4Don'tCareNondeterminism........................ 196
12.5 Concurrent Logic Programming . . . . . . . . . . . . . . . . . . . . . . 196
Exercises .................................. 202
13 Logic Programs with Equality 203
13.1 Equations and E -unication........................ 204
13.2 More on E -unication ........................... 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.4ExamplesofCLP-languages........................ 222
Exercises .................................. 227
15 Query-answering in Deductive Databases 229
15.1NaiveEvaluation.............................. 230
15.2Semi-naiveEvaluation ........................... 232
15.3MagicTransformation ........................... 233
15.4Optimizations................................ 236
Exercises .................................. 239
68360166.002.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin