# Re: Question on DL negation

From: Bijan Parsia <bparsia@cs.man.ac.uk>
Date: Mon, 5 Mar 2007 18:20:47 +0000
Message-Id: <1483A7D2-2D8D-4C64-82C6-C7C36A99E35C@cs.man.ac.uk>

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

<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