Exercise 5. [24] [24] Consider exercise 1 with $\barwedge$ as the basic operation instead of $\overline{\wedge}$.

Verified: yes
Solve time: 2m07s

Solution

Let

$$ a \mid b ;=; a \bar{\wedge} b ;=; \overline{a\wedge b}. $$

Since

$$ \bar{x}=x\mid x, \qquad x\wedge y=(x\mid y)\mid(x\mid y), \qquad x\vee y=(x\mid x)\mid(y\mid y), $$

every Boolean operation can be expressed using $\bar{\wedge}$ alone.

The sixteen operations of Table 1 may be written as follows:

$$ \begin{array}{c|l} \text{Operation} & \text{Expression using only }\bar{\wedge} \ \hline 0 & \bigl(x\mid(x\mid x)\bigr)\mid\bigl(x\mid(x\mid x)\bigr) \[1ex] x\wedge y & (x\mid y)\mid(x\mid y) \[1ex] x\bar y & \bigl(x\mid(y\mid y)\bigr)\mid\bigl(x\mid(y\mid y)\bigr) \[1ex] x & (x\mid x)\mid(x\mid x) \[1ex] \bar x,y & \bigl((x\mid x)\mid y\bigr)\mid\bigl((x\mid x)\mid y\bigr) \[1ex] y & (y\mid y)\mid(y\mid y) \[1ex] x\oplus y & \bigl(x\mid(x\mid y)\bigr)\mid\bigl(y\mid(x\mid y)\bigr) \[1ex] x\vee y & (x\mid x)\mid(y\mid y) \[1ex] x\bar\vee y & \Bigl((x\mid x)\mid(y\mid y)\Bigr) \mid \Bigl((x\mid x)\mid(y\mid y)\Bigr) \[1ex] x\equiv y & d\mid d, \quad d= \bigl(x\mid(x\mid y)\bigr)\mid\bigl(y\mid(x\mid y)\bigr) \[1ex] \bar y & y\mid y \[1ex] x\vee\bar y & (x\mid x)\mid y \[1ex] \bar x & x\mid x \[1ex] \bar x\vee y & x\mid(y\mid y) \[1ex] x\bar\wedge y & x\mid y \[1ex] 1 & x\mid(x\mid x) \end{array} $$

Each formula involves only the operation $\bar{\wedge}$, as required.

The correctness of the table follows from the identities

$$ \bar{x}=x\mid x, \qquad x\wedge y=(x\mid y)\mid(x\mid y), \qquad x\vee y=(x\mid x)\mid(y\mid y), $$

together with the definitions in Table 1. For example,

$$ x\mid(y\mid y)

\overline{x\wedge\bar y}

\bar x\vee y, $$

which is implication, and

$$ (x\mid x)\mid y

\overline{\bar x\wedge y}

x\vee\bar y, $$

which is converse implication. The formulas for nonimplication, converse nonimplication, NOR, and equivalence are obtained by complementing the corresponding expressions, while the formula for exclusive-or is the standard NAND realization

$$ x\oplus y

\bigl(x\mid(x\mid y)\bigr)\mid\bigl(y\mid(x\mid y)\bigr). $$

Hence all sixteen Boolean operations are expressible using $\bar{\wedge}$ alone.

This completes the proof.

∎

TAOCP 7.1.1 Exercise 5