1.5k 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)$
This type question is also solved to convert Digital logic

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.
selected by
@Srestha, this is how by giving statements to the proposition you've translated the statements. However, where is the proof part??

@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

Someone please give a counter example for C) option. I think that it should also be true.
check my comment above.
@bikram @manu00x can you explain why C & D are not true?

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.

How? will you brief it?

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

@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
ans B)

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. [   (∀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.

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 (∀x P(x)) or (∀xQ(x)) to be true, each must be true for all values which is not possible as per assumption we made.Thus, RHS becomes FALSE.

thus, T → F makes statement A False.

C. [ ∀x(P(x)) ⟹ ∀x(Q(x)) ] ⟹ [ ∀x(P(x)⟹Q(x)) ]

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

 x P(x) Q(x) x1 F T x2 T F

LHS: for assumed domain ∀x(P(x)) will becomes False and  ∀x(Q(x)) will also false as a whole.Since F → F is True, LHS becomes TRUE.

RHS: for x1 (P(x)⟹Q(x)) is True and for x2 (P(x)⟹Q(x)) is False. As a whole ∀x(P(x)⟹Q(x)) becomes False, thus RHS becomes FALSE.

thus, T→F makes statement C as False.

D. [ ∀x(P(x)) (∀x(Q(x))) ] ⟹ [ ∀x(P(x) Q(x)) ]

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

LHS:  ∀x(P(x)) becomes false as x1 is false. Also (∀x(Q(x))) becomes false as x2 is false.Thus F ↔ F implies LHS is TRUE.

RHS: (P(x) Q(x)) will be false for both x1 and x2. Hence ∀x(P(x) Q(x)) becomes False which makes RHS to be FALSE.

thus T→F makes statement D as False.

B. [ ∀x(P(x) ⟹ Q(x)) ] ⟹ [ (∀xP(x))(∀xQ(x)) ]

as we are assuming LHS to be TRUE then we'll not make any such a 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:

 x P(x) Q(x) x1 T T x2 F T x3 F F

LHS: (P(x) ⟹ Q(x)) becomes TRUE for each value and thus ∀x(P(x) ⟹ Q(x)) become TRUE.

RHS: (∀xP(x)) 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.

All the other options can be eliminated by using method of contradiction

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

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

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.??

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.

k i got.. we have to think more..:) and WE have to check RHS also.!!to check it is false or true!!