(15 points) Let $P, Q, R$ denote distinct propositional variables.
(a) Write the formula which $((P \wedge Q) \vee \neg R)$ abbreviates.
(b) Is $((\neg P \leftrightarrow Q) \vee(P \leftrightarrow Q))$ a tautology? Justify.
(c) Are $((R \rightarrow Q) \leftrightarrow P)$ and $(P \vee(\neg R \wedge \neg Q))$ truth equivalent? Justify.

(15 points) For any formula $\varphi$, let $V(\varphi)$ be the number of propositional variables occurring in $\varphi$ including repeats, and let $S(\varphi)$ be the number of brackets $(,$, and connectives $\neg, \rightarrow$ in $\varphi$. For example,
$$
\psi=\left(\left(P_{1} \rightarrow P_{2}\right) \rightarrow \neg P_{1}\right)
$$
has $V(\psi)=3$ and $S(\psi)=7$.
Prove that, for all formulas $\varphi, \varphi$ is not a propositional variable if and only if $V(\varphi) \leq S(\varphi)$.

(10 points) Let $P, Q, R$ be distinct propositional variables. Find the disjunctive normal form (DNF) of $((P \rightarrow(Q \wedge R)) \vee(\neg Q \wedge R))$.

(10 points) Decide whether the following argument is valid by first converting to a question of satisfiability of clauses, and then using the Davis Putnam Procedure (DPP).
$$
(P \wedge \neg R),(P \vee \neg Q),(P \rightarrow(Q \vee R)) \text {, therefore } Q
$$

(10 points) Determine whether the following set of Horn clauses is satifiable.
$$
{{P},{P, \neg R},{R, \neg W, \neg S},{Q},{\neg P, S},{\neg Q, W},{\neg P, \neg Q, \neg R},{\neg W, S}}
$$

(10 points) Let $P, Q, R, S, T$ be distinct propositional variables. Find an instance of 3 -SAT which is satisfiably equivalent to
$$
{{P},{P, Q, \neg R, S, \neg T},{\neg Q, \neg S}} .
$$

(20 points) Determine if the following proof system for propositional logic is sound and/or complete. Justify your answer for both.
Axioms: All tautologies.
Rules: If $\psi$ is a subformula of $\varphi$, then we can infer $\psi$ from $\varphi$.

(10 points) Let $\varphi$ be a propositional formula. By the completeness theorem, notice that ${\neg \neg \varphi} \vdash \varphi$. Write down a derivation of $\varphi$ from ${\neg \neg \varphi}$.

(25 points) Consider the first order language $\mathcal{L}=(R, g, f, c)$, where $R$ is a binary relation, $f$ is a binary function, $g$ is a 3 -nary function, and $c$ is a constant.
(a) Consider the interpretation $\mathcal{I}=(\mathcal{A}, \beta)$ of $\mathcal{L}$ with domain $A=\mathbb{R}, c^{\mathcal{A}}=-2, f^{\mathcal{A}}(x, y)=$ $x-y, g^{\mathcal{A}}(x, y, z)=x^{2}+y^{2}-z^{2}$, and $\beta\left(x_{i}\right)=-i$. Compute $\mathcal{I}\left(f g f x_{1} c c x_{2} x_{5}\right)$.
(b) Find an interpretation $\mathcal{I}$ such that $\mathcal{I} \neq \forall x_{3} R f x_{1} \operatorname{cg} x_{1} c x_{3}$.
(c) Find an interpretation $\mathcal{I}$ such that $\mathcal{I} \models \forall x_{3} R f_{1} \operatorname{cg} x_{1} c x_{3}$.

Consider the language of arithmetic $\mathcal{L}{\text {ar }}$. (a) (5 points) Translate the following English sentence into a statement in $\mathcal{L}{\text {ar }}$ “The only integer divisible by zero is itself.” You may not use the notation | to denote “divides”.
(b) (5 points) Translate the following formula into an English statement about the natural numbers.
$$
(\forall x(\exists y x \cdot y \approx x+1 \vee x \approx 1)
$$
(c) (10 points) For $\varphi=\forall a a<a+1$ and
$$
\Gamma={0<1, \forall x \forall y \forall z((x<y \wedge 0<z) \rightarrow z+x<z+y)}
$$
prove $\Gamma \models \varphi$.

Consider the language of graphs $\mathcal{L}={E}$, where $E$ is a binary relation. For all natural numbers $n$, we define the formula
$$
\begin{gathered}
\psi_{n}=\exists x \exists y \neg \exists v_{1} \cdots \exists v_{n-1}\left(\left(E x v_{1} \vee x \approx v_{1}\right) \wedge\left(E v_{1} v_{2} \vee v_{1} \approx v_{2}\right) \wedge\right. \
\left.\cdots \wedge\left(E v_{n-1} v_{n} \vee v_{n-1} \approx v_{n}\right) \wedge\left(E v_{n} y \vee v_{n} \approx y\right)\right) .
\end{gathered}
$$
We then make the following definition: we say that an interpretation $\mathcal{G}$ of $\mathcal{L}$ has finite