Re: Question on DL negation

Bijan Parsia wrote:
> You can see by playing around with combinations of the role constructors 
> the effects on complexity.
> 
> Remember that all this is just (a fragment of) FOL (well, except if you 
> add transitive closure per se), so all the constructors are just normal 
> propositional (for the most part) connectives on binary predicates.
> 
> Expressive role constructors are associated with propositional dynamic 
> logic (and converse propositional dynamic logic).
> 
> It's also instructive to see how arbitrary concept negation is 
> difficult. You can see in the tractable fragments document that most of 
> them allow concept (i.e., restricted) disjointness:
>     <http://www.cs.man.ac.uk/~ezolin/logic/complexity.html>

The difficulty with negation arises when passing from predicates to 
classes.  The negation of a predicate simply complements its truth 
value.  Lifting logical connectives to the status of operations on sets 
and classes is a delicate business.  An early step to take when making 
that move is to trust relative complement but not absolute complement of 
a set or class.

In the standard (Fischer-Ladner) semantics of propositional dynamic 
logic, propositional negation of P is interpreted as the complement of 
the set of worlds in which P holds *relative to* a specified *set* W of 
all possible worlds constituting the underlying set of the Kripke 
structure.  If your semantics has that form then you are on safe ground 
with negation.  If however it just has the intuitive meaning of 
"everything else" then you leave yourself wide open to the problems of 
impredicativity such as Russell's Paradox.

Vaughan

PS.  I'm very much enjoying the fractal discussion, but have been 
resisting the strong temptation to participate.

Received on Monday, 5 March 2007 17:22:04 UTC