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

Hi arjun,

Just stuck over this question. See if you can help.

Page 46 of Discrete Mathematics & its Applications , Kenneth H. Rosen Seventh editions  Exercise question number 48 and 49 quotes as follows:

So by the above equivalences and since the gate question mentions that β has no free variable

A. [β→(∃x,α(x))]→[∀x,β→α(x)] should become [β→(∃x,α(x))]→[β→(∀x,α(x))]

B. [∃x,β→α(x)]→[β→(∀x,α(x))] should also become  [β→(∃x,α(x))]→[β→(∀x,α(x))]

 

What's your take on this?

---

yes, they both are same.

---

arjun sir,can you explain option D more

??i am finding  LHS and RHS same.i mean a(x) is true for every x and for every x,a(x) is true..is not the same thing??

---

and also i am not able to diff btw C & D

---

That is the issue with quantification. See this scenario,

For every person, if he works hard, company value increases. (Same as if any person works hard, company value increases).

If every person works hard, then company value increases.

So, the second one is more restrictive and this corresponds to LHS of D option and the first one corresponds to LHS of C option.

---

but sir what is the difference btw lhs and rhs of option D

---

in iption D

LHS ays if a (x) is true for all x then  b is true

RHS says if for any x a(x) is true then b is true

i think LHS -> RHS here

---

RHS of option D is same as LHS of option C. All due to the placement of "(". In English sentence this is like a pause and the whole meaning changes.

---

Your translations are correct. Now, try making LHS true and RHS false.

---

sir ,taking your example of if employee works hard,company values increases.

lhs of D says if all employees work hard then company value increases.

RHS says if any employee works hard then company value increases.

now ,if all employee work hard(LHS) then obviously any employee will work hard(RHS),LHS is inclusive of RHS.

---

Yes, all your statements are TRUE. But you did not take the whole of LHS or RHS. Here, left part of LHS, implies left part of RHS as you told. But for implication, it becomes TRUE when left part is false. This is what is happening here. That is why I told you to try making LHS true and RHS false. 

LHS says if a (x) is true for all x then  b is true

RHS says if for any x a(x) is true then b is true

So, LHS is true - when say at least one x is there with a(x) is false - irrespective of $\beta$, so let $\beta$ be false. But RHS is false, if $\beta$ is false and there is at least one $x$, with $a(x)$ true.  

---

ook,i got it sir.

..what you are saying is if for atleast one x ,a(x) is not true then left part of lhs is false and beta is false as beta is true if only all the x are true hence lhs is true,now in RHS ,Beta is false and left part of rhs i.e for any x,a(x) is true is true..so RHS becomes false.and hence the result

.thankyou sir

---

yes, but beta being false is our assumption - not that it will always be false. To prove an implication as FALSE, always try to make LHS true and RHS false.

---

what is the meaning of having free variable

---

[∀x,β→α(x)] is same as saying [β→ ∀x α(x)]. Is that true??
That is how option A is interpreted??

---

Not able to understand the difference between LHS and RHS of option D. Plz explain it more. Its really hard.

Arjun sir you said that LHS of option D is same as RHS of option C. How??

[∀x,α(x)→β ] , Because of comma does it mean that  if a(x) is true for some x then B is true.

If quantification has higher precedence will it not evaluate ∀x,α(x) first??

---

1. Because of comma does it mean that  if a(x) is true for some x then B is true.

       It means for all x , if  α(x) is true then β  is true. 

yes , worked as ().

---

[∀x,α(x)→β ] is same as [∀x(α(x)→β)]??
And what if comma or paranthesis is not present?? wat will be the interpretation then??

---

yes both are same.

if  ∀xα(x)→β is given then it will be treated as  (∀xα(x))→β means if α(x) is true for all x then β is true,

 ∀x(α(x)→β) means for all x if α(x) is true then β is true.

---

Thanx a lot Anirudh sir. You have cleared such a big doubt of mine. Thanx a million.

---

can u plz tell me further what is the exact meaning of saying B has no free variable??

---

See 

Free variables : used to denote unknown or unspecified objects, 

          means on which no quantification done . Example: (5 < x) ∨ (x² + x − 2 = 0) here x is free variable.

Bound variables: used to quantify, Example :∃x((5 < x) ∨ (x² + x − 2 = 0)) here x is bounded variable. 

Now β is a first order formula with no free variable. means we can apply quantifiaction on β.

ecample in Option B. [∃x,β→α(x)] says if for some x, β is true then α(x) is true.

if  β is free variable than ∃x,β→α(x) $\equiv$ β→∃x,α(x) says if β true then some α(x) is true.

---

But here α(x) is a first order formulae with x as free variable then why have we applied quaantification on α(x) ?? :-(

I am confused.

---

If x does not occur free in C, then

∀x (A(x) → C) ≡ ∃x A(x) → C.

∃x (A(x) → C) ≡ ∀x A(x) → C.

You wrote- if  β is free variable than ∃x,β→α(x) ≡≡ β→∃x,α(x) says if β true then some α(x) is true

Its creating lots o confusion.

---

Arjun sir can u plzz explain what is meant by B having no free variable? You said it will be indeoendent of x. I am confused rearding all this. If you could tell??

---

Here is $\alpha(x)$ a first order formula with $x$ as a free variable, and $\beta$ is a first order formula with no free variable.

What this means is both are actually formula in first order logic and not constants or even just predicate logic formula. While $\alpha$ has a free variable, $\beta$ is not having one. Free variable just means it is not quantified. But in all the options $x$ is quantified- we are making a new formula where $x$ is quantified in each case.

---

@ Arjun sir, So does it mean B(BETA) is quantified already because it has not got any free variable?? So why are we quantifying it in the options?? what does it imply?? I dont know why i am so confused :-(

Also when beta is quantified how is it independent of x??

---

No, it doesnt mean so. You can consider $\alpha$ and $\beta$ as two functions in C language. While $\alpha$ takes in an argument $x$, $\beta$ does not. Now, each option is like using these functions in a program. There we apply quantification for $x$ before calling $\alpha$. Inside $\alpha$ and $\beta$, there can be any number of other quantified variables like local variables in a C function.

---

so by what i understood i think since beta doesnt take X as an argument, quantifying beta is redundant like 

∃x(β)= β

am i right sir??

---

yes. But that is false for an empty domain. But for this subject we always assume non-empty domain. Some other identities we use also make use of this assumption.

---

Thanx a lot sir for explaining the concept. Well i should now not ask about empty domain right?? whats that??

---

@Arjun Sir , Wrt to Option C.[(∃x,α(x))→β]→[∀x,α(x)→β]

β is a formula which is independent of x. (if β is true for one x, it is true for every x and vice versa). 

Sir, I m not getting this blue bold Marked Line...plz help

---

@Arjun Sir,

For option (D),

Let the domain of α(x) be set of integers {1,2,3,4,5}

How do

(∀x,α(x))

And

∀x,α(x)

differ here.

 

Like I can write

∃x($\alpha$(x)) as  ($\alpha$(1) v $\alpha$(2) v $\alpha$(3) v $\alpha$(4) v $\alpha$(5))

considering the domain given above

---

In option A and B, the variable x is not quantified properly, it is ambiguous. How to determine if x is quantified when brackets are not used. And what is the meaning of comma after the quantifier?

---

Is this the correct way to solve the problem? Can someone tell me how to rotate image?

---

how is RHS of option D is same as LHS of option C? they have different quantifiers

---

@Arjun Sir , Thank you so much sir for the nice explanation.

---

Great answer.

---

can anyone tell me whats the relation between the comma and scope?

---

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!