\documentclass[11pt]{article}
\usepackage{header}
%%% Change these %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def
\title{HW 1}
\def
\due{Friday, September 2 at 10PM}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle
\fontsize{12}{15}
\selectfont
\begin{Questions}
%%% Include questions here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Question
\textbf{True or False}
(10 points)
\begin{Parts}
\Part For each question, circle whether the statement is true or false.
\begin{itemize}
\def
\itema{\item[T\quad F\quad]}
\itema $
\forall x
\in
\Z$, $x + 1
\in
\Z$.
\itema $
\forall x
\in
\Z$, if $
\frac{x}{2}
\in
\Z$ then $
\frac{x + 1}{2}
\in
\Z$.
\itema $
\forall x
\in
\Z$, if $
\frac{x}{2}
\not
\in
\Z$ then $
\frac{x + 1}{2}
\in
\Z$.
\itema $
\forall x
\in
\Z$, $
\exists y
\in
\Z
\ s.t.
\ xy = 1$.
\itema $
\forall x
\in
\Z$, $
\exists y
\in
\Q
\ s.t.
\ xy = 1$.
\end{itemize}
\Part Consider the expression $
\displaystyle
\sum_{i = 0}
^n f(i)$.
Circle each of the following expressions that it is equal to. Justify your answers.
\begin{itemize}
\item $f(0)
\cdot f(1)
\cdot f(2)
\cdots f(n-1)
\cdot f(n)$
\item $
\displaystyle
\sum_{i = 0}
^
{n-1}
( f(i) + f(n))$
\item $
\left(
\displaystyle
\sum_{i = 0}
^
{n-1}
f(i)
\right) + f(n)$
\item $f(0) + f(1) +
\cdots + f(n)$
\item $
\displaystyle
\sum_{i = 0}
^
{\lfloor\frac{n}{2} \rfloor}
f(i) +
\displaystyle
\sum_{j = \lfloor\frac{n}{2}\rfloor + 1}
^n f(j)$
\end{itemize}
\end{Parts}
\Question
\textbf{Watson Selection Task}
(3 points)
Suppose we have four cards on a table. Each card has a color
on one side (red, blue, or green) and a shape on the other
side (square, circle, or triangle).
Consider the following theory:
``If a card is red, then it has a square on the other side.''
Suppose the sides facing up are as follows: red, blue, square, triangle.
Which cards do you need to flip to test the theory?
\Question
\textbf{Prove or Disprove}
(8 points)
\begin{Parts}
\Part $A
\lor (B
\land C)
\equiv (A
\lor B)
\land (A
\lor C)$.
\Part $A
\land (B
\lor C)
\equiv (A
\land B)
\lor (A
\land C)$.
\Part $A
\implies (B
\land C)
\equiv (A
\implies B)
\land (A
\implies C)$
\Part $A
\implies (B
\lor C)
\equiv (A
\implies B)
\lor (A
\implies C)$
\end{Parts}
\Question
\textbf{Boolean Circuits}
(20 points)
Propositional logic and Boolean circuits\\
The exclusive OR (written as XOR or $
\oplus$ ) is just what it sounds like:
$P
\oplus Q$ is true when exactly one of $P,Q$ is true.
\begin{enumerate}
\item Show, using a truth table, that $P
\oplus Q$ is equivalent to $(P
\vee Q)
\wedge
\lnot{(P \wedge Q)}
$.
\item
Logic is key to many fundamental areas of computer science such as digital circuits. Below you can see the symbols for some of the common gates used in digital circuits. The wires all carry boolean values (true or false), and the ones coming in from the left are
\textit{input}
s and the ones exiting from the right are
\textit{output}
s.
\begin{center}
\includegraphics[scale = 0.7]{resources/circuit.pdf}
\end{center}
These gates, from left to right, are NOT, AND, and OR. Below you can find their truth tables
\begin{center}
\begin{tabular}{c|c}
$x$&$y$\\
\hline
false&true\\
true&false\\
\end{tabular}
\hspace{2cm}
\begin{tabular}{c|c|c}
$x_1$&$x_2$&$y$\\
\hline
false&false&false\\
false&true&false\\
true&false&false\\
true&true&true\\
\end{tabular}
\hspace{2cm}
\begin{tabular}{c|c|c}
$x_1$&$x_2$&$y$\\
\hline
false&false&false\\
false&true&true\\
true&false&true\\
true&true&true\\
\end{tabular}
\end{center}
Using these logical gates, implement XOR. Assume that two input wires $P$ and $Q$ are given to you. Connect them using AND, OR, and NOT gates and produce an output wire whose value is always $P
\oplus Q$. Draw the circuit you designed using the standard symbols for the gates.
\item (Optional)
Another common gate used in hardware chips, is the NAND gate, which can be thought of as an AND whose output is inverted. Below you can find the symbol and the truth table for the NAND gate.
\begin{center}
\includegraphics[scale = 0.7]{resources/nand.pdf}
\end{center}
\begin{center}
\begin{tabular}{c|c|c}
$x_1$&$x_2$&$y$\\
\hline
false&false&true\\
false&true&true\\
true&false&true\\
true&true&false\\
\end{tabular}
\end{center}
Implement XOR using the minimal number of NAND gates. You may only use NAND gates, and no other gate.
\end{enumerate}
\Question
\textbf{Equivalent or Not}
(9 points)
Determine whether the following equivalences hold, and give brief justifications for your answers. Clearly state whether or not each pair is equivalent.
\begin{Parts}
\Part (3 points) $
\forall x~
\exists y~
\big(P(x)
\Rightarrow Q(x,y)
\big)~
\equiv~
\forall x~
\big(P(x)
\Rightarrow(
\exists y~Q(x,y))
\big)$
\Part (3 points) $
\neg
\exists x~
\forall y~
\big(P(x,y)
\Rightarrow
\neg Q(x,y)
\big)~
\equiv~
\forall x~
\big( (
\exists y~P(x,y))
\land (
\exists y~Q(x,y))
\big)$
%
\Part (3 points) $
\neg
\exists x~
\forall y~
\big(P(x)
\Rightarrow
\neg Q(x,y)
\big)~
\equiv~
\forall x~
\exists y~
\big(P(x)
\land Q(x,y)
\big)$
%
%
\Part (3 points) $
\forall x~
\exists y~
\big(Q(x,y)
\Rightarrow P(x)
\big)~
\equiv~
\forall x~
\big((
\exists y~Q(x,y))
\Rightarrow P(x)
\big)$
\end{Parts}
\Question
\textbf{Counterfeit Coins}
(20 points)
\begin{Parts}
\Part (8 points)
Suppose you have $9$ gold coins that look identical, but you also know
one (and only one)
of them is counterfeit. The counterfeit coin weighs slightly less
than the others. You also have access to a balance scale to compare
the weight of two sets of coins --- i.e., it can tell you whether
one set of coins is heavier, lighter, or equal in weight to another
(and no other information). However, your access to this scale is
very limited.
Can you find the counterfeit coin using
{\em just two weighings}
?
Prove your answer.
\Part (12 points)
Now consider a generalization of the same scenario described above.
You now have $3^n$ coins, $n
\geq 1$, only one of which is counterfeit.
You wish to find the counterfeit coin with just $n$ weighings.
Can you do it? Prove your answer.
\end{Parts}
\Question
\textbf{Proof Checker}
(15 points)
In this question, you will play ``CS70 Grader'':
you are tasked with checking someone else's attempt at a proof.
For each of the ``proofs'' below, say whether you think it is correct or incorrect.
If you think the proof is incorrect, explain clearly and concisely where the logical error in the proof lies.
(If you think the proof is correct, you do not need to give any explanation.)
Simply saying that the claim (or the inductive hypothesis) is false is not a valid explanation.
\begin{Parts}
\Part
\textbf{Claim}
: for all $n
\in
\N$, $(2n+1$ is a multiple of $3)
\implies (n^2+1$ is a multiple of $3)$.
\textbf{Proof}
: proof by contraposition. Assume $2n+1$ is not a multiple of 3.
\begin{itemize}
\item If $n=3k+1$ for $k
\in
\N$, then $n^2+1=9k^2+6k+2$ is not a multiple of 3.
\item If $n=3k+2$ for $k
\in
\N$, then $n^2+1=9k^2+12k+5$ is not a multiple of 3.
\item If $n=3k+3$ for $k
\in
\N$, then $n^2+1=9k^2+18k+10$ is not a multiple of 3.
\end{itemize}
In all cases, we have concluded $n^2+1$ is not a multiple of 3, so we have proved the claim.
\Part
\textbf{Claim}
: for all $n
\in
\N$, $n<2^n$.
\textbf{Proof}
: the proof will be by induction on $n$.
\begin{itemize}
\item Base case: suppose that $n=0$. $2^0=1$ which is greater than $0$, so the statement is true for $n=0$.
\item Inductive hypothesis: assume $n<2^n$.
\item{n+1} Inductive step: we need to show that $n+1<2^
$. By the inductive hypothesis, we know that $n<2^n$. Plugging in $n+1$ in place of $n$, we get $n+1<2^
{n+1}
$, which is what we needed to show. This completes the inductive step.
\end{itemize}
\Part
\textbf{Claim}
: for all $x,y,n
\in
\N$, if $
\max(x,y)=n$, then $x
\leq y$.
\textbf{Proof}
: the proof will be by induction on $n$.
\begin{itemize}
\item Base case: suppose that $n=0$. If $
\max(x,y)=0$ and $x,y
\in
\N$, then $x=0$ and $y=0$, hence $x
\leq y$.
\item Inductive hypothesis: assume that, whenever we have $
\max(x,y)=k$, then $x
\leq y$ must follow.
\item Inductive step: we must prove that if $
\max(x,y)=k+1$, then $x
\leq y$. Suppose $x,y$ are such that $
\max(x,y)=k+1$. Then, it follows that $
\max(x-1,y-1)=k$, so by the inductive hypothesis, $x-1
\leq y-1$. In this case, we have $x
\leq y$, completing the induction step.
\end{itemize}
\end{Parts}
\Question
\textbf{Prove or Disprove}
(15 points)
Prove or disprove each of the following statements. For each proof, state which of the proof types (as discussed in Note~2) you used.
\begin{Parts}
\Part (3 points)
For all natural numbers $n$, if $n$ is odd then $n^2+3n$ is even.
\Part (3 points)
For all real numbers $a,b$, if $a+b
\ge 20$ then $a
\ge 17$ or $b
\ge 3$.
\Part (3 points)
For all real numbers $r$, if $r$ is irrational then $r+1$ is irrational.
\Part (3 points) For all natural numbers $n$, $10n^3>n!$.
\Part (3 points) For all natural numbers $a$ where $a^5$ is odd, then
$a$ is odd.
\end{Parts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{Questions}
\end{document}