GATE CSE 2004 | Question: 23, ISRO2007-32

Question

Identify the correct translation into logical notation of the following assertion.

Some boys in the class are taller than all the girls

Note: $\text{taller} (x, y)$ is true if $x$ is taller than $y$.

• A. $(\exists x) (\text{boy}(x) \rightarrow (\forall y) (\text{girl}(y) \land \text{taller}(x, y)))$
• B. $(\exists x) (\text{boy}(x) \land (\forall y) (\text{girl}(y) \land \text{taller}(x, y)))$
• C. $(\exists x) (\text{boy}(x) \rightarrow (\forall y) (\text{girl}(y) \rightarrow \text{taller}(x, y)))$
• D. $(\exists x) (\text{boy}(x) \land (\forall y) (\text{girl}(y) \rightarrow \text{taller}(x, y)))$

Comments

@Deepak Poonia Just watched the revision lecture, was helpful.

---

d
done

---

https://youtu.be/s41PLmHGf08?list=PLIPZ2_p3RNHidhFvyKH4U_VE1rFAyvG8U&t=422

Answer 1

Now many people get confused when to use $\wedge$ and when to use $\implies$. This question tests exactly that.
We use $\wedge$ when we want to say that the both predicates in this statement are always true, no matter what the value of $x$ is. We use $\implies$ when we want to say that although there is no need for left predicate to be true always, but whenever it becomes true, right predicate must also be true.
Now we have been given the statement $\text{ “Some boys in the class are taller than all the girls"}$. Now we know for sure that there is at least a boy in class. So we want to proceed with $ “\left(\exists x\right)(boy\left(x\right)\wedge"$ and not $ “\left(\exists x\right) (boy\left(x\right) \implies"$, because latter would have meant that we are putting no restriction on the existence of boy i.e. there may be a boy-less class, which is clearly we don't want, because in the statement itself, we are given that there are some boys in the class. So options (A) and (C) are ruled out.
Now if we see option (B), it says, every y in class is a girl i.e. every person in class is a girl, which is clearly false. So we eliminate this option also, and we get correct option (D). Let us see option (D)explicitly also whether it is true or not. So it says that if person y is a girl, then x is taller than y, which is really we wanted to say.
So option (D) is correct.

http://www.cse.iitd.ac.in/~mittal/gate/gate_math_2004.html
 

Comments

@ash_khola it is still valid.It does not matter whether girls exist or not but if a girl exists,then there is some boy who is taller than her,for all girls.

---

nice explaination

---

@athenahermes even i also assumed the same and got confused ..... but IN FOL, EVERY VARIABLE SHARE THE SAME DOMAIN UNLESS EXPLICITELY MENTIONED ....so here  Also if x has the domain class (consist of boys and girls) then y variable also must have the same domain class (consist of boys and girls).

Answer 2

I have attached two links here. They contain photos clicked from my worked out solution. Hopefully this will clear the doubts arising between option B and D.

https://i.stack.imgur.com/zc2j5.jpg

https://i.stack.imgur.com/hgbnR.jpg

Comments

@minipanda you explained amazingly well sir.

---

This is the best solution, others are right too, this is easy to understand.

---

Really good sol!!

Answer 3

(∃x)(boy(x) ⋀ (∀y)(girl(y) → taller(x, y)))

Should be the answer.

Comments

ya sushmita

---

But what if there is no no girl, option D will still give true which shouldnt be.

---

if there is no girl this statement still satisfies : some boys in class are taller then all the girls.

Answer 4

Detailed Video Solution: https://youtu.be/60kicY3otM0?feature=shared

Analysis of EACH Option:

Option A:

We know that $P \rightarrow Q = P' + Q$

So, Option A is saying that: There exists a $x$ in the class such that either "$x$ is a girl" or "everyone is a girl & $x$ is taller than everyone".

NOTE that Option A is True if there is at least one girl in the class, else option $A$ is false. 

---

Option B:

Option B is saying that: There exists a $x$ in the class such that $x$ is a boy and everyone is a girl and $x$ is taller than everyone".

NOTE that Option B is Never True.

---

Option C:

We know that $P \rightarrow Q = P' + Q$

So, Option C is saying that: There exists a $x$ in the class such that either "$x$ is a girl" or "if anyone $y$ is a girl then $x$ is taller than $y$".

NOTE that Option C is Always True. If there is at least one girl in the class, then Option C becomes True, & also, if there is no girl in the class then also option C becomes True.

---

Option D Analysis: https://youtu.be/60kicY3otM0?feature=shared

Comments

Deepak Poonia I think more precise statement should be this for option A ...There exists an $x$ such that either '$x$ is not a boy' or 'everything in the universe is a girl & $x$ is taller than everything'. Can we write $\neg\text{boy} \neq \text{girl}$ ? what if third things exist in the domain...Plz let me correct if I am wrong ?

Answer 5

we have been given the statement "Some boys in the class are taller than all the girls". Now we know for sure that there is atleast a boy in class. So we want to proceed with "(∃x) (boy(x) ∧" and not "(∃x) (boy(x) →", because latter would have meant that we are putting no restriction on the existence of boy i.e. there may be a boy-less class, which is clearly we don't want, because in the statement itself, we are given that there are some boys in the class. So options (A) and (C) are ruled out.

Now if we see option (B), it says, every y in class is a girl i.e. every person in class is a girl, which is clearly false. So we eliminate this option also, and we get correct option (D). So it says that if person y is a girl, then x is taller than y, which is really we wanted to say.
So option (D) is correct.

Comments

But the question says taller than all girls that means there is no question on existence of girls also. Doesn't it? Then it should make (B) right answer??

---

But what if there is no no girl, option D will still give true which shouldnt be.

Answer 6

Some boys in the class are taller than all the girls.

Our domain is $\textbf{set of boys & girls in the whole class.}$

We rewrite like this:

$\text{There exists some x such that x is boy}\; \color{Red}\text{and}$ $\text{for all y, if y is girl, then x is taller than y}$

logically we can write: $\color{DarkRed}(\exists x) \text{(boy(x)} \wedge (\forall y)(\text{girl(y) → taller(x,y))})$

$\color{DarkGreen}\text{Ans: D}$

Comments

thanx