Dark Mode

157 views

3 votes

Recall that a "sentence/proposition" is a predicate logic formula that has no free variables.

In predicate logic, a set of sentences is satisfiable iff there is some interpretation in which all the sentences are satisfied.

Which of the following sets of sentences is satisfiable?

In predicate logic, a set of sentences is satisfiable iff there is some interpretation in which all the sentences are satisfied.

Which of the following sets of sentences is satisfiable?

- $\{\exists x Q(x), \forall x (Q(x) \rightarrow R(x)), \forall x \neg R(x)\}.$
- $\{ \exists y \forall x P(x,y), \forall x \neg P(x,x)\}.$
- $\{\forall x \forall y (P(x,y) \rightarrow P(y,y)), \forall x \neg P(x,x), \exists x \exists y (P(x,y)\}.$
- $\{ \forall x \exists y P(x,y), \forall x \neg P(x,x)\}.$

3 votes

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

- $x Q(x)$ and
- $x Q(x).$

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.)