\documentclass{article}   

\title{Discrete Mathematics and Applications} 
\author 
{Moshe Rosenfeld\\ 
\\ Hanoi 2010\\
{\tt moishe@u.washington.edu}}
\date{}
        

\begin{document}           

\maketitle                

\section{Assignment No. 2: logic}
Due:  tuesday, Sep. 25\\

Please submit your answer in a neat, readable properly organized format.\


\begin {enumerate}
\item a. Construct a truth table for a Boolean expression $ F( p,q,r,s)$  such that $ F(p,q,r,s) = T$ only when either one orl three variables equal T.\\
b.  Use logic gates to implement this table.\\
c.  Use only NAND gates to implement this table.\\

\item   Given the disjunction $(x + y + s + t + w)$. Construct an  3-SAT instance F such that F is TRUE if and only if $(x+y+s+t+w)$ is true.\\
\item  Prove that any 3-SAT instance with 7 clauses is satisfiable.
\item   Find a compound proposition logically equivalent to $p \rightarrow q$ using only the NAND operator.
\item  The police suspects that four persons hacked into the university computer system. The four persons made the following statement to the police: \\
Anh: Phuong did it.\\
Phuong: Ben did it.\\
Tuan: I did not do I\\
Ben: Phuong lied when he said that I did it.\\

a. Suppose the police know that exactly one person is lying, who did it?\\
b. Suppose the police know that exactly one person is telling the truth, who did it?\\
Justify your answer.
\item * Construct an instance F of 3-SAT that:\\
1. F has 10 clauses\\
2. F is not satisfiable.\\
3. If you delete any clause, the resulting instance with 9 clauses will be satisfiable.
\end{enumerate}


\section {SAGE exercises}
\begin{enumerate}
\item 11 is a prime number. Find the largest number you can of the form 11...1 which is prime.\\
Can you form a related hypothesis?
\item  Create the set:\\ 
$ A = \{ n | n \in N, n = a^2 + b^2, \ a,b \in N,\  n \leq  k\}$ \\
For different values of k, what is the ratio $|A|/n\quad |A|$ is the size of A.? \\
Can you form an hypothesis?

\end{enumerate}
\end{document}