Section 7.1.1: Boolean Basics

Exercise 4. [24] [24] (H. M. Sheffer.) The purpose of this exercise is to show that all of the operations in Table 1 can be expressed in terms of NAND. (a) For each of the 16 operators $\circ$ in that table, find a formula equivalent to $x \circ y$ that uses only $\barwedge$ as an operator. Your formula should be as short as possible. For example, the answer for operation $\sqcup$ is simply "$x$", but the answer for $\sqcap$ is "$x \barwedge \lambda$". Do not use the constants 0 or 1 in your formulas. (b) Similarly, find 16 short formulas when constants are allowed. For example, $x \sqcup y$ can now be expressed also as "$\bar{x} \barwedge 1$".

Verified: no
Solve time: 5m47s

---

Let $x \bar\wedge y$ denote NAND, i.e. $x \bar\wedge y=\overline{x\wedge y}$.

Basic NAND identities

From the definition,

$$ \bar x = x \bar\wedge x. $$

Double negation gives back the variable:

$$ x = (x \bar\wedge x)\bar\wedge(x \bar\wedge x). $$

Define derived operations:

$$ x\wedge y = (x\bar\wedge y)\bar\wedge(x\bar\wedge y), $$

$$ x\vee y = (x\bar\wedge x)\bar\wedge(y\bar\wedge y). $$

A constant-free construction of truth constants is needed for part (a):

$$ 1 = x \bar\wedge (x \bar\wedge x), \qquad 0 = 1 \bar\wedge 1. $$

All of these use only NAND.

(a) NAND only, no constants allowed

The 16 Boolean functions are listed in truth-table order $(00,01,10,11)$.

$0000$ (constant 0)

$$ 0 = \bigl(x \bar\wedge (x \bar\wedge x)\bigr)\bar\wedge \bigl(x \bar\wedge (x \bar\wedge x)\bigr). $$

$0001$ ($x \wedge y$)

$$ x\wedge y = (x\bar\wedge y)\bar\wedge(x\bar\wedge y). $$

$0010$ ($x \wedge \bar y$)

$$ x\wedge \bar y

\bigl(x \bar\wedge (y\bar\wedge y)\bigr)\bar\wedge \bigl(x \bar\wedge (y\bar\wedge y)\bigr). $$

$0011$ ($x$)

$$ x = (x\bar\wedge x)\bar\wedge(x\bar\wedge x). $$

$0100$ ($\bar x \wedge y$)

$$ \bar x \wedge y

\bigl((x\bar\wedge x)\bar\wedge y\bigr)\bar\wedge \bigl((x\bar\wedge x)\bar\wedge y\bigr). $$

$0101$ ($y$)

$$ y = (y\bar\wedge y)\bar\wedge(y\bar\wedge y). $$

$0110$ ($x \oplus y$)

Let $a = x \bar\wedge y$. Then

$$ x\oplus y = (x \bar\wedge a)\bar\wedge (y \bar\wedge a). $$

So

$$ x\oplus y = \bigl(x \bar\wedge (x\bar\wedge y)\bigr)\bar\wedge \bigl(y \bar\wedge (x\bar\wedge y)\bigr). $$

$0111$ ($x \vee y$)

$$ x \vee y = (x\bar\wedge x)\bar\wedge (y\bar\wedge y). $$

$1000$ ($\overline{x \vee y}$, NOR)

Let $b = (x\bar\wedge x)\bar\wedge(y\bar\wedge y)$. Then

$$ \overline{x\vee y} = b \bar\wedge b. $$

$1001$ ($x \equiv y$)

Let $c = x \oplus y$. Then

$$ x \equiv y = c \bar\wedge c. $$

$1010$ ($\bar y$)

$$ \bar y = y \bar\wedge y. $$

$1011$ ($x \vee \bar y$)

$$ x \vee \bar y

\bigl(x\bar\wedge x\bigr)\bar\wedge \bigl((y\bar\wedge y)\bar\wedge(y\bar\wedge y)\bigr). $$

$1100$ ($\bar x$)

$$ \bar x = x \bar\wedge x. $$

$1101$ ($x \to y$)

Implication is $\bar x \vee y$. Using NAND only,

$$ x \to y = x \bar\wedge (y \bar\wedge y). $$

This corrects the earlier error: the expression depends on $\bar x \vee y$, not $x \vee y$.

$1110$ (NAND)

$$ x \bar\wedge y. $$

$1111$ (tautology)

$$ 1 = x \bar\wedge (x \bar\wedge x), $$

and equivalently $1 = 0 \bar\wedge 0$ using the construction above.

(b) NAND with constants allowed

Now $0$ and $1$ may be used directly, so expressions shorten.

$0000$

$$ 0 $$

$0001$

$$ (x\bar\wedge y)\bar\wedge(x\bar\wedge y) $$

$0010$

$$ (x\bar\wedge \bar y)\bar\wedge(x\bar\wedge \bar y), \qquad \bar y = y\bar\wedge y $$

$0011$

$$ x $$

$0100$

$$ (\bar x \bar\wedge y)\bar\wedge(\bar x \bar\wedge y), \qquad \bar x = x\bar\wedge x $$

$0101$

$$ y $$

$0110$

$$ (x\bar\wedge(x\bar\wedge y))\bar\wedge(y\bar\wedge(x\bar\wedge y)) $$

$0111$

$$ (x\bar\wedge x)\bar\wedge(y\bar\wedge y) $$

$1000$

$$ ((x\bar\wedge x)\bar\wedge(y\bar\wedge y))\bar\wedge((x\bar\wedge x)\bar\wedge(y\bar\wedge y)) $$

$1001$

$$ (x\oplus y)\bar\wedge(x\oplus y) $$

$1010$

$$ y\bar\wedge y $$

$1011$

$$ x \vee \bar y

(x\bar\wedge x)\bar\wedge(y\bar\wedge y) $$

$1100$

$$ x\bar\wedge x $$

$1101$ (implication)

$$ x \to y = x \bar\wedge (y\bar\wedge y) $$

$1110$

$$ x \bar\wedge y $$

$1111$

$$ 1 $$

All 16 Boolean functions are thus expressed using only NAND, and the incorrect implication identity from the previous solution has been replaced by the correct one.