10,975 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
how to solve these questions?

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. $\mathbf{[ (\forall 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, atleast one of the $P(x)$ or $Q(x)$ must be true for all values of $x$, 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.

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

by

Thanks for the video.

Can someone please provide a algebraic proof for option B?

When I try to derive it, I get,

$\forall x [ P(x) \rightarrow Q(x) ] \ \rightarrow \ [\exists x P(x) \rightarrow \forall x Q(x)]$

$\exists$(x) means true for atleast one x.

$\forall$(x) means true for each and every x.
This is what I was looking for. This can be applied to any problem and can be solved in a couple of minutes. Thanks a lot man!!

Sir @

typo in option C right side

F → T is T

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.

check my comment above.
@bikram @manu00x can you explain why C & D are not true?
@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

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
yes prashant sir that is very nice approach Arjun sir and @bhuv explain that approach very clearly