GATE IT 2008 | Question: 21

Question

Which of the following first order formulae is logically valid? Here $\alpha(x)$ is a first order formula with $x$ as a free variable, and $\beta$ is a first order formula with no free variable.

• A. $[\beta \rightarrow (\exists x, \alpha(x))] \rightarrow [\forall x, \beta \rightarrow \alpha(x)]$
• B. $[\exists x, \beta \rightarrow \alpha(x)] \rightarrow [\beta \rightarrow (\forall x, \alpha(x))]$
• C. $[(\exists x, \alpha(x)) \rightarrow \beta] \rightarrow [\forall x, \alpha(x) \rightarrow \beta]$
• D. $[(\forall x, \alpha(x)) \rightarrow \beta] \rightarrow [\forall x, \alpha(x) \rightarrow \beta]$

Comments

[β→(∃x,α(x))] →[∀x,β→α(x)]

In LHS we are considering α(x) individually but in RHS we are using ∀x.

So how we will compare both LHS and RHS?

Like if Beta is true and α(x) is false then for that particular case LHS will be false but RHS will be false always.

Answer 1

• A.  $[\beta \to (\exists x, \alpha(x))] \to [\forall x, \beta \to \alpha(x)]$
  LHS: If $\beta$ (some condition) is true, then there exists an $x$ for which $\alpha(x)$ is true.  
  RHS: For all $x$, if $\beta$ is true then $\alpha(x)$ is true. This is same as saying if $\beta$ is true then for all $x$,
  $\alpha(x)$ is true. $(\beta \implies \forall x, \alpha(x))$.
  So, $$\text{RHS} \implies \text {LHS} \text{ and } \text{LHS} \not\Longrightarrow  \text{RHS}.$$
• B. $[\exists x, \beta \to \alpha(x)] \to [\beta \to (\forall x, \alpha(x))]$
  LHS: There exists an $x$ such that if $\beta$ is true then $\alpha(x)$ is true. 
  RHS: If $\beta$ is true then for all $x, \alpha(x)$ is true.  
  So, $$\text{RHS} \implies \text {LHS} \text{ and }  \text{LHS} \not\Longrightarrow  \text{RHS}.$$
• C. $[(\exists x, \alpha(x)) \to \beta] \to [\forall x, \alpha(x) \to \beta]$
  LHS: If there is an $x$ such that $\alpha(x)$ is true, then $\beta$ is true. 
  RHS: For all $x$, if $\alpha(x)$ is true, then $\beta$ is true. 
  Here, both LHS and RHS are in fact same as $\beta$ is a formula which is independent of $x$. (if $\beta$ is true for one $x$, it is true for every $x$ and vice versa). 
  So, $$\text{RHS} \implies \text {LHS} \text{ and }  \text{LHS} \implies  \text{RHS}.$$
• D. $[(\forall x, \alpha(x)) \to \beta] \to [\forall x, \alpha(x) \to \beta]$
  LHS: If $\alpha(x)$ is true for every $x$, then $\beta$ is true.
  RHS: For every $x$, if $\alpha(x)$ is true then $\beta$ is true. 
  So, $$\text{RHS} \implies \text {LHS}  \text{ and }  \text{LHS} \not\Longrightarrow  \text{RHS}.$$

So, answer here is option C.

Any of options $A$, $B$, or $D$ could be valid if their implication is reversed. For option C, LHS, and RHS being equivalent, even if the implication is reversed (or changed to double implies) it remains valid. 

Comments

Thanks a lot @Arjun . Great contribution. Nice explanation.

---

@Arjun Sir,

In option D, if LHS is more restrictive than RHS so LHS should imply RHS, isnt it? Because, (More restrictive condition)-->(Less restrictive condition)  .

Ex. (conflict serializable)-->(view serializable)

In option D, You have written RHS(less restrictive)-->LHS(more restrictive). Shouldn’t it be the other way around?

---

GO Volume 1 PDF 2021 has printed Not implication as implication

Answer 2

Usually operator , (comma) is used to replace braces in logical expressions

Let s consider the domain of x as {1,2}.

We will invalidate options one by one by invalidating the given conditional.

(A) $\{  \beta \rightarrow (\exists x , \alpha(x) ) \}  \rightarrow \{ \forall x , \beta \rightarrow \alpha(x) \}$

  The above expression can be re-written as :

  $\{  \beta \rightarrow (\exists x ( \alpha(x) ) ) \}  \rightarrow \{ \forall x ( \beta \rightarrow \alpha(x) ) \}$

Notice comma has been replaced by ()

Now we don't know what variable input does $\beta$ take so let us assume it  to be a simple propositional variable.

The L.H.S. can be re-written considering domain of x as {1,2} as

$\beta \rightarrow (\alpha_{1}+ \alpha_{2})$

This can be further written as : $\sim\beta + (\alpha_{1}+ \alpha_{2})$

R.H.S. can be re-written as : $(\beta \rightarrow \alpha_{1}) \land (\beta \rightarrow \alpha_{2})$

which evaluates as $\sim\beta + \alpha_{1}.\alpha_{2}$

Now we can clearly see that L.H.S $\rightarrow$ R.H.S. will be false if $\beta$ is true, $\alpha_{1}$ is true and $\alpha_{2}$ is false. Implication became invalid so we eliminate this option.

(B) $\{ \exists x , \beta \rightarrow \alpha(x) \} \rightarrow \{ \beta \rightarrow (\forall x, \alpha(x)) \}$

  after replacing comma it becomes

 $\{ \exists x ( \beta \rightarrow \alpha(x) ) \} \rightarrow \{ \beta \rightarrow (\forall x (\alpha(x))) \}$

Now re-writing L.H.S. and R.H.S. considering domain of x

L.H.S.  : $(\beta \rightarrow \alpha_{1})+(\beta \rightarrow \alpha_{2})$ and this evaluates to

$\sim\beta + \alpha_{1} + \alpha_{2}$

R.H.S. : $\beta \rightarrow (\alpha_{1}.\alpha_{2})$

and this evaluates to $\sim \beta + \alpha_{1}.\alpha_{2}$

This implication can also become false, following same reasoning from option (A).

(C) $\{ (\exists x , \alpha(x) ) \rightarrow \beta \} \rightarrow \{ \forall x, \alpha(x) \rightarrow \beta \}$

After replacing comma it becomes

$\{ (\exists x ( \alpha(x)) ) \rightarrow \beta \} \rightarrow \{ \forall x  (\alpha(x) \rightarrow \beta) \}$

L.H.S. : $(\alpha_{1} + \alpha_{2}) \rightarrow \beta$

which evaluates to

$\sim\alpha_{1}.\sim\alpha_{2} + \beta$

R.H.S. : $(\alpha_{1}\rightarrow\beta).(\alpha_{2}\rightarrow\beta)$

which evaluates to $\sim\alpha_{1}.\sim\alpha_{2} + \beta$

which is same as L.H.S. and hence this implication is valid.

(D) $\{ (\forall x, \alpha(x)) \rightarrow \beta \} \rightarrow \{ \forall x, \alpha(x) \rightarrow  \beta \}$

after replacing comma it becomes

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

Considering domain of x to be {1,2} we re-write L.H.S. and R.H.S.

L.H.S. : $(\alpha_{1}.\alpha_{2})\rightarrow \beta$

and this evaluates to

$\sim \alpha_{1} + \sim \alpha_{2} + \beta$

R.H.S. : $(\alpha_{1}\rightarrow \beta)(\alpha_{2}\rightarrow\beta)$

Which evaluates to $\sim\alpha_{1}.\sim\alpha_{2}+\beta$

Now this implication can be set false, when $\sim\alpha_{1} $ is true , $\beta$ is false and $\sim\alpha_{2}$ is false.

Hence, this implication is invalid.

Answer (c)

Comments

best explaination

---

Well explained.

---

Simple and crystal clear!

Answer 3

[(∃x,α(x))→β]→[∀x,α(x)→β]

LHS => (∃x,α(x))→β ))

              (~∃x,α(x)) V β -> (∀x, ~α(x)) V β  )  -> (∀x, (~α(x) V β)) (I can change scope of  ∀x as B do not have x as  free variable in it.

(∀x, (α(x) -> β)) Proved !

C is correct

Comments

@abhay_nanda, if you do the same then you will get ∃x,α(x))→β which is different from what RHS option D has shown...

---

nice approach akash sir

---

if this is true   (∀x, ~α(x)) V β  )  -> (∀x, (~α(x) V β))   according to your soln

then option D is also correct ?!

Answer 4

Additional details added to Arjun's answer.

 

Option A: $[β→(∃x,α(x))]→[∀x,β→α(x)]$

$LHS$: If $\beta$ then there exists an x, such that $\alpha(x)$ is true.
(If exam is held, then there exists a student, such that the student takes the exam)

$RHS$: For all x, if $\beta$ then $\alpha(x)$ is true.
(For all students, if exam is held, then they take the exam)

You can see the RHS is kinda like the superset of LHS. LHS clearly doesn't imply RHS, hence this option is incorrect.

---

Option B: $[∃x,β→α(x)]→[β→(∀x,α(x))]$

$LHS$: There exists an x such that if $\beta$, then $\alpha(x)$ is true.
(There exists a student, such that if exam is held, then the student takes the exam)

$RHS$: If $\beta$ then for all x, $\alpha(x)$ is true
(If exam is held, then for all students it is true that they take the exam)

For the same reason as above, this option is also incorrect.

---

Option C: $[(∃x,α(x))→β]→[∀x,α(x)→β]$

$LHS$: If there exists an x, such that $\alpha(x)$ is true, then  $\beta$.
(If there exists a student, such that it is true they take the exam, then the exam is held)

$RHS$: For all x, if $\alpha(x)$ is true the $\beta$.
(For all students, if they take the exam, then the exam is held)

Correct!

---

Option D: $[(∀x,α(x))→β]→[∀x,α(x)→β]$

$LHS$: If for all x, $\alpha(x)$ is true, then $\beta$.
(If for all students, they take the exam, then the exam is held.)

$RHS$: For all x, if $\alpha(x)$ is true, then $\beta$.
(For all students, if they take the exam then the exam is held)

The LHS does NOT imply RHS. In LHS if a student takes the exam it is held for him/her personally. But in RHS is all the students take the exam, only then it is considered held.

This option is incorrect!

---

 

 

Now, some background knowledge:

1

The comma i.e. "," operator after a quantifier means that the quantifier applies to the rest of the statement. Hence, in essence:

$[∀x,α(x)→β ]$ is equivalent to  $[∀x(α(x)→β)]$

This means you can replace the comma by parentheses.

Also, full stop/dot/period i.e. "." can be used in place of comma.

 

2

Notice the difference between the interpretations:

$[∀x,β→α(x)]$ => For all x... // Here only $\beta$ will be in range of "if"

$[(∀x,β)→α(x)]$ => If for all x... //Here the quantifier is also in the range of "if"

Comments

Very good answer!