There are a number of further issues I need to discuss regarding quantification in particular.

It’s easy to see that any predicate that can be expressed in terms of EXISTS can be expressed in terms of FORALL instead and vice versa. By way of example, consider the following predicate once again:

EXISTS(`x`

is taller than Steve )`x`

(“Somebody is taller than Steve”; of course, this predicate is in fact a simple proposition). Another way to say the same thing is:

NOT ( FORALL( NOT (`x`

is taller than Steve ) ) )`x`

(“It is not the case that nobody is taller than Steve”). More generally, in fact, the predicate

EXISTS(`x`

(`p`

) )`x`

is logically equivalent to the predicate

NOT ( FORALL( NOT (`x`

(`p`

) ) ) )`x`

(where the predicate *p* might legitimately involve other parameters in addition to *x*). Likewise, the predicate

FORALL(`x`

(`p`

) )`x`

is logically equivalent to the predicate

NOT ( EXISTS( NOT (`x`

(`p`

) ) ) )`x`

(where, again, the predicate *p* might legitimately involve other parameters in addition to *x*).

It follows from all of the above that a formal language doesn’t need to support both EXISTS and FORALL explicitly. But it’s very desirable to support them both in practice. The reason is that some problems are “more naturally” formulated in terms of EXISTS, while others are “more naturally” formulated in terms of FORALL instead. For example, SQL supports EXISTS but not FORALL, as we know; as a consequence, certain queries are quite awkward ...

Start Free Trial

No credit card required