The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+28 votes
3.8k views

Let $P(x)$ and $Q(x)$ be arbitrary predicates. Which of the following statements is always TRUE?

  1. $\left(\left(\forall x \left(P\left(x\right) \vee Q\left(x\right)\right)\right)\right) \implies \left(\left(\forall x P\left(x\right)\right) \vee \left(\forall xQ\left(x\right)\right)\right)$
  2. $\left(\forall x \left(P\left(x\right) \implies Q\left(x\right)\right)\right) \implies \left(\left(\forall x P\left(x\right)\right) \implies \left(\forall xQ\left(x\right)\right)\right)$
  3. $\left(\forall x\left(P\left(x\right) \right) \implies \forall x \left( Q\left(x\right)\right)\right) \implies \left(\forall x \left( P\left(x\right) \implies Q\left(x\right)\right)\right)$
  4. $\left(\forall x \left( P\left(x\right)\right) \Leftrightarrow \left(\forall x \left( Q\left(x\right)\right)\right) \right) \implies \left(\forall x  \left (P\left(x\right) \Leftrightarrow Q\left(x\right)\right)\right)$
asked in Mathematical Logic by Boss (19.1k points)
edited by | 3.8k views
+1
This type question is also solved to convert Digital logic
0
how to solve these questions?

7 Answers

+20 votes
Best answer

Procedure to be followed: For each option assume LHS to be TRUE and try to make RHS be False by selecting some values which makes LHS true in every condition.
(one can also start from RHS assuming it to be false and trying to make LHS to be true)

A. $[   (\forall  \mathbf{x (P(x)} ∨ \mathbf{Q(x))) ]} ⟹ [ (∀ \mathbf{x P(x))} ∨ \mathbf{(∀xQ(x))} ]$

 Let us assume the domain of $x$ such that, for the first half of the values $P(x)$ is True & $Q(x)$ is False while for the other half, $Q(x)$ is True and $P(x)$ is False.

LHS: Since for LHS to be true either $P(x)$ or $Q(x)$ should be true. Hence our assumption of the domain will make LHS be TRUE.

RHS: for $(∀\mathbf{x P(x))}$ or $(∀ \mathbf{x Q(x))}$ to be true, each must be true for all values which is not possible as per assumption we have made.Thus, RHS becomes FALSE.

Thus, $T → F$ makes statement A False.

C. $[ ∀\mathbf{x(P(x))} ⟹ ∀\mathbf{x(Q(x))} ] ⟹ [ ∀\mathbf{x(P(x)⟹Q(x))} ]$

Let us assume some values of $P(x)$ and $Q(x)$ as follows :

$$\begin{array}{l|l|l} \text{$x$}  &  \text{$P(x)$} & \text{ $Q(x)$} \\ \hline \text{$x_1$} & \text{$F$} & \text{$T$} \\ \text{$x_2$} & \text{$T$} &\text{$F$}  \end{array}$$
LHS: for assumed domain $∀ \mathbf{ x(P(x)) }$ will becomes False and  $∀\mathbf{x(Q(x))}$ will also be false. Since $F → F$ is True, LHS becomes TRUE.

RHS: for $x_1$ $\mathbf{[(P(x)⟹Q(x))}$ is True and for $x_2$ $\mathbf{(P(x)⟹Q(x))}$ is False. As a whole $∀\mathbf{x(P(x)⟹Q(x))}$ becomes False, thus RHS becomes FALSE.

      Thus, $T→F$ makes statement C as False.

D. $[ ∀\mathbf{x(P(x))} ⇔ \mathbf{(∀x(Q(x))) ]} ⟹ [ ∀\mathbf{x(P(x) ⇔ Q(x)) ]}$

   if we assume same domain as in above option C,then observations are as following :

LHS:  $∀\mathbf{x(P(x))}$ becomes false as $x_1$ is false. Also $(∀\mathbf{x(Q(x)))}$ becomes false as $x_2$ is false.Thus $F ↔ F$ implies LHS is TRUE.

RHS: $\mathbf{(P(x) Q(x))}$ will be false for both $x_1$ and $x_2$. Hence $∀\mathbf{x(P(x) ⇔ Q(x))}$ becomes False which makes RHS to be FALSE.

    Thus $T→F$ makes statement D as False.

B. $[ ∀\mathbf{x(P(x) ⟹ Q(x)) ] ⟹ [ (∀xP(x)) ⟹ (∀xQ(x)) ]}$

    As we are assuming LHS to be TRUE then we'll not make any selection in which $P(x)$ is True and $Q(x)$ is false as it will make our assumption false.Thus values can be like this:

$$\begin{array}{l|l|l}\text{$x$}  &  \text{$P(x)$} & \text{ $Q(x)$} \\\hline \text{$x_1$} & \text{$T$} & \text{$T$} \\ \text{$x_2$} & \text{$F$} &\text{$T$} \\ \text{$x_3$} & \text{$F$} &\text{$F$}   \end{array}$$
LHS: $\mathbf{(P(x) ⟹ Q(x))}$ becomes TRUE for each value and thus $∀\mathbf{x(P(x) ⟹ Q(x))}$ become TRUE.

RHS: $\mathbf{(∀xP(x)) \text{ and } (∀xQ(x))}$ both becomes false for assumed values which implies $F→F$ and thus makes RHS to be TRUE.

Hence $T→T$ makes statement B to be TRUE. Thus Answer is B.

answered by Active (1.8k points)
edited by
0
Awsome... Excellent..   Thanks... initally after seeing , i was thinking that its too long. but now understand....
0

A. [   (∀x (P(x) ∨ Q(x))) ] ⟹ [ (∀x P(x)) (∀xQ(x)) ]

      Let we assume domain of x such that for the first half of the values P(x) is True & Q(x) is False while for another half, Q(x) is True and P(x) is False. 

how for all x is satisfied when domain contain half of those values for which  p(x) is not true?

0

@Anshul Shankar, 

try to understand it like this, in LHS we have certain values of x . Now for LHS to be true, for all x either P(x) True or Q(x) true. Both can not be False for same 'x'. Hence this assumption will make whole LHS true.

Now come to RHS. In our assumption we assume that for first half only P(x) is true. So ∀x P(x) become false.

Similar reasoning for ∀x Q(x) and hence RHS become False.

0
very helpful !
0
Why did you take T->F case in Option C. If you take then it is also false.am i right?
0
Thank you so much for the explanation.
0
Thanks for the video.
+35 votes

Answer..

answered by (417 points)
0
very gud explaination buddy .. keep it up :)
0
CHECK D option in ur explanation both p1 and p2 shoud be true
0
How are you taking these examples I'm unable to understand.
+1
very gd answer  ....  This is the quick approach to solve ..... For all means AND and There exists mean OR ...
0

Aaditya Pundir  Puja Mishra in option C RHS, why we have taken [ P2-->(Q3.Q4)] and not [P2-->(Q1.Q2)]. I know there's a for all x outside , but why the domains are changing for Q(x) ?

0
can someone verify whether this method is correct or not, Problem I think is that he is taking two pairs of P and two pairs of Q at same time
0
It is a perfectly valid method.U can watch Kiran sir lectures regarding this topic, they are excellent.
0
When I am taking q1-T and q2 as F I am getting option a is correct ..
0
If we put P1,Q1 = F and P2,Q2= T

Then method wouldn't work for A
0
Best answer....
+28 votes
Answer: B

Let P: Student is a girl.

and Q: Student is smart.

Option B says: IF for all student x if x is a girl then the student is smart THEN if the whole class comprises of girls then the whole class comprises of smart students.
answered by Boss (33.8k points)
0
Why not? :)
0
how is option D wrong? can someone elaborate?
+9
If everyone is having black money everyone will hate demonatisation. This does not imply
"If anyone is having black money he hates demonatisation".
But the second statement does imply first as it is true for each element of the set and hence must be true for all elements taken together.
0
Like you did for option B, can u Please explain an example for other options?
0
can someone please provide the way to solve these type of questions ?
0
Please explain how option D is wrong. Thanks.
0
Using the example given.

Option A

For all students x , x is a girl or x is a smart person .  then
 All students are girls or all students are smart persons.

Option C

All students are girls then all are smart people .  then
for all students if x is  girl then it is a smart student .

How does these are wrong ? :o
 

  How does this is wrong ?
0
thanks sir.
0
According to me, options B,C,D are correct. Provable by proof by contradiction. Please correct me if wrong.
0
Please explain option C by taking an example.
0
How option D is wrong?

for example:

LHS

if every student is passed in physics then every student is passed in chemistry AND if every student is passed in chemistry then every student is passed in physics.

RHS

for every student if he is passed in phy then he is passed in chem and if he is passed in chem then he is passed in phy.

if LHS is true then definitely RHS will also be true. then how option D is wrong.
0

@soumya29 here is an example showing why option c is not always true.

let LHS means if every student is passed in physics then every student is passed in chemistry

and RHS means for every student x if x is passed in physics then x is also passed in chemistry

now to prove that option c is not always true we have to make LHS true and RHS false

+2
P: Student is a girl.

and Q: Student is smart.

B)(every student, if she is girl then smart) implies (if every student is girl then any student is smart)

C) (if every student is girl then any student is smart) implies (every student, if she is girl then smart)

D) (every student is girl if and only if any student is smart) implies (every student, if and only if she is girl then smart)
0
@Srestha, this is how by giving statements to the proposition you've translated the statements. However, where is the proof part??
0

@Devshree

yes. And when I converted them , the statement itself told which is true and which is false.

Isnot it?

See what B) told

"every student , if she is girl" means every student neednot to be girl , but when the student is girl, then she is smart.

Now, in RHS told "every student is girl" this set is smaller one.

That is why LHS implies RHS

Similarly other option too

+1
Someone please give a counter example for C) option. I think that it should also be true.
0
check my comment above.
0
@bikram @manu00x can you explain why C & D are not true?
0
@arjun sir your approach to solve these type of question by taking a set of values and try to false is really awesome ,i always follow that approach and feel calm
+17 votes

For these kind of quetion use method.

Put RHS is false then try to make LHS is true . if this happen then statemnt is false otherwise true.

Or 

Put LHS is True then try to make RHS is False . if this happen then statemnt is false otherwise true.

answered by Veteran (61.4k points)
0
How? will you brief it?
0

Can u please brief on how to arrive at the solution using above method

0
@anirudh,
Can u pls explain that method using all the options ?   Because there is no resouces n=or nothing i knew which give a general easy approch to these kind of question :(

If you can do it would be a great help
0
yes prashant sir that is very nice approach Arjun sir and @bhuv explain that approach very clearly
0 votes
For the better explanation check this one

https://www.youtube.com/watch?v=xR2YzdGzf9k
answered by Junior (605 points)
–4 votes
ans B)
answered by Active (2.6k points)
–5 votes
D is the correct answer.

All the other options can be eliminated by using method of contradiction
answered by (253 points)
0

D is not correct. You can see other examples here- you can follow similar methods used here and solve these questions easily:
https://gateoverflow.in/questions/mathematics/discrete-mathematics/mathematical-logic

0
Is 'C' the right answer? and thanks.
0
Nopes. You can try a small set and assume some P and Q. You will get the answer.
0

sir ,suppose set X={3,6,12,24 }

                         P : multiple of 3     

                         Q :even no

in (c) option it says " if  for every X P is true then for all X q also true.." (  this left side of implication)

in above eg for all values of X p is true as all elements of X are multiple of 3  but for all q it is not true 

hence left side of implication is false so (FALSE)' + (x(P(x)Q(x))) which is true .?? sir plzz help.??

0

That is correct. But you just proved C is not a contradiction by giving an example where it evaluates to TRUE. But you have to prove C is ALWAYS TRUE. In your example, replace 24 with 25 and you will get such an example. 

+1
k i got.. we have to think more..:) and WE have to check RHS also.!!to check it is false or true!!
0
This link is not working.
Answer:

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
49,434 questions
53,630 answers
186,008 comments
70,900 users