Re: newbie question

From: pat hayes <phayes@ai.uwf.edu>
Date: Sun, 22 Apr 2001 13:22:21 -0500
Message-Id: <v04210143b708c4676c9a@[205.160.76.206]>
To: "Danny Ayers" <danny@panlanka.net>

```>Ok, I wanted to emphasise naivety.
>
>I am not a logician, but after muttering about the need for the ability to
>have inheritance in metadata, I'm curious to know how something like
>inheritance fits in in formal logic terms - does it fall under
>qualification? (I am reading up on this, I assure you, though it's taking me
>a while to absorb - I'd just like a predicate to be the same thing from one
>doc to the next ;-).

OK. There's a couple of very basic ideas which re-appear in a number
of different forms. The ideas are basically a thing being in a set,
and one set being a subset of another.

First form: Talk about classes and instances. Object T is instance of
class C, and one class is subclass of another class.  Traditional
terminology in OO world.

Second form: Talk about things and sets. Thing T is member of set S,
and one set is subset of another set. Traditional terminology in
mathematics.

Third form: Talk about properties and individuals (= things).
Property P is true of thing T,(written (P T) in KIF syntax, P(T) in
more traditional logical syntax) and one property entails (or
implies) another property (ie if the first one is true of something
then so is the second.) Traditional terminology in formal logic. The
connection with the first two is through the fact that in formal
logic, a property is usually treated as pretty much the same as the
set of things it is true of, so you can say (Human Joe) or Joe is in
the set/class Human, and it means the same thing.

There are other forms as well, and these are sometimes combined
together, eg. some logicians talk about sorts and subsorts (= classes
and subclasses, but treated as similar to properties, and checkable
at parse time rather than having to do arbitrary inferences).

(One thing to note about the third form is that it doesnt have any
direct way to speak about the classes/properties, so it has to use
quantifers to say the equivalent of 'subclass'. Eg (A is subclass of
B) would look like this in logic, using KIF syntax:
(forall (?x)(implies (A ?x) (B ?x))), ie anything that is in A must
be in B.  Also, notice that this usage of the word "property" is
*different* from the usage in DAML+OIL, which uses the first form. In
the first form, "property" usually means something that relates
members of a class to other things, eg 'father' is a property of
human beings. In the other terminologies this would be called a
binary relation. )

Inheritance is the inference from something being true for a whole
class, to its being true for any subclass or instance. (Think of
classes and subclasses forming a tree with the universal class at the
top and the instances at the bottom, then inheritance moves
properties 'down' this tree.) So if you know that all mammals have
warm blood and you know that Aardvarks are mammals (or that Arthur is
a mammal) you know that Aardvarks (Arthur) has warm blood. This is
just normal logical inference in the third form, eg this example
would be

(forall (?x)(implies (Mammal ?x)(Warmblooded ?x)))
(forall (?x)(implies (Aardvark ?x)(Mammal ?x)))
infer
(forall (?x)(implies (Aardvark ?x)(Warmblooded ?x)))

In the first form it might look like this:
Mammal is subclass of Warmblooded
Aardvark is subclass of Mammal
infer
Aardvark is subclass of Warmblooded

Notice that saying 'subclass' and saying 'everything in a class has a
property' amount to the same thing, which is what you would expect if
you think about it. (Some combined forms would use one syntax for
subclass and a different one for saying warmblooded, but that is just
showing off.)

The most common way this is all said is that the first form
(class/instance) is used to talk about the classes that one is
proposing to use inheritance on in some special (efficient) way, and
anything else is said in the third form and called 'rules', which is
a non-logical way to say 'axioms'.

Inheritance is such a big deal for 3 reasons: (1) subclass
heirarchies tend not to change much, or at least not very often (2)
inheritance inferences are VERY common; and (3) inheritance
inferences can be managed very efficiently if they are separated out
from other inferences. (No, four reasons. (4) It is very handy to
state properties once somewhere in the heirarchy and not have to keep
repeating them over and over for every new thing in the database. So
inheritance inferences are necessary.) All of which suggests it is a
very good idea to put inheritance inferences into a special inference
black-box and compile it down to the metal, which is what everyone
wants to do.

DAML is influenced by this goal, but like most other languages it
also had to compromise. To get really, really fast inferences you
need to restrict the inheritance to a very simple case (just subclass
and instance, basically) and people tend to want to say more
complicated things (eg property restrictions in DAML) and as soon as
you start doing that, it gets harder to keep all the relevant
inferences inside the box and keep the box running very fast.
(Actually, strictly, it gets hard to *guarantee* that the box will
run fast. In practice, one can get quite useful speeds out of quite
an expressive box almost all the time, though you do have to be
careful.)

Hope this helps some.

Pat Hayes

PS. On "predicate": logicians tend to make a very strict distinction
between things and names of things.  You will often find that one
will uses "predicate" only to refer to *names*, ie its a kind of
symbol, but others will use "predicate" to mean what the symbol
refers to, which would be what I'm calling a property. If you read
one guy's prose with the other one's meanings you will get very
confused, so find out exactly what they mean and bear it in mind when