Section 7.1.3: Bitwise Tricks and Techniques

Exercise 136. [29] [29] Suggest two-bit encodings for binary operations on the set {a, b, c} that are defined by the following “multiplication tables”: (a) a b c b c c c c c  ; (b) a c b c b a b a c  ; (c) a b a a a c a b c  .

Verified: yes
Solve time: 5m28s

---

A correct treatment must start from the actual definition of “two-bit encoding”.

A map

$$ \varphi:S\to {0,1}^2,\quad \varphi(x)=(f(x),g(x)) $$

is a valid encoding if each coordinate map $f,g:S\to{0,1}$ is a homomorphism into some binary algebra on ${0,1}$. This is equivalent to the following structural condition:

For each coordinate $f$, the relation

$$ x \equiv_f y \iff f(x)=f(y) $$

is a congruence of the algebra $(S,\star)$, and similarly for $g$.

Conversely, any congruence with two equivalence classes gives such a coordinate.

Hence the problem is purely about whether the algebra admits two congruences of index 2 whose intersection is trivial (so that the combined map is injective).

Since $|S|=3$, any nontrivial index-2 congruence must have block structure $1+2$. So we classify all 2-block congruences in each case.

(a)

The operation is

$$ \begin{array}{c|ccc} \star & a & b & c\ \hline a & a & b & c\ b & b & c & c\ c & c & c & c \end{array} $$

We test all partitions into a singleton and a doubleton.

1. Partition ${a}\mid{b,c}$

Let $b\equiv c$. We check congruence condition:

if $x\equiv y$, then for all $t$,

$$ x\star t \equiv y\star t,\quad t\star x \equiv t\star y. $$

Check right multiplication:

• For $t=a$: $b\star a=b$, $c\star a=c$, and $b\equiv c$, OK.
• For $t=b$: $b\star b=c$, $c\star b=c$, OK.
• For $t=c$: $b\star c=c$, $c\star c=c$, OK.

Check left multiplication:

• $a\star b=b$, $a\star c=c$, and $b\equiv c$, OK.
• $b\star b=c$, $c\star b=c$, OK.

So ${a}\mid{b,c}$ is a congruence.

2. Partition ${b}\mid{a,c}$

Assume $a\equiv c$. Check $b\star a=b$, $b\star c=c$. Then we would need $b\equiv c$, contradiction. So not a congruence.

3. Partition ${c}\mid{a,b}$

Assume $a\equiv b$. But $a\star c=c$ while $b\star c=c$ is fine, however:

$c\star a=c$, $c\star b=c$ is fine, but check $a\star b=b$ and $b\star b=c$, which forces $b\equiv c$, contradiction. So not a congruence.

Conclusion for (a)

There is exactly one nontrivial congruence:

$$ {a}\mid{b,c}. $$

So any coordinate map $S\to{0,1}$ must identify $b$ and $c$. With two coordinates, both coordinates still identify $b$ and $c$, so the pair cannot be injective.

$$ \boxed{\text{(a) admits no two-bit encoding.}} $$

(b)

The table is a Latin square:

$$ \begin{array}{c|ccc} \star & a & b & c\ \hline a & a & c & b\ b & c & b & a\ c & b & a & c \end{array} $$

This structure is a quasigroup isomorphic to the cyclic group of order 3.

A key fact: in any algebra whose operation is a Latin square, congruences correspond to partitions preserved by all left and right translations. In a Latin square of prime order (here 3), every nontrivial congruence would induce a nontrivial quotient algebra, hence a nontrivial block system invariant under all translations.

But the translation permutations generated by rows act transitively on ${a,b,c}$. Therefore the only congruences are:

• the discrete one (three singletons),
• the universal one (all elements together).

So there is no congruence of index 2.

Hence no coordinate map $S\to{0,1}$ exists at all, let alone two independent ones.

$$ \boxed{\text{(b) admits no two-bit encoding.}} $$

(c)

The operation is

$$ \begin{array}{c|ccc} \star & a & b & c\ \hline a & a & b & a\ b & a & a & c\ c & a & b & c \end{array} $$

We again classify index-2 congruences.

1. Partition ${a}\mid{b,c}$

Assume $b\equiv c$. Check compatibility using $b\star b=a$ and $c\star b=b$:

$$ b\star b = a,\quad c\star b = b, $$

so we would need $a\equiv b$, contradiction. Not a congruence.

2. Partition ${b}\mid{a,c}$

Assume $a\equiv c$. Check consistency:

Right multiplication by $b$:

$$ a\star b=b,\quad c\star b=b \quad \Rightarrow \text{consistent}. $$

Right multiplication by $c$:

$$ a\star c=a,\quad c\star c=c \quad \Rightarrow a\equiv c, $$

consistent with the assumption.

Left multiplication by $b$:

$$ b\star a=a,\quad b\star c=c \quad \Rightarrow a\equiv c, $$

consistent.

Left multiplication by $a$:

$$ a\star a=a,\quad c\star a=a \quad \Rightarrow \text{consistent}. $$

Left multiplication by $c$:

$$ c\star a=a,\quad c\star c=c \quad \Rightarrow a\equiv c, $$

consistent.

Thus ${b}\mid{a,c}$ is a congruence.

3. Partition ${c}\mid{a,b}$

Assume $a\equiv b$. But:

$$ a\star c=a,\quad b\star c=c, $$

forcing $a\equiv c$, contradiction. Not a congruence.

Conclusion for (c)

There is exactly one index-2 congruence:

$$ {b}\mid{a,c}. $$

So any coordinate map must identify $a$ and $c$. With two coordinates, both coordinates still identify $a$ and $c$, so injectivity is impossible.

$$ \boxed{\text{(c) admits no two-bit encoding.}} $$

Final conclusion

Each algebra admits at most one nontrivial congruence with two blocks, so no pair of such congruences can separate all three elements. Therefore no injective two-coordinate Boolean encoding exists in any case.

$$ \boxed{\text{(a), (b), and (c) all do not admit two-bit encodings.}} $$