The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
83 views

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

asked in Mathematical Logic by Active (1.3k points) | 83 views
+1
suppose $X = \left \{ 1,2,3,4,5 \right \}$

P(x) = "x is prime"

Q(x) = "x is non prime"

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

now LHS can be true because for "P" $x$ can be 3 and for Q $x$ can be 4 whereas RHS can never be true.
0
@Utkarsk

Both are false???
+2
yes
0
@Mk Utkarsh

yes, Thank you
0
T ---> F combination? there is "equivalence" in between not "implication"
0
@ Mk Utkarsh

Sorry, mistakenly written something else, recheck the corrected one (edited)
0
how are you checking LHS and RHS different or same?
0
what is the answer given?
0
Ans given :

Option B
+1
for checking p⇔q we need to check p=>q and q=>p
So in statement S1 we can conclude p=>q is true  but q=>p is false as explained by utkarsh abve like taking example,if you try to solve mathematically than also you will get false
and same for S2 too we can say.
So according to me both are incorrect..please check:)
0
$S_1$ and $S_2$ are Same Expression. $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.
0

So in statement S1 we can conclude p=>q is true  but q=>p is false

@Shubham, In $S_1$, $Q \rightarrow P$ is Valid. Not $P \rightarrow Q.$ 

0

suppose X={1,2,3,4,5}X={1,2,3,4,5}

P(x) = "x is prime"

Q(x) = "x is non prime"

∃xP(x)→∃xQ(x)⇔∃x(P(x)→Q(x))

now LHS can be true because for "P" xx can be 3 and for Q xx can be 4 whereas RHS can never be true.

@MK Utkarsh,  (∃xP(x)→∃xQ(x)) →  ∃x(P(x)→Q(x)) is Valid. Not the converse. 

0
@deepak in first statement for example

P(x)=x passes in physics

Q(x)=x passed in chemistry

to show P->Q is valid, we cannot have case like true->false like,...... so i will try to make it if its possible than it will be invalid.

∃x(P(x)→Q(x))→(∃xP(x)→∃xQ(x))

lets take our domain x contain two children

Stnt nme         passed(p)          passes(c)

rahul                yes                      yes

rohit                 no/yes                        no/yes

LHS says there exists atleast one student who has passed both in physics and chemistry we need to make it true so i have taken exmple accordingly and have made rahul passed both,now RHS says there exist atleast one student passed in physics and one passed in chemistry not neccessary that both are same,it will result in true

so both side we get true->true,so its valid  I guess

But as other way you try it

∃x(P(x)→Q(x))←(∃xP(x)→∃xQ(x))

rahul          yes            no

rohit           no              yes

we can make LHS true but RHS will be false so we hve come up with case true-> false,so its not valid
0

so both side we get true->true,so its valid  I guess

To show Something is Valid, You can't take one case and say that it is valid. Either you would have to take all the possibilities into Consideration or You need to show No counter example exists.

 we can make LHS true but RHS will be false so we hve come up with case true-> false,so its not valid

The Original equation is of the Form $LHS \leftarrow RHS$, Not $LHS \rightarrow RHS$.  

0
@deepak i have not taken any specific case..

i have tried to make one side true and other side false. i want to ask you one thing
∃x(P(x)→Q(x)) this means this only na...that there must be atleast one student who have passed physics must have also passed chemistry(according to my abve exmple)...so if i need to make it true i have take that case in which one student passes both..so if i do this..right side can never becme false...so how come it is not valid..?
0
Stnt nme         passed(p)          passes(c)

rahul                True                    false

rohit                 false                       false

Consider this instance.
0
aha ok i got my mistake...∃x(P(x)→Q(x)) it can be true for other cases...too..:)

this point got stucked in my mind "there exist atleast one student who has passed physics must have also passed chemistry".
+1
No Problem. Refer the formal proof I given below and try to solve such question this way. Practice it more and no  such question will go wrong ever.
0
@Deepak yeah thank you..:)

2 Answers

+2 votes
Best answer

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.

answered by Boss (18.8k points)
selected by
0 votes

S1 should be false.

answered by Boss (23.9k points)
+1
@ abhishekmehta4u

Yeah, I solved it again and found the same, but S1 and S2 giving the same result.

May be key given is wrong then.
0
Yes answer may be givrn is wrong.

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,976 questions
47,609 answers
146,779 comments
62,342 users