\documentclass[11pt]{article}

\usepackage{times,mathptm}
\usepackage{pifont}
\usepackage{exscale}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{epsfig}

\textwidth 6.5in
\textheight 9in
\oddsidemargin -0.0in
\topmargin -0.0in

\parindent 0pt     
\parskip 0pt	   

\begin{document}

\begin{center}             
\begin{LARGE}
{\bf CSci 243 Example Solutions}
\end{LARGE}
\vskip 0.25cm      

Last Updated: \today 
\end{center}


\begin{enumerate}

\item Write the truth table definitions for logical operators $\lnot$, $\land$ $\lor$, $\oplus$, $\rightarrow$, and $\leftrightarrow$. \\

\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline
$p$ & $q$ & $\lnot p$ & $p\land q$ & $p\lor q$ & $p\oplus q$ & $p\rightarrow q$ & $p\leftrightarrow q$ \\ \hline
T   & T   & F         & T          & T         & F         & T                & T                    \\
T   & F   & F         & F          & T         & T         & F                & F                    \\
F   & T   & T         & F          & T         & T         & T                & F                    \\
F   & F   & T         & F          & F         & F         & T                & T                    \\ \hline
\end{tabular}


\item Using logical identities and laws, show the logic equivalence of $\lnot(p\lor(\lnot p\land q))$ and $\lnot p\land\lnot q$ \\
\begin{align*}
\lnot(p\lor(\lnot p\land q)) 
&\equiv \lnot p\land\lnot(\lnot p\land q)         &\text{De Morgan's Law} \\
&\equiv \lnot p\land(\lnot(\lnot p)\lor\lnot q)  &\text{De Morgan's Law} \\
&\equiv \lnot p\land(p\lor\lnot q)               &\text{Double Negative} \\
&\equiv (\lnot p\land p)\lor(\lnot p\land\lnot q) &\text{Distribution} \\
&\equiv \text{F}\lor(\lnot p\land\lnot q)         &\text{Negation} \\
&\equiv (\lnot p\land\lnot q)\lor\text{F}         &\text{Commutative} \\
&\equiv \lnot p\land\lnot q                       &\text{Identity} 
\end{align*}

\item  Show $\overline{A\cup B} \subseteq \overline{A} \cap \overline{B}$ (a subset proof). Note: a technical proof can aid in the writing of a descriptive proof. \\

Technical Proof:
\begin{align*}
\forall x \in \overline{A\cup B}
&\Rightarrow x \not\in A \cup B									&\text{defintion of complement}\\
&\Rightarrow \lnot (x \in A \cup B)								&\text{property of not}\\
&\Rightarrow \lnot (x \in A \lor x \in B)						&\text{definition of union}\\
&\Rightarrow \lnot (x \in A) \land \lnot (x \in B)				&\text{logical De Morgan's} \\
&\Rightarrow x \in \overline{A} \land x \in \overline{B}		&\text{definition of complement}\\
&\Rightarrow x \in \overline{A} \cap \overline{B}    			&\text{definition of intersection} 
\end{align*}
Therefore $\overline{A\cup B} \subseteq \overline{A} \cap \overline{B}$ \\

Descriptive Proof: \\  For any element $x$ in the set $\overline{A\cup B}$, $x$ will not be in $A \cup B$ by the definition of complement.  Then is is not the case that $x\in A$ or $x\in B$, by the definition of a union.  By De Morgan's, it must be the case that $x\not\in A$ and $x\not\in B$.  Then by the definition of complement, $x\in \overline{A}$ and $x\in \overline{B}$.  Thus by the definition of intersection, $x$ must be in $\overline{A} \cap \overline{B}$.

\newpage %Too little of the next problem shows of the first page, so start a new page

\item Show by induction that $\sum_{i=1}^n i = \frac{1}{2}n(n+1)$. \\

Proof: Let $P(n)$ be the statement $\sum_{i=1}^{n} i = \frac{1}{2} n(n+1)$.

Base Case: $P(1)$ is the statement $\sum_{i=1}^1 i = 1 = \frac{1}{2}(1)(1+1)$ is true. 

Induction Hypothesis: Assume $P(k)$, $\sum_{i=1}^{k} i = \frac{1}{2} k(k+1)$, is true for some $k \geq 1$.

Show $P(k+1)$ is true: 
\begin{align*}
\textstyle\sum_{i=1}^{k+1} i 
&= \textstyle\sum_{i=1}^k i + (k+1) \\
&= \textstyle\frac{1}{2}k(k+1) + (k+1) 					& \text{by Induction Hypothesis} \\
&= \textstyle\frac{k(k+1)}{2} + \frac{2(k+1)}{2} \\
&= \textstyle\frac{(k+2)(k+1)}{2} \\
&= \textstyle\frac{1}{2} (k+1)(k+2)
\end{align*}

\item Write pseudocode for finding the maximum number in a list of integers.

\texttt{Algorithm findMax($a_1, a_2, \ldots, a_n$: integers)(output x: integer) \\
\hspace*{2em} max := $a_1$ \\
\hspace*{2em} for $i$ := 2 to $n$ \\
\hspace*{4em} if max $<$ $a_i$, then max := $a_i$ \\
\hspace*{2em} return max 
}

or

\begin{verbatim}
Algorithm findMax(a1, a2, ..., an: integers)(output x: integer)
   max := a1
   for i := 2 to n
      if max < ai, then max := ai
   return max
\end{verbatim}


\end{enumerate}

\end{document}
