0

How can I express $(\bar{x})y + \bar{z}$ using only NAND?

I know the solution is $((x↑x)↑y)↑z$, but I don't understand how to get to there without expanding into an extremely long answer?

The brute force technique given to me was:

  1. eliminate addition (using $\bar{a+b} = \bar{a}\bar{b}$)
  2. eliminate multiplication (using $ab = (a↑b)↑(a↑b)$)
  3. eliminate complement (using $\bar{a} = a↑a$)

Will show my previous work if needed.

mathguy
  • 927
  • Yes, it would be nice if you could show us what you ended up with following that brute force technique, so we can see how long of an answer you get. And then we/you can also think about how to simplify that answer back to the provided solution. – Bram28 Nov 06 '19 at 19:44

2 Answers2

1

$$p ↑ q\equiv\overline{p}+\overline{q}\equiv \neg p\lor\neg q\tag*{aka Nand}$$

And the fully simplified solution should be:

$$(\overline{x}↑y)↑z$$

Basicly, first try to express the statement in form of $\overline{p}+\overline{q}$, to get this we need De Morgan's law:

Boolean algebra notation:

\begin{align} \overline{x}y+\overline{z}\tag*{$\text{De Morgan's law}$} &\equiv\overline{\overline{\overline{x}}+\overline{y}}+\overline{z}\\ &\equiv\overline{\overline{x}↑y}+\overline{z}\\ &\equiv(\overline{x}↑y)↑z\\ \end{align}

PL notation:

\begin{align} (\neg x\land y) \lor \neg z\tag*{$\text{De Morgan's law}$} &\equiv\neg(\neg\neg x\lor \neg y)\lor\neg z\\ &\equiv\neg(\neg x↑y)\lor \neg z\\ &\equiv(\neg x↑y)↑z\\ \end{align}

First use De Morgan's law backward, so the statement is in form of $\overline{p}+\overline{q},$
and the last two line is just substitute the definition.
Therefore we simplified it with Nand.

Ethan
  • 5,291
1

Since $x \uparrow y = (xy)'$, we just need to get it in that form, and that's easy for this one:

$$x'y+z'=((x'y)'z)'=(((xx)'y)'z)'=((x\uparrow x)\uparrow y)\uparrow z$$

Bram28
  • 100,612
  • 6
  • 70
  • 118