GATE CS 2010 Q30 — Propositional and First Order Logic

To find the correct English translation of the formula $\forall x \exists y \exists t (\neg F(x, y, t))$, we can analyze the statement step-by-step or translate the given options into logical formulas.

Step-by-Step Translation of Option B

Consider the statement in Option B: "No one can fool everyone all the time."

1. First, let us write the statement: "There exists a person $x$ who can fool everyone $y$ at all times $t$." $$\exists x \forall y \forall t (F(x, y, t))$$
2. The statement "No one can fool everyone all the time" is the negation of the above statement: $$\neg \big[ \exists x \forall y \forall t (F(x, y, t)) \big]$$
3. Applying the rules of quantifier negation (De Morgan's laws for quantifiers): $$\neg \exists x \, P(x) \equiv \forall x \, \neg P(x)$$ Applying this to our formula: $$\forall x \neg \big[ \forall y \forall t (F(x, y, t)) \big]$$ $$\equiv \forall x \exists y \exists t (\neg F(x, y, t))$$

This matches the given first-order logic formula exactly.

Analysis of Other Options

• Option A: "Everyone can fool some person at some time." $$\forall x \exists y \exists t (F(x, y, t))$$
• Option D: "No one can fool some person at some time." $$\neg \exists x \exists y \exists t (F(x, y, t)) \equiv \forall x \forall y \forall t (\neg F(x, y, t))$$