Consider the following first order logic formula in which R is a binary relation symbol. forall y (R(y, x) => R(g, y)) 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

GATE 2006 · Discrete Mathematics · First Order Logic · medium

Answer: B. satisfiable and so is its negation

1. Find an interpretation where the formula is TRUE: Let domain = {a}, R = empty relation, x = a, g = a. Then R(y,x) is false for all y, so the implication R(y,x) => R(g,y) is true for all y (vacuously). Hence forall y (...) is true. The formula is satisfiable.
2. Find an interpretation where the formula is FALSE (making negation TRUE): Let domain = {a, b}, let g = a, x = b. Set R = {(a,b)} (only a relates to b). Choose y = a: antecedent R(a,x) = R(a,b) = TRUE, consequent R(g,a) = R(a,a) = FALSE. So the implication fails for y = a, making the formula false. Hence its negation is also satisfiable.