Consider the following formula and its two interpretations I_1 and I_2.
alpha: forall x (P_1(x) -> exists y (Q(x,y) => P_2(y)))
I_1: Domain: the set of natural numbers; P_1(x) = 'x is a prime number'; Q(x,y) = 'y divides x'; P_2(y) = 'y is a prime number'
I_2: same as I_1 except that P_2(y) = 'y 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 satisfy alpha
GATE 2003 · Discrete Mathematics · First Order Logic · medium
Answer: Both I_1 and I_2 satisfy alpha. Answer: D.
Check I_1: P_1(x) = 'x is prime', P_2(y) = 'y is prime', Q(x,y) = 'y divides x': Take any prime x. Choose y = x+1. Then (x+1) does not divide x, so Q(x, x+1) is false. The implication Q(x, x+1) => P_2(x+1) is vacuously true. Thus 'exists y (Q(x,y) => P_2(y))' is satisfied. Since P_1(x) -> satisfied-exists is true, alpha holds under I_1.
Check I_2: P_2(y) = 'y is composite' (everything else same): Exact same argument applies. For any prime x, pick y = x+1. Q(x, x+1) is false (x+1 does not divide x), so the implication is vacuously true. Hence 'exists y' is satisfied and alpha holds under I_2 as well.