TAOCP 7.1.4 Exercise 188

Exercise 188. [16] [16] Express the 16 Boolean functions f(x1, x2) as families of subsets of {1, 2}.

Verified: yes
Solve time: 1m13s

Solution

In the ZDD representation used in this section, a Boolean function is identified with the family of subsets on which it is true. For two variables, the ground set is ${1,2}$, whose subsets are

$$ \emptyset,\ {1},\ {2},\ {1,2}. $$

The correspondence with truth tables is

$$ \begin{array}{c|c} (x_1,x_2) & \text{subset}\ \hline (0,0) & \emptyset\ (0,1) & {2}\ (1,0) & {1}\ (1,1) & {1,2}. \end{array} $$

Hence every Boolean function $f(x_1,x_2)$ is represented by the family

$$ \mathcal F(f)= \bigl{ S\subseteq{1,2}\mid f(\chi_S(1),\chi_S(2))=1 \bigr}, $$

where $\chi_S(i)=1$ if $i\in S$ and $\chi_S(i)=0$ otherwise.

There are $2^4=16$ such families, namely

$$ \begin{array}{c|c} \text{Truth table} & \mathcal F(f)\ \hline 0000 & \emptyset\ 0001 & {{1,2}}\ 0010 & {{1}}\ 0011 & {{1},{1,2}}\ 0100 & {{2}}\ 0101 & {{2},{1,2}}\ 0110 & {{2},{1}}\ 0111 & {{2},{1},{1,2}}\ 1000 & {\emptyset}\ 1001 & {\emptyset,{1,2}}\ 1010 & {\emptyset,{1}}\ 1011 & {\emptyset,{1},{1,2}}\ 1100 & {\emptyset,{2}}\ 1101 & {\emptyset,{2},{1,2}}\ 1110 & {\emptyset,{2},{1}}\ 1111 & {\emptyset,{2},{1},{1,2}}. \end{array} $$

Every family of subsets of ${1,2}$ appears exactly once in this table, because each of the four subsets may independently be included or excluded. Conversely, every Boolean function determines exactly one such family by the preceding correspondence between subsets and assignments.

Therefore the sixteen Boolean functions of two variables are represented precisely by the sixteen families listed above.

$$ \boxed{\text{The correspondence is exactly the table above.}} $$