What is a Karnaugh map (K-map)?

Karnaugh map (K-map) is a graphical representation of boolean and logical expressions. It helps to reduce the terms and simplify the logical circuits. Nowadays, interpretable artificial intelligence also uses the Karnaugh map in its computation to calculate which node in the neural network is participating in the decision. By this, we can also reduce the number of nodes and layers in the neural network.

In this Answer, we will discuss the Karnaugh map and take a simple expression to understand how the Karnaugh map helps reduce a logical expression.

Example

There are two forms of Karnaugh maps: the sum of the products (SOP) and the product of the sum (POS). In this Answer, we only look at the sum of the products (SOP) Karnaugh map.

Let us take an expression.

$Z=∑P,Q,R​(1,3,5,7)$

The expression shows that it can accept the input of 1,3,5, and 7 in three binary variables $P$, $Q$ and $R$.

• The Karnaugh map of three variables is illustrated below:

• The boolean expression for the equation $Z=∑P,Q,R​(1,3,5,7)$is $Z=\overline{PQ}R+\overline{P}QR+P\overline{Q}R+PQR$

• We want to reduce this equation with the help of the Karnaugh map. We will place $1$ where we want $Z$ to respond. Otherwise, we place $0$.

• In this step, make a rectangular box containing $1$the power of $2$ like; a rectangular container may have $2$,$4$,$6$, and so on many boxes in it.

• Remember that a rectangular box cannot be overlapped with the other rectangular box.

• Using these rectangular boxes, we can formulate the equation as,

  • $Z=\overline{Q}R(P+\overline{P})+QR(\overline{P}+P)$

  • As we know that $(P+\overline{P})=1$, then the equation will become, $Z=\overline{Q}R+QR$

  • Further, we can take R as common,

  • $Z=R(Q​+\overline{Q})$

  • $Z=R$

• So using the Karnaugh map, we have reduced our function only to a single term.

• As illustrated above, the Karnaugh map shows, the value is $1$, when R is $1$. For every other state, it is $0$.

Application of Kmap

There are several applications of K-map, from logic simplification to interpretable AI, where engineers predict the logical relationship between the variables, and it helps detect errors.

ML engineers can reduce the number of nodes in their neural network by simplifying the logical expression.

Conclusion

In this Answer, we discussed how the Karnaugh map can help to simplify logical expressions. We also looked at some applications of a K-map and how it helps maintain the size of neural networks. Now, let's take a quiz to test our understanding.