I have:
$$\begin{align}
\exists x \forall y P(x,y) \\
\end{align}$$
where
$$\begin{align}
M=\{a,b\} \\
\end{align}$$
I need to convert this formula to propositional logic. I know that if M is finite then you can eliminate quantifier, but what can I do when there is two quantifiers? Any hints, help would be appreciated
0
$\begingroup$
$\endgroup$
1
$\begingroup$
$\endgroup$
Try to eliminate quantifiers step by step: $$ \begin{aligned} \exists x\forall yP(x,y) &\iff \exists x (P(x,a)\land P(x,b))\\ &\iff \left(P(a,a)\land P(a,b)\right)\lor \left(P(b,a)\land P(b,b)\right). \end{aligned}$$
-
$\begingroup$ is order of eliminating quantifiers important? $\endgroup$ – user2965303 Nov 3 '14 at 12:52
-
-
$\begingroup$ If you eliminate quantifiers by different order you may get formula whose form is difficult to the form of that. But these two are logically equivalent. $\endgroup$ – Hanul Jeon Nov 3 '14 at 12:53
