Consider the following first order logic formula in which R is a binary…
2006
Consider the following first order logic formula in which R is a binary relation symbol.
∀x∀y (R(x, y) => R(y, x))
The formula is
- A.
satisfiable and valid
- B.
satisfiable and so is its negation
- C.
unsatisfiable but its negation is valid
- D.
satisfiable but its negation is unsatisfiable
Attempted by 94 students.
Show answer & explanation
Correct answer: B
Short answer: The formula is satisfiable, and so is its negation. Therefore the formula is neither valid nor unsatisfiable.
Reasoning:
Satisfiable example: Any model with R empty (no ordered pairs).
In such a model R(x,y) is false for every x,y, so the implication R(x,y) => R(y,x) is true for all pairs, making the universal formula true.
Counterexample showing the formula is not valid (and showing the negation is satisfiable): Take domain {a,b} and let R = {(a,b)}.
Then R(a,b) holds but R(b,a) does not, so the implication R(a,b) => R(b,a) is false and the universal formula fails in this model. The negation ∃x∃y (R(x,y) ∧ ¬R(y,x)) is satisfied by x=a,y=b in this model.
Conclusion: Both the formula and its negation have models, so the correct classification is that the formula is satisfiable and so is its negation.