An example of translating from English to predicate calculus with comments on the scope of quantifiers

Write using predicate calculus the following:

``All blocks on top of blocks that have been moved or that are attached to blocks that have been moved have also been moved.''

We will use the following predicates:

$block(x)$ = x is a block. We can assume all objects are blocks and skip it.
$moved(x)$ = x moved
$on(x,y)$ = x is on y
$attached(x,y)$ = x is attached to y.

We can write this in our first attempt as:


\begin{displaymath}
\forall  x \: [\exists  y \: [on(x,y) \lor attached(x,y)] \land moved(y)]
\Rightarrow moved(x)
\end{displaymath} (1)

An alternative way of writing it, which is equivalent to (1), is:


\begin{displaymath}
\forall  x \: \forall  y \: [(on(x,y) \lor attached(x,y)) \land moved(y)]
\Rightarrow moved(x)
\end{displaymath} (2)

Please notice that $\forall  y$ is not in the premise of the implication but quantifies the entire expression. The general rule is that we can either use a universal quantifier which quantifies over the entire expression, or use an existential quantifier which quantifies just over the premise. They are equivalent because when we convert to CNF the premise is negated and so the existential quantifier becomes a universal quantifier.

This other writing is NOT equivalent to (1) or (2):


\begin{displaymath}
\forall  x \: [\forall  y \: (on(x,y) \lor attached(x,y)) \land moved(y)]
\Rightarrow moved(x)
\end{displaymath} (3)

Try to convert it to CNF to see the difference. You can notice that the expression
$\forall  y \: (on(x,y) \lor
attached(x,y)) \land moved(y)$ contains a universal quantifier and conjunctions but no implication.

There is one more writing which uses an existential quantifier and which is equivalent to (3):


\begin{displaymath}
\forall  x \: \exists  y \: [(on(x,y) \lor attached(x,y)) \land moved(y)]
\Rightarrow moved(x)
\end{displaymath} (4)

This is also incorrect. It says that for all blocks $x$ there exists at least a block $y$. The original sentence says that if there is a block on $y$ or attached to $y$ which moved then $x$ also moved.




Maria Gini 2004-11-15