Karnaugh maps

Strictly speaking, a Karnaugh map is a tool for simplifying expressions in Boolean algebra. As such, its purpose is to determine how to construct logic circuits in the most efficient way for various applications in electronic data processing. 

A Karnaugh map is a representation of a truth table for a given logic function. It can simplify the problem of finding the most concise way of writing the logic function.

In logic, we think of combinations of events and whether the various combinations either occur or do not occur. This is expressed in terms of the operations of set theory: union, intersection, complementation.

In probability, we consider events and so, the same set operations arise. We assign numbers, called probabilities, to events and combinations of events in a sample space and the structure of a Karnaugh map can help in visualising how the probabilities of the various events should be combined.

In the context of logic, if there are two possible events, $A$A and $B$B, we might consider the combination ($A$A or $B$B) which in set notation is $A\cup B$A∪B and in the notation often used by electronics engineers is $A+B$A+B.

Similarly, the combination ($A$A and $B$B) is written in set notation as $A\cap B$A∩B and in other environments as $A.B$A.B, like a product.

The complement of event $A$A can be written $\overline{A}$A or $A'$A′ or $\neg A$¬A. It means not $A$A.

Example 1

Here is a very basic example of the kind of simplification that can occur in logical expressions. Suppose it is required that a logic circuit outputs the value 'true' only when events $A$A and not $B$B occur or when events not $A$A and not $B$B occur. 

In set notation this is $(A\cap B')\cup(A'\cap B')$(A∩B′)∪(A′∩B′). (It is also written $AB'+A'B'$AB′+A′B′. ) We see from the original statement of the problem that this compound event occurs whenever the event $B$B does not occur regardless of whether or not $A$A occurs. So, the electronic circuit only needs to test for the occurrence of event $B$B.

 

the karnaugh map

With two events, $A$A and $B$B, the possible expressions involving intersections are $AB$AB, $AB'$AB′, $A'B'$A′B′ and $A'B$A′B.  We can make a table like this:

To represent the Boolean expression $AB'+A'B'$AB′+A′B′, we have placed $1$1s in the cells corresponding to $AB'$AB′ and $A'B'$A′B′. It becomes clear that the only cells that matter are those forming the $B'$B′ column. These represent the union $AB'+A'B'$AB′+A′B′. We conclude that $AB'+A'B'$AB′+A′B′ is true when $B'$B′ is true.

This device becomes more useful when there are more Boolean variables involved and when simplification by the rules of Boolean algebra becomes cumbersome.

We consider Karnaugh maps in the context of logic in more detail in another chapter.

 

probability

For our purposes, we overlay the Karnaugh map structure with probability values. Here, we are not so much interested in the truth value of the various Boolean expressions, but rather in their probabilities.

In the following table, an extra row and column have been included for the probabilities $P(A)=P\left((A\cap B)\cup(A\cap B')\right)$P(A)=P((A∩B)∪(A∩B′)), $P(A')=P\left((A'\cap B)\cup(A'\cap B')\right)$P(A′)=P((A′∩B)∪(A′∩B′)), and similarly for $P(B)$P(B) and $P(B')$P(B′).  These are called the marginal probabilities.

We have put in some possible probability values as an illustration.

Since events $A,A',B'$A,A′,B′ and $B$B are the only events that can occur, the total probability in the lower right-hand corner must be $1$1.

Notice that if we erased no more than one cell value from each row and column, it would be possible to reconstruct the complete table. Thus, in this case, we could have as many as three missing probabilities and it would be possible to deduce what they were.

Example 2

In a study of a species of mosquito, it was found that $53%$53% of specimens in a sample carried a virus $A$A and $71%$71% carried virus $B$B. Also, $29%$29% carried neither $A$A nor $B$B viruses.

We can consider these frequencies as probabilities and complete a Karnaugh-style table as follows. The orange cells contain the given information and we have calculated the remaining probabilities so that the row and column sums will be correct.

From this, we see that the probability that a mosquito does not carry virus $A$A is $0.47$0.47 and that a mosquito does not carry virus $B$B is $0.32$0.32. The probability that a mosquito carries both viruses is $0.5$0.5. Similarly, we can read off the probabilities for $P(A\cap B')$P(A∩B′) and $P(A'\cap B)$P(A′∩B).

Worked examples

Question 1

Question 2