FOL versus Rule Languages - A tutorial

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.

1) Rule languages with an operational semantics only

Many programming languages and also rule languages do not come along
with a declarative semantics. Here, the interpreter/compiler or best an
operation semantics specifying the immediate consequences of executing
of an action in this languages specify their semantics.

This may hold for many rule languages that include powerful specification
means for control flow (directly or indirectly by referring to a certain 
evaluation
strategy of the rules). "Programming" in such languages comes dangerously
close to spaghetti code and go-to programming. In reaction to this, there
were efforts in the 80tees and 90tees to separate control constructs and
define them on top of rule languages. Prominent efforts around this were
KADS and CommonKADS in Europe and Guus Schreiber may be willing
to provide a tutorial on them.

Actually, it is possible to cover the procedural aspects of such languages
in a declarative framework as shown by Transaction Logic (Tlogic, developed
by Michal Kiefer) but I am not sure whether this is in the scope of the desired
working group. Anyway if it is, we already have a powerful framework in
place to deal with it.

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.

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. 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. 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);
	- 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.

	"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.
	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]

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.
----------------------------------------------------------------
Dieter Fensel, http://www.deri.org/
Tel.: +43-512-5076485/8

Received on Friday, 26 August 2005 08:25:25 UTC