Karnaugh Maps

Karnaugh maps are an alternative way to define and express logical connectives $f:\{0,1{\}}^n\to \{0,1\}$.

We first assign $n$ labels $x_1,\dots ,x_n$ to each element of the input tuple from $\{0,1{\}}^n$. We then choose an index and split the input tuple $(x_1,\dots ,x_n)$ into two tuples $(x_1,\dots ,x_k)$ and $(x_{k+1},\dots ,x_n)$. Finally, we construct a table in the following way:

• Plot all possible combinations for $(x_1,\dots ,x_k)$ as the first column. This should be done in a way so as to ensure that each combination differs by its adjacent ones only by a single input.
• Plot all possible combination for $(x_{k+1},\dots ,x_n)$ as the first row. This should be done in a way so as to ensure that each combination differs by its adjacent ones only by a single input.
• The cell at the $i$-th row and the $j$-th column is filled with the value of $f$ evaluated at the tuple obtained by concatenating the combination for $(x_1,\dots ,x_k)$ at the $i$-th row and the combination for $(x_{k+1},\dots ,x_n)$ at the $j$-th column.

A table constructed in this manner fully describes $f$ and is known as a Karnaugh map of $f$.

Example: Karnaugh Map of Negation

Consider the negation function $f:\{0,1\}\to \{0,1\}$ defined as

$$f(x)=\{\begin{array}{l}0\text{if }x=1\\ 1\text{if }x=0\end{array}$$

It has only two possible Karnaugh maps:

x
0	1
1	0

x	0	1
	1	0

Example: Karnaugh Map of Conjunction

Consider the conjunction function $f:\{0,1\}\to \{0,1\}$ defined in the following way:

$$\mathrm{AND}(x,y)\stackrel{\text{def}}{=}\{\begin{array}{l}1\text{if }x=y=1\\ 0\text{otherwise}\end{array}$$

One of its Karnaugh maps is the following:

Another one is this:d

The following, however, is not a Karnaugh map of $f$ because the strings $01$ and $01$ differ in both places and not in a single one.