GATE CSE 2003 | Question: 33

Question

Consider the following formula and its two interpretations \(I_1\) and \(I_2\).

\(\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]\)

\(I_1\) : Domain: the set of natural numbers

\(P_x\) =  '$x$ is a prime number'

\(Q_{xy}\) = '$y$ divides $x$'

\(I_2\) : same as \(I_1\) except that \(P_x\) = '$x$ is a composite number'.

Which of the following statements is true?

• A. \(I_1\) satisfies \(\alpha\), \(I_2\) does not
• B. \(I_2\) satisfies \(\alpha\), \(I_1\) does not
• C. Neither \(I_1\) nor \(I_2\) satisfies \(\alpha\)
• D. Both \(I_1\) and \(I_2\) satisfies \(\alpha\)

Comments

Here, 𝑅𝐻𝑆=∀𝑥𝑃𝑥′ is always true,

@strawberry-jam Yours easiest and fastest way is totally wrong.

 This statement will be true iff P(x) is false for every element in the domain. 

---

https://gateoverflow.in/923/gate-cse-2003-question-33?show=531424#a531424

How to analyze such FOL Expressions

Hopefully it helps :)

 

---

Q_yy means "y divides y". That's true for every y. So ¬Q_yy is always false, no matter what y is.  it's the constant F.
The inner part becomes (∀y)[Q_xy ↔ F], which says "no y divides x".
Counterexample: take y = x: x divides x, so Q_xx is true. The inner part is always false too.
substitute again.
LHS now: (∀x)[P_x ↔ F] = (∀x)[¬P_x] (since P ↔ F is ¬P.)
α = (∀x)[¬P_x] → (∀x)[¬P_x]
A → A is a tautology, so α is true in every interpretation. Both I1 and I2 satisfy it.

Answer 1

Given Statement:

$$ \alpha: (\forall x)\left[ P_x \Leftrightarrow \color{#007acc}{ \left( \forall y \color{#007acc}{ \left[ Q_{xy} \Leftrightarrow \neg Q_{yy} \right] } \right) } \right] \Rightarrow (\forall x)[\neg P_x] $$

Note: We are told that \( Q_{yy} \) is always True. So \( \neg Q_{yy} \) is always False.

---

Let’s analyze the Left-Hand Side (LHS):

$$ (\forall x)\left[ P_x \Leftrightarrow \color{#009966}{ \left( \forall y \color{#009966}{ \left[ Q_{xy} \Leftrightarrow \neg Q_{yy} \right] } \right) } \right] $$

Since \( \neg Q_{yy} \) is always False, we substitute:

$$ (\forall y)\left[Q_{xy} \Leftrightarrow \text{False} \right] $$

Using the identity: \( A \Leftrightarrow \text{False} \equiv \neg A \), this becomes:

$$ (\forall y)\left[\neg Q_{xy} \right] $$

So the entire LHS now simplifies to:

$$ (\forall x)\left[P_x \Leftrightarrow (\forall y)[\neg Q_{xy}] \right] $$

Now interpret: \( (\forall y)[\neg Q_{xy}] \) means that no value of \( y \) divides \( x \). But this is clearly false because:

• At least one value (e.g., \( y = 1 \) or \( y = x \)) always divides \( x \)

So \( (\forall y)[\neg Q_{xy}] \) is false, and:

$$ P_x \Leftrightarrow \text{False} \Rightarrow \neg P_x $$

Therefore, LHS becomes:

$$ (\forall x)[\neg P_x] $$

---

Now the full formula becomes:

$$ (\forall x)[\neg P_x] \Rightarrow (\forall x)[\neg P_x] $$

This is a trivially true implication — any statement implies itself.

Conclusion:
The formula \( \alpha \) is always true, no matter what \( P(x) \) represents — whether it’s for prime numbers, composite numbers, etc.

✅ Therefore, both I₁ and I₂ satisfy \( \alpha \).
Correct Option: D

Comments

Those who don't understand how ¬Qyy is always false -

Qxy = ' y divides x ' (Given in the question)

so Qyy = 'y divides y'   =  y|y = 1 =  Always true

 ¬Qyy =   ¬(1) = '0' = Always false. 

---

So even if option would have been given valid instead of satisfy then also both i1 and i2 are valid right @Sachin Mittal 1 sir ?

---

Fantastic answer

Answer 2

$\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]$

This is can be interpreted as:

• $\alpha: \left( (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \right) \Rightarrow \left((\forall x)\left[\neg P_x\right] \right)$

See the RHS. It says $P(x)$ is false for any natural number. But there are natural numbers which are prime and hence this RHS is FALSE. Now, to make $\alpha$ TRUE, LHS must be FALSE for any $x$. Here, LHS is bit complex, so lets consider it separately. 

$ (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] $

LHS is TRUE only if the given implication is TRUE for all $x$. Here the rightmost double implication $(\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]$ is always FALSE, because $x$ can be equal to $y$ and hence forall can never be TRUE. So the LHS reduces to just $(\forall x) \neg P(x)$ and returns FALSE as we have prime as well as non-prime natural numbers. So, FALSE $\Rightarrow$ FALSE returns TRUE making both $I_1$ and $I_2$ satisfy $\alpha$. D choice. 

Comments

(∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]

Now [Qxy⇔¬Qyy] becomes false as mentioned in answer.

(∀x)[Px⇔(∀y)[False]]

(∀x)[Px⇔[False]]

(∀x)[¬Px]

Please tell if i am wrong

---

@rahul sharma 5 correct !

---

Hi @Arjun sir

just one doubt
 when it says p(x): x is a prime number
 α:(∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]⇒(∀x)[¬Px]

then, in that (∀x) does that means x itself is a set of prime numbers and for all x quantifier is going to pick every prime number value from the set

when it says p(x): x is a composite number
 α:(∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]⇒(∀x)[¬Px]

then, in that (∀x) does that means x itself is a set of composite  numbers and for all x quantifier is going to pick every composite number value from the set

and the domain of Y:{set of all  natural numbers}

Answer 3

all logic concept is based on $T\rightarrow F$ .

1st let's see for $I_{2}$

If we somehow make a combination such that the implication will false, then we're done.

Now we have only one way to make an implication false, which is $T\rightarrow F$ combination.

If the domain is composite(means not prime) then right side of the $\alpha$ is always T, which implies we can't make $\alpha$ false.    $P_{x} = F$   i.e    $\sim P_{x} = T$ always.

So, $I_{2}$ satisfies $\alpha$.

 

Now, let's come in $I_{1}$

In $I_{1}$,  $\sim {Q_{yy}}$ is always false because in any circumstances y divides y.

now, try to make $T\rightarrow F$ combination.

let's forget about quantifiers & treat $\alpha$ as $[P_{x} \Leftrightarrow [Q_{xy}\Leftrightarrow Q_{yy}]] \rightarrow \sim P_{x}$.

take $P_{13}$, RHS is F.  LHS is $[P_{13} \Leftrightarrow [Q_{13.1}\Leftrightarrow Q_{1.1}]]$

So, $[P_{13} \Leftrightarrow [T\Leftrightarrow F]]$

$[P_{13} \Leftrightarrow F]$  = $F$, which means $F\rightarrow F$ implies T

So, using any number(composite or prime), we can't make the implication false.

So, $I_{1}$ also satisfies $\alpha$.

Option D is the answer.

 

 

Answer 4

this a more intuitive way to solve about it

Q(y,y) = y divides y =  True for every natural number 

so neg(Q) = False always

so our statement becomes

$$\forall_x[P_x \leftrightarrow \forall_y[Q_{xy} \leftrightarrow False]] \longrightarrow \forall_x \neg P_x$$

$$\forall_x[P_x \leftrightarrow \forall_y[\neg Q_{xy}]] \longrightarrow \forall_x \neg P_x$$

1. FOR I1 , statement $\alpha$ can be read as

   $$\forall_x[\text{x is prime}\leftrightarrow \forall_y[\text{x is not divisible by y}]] \longrightarrow \forall_x \text{x is not prime}$$
   $$\text{x is prime if and only if it is not divisible by any natural number} \longrightarrow \forall_x \text{x is not prime}$$
   here the antecedent is false (counterexample 3 which is divisible by 1 and 3)
   $False\rightarrow anything = True$
   so I1 satisfies  $\alpha$

2. FOR I2 , statement $\alpha$ can be read as

   $$\forall_x[\text{x is not prime}\leftrightarrow \forall_y[\text{x is not divisible by y}]] \longrightarrow \forall_x \text{x is prime}$$
   $$\text{x is not prime if and only if it is not divisible by any natural number} \longrightarrow \forall_x \text{x is not prime}$$
   here the antecedent is false (counterexample 4 which is divisible by 2 and 4)
   $False\rightarrow anything = True$
   so I2 satisfies  $\alpha$

Answer 5

For solving the question, the answers provided previously are clear, concise, and correct.

But, to solve the question mathematically, here is my solution:

Step 1: Convert to CNF

$α: \forall x [P_x \leftrightarrow \forall y (Q_{xy} \leftrightarrow \neg Q_{yy})] \rightarrow \forall x[\neg P_x]$

$= \forall x [P_x \leftrightarrow \forall y (Q_{xy} \leftrightarrow \text{False})] \rightarrow \forall x[\neg P_x]$

$= \forall x [P_x \leftrightarrow \forall y \neg Q_{xy}] \rightarrow \forall x[\neg P_x]$

Now on, let’s re-write the connectives as +, *, ‘

$= \forall x [P_x \leftrightarrow \forall y Q_{xy}’] \rightarrow \forall x[P_x’]$

$= \forall x [P_x(\forall y Q_{xy}’)+P_x’(\forall y Q_{xy}’)’] \rightarrow \forall x[P_x’]$

$= \forall x [P_x(\forall y Q_{xy}’)+P_x’(\exists y Q_{xy})] \rightarrow \forall x[P_x’]$

Since, both the $x$ differs, replace the 2nd occurrence with $z$:

$= \forall x [P_x(\forall y Q_{xy}’)+P_x’(\exists y Q_{xy})] \rightarrow \forall z[P_z’]$

$= [\forall x [P_x(\forall y Q_{xy}’)+P_x’(\exists y Q_{xy})]]’ + \forall z[P_z’]$

$= [\exists x \{(P_x’ + \exists y Q_{xy})(P_x + \forall y Q_{xy}’)\}] + \forall z[P_z’]$

$= [\exists x \{(P_x’ + \exists y Q_{xy})(P_x + \forall y Q_{xy}’)\}] + \forall z[P_z’]$

Distribute, the addition over multiplication,

$= [\exists x \{(P_x’ + \exists y Q_{xy} + \forall z[P_z’])(P_x + \forall y Q_{xy}’ + \forall z[P_z’])\}]$ (CNF Form)

$= [\exists x \{(P’(x) + \exists y Q(x,y) + \forall zP’(z))(P(x) + \forall y Q’(x,y) + \forall zP’(z))\}]$

Step 2: Replace existential Quantifiers with Skolem functions and remove all quantifiers

$= (P’(S(x)) + Q(S(x),S(y)) + P’(z))*(P(S(x)) + Q’(S(x),y) + P’(z))$

Step 3: Unification

$\text{Unify}[(P’(S(x)) + Q(S(x),S(y)) + P’(z)),\text{  }(P(S(x)) + Q’(S(x),y) + P’(z))] = \theta$

$\theta = \{S(x)/x, S(y)/y, z/x\}$

Substitute with $\theta$

$= (P’(x) + Q(x,y) + P’(x))*(P(x) + Q’(x,y) + P’(x))$

$= (P’(x) + Q(x,y))*(Q’(x,y))$

Step 4: Apply Resolution Principle

$\underline{(P’(x) + Q(x,y)), \text{    }(Q’(x,y))}$
$P’(x)$

$=P’(x)$

 

$\therefore \alpha : P_x’$

which is satisfied by any $P_x$

Answer 6

How to analysis such FOL expressions 
Hopefully this helps 

Comments

I think u have written apha value wrong ...but logic are correct