Knowledge Representation and Reasoning

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

ISBN: 9781558609327 | 1558609326
Cover: Hardcover
Copyright: 5/19/2004

Buy Used

Usually Ships in 3-5 Business Days

$73.42
Buy New

Print on Demand: 2-4 Weeks. This item cannot be cancelled or returned.

$101.47
eBook

Available Instantly

Online: 180 Days

Downloadable: 180 Days

$49.59

Knowledge representation is at the very core of a radical idea for understanding intelligence. Instead of trying to understand or build brains from the bottom up, its goal is to understand and build intelligent behavior from the top down, putting the focus on what an agent needs to know in order to behave intelligently, how this knowledge can be represented symbolically, and how automated reasoning procedures can make this knowledge available as needed. This landmark text takes the central concepts of knowledge representation developed over the last 50 years and illustrates them in a lucid and compelling way. Each of the various styles of representation is presented in a simple and intuitive form, and the basics of reasoning with that representation are explained in detail. This approach gives readers a solid foundation for understanding the more advanced work found in the research literature. The presentation is clear enough to be accessible to a broad audience, including researchers and practitioners in database management, information retrieval, and object-oriented systems as well as artificial intelligence. This book provides the foundation in knowledge representation and reasoning that every AI practitioner needs.

Preface

xvii

Acknowledgments

xxvii

1 Introduction

(186)

1.1 The Key Concepts: Knowledge, Representation, and Reasoning

(3)

1.2 Why Knowledge Representation and Reasoning?

(6)

1.2.1 Knowledge-Based Systems

(1)

1.2.2 Why Knowledge Representation?

(2)

1.2.3 Why Reasoning?

(2)

1.3 The Role of Logic

(1)

1.4 Bibliographic Notes

(1)

1.5 Exercises

(2)

2 The Language of First-Order Logic

(16)

2.1 Introduction

(1)

2.2 The Syntax

(2)

2.3 The Semantics

(4)

2.3.1 Interpretations

(1)

2.3.2 Denotation

(1)

2.3.3 Satisfaction and Models

(1)

2.4 The Pragmatics

(3)

2.4.1 Logical Consequence

(1)

2.4.2 Why We Care

(2)

2.5 Explicit and Implicit Belief

(3)

2.5.1 An Example

(2)

2.5.2 Knowledge-Based Systems

(1)

2.6 Bibliographic Notes

(1)

2.7 Exercises

(3)

3 Expressing Knowledge

(18)

3.1 Knowledge Engineering

(1)

3.2 Vocabulary

(1)

3.3 Basic Facts

(1)

3.4 Complex Facts

(2)

3.5 Terminological Facts

(1)

3.6 Entailments

(4)

3.7 Abstract Individuals

(2)

3.8 Other Sorts of Facts

(1)

3.9 Bibliographic Notes

(1)

3.10 Exercises

(4)

4 Resolution

(36)

4.1 The Propositional Case

(5)

4.1.1 Resolution Derivations

(1)

4.1.2 An Entailment Procedure

(2)

4.2 Handling Variables and Quantifiers

(12)

4.2.1 First-Order Resolution

(3)

4.2.2 Answer Extraction

(3)

4.2.3 Skolemization

(1)

4.2.4 Equality

(2)

4.3 Dealing with Computational Intractability

(7)

4.3.1 The First-Order Case

(1)

4.3.2 The Herbrand Theorem

(1)

4.3.3 The Propositional Case

(1)

4.3.4 The Implications

(1)

4.3.5 SAT Solvers

(1)

4.3.6 Most General Unifiers

(1)

4.3.7 Other Refinements

(2)

4.4 Bibliographic Notes

(1)

4.5 Exercises

(10)

5 Reasoning with Horn Clauses

(14)

5.1 Horn Clauses

(1)

5.1.1 Resolution Derivations with Horn Clauses

(1)

5.2 SLD Resolution

(4)

5.2.1 Goal Trees

(2)

5.3 Computing SLD Derivations

(3)

5.3.1 Backward Chaining

(2)

5.3.2 Forward Chaining

(1)

5.3.3 The First-Order Case

(1)

5.4 Bibliographic Notes

(1)

5.5 Exercises

(4)

6 Procedural Control of Reasoning

(18)

6.1 Facts and Rules

100

(1)

6.2 Rule Formation and Search Strategy

101

(1)

6.3 Algorithm Design

102

(1)

6.4 Specifying Goal Order

103

(1)

6.5 Committing to Proof Methods

104

(2)

6.6 Controlling Backtracking

106

(2)

6.7 Negation as Failure

108

(2)

6.8 Dynamic Databases

110

(2)

6.8.1 The PLANNER Approach

111

(1)

6.9 Bibliographic Notes

112

(1)

6.10 Exercises

113

(4)

7 Rules in Production Systems

117

(18)

7.1 Production Systems: Basic Operation

118

(1)

7.2 Working Memory

119

(1)

7.3 Production Rules

120

(2)

7.4 A First Example

122

(3)

7.5 A Second Example

125

(1)

7.6 Conflict Resolution

126

(1)

7.7 Making Production Systems More Efficient

127

(2)

7.8 Applications and Advantages

129

(1)

7.9 Some Significant Production Rule Systems

130

(2)

7.10 Bibliographic Notes

132

(1)

7.11 Exercises

133

(2)

8 Object-Oriented Representation

135

(20)

8.1 Objects and Frames

135

(1)

8.2 A Basic Frame Formalism

136

(5)

8.2.1 Generic and Individual Frames

136

(2)

8.2.2 Inheritance

138

(2)

8.2.3 Reasoning with Frames

140

(1)

8.3 An Example: Using Frames to Plan a Trip

141

(8)

8.3.1 Using the Example Frames

146

(3)

8.4 Beyond the Basics

149

(3)

8.4.1 Other Uses of Frames

149

(1)

8.4.2 Extensions to the Frame Formalism

150

(1)

8.4.3 Object-Driven Programming with Frames

151

(1)

8.5 Bibliographic Notes

152

(1)

8.6 Exercises

153

(2)

9 Structured Descriptions

155

(32)

9.1 Descriptions

156

(2)

9.1.1 Noun Phrases

156

(1)

9.1.2 Concepts, Roles, and Constants

157

(1)

9.2 A Description Language

158

(2)

9.3 Meaning and Entailment

160

(3)

9.3.1 Interpretations

160

(1)

9.3.2 Truth in an Interpretation

161

(1)

9.3.3 Entailment

162

(1)

9.4 Computing Entailments

163

(8)

9.4.1 Simplifying the Knowledge Base

164

(1)

9.4.2 Normalization

165

(2)

9.4.3 Structure Matching

167

(1)

9.4.4 The Correctness of the Subsumption Computation

168

(1)

9.4.5 Computing Satisfaction

169

(2)

9.5 Taxonomies and Classification

171

(6)

9.5.1 A Taxonomy of Atomic Concepts and Constants

172

(1)

9.5.2 Computing Classification

173

(2)

9.5.3 Answering the Questions

175

(1)

9.5.4 Taxonomies versus Frame Hierarchies

175

(1)

9.5.5 Inheritance and Propagation

176

(1)

9.6 Beyond the Basics

177

(4)

9.6.1 Extensions to the Language

177

(2)

9.6.2 Applications of Description Logics

179

(2)

9.7 Bibliographic Notes

181

(1)

9.8 Exercises

182

(5)

10 Inheritance

187

(18)

10.1 Inheritance Networks

188

(1)

10.1.1 Strict Inheritance

189

(1)

10.1.2 Defeasible Inheritance

190

(2)

10.2 Strategies for Defeasible Inheritance

192

(1)

10.2.1 The Shortest Path Heuristic

192

(1)

10.2.2 Problems with Shortest Path

194

(1)

10.2.3 Inferential Distance

195

(1)

10.3 A Formal Account of Inheritance Networks

196

(1)

10.3.1 Extensions

199

(1)

10.3.2 Some Subtleties of Inheritance Reasoning

201

(1)

10.4 Bibliographic Notes

202

(1)

10.5 Exercises

203

(2)

11 Defaults

205

(32)

11.1 Introduction

205

(1)

11.1.1 Generics and Universals

206

(1)

11.1.2 Default Reasoning

207

(1)

11.1.3 Nonmonotonicity

209

(1)

11.2 Closed-World Reasoning

209

(1)

11.2.1 The Closed-World Assumption

210

(1)

11.2.2 Consistency and Completeness of Knowledge

211

(1)

11.2.3 Query Evaluation

211

(1)

11.2.4 Consistency and a Generalized Assumption

212

(1)

11.2.5 Quantifiers and Domain Closure

213

(2)

11.3 Circumscription

215

(1)

11.3.1 Minimal Entailment

216

(1)

11.3.2 The Circumscription Axiom

219

(1)

11.3.3 Fixed and Variable Predicates

219

(3)

11.4 Default Logic

222

(1)

11.4.1 Default Rules

222

(1)

11.4.2 Default Extensions

223

(1)

11.4.3 Multiple Extensions

224

(3)

11.5 Autoepistemic Logic

227

(1)

11.5.1 Stable Sets and Expansions

228

(1)

11.5.2 Enumerating Stable Expansions

230

(2)

11.6 Conclusion

232

(1)

11.7 Bibliographic Notes

233

(1)

11.8 Exercises

233

(4)

12 Vagueness, Uncertainty, and Degrees of Belief

237

(30)

12.1 Noncategorical Reasoning

238

(1)

12.2 Objective Probability

239

(1)

12.2.1 The Basic Postulates

240

(1)

12.2.2 Conditional Probability and Independence

241

(2)

12.3 Subjective Probability

243

(1)

12.3.1 From Statistics to Belief

244

(1)

12.3.2 A Basic Bayesian Approach

245

(1)

12.3.3 Belief Networks

246

(1)

12.3.4 An Example Network

247

(1)

12.3.5 Influence Diagrams

250

(1)

12.3.6 Dempster-Shafer Theory

251

(2)

12.4 Vagueness

253

(1)

12.4.1 Conjunction and Disjunction

255

(1)

12.4.2 Rules

255

(1)

12.4.3 A Bayesian Reconstruction

259

(3)

12.5 Bibliographic Notes

262

(1)

12.6 Exercises

263

(4)

13 Explanation and Diagnosis

267

(18)

13.1 Diagnosis

268

(1)

13.2 Explanation

269

(1)

13.2.1 Some Simplifications

270

(1)

13.2.2 Prime Implicates

271

(1)

13.2.3 Computing Explanations

272

(1)

13.3 A Circuit Example

273

(1)

13.3.1 Abductive Diagnosis

275

(1)

13.3.2 Consistency-Based Diagnosis

277

(2)

13.4 Beyond the Basics

279

(1)

13.4.1 Extensions

279

(1)

13.4.2 Other Applications

280

(1)

13.5 Bibliographic Notes

281

(1)

13.6 Exercises

282

(3)

14 Actions

285

(20)

14.1 The Situation Calculus

286

(1)

14.1.1 Fluents

286

(1)

14.1.2 Precondition and Effect Axioms

287

(1)

14.1.3 Frame Axioms

288

(1)

14.1.4 Using the Situation Calculus

289

(2)

14.2 A Simple Solution to the Frame Problem

291

(1)

14.2.1 Explanation Closure

292

(1)

14.2.2 Successor State Axioms

292

(1)

14.2.3 Summary

294

(1)

14.3 Complex Actions

295

(1)

14.3.1 The Do Formula

295

(1)

14.3.2 GoLoG

297

(1)

14.3.3 An Example

298

(1)

14.4 Bibliographic Notes

299

(2)

14.5 Exercises

301

(4)

15 Planning

305

(22)

15.1 Planning in the Situation Calculus

306

(1)

15.1.1 An Example

307

(1)

15.1.2 Using Resolution

308

(4)

15.2 The STRIPS Representation

312

(1)

15.2.1 Progressive Planning

314

(1)

15.2.2 Regressive Planning

315

(1)

15.3 Planning as a Reasoning Task

316

(1)

15.3.1 Avoiding Redundant Search

317

(1)

15.3.2 Application-Dependent Control

318

(2)

15.4 Beyond the Basics

320

(1)

15.4.1 Hierarchical Planning

320

(1)

15.4.2 Conditional Planning

321

(1)

15.4.3 "Even the Best-Laid Plans..."

322

(1)

15.5 Bibliographic Notes

322

(1)

15.6 Exercises

323

(4)

16 The Tradeoff between Expressiveness and Tractability

327

(22)

16.1 A Description Logic Case Study

329

(1)

16.1.1 Two Description Logic Languages

329

(1)

16.1.2 Computing Subsumption

330

(2)

16.2 Limited Languages

332

(2)

16.3 What Makes Reasoning Hard?

334

(2)

16.4 Vivid Knowledge

336

(1)

16.4.1 Analogues, Diagrams, Models

337

(2)

16.5 Beyond Vivid

339

(1)

16.5.1 Sets of Literals

339

(1)

16.5.2 Incorporating Definitions

340

(1)

16.5.3 Hybrid Reasoning

340

(2)

16.6 Bibliographic Notes

342

(1)

16.7 Exercises

343

(6)

Bibliography

349

(28)

Index

377

Please wait while the item is added to your bag...

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Knowledge Representation and Reasoning

Summary

Table of Contents

Supplemental Materials