edited by
16,300 views
78 votes
78 votes

Which of the following predicate calculus statements is/are valid?

  1. $(\forall (x)) P(x) \vee (\forall(x))Q(x) \implies (\forall (x)) (P(x) \vee Q(x))$
  2. $(\exists (x)) P(x) \wedge (\exists (x))Q(x) \implies (\exists (x)) (P(x) \wedge Q(x))$
  3. $(\forall (x)) (P(x) \vee Q(x)) \implies (\forall (x)) P(x) \vee (\forall (x)) Q(x)$
  4. $(\exists (x)) (P(x) \vee Q(x)) \implies \sim (\forall (x)) P(x) \vee (\exists (x)) Q(x)$
edited by

6 Answers

Best answer
76 votes
76 votes
  1. The corresponding English meaning: If $P(x)$ is true for all $x$, or if $Q(x)$ is true for all $x$, then for all $x$, either $P(x)$ is true or $Q(x)$ is true. This is always true and hence valid. To understand deeply, consider $X = \{3,6,9,12\}$. For LHS of implication to be true, either $P(x)$ must be true for all elements in $X$ or $Q(x)$ must be true for all elements in $X$. In either case, if we take each element $x$ in $X$, either one of $P(x)$ or $Q(x)$ will be true. Hence, this implication is always valid.
    If still in doubt, let $P(x)$ mean $x$ is a multiple of $3$ and $Q(x)$ means $x$ is a multiple of $2$.
  2. The corresponding English meaning: If $P(x)$ is true for at least one $x$, and if $Q(x)$ is true for at least one $x$, then there is at least one $x$ for which both $P(x)$ and $Q(x)$ are true. This is not always true as $P(x)$ can be true for one $x$ and $Q(x)$ can be true for some other $x$ . To understand deeply, consider $X = \{3,6,9,12\}$. Let $P(x)$ be $x$ is a multiple of $9$ and $Q(x)$ be $x$ is a multiple of $6$. Now, LHS of implication is true, since $P(x)$ is true for $x = 9$, and $Q(x)$ is true for $x = 6$. But RHS of implication is not true as there is no $x$ for which both $P(x)$ and $Q(x)$ holds.  Hence, this implication is not valid.
  3. If for each $x$, either $P(x)$ is true or $Q(x)$ is true then $P(x)$ is true for all $x$ or $Q(x)$ is true for all $x$. Just one read is enough to see this is an invalid implication. Consider set $\{2,4,5\}.$ Here every element is either a multiple or $2$ or $5.$ But all elements are neither multiple of $2$ nor $5.$
  4. If there is at least one $x$ for which either $P(x)$ or $Q(x)$ is true then either it is not the case that $P(x)$ is true for all $x$ or $Q(x)$ is true for at least one $x$. This is clearly invalid as  LHS of implication becomes true if $P(x)$ is true for some $x$ and $Q(x)$ is not true for any $x$, but RHS will be false (if $P(x)$ is true for all $x$).
    A little modification to the statement is enough to make it valid:
    $$\exists (x) (P(x) \vee Q(x)) \implies \sim (\forall (x) \sim  P(x)) \vee \exists (x) Q(x)$$
    which means if there is at least one $x$ for which either $P(x)$ or $Q(x)$ is true then
    either it is not the case that $\sim P(x)$ is true for all $x$ (which means $P(x)$  is true for some $x$) or $Q(x)$ is true for some $x$.

Note:

  • De Morgan's law is applicable in first order logic and is quite useful: $$\forall(x)(P(x)) \equiv \neg \exists (x)(\neg P(x))$$
  • This is a logical reasoning statement which means if $P(x)$ is true for all $x$, then there can never exist an $x$ for which $P(x)$ is not true. This formula is quite useful in proving validity of many statements as is its converse given below: $$\exists(x)(P(x)) \equiv \neg \forall (x)(\neg P(x))$$

Correct Answer: $A$

edited by
27 votes
27 votes

$A \implies B$ in this implication we can say this is false, if we can show a situation where A is true but at the same time B is false.

In the 4th case : $(\exists (x)) (P(x) \vee Q(x)) \implies \sim (\forall (x)) P(x) \vee (\exists (x)) Q(x)$

To check validity we do the following : 

1st approach:

  • Assume LHS as true or (1) based on some condition.
  • Then try to make RHS false (0) on the same set of conditions as above.

Or,

2nd approach:

  • Assume RHS as false (0) and try to make LHS as true (1) on some common conditions.

if we can show anyone one of the above situation exists. Then implication 4 is false.

Using second approach:

in RHS assume all $Q(x)$ are false (0) and all $P(x)$ are true (1) such that RHS becomes false (0).

Based on these above condition if we look on the left hand side, we find that LHS side is true (1) since all $P(x)$ are true.

edited by
3 votes
3 votes

For brevity, I will write $P(x)$ as $P_x$

Let the domain of $x = \{1, 2\}$

Option A:

$(\forall x P(x) \lor \forall x Q(x)) \rightarrow \forall x (P(x) \lor Q(x))$

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

$=(P_1P_2 + Q_1Q_2) \rightarrow (P_1P_2 + Q_1Q_2 + P_1Q_2 + P_2Q_1)$

$=(P_1P_2 + Q_1Q_2)’ + (P_1P_2 + Q_1Q_2) + (P_1Q_2 + P_2Q_1)$

$=true$

$\therefore$ valid


Option B:

$(\exists x P(x) \land \exists x Q(x)) \rightarrow \exists x (P(x) \land Q(x))$

$=\{(P_1 + P_2)(Q_1 + Q_2)\} \rightarrow (P_1Q_1 + P_2Q_2)$

$=\{(P_1 + P_2)(Q_1 + Q_2)\}’ + (P_1Q_1 + P_2Q_2)$

$=P_1’P_2’ + Q_1’Q_2’ + P_1Q_1 + P_2Q_2$

$\therefore$ NOT valid


Option C:

$\forall x (P(x) \lor Q(x)) \rightarrow (\forall x P(x) \lor \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)$

$= P_1’Q_1’ + P_2’Q_2’ + P_1P_2 + Q_1Q_2$

$\therefore$ NOT valid


Option D:

$\exists x (P(x) \lor Q(x)) \rightarrow \neg (\forall x P(x) \lor \exists x Q(x))$

$=\exists x (P(x) \lor Q(x)) \rightarrow (\exists x \neg P(x) \land \forall x \neg Q(x))$

$= \{(P_1 + Q_1)(P_2 + Q_2)\} \rightarrow (P_1’ + P_2’)(Q_1’Q_2’)$

$= P_1’Q_1’ + P_2’Q_2’ + (P_1’ + P_2’)(Q_1’Q_2’)$

$=P_1’Q_1’ + P_2’Q_2’$

$\therefore$ NOT valid

 

1 votes
1 votes

A. option is valid because $(\forall (x)) P(x) \vee (\forall(x))Q(x) \implies (\forall (x)) (P(x) \vee Q(x))$

LHS means that either for all values of x P(x) is true OR for all values of x Q(x) is true. On the RHS it may so happen that for some values of x P(x) is true and for the rest of the values Q(x) is true. Still then the whole of the RHS will be true as well as we can see that for the condition for which the LHS is true i.e., either for the whole of x P(x) is true or for whole of x Q(x) is true RHS is true . so we can say that $LHS \implies RHS$. so, A is valid

B. $(\exists (x)) P(x) \wedge (\exists (x))Q(x) \implies (\exists (x)) (P(x) \wedge Q(x))$

LHS means that if for even 1 value of x P(x) is true then $(\exists (x)) P(x) $ is true similar case can be considered for $(\exists (x))Q(x)$. But on RHS it says that there must exist at least one value of x such that both P(x) and Q(x) are true. so for all the true values of LHS RHS will not be true so not valid

C. $(\forall (x)) (P(x) \vee Q(x)) \implies (\forall (x)) P(x) \vee (\forall (x)) Q(x)$

On LHS it says that for all values of x (x is bounded by both P(x) and Q(x)) either P(x) is true or Q(x) is true. RHS says that for all the values of x either P(x) is true or Q(x) is true. Clearly you cannot replace LHS with RHS because it need not be the case in LHS that for all values of x P(x) is true or for all values of x Q(x) is true so not valid.

D.$(\exists (x)) (P(x) \vee Q(x)) \implies \sim (\forall (x)) P(x) \vee (\exists (x)) Q(x)$

For this you can see that on the LHS P(x) is true when for all values of x P(x) is true but on RHS you will see that for the above condition RHS will give false value so it is not valid 

Answer:

Related questions

24 votes
24 votes
4 answers
2
Kathleen asked Sep 13, 2014
9,918 views
Which of the following is/are a tautology?$a \vee b \to b \wedge c$$a \wedge b \to b \vee c$$a \vee b \to \left(b \to c \right)$$a \to b \to \left(b \to c \right)$