GATE CS 2014 Set 1 Q1 — Propositional and First Order Logic

To translate the statement "Not all that glitters is gold" into first-order logic, we can break it down step-by-step:

1. First, let's write the statement "All that glitters is gold": $$\forall x \, (\text{glitters}(x) \Rightarrow \text{gold}(x))$$
2. Now, we negate this statement to get "Not all that glitters is gold": $$\neg \forall x \, (\text{glitters}(x) \Rightarrow \text{gold}(x))$$
3. Using the logical equivalence $\neg \forall x \, P(x) \equiv \exists x \, \neg P(x)$, we get: $$\exists x \, \neg (\text{glitters}(x) \Rightarrow \text{gold}(x))$$
4. Using the implication negation rule $\neg (A \Rightarrow B) \equiv A \wedge \neg B$, we simplify the formula to: $$\exists x \, (\text{glitters}(x) \wedge \neg \text{gold}(x))$$

This matches Option D, which states that "there exists some object $x$ that glitters and is not gold".

Analysis of other options:

• Option A: $\forall x \, (\text{glitters}(x) \Rightarrow \neg \text{gold}(x))$ translates to "Nothing that glitters is gold" (or "All glittering things are not gold").
• Option B: $\forall x \, (\text{gold}(x) \Rightarrow \text{glitters}(x))$ translates to "All gold things glitter".
• Option C: $\exists x \, (\text{gold}(x) \wedge \neg \text{glitters}(x))$ translates to "There is some gold that does not glitter".