\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 7 at 9:00AM, DEAD-CAT DAY Feb 9, 9:00AM} \begin{enumerate} \item (10 points) When is the untimed part of the first midterm MORALLY DUE (give date and time)? When is the timed part of the first midterm (give date and time)? When is the untimed part of the second midterm MORALLY DUE (give date and time)? When is the timed part of the second midterm (give date and time)? If you cannot make timeslot of the first midterm TELL DR. GASARCH NOW!!!!!! If you cannot make timeslot of the second midterm TELL DR. GASARCH NOW!!!!!! \vfill \centerline{\bf GOTO NEXT PAGE FOR NEXT PROBLEM} \newpage \item (20 points) Give a Propositional Formula on three variables that has exactly four satisfying assignments. Give the satisfying assignments. \vfill \centerline{\bf GOTO NEXT PAGE FOR NEXT PROBLEM} \newpage \item (20 points) \begin{itemize} \item Do a truth table for $(p\implies q)\implies r$. \item Do a truth table for $p\implies (q\implies r)$. \item Are they equivalent? If NOT then state a row where they differ. \end{itemize} \vfill \centerline{\bf GOTO NEXT PAGE FOR NEXT PROBLEM} \newpage \item (25 points) $n$ has the EMILY property if there is a formula on $n$ variables with exactly $n^3+17$ satisfying assignments. \begin{enumerate} \item (10 points) Fill in the following sentence $n$ has the EMILY property IFF BLANK($n$). 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} \vfill \centerline{\bf GOTO NEXT PAGE FOR NEXT PROBLEM} \newpage \item (25 points) If $x$ is a real number then $\floor{x}$ is that number rounded DOWN. Examples: $\floor{\pi}=3$, $\floor{\sqrt{2}}=1$. \begin{enumerate} \item (10 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 3 outputs $a,b,c$. $$f(x,y,z) = \begin{cases} \floor{(xyz)^{1.5} - 1.7(xyz))} & \hbox{if \floor{(xyz)^{1.5} - 1.7(xyz)} \ge 0} \cr 0 & \hbox{otherwise}\cr \end{cases}$$ (EXAMPLE: Lets look at the row of the table that has $x=1$,$y=0$, $z=1$. Since $(xyz)=(101)=6$ and $\floor{6^{1.5}-(1.7)\times 6} = \floor{4.49\ldots}=4$, the output is $(100)$ so $a=1$, $b=0$, $c=0$. Hence the below is part of the table. $\begin{array}{|ccc|ccc|} \hline x & y & z & a & b & c \cr \hline 1 & 0 & 1 & 1 & 0 & 0 \cr \hline \end{array}$ \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}