GATE CS 2014 Set 1 Q.11 (CS Q.1): Propositional and First-Order Logic

Consider the statement

\text{“Not all that glitters is gold”}

Predicate $glitters(x)$ is true if $x$ glitters and predicate $gold(x)$ is true if $x$ is gold. Which one of the following logical formulae represents the above statement?

$\forall x: glitters(x) \implies \neg gold(x)$

$\forall x: gold(x) \implies glitters(x)$

$\exists x: gold(x) \land \neg glitters(x)$

$\exists x: glitters(x) \land \neg gold(x)$

Official answer and solution

Official answer: D
From: Official GATE 2014 answer key

Solution

Translate the colloquial statement 'Not all that glitters is gold' into first-order predicate logic and apply quantifier negation rules.

The natural English statement 'Not all that glitters is gold' means:
'It is not the case that every object that glitters is gold.'

First, express 'All that glitters is gold':

\forall x (glitters(x) \implies gold(x))

Now negate this statement:

\neg \forall x (glitters(x) \implies gold(x))

Applying quantifier negation and implication equivalence ( $P \implies Q \equiv \neg P \lor Q$ ):

\exists x \neg (\neg glitters(x) \lor gold(x))

\exists x (glitters(x) \land \neg gold(x))

This states: 'There exists an object that glitters and is not gold.'
This matches option D exactly.

Final answer

Common trap

Confusing 'Not all A are B' ( $\exists x (A(x) \land \neg B(x))$ ) with 'No A are B' ( $\forall x (A(x) \implies \neg B(x))$ ).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 1
Question: 11 of 65, printed as CS Q.1
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source