\problemdata
{intro-logic}
{S00}

\begin{problem}
In some computer architectures, the basic computer operation
is ``NAND'', denoted~$\nand$, where $A \nand B$ means $\neg (A \land
B)$.  Show that all the basic boolean operations can be implemented
using the single $\nand$ operation.  That is, rewrite each of the
following formulas as equivalent formulas using only the $\nand$
operator (and parentheses).

\begin{problemparts}
\problempart $\neg A$
\solution{
$A \nand A$
}
\problempart $A \lor B$
\solution{
       $(A \nand A) \nand (B \nand B)$
        \quad ($\Longleftrightarrow
         \neg ( \neg A \land \neg B)
        \Longleftrightarrow 
        \neg A \nand \neg B$)
}
\problempart $A \land B$
\solution{
  $(A \nand B) \nand (A \nand B)$ 
  \quad ($\Longleftrightarrow \neg(A \nand B)$)
}
\problempart $A \implies B$
\solution{
  $A \nand (B \nand B)$
        \quad ($\Longleftrightarrow B \lor \neg A)$)
}
\end{problemparts}
\end{problem}


 
