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

Brackets are not matching in (D) . pls fix

---

i  got the answer. but the thing is that how to come up with such example within 3 minutes in Exam ?? Is there any other method to check it ? If i am not able to come with some example ????

---

for 3)

in RHS Assume α is not true for all x, then in LHS first part become false making 2nd part of the RHS as true hence overall LHS become true

T->F

hence false

kindly check this??

Answer 1

For faster problem solving, try this method/hack:

Let Universe $=\{1, 2\}$

Option A: $(\forall x α_x \rightarrow \forall x β_x) \rightarrow \forall x (α_x \rightarrow β_x)$

$=[α_1α_2 \rightarrow β_1β_2] \rightarrow \{(α_1 \rightarrow β_1)(α_2 \rightarrow β_2)\}$

$= [(α_1α_2)’ + β_1β_2] \rightarrow (α_1’ + β_1)(α_2’ +  β_2) = (α_1α_2)(β_1β_2)’ + (α_1’ + β_1)(α_2’ +  β_2)$

$=$ contingengy

 

Option B: $\forall x α_x \rightarrow \exists x (α_x \land β_x)$

$= (α_1α_2)’ + (α_1β_1) + (α_2β_2) = $ valid

 

Option C: $\forall x (α_x \lor β_x) \rightarrow (\exists x α_x \rightarrow \forall x α_x)$

$= [(α_1 +  β_1)(α_2 +  β_2)]’ + (α_1 + α_1)’  +  α_1α_2) = $ contingency

 

Option D: $\forall x (α_x \rightarrow β_x) \rightarrow (\forall x α_x \rightarrow \forall x β_x)$

$= [(α_1’ + β_1)(α_2’ + β_2)]’ + (α_1α_2)’ + β_1β_2 = $ contingengy

 

How is valid/contingency magically declared? Well, there are 3 ways:

1. Solve till completion (not recommended for GATE problems)
    
2. Try out all combinations of truth values, till at least one $false$ (only if you have too much time to spare)
    
3. For 2 formula systems $\alpha(x), \beta(x)$, after changing FOL to propositional form,
   
   put $(α_1, α_2, β_1, β_2) = (1, 0, 0, 1)$ respectively
   
   This will give the proper result in most cases.
   
   If any ambiguity arises, then try option 2(above)

---

NOTE:

This is not an official method. I found this method out myself after solving loads of GATE questions.

I'm yet to encounter a question which is not solvable by this method, but I'm sure such a problem exists somewhere, hence the caveat 'most cases.’

Don't believe me, try it out yourself. You're welcome!

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 2

The correct option is D (∀x)[α⇒β]⇒((∀x)[α]⇒(∀x)[β])
 

(∀x)[α⇒β]⇒((∀x)[α]⇒∀(x)[β])
is a logical equivalence and therefore 

a valid first order formula.

Answer 3

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

So,(D) is ans.