GATE 2008 | Question 21

Question

I have been trying to solve the question GATE CSE 2008 Question.

Are the following two representations logically equivalent ?

1. $\beta \rightarrow (\exists x, \alpha (x))$
2. $\exists x, \beta \rightarrow \alpha (x)$

Answer 1

I guess Yes,

we can write the $2^{nd} $  expression as,

$\exists_{x}(\beta \rightarrow \alpha (x))$

$\exists_{x}(\bar{\beta} + \alpha (x))$

$\exists_{x}\bar{\beta} + \exists_{x}(\alpha (x))$

As $\beta$ is not bounded Variable.

$\bar{\beta} + \exists_{x}(\alpha (x))$

$\beta \rightarrow (\exists_{x},\alpha (x))$

Which is the $1^{st}$ expression.

So same.

Answer 2

To solve this easily, let’s assume there are 2 elements in the domain of $x$

i.e., $D_x = \{x_0, x_1\}$

1. $[β \rightarrow (\exists x, α(x))]$
   $=β \rightarrow (α(x_0) + α(x_1))$
   $=β’ + α(x_0) + α(x_1)$
    
2. $[\exists x, β \rightarrow α(x)]$
   $=(β \rightarrow α(x_0)) + (β \rightarrow α(x_1))$
   $=(β’ + α(x_0)) + (β’+ α(x_1)$
   $=β’ + α(x_0) + α(x_1)$

 

(1.) and (2.) are Logically Equivalent.

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

---

@strawberry-jam  : can you plz show how to convert following FOL to propositional form

$1. \forall x (P(x) \rightarrow \exists y Q(y,x))$

$2. \forall x (Q(f(x),x) \rightarrow Q(x,x))$

$3. \forall x \forall y (Q(x,y) \rightarrow P(x))$

$4. \forall x \exists y (Q(x,y) \vee Q(y,x))$

 

---

Let domain of $x = \{x_1, x_2\}$ and $y=\{y1,y2\}$

1. $\forall x(P(x) \rightarrow \exists y Q(y,x)) = \forall x(\neg P(x) \lor \exists Q(y,x)) $

$=[\neg P(x_1) \lor \{Q(y_1, x_1) \lor Q(y_2, x_1)\}] \land [\neg P(x_2) \lor \{Q(y_1, x_2) \lor Q(y_2, x_2)\}]$
 

2. $\forall x(Q(f(x),x) \rightarrow Q(x,x))$

$= \{Q(f(x_1),x_1) \rightarrow Q(x_1,x_1)\} \land \{ Q(f(x_2),x_2) \rightarrow Q(x_2,x_2) \}$

3. $\forall x \forall y (Q(x,y) \rightarrow P(x))= \forall x \forall y (\neg Q(x,y) \lor P(x))$

$= \{  \neg Q(x_1, y_1) \lor P(x_1) \} \land \{  \neg Q(x_1, y_2) \lor P(x_1) \} \land \{  \neg Q(x_2, y_1) \lor P(x_2) \} \land \{  \neg Q(x_2, y_2) \lor P(x_2) \}$
 

4. $\forall x \exists y (Q(x,y) \lor Q(y,x))$

$= [\{ Q(x_1, y_1) \lor Q(y_1, x_1)\} \lor \{ Q(x_1, y_2) \lor Q(y_2, x_1)\}] \land [\{ Q(x_2, y_1) \lor Q(y_1, x_2)\} \lor \{ Q(x_2, y_2) \lor Q(y_2, x_2)\}]$

---

Thanks,

I was trying to solve questions on FOL equivalence of 2 statements involving such combination of $\forall$ and $\exists$.  Trying to convert each statment from FOL to PL and then comparing them.

If possible , Could you also explain this with an example which has both   $\forall$ and $\exists$

Answer 3

TRUE