Option A Explanation:
The formula set $\{\exists x Q(x), \forall x (Q(x) \rightarrow R(x)), \forall x \neg R(x)\}$ is satisfied in an interpretation $M,$ if all the formulas in that set are satisfied by that same interpretation. Thus, we seek a interpretation, $M,$ that satisfies the three formulas
- $\exists x Q(x)$
- $\forall x (Q(x) \rightarrow R(x))$ and
- $\forall x \neg R(x).$
For the first formula to be satisfied in $M,$ we need a value “$a$” for $x$ such that “$a$” is in $Q^{M}$ i.e. $Q(a) =$ True. But if the second formula is satisfied in $M,$ this implies that “$a$” is also in $R^M$ i.e. $R(a) =$ True.
The latter makes it impossible for $M$ to satisfy the third formula, which states (if re-expressed with quantifier equivalences) that no value of $M$ is in $R^{M}$ i.e. no value of $M$ satisfies $R.$
Thus, there cannot be an interpretation $M$ that satisfies all three formulas.
For Practice - (Choosing any two formulas above, can you find interpretations that satisfy these two formulas?) (Comment your answer.)
Option B Explanation:
The formula set $\{ \exists y \forall x P(x,y), \forall x \neg P(x,x)\}$ is satisfied in an interpretation $M,$ if all the formulas in that set are satisfied by that same interpretation. Thus, we seek a interpretation, $M,$ that satisfies the two formulas
- $\exists y \forall x P(x,y)$ and
- $\forall x \neg P(x,x).$
For the first formula to be satisfied in $M,$ we need a value “$b$” for y such that $P(a,b) =$ True for all values “$a$”. In particular, this has to be the case for the value of $y.$ Thus, we infer that $P(b,b)=$ True. But the latter makes it impossible for $M$ to satisfy the second formula, which states (if re-expressed with quantifier equivalences) that no pair of the form $(a,a)$ is in $P^{M}$ i.e. For no pair $(a,a), P$ is true.
Thus, there cannot be an interpretation $M$ that satisfies all two formulas.
For Practice - (Can you find interpretations that satisfy just one of these formulas?)(Comment your answer.)
Option C Explanation:
The formula set $\{\forall x \forall y (P(x,y) \rightarrow P(y,y)), \forall x \neg P(x,x), \exists x \exists y (P(x,y)\}$ is satisfied in an interpretation $M,$ if all the formulas in that set are satisfied by that same interpretation. Thus, we seek an interpretation, $M,$ that satisfies the three formulas
- $\forall x \forall y (P(x,y) \rightarrow P(y,y))$
- $\forall x \neg P(x,x)$ and
- $\exists x \exists y (P(x,y).$
For the third formula to be satisfied in $M,$ we need values, “$a$” for $x$ and “$b$” for $y,$ such that $P(a,b) =$ True. But then we can infer that $P(a,a) =$ True as well, provided that our interpretation satisfies the first formula. However, the latter makes it impossible for $M$ to satisfy the second formula, which states (if re-expressed with quantifier equivalences) that no pair of the form $(a,a)$ is in $P^M$ i.e. for no pair $(a,a), P$ is true.
Thus, there cannot be an interpretation $M$ that satisfies all three formulas.
For Practice - (Choosing any two formulas above, can you find interpretations that satisfy these two formulas?)(Comment your answer.)
Option D Explanation:
The formula set $\{ \forall x \exists y P(x,y), \forall x \neg P(x,x)\}$ is satisfied in a interpretation $M,$ if all the formulas in that set are satisfied by that same interpretation. Thus, we seek a interpretation, $M,$ that satisfies the two formulas
- $\forall x \exists y P(x,y)$ and
- $\forall x \neg P(x,x).$
The first formula states that $P$ is a "total" relation: for all values $a,$ there has to be some value $b$ such that $(a,b)$ is in $P^M.$ The second formula says that no pair of the form $(a,a)$ can be in $P^M.$ With these constraints at hand, we can easily construct an interpretation $M$ that satisfies both formulas:
- $A = \{a,b\};$
- $P^M = \{(a,b),(b,a)\}.$ (it means that $P(a,b), P(b,a)$ are true, but for other pairs, $P$ is not true.)
For Practice -
The formula set $\{ \exists x Q(x), \forall x \neg Q(x)\}$ is satisfied in an interpretation $M,$ if all the formulas in that set are satisfied by that same interpretation. Thus, we seek a interpretation, $M,$ that satisfies the two formulas
For the first formula to be satisfied in $M,$ we need a value a for $x$ such that a is in $Q^{M}.$ But the latter makes it impossible for $M$ to satisfy the second formula, which states (if re-expressed with quantifier equivalences) that no value $a$ is in $Q^{M}.$
Thus, there cannot be an interpretation $M$ that satisfies both formulas.
For Practice - (Can you find interpretations that satisfy one of these formulas?)(Comment your answer.)
