Science of Computational Logic

1| Working Material |

Ste en H olldobler

International Center for Computational Logic

Technische Universit at Dresden

D{01062 Dresden

sh@iccl.tu-dresden.de

January 16, 2012

1 The working material is incomplete and may contain errors. Any suggestions are greatly

appreciated.Contents

1 Description Logic 3

1.1 Terminologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Assertions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3 Subsumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4 Unsatis ability Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5 Final Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Equational Logic 11

2.1 Equational Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2 Paramodulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3 Term Rewriting Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3.1 Termination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3.2 Con uence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3.3 Completion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.4 Uni cation Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.4.1 Uni cation under Equality . . . . . . . . . . . . . . . . . . . . . . . 28

2.4.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.4.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.4.4 Multisets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.5 Final Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3 Actions and Causality 41

3.1 Conjunctive Planning Problems . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.2 Blocks World . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.2.1 A Fluent Calculus Implementation . . . . . . . . . . . . . . . . . . . 44

3.2.2 SLDE-Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.2.3 Solving Conjunctive Planning Problems . . . . . . . . . . . . . . . . 46

3.2.4 Solving the Frame Problem . . . . . . . . . . . . . . . . . . . . . . . 46

iiiiv CONTENTS

3.2.5 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4 Deduction, Abduction, and Induction 51

4.1 Deduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.1.1 Sorts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.2 Abduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.2.1 Abduction in Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.2.2 Knowledge Assimilation . . . . . . . . . . . . . . . . . . . . . . . . . 58

4.2.3 Theory Revision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.2.4 Abduction and Model Generation . . . . . . . . . . . . . . . . . . . 60

4.2.5 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

4.3 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5 Non-Monotonic Reasoning 65Notation

In this book we will make the following notational conventions:

a constant

bt

C unary relation symbol denoting a concept

C set of concept formulas

D non-empty domain of an interpretaion

E set of equations

Edse expression containing an occurrence of the term s

Eds=te where an occurrence of the term s has been replaced by t

E equational system obtained from the term rewriting systemRR

E axioms of equality

" empty substitution

g function symbol

f symbol

F formula

F set of formulas

g function symbol

G formula

H formula

I interpretation

K a set of formulas often called knowledge base

l term; left-hand side of an equation or rewrite rule

L literal

p relation symbol

r term; the right-hand side of equations or rewrite rules

R binary relation symbol denoting a role

R term rewriting system

s term

t term

substitution

u term

U variable

V v

W variable

X v

Y variable

Z v

In addition, we will consider the following precedence hierarchy among connectives:

f8;9g:f^;_g!$:2 CONTENTSChapter 1

Description Logic

In the late 1960s and early 1970s, it was recognized that knowledge representation and

reasoning is at the heart of any intelligent system. Heavily in uenced by the work of

Quillian on so-called semantic networks [Qui68] and the work of Minsky on so-called

frames [Min75] simple graphs and structured objects were used to represent knowledge

and many algorithms were developed which manipulated these data structures. At rst

sight, these systems were quite attractive because they apparently admitted an intuitive

semantics, which was easy to understand. For example, a graph like the one shown in

Figure 1.1 seems to represent the following short story.

Dogs, cats and mice are mammals. Dogs dislike cats and, in particular, the

dog Rudi, which is a German shepherd, has bitten the cat Tom while Tom was

chasing the mouse Jerry.

Simple algorithms operating on this graph can be applied to conclude that, for example,

German shepherds are mammals, Rudi dislikes Tom, etc.

Shortly afterwards, however, it was recognized that systems based on these techniques

lack a formal semantics (see e.g. [Woo75]). What precisely is denoted by a link? What

precisely is denoted by a vertex? It was also observed that the algorithms which operated

on these data structures did not always yield the intended results. This led to a formal

reconstruction of semantic networks as well as frame systems within logic (see e.g. [Sch76,

Hay79]). At around the same time, Brachman developed the idea that formally de ned

concepts should be interrelated and organized in networks such that the structure of

these networks allows reasoning about possible conclusions [Bra78]. This line of research

led to the knowledge representation and reasoning system KlOne [BS85], which is the

ancester of a whole family of systems. Such systems have been used in a wide range

of practical applications including nancial management systems, computer con guration

systems, software information systems and database interfaces. KlOne has also led to a

thorough investigation of the semantics of the representations used in these systems and the

development of correct and complete algorithms for computing with these representations.

Today the eld is called description logic and this chapter gives an introduction into such

logics.

Description logics focus on descriptions of concepts and their interrelationships in cer-

tain domains. Based on so-called atomic concepts and relations between concepts, which

are traditionally called roles, more complex concepts are formed with the help of certain

34 CHAPTER 1. DESCRIPTION LOGIC

mammals

are areare

dogs cats mice

dislike

are

german shephards is a

is a

jerryrudi tom

has bitten was chasing

Figure 1.1: A simple semantic network with apparently obvious intended meaning.

operators. Furthermore, assertions about certain aspects of the world can be made. For

example, a certain individual may be an instance of a certain concept or two individuals

are connected via a certain role. The basic inference tasks provided by description logics

are subsumption and unsatis ability testing . Subsumption is used to check whether a cat-

egory is a subset of another category. As we shall see in the next paragraph, description

logics do not allow the speci cation of subsumption hierarchies explicitly but these hier-

archies depend on the de nitions of the concepts. The unsatis ability check allows the

determination of whether an individual belongs to a certain concept. A formal account of

these notions will be developed in the following sections.

1.1 Terminologies

We consider an alphabet with constant symbols, the variables X; Y; ::: , the connectives

:;^;_;!;$ , the quanti ers 8 and9 , and the special symbols (; ;; ) . For notational

C convenicence, C shall denote a unary relation symbols and R a binary relation symbol

R in the sequel. Informally, C denotes a concept whereas R denotes a role.

Terms are dened as usual, ie., the set of terms is the union of the set of constant

symbols and the set of variables. The set of role formulas consists of all strings of the

form R(X;Y ). The set of atomic concept formulas consists of all strings of the form

C(X). As we will see shortly, each concept formula contains precisely one free variable.

Hence, concept formulas will be denoted by F (X) and G(X), where X is the only

concept formula free variable occurring in F and G. The set of concept formulas is the smallest set C

satisfying the following conditions:

1. All atomic formulas are in C.

2. If F (X) is in C , so is :F (X).

3. If F (X) and G(X) are in C, so are F (X)^G(X) and F (X)_G(X).6

1.1. TERMINOLOGIES 5

4. if R(X;Y ) is a role formula and F (Y ) is in C, then (9Y )(R(X;Y )^F (Y )) and

(8X)(R(X;Y )!F (Y )) are in C as well.

The set of concept axioms consists of all strings of the form (8X)(C(X)! F (X)) or concept axioms

(8X)(C(X)$ F (X)). A terminology or T-box is a nite set K of concept axioms terminologyT

such that T-box

KT

1. each atomic concept C occurs at most once as left-hand side of an axiom and

12. the set does not contain any cycles.

The set of generalized concept axioms consists of all strings of the form (8X) (F (X)! gerneralized

concept axiomG(X)) or (8X) (F (X)$G(X)) .

An example of a T-box is shown in Table 1.1. Informally, the concepts woman and

man are not completely de ned but a necessary condition is stated, viz. that both are

persons. The remaining concepts are completely de ned. For example, a father is a

man who has a child which is a person. By inspection we observe that all axioms are

universally closed in a T-box. Hence, the universal quanti ers can be omitted. Likewise,

because each concept formula has precisely one free variable, this variable can be omitted as

well. Furthermore, the structure of remaining quanti ed formulas like ( 9Y ) (child(X;Y )^

parent(Y )) and (8Y ) (child(X;Y )!:man(Y )) is also quite regular, which allows for

further abbreviations like 9child : parent and 8child ::man , respectively. Alltogether,

Table 1.1 depicts the simple terminology also in abbreviated form, where the usage of the

symbols v; =; u and t instead of !; $; ^ and _ , respectively, is motivated by the

following semantics.

The semantics for terminologies is the usual semantics for rst order logic formulas.

However, the restricted form of concept formulas and concept axioms allows the represen-

tation of the semantics in a more convenient and intuitive form. Let I be an interpretation

with nite, non-empty domain D.

I I assigns to each constant a an element a of D.

I I assigns to each unary predicate symbol C a subset C D. This subset contains

Iprecisely the individuals from D which belong to C .

I I Let F and G be the subsets of D assigned to the concept formulas D(X) and

I I I IE(X), respectively. Then, I assigns DnF , F \G , and F [G to the concept1

formulas :F (X), F (X)^G(X), and F (X)_G(X), respectively.

I I I assigns to each binary relation symbol symbol R a set R DD . Let R (d)

0 Idenote the set of all d 2D obtained from R by selecting all tuples whose rst

argument is d and projecting this selection onto the second argument, i.e.,

I 0 0 IR (d) =fd 2Dj (d;d )2Rg:

Then, I assigns

I Ifd2DjR (d)\F =;g

1 0A concept C depends on the concept C wrt the T-box K i K contains a concept axiom of theT T

0form (8X)(C(X)!F (X)) or (8X)(C(X)$F (X)) such that C occurs in F . A T-box is said to

be cyclic i it contains a concept which recursively depends on itself.