Logic, Programming and Prolog (2nd Edition) - Ulf Nilsson and Jan Małuszyński.pdf

(1856 KB) Pobierz
bok.dvi
LOGIC,PROGRAMMINGAND
PROLOG(2ED)
UlfNilssonandJanMaÃluszy¶nski
Copyrightc ° 2000,UlfNilssonandJanMaÃluszy¶nski.Thebookmaybedown-
loadedandprintedforpersonaluseonlyprovidedthatthetext(1)isnotaltered
inanyway,and(2)isaccompaniedbythiscopyrightnotice.Thebookmayalso
becopiedanddistributedinpaper-formfornon-pro¯tuseonly.Nootherform
ofdistributionisallowed.Itisnotallowedtodistributethebookelectronically.
ThisbookwaspreviouslypublishedbyJohnWiley&SonsLtd.Thebookwas
originallypublishedin1990withthesecondeditionin1995.Thecopyrightwas
revertedbacktotheauthorsinNovember2000.
Forfurtherinformationaboutupdatesandsupplementarymaterialpleasecheck
outthebookweb-siteat
http://www.ida.liu.se/~ulfni/lpp
orcontacttheauthorsat ulfni@ida.liu.se and janma@ida.liu.se .
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
383890237.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
383890237.002.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin