W3C home > Mailing lists > Public > public-rule-workshop-discuss@w3.org > August 2005

Re: FOL versus Rule Languages - A tutorial

From: doug foxvog <doug.foxvog@deri.org>
Date: Fri, 26 Aug 2005 12:05:34 +0100
To: Dieter Fensel <dieter.fensel@deri.org>
Cc: public-rule-workshop-discuss@w3.org, Christian de Sainte Marie <csma@ilog.fr>
Message-id: <430EF77E.4030504@deri.org>

Dieter Fensel wrote:

> Dear Christian,
> 
> thank you for you long emails that help me to understand better what you
> want to achieve. You also asked for a more detailed explanation of the
> semantics of FOL and typical rule language. I will try to provide this.

> ...
> 2) Rule languages with a model theoretical semantics
> 
> The semantics of datalog can be defined independent from any evaluation
> strategy of the rules. Basically it is defined by the minimal Herbrand 
> model
> (it is a Herbrand model with the property that any interpretation assigning
> less facts as being to be true is no longer a model) which can be defined
> In case of simple datalog without negation in the body this Herbrand model
> is unique and can be defined as as the intersection of all Herbrand models.

> In case you use more expressive rule languages there may be several
> minimal models and you need to define a preference function that selects
> one minimal model as the preferred one. And with disjunctive logic 
> programming it get even more elaborated.

> But the essence stays the same. The semantics is truly defined 
> declarative in
> terms of a defined model and not in terms of an evaluation strategy of 
> rules.

> And that extension are truly monotonic in the sense that in the case of a
> restricted sublanguage the confirm with the simpler definition of the 
> unique model.

However, below you discuss reasoning with minimal model semantics
(MMS).  MMS is non-monotonic in that anything that cannot be proved
true in MMS is concluded to be false.  Adding any (non-provable)
ground statement or rule to a Herbrand model, limits the Herbrand
space and falsifies the conclusions that various statements are
false obtained from the earlier model.

> 3) The semantics of FOL
> 
> In FOL (like in rule languages) we define interpretations as function that
> assign relations to predicate symbols and functions to function symbols.
> An interpretation of a set of formulae is called a model of that set of 
> formulas
> if they are true under this interpretation. A set of formulae is called 
> a tautology
> when it is true in any interpretation. Most reasoning in FOL is about such
> tautologies.
> 
> Now where is the difference:
> 
> 3.1) In rule languages we restrict ourselves to a certain type of 
> interpretations/models
> which are called Herbrand models. Basically we use funny self 
> referential trick
> and interpreting symbols by themselves. This does not cause much of a harm
> since the operation is truth preserving, i.e., any set of formula that 
> has a model
> also has a Herbrand model.
> 
> 3.2) NOW COMES the important difference. In FOL we reason about ALL 
> Herbrand
> models. With rule languages we select a certain Herbrand model as the 
> ground
> of our inference.

I think you mean that we CAN, not that we MUST.  Not every rule language
requires a Closed World Assumption (CWA).

> Therefore, we can often infer more information than 
> under FOL
> semantics since our statement must only be true in one specific model 
> and not
> in all possible Herbrand interpretations.

We cannot infer more because the statement must be true in one specific
model, but because (and if) we select a model which has far more
assertions in it -- the additional assertions provided by applying the
Closed World Assumption to the model.  We can infer more by making the
assumption that anything we cannot infer in our limited logic, we will 
infer as being false -- this is the Closed World Assumption.  By adding
this rule, we should not be surprised that more can be concluded.

The Closed World Assumption is not a First Order Logic rule.  It cannot
be expressed in FOL.

> THEREFORE we have the 
> contradicting situation that
>     - all these rule languages are a syntactical subset of FOL (and FOL 
> could
>     easily serve as an exchange syntax);

They are only a syntactical subset because one of their rules is not
expressed in the language -- and cannot be expressed either in their
language or in FOL.

>     - all these rule languages are not a semantical subset of FOL. They 
> have
>     MORE expressive power than the corresponding syntactical subset of
>     FOL under FOL semantics. Therefore, FOL fails as an umbrella language
>     when using its semantics.

This does not limit FOL from being used to express the language so that
it can be used as an interlingua.  It merely prevents non-monotonic
reasoning used by the rule languages with CWA.  A predicate could be
used to indicate which rule languages use the CWA.

>     "Assume you have
> 
>     p(a,b), p(b,c)
>     and the following two rules:
>     p(x,y) -> q(x,y)
>     p(x,y) & p(y,z) -> q(x,z)
> 
>     Then under minimal model semantics q is the deductive closure
>     of p, i.e., q(a,b), q(b,c), q(a,c) are true and no other q(x,y) us 
> true.

Transitive closure gives you the first three conclusions.  "Deductive
closure" provides the additional assumption of minimal model semantics
(i.e. a closed-world assumption), which gives you the final conclusion
(that no other q(x,y) is true).  Without using MMS (or CWA) this last
conclusion would not occur.

This, of course, is non-monotonic.  Adding to the model the statement,
q(a,a) would falsify the conclusion ~q(a,a) derived from MMS.

>     In FOL, this is different since you cannot exclude models in which
>     q(a,a) is true. That is, you cannot express deductive closure in 
> FOL." [1]

If you define deductive closure as applying a closed world assumption
after deducing what can be deduced, then it is non-monotonic.  Thus,
you cannot express a non-monotonic result in FOL.  This is correct.

However, one needn't be restricted to a CWA.

> 3.3) Finally you could hope for the following. Okay, lets take FOL and 
> apply a
> unique Herbrand model semantics to it and we have our super language.
> Unfortunately, this is a NO GO. Such unique models only exist for 
> syntactical
> restrictions of FOL and there is no known way to define such a model for 
> full
> FOL.
> 
> I hope this helps.
> 
> 
>     -- dieter
> 
> 
> PS: I do not think you need a PhD in logics in order to understand this 
> stuff. At least
> I "only" hold an PhD in applied economics.
> 
> [1] All facts, that are not element of the minimal Herbrand model are 
> necessarily
> false, i.e., their negation is true (at least as long as you stay in a 
> two valued logic;
> compare an earlier email of Gerd Wagner). Therefore, the ongoing 
> discussion about
> NAF, SNAF, XRAF and waffwaff is slightly pointless.

It seems to me that if you assume a nonmonotonic logic, that wouldn't
make discussion of non-monotonic logics pointless.

> ----------------------------------------------------------------
> Dieter Fensel, http://www.deri.org/
> Tel.: +43-512-5076485/8

==========================================================
douglas foxvog	  doug.foxvog@deri.org	 +353 (91) 495 150
Digital Enterprise Research Institute (DERI)
National University of Ireland, Galway
Galway, Ireland				http://www.deri.ie
==========================================================
Received on Friday, 26 August 2005 11:05:46 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 8 January 2008 14:16:23 GMT