GATE CSE 2020 | Question: 39

Question

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

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

• A. $\forall x (p(x) \vee W) \equiv \forall x \: ( px) \vee W$
• B. $\exists x(p(x) \wedge W) \equiv \exists x \: p(x) \wedge W$
• C. $\forall x(p(x) \rightarrow W) \equiv \forall x \: p(x) \rightarrow W$
• D. $\exists x(p(x) \rightarrow W) \equiv \forall x \:  p(x) \rightarrow W$

Comments

@Suraj Reddy, For null quantification rules, $W$ can have free variables in it, but $W$ should not have a free variable $x.$ The same proof will work, but one statement we will have to add (or implicitly keep in the back of our mind) before the proof is “for any value-assignment to all the free variables of $W$, either $W$ will be True or $W$ will be false”. 

If $W$ has some free variable(s), say $y$, then LHS & RHS both will be Predicates over variable $y$, not propositions, But that is fine because we only find equivalence of LHS & RHS.  

See THIS example. See THIS also. 

---

@Deepak Poonia So, either $W$ is a quantified predicate formula, or $W$ has some other free variable y but not x where we can think(of the option A) as $\exists y \forall x(p(x)\vee W)  \equiv \exists y (\forall xp(x)\vee W)$. Just finding equivalence between predicates doesn’t make sense.

---

@Suraj Reddy, I think the usefulness of predicate-equivalence comes during inference of one statement from a set of given statements. More about the usefulness of equivalence of predicates I will need to check. But the concept is what I have mentioned in the previous comments & in this lecture. 

Answer 1

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

Comments

Thanks @ shashin

---

@Ayush Upadhyaya, @Arjun Sir, @Lakshman Patel RJIT In option C, it must be $\forall x(\lnot P(X) \lor W) \equiv \forall x(\lnot P(X)) \lor W \equiv\lnot (\exists xP(x) )\lor W \equiv \exists x P(x) \rightarrow W$ which is !=RHS. That’s why Option C is not logically valid. It needs edit.

---

@Abhrajyoti00

That’s right what you have pointed out. The answer has been corrected.

Detailed Video Solution: https://www.youtube.com/watch?v=DinrKHKYFXY  

Answer 2

Option C is not logically valid

 

Comments

ramcharantej_24

sorry for late reply. I do not know which property but I am telling what am I thinking.

if p1.p2=true then p1+p2 will definitely be true so w(p1+p2)  will depend upon value of w so we can write

p1p2 + w + w(p1+p2) = p1p2+ w

Here w is main factor if w is false then w(p1p2) will be false. But if w is true then value of w(p1+p2) still be redundant because in both equation there is w with ORing condition so overall value would be true.

---

Navneet Singh Tomar you are proving B->A false by making T->F.that’s perfectly OK.But here we’ve to prove A->B false.we can do that by making T->F but that’s can’t be done here.

If B->A is false then how can u say A->B is false ??

---

@mrinmoyh Bro to prove logically valid both sides should be true that is A->B as well as B->A should be true.

A->B= True

B->A= False

So overall it is false hence not logically valid

Answer 3

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.

Answer 4

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

Comments

see i totally understand how and what you are trying to prove, but i have a doubt

 

in explanation of option c you took for-all and distributed it within the bracket after converting implies to boolean logic

and according to distributive law

→ for-all is distributive over conjunction, not disjunction

→ there-exists is distributive over disjunction, not conjunction

 

it can be either of two cases

case 1 ) → as w has no free occurrence of x so it becomes constant and then for-all is able to distribute over disjunction

or

case 2 ) → i missed something, i would appreciate if you could solve my doubt