\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{psfrag}
\usepackage{subfigure}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amssymb}

\newcommand{\vect}[1]{\mathbf{#1}}

\usepackage[top = 2.55cm, bottom=2.55cm, left = 2.55cm , right = 2.55cm]{geometry}

\makeatletter

\makeatother

\usepackage{color, graphics, times, mathptm}

\definecolor{light}{gray}{0.75}

\usepackage{fancyhdr}
 
\pagestyle{fancy}
\fancyhf{}
\rhead{ \textbf{CSE140 Exam 1, Week 4, 2021} \hspace{1cm}
Name\hspace{4cm}}
\rfoot{Page \thepage}

\begin{document}
This is a take-home exam. You are allowed to check books, notes, and conduct an internet search.
However, you are expected to work on the solution by yourself. 
No discussion with anyone else is allowed.

There are two parts to the exam. Part A weighs 90 points.
Part B weighs 10 points. However, in Part B, the total weight of the problems
is higher than 10 points. You are encouraged to earn up to 
10 points. In other words, there is no penalty on
wrong solutions in Part B, but the maximum points to earn are limited to 10 points.

Please read the following instructions carefully.
If you are unclear about any of the questions on the exam,
make the most plausible assumption to answer the question.
Instructors and proctors will not answer questions on the exam material.
{\textbf{All the Best!}} \\

\noindent
{\LARGE Part A: (90 pts)}

\section{True or False}
Check if the following statements are True or False.
State your choice and use one sentence to explain your choice. (2 pts each)

\noindent
1. In Boolean algebra, if $xy=xz$, then $y=z$, where $x,y,z$ are three Boolean
variables.

\noindent
2. In Boolean algebra, if $x+y=xy$, then $x=y$, where $x, y$ are two 
Boolean variables.

\noindent
3. In Boolean algebra, if $x+y=1$, $xy=0$ and $x+z=1$, $xz=0$, then $y=z$, 
where $x, y, z$ are three Boolean variables.

\noindent
4. Karnaugh map: In a Karnaugh map, it is possible that none of the prime implicant
is essential.

\noindent
5. Universal set: $\{AND, OR\}$ is a universal set.

\noindent
6. Universal set: $\{f(x,y,z)=xyz'\}$ is a universal set.

\noindent
7. Universal set: $\{f(x,y,z)=xyz+x'y' \}$ is a universal set.


\section{CMOS Circuits}
Design a CMOS gate with function $y(a, b, c, d) = [(a+b)cd]'$.
Draw the schematic diagram using NMOS and PMOS transistors as the basic elements.
(16 pts)

\section{Boolean Algebra}
Simplify the following two Boolean functions and state the laws/theorems in
your derivation. 

\noindent
1. $f(a,b,c)=ab'+a'b'c+b'c$. (10 pts)

\noindent
2. $f(a,b,c)=(a+bc)(a'+b'c')(bc+b'c')$. (10 pts)

\section{Karnaugh Map}
\subsection{Sum of Products Expressions}
\label{K-map_SoP}
Use Karnaugh map to simplify function
$f(a,b,c) = \sum m(0,1,6) + \sum d(3,4,7)$. 

\noindent
Write the K-map and list all possible minimal sum of products expressions.
No need for the logic diagram. (10 pts)

\subsection{Product of Sums Expressions}
\label{K-map_PoS}
Use Karnaugh map to simplify function
$f(a,b,c) = \sum m(1,3,4) + \sum d(2,5)$. 

\noindent
Write the K-map and list all possible minimal product of sums expressions.
No need for the logic diagram. (10 pts)

\section{Other Types of Gates}

Consider the function $f(x,y)$ where $\bigoplus$ is an Exclusive OR operator and
the priority of the operators is AND (first), Exclusive OR and OR (last):

\indent
$f(x,y)= (xy)\bigoplus (x'+y') \bigoplus y \bigoplus x \bigoplus (xy) \bigoplus (x'y')$.

\noindent
Simplify the function into a minimal sum of products expression using switching
function techniques e.g. Shannon's expansion. Show your derivation.
Write the solution in a Boolean expression. (20 pts)

\vspace{4mm}
\noindent
{\LARGE Part B: (10 pts)}
8
In Part B, the total weight of the problems
is higher than 10 points. You are encouraged to earn up to 
10 points. In other words, there is no penalty on
wrong solutions, but the maximum points to earn are limited to 10 points.
Note that some problems are open, i.e. exact (perfect) solutions may be challenging to derive.
Nonetheless, the principles taught in the class can be used to start the exploration.\\

\noindent
{\textbf B.1. Boolean Algebra:}
In the framework of Boolean algebra, we would like to construct a "$-$" operator such that
$(x+y)-y=x$, where $x, y$ are Boolean variables. 
In other words, "$-$" is an inverse operator of the "$+$" operator.
Is it possible to construct using Boolean algebra?
State your choice of Yes or No. Explain your solution with no more than four sentences.
(5 pts)\\

\noindent
{\textbf B.2. Voting machine:}
Given a nine input function $f(a_8, a_7, a_6, a_5, a_4, a_3, a_2, a_1, a_0)$, construct
the function according to the following specification using a minimal network of
AND, OR, NOT gates. Assuming that NOT gate is free. The network can have more
than two levels of gates.
Show your designs with logic diagrams.
(5 pts)

\noindent
i. Function $f=1$, when one or more inputs are true, otherwise, $f=0$.

\noindent
ii. Function $f=1$, when two or more inputs are true, otherwise, $f=0$.

\noindent
iii. Function $f=1$, when five or more inputs are true, otherwise, $f=0$ (a majority function).\\

\noindent
{\textbf B.3. Karnaugh Map:}
Given a four input combination function $f(a,b,c,d)$, we have On-Set $F=$$ \sum m(2,3,5,6, 8,9, 12, 15)$ and an empty Don't-Care set. Implement the function with \{AND, XOR, NOT\}
gates only (no other gates). 
Assuming that we can have multiple (more than 2) input gates and NOT gates are free. Design with a minimal networks in terms of
the total number of AND, XOR gates.
Draw a logic diagram to illustrate the design. (5pts)\\

\noindent
{\textbf B.4. Quantum Computing:}
Quantum computing machine is a potential technology for digital logic designs.
(5 pts)

\noindent
B.4.1. Given a three-input, three-output quantum gate
$f(a, b, c)=(a, b, (ab)\bigoplus c)$,
can $\{f(a, b, c)\}$ be a
universal set? State your choice of Yes or No. Explain your choice.

\noindent
B.4.2. Given the output of the
quantum gate in B.5.1, can we
recover the input?
State your choice of Yes or No.
If Yes, provide your formula to recover
the input. If No, explain your choice.

\noindent
B.4.3. Predict the potential impact on the computing industry and new
start-up opportunities due to the quantum computing technologies.
Limit your answer to four sentences.

\end{document}