Dark Mode

179 views

3 votes

Working with a unary predicate symbol, $P,$ a binary predicate symbol $Q$ and a unary function symbol $f,$ consider the following interpretation $M,$ given by,

- Universe $A = \{a,b,c,d\};$
- $P^M = \{a,b\}$ (it means that $P(a),P(b)$ are true, and $P(c),P(d)$ are false)
- $Q^M = \{(a,b), (b,b), (c,b)\}$ (it means that $Q(a,b),Q(b,b),Q(c,b)$ are true, and for remaining pairs $Q$ is false)
- $f^M (a) = b, f^M (b) = b, f^M (c) = a,$ and $f^M (d) = c$

Which of the following formulas are satisfied in the interpretation $M?$

- $\forall x (P(x) \rightarrow \exists y Q(y,x))$
- $\forall x (Q(f(x),x) \rightarrow Q(x,x))$
- $\forall x \forall y (Q(x,y) \rightarrow P(x))$
- $\forall x \exists y (Q(x,y) \vee Q(y,x))$

3 votes

Option A Explanation:

The formula $\forall x (P(x) \rightarrow \exists y Q(y,x))$ is satisfied in the given interpretation if, and only if, for all values of $x$ that satisfy $P$ there is some value for $y$ such that $Q(y,x)$ holds. In this case, $a$ and $b$ are the only values which satisfy $P.$ So for each one of them we have to find some value for $y$ such that $Q(y,x)$ holds. For $x$ being $b,$ we may choose $a, b,$ or $c$ for $y$ to meet this requirement. However, for $x$ being $a,$ there is no value $y$ such that $(y,a)$ is in $Q^M.$ Thus, this formula is not satisfied in the given interpretation.

Option B Explanation:

the formula $\forall x (Q(f(x),x) \rightarrow Q(x,x))$ is satisfied in the given interpretation if, and only if, for all values of $x$ such that the pair $(f^M(x),x)$ is in $Q^M$ we also have that $(x,x)$ is in $Q^M.$ To determine whether this formula is satisfied in the given interpretation, we only have to verify the validity of the implication for all choices of $x,$ where $(f^M(x),x)$ is in $Q^M.$

- If the value of $x$ is $a,$ then the resulting pair $(f^M(a),a)$ is $(b,a)$ and not in $Q^M.$ There is nothing to check in this case.
- If the value of $x$ is $b,$ then the resulting pair $(f^M(b),b)$ is $(b,b)$ which is in $Q^M.$ Thus, we have to check whether $(b,b)$ is in $Q^M$ as well, but we already noted that.
- If the value of $x$ is $c,$ then the resulting pair $(f^M(c),c)$ is $(a,c)$ is not in $Q^M.$ There is nothing to check in this case.
- Finally, if the value of $x$ is $d,$ then the resulting pair $(f^M(d),d)$ is $(c,d)$ which is not in $Q^M.$ There is nothing to check in this case.

To summarize, we showed that the implication $Q(f(x),x) \rightarrow Q(x,x)$ holds for all choices of $x.$ Thus, the formula in question is satisfied in the given model.

Option C Explanation:

the formula $\forall x \forall y (Q(x,y) \rightarrow P(x))$ is satisfied in the given interpretation if, and only if, for all values of $x$ and $y$ such that the pair $(x,y)$ is in $Q^M$ we also have that $x$ is in $P^M.$ To determine whether this formula is satisfied in the given interpretation, we only have to verify the validity of the implication for all choices of $x$ and $y,$ where $(x,y)$ is in $Q^M$ (why?).

- If the value of $x$ is a and the value of $y$ is $b,$ then $a$ is in $P^M.$
- If the value of $x$ is $b$ and the value of $y$ is $b$ as well, then $b$ is in $P^M.$
- If the value of $x$ is $c$ and the value of $y$ is $b,$ then $c$ is not in $P^M.$

Thus, the last case demonstrated that the implication $Q(x,y) \rightarrow P(x)$ does not hold for all choices of $x$ and $y.$ Therefore, the formula in question is not satisfied in the given interpretation.

Option D Explanation:

the formula $\forall x \exists y (Q(x,y) \vee Q(y,x))$ is satisfied in the given interpretation if, and only if, for all values of $x$ we can find a value for $y$ such that the pair $(x,y)$ or the pair $(y,x)$ is in $Q^M.$ Thus, we need to verify this for all possible choices of $x.$

- If the value of $x$ is $a,$ then $(a,b)$ is in $Q^M$ and we therefore may choose $y$ to be $b.$
- If the value of $x$ is $b,$ then $(a,b), (b,b),$ and $(c,b)$ are in $Q^M;$ therefore may choose $y$ to be $b, b,$ or $c,$ respectively.
- If the value of $x$ is $c,$ then $(c,b)$ is in $Q6M;$ therefore may choose $y$ to be $b.$
- Finally, if the value of $x$ is $d,$ there is no pair in $Q^M$ whose first or second component equals $c;$ therefore we cannot find a value for $y$ to make the disjunction $Q(x,y) \vee Q(y,x)$ true for the given value of $x.$

Thus, the last case demonstrated that, given that $x$ has value $d,$ the disjunction $Q(x,y) \vee Q(y,x)$ is false for all values of $y.$ Therefore, the formula in question is not satisfied in the given interpretation.

For Practice, consider the formula $\forall x Q(f(x),x) :$

the formula $\forall x Q(f(x),x)$ is satisfied in the given interpretation if, and only if, for all values of $x$ the pair $(f^M(x),x)$ is in $Q^M.$ To answer this, we simply compute all these pairs.

- If the value of $x$ is $a,$ then the resulting pair is $(f^M(a),a),$ which is $(b,a).$ Since this pair is not in $Q^M,$ we already see that the formula is not satisfied in the given interpretation. Thus, there is no need to generate the remaining pairs.