Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've tried every which way I can think of to manipulate the algebra using the various laws I was given, but I cannot figure out a way to get $\overline{x+y}$ to convert to only NAND operations using $\overline{x\cdot x}$, $\overline{x\cdot y}$, or $\overline{y\cdot y}$

I've tried using idempotent, DeMorgan's, identity, and double negation laws to no avail.

share|cite|improve this question
1 – MJD Feb 7 '13 at 3:54
up vote 1 down vote accepted

I’ll use $\mid$ for the connective NAND. You want $\overline{x+y}$; as a first step, this is $(x+y)\mid(x+y)$. Now check that $x+y=(x\mid x)\mid(y\mid y)$, and put the pieces together.

share|cite|improve this answer
sigh I've spent a good hour doing various things and I did get to that as a first step, but I can't believe I didn't see that I could easily convert the two $x+y$ to $\overline{\overline{x\cdot x}\cdot\overline{y\cdot y}}$ – agent154 Feb 7 '13 at 4:07
@agent154: Trust me, I know the feeling! – Brian M. Scott Feb 7 '13 at 4:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.