W3C home > Mailing lists > Public > semantic-web@w3.org > March 2011

Re: Blank nodes, "leaning", and the LEM

From: Pat Hayes <phayes@ihmc.us>
Date: Wed, 23 Mar 2011 09:08:54 -0500
Cc: Enrico Franconi <franconi@inf.unibz.it>, "<tim.glover@bt.com>" <tim.glover@bt.com>, semantic-web@w3.org
Message-Id: <B51B4509-BB85-47F8-94CA-BCC3E98EA178@ihmc.us>
To: nathan@webr3.org

On Mar 23, 2011, at 8:47 AM, Nathan wrote:

> would this be a good time to gently nudge at http://www.w3.org/TR/lbase/ ?

Other sources for a similar observation include Fikes & McGuiness 2001 (http://www.ksl.stanford.edu/people/dlm/daml-semantics/abstract-axiomatic-semantics.html) and Menzel & Hayes 2003 (http://philpapers.org/rec/MENSAL-2) and Hayes 2005 (http://www.ihmc.us/ users/phayes/CL/SW2SCL.html). I am sure there are many others.

Pat

> 
> Enrico Franconi wrote:
>> On 23 Mar 2011, at 14:15, <tim.glover@bt.com> <tim.glover@bt.com> wrote:
>>> Thanks for the link, but I respectfully stick to my point.  FOL is very powerful, and no doubt can be used to model RDF; but that is very different from saying they are the same thing. FOL can be used to model all sorts of things.  And in my view the apparent and superficial similarities between RDF and FOL are misleading.
>> I also respectfully stick to my observation. The connection between RDF and logic is not accidental nor tricky nor misleading. It is plain and natural: an RDF graph is in essence a conjunction formula of triple atoms whose bnodes correspond to globally quantified existential variables. This is it. On these grounds you can use RDF as the basis of the semantic web cake, which has logics on the layers above. I don't see how this can be misleading. You can decide to ignore this fact if logic confuses you.
>> As it is shown in the paper cited below (but it is no rocket science), the essence of the semantics as defined in the RDF normative specs is completely (i.e., bidirectionally) equivalent to the existential-conjunctive fragment of first order logic with a 'triple' predicate.
>> cheers
>> --e.
>>> Tim.     From: Enrico Franconi [mailto:franconi@inf.unibz.it] Sent: 23 March 2011 13:08
>>> To: Glover,T,Tim,DES5 R
>>> Cc: semantic-web@w3.org
>>> Subject: Re: Blank nodes, "leaning", and the LEM
>>> I dare to disagree on the fact that any resemblance of RDF  to predicate logic is coincidental, accidental and entirely misleading. Please check:
>>> Jos de Bruijn, Enrico Franconi, Sergio Tessaris (2005). Logical Reconstruction of normative RDF. Proc. of the Workshosp on OWL Experiences and Directions (OWLED 2005), Galway, Ireland, November 2005. <http://www.inf.unibz.it/~franconi/papers/owled-05.pdf>
>>> cheers
>>> --e.
>>> On 23 Mar 2011, at 13:41, <tim.glover@bt.com> <tim.glover@bt.com> wrote:
>>> 
>>> 
>>>  From: Glover,T,Tim,DES5 R Sent: 23 March 2011 12:38
>>> To: 'Gregg Reynolds'
>>> Subject: RE: Blank nodes, "leaning", and the LEM
>>>  Greg,
>>> As  you pointed out in your previous email, any resemblance of RDF  to predicate logic is coincidental, accidental and entirely misleading. Blank nodes are analogous to existential variables in PL, but the systems are completely  different.
>>> The only way is to understand RDF is by reference to Pat Hayes’ semantics of 2004, which is the definitive description of RDF. This document makes explicit many of the “heresies” you mentioned earlier.
>>> According to this document,
>>> An RDF graph  is a set of RDF triples.
>>> 
>>> A sub-graph of an RDF graph is a subset of the triples in the graph
>>> 
>>> A proper instance of a graph is an instance in which a blank node has been replaced by a name, or two blank nodes in the graph have been mapped into the same node in the instance.
>>> 
>>> An RDF graph is lean if it has no instance which is a proper sub-graph of the graph. For example, the graph
>>> 
>>> <ex:a> <ex:p> _:x .
>>> _:y <ex:p> _:x .
>>> 
>>> is not lean, but
>>> 
>>> <ex:a> <ex:p> _:x .
>>> _:x <ex:p> _:x .
>>> 
>>> is lean.
>>> 
>>> The first example is not lean, because it has the instance <ex:a> <ex:p> _:x , obtained by mapping _:y to <ex:a>. The second example is lean because there is no mapping of _:x to anything which is a proper sub-graph of the original.
>>> 
>>> Taking your example,
>>>  [1]  <ex:Pedro ex:owns _:x>,  <ex:Pedro ex:owns _:y>
>>> [2] <ex:Pedro ex:owns _:x>
>>>  [1] is not lean because it has the proper instance <ex:Pedro ex:owns _:x>,<ex:Pedro ex:owns _:x>, obtained by substituting _:x for _:y.
>>> You go on to say
>>> Informally, leaning is premised on the idea that both clauses in [1] "say the same thing", namely that Pedro owns something.  So one of the clauses can be removed
>>> No, leaning is premised on the idea of a syntactic  substitution of blank nodes for something else.    I don't think this works logically.   Well it works logically, but the logic is very different from predicate logic. RDF is not predicate logic!! I strongly recommend reading the semantics document in full, and spending time on it.
>>> BTW, do not make the common mistake that the triple <a b c> represents the graph   a---b--->c.  An RDF “graph” is actually a hyper-graph in which the triples are edges, each linking three nodes.   This can’t be drawn easily -  Its best just to use the definition “an rdf graph is a set of triples” and leave it at that
>>> Best wishes,
>>> Tim
>>>  From: semantic-web-request@w3.org [mailto:semantic-web-request@w3.org] On Behalf Of Gregg Reynolds
>>> Sent: 23 March 2011 11:40
>>> To: SW-forum Web
>>> Subject: Blank nodes, "leaning", and the LEM
>>> I think the definition of leaning might be a little problematic so I could use a reality check.
>>> RDF Semantics defines (sort of) blank nodes as existentially quantified variables.  Ok.
>>> If I understand "leaning" correctly  (aside: something wrong with "normalization"?) it works something like the following.  Graph [1] below is not lean; graph [2] is the "lean" version of graph [1]:
>>> [1]  <ex:Pedro ex:owns _:x>,  <ex:Pedro ex:owns _:y>
>>> [2] <ex:Pedro ex:owns _:x>
>>> Informally, leaning is premised on the idea that both clauses in [1] "say the same thing", namely that Pedro owns something.  So one of the clauses can be removed.  (BTW, the example is inspired by the famous 'donkey sentence' "Every farmer who owns a donkey beats it".)
>>> I don't think this works logically.  Treating the blank nodes as existentially quantified variables and translating into logic (using email markup from Z, where %E% means "There exists"), [3] is equivalent to [1]:
>>> [3]   %E% x, y @ Owns(Pedro, x) /\ Owns(Pedro y)
>>> Leaning substitutes x for y in [3].  (Alternatively: it substitutes z for both) and then removes the redundant clause.  But doesn't that violate the rules of substitution?  Both x and y are bound in [3]; substituting x for y or z for both changes the meaning of [3].
>>> The problem I see is that even if the clauses in [1] individually mean "Pedro owns something", reading them as redundant means that conjunction must be vacuous.  But I don't see how that can be right; logical /\ is meaningful.  So the clauses in [1] should be read "Pedro owns some x" and "Pedro owns some y"; substituting "some thing" for both changes the meaning.  It amounts to an unmotivated abstraction.
>>> To put it another way, the symbols 'x' and 'y' in [1] are not purely extensional.  Being distinct (bound) symbols, they have different intensions and are not interchangeable.
>>> That's the syntactic view, but the semantic view is equally problematic.  The problem is that existentially quantified  sentences  characterize populations, not individuals; so existentially quantified variables do not denote individuals.  Sentence [2] says that *some* individual in the population under consideration is owned by Pedro; it does not say that _:x denotes such an individual.  So [1] could characterize a population containing one thing that Pedro owns, or it could characterize a population containing two or more such individuals:  either _:x = _:y or _:x != _:y. We have no way of knowing which.    The Law of the Excluded Middle rears its ugly head.   If [1] were a *description* of a population we could survey it and decide which case holds; but I don't see how RDF can be treated as anything but a constructive language, meaning that [1] must be treated not as description but as prescription.  The problem then is that we don't know which population to construct.  Unless we outlaw the LEM, in which case  we construct a population with exactly two individuals owned by Pedro, and leaning is invalid.  At least I think that's how it would work.  My understanding is that outlawing the LEM would require choosing _:x != _:y in [3], but I'm not entirely confident that this is correct.  I guess it relies on the implicit assumption that  P != Q in P /\ Q.  Certainly one cannot *infer* P = Q from the conjunction.  Maybe the real problem is that data description languages and logical calculi are just different beasts.
>>> To put it yet another way, leaning seems to rely on the truth value of the clauses in [1] rather than their meanings.  But by that reasoning we could discard all true clauses except one in any conjunction.  Truth would be preserved, but meaning would be mangled.
>>> Leaning amounts to the selection of _:x = _:y over _:x != _:y.  I guess you could consider that one way of dealing with the LEM, but if I'm not mistaken it amounts to a redefinition of logical conjunction, which seems a little dubious.  Or maybe not; but it sure seems counter-intuitive.  It also seems incompatible with open-world semantics, which embraces "we don't know".
>>> Does that make sense?  Am I missing something?
>>> Thanks,
>>> Gregg
>>> 
> 
> 
> 

------------------------------------------------------------
IHMC                                     (850)434 8903 or (650)494 3973   
40 South Alcaniz St.           (850)202 4416   office
Pensacola                            (850)202 4440   fax
FL 32502                              (850)291 0667   mobile
phayesAT-SIGNihmc.us       http://www.ihmc.us/users/phayes
Received on Wednesday, 23 March 2011 14:11:51 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 21:45:42 GMT