Identify the correct translation into logical notation of the following assertion. "Some boys in the class are taller than all the girls" Note: taller(x, y) is true if x is taller than y. A. (exists x)(boy(x) ^ (forall y)(girl(y) ^ taller(x,y))) B. (exists x)(boy(x) ^ (forall y)(girl(y) -> taller(x,y))) C. (exists x)(boy(x)) ^ (forall y)(girl(y) ^ taller(x,y)) D. (exists x)(boy(x)) ^ (forall y)(girl(y) -> taller(x,y))

GATE 2004 · Discrete Mathematics · First Order Logic · easy

Answer: The correct translation is D: (exists x)(boy(x)) ^ (forall y)(girl(y) -> taller(x,y)).

1. Translate 'some boys' using the existential quantifier: The sentence starts with 'some boys', so begin with (exists x)(boy(x) ^ ...). The property B of this boy x is that he is taller than all girls.
2. Translate 'taller than all the girls' using the universal with implication: 'All the girls' becomes (forall y)(girl(y) -> taller(x,y)). Using conjunction instead of implication (girl(y) ^ taller(x,y)) would be wrong: forall y (girl(y) ^ taller(x,y)) would assert every y in the domain is a girl AND shorter than x, which is too strong.
3. Combine and identify the correct option: The full translation is: (exists x)(boy(x)) ^ (forall y)(girl(y) -> taller(x,y)). This matches option D. Option B would be (exists x)(boy(x) ^ (forall y)(girl(y) -> taller(x,y))) which is logically equivalent but bundles the universal inside the existential scope; the answer key picks D which keeps them as a conjunction at the top level.