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

 

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

LHS

 (∃x,α(x))→β ))

 (~∃x,α(x)) V β)

(∀x, ~α(x)) V β  ) 

 (∀x, (~α(x) V β)) 

R.H.S

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

Proved So

L.H.S = R.H.S

C is correct Option