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

\begin{document}
\maketitle
\section*{\underline{Homework 4}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 1}

Build the truth tables for the Boolean expressions:
\begin{itemize}
\item [a)] $\Bar{A}{B}$
\item [b)] $\overline{A\bar{B}}$
\item [c)] $A+\Bar{B}$
\item [d)] $\overline{A+\bar{B}}$
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 2}

An engineer hands you a piece of paper with the following Boolean expression on it, and tells you to build a gate circuit to perform that function:
\begin{eqnarray*}
A\Bar{B}+\Bar{C}(A+B)
\end{eqnarray*}
Draw a logic gate circuit for this function Represent its table of truth.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 3}

Suppose we wished to have an OR gate for some logic purpose, but did not have any OR gates on hand. Instead, we only had NAND gates in our parts collection. Draw a diagram whereby multiple NAND gates are connected together to form an OR gate.

\emph{(Hint: the NOT gate can be formed using:)}

\begin{figure}[!h]
\centering
\includegraphics[width=3in]{HW3_3}
\end{figure}

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 4}

Design a circuit that implements majority voting for three individuals (i.e. the ouput of the circuit is 1 if two at least of the inputs are 1, and 0 otherwise).
Build its truth table. (\emph{Hint: consider the Boolean expression $(A+B)\cdot C + (A+C)\cdot B$}).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 5}

On the fabled island of Knights and Knaves, we meet three people, John, Kari, and Tania, one of whom is a knight, one a knave, and one a spy. The knight always tells the truth, the knave always lies, and the spy can either lie or tell the truth.
\begin{center}
John says: ``Tania is a knave"\\
Kari says: "John is the knight"\\
Tania says: "I am the spy"
\end{center}
What are John, Kari, and Tania?

\end{document}

