% 
% hw1.tex
%
%   This is a LaTeX template to get you started
%   making problem-set solutions
%
 
\documentclass[11pt]{article}

\usepackage{amssymb,amsmath,pstricks,framed}
\usepackage{color}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textheight}{9.0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.5in}

% *** GRAPHICS RELATED PACKAGES ***
%

\usepackage[pdftex]{graphicx}
 \graphicspath{{./}}
 \DeclareGraphicsExtensions{.pdf,.jpeg,.png}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\bf Data, Logic, and Computing\\[2ex] 
       \rm\normalsize ECS 17 (Winter 2024)}
\date{\today}
\author{Patrice Koehl\\koehl@cs.ucdavis.edu}

\begin{document}
\maketitle
\section*{\underline{Midterm 2: solutions}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Part I: logic (2 questions, each 10 points; total 20 points)} 

\textcolor{blue}{\emph{Using truth tables, establish for each of the two propositions below if it is a tautology, a contradiction or neither.}}

\begin{itemize}

\item [1)] \textcolor{blue}{\emph{$(p \leftrightarrow q) \leftrightarrow ( \lnot p \leftrightarrow \lnot q)$}}

\begin{table} [h]
\begin{center}
\begin{tabular}{c c c c c c c}
\hline \\
$p$ & $q$ & $p \leftrightarrow q$ & $\lnot p$ & $\lnot q$ & $\lnot p \leftrightarrow \lnot q$ & $(p \leftrightarrow q) \leftrightarrow ( \lnot p \leftrightarrow \lnot q)$ \\
\hline \\
T & T & T & F & F & T & T \\
T & F & F & F & T & F & T \\
F & T & F & T & F & F & T \\
F & F & T & T & T & T & T \\
\hline
\end{tabular}
\end{center}
\end{table}

The proposition is a tautology.

\item[2)] \textcolor{blue}{\emph{$(p \rightarrow (q \land r)) \lor ((p \land q) \rightarrow r)$}}

\begin{table} [h]
\begin{center}
\begin{tabular}{c c c c c c c c}
\hline \\
$p$ & $q$ & $r$ & $q \land r$ & $p \rightarrow (q \land r)$ & $p \land q$ & $(p \land q) \rightarrow r$ & $(p \rightarrow (q \land r)) \lor ((p \land q) \rightarrow r)$ \\
\hline \\
T & T & T & T & T & T & T & T \\
T & T & F & F & F & T & F & F \\
T & F & T & F & F & F & T & T \\
T & F & F & F & F & F & T & T \\
F & T & T & T & T & F & T & T \\
F & T & F & F & T & F & T & T \\
F & F & T & F & T & F & T & T \\
F & F & F & F & T & F & T & T\\
\hline
\end{tabular}
\end{center}
\end{table}

The proposition is not a tautology.

\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Part II: proofs (5 questions, each 10 points; total 50 points)} 

\begin{itemize}

\item [1)] \textcolor{blue}{\emph{Prove that if $7n^2+4$ is even, then $n$ is even, where $n$ is a natural number.}}

\vspace{0.1in}
We want to prove an implication of the form $p \rightarrow q$ is true, with:

\begin{center}
\begin{tabular}{ c c }
 $p: 7n^2+4$ is even & $\lnot p: 7n^2 + 4$ is odd \\ 
 $q: n$ is even & $\lnot q: n$ is odd 
 \end{tabular}
\end{center}

We use an indirect proof:

We assume that $\lnot q$ is true, i.e. that $n$ is odd. There exists an integer k such that $n = 2k+1$. Then,

\begin{eqnarray*}
7n^2 + 4 &=& 7(2k+1)^2 + 4 \\
&=& 7(4k^2+4k+1) + 4 \\
&=& 28k^2 +28k +13 \\
&=& 2( 14k^2 + 14k + 6) + 1
\end{eqnarray*}

As $14k^2 + 14k + 6$ is an integer, $7n^2+4$ is odd, and therefore $\lnot p$ is true.

We have shown that $\lnot q \rightarrow \lnot p$ is true, therefore $p \rightarrow q$ is true.


\item [2)] \textcolor{blue}{\emph{2) Let $a$, $b$, and $c$ be consecutive integers with $a<b<c$. Show that if $a\neq -1$ and $a\neq 3$, then  $a^2 + b^2 \neq c^2$.}}

\vspace{0.1in}
We want to prove an implication of the form $p \rightarrow q$ is true, with:

\begin{center}
\begin{tabular}{ c c }
 $p:$ $a\neq -1$ and $a\neq 3$ & $\lnot p:$ $a= -1$ or $a=3$ \\ 
 $q: a^2 + b^2 \neq c^2$ & $\lnot q: a^2 + b^2 = c^2$
  \end{tabular}
\end{center}

Clearly, it is easier to use an indirect proof.

We assume that $\lnot q$ is true, i.e. that $a^2 + b^2 = c^2$. Recall that $a$, $b$, and $c$ are \textbf{consecutive integers }with $a<b<c$. Then:
\begin{eqnarray*}
b &=& a + 1 \\
c &=& b+1 = a+2
\end{eqnarray*}

Therefore, the equation $a^2 + b^2 = c^2$ becomes:

\begin{eqnarray*}
a^2 + b^2 &=& c ^2 \\
a^2+(a+1)^2 &=& (a+2)^2 \\
a^2 + a^2 + 2a + 1 &=& a^2 + 4a + 4 \\
a^2 -2a -3 &=& 0 \\
(a+1)(a-3) &=& 0
\end{eqnarray*}

whose solutions are  $a=-1$ or $a=3$, i.e. that $\lnot p$ is true. 

We have shown that $\lnot q \rightarrow \lnot p$ is true, therefore $p \rightarrow q$ is true.

\item [3)] \textcolor{blue}{\emph{Let $a$ and $b$ be two positive real numbers. Use a proof by contradiction to show that if $\frac{a}{b+1}=\frac{b}{a+1}$, then $a=b$.}}

\vspace{0.1in}
We want to prove an implication of the form $p \rightarrow q$ is true, with:

\begin{center}
\begin{tabular}{ c c }
 $p:$  $\frac{a}{b+1}=\frac{b}{a+1}$ & $\lnot p:$ $\frac{a}{b+1}\neq \frac{b}{a+1}$ \\ 
 $q: a = b$  & $\lnot q: a \neq b$
 \end{tabular}
\end{center}

We use a proof by contradiction:

We assume that $p$ is true, and $q$ is false. Since $p$ is true,
\begin{eqnarray*}
\frac{a}{b+1}&=&\frac{b}{a+1} \\
a(a+1) &=& b(b+1) \\
a^2 - b^2 + (a-b) &=& 0 \\
(a-b)(a+b+1) & = & 0
\end{eqnarray*}
As $q$ is false, $a\ne b$ and therefore $a-b \neq 0$. Therefore,
\begin{eqnarray*}
a+b = -1 
\end{eqnarray*}
However, $a$ and $b$ are both positive: we have reached a contradiction. Therefore $p\rightarrow q$ is true.

\item [4)] \textcolor{blue}{\emph{Prove that $n^2+n+9$ is odd for all integer $n$}}

\vspace{0.1in}
Let $n$ be an integer. We know that $n(n+1)=n^2+n$ is an even number. Therefore, there exists an integer $k$ such that:
\begin{eqnarray*}
n^2+n = 2k
\end{eqnarray*}
Therefore,
\begin{eqnarray*}
n^2+n +9 = 2k + 9 = 2(k+4) + 1
\end{eqnarray*}
Since k+4 is an integer, we have that $n^2+n+9$ is odd.

\item [5)] \textcolor{blue}{\emph{Let $a$ and $b$ be two integers. Use a direct proof to show that if $a^2+4b^2-4ab$ is even, then $a+2b$ is even.}}

\vspace{0.1in}
We want to prove an implication of the form $p \rightarrow q$ is true, with:

\begin{center}
\begin{tabular}{ c c }
 $p: a^2+4b^2 -4ab$ is even & $\lnot p: a^2+b^2 -4ab $ is odd \\ 
 $q: a+2b$ is even & $\lnot q: a+2b$ is odd 
 \end{tabular}
\end{center}

We use a direct proof:

We suppose that $p$ is true: there exists an integer $k$ such that $a^2+4b^2 -4ab = 2k$. Note that
\begin{eqnarray*}
(a+2b)^2 &=& a^2 + 4b^2 + 4ab \\
&=& 2k + 4ab + 4ab \\
&=& 2(k+4ab)
\end{eqnarray*}
Since $k+2ab$ is an integer, $(a+2b)^2$ is even. Therefore $a+2b$ is even (using the ``Prayer"), i.e. $q$ is true.

We have therefore shown that $p \rightarrow q$ is true.
\end{itemize}
\end{document}