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.