GATE CSE 2003 | Question: 32

Question

Which of the following is a valid first order formula? (Here \(\alpha\) and \(\beta\) are first order formulae with $x$ as their only free variable)

• A. $((∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α ⇒ β]$
• B. $(∀x)[α] ⇒ (∃x)[α ∧ β]$
• C. $((∀x)[α ∨ β] ⇒ (∃x)[α]) ⇒ (∀x)[α]$
• D. $(∀x)[α ⇒ β] ⇒ (((∀x)[α]) ⇒ (∀x)[β])$

Comments

https://www.youtube.com/live/wzVFO4hyVfo?si=jlZqU9mS20ktzQs6&t=7542

---

Important things about this Question 

Here α and β are first order formulae with x as their only free variable

 This statement actually means:

$\alpha$ is not a predicate symbol.

$\alpha$ is a formula.

The only variable that may occur free inside $\alpha$ is $x$.

Similarly:

$\beta$ is also a formula,

whose only possible free variable is $x$.

Explain with examples 

Example 1: $\alpha = P(x)$ // here α is formula not predicate symbol

$Free Variable (\alpha) = \{x\}$

$\alpha$ is allowed here 

Example 2 : $\alpha = P(x) \land \exists y Q(x,y)$ // here α is formula not predicate symbol

here , $x$ is free , $y$ is bound

So $Free Variable (\alpha) = \{x\}$

$\alpha$ is allowed here 

Example 3: $\alpha = P(x, y)$ // here α is formula not predicate symbol

Now, both $x$ and $y$ are free.

$\alpha$ is not allowed here

---

in option (a) Antecedent part one closing bracket ')' is missing. please correct it.

Answer 1

deepak sir's explantion   https://www.youtube.com/live/wzVFO4hyVfo?si=ePStRdhWmrtnl4a6&t=7547

Answer 2

Option (D) (∀x)[α ⇒ β] ⇒ (((∀x)[α]) ⇒ (∀x)[β]) is valid.

So,(D) is ans.