Consider the following formula a and its two interpretations I1 and I2 Which…
2003
Consider the following formula a and its two interpretations I1 and I2
Which of the following statements is true?
Answer: C. Both I1 and I2 satisfy α — Key observation: for every y in the domain Q(y,y) is true (y divides itself), so ¬Q(y,y) is false for all y. Fix x. The subformula (∀y)[Q(x,y) ⇔ ¬Q(y,y)]…
- A.
I2 satisfies α, I1 does not
- B.
Neither I2 nor I2 satisfies α
- C.
Both I1 and I2 satisfy α
- D.
I1 satisfies α, I2 does not
Attempted by 15 students.
Show answer & explanation
Correct answer: C
Key observation: for every y in the domain Q(y,y) is true (y divides itself), so ¬Q(y,y) is false for all y.
Fix x. The subformula (∀y)[Q(x,y) ⇔ ¬Q(y,y)] becomes (∀y)[Q(x,y) ⇔ false], i.e. it asserts that no y divides x. But y = x divides x, so this subformula is false for every x. Call this subformula R(x).
Therefore the antecedent (∀x)[P(x) ⇔ R(x)] is equivalent to (∀x)[P(x) ⇔ false], i.e. (∀x)¬P(x). The consequent of the main implication is also (∀x)¬P(x).
Hence the whole formula is (∀x)¬P(x) ⇒ (∀x)¬P(x), which is true in any interpretation. In particular, it holds whether P denotes "x is prime" or "x is composite".
Conclusion: Both given interpretations satisfy α.
Explore the full course: Iocl Engineers Officers Grade A Paper 2