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

(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

Sir, please mention some example for option d

---

added :)

---

sir ,for (d) option take set as {2,5,7,13} where [ alpha : prime numbers] [beta : odd numbers] (∀x)[α ⇒ β] ⇒ ((∀x)[α]) ⇒ (∀x)[β]) now left side of implication we have for all x alpha implies beta which is false means false------> RHS now solving RHS, RHS says for all x if alpha than for all x beta also there.. which is false means now RHS is false.. therefore false --------> false (i.e) true +false which is always true.. so (d) option correct plz check is that correct/?????

---

What you told is correct. But what we want to prove is "validity". That is our formula must be TRUE for all instances. So, taking an example won't help. Example helps only for proving satisfiability.

---

@arjun sir,how to solve these type of question which involve quantifiers in them and ask us to rove tautology??..pls help

---

You need to know the De-Morgan's law for first order logic. Then with a good English, basics of set theory and a bit of practice you can solve any such question easily. The weblinks here are good: http://gatecse.in/mathematical-logic/

---

@Arjun if we take universal domain as persons

α =males

β=females

For this B. option becomes true ?

i had checked other options im getting B. plz verify with my domain

---

you are taking domain person dont include person which is man and women.

if you are seeing like that then Arjun sir ans also wrong take 12 in set . so the logic is B is not true for any possible domain.

If we prove it is wrong for any domain then it is invalid .

---

@Gabbar For that domain, option B becomes TRUE if there exist a person who is both male as well as female.

Anyway, important thing here is not to make the formula TRUE or FALSE. A formula is VALID if no instance of it is FALSE. So, it is enough to give any instance which gives FALSE and prove that our formula is not valid. But now how to prove that a given formula is VALID? - Here we cannot take any example as we are not going to get instance which is false. And getting one or two instances which are TRUE does not prove anything.

---

Nice discussion on such confusing question.Thanks, everyone.

---

How A) and D) differs?

A)Say α=Number divisible by 3, β=Number divisible by 4

((∀x)[α] ⇒ (∀x)[β]) = (( ∃x )[~α] + (∀x)[β])

i.e. Some number not divisible by 3 or all number divisible by 4

So, LHS could be {7,5}

RHS= (∀x)[α ⇒ β] = (∀x)[~α + β]

i.e. all number of set x either not divisible by 3 or divisible by 4

So, RHS could contain {4,8,7,5}

So, LHS doesnot implies RHS.

D)just opposite to A). So, it is valid :)

---

(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.

For Each X={3,6,9,8} 

LHS= (T^T^T^F)=>(F^F^F^T)
                     F=>F
                     TRUE

RHS= [(T=>F)^(T=>F)^(T=>F)^(F=>T)]
                          FALSE

TRUE=>FALSE
Make Implication False.

---

Sir , Won't the answer keep on changing if we take different values of X

---

I am unable to understand the approach for this question at all. Kindly explain how is this being done?

---

@arjun, will there be a difference if in place of free variable, x is a bounded variable?

---

srestha you said LHS does not implies RHS 

there can be 2 cases for that T---->F and F---->T 

in the example you gave{7,5} proves T---->T 

and in example arjun sir gave {3,6,9,8} proves T-----> F (not valid)

---

@Arjun Sir I have some questions, rather i am asking for a suggestion to solve such kind of problems

1)Sir i have gone through  your several approaches that you follow for solving such problems where i have observed for various options (let say a,b,c,d) yu are taking different  set of domains and propositional fuctions respectively let say for option a )you take domain(x)={3,6,9,12} and p(x): x is a even number q(x): x is a odd number

let say for option b) domain(x)={3,6,8} p(x):x is a multiple of 3 q(x)=x is multiple of 2   

So my question is Is it right approach before solving a problem to predefine a fixed domain and fixed propositional functions for all options a,b,c,d

let say domain(x)={3,6,8} p(x):x is a multiple of 3 q(x)=x is multiple of 2   

now for this same set of domain as well as propositional functions can i solve all the options a,b,c,d

2).I sometimes fell in fear when i found a option True and it is valid .I fear that if someone came up with set of   domain and propositional functions which proves its false .So,in course of fear i think more about that problem which takes more time .

So my question is how to handle  such situation  ?

---

The point is that to prove something correct you've make sure it is correct for each and every case(maybe infinite in number) but to prove something wrong we only need one case.

So, to check validity of implication try to prove it false, by trying to make LHS as True and RHS as false, if you'll able to do so then implication is not valid otherwise it is valid.

I think arjun sir also done the same he found out one case such that implication can be proved wrong and yes, you've thing that by yourself and don't worry it will come easy if you practice with right mindset as I mentioned above.

---

@Arjun Can we say that in option A) a weaker condition implies a stronger condition which makes it wrong. But in option D) a stronger condition implies a weaker condition which makes it correct.

---

What if we solve option d with set {3,6,9,8} then this option d will not be true or valid.

valid means for any set this option holds true but for {3,6,9,8} this is not true.

---

I'm not getting the trick actually.

Can anyone tell me what is the basic fanda to do this type of questions?

---

@halder just read @bhuv comment u will understand inshallah what is going on here

---

Option B and C can be eliminated easily.But doubt comes in A and D..

For B  $\forall x( \alpha)\rightarrow \exists x(\alpha\wedge\beta)$

it is not valid because if $\alpha$  is true for all values of x and $\beta$  is false for all values of x then rhs is always false and LHS is true. So $TRUE \rightarrow FALSE$  is false. So option B is invalid.. Similarly we can prove that C is also invalid..

---

what does x as their onlu free variable mean here?

---

it means that only x can take any random value in the domain .

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

mza sa aa gya

---

@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$

 

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 $

Answer 4

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

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

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