• edited by
26,356 views
60 60 votes

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)$

12 Answers

Best answer
86 86 votes

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.

• edited by
74 74 votes

Answer..

36 36 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.
18 18 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.

4 4 votes

For brevity, $P(x)$ is written as $P_x$ and the connectives are interchanged with +, *, ‘

Let the domain be $\{1, 2\}$

Option A:

$\forall x (P_x + Q_x) \rightarrow \forall x P_x + \forall x Q_x$

$=\{(P_1 + Q_1)(P_2 + Q_2)\} \rightarrow P_1P_2 + Q_1Q_2 = P_1’Q_1’ + P_2’Q_2’ + P_1P_2 + Q_1Q_2 =$ a contingency

 

Option B: (Ans)

$\forall x (P_x \rightarrow Q_x) \rightarrow (\forall x P_x \rightarrow \forall x Q_x)$

$= (P_1’+ Q_1)(P_2’+ Q_2) \rightarrow (P_1P_2 \rightarrow Q_1Q_2) = P_1Q_1’ + P_2Q_2’ + (P_1’ + P_2’) + Q_1Q_2$

$= P_1’ + Q_1’ + P_2’ + Q_2’ + Q_1Q_2 = P_1’ + P_2’ + (Q_1Q_2)’ + Q_1Q_2 = 1 = $ valid

 

Option C:

$(\forall x P_x \rightarrow \forall x Q_x) \rightarrow \forall x (P_x \rightarrow Q_x)$

$= (P_1P_2 \rightarrow Q_1Q_2) \rightarrow  (P_1’+ Q_1)(P_2’+ Q_2) = (P_1P_2)(Q_1Q_2)’ + (P_1’+ Q_1)(P_2’+ Q_2) =$ contingency

 

Option D:

$(\forall x P_x \leftrightarrow \forall x Q_x )\rightarrow \forall x (P_x \leftrightarrow Q_x)$

$=(P_1P_2 \leftrightarrow Q_1Q_2) \rightarrow (P_1 \leftrightarrow Q_1)(P_2 \leftrightarrow Q_2)$

$=(P_1P_2Q_1Q_2 + (P_1P_2)’(Q_1Q_2)’) \rightarrow (P_1Q_1 + P_1’Q_1’)(P_2Q_2 + P_2’Q_2’)$

$=(P_1P_2Q_1Q_2)’(P_1P_2 + Q_1Q_2) + (P_1Q_1 + P_1’Q_1’)(P_2Q_2 + P_2’Q_2’) = $ contingency

 

NOTE:

For Options (A.), (C.) and (D.) put $P_1,P_2,Q_1,Q_2 = 1, 0, 0, 1$ to prove contingency

Answer:
Position:
Show:

Related questions

73 73 votes
7 answers 7 answers
26.7k
26.7k views
Ishrat Jahan asked Nov 3, 2014
26,716 views
Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to...
31 31 votes
5 answers 5 answers
9.3k
9.3k views
Ishrat Jahan asked Nov 3, 2014
9,288 views
Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to...
48 48 votes
8 answers 8 answers
13.1k
13.1k views
Ishrat Jahan asked Nov 3, 2014
13,107 views
A sink in a directed graph is a vertex i such that there is an edge from every vertex $j \neq i$ to $i$ and there is no edge from $i$ to any other vertex. A directed grap...
48 48 votes
5 answers 5 answers
16.1k
16.1k views
Ishrat Jahan asked Nov 3, 2014
16,137 views
A sink in a directed graph is a vertex i such that there is an edge from every vertex $j \neq i$ to $i$ and there is no edge from $i$ to any other vertex. A directed grap...