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

Counter Example for I1 case :

X={11,121 }

Y={11}

 

Counter Example for I2 case :

X={4,6,2}

Y={2}

 

option D

Comments

Can you explain your with a few more words please?

---

Can someone explain how this counter example is working?