GATE CS 2008 Q15 — Tuple Calculus and SQL

In first-order logic and relational calculus, the universal quantifier ($\forall$) and the existential quantifier ($\exists$) are related by the following standard equivalence:

Applying this equivalence to a restricted domain where the tuple $t$ belongs to the relation $r$, the expression "for all tuples $t$ in $r$, $P(t)$ is true" can be rewritten as:

This translates to: "There does not exist a tuple $t$ in $r$ for which $P(t)$ is false." This matches expression III exactly.

Let's verify why the others are incorrect:

• I: $\neg \exists t \in r \left(P\left(t\right)\right)$ is equivalent to $\forall t \in r \left(\neg P\left(t\right)\right)$ (no tuple in $r$ satisfies $P$).
• II and IV: These expressions involve $t \notin r$, which refers to tuples outside the relation $r$ and cannot be equivalent to a statement restricted to $t \in r$.

Thus, only expression III is equivalent, which corresponds to option C.