Answer as many questions as you can.

1. Circle all the free variable occurrences in the following formula:

   $$\forall z. z \supset \boxed{x} \supset (\forall x. Px \land \exists y. Qxy) \lor Rz\boxed{x}$$

2. Perform the substitution $(\forall f. \exists y. P\,(f\,x\,y))[x \mapsto f\,y]$.
   Both $f$ and $y$ would get captured, so they must both be renamed. $$\forall g. \exists z. P\,(g\,(f\,y)\,z)$$
3. Write in logical notation the judgement: $0$ is the best number assuming that numbers exist and also assuming that the best number is unique. (Please note there are two assumptions here, not one assumption that is a conjunction of two claims.)
   Let $Nx$ be “$x$ is a number” and $Bx$ be “$x$ is the best number,” which means it is also a number (you get that with type inference, but if that bothers you, add $Nx$ and $Ny$ as conjuncts before $Bx$ and $By$). $$(\exists x. Nx),\; (\forall x. \forall y. (Bx \land By \supset x = y)) \;\vdash\; B\,0$$
4. In a many-valued logic, does the sentence “This sentence is false” have the truth value of true, false, both, or neither? (There is a best answer here that I am looking for, despite the fact that philosophers may disagree about it.)

   BOTH is the best answer. It obviously cannot be true-only or false-only, because if you assume the sentence is true then it’s false, and if you assume it’s false then it’s true. Therefore both truth values coexist.

   What about neither? This means you are committed to it being not true and not false. Interestingly, this is coherent and an acceptable answer for this exam. However, the reason for preferring both is that neither does not work for the related “This sentence is not true” (try it). This is beyond where we are now in class. Sigh.

5. What does it mean for a logical system to be sound, in terms of $\vdash$ and $\vDash$?
   If $\;\vdash A$, then $\;\vDash A$ (for every formula $A$).
6. Write (in the logic notation used in this class) an encoding of “No vampire will ever be able to see their own reflection in a mirror”.
   Let $Vx$ mean $x$ is a vampire, $Mx$ mean $x$ is a mirror, $Sxyz$ mean $x$ sees $y$ in $z$, and $rx$ is the reflection of $x$. $$\forall x. Vx \supset \forall y. (My \supset \lnot \lozenge\mathbf{F}(Sx(rx)y))$$
7. Write (in the logic notation used in this class) an encoding of “Every robot that once served a human is now obligated to obey the one who repaired it.”
   Let $Rx$ mean $x$ is a robot, $Hx$ mean $x$ is a human, $Sxy$ mean $x$ serves $y$, $Oxy$ mean $x$ obeys $y$, and $rx$ is the repairer of $x$. $$ \forall x. (Rx \land (\exists y. Hy \land \mathbf{P}(Sxy)) \supset \mathscr{O}(Ox(rx))) $$
8. Write (in the logic notation used in this class) an encoding of “Some prime number is greater than every number Tanya knows.”
   Let $Px$ mean $x$ is prime, $t$ mean Tanya. $$ \exists x. Px \land \forall y. \mathscr{K}_t y \supset x \gt y $$ Because $x$ is constrained to numbers by $P$, and we used $\gt$, then by type inference $y$ is a number, so we don’t need a special $\mathit{isNumber}$ predicate.