in Mathematical Logic recategorized by
157 views
3 votes
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?
  1. $\{\exists x Q(x), \forall x (Q(x) \rightarrow R(x)), \forall x \neg R(x)\}.$
  2. $\{ \exists y \forall x P(x,y), \forall x \neg P(x,x)\}.$
  3. $\{\forall x \forall y (P(x,y) \rightarrow P(y,y)), \forall x \neg P(x,x), \exists x \exists y (P(x,y)\}.$
  4. $\{ \forall x \exists y P(x,y), \forall x \neg P(x,x)\}.$
in Mathematical Logic recategorized by
157 views

1 Answer

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

edited by