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

To solve such questions consider domain to be (x1,x2)

keep in mind these two rules :

1. ∀x is “ANDing” of all values in the domain because ∀x is only true if predicate is true for all the values of domain
2. ∃x is “ORing” of all values in the domain because ∃x  is true if predicate is true for atleast 1 value of the domain

 

Option	L.H.S	R.H.S	L.H.S==R.H.S
A	∀x(p(x)∨W) (p(x1)∨W)^(p(x2)∨W) =(p1+w)(p2+w) =p1p2+p1w+p2w+w =p1p2+w(p1+p2+1) =p1p2+w	∀x(px)∨W =(p(x1)^p(x2))∨W = p1p2+w	True
B	∃x(p(x)∧W) =p1w+p2w =w(p1+p2)	∃xp(x)∧W =(p1+p2)w	True
C	∀x(p(x)→W) =(p1→W)p2(→w) =(p1’+w)(p2’+w) =p1’p2’+p1’w+p2’w+w =p1’p2’+w(p1’+p2’+1) =p1’p2’+w	∀xp(x)→W =(p1p2→w) =(p1p2)’+w =p1’+p2’+w	False
D	∃x(p(x)→W) =(p1→W)+(p2→W) =p1’+w+p2’+w =p1’+p2’+w	∀xp(x)→W =p1p2→W =(p1p2)’+w =p1’+p2’+w	True

So in only option C L.H.S !=R.H.S

Answer (C)

Answer 2

Option C is logically invalid. Hence option C is correct

Answer 3

Let domain of $x = \{x_1, x_2\}$

Option A:

$[\forall x (P(x) \lor W) \equiv \forall x P(x) \lor W]$

$LHS: \forall x (P(x) \lor W) =(P(x_1) + W) * (P(x_2) + W) =P(x_1)P(x_2) + W$

$ RHS: \forall x P(x) \lor W = P(x_1)*P(x_2) + W$

$\therefore LHS \equiv RHS$

 

Option B:

$[\exists x (P(x) \land W) \equiv \exists x P(x) \land W ]$

$LHS: \exists x (P(x) \land W) = (P(x_1).W)+(P(x_2).W) = \{P(x_1)+P(x_2)\}*W$

$RHS: \exists x P(x) \land W = \{P(x_1) + P(x_2)\} * W$

$\therefore LHS \equiv RHS$

 

Option C:

$[\forall x (P(x) \rightarrow W) \equiv \forall x P(x) \rightarrow W]$

$LHS: \forall x (P(x) \rightarrow W) = \{(P(x_1) \rightarrow W)*(P(x_2) \rightarrow W)\} = (P’(x_1) + W)(P’(x_2) + W) = P’(x_1)P’(x_2) + W$

$RHS: \forall x P(x) \rightarrow W = (P(x_1)P(x_2)) \rightarrow W = (P(x_1)P(x_2)’ + W = P’(x_1) + P’(x_2) + W$

$\therefore LHS \not \equiv RHS$

 

Option D:

$[\exists x (P(x) \rightarrow W) \equiv \forall x P(x) \rightarrow W]$

$LHS: \exists x (P(x) \rightarrow W) = \{(P(x_1) \rightarrow W) + (P(x_2) \rightarrow W)\} = P’(x_1) + W + P’(x_2) + W = P’(x_1) + P’(x_2) + W$

$RHS: \forall x P(x) \rightarrow W = (P(x_1)*P(x_2)) \rightarrow W = (P(x_1)P(x_2))’ + W =  P’(x_1) + P’(x_2) + W$

$\therefore LHS \equiv RHS$

Comments

Required Information:

FOL conversion to Propositional Form

$\forall xP(x) \equiv \{P(x_1) \land P(x_2) \land … \}, x_i \in \text{domain(}x)$

i.e., the conjunction of all propositions

 

$\exists xP(x) \equiv \{P(x_1) \lor P(x_2) \lor … \}, x_i \in \text{domain(}x)$

i.e., the disjunction of all propositions

Answer 4

option C correct