- From: Dieter Fensel <dieter.fensel@deri.org>
- Date: Fri, 26 Aug 2005 09:42:19 +0200
- To: public-rule-workshop-discuss@w3.org
- Cc: Christian de Sainte Marie <csma@ilog.fr>
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