retagged by
16,920 views
42 votes
42 votes

Which one of the following predicate formulae is NOT logically valid?

Note that $W$ is a predicate formula without any free occurrence of $x$.

  1. $\forall x (p(x) \vee W) \equiv \forall x \: ( px) \vee W$
  2. $\exists x(p(x) \wedge W) \equiv \exists x \: p(x) \wedge W$
  3. $\forall x(p(x) \rightarrow W) \equiv \forall x \: p(x) \rightarrow W$
  4. $\exists x(p(x) \rightarrow W) \equiv \forall x \:  p(x) \rightarrow W$
retagged by

9 Answers

Best answer
32 votes
32 votes

(A)Let's consider two cases.

W-True.This makes both LHS and RHS True.
W-False.The value of LHS depends upon the truth value of $\forall$xP(x). Same will be the case for RHS.
Hence LHS =RHS.

(B)Using analogy in (A), we can prove that this is also valid.
W-True.LHS=RHS=True
W-False.LHS=RHS=False always.

(C)$\forall x(P(x) \rightarrow W) \equiv \forall xP(x) \rightarrow W$

LHS can be re-written as $\forall x(\lnot P(X) \lor W) \equiv \exists xP(x) \rightarrow W$

(C) is not logically valid.

(D)$\exists x(P(x) \rightarrow W) \equiv \exists x(\lnot P(X) \lor W) $

Using Demorgan law for quantifiers we can again rewrite it as:

$\lnot \forall x P(x) \lor W \equiv \forall x P(x) \rightarrow W$

Option (D) is valid.

edited by
40 votes
40 votes

Option C is not logically valid

 

9 votes
9 votes

Option A and B are pretty clear. They are logically valid.

Option C and D can be checked with a simple truth table construction taking two values x1 and x2, i.e. p(x1) and p(x2)

Note:-

Column 3 below indicates L.H.S of option C.

Column 4 below indicates L.H.S of option D.

Column 5 below indicates R.H.S of option C and D.

p(x1) p(x2) (p(x1)->W) $\Lambda$ (p(x2)->W) (p(x1)->W) $\vee$ (p(x2)->W) (p(x1) $\Lambda$ p(x2))->W
T T W W W
T F W T T
F T W T T
F F T T T

 

You can clearly see the 3rd column is not matching with the 5th column.  So option C is not valid which is the required answer.

edited by
6 votes
6 votes

Laws for Manipulating Quantifiers: There is rule analogous to DeMorgan's law that allows us to move a NOT operator through an expression containing a quantifier.

  • $\neg (\forall x\: P(x)) \equiv \neg \forall x \neg P(x) \equiv \exists x \neg P(x)$
  • $\neg (\exists x\: P(x)) \equiv \neg \exists x \neg P(x) \equiv \forall x \neg P(x)$

Domain $: p_{1},p_{2}$

A.$\forall x (p(x)\vee W)\equiv \forall x\:p(x) \vee W$

$\textsf{LHS}:\forall x (p(x)\vee W) \equiv \forall x \:p(x)\vee W \equiv p_{1}p_{2}+W$

$\textsf{RHS}:\forall x \:p(x)\vee W \equiv p_{1}p_{2}+W$

Here, $\textsf{LHS} = \textsf{RHS}$

So, option $(A)$ is Valid.

B.$\exists x (p(x)\wedge W)\equiv \exists  x\:p(x) \wedge W$

$\textsf{LHS}:\exists x (p(x)\wedge W) \equiv (p_{1} + p_{2})\cdot W $

$\textsf{RHS}:\exists  x\:p(x) \wedge W \equiv (p_{1} + p_{2})\cdot W $

Here, $\textsf{LHS} = \textsf{RHS}$

So, option $(B)$ is Valid.

C.$\forall x (p(x)\rightarrow W)\equiv \forall x\:p(x) \rightarrow W$

$\textsf{LHS}:\forall x (p(x)\rightarrow W) \equiv \forall x(\neg p(x) \vee W) \equiv \forall x\:\neg p(x)  \vee W \equiv \overline{p_{1}}\overline{p_{2}} + W \equiv \overline{(p_{1} + p_{2})} + W$

$\textsf{RHS}:\forall x\:p(x) \rightarrow W \equiv \neg [\forall x\: p(x)] \vee W = \neg \forall x \neg p(x) \vee W \equiv \exists x \neg p(x)\vee W \equiv \overline{p_{1}} + \overline{{p_{2}}} + W \equiv \overline{(p_{1}\cdot p_{2})}+ W$

Here, $\textsf{LHS} \neq  \textsf{RHS}$

So, option $(C)$ is NOT Valid.

D.$\exists x (p(x)\rightarrow W)\equiv \forall x\:p(x) \rightarrow W$

$\textsf{LHS}:\exists x (p(x)\rightarrow W) \equiv \exists x (\neg p(x)\vee W) \equiv \exists x \neg p(x)\vee W \equiv \overline{p_{1}} + \overline{p_{2}} + W$

$\textsf{RHS}:\forall x\:p(x) \rightarrow W \equiv \neg (\forall x\: p(x)) \vee W \equiv \neg \forall x \neg p(x) \vee W \equiv \exists x \neg p(x) \vee W \equiv \overline{p_{1}} + \overline{p_{2}} + W$

Here, $\textsf{LHS} = \textsf{RHS}$

So, option $(D)$ is Valid.

So, the correct answer is $(C).$

edited by
Answer:

Related questions

9 votes
9 votes
3 answers
4
Arjun asked Feb 12, 2020
5,731 views
If $P = 3$, $R = 27$, $T = 243$, then $Q + S =$ ________$40$$80$$90$$110$