3
$\begingroup$

I want to express the fact that for all $x \in A$ that have the property that for all $y\in x$ $T(x,y)$ is true and there exists an $u \in B$ such that $P(y,u)$ is true AND for all $v\in C$, $Q(y,v)$ and $R(x,v)$ are also true, then $S(x)$ is true.

(Note that this statement is just a toy statement I have invented, because I was not sure I understood this transformation well, so I wanted to make it difficult, keeping with the idea, that if I got this difficult one right, that I probably understood how to do the transformations)

Formulated in a formal language of predicate logic, would this be

$ \forall x ( x\in A \land \ \ \forall y (y\in x \rightarrow \ ( T(x,y) \land \ldots $ $ \ldots \land ( \exists u ( u \in B \land P(y,u) \land \forall v ( v\in C \rightarrow ( Q(y,v) \land R(x,v)))))))\rightarrow S(x) ) $

(hope I didn't forget any paranthesis...) ?

Is there also a way to move the quantifiers "$\forall$" at the front, so that that string starts with $\forall x \forall y \ldots$ ?

  • 1
    All quantifiers can be moved to the front. However, we cannot in general move the universal quantifiers to the front, to be followed by the existential quantifiers. (I am assuming that we will not introduce additional function symbols to the language.)2011-07-15

1 Answers 1

3

As André said, you can move all of the quantifiers to the front; the result is an expression in what is called prenex normal form, and the conversion can be done quite mechanically. A formula can have more than one prenex normal form, but they will of course all be logically equivalent.

Edit: As Carl reminded me, logically equivalent prenex forms can (contrary to what I originally wrote) begin with different quantifiers: $\forall x \exists y(\phi(x) \land \psi(y))$ and $\exists y \forall x (\phi(x) \land \psi(y))$ are both prenex forms of $\forall x \phi(x) \land \exists x \psi(x)$. However, the order of the quantifiers can also matter: $\forall x \exists y \phi(x,y)$ and $\exists y \forall x \phi(y,x)$ are not logically equivalent. And it is certainly not possible in general to bring all of the universal quantifiers to the front.

  • 0
    @ Brian M. Scott ok, thanks, good remark about the scope of $u$2011-07-16