Self

Question

∀x∃y P(x) → Q(y) ≡ ∀x P(x) → ∃yQ(y)

We have to prove whether this is a tautology or not.

How do we proceed ?

Comments

please check your question again, not able to decode left part.

I also had this kind of doubt ... so you can also refer https://gateoverflow.in/63850/propositional-logic-self-doubt#c64264

---

That is exactly the problem, even I can't decode the left part. We have two variables x and y and on LHS we have both ∀x ∃y applied to the entire scope of LHS.

However, the other part of my question is: if we have quantified predicates, what is the method to test for a tautology?

Answer 1

Let $P\left ( x \right )=$" $x$ is a is divisible by  2

Let $Q\left ( y \right )=$" $y$ is a Divisible by  4

And let domain be even number.

$\forall x \exists P\left ( x \right )\rightarrow Q\left ( x \right )$

LHS implies $\forall P\left ( x \right )$  is true and also $\exists y Q\left ( y \right )\left [ y=\left \{ 4,8,12,.. \right \} \right ]$

True$\rightarrow$True $\Rightarrow$true

now $\forall x P\left ( x \right )\rightarrow \exists y Q\left ( y \right )$

$\forall x P\left ( x \right )$ is always true and also $\exists y Q\left ( y \right )$ is also true 

True$\rightarrow$true$\Rightarrow$true 

$\therefore$LHS$=$RHS

If you have confusion change the domain,

---

Let domain be  the Prime number,

now taking your LHS $\forall P\left ( x \right )$ is false ,you can blindly say LHS is True and same for RHS giving $\Rightarrow$LHS= RHS

---

Answer 2

P: fall from scooter

Q: break the leg

LHS: If all fell from scooter, then some of them broke their legs.

RHS: Also the same thing.

So, tautology.

We can move the Ǝy ahead so that LHS is equivalent to RHS.