Exercise 6. [21] [21] (E. Schröder.) (a) Which of the 16 operations in Table 1 are associative, in other words, which satisfy $(x \circ y) \circ z = x \circ (y \circ z)$? (b) Which of them satisfy the identity $(x \circ y) \circ (y \circ z) = x \circ z$?

Verified: yes
Solve time: 5m07s

Solution

Let

$$ a=f(0,0),\qquad b=f(0,1),\qquad c=f(1,0),\qquad d=f(1,1), $$

so that the binary operation $\circ$ is represented by the truth table $abcd$.

(a) Associative operations

We seek all operations satisfying

$$ (x\circ y)\circ z=x\circ (y\circ z) $$

for all $x,y,z\in{0,1}$.

Consider the four input triples $(0,0,1)$, $(1,0,0)$, $(1,1,0)$, and $(0,1,1)$. They yield

$$ f(a,1)=f(0,b), \tag{1} $$

$$ f(c,0)=f(1,a), \tag{2} $$

$$ f(d,0)=f(1,c), \tag{3} $$

$$ f(b,1)=f(0,d). \tag{4} $$

Writing each equation in terms of $a,b,c,d$,

$$ (1)\iff \begin{cases} b=a,& a=0,\ d=b,& a=1, \end{cases} $$

$$ (2)\iff \begin{cases} a=c,& c=0,\ c=d,& c=1, \end{cases} $$

$$ (3)\iff \begin{cases} a=c,& d=0,\ c=d,& d=1, \end{cases} $$

$$ (4)\iff \begin{cases} b=a,& b=0,\ d=b,& b=1. \end{cases} $$

Each of these equations is automatically true unless $a=1$ and $d=0$. Hence associativity implies

$$ a=0 \quad\text{or}\quad d=1. $$

Therefore the four tables

$$ 1000,\quad 1010,\quad 1100,\quad 1110 $$

cannot be associative.

There remain $12$ candidates.

Now check the four operations

$$ 0010,\qquad 0100,\qquad 1011,\qquad 1101. $$

They are not associative:

$$ 0010:\quad ((1\circ0)\circ1)=0,\qquad 1\circ(0\circ1)=1; $$

$$ 0100:\quad ((1\circ0)\circ1)=1,\qquad 1\circ(0\circ1)=0; $$

$$ 1011:\quad ((0\circ1)\circ0)=1,\qquad 0\circ(1\circ0)=0; $$

$$ 1101:\quad ((0\circ1)\circ0)=0,\qquad 0\circ(1\circ0)=1. $$

Thus these four are excluded.

The remaining eight operations are

$$ 0000,\quad 0001,\quad 0011,\quad 0101,\quad 0110,\quad 0111,\quad 1001,\quad 1111. $$

These correspond respectively to

$$ 0,\qquad x\wedge y,\qquad x,\qquad y, \qquad x\oplus y,\qquad x\vee y, \qquad x\equiv y,\qquad 1. $$

Verification:

$0$ and $1$ are associative because both sides are constant.
$x$ and $y$ are associative because both sides reduce to the same projection.
$\wedge$ and $\vee$ are associative by the usual Boolean laws.
$\oplus$ is addition modulo $2$, hence associative:

$$ (x\oplus y)\oplus z=x\oplus(y\oplus z). $$

Since

$$ x\equiv y = 1\oplus x\oplus y, $$

we have

$$ (x\equiv y)\equiv z =1\oplus(1\oplus x\oplus y)\oplus z =x\oplus y\oplus z\oplus1, $$

and similarly

$$ x\equiv(y\equiv z) =1\oplus x\oplus(1\oplus y\oplus z) =x\oplus y\oplus z\oplus1. $$

Hence $\equiv$ is associative.

Therefore the associative operations are exactly

$$ \boxed{,0,\ \wedge,\ x,\ y,\ \oplus,\ \vee,\ \equiv,\ 1, }. $$

(b) Operations satisfying $(x\circ y)\circ(y\circ z)=x\circ z$

We seek all operations satisfying

$$ (x\circ y)\circ (y\circ z)=x\circ z $$

for all $x,y,z\in{0,1}$.

Set $y=0$. For the four pairs $(x,z)$ we obtain

$$ f(a,a)=a, \tag{1} $$

$$ f(a,b)=b, \tag{2} $$

$$ f(c,a)=c, \tag{3} $$

$$ f(c,b)=d. \tag{4} $$

From (1),

$$ f(a,a)=a $$

means either $a=0$ or $d=1$.

Case 1: $a=1$

Equation (2) becomes

$$ f(1,b)=b. $$

If $b=0$, this gives $c=0$.

If $b=1$, this gives $d=1$.

Equation (3) becomes

$$ f(c,1)=c. $$

If $c=0$, this gives $b=0$.

If $c=1$, this gives $d=1$.

Hence the only possibilities are

$$ 1001,\qquad 1111. $$

Case 2: $a=0$

Then (2) and (3) hold automatically. Equation (4) becomes

$$ f(c,b)=d. $$

There are four possibilities:

$(c,b)=(0,0)$: $d=0$, giving $0000$.
$(c,b)=(1,0)$: $d=1$, giving $0011$.
$(c,b)=(0,1)$: $d=1$, giving $0101$.
$(c,b)=(1,1)$: $f(1,1)=d$, so $d$ may be $0$ or $1$, giving $0110$ and $0111$.

Thus the only candidates are

$$ 0000,\ 0011,\ 0101,\ 0110,\ 0111,\ 1001,\ 1111. $$

Now verify them.

$0000$ (constant $0$), $0011$ (projection $x$), $0101$ (projection $y$), and $1111$ (constant $1$) satisfy the identity trivially.
For XOR,

$$ (x\oplus y)\oplus (y\oplus z)

x\oplus y\oplus y\oplus z

x\oplus z. $$

For equivalence,

$$ (x\equiv y)\equiv (y\equiv z)

(1\oplus x\oplus y)\equiv(1\oplus y\oplus z). $$

Using $u\equiv v=1\oplus u\oplus v$,

$$ =1\oplus(1\oplus x\oplus y)\oplus(1\oplus y\oplus z) =1\oplus x\oplus z =x\equiv z. $$

The remaining candidate $0111$ is $x\vee y$. It does not satisfy the identity, since

$$ x=0,\quad y=1,\quad z=0 $$

gives

$$ (0\vee1)\vee(1\vee0)=1, $$

while

$$ 0\vee0=0. $$

Hence $0111$ must be excluded.

Therefore the operations satisfying

$$ (x\circ y)\circ(y\circ z)=x\circ z $$

are exactly

$$ \boxed{,0,\ x,\ y,\ \oplus,\ \equiv,\ 1, }. $$

Equivalently, the corresponding truth tables are

$$ \boxed{0000,\ 0011,\ 0101,\ 0110,\ 1001,\ 1111}. $$

$\square$

TAOCP 7.1.1 Exercise 6