# Thread: FOL satisfiability of a sentence

1. ## FOL satisfiability of a sentence

Hi Everyone! I've been revising for my exams and got stuck at this question:

The following sentence of First-Order Logic
$\displaystyle ((\forall X p(X)) \to (\forall X q(X))) \wedge p(a) \wedge \neg q(a)$
is
A. valid and satisfiable
B. valid and unsatisfiable
C. valid but its satisfiability cannot be determined
D. invalid and satisfiable
E. invalid and unsatisfiable
F. invalid but its satisfiability cannot be determined
I would think it's E as I can't really find a model which would satisfy this sentence, though the answer is D. Could you please give me a hint as how I should approach this? Assuming that D is the correct answer I must be missing something.

My thinking: if $\displaystyle p(a)$ is to be true then $\displaystyle \forall X p(X)$ must be true as well. This implies that $\displaystyle \forall X q(X)$ must be true and $\displaystyle \neg p(q)$ will inevitably be false.

EDIT:
OK, if we change $\displaystyle ((\forall X p(X)) \to (\forall X q(X)))$ into $\displaystyle ((\neg \forall X p(X)) \vee (\forall X q(X)))$ I can indeed see that the sentence is satisfiable.
Could someone please tell me why I couldn't see it without transforming the implication into disjunction?

2. Originally Posted by Szyszec
My thinking: if $\displaystyle p(a)$ is to be true then $\displaystyle \forall X p(X)$ must be true as well.
The fact that my neighbor, say, John is a horrible person does not imply that all people are horrible. Then a large part of life would lose meaning.

Both the premise and the conclusion of $\displaystyle ((\forall X p(X)) \to (\forall X q(X)))$ can be false in a particular interpretation, so p(a) can be true and q(a) can be false in that interpretation.

You also need to show that the sentence is invalid, i.e., you need to find a counter-interpretation.

Originally Posted by Szyszec
OK, if we change $\displaystyle ((\forall X p(X)) \to (\forall X q(X)))$ into $\displaystyle ((\neg \forall X p(X)) \vee (\forall X q(X)))$ I can indeed see that the sentence is satisfiable.
Could someone please tell me why I couldn't see it without transforming the implication into disjunction?
I am not sure why you could not see it. In fact, I am not sure how changing $\displaystyle ((\forall X p(X)) \to (\forall X q(X)))$ into $\displaystyle ((\neg \forall X p(X)) \vee (\forall X q(X)))$ helps in seeing that the original sentence is satisfiable. The problem with your post before "EDIT," as I pointed out above, is that p(a) can be true and $\displaystyle \forall X p(X)$ can still be false.

Edit: Additional remark. I don't see how B can be true for any sentence except when one considers validity and satisfiability with respect to an empty class of interpretations. If one considers all interpretations and a sentence is valid, then it is true in all interpretations, so it can't be unsatisfiable. Similarly, "satisfiable" is unnecessary in A since it is implied by "valid."