0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ is order of eliminating quantifiers important? $\endgroup$ – user2965303 Nov 3 '14 at 12:52
  • $\begingroup$ @user2965303 It is not important. $\endgroup$ – Hanul Jeon 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.