% 
% 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 2022)}
\date{\today}
\author{Patrice Koehl\\koehl@cs.ucdavis.edu}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Part I: logic (1 question, 10 points)} 

\textcolor{blue}{\emph{Using a truth table, establish if the poposition below if it is a tautology, a contradiction or neither.}}

\textcolor{blue}{\emph{$(p \rightarrow q) \leftrightarrow ( \lnot q \rightarrow \lnot p)$}}

\begin{table}[!h]
\begin{tabular}{| c | c | c | c | c | c | c |}
\hline
$p$ & $q$ & $p\rightarrow q$ & $\lnot q$ & $\lnot p$ & $\lnot q\rightarrow \lnot p$ & $(p\rightarrow q)\leftrightarrow (\lnot q\rightarrow \lnot p)$\\ 
\hline
T & T & \textcolor{blue}{T} & \textcolor{blue}{F} & \textcolor{blue}{F} & \textcolor{blue}{T} & \textcolor{red}{T}\\ 
T & F & \textcolor{blue}{F} & \textcolor{blue}{T} & \textcolor{blue}{F} & \textcolor{blue}{F} & \textcolor{red}{T}\\ 
F & T & \textcolor{blue}{T} & \textcolor{blue}{F} & \textcolor{blue}{T} & \textcolor{blue}{T} & \textcolor{red}{T}\\ 
F & F & \textcolor{blue}{T} & \textcolor{blue}{T} & \textcolor{blue}{T} & \textcolor{blue}{T} & \textcolor{red}{T}\\ 
\hline
\end{tabular}
\end{table}

Therefore the proposition $(p \rightarrow q) \leftrightarrow ( \lnot q \rightarrow \lnot p)$ is a tautology.

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

\begin{itemize}

\item [1)] \textcolor{blue}{\emph{Prove that if $7n^2+4$ is even, then $n^2+2$ 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^2+2$ is even & $\lnot q: n^2+2$ is odd
 \end{tabular}
\end{center}

We use a direct proof:

We assume that $p$ is true, i.e. that $7n^2+4$ is even. There exists an integer $k$ such that $7n^2+4 = 2k$. Let us first rewrite:

\begin{eqnarray*}
7n^2 + 4 &=& 6n^2 + 2 + n^2+2 
\end{eqnarray*}
We then have:
\begin{eqnarray*}
2k = 6n^2+2 + n^2+2
\end{eqnarray*}
and therefore
\begin{eqnarray*}
n^2+2 &=& 2k - 6n^2 -2 \\
&=& 2(k-3n^2-1)
\end{eqnarray*}

As $k-3n^2-1$ is an integer, $n^2+2$ is even, and therefore $q$ is true.

We have shown that $p \rightarrow q$ is true using a direct proof.

\item [2)] \textcolor{blue}{\emph{Let $n$ be a natural number. Use a direct proof to show that if $6n^2+3n+11$ is odd, then $n$ 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: 6n^2+3n+11$ is odd &\\ 
 $q: n$ is even &
  \end{tabular}
\end{center}

We use a direct proof:

We assume that $p$ is true, i.e. that $6n^2+3n+11$ is odd. There exists an integer $k$ such that $6n^2+3n+11 = 2k+1$, which we rewrite:

\begin{eqnarray*}
6n^2+3n+11 &=& 2k+1 \\
n + 6n^2 + 2n + 11 &=& 2k + 1 \\
n &=& 2k + 1 - 6n^2 - 2n - 11 \\
n &=& 2k - 6n^2 - 2n -10 \\
n&=& 2(k-3n^2-n-5)
\end{eqnarray*}

As $k-3n^2-n-5$ is an integer, $n$ is even, and therefore $q$ is true.

We have shown that $p \rightarrow q$ is true using a direct proof.

\item [3)] \textcolor{blue}{\emph{Let $n$ be a natural number. Use a proof by contradiction to show that $\sqrt{4n+2}$ is not an integer.}}

\vspace{0.1in}

We use a proof by contradiction. If $p$ is the proposition, ``$\sqrt{4n+2}$ is not an integer", then $\lnot p$ is the proposition ``$\sqrt{4n+2}$ is an integer".

We assume that $\lnot p$ is true. There exists an integer $k$ such that $\sqrt{4n+2}=k$.
After squaring,
\begin{eqnarray*}
k^2 &=& 4n+2 \\
&=& 2(2n+1)
\end{eqnarray*}
 As $2n+1$ is an integer, $k^2$ is even, and therefore $k$ is even (prayer).

As $k$ is even, there exists an integer $l$ such that $k=2l$. Replacing above,
\begin{eqnarray*}
(2l)^2 &=& 4n+2 \\
4l^2 &=& 4n+2
\end{eqnarray*}
After division by 2,
\begin{eqnarray*}
2l^2 &=& 2n+1
\end{eqnarray*}
As $l$ is an integer, $2l^2$ is even. Similarly, as $n$ is an integer, $2n+1$ is odd. This leads to a contradiction, as an even number can't be equal to an odd number.
Therefore it is false that $\lnot p$ is false, and $p$ is true.

We have shown $p$ is true using a proof by contradiction.

\item [4)] \textcolor{blue}{\emph{Let $a$ and $b$ be 2 integers. Use a direct proof to show that if $a^2+b^2$ is even, then $a^2-b^2$ 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+b^2$ is even &\\ 
 $q: a^2-b^2$ is even &
  \end{tabular}
\end{center}

We use a direct proof:

We assume that $p$ is true, i.e. that $a^2+b^2$ is even. There exists an integer $k$ such that $a^2+b^2 = 2k$. Let us first rewrite:

\begin{eqnarray*}
a^2-b^2 &=& a^2+b^2 - 2b^2 \\
&=& 2k - 2b^2 \\
&=& 2(k-b^2) 
\end{eqnarray*}

As $k-b^2$ is an integer, $a^2-b^2$ is even, and therefore $q$ is true.

We have shown that $p \rightarrow q$ is true using a direct proof.

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Part III: knights and knaves (1 question, 10 points)} 

\textcolor{blue}{\emph{A very special island is inhabited only by Knights and Knaves. Knights always tell the truth, while Knaves always lie. You meet three inhabitants: Alex, John and Sally. Alex says, ``John is a Knight if and only if Sally is a Knave". John says, ``If Sally is a Knight, then Alex is a Knight". Can you find what Alex, John, and Sally are? Explain your answer.}}

\newpage

Let us build the table for the possible options for Alex, John, and Sally. We then check the validity of the two statements, and finally check the consistency of the truth values for those statements with the nature of Alex and John.

\begin{table} [!h]
\begin{center}
\begin{tabular}{c c c c c c c}
\hline \\
Line  & Alex  & John  & Sally & Alex says & John says & Compatibility \\
\hline \\
1 & Knight & Knight & Knight & F & T &  No: Alex would be a Knight who lies\\
2 & Knight & Knight & Knave & T & T & Yes \\
3 & Knight & Knave & Knight & T & T & No, John would be a Knave who tells the truth\\
4 & Knight & Knave & Knave & F & T &  No, John would be a Knave who tells the truth\\
5 & Knave & Knight & Knight & F & F & No, John would be a Knight who lies\\
6 & Knave & Knight & Knave & T & T & No, Alex would be a Knave who tells the truth \\
7 & Knave & Knave & Knight & T & F &  No, Alex would be a Knave who tells the truth\\
8 & Knave & Knave & Knave & F & T & No, John would be a Knave who tells the truth \\
\hline
\end{tabular}
\end{center}
\end{table}

Therefore Alex and John are Knights and Sally is a Knave.


\end{document}