The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+34 votes
3.2k views

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

  1. $(\exists x) (\text{boy}(x) \rightarrow (\forall y) (\text{girl}(y) \land \text{taller}(x, y)))$
  2. $(\exists x) (\text{boy}(x) \land (\forall y) (\text{girl}(y) \land \text{taller}(x, y)))$
  3. $(\exists x) (\text{boy}(x) \rightarrow (\forall y) (\text{girl}(y) \rightarrow \text{taller}(x, y)))$
  4. $(\exists x) (\text{boy}(x) \land (\forall y) (\text{girl}(y) \rightarrow \text{taller}(x, y)))$
asked in Mathematical Logic by Veteran (59.5k points)
edited by | 3.2k views
0

(A) (∃x) (boy(x) → (∀y) (girl(y) ∧ taller(x,y))) 
(B) (∃x) (boy(x) ∧ (∀y) (girl(y) ∧ taller(x,y))) 
(C) (∃x) (boy(x) → (∀y) (girl(y) → taller(x,y))) 
(D) (∃x) (boy(x) ∧ (∀y) (girl(y) → taller(x,y)))

0
For those who are still confused between ^ and ->.

Use ^ for there exist(∃) and use -> for all(∀).
0
@vishal there exist operator is distributed over OR not AND so that it gives values according to the domain.

4 Answers

+86 votes
Best answer

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
 

answered by Loyal (5.9k points)
edited by
0
very nice explanation thanks..
0
How option B says all students in the class are girls. ??
+2
How option B says all students are girls. ?
+16

@vijaycs plz see below examples..hope it will clear ur doubt.

 Example1 :- For the set of natural no.

P(x)= x is a prime no.

but $\forall$y P(x) is false

as above statement says every number is prime number.

Example 2:-

∀x∃y( fsa(x) ∧ pda(y) ∧ equivalent(x,y))

Everything is a FSA and has an equivalent PDA.

(Note:- here and (^) connective also imp. ...instead if -> (implication) will there means ..it says that for every x if x is a fsa then..)

https://gateoverflow.in/441/gate2008-30

Example 3:-(Ur Doubt)

When Universe of Discourse is a class (consist of boys and girls)

girl(y)= y is a girl.

but $\forall$y girl(y) is false

as above statement says everyone is girl.

and particularly

  1. (∃x) (boy(x) ∧ (∀y)(girl(y) ∧ taller(x,y)))

  2. (∃x) (boy(x) ∧ (∀y)(girl(y) → taller(x,y))

Here ^,-> matters...

^  detemines all y must be girl which is clearly false

-> determines if y is girl then .....

+3
Nice explanation and a great source for such type questions.
+14 votes
(∃x)(boy(x) ⋀ (∀y)(girl(y) → taller(x, y)))

Should be the answer.
answered by Veteran (355k points)
0

y not b) bcz if (∃x)(boy(x) ⋀ (∀y)(girl(y) → taller(x, y))) then  girl(y) → taller(x, y)) if we simplify then it wil be ~girls or taller kindly say how this satisfy the condition according to me ans shd b kindly correct me

0
In B, the girl(y) is applied to all y, but y can also be a boy.
0

not getting its meaning the girl(y) is applied to all y, but y can also be a boy. kindly repeat ......

0
Here we have boys as well as girls in the universe. So $\forall y \text{girl}(y)$ means there is no boy meaning $\exists x \text{boy}(x)$ is false
0

but here x denote for boy & y for girl then how it can b So ygirl(y) means there is no boy meaning xboy(x) is false  possible not getting please elaborate more...

+3
No. Y is not denoting girl. If we make sure y denotes a girl, then it is correct. And that's why we need an "implies".
0

y we cant sure as they hv mention 

then wts mean of this note??

Note: taller (x, y) is true if x is taller than y. 

Some boys in the class are taller than all the girls 

+3
The Note is applicable for any x,y. Now we have to quantify x to SOME boys and y to ALL girls. But in B option, y is quantified to ALL (here all students in class) and not just to all girls.
0

sir please say how u predict   in B option, y is quantified to ALL (here all students in class) and not just to all girls.???

+2
It is not prediction. By default a variable applies to the largest possible set.
0
this now m geetin need of "implies" but please make me clr one more thing if we simplify "imples" then will get ~girls or tall will not effect ans??//?
+1
No, That would mean the same. Obviously the formula is not ensuring that any girl exist in the glass, but only ensuring that IF any girl exist, her height is shorter than that of a boy.
0
What does option b signifies??
+1
I understod the solution but just wanna ask one thing for extra understanding. Can we move (∀y) ie for all y just before the inner paranthesis that is just after ∃x, according to null quantification rule??
0
ya sushmita
+6 votes

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

answered by Loyal (8.1k points)
0
Very nice explanation @minipanda
+1
Thank you :)
+4 votes
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.
answered by Active (4.1k points)
–3
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??


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,040 questions
45,538 answers
131,827 comments
48,858 users