GATE CS 2004 Q23 — Propositional and First Order Logic

To translate the English sentence into first-order logic, we can break it down into two parts:

1. "Some boys..."
   This indicates an existential quantifier ($\exists x$). When using $\exists$, we pair it with a conjunction ($\land$) because we want to assert that there exists an element $x$ which is both a boy and satisfies the subsequent condition: $$\exists x (\text{boy}(x) \land \dots)$$ Using an implication like $\exists x (\text{boy}(x) \rightarrow \dots)$ is incorrect because it would be vacuously true if there exists any object in the domain that is not a boy.
2. "...are taller than all the girls."
   This means that for the chosen boy $x$, and for every $y$ in the domain, if $y$ is a girl, then $x$ is taller than $y$. This is a universal statement ($\forall y$) which is paired with an implication ($\rightarrow$): $$\forall y (\text{girl}(y) \rightarrow \text{taller}(x, y))$$ Using a conjunction like $\forall y (\text{girl}(y) \land \text{taller}(x, y))$ is incorrect because it would assert that every entity $y$ in the universe is a girl and $x$ is taller than them.

Combining these two parts, we get:

This matches Option D.