% 
% 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*{Exercise 1 \emph{(1 question, 10 points)}}

\textcolor{blue}{\emph{Let $a$ and $b$ be two real numbers, with $a\ne 0$ and $b \ne 0$. Use a proof by contradiction to show that if $ab>0$, then $\frac{a}{b}+\frac{b}{a}\ge 2.$}}

Let:

p: $ab >0$

\vspace{0.1in}
q: $\frac{a}{b}+\frac{b}{a} \ge 2$

\vspace{0.1in}
and let $A$ be the proposition $p \rightarrow q$. We want to show that A is true. We use a proof by contradiction, i.e. we suppose that what we want to show is false, namely that A is not true, i.e. $p$ is true AND $q$ is false.

$p$ is true: $ab > 0$. Similarly, as $q$ is false, $\frac{a}{b}+\frac{b}{a} < 2$. As $ab >0$, we can multiply this inequality by $ab$ without changing its sense; we get:

\begin{eqnarray*}
a^2 + b^2 < 2ab
\end{eqnarray*}
which gives
\begin{eqnarray*}
a^2+b^2-2ab < 0
\end{eqnarray*}
i.e.
\begin{eqnarray*}
(a-b)^2 < 0
\end{eqnarray*}
However, $(a-b)^2$ is a square, and therefore $(a-b)^2 \ge 0$. we have reached a contradiction. The proposition $A$ is therefore true.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 2 \emph{2 questions, each 10 points; total 20 points)}}

\begin{itemize}
\item [1)] \textcolor{blue}{\emph{Let $a$ and $b$ be two integers. Show that if $a+b\sqrt{2}=0$, then $a=0$ and $b=0$.}}

Let:

p: $a+b\sqrt{2}=0$

\vspace{0.1in}
q: $a=0$ and $b=0$

\vspace{0.1in}
and let $A$ be the proposition $p \rightarrow q$. We want to show that A is true. We use a proof by contradiction, i.e. we suppose that what we want to show is false, namely that $A$ is not true, i.e. $p$ is true AND $q$ is false.

As $q$ is false, either $a\ne 0$ or $b \ne 0$. As $b$ may be 0, we look at the two corresponding cases:
\begin{itemize}
\item[a)] $b=0$. Since $p$ is true, we get $a=0$. But this is in contradiction with $\lnot q$: we have reached a contradiction
\item[b)] $b \ne 0$. We can then divide by $b$ in $p$ and we obtain:
\begin{eqnarray*}
\sqrt{2} = \frac{-a}{b}
\end{eqnarray*}
As $-a$ and $b$ are integers, with $b\ne0$, this suggests that $\sqrt{2}$ is rational... but we know that this is not true. We have reached a contradiction. 
\end{itemize}
In all cases, we have reached a contradiction. The proposition $A$ is therefore true.

\item [2)] \textcolor{blue}{\emph{Let $m$, $n$, $p$, and $q$ be four integers. Show that  $m+n\sqrt{2}=p+q\sqrt{2}$, if and only if $m=p$ and $n=q$.}}

Let:

P: $m+n\sqrt{2}=p+q\sqrt{2}$

\vspace{0.1in}
Q: $m=n$ and $p=q$

\vspace{0.1in}
and let $A$ be the proposition $P \leftrightarrow Q$. We want to show that A is true. We prove both $P\rightarrow Q$ and $Q\rightarrow P$.

\begin{itemize}

\item [a)] Lest us prove $P\rightarrow Q$. We use a direct proof.

We assume $P$ is true, namely that
\begin{eqnarray*}
m+n\sqrt{2}=p+q\sqrt{2}
\end{eqnarray*}
which we rewrite as:
\begin{eqnarray*}
(m-p)+(n-q)\sqrt{2}=0
\end{eqnarray*}
As $m-p$ and $n-q$ are both integers, based on part 1, we find that $m-p=0$ and $n-q=0$, namely $m=p$ and $n=q$. Therefore $Q$ is true, and consequently $P\rightarrow Q$ is true.

\item [b)] Lest us prove $Q\rightarrow P$. We use a direct proof.

As $Q$ is true, $m=p$ and $n=q$. Then $m+n\sqrt{2}=p+q\sqrt{2}$, namely $P$ is true. Therefore $Q\rightarrow P$ is true.
\end{itemize}
We have shown that $P\rightarrow Q$ and $Q\rightarrow P$ are true. Therefore $A$ is true.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 3 \emph{(1 question, 10 points)}}

\textcolor{blue}{\emph{Let $x$ be a real number. Show that $|x-1| \le x^2-x+1$, where $| |$ is the absolute value.}}

Let:

P: $|x-1| \le x^2-x+1$

\vspace{0.1in}
where $x$ is a real number. Let us define $A(x) = |x-1|$ and $B(x) = x^2-x+1$. To show that $P$ is true, we use a proof by case:
\begin{itemize}
\item [a)] $x\ge 1$. Then,
\begin{eqnarray*}
A(x) &=& x-1 \\
B(x) &=& x^2-x+1
\end{eqnarray*}
Therefore
\begin{eqnarray*}
A(x) -B(x) &=& x-1 - x^2 +x -1\\
&=& -(x^2-2x+1) -1 \\
&=& -(x-1)^2 -1 \\
&<& 0
\end{eqnarray*}
Therefore $A(x)\le B(x)$ and $P$ is true.
\item [b)] $x < 1$. Then,
\begin{eqnarray*}
A(x) &=& -x+1 \\
B(x) &=& x^2-x+1
\end{eqnarray*}
Therefore
\begin{eqnarray*}
A(x) -B(x) &=& -x+1 - x^2 +x -1\\
&=& -x^2 \\
&<& 0
\end{eqnarray*}
Therefore $A(x)\le B(x)$ and $P$ is true.
\end{itemize}
In al cases, $P$ is true.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 4 \emph{(1 question, 10 points)}}

\textcolor{blue}{\emph{Let $a$ and $b$ be two integers. Show that if $(a^2+b^2)^2$ is even, then $a+b$ is even.}}

Let:

p: $(a^2+b^2)^2$ is even

\vspace{0.1in}
q: $a+b$ is even

\vspace{0.1in}
and let $A$ be the proposition $p \rightarrow q$. We want to show that $A$ is true. We use a direct proof.

We assume that $(a^2+b^2)^2$ is even. Let $n = a^2+b^2$; $n$ is an integer. The assumption is therefore that $n^2$ is even. We know then that $n$ is even. Therefore $a^2+b^2$ is even, but this leads to $a+b$ is even, using the theorems we can assume to be true. Therefore $q$ is true, and $A$ is true by direct proof.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 5 \emph{(1 question, 10 points)}}

\textcolor{blue}{\emph{Let $a$ and $b$ be two real numbers. Show that if $a\ne -1$ and $b\ne -1$, then $a+b+ab\ne -1$.}}

Let:

p: $a\ne -1$ and $b\ne -1$

\vspace{0.1in}
q: $a+b+ab\ne -1$

\vspace{0.1in}
and let $A$ be the proposition $p \rightarrow q$. We want to show that $A$ is true. We use an indirect proof. We need to define first:
$\lnot p$: $a= -1$ or $b=-1$

\vspace{0.1in}
$\lnot q$: $a+b+ab= -1$

We assume $\lnot q$. Therefore $a+b+ab = -1$. Using the hint, we find $(a+1)(b+1)-1 = -1$, i.e. $(a+1)(b+1)=0$. This leads to $a=-1$ or $b=-1$, namely $\lnot p$ is true.
Therefore $A$ is true by indirect proof.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 6 \emph{(1 question, 10 points)}}

\textcolor{blue}{\emph{Let $a$ and $b$ be two integers. Show that $a^2-4b\ne 2$.}}

Let:

P: $a^2-4b\ne 2$

\vspace{0.1in}
where $a$ and $b$ are two integers. To show that $P$ is true, we use a proof by contradiction, namely we assume $P$ is false:
\begin{eqnarray*}
a^2 - 4b = 2
\end{eqnarray*}
We get:
\begin{eqnarray*}
a^2 = 2 + 4b = 2(1+2b)
\end{eqnarray*}
As $1+2b$ is an integer, $a^2$ is even, and therefore $a$ is even. There exists an integer $k$ such that $a=2k$. Replacing above, we get:
\begin{eqnarray*}
(2k)^2 - 4b &=& 2 \\
4k^2 - 4b &=& 2
\end{eqnarray*}
After division by 2,
\begin{eqnarray*}
2k^2 - 2b = 1
\end{eqnarray*}
$2k^2-2b=2(k^2-b)$ and since $k^2-b$ is an integer, $2k^2-2b$ is even. However, 1 is odd: we have reached a contradiction. Therefore $P$ is true.

\end{document}

