1,041 views
0 votes
0 votes

" S2 is incorrect " mentioned in the solution. But I am not getting True --> false pair.

2 Answers

Best answer
2 votes
2 votes

Both $S_1$ and $S_2$ are Exactly Same Expressions. 

$P \leftrightarrow Q = Q \leftrightarrow P$

And Yes, Both are Incorrect.

$\exists x (P(x) \rightarrow Q(x)) \leftarrow (\exists x P(x) \rightarrow \exists x Q(x) )$ Is Valid.

But $\exists x (P(x) \rightarrow Q(x)) \rightarrow (\exists x P(x) \rightarrow \exists x Q(x) )$ is Not Valid.


Formal Proof :

To Prove any Bi-implication statement like $P \leftrightarrow Q$, We should usually prove it in Two parts : $P \rightarrow Q$ and $Q \rightarrow P$. 


 So, In $S_1$, Let's first Check the $Q \rightarrow P $ part i.e.

 $    (\exists x P(x) \rightarrow \exists x Q(x) )  \rightarrow \exists x (P(x) \rightarrow Q(x))  $

It is an Implication statement of the form $A \rightarrow B$...Hence It is Always True except when $A$ is True and $B$ is False.

So, Instead of proving any implication statement True, We should usually  try to prove it False as Any Implication statement will be False in only one case.

Similarly, here also, We would make $A$ True and then we will Try to make $B$ false. If we can somehow do it...then we can say that the implication $A \rightarrow B$ is False. And If we can never make $A$ True and $B$ false Simultaneously then  we can say that the implication $A \rightarrow B$ is True.  

So, Let's make $A$ true i.e. $   (\exists x P(x) \rightarrow \exists x Q(x) ) $ True.

$x$ belongs to some Non-empty domain. So, Let me take Three element ($x1,x2,x3$) in the domain..(Note that Domain need not have only or exactly three elements..there could be infinite elements as well...But with experience I found that for such equivalences(distributive properties) in logic, every type of equivalence can be shown True/False with accuracy by just having $3$ elements in the domain.. )

To make $   (\exists x P(x) \rightarrow \exists x Q(x) ) $ True, We can observe that It will be True in Two cases i.e. When $\exists x P(x)$ is False Or $\exists x Q(x)$ is True. 

So, Now making LHS $A$ i.e. $   (\exists x P(x) \rightarrow \exists x Q(x) ) $ True is Headache as we would need to consider these Two possibilities. So, Instead of making $A$ True then Trying to make $B$ false, We will do the Opposite i.e. Making $B$ false and then will try to make $A$ True. 

So, Let's make $B$ False i.e. $ \exists x (P(x) \rightarrow Q(x)) $ False.

To make it false, We can see that $ \exists x P(x)$ becomes false when for All the elements($x$) in the domain, Property $P$ becomes false.

So, To make   $ \exists x (P(x) \rightarrow Q(x)) $ False , we need to make $P(x) \rightarrow Q(x)$ False for All $x = x_1,x_2,x_3$

So, For $x_1$, To make $P1 \rightarrow Q1$ False, We will have to make $P1 = True$ and $Q1 = False$

Similarly, For $X_2, X_3$, $P2 = True, P3 =True$ and $Q2 = False, Q3 = False$

So, We can say that making $Pi = True$ and $Qi = False$, $\forall X_i \in Domain$ is the Only Possibility to make RHS $B$ i.e. $ \exists x (P(x) \rightarrow Q(x)) $ False.

Now, Since we have made RHS $B$ False, Now we will try to make LHS $A$  i.e. $   (\exists x P(x) \rightarrow \exists x Q(x) ) $  True. 

But we can see that If RHS is False, then LHS can never be True as $\exists x P(x)$ is True, Because $\forall x \in Domain$ $P$ is True, and $\exists x Q(x)$ is False because $\forall x \in Domain$ $P$ is False.

So, We can never make $A$ True and $B$ False simultaneously. Hence, 

$    (\exists x P(x) \rightarrow \exists x Q(x) )  \rightarrow \exists x (P(x) \rightarrow Q(x))  $ Is Valid.


Now let's check for 

$\exists x (P(x) \rightarrow Q(x)) \rightarrow (\exists x P(x) \rightarrow \exists x Q(x) )$

 It is an Implication statement of the form $A \rightarrow B$...Hence It is Always True except when $A$ is True and $B$ is False. So, We will apply similar approach as above and will try to make LHS True and RHS False simultaneously.

So, Let's first make RHS False i.e. $(\exists x P(x) \rightarrow \exists x Q(x) )$ False.

So, It will be False iff $\exists x P(x) $ is True and $\exists x Q(x)$ is False. So, $\exists x P(x) $ will be True if for at least one element in the Domain, $P$ is True. So, Let that element be $X_1$, So, $P1 = True$.

$\exists x Q(x) )$ will be False iff for all elements in the domain, $Q$ is False. So, $Q1 = Q2 = Q3 = False$

Now, Let's Try to make $LHS$ i.e. $\exists x (P(x) \rightarrow Q(x)) True .

So, We can see that we can make it True by putting $P2 = False$. 

So, We have just shown that we can make $LHS$ True and RHS False simultaneously. 

So, $\exists x (P(x) \rightarrow Q(x)) \rightarrow (\exists x P(x) \rightarrow \exists x Q(x) )$ is NOT Valid.


Hence, We can say that $\exists x (P(x) \rightarrow Q(x)) \leftrightarrow (\exists x P(x) \rightarrow \exists x Q(x) )$ is Not Valid.

selected by
0 votes
0 votes

S1 should be false.

No related questions found