Thursday, April 12, 2007

Logic and Sleep

After revealing my confusion last night, I went to bed thinking I'd just exposed myself as an idiot. Nothing like that to motivate you to solve a problem for yourself! So after sleeping on it, I finally worked it out for myself.

I sort of understood role restrictions. While it's true that (∀(R|C).A) returns the same set as (∀(R).(AC)), the semantics of value and role restrictions are different. Value restriction means that every usage of a role must refer to a category, while role restriction is a selection of those usages which refer to that category.

However, I was wrong that it was the inability to see this difference that led me to false conclusions about those properties. My main problem was failing to take proper account of the universal qualifier used in the value restriction (and forgetting that this does NOT imply existence).

I finally "got it" when I thought about some example roles. Consider a town where there are a number of people named Smith and Jones (among other names). I could ask the question, "Who in town knows only the men in the Smith and Jones families?" Note that these people may also know males and females in other families, as this is not a restriction imposed by the question.

I could encode the question according to the original proposition with:

So then when I say (∀(R|C).A) this is now equivalent to (∀(knows|Smith).Male). Once I got that, I realized it was easier to think of a restricted role as a new role altogether (a sub-Property in RDFS parlance). So the new role might be called knows-a-Smith, and the expression (∀knows-a-Smith.Male) means the selection of people who only know Smiths that are male. Since I'm describing this in natural language, I should point out that the expression does not say that these people actually know anybody named Smith, only that if they do, then that Smith must be a male.

So my question of equivalence goes from:

(∀(R|C).A) ⊓ (∀(R|D).A)     ≡    ∀(R|(CD)).A

To the expression:

(∀(knows|Smith).Male) ⊓ (∀(knows|Jones).Male)     ≡    ∀(knows|(SmithJones)).Male

Or even simpler:

(∀(knows-a-Smith).Male) ⊓ (∀(knows-a-Jones).Male)     ≡    ∀(knows-a-Smith-or-Jones).Male

This means that the set of people who know only male Smiths, and also know only male Joneses is the same as the set of people who know "Smiths or Joneses" who are only male. (These things can get hard to parse in English, so it's a good thing we have a syntax that is more exact - even if it is hard to read).

It's easy to see that the intersection of Smith-knowing-people and Jones-knowing-people fall into the union expression of people-who-know-Smiths-or-Joneses. But my problem was that union includes people who only know Smiths (and not Joneses), and people who only know Joneses (and not Smiths), and I couldn't see how these people could be in the intersection expression.

An easy way to find a flaw in the proposition was to think of a counter example. ie. Who could satisfy the union, but not the intersection? There's symmetry when considering Smith or Jones, so I only have to look at one of the names. The relevant interpretations include:
  1. People who know male Smiths and also know Male Joneses
  2. People who only know male Smiths
  3. People who only know make Joneses
  4. People who don't know anyone named Jones or Smith
People who know female Smiths or Joneses are not in the intersection of (∀(knows-a-Smith).Male) ⊓ (∀(knows-a-Jones).Male). They are also not in the value union of (∀(knows-a-Smith-or-Jones).Male), since the role restriction (ie. referring to a male) is not met if they know a female with those names.

When thinking of the "union" it is easy to see that all three of the listed groups here are relevant. But for the intersection it wasn't instantly apparent for me that everyone was included:
(∀(knows|Smith).Male) ⊓ (∀(knows|Jones).Male)

For this to not be in conflict, we need all the relevant sets present on both sides of this intersection operator.

This is where I was getting caught up with the universal qualifier. Anyone in group 1 (knows both Smiths and Joneses) is on both sides of this intersection. Anyone in group 2 (knows Smiths, but not Jones) is on the left hand side of this intersection... but how are they on the right? The point here is that anyone without use of the role (knows|Smith) satisfies the condition of (∀(knows|Smith).Male), since there is a universal qualifier here, and NOT an existential qualifier. The (knows|Smith) is an empty set for these people (which threw me off), but an empty set doesn't violate the condition because of the use of the universal qualifier.


This same reasoning applies for groups 3 and 4, so I find there are no conflicts.

No comments: