OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]
Duality of quantifiers

Hi Folks,

So, you’ve got an XML document containing a bunch of integers:









You want to know: Is it true that not all the integers are even?


To find the answer, you create this XPath expression:


not (every $x in /Test/* satisfies $x mod 2 eq 0)

“Is it not the case that every x in Test is even?”

Alternatively, you could have written the XPath expression this way:

some $x in /Test/* satisfies not ($x mod 2 eq 0)

“Are there some x in Test that are not even?”

The two XPath expressions are equivalent – they produce the same results.

Let’s denote the test for evenness ($x mod 2 eq 0) with p(x), where p represents the evenness test on x.

Let’s denote the set of values being evaluated ( /Test/* ) with seq.

Then the two XPath expressions can be written:

not (every $x in seq satisfies p(x))

some $x in seq satisfies not p(x)

Using a slightly more abstract (non-XPath) notation, we can write the expressions as:

not (for all x) p(x)

(for some x) [not p(x)]

The two expressions are equivalent.

for all” and “for some” are called quantifiers. In particular, “for all” is called the universal quantifier and “for some” is called the existential quantifier.

The equivalence of these two expressions:

not (for all x) p(x)

(for some x) [not p(x)]

is called the “duality of quantifiers”.

Here are two more equivalent expressions, exhibiting the duality of quantifiers:

          not (for some x) p(x)

          (for all x) [not p(x)]

Converting them to XPath, we have:

not (some $x in /Test/* satisfies $x mod 2 eq 0)

          every $x in /Test/* satisfies not ($x mod 2 eq 0)

Both express this: “Is it the case that none of the x values are even?”



[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]

News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 1993-2007 XML.org. This site is hosted by OASIS