\documentclass[11pt]{article}

\usepackage{hw}

\begin{document}

\dotitle{(Sample Midterm)}{: not due}

\begin{enumerate}

\item Let $A$ be the subset of natural numbers defined inductively by the following clauses:
\begin{itemize}
\item $1 \in A$
\item If $n \in A$, then $4n \in A$
\item If $n \in A$, then $n+2 \in A$
\end{itemize}

Show that 48 is an element of $A$ by giving a construction sequence.

Show that 11 is not an element of $A$.

Is $A$ freely generated? Justify your answer.

\item
 Remember that if $\ph$ and $\psi$ are any
propositional formulas and $p_i$ is a propositional variable, then
$\ph[\psi/p_i]$ is defined by recursion, as follows:
\begin{itemize}
\item If $\ph$ is a propositional variable $p_j$, then
\[
\ph[\psi/p_i] = \left\{
\begin{array}{ll}
  \psi & \mbox{if $i = j$} \\
  p_j & \mbox{otherwise}
\end{array}
\right.
\]
\item If $\ph$ is of the form $(\theta \mathop{\square} \eta)$, then
\[
\ph[\psi/p_i] = (\theta[\psi/p_i] \mathop{\square} \eta[\psi/p_i]).
\]
\item If $\ph$ is of the form $(\lnot \theta)$, then
\[
\ph[\psi/p_i] = (\lnot \theta[\psi/p_i]).
\]
\end{itemize}

Prove that for any formulas $\ph, \psi, \theta$ and variable $p$,  if $\models \psi \leftrightarrow \theta$ then $\models \ph[\psi/p] \limplies \ph[\theta/p]$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item Use algebraic means to put the following formula in disjunctive normal form (an ``and'' of ``or'''s):
\[
\lnot ((\lnot p_0 \lor p_1) \land (p_2 \limplies p_3))
\]


\item
Use truth tables to show the following.

$$(p\land q)\land r\limplies (p\lor r))$$

 is a tautology.

It is not the case that $p\lor q \models p\limplies q$.


\item
 Give natural deduction proofs of the following:

$$\lnot (\ph \land \lnot \psi)\limplies(\ph\limplies \psi)$$
and
$$(\ph \land \psi) \vdash \lnot (\ph \land \lnot \psi)$$


\item State the soundness theorem. Use soundness to show that the system of natural deduction is \emph{free from
    contradiction}, in the sense that not both $\vdash\varphi$ and
  $\vdash\neg\varphi$ hold, for any propositional formula
  $\varphi$. 

\item   Prove the completeness theorem, given the assumption that every consistent set of sentences has a model.

\item\addstar Suppose a set of sentences $\Gamma$ has no model.  Prove that then some finite subset of $\Gamma$ has no model.  (Hint: you may use soundness and completeness.)


\end{enumerate}

\end{document}