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_0, \dotsc, x_{n-1}\) to each element of the input tuple from \(\{0, 1\}^n\). We then choose an index \(k \in [1;n-1]\) and split the input tuple \((x_0, \dotsc, x_{n-1})\) into two tuples \((x_0, \dotsc, x_{k-1})\) and \((x_{k}, \dotsc, x_{n-1})\). Finally, we construct a table with \(2^k\) columns and \(2^{n-k}\) rows in the following way:
- We label the columns with all possible binary sequences representing numbers in the range \([0; 2^k]\). This should be done in a way so as to ensure that each combination differs by its adjacent ones only by a single input.
- We label the rows with all possible binary sequences representing numbers in the range \([0; 2^{n-k}]\). 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 column and the \(j\)-th row is filled with the value of \(f\) evaluated at the concatenation of the label of the \(i\)-th column and the label of the \(j\)-th row.

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