\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, hyperref,varwidth,wasysym}
\pagestyle{empty}
\newcommand{\st}{~\mid~}
\newcommand{\bAlg}[1]{\begin{center}\begin{varwidth}{\textwidth}
#1
\begin{enumerate}\setlength{\itemsep}{-3pt}}
\newcommand{\eAlg}{\end{enumerate}\end{varwidth}\end{center}}
%\name{}
\assignment{CSE 20 Homework 2}
\duedate{Due: October 14, 2017 at 11pm}
\begin{document}
\begin{center}
\begin{minipage}[t]{6in}
\rule{\linewidth}{2pt}
{\sc Topics} Number representation, Logic, and Circuits
\newline
{\sc Reading} Rosen Section 4.1: pages 237-240, (up to but not including Modular Arithmetic),
Section 4.2: pages 245-253 (up to but not including Modular Exponentiation),
Sections 1.1, 1.2, 1.3 (up to page 31).
\newline
{\sc Key Concepts} Base expansion, decimal expansion, binary expansion,
hexadecimal expansion, octal expansion, bit shift, DIV, MOD.
Proposition, propositional variable, truth value, compound propositions,
truth table, negation, conjunction, disjunction, exclusive or, conditional statements,
converse, contrapositive, inverse,
biconditional, bitwise operations, consistent specifications, logical equivalence,
De Morgan's laws.\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.] ({\bf 6 points}) You have one thousand $\$1$ bills. How can you
distribute them among ten envelopes so that any amount between $\$1$ and $\$1000$,
inclusive, can be given as some combination of these envelopes? No change is allowed,
and you are not allowed to open any of the envelopes once you've determined how many
bills to put in each at the start.
\begin{itemize}
\item[a.] For each of the ten envelopes, say specifically how many $\$1$ bills
you will put in it. Justify your approach.
\item[b.] Explain how you will use (some of) the envelopes to give $\$ 142$.
\item[c.] Explain how you will use (some of) the envelopes to give $\$ 917$.
\end{itemize}
\end{problem}.
\begin{problem}[2.] ({\bf 9 points})
In this question, you will construct a circuit that takes a pair of
fixed width two-bit representations $(x_1 x_0)_2$ and
$(y_1y_0)_2$ and computes the four output bits for their integer product.
For example, the product of $(10)_2$ and $(11)_2$ is $(110)_2$ and could be computed by
long multiplication as
\begin{align*}
& 1~0 \qquad \text{This is $x_1 x_0$}\\
\times ~& 1~1 \qquad \text{This is $y_1 y_0$}\\
\overline{\phantom{x}}&\overline{\phantom{x y z}}\\
& 1~0 \\
+ 1~& 0~ \\
\overline{\phantom{x}}&\overline{\phantom{x y z}}\\
1~& 1~0 \qquad \text{This is the product, whose four output bits will be $0110$}.
\end{align*}
\begin{itemize}
\item[a.] Express the two-bit output of multiplying $y_0$ with $(x_1 x_0)_2$ as two compound
propositions: one for the least significant bit, call it $a_0$, and one of the most significant bit, call it $a_1$.
\item[b.] Use part a. and our work in class on adding integers in binary to express each of the
four bits of output as compound propositions with inputs $x_0, x_1, y_0, y_1$.
\item[c.] Draw a logic circuit with four inputs and four outputs implementing your design in part b.
{\it Note: the logic circuit may include the gates for AND, OR, and XOR, and each gate
may have as many inputs as you need.}
\end{itemize}
\end{problem}
\begin{problem}[3.] ({\bf 9 points}) Which of the following compound propositions
are {\bf tautologies}, which are {\bf contradictions}, and which are {\bf neither} (contingencies).
Justify your answer for each.
\begin{itemize}
\item[a.] $\neg q \vee ( p \wedge q)$
\item[b.] $(p \vee \neg q) \wedge (\neg p \vee q)$
\item[c.] $(\neg p \vee q) \vee (p \wedge q)$
\end{itemize}
\end{problem}
\begin{problem}[4.] ({\bf 6 points})
You are modeling a computer system which has three error flags: the COM flag is set to on when the computer is out of memory; the DEO flag is set to on when a disk error occurs; the NET flag is set to on when network connectivity is unreliable. Are the following system specifications {\bf consistent}?
\begin{quote}
If the computer is out of memory, then network connectivity
is unreliable. No disk errors can occur when the computer is out of memory.
\end{quote}
{\it For full credit, describe your model by associating propositional variables with each of your basic
propositions and then justify why the compound propositions that result from translating the system specifications
are or are not consistent.}
\end{problem}
\end{document}