\documentclass[12pt]{article}
\usepackage{comment}
\usepackage{amsmath}

\newcommand{\into}{{\rightarrow}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\Rpos}{{\sf R}^+}


\begin{document}

\centerline{\bf Homework 01, MORALLY Due Feb 5 at 10:00AM} 

\centerline{\bf DEAD-CAT DAY Feb 7, 10:00AM}

\begin{enumerate}


\item
(20 points)
Give a Propositional Formula on four variables that has exactly
three satisfying assignments.
Give the satisfying assignments.


\newpage 

\item
(20 points)
Use truth table so show that 

$$(x \vee y) \wedge z$$

is not equivalent to

$$x\vee (y\wedge z).$$

INDICATE which rows they differ on. 


\newpage

\item
(30 points)
$n$ has the {\it emily property} if there is a  formula on $n$ variables with
exactly $n^2+100$ satisfying assignments. 

\begin{enumerate}
\item
(15 points)
Fill in the BLANK in the following sentence

\bigskip

$n$ has the emily property IFF BLANK($n$).

\bigskip

The condition BLANK has to be simple, for example,
$n$ is divisible by 5 (thats not the answer). 

\item
(15 points)
Prove the statement you made in the first part.
Note that this means you have to show that

If BLANK($n$) then $n$ has the emily property

and

If NOT(BLANK($n$)) then $n$ DOES NOT have the emily property
\end{enumerate}










\newpage

\item
(30 points) 
(NOTE: 0 and 1 are NOT prime. You will need that for this problem.) 
\begin{enumerate}
\item
(15 points)
View the input $x,y,z$ as the number in binary $xyz$ which we denote $(xyz)$. 
For example, $100$ is 4. 

Write a Truth Table for the following function with 3 inputs $x,y,z$ and 1 output $a$. 

\begin{equation*}
f(x,y,z) = 
\begin{cases}
0  & \hbox{if $(xyz)$ is NOT PRIME.} \cr
1  & \hbox{if $(xyz)$ is PRIME.} \cr
\end{cases}
\end{equation*} 

\item
(15 points) 
Convert your truth table into formulas.
DO NOT SIMPLIFY.

\item
(0 points- DO NOT HAND IN)
Draw a circuit that computes that truth table. 
\end{enumerate}



\end{enumerate}
\end{document}