Re: Question on DL negation

On 5 Mar 2007, at 17:21, Vaughan Pratt wrote:

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

I don't see that at all. I'm not sure what you mean by "predicates"  
and "classes" here. In DLs, classes generally refer to one place  
predicates (consider the obvious model theoretic intepretation).

> The negation of a predicate simply complements its truth value.

Er... \forall(x)(C(x) \leftarrow \neg D(x)).

The predicate doesn't have a truth value.

>   Lifting logical connectives to the status of operations on sets  
> and classes is a delicate business.

I don't know why you put it this way. That is, I don't see any  
additional insight and some confusion. General negation is powerful  
and thus difficult. Having it allows for some nice interdefinability.

>   An early step to take when making that move is to trust relative  
> complement but not absolute complement of a set or class.

"Trust" is strong, but in any case, I still fail to see that you've  
said anything different except, to my mind, in more confusing terms.

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

Uh, I'm very skeptical about this last bit, though I'm no PDL person.

	<http://www.springerlink.com/content/cf40guhq1m5t6lpu/>
	<http://www.sciencedirect.com/science? 
_ob=MImg&_imagekey=B6WJ0-4B55K9J- 
G-5&_cdi=6864&_user=494590&_orig=browse&_coverDate=04%2F30% 
2F1979&_sk=999819997&view=c&wchp=dGLbVlb- 
zSkzS&md5=e6986bd20377ddee8f055be2886a8368&ie=/sdarticle.pdf>
	<http://www.csc.liv.ac.uk/~dirk/paper/mthesis-dirkwalther.pdf>

PDL with arbitrary negation of programs (i.e., arbitrary negation of  
role expressions) is undecidable, but that's hardly the same thing as  
allowing for paradoxes. I'd be interested in your construction of the  
Russell's paradox in PDL^-. Atomic negation, on the other hand, seems  
ok. But restriction to atomic negation and restriction to  
disjointness are not quite the same thing.

Ok, this is a distraction now :)

Cheers,
Bijan.

Received on Monday, 5 March 2007 18:21:22 UTC