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

(D) is the answer.

• A. Let $X = \{3,6,9,8\}$. Let $α$ denote multiple of $3$ and $β$ denote multiple of $4. (∀x)[α]$ becomes false as $8$ is not a multiple of $3$, and so $(∀x)[α] ⇒ (∀x)[β]$ becomes TRUE. Now, this won't imply $(∀x)[α ⇒ β]$ as multiple of $3$ doesn't imply multiple of $4$ for $3, 6$ or $9$.
   
• B. Let $X = \{3,6,9\}$. Let $α$ denote multiple of $3$ and $β$ denote multiple of $4$. Now LHS is TRUE but RHS is false as none of the $x$ in $X$, is a multiple of $4$.
   
• C. Let $X = \{3,6,9,7\}$.  Let $α$ denote multiple of $3$ and $β$ denote multiple of $4$. Now  $(∀x)[α ∨ β]$ becomes false and hence LHS $= ((∀x)[α ∨ β] ⇒ (∃x)[α])$ becomes true. But RHS is false as $7$ is not a multiple of $3$.
   
• D. This is valid. LHS is saying that if $α$ is holding for any $x$, then $β$ also holds for that $x$. RHS is saying if $α$ is holding for all $x$, then $β$ also holds for all $x$. Clearly LHS $\implies$ RHS (but RHS does not imply LHS).
  For example, let $X = \{4, 8, 12\}, α$ denote multiple of $2$ and $β$ denote multiple of $4$. LHS $= (∀x)[α ⇒ β],$ is TRUE. RHS is also true. If we add '$3$' to $X$, then LHS is true, first part of RHS becomes false and thus RHS also becomes TRUE. There is no way we can make LHS true and RHS false here. But if we add $2$ and $3$ to $X$, RHS will be true and LHS will be false. So, we can't say RHS implies LHS.

Comments

X is a free variable a free variable doesn't depend on any quantifier.....and in this ans x is assumed as a bounded variable

---

Ok I understood x is free variable of alpha but after applying quantifer is automatically become bounded variable

---

yeah, here the option C is correctly solved, in the PYQ solution video, instructor got the parenthesis wrong

Answer 2

@Arjun sir already provided the best answer for this but this is another way of solving this. Strategy behind these question is assume L.H.S as true and make R.H.S as false by some values for which L.H.S is true-

 

1)((∀x)[α]⇒(∀x)[β])⇒(∀x)[α⇒β]

Assume some values of x for α and β which makes LHS as true-

x	α	β
x1	T	F
x2	F	T

 

In LHS  (∀x)[α] is false for the assumed domain and same as (∀x)[β] is false for the assumed domain. Now we know that              F-> F = T makes LHS true.

In RHS [α⇒β] is false for x1 and true for x2. So for all x RHS will become false.

$\therefore$ T -> F = F (Not Valid)

 

2)(∀x)[α]⇒(∃x)[α∧β]

Assume some values of x for α and β which makes LHS as true-

x	α	β
x1	T	F
x2	T	F

 

In LHS  (∀x)[α] is true for the assumed domain which makes the whole LHS true.

In RHS [α$\wedge$β] is false for x1 as well as for x2. So in RHS there is no true value, which makes whole RHS as false.

$\therefore$ T -> F = F (Not Valid)

 

3)((∀x)[α∨β]⇒(∃x)[α])⇒(∀x)[α]

Assume some values of x for α and β which makes LHS as true-

x	α	β
x1	T	F
x2	F	T

 

In LHS  [α∨β] is true for the x1 as well as for x2 which makes (∀x)[α∨β] as true and (∃x)[α] is true for the assumed domain because of x1. Now we know that  T-> T = T makes LHS true.

In RHS  (∀x)[α] is false for the assumed domain which makes the whole RHS false.

$\therefore$ T -> F = F (Not Valid)

 

4)(∀x)[α⇒β]⇒(((∀x)[α])⇒(∀x)[β])

Assume some values of x for α and β which makes LHS as true-

x	α	β
x1	T	T
x2	F	T
x3	F	F

 

In LHS [α⇒β] is true for x1,x2 and x3. So for all x LHS will become true.

In RHS  (∀x)[α] is false for the assumed domain and same as (∀x)[β] is false for the assumed domain. Now we know that              F-> F = T makes RHS true.

$\therefore$ T-> T = T (Valid)

 

So correct answer is option D.

Comments

@Shubhgupta How did you decide for the fourth option that till what part will be LHS and RHS??

---

@abir_banerjee

with brackets. 

                                   $\color{cyan} \downarrow$             $\color{cyan} \downarrow$
$(\forall x)[\alpha \rightarrow \beta] \rightarrow(((\forall x)[\alpha]) \rightarrow (\forall x)\beta)$
                                $\color{red} \uparrow$                                      $\color{red} \uparrow$

 

---

Very neatly explained....

Answer 3

A)  $(∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α ⇒ β]$ 

For A the above sentence means that for all x if α is true then for all x  β should also be true. Here both α and β are bounded by different values of x. But on RHS α and β are bounded by the same value of X. so if even 1 value of α becomes false on the LHS side, the whole of expression $(∀x)[α]$ becomes false so regardless of the value of $(∀x)[β])$ the value of LHS is $TRUE$. So we can encounter a situation where α is True and β is false.  Here on LHS we are actually comparing the whole set. So, A is false

B) $(∀x)[α] ⇒ (∃x)[α ∧ β]$

Though whole of α may be true but that does not mean β will also be true so LHS does not imply RHS. so, B is false

C) $((∀x)[α ∨ β] ⇒ (∃x)[α]) ⇒ (∀x)[α]$

This one is clearly invalid because for every x if $α ∨ β$ is true so either α is true or β s true. It may so happen that there exists some values of α which are true but that does not mean all of α will be true because there can also be value of β which can be true.

D)$(∀x)[α ⇒ β] ⇒ (((∀x)[α]) ⇒ (∀x)[β])$

This one is $VALID$ because both α and β bound same value of x. On RHS α and β can bound same or different values of x .So we can say that $LHS\subseteq RHS $

Comments

BEST explanation

 

Answer 4

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

---

This disproves it bro

Answer 5

D. (∀x)[α ⇒ β] ⇒ (((∀x)[α]) ⇒ (∀x)[β])

(∀x)[~α $\vee$ β] ⇒ (~(∀x[α])) $\vee$  (∀x)[β])

(∀x)[~α $\vee$ β] ⇒ ∃ x(~α) V (∀x)[β]) which is TRUE.

 

Answer 6

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

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

a valid first order formula.