checking validity of given first order logic

59 Views Asked by At

Apologies if this question is already posted.As it is hard to search $\LaTeX$ in google and first order logic in nothing without $\LaTeX$ .But i am sure i have different doubt than that of already posted one!

Question

Check if the given formula is valid or not.

$1.\forall x \exists y P(x,y) \Rightarrow \exists y \forall x P(x,y)$

$2.\forall x (P(x) \Rightarrow Q(x))\Rightarrow \left ( \forall x P(x) \Rightarrow \forall x Q(x) \right )$

My Approach

$1.\forall x \exists y P(x,y) \Rightarrow \exists y \forall x P(x,y)$

$x=\text{set of all boys}$

$y=\text{set of all girls}$

$P(x,y)=\text{x loves y}$

LHS=All boys loves some girls

RHS=some girl is loved by every boy. Hence $LHS \rightarrow RHS $ is not valid as LHS=true and RHS=false

$2.\forall x (P(x) \Rightarrow Q(x))\Rightarrow \left ( \forall x P(x) \Rightarrow \forall x Q(x) \right )$

$x=\text{set of natural numbers}$

$P(x)=x \text{which is multiple of }4$

$Q(x)= \text{Even natural numbers }$

LHS= $\forall x (P(x) \Rightarrow Q(x))$ which is always true.

RHS=$\left ( \forall x P(x) \Rightarrow \forall x Q(x) \right )$

which says that if everything is multiple of $4$ then everything is even which is not true.

Hence $LHS \rightarrow RHS $ is not valid as LHS=true and RHS=false

But i feel that $2$ is incorrect. Please help!