# Karnaugh Maps In Pandas#

As many of you know, I held a session on Logic this past month as part of “All the Computer Science You Never Took in College”. While I have never taken a computer science class in my life, I resonated with many of these concepts as things that I had encountered

A fun example that I presented used `pandas` to simplify a boolean algebra expression via a Karnaugh map. Karnaugh maps are useful tabular representations of boolean expressions that we can use to visually simplify this expression to a disjunctive form.

```from pandas import MultiIndex, Series
from numpy import where

s = Series(
data=[0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0],
name='result',
index=MultiIndex.from_product(
[[False, True]]*4, names=[*'ABCD']
),
)

print(s)
```
```A      B      C      D
False  False  False  False    0
True     0
True   False    1
True     0
True   False  False    0
True     0
True   False    1
True     0
True   False  False  False    0
True     1
True   False    0
True     1
True   False  False    1
True     1
True   False    0
True     0
Name: result, dtype: int64
```

In the above 4 variable truth table, we can see a specific pattern of outputs. However, what we don’t know is an expression that might have given rise to this pattern of results. Thankfully, we can solve this fairly easily using a Karnaugh map. But before we can address this problem with a Karnaugh map- we first need to restructure our data to obtain the proper representation of the map.

Karnaugh maps are characterized by projecting a truth table into 2 (commonly nested) dimensions. From this 2d perspective, we then flip the final 2 bits of dimensions (thus interchanging the rows/columns that are labelled as (True, True) with (True, False). Thus the final ordering of both the rows and columns is: `[(False, False), (False, True), (True, True), (True, False)]`.

```ordering = [(False, False), (False, True), (True, True), (True, False)]
kmap = s.unstack(['A', 'B']).loc[ordering, ordering]
kmap
```
A False True
B False True True False
C D
False False 0 0 1 0
True 0 0 1 1
True True 0 0 0 1
False 1 1 0 0

Once we have organized our map as above, we look for groupings of active outputs (`1`’s) that are in groups of 8, 4, or 2 in either the vertical or horizontal direction. Once we locate those groups, we determine which of the input variables remain constant across that group.

```from pandas import DataFrame, IndexSlice
from IPython.display import display

def highlight_groups(df):
style_df = DataFrame(None, index=df.index, columns=df.columns)
style_df.loc[(True, False), False] = 'background-color: #90EE90' # green
style_df.loc[False, (True, True)] = 'background-color: #8989ff'   # blue
style_df.loc[IndexSlice[:, True], (True, False)] = 'background-color: #ffd589' # orange

return style_df

display(
kmap.style.apply(highlight_groups, axis=None),
)
```
A False True
B False True True False
C D
False False 0 0 1 0
True 0 0 1 1
True True 0 0 0 1
False 1 1 0 0

To construct the function that outputs this truth table, we whether or not any input variables `{A, B, C, D}` remain constant within each of these groups.

Starting with the green group, we can note that `A` is False for both values in the green group. Then we also note that `D` is also `False` for both, and `C` is `True` for this group. The only variable that changes is `B` (so we can exclude it here). Now we take each of these constant input variables and join them with `&` while also ensuring all inputs are `True` by negating any `False` values. By doing so, we are able to piece together a puzzle that points to the solution: the green groups outputs can be represented by `~A & C & ~D` (`A` and `D` are negated since they were both constant and `False`).

The green group is simply one part of this puzzle, as we have solved the question “what combination of inputs give rise to output observed in the green group”. We repeat this process for the rest of the observed groups, then combine these groups with an inclusive or. Leading to a solution of: `(A & B & ~C) | (~A & C & ~D) | (A & ~B & D)` for the `blue | green | orange` groups respectively.

## Testing the Karnaugh Map Solution#

Testing this is fairly straightforward. We can simply plug our solution back into our `DataFrame` using the `eval` method, and check to see if our solution recreates the same truth table we began with!

```kmap_soln = '(A & B & ~C) | (~A & C & ~D) | (A & ~B & D)'

print(
s.reset_index()
.eval(f'solution = {kmap_soln}').astype({'solution': int})
.set_index(s.index.names)
)
```
```                         result  solution
A     B     C     D
False False False False       0         0
True        0         0
True  False       1         1
True        0         0
True  False False       0         0
True        0         0
True  False       1         1
True        0         0
True  False False False       0         0
True        1         1
True  False       0         0
True        1         1
True  False False       1         1
True        1         1
True  False       0         0
True        0         0
```

Looks like everything is correct here! But if you’re like me, then you are probably interested in triple checking your work. Thankfully, we can simply plug in our truth table directly into `sympy`, and compare whether or not the simplified equations match each other. We check simplified equation forms because the equation derived by our Karnaugh map and `sympy` may be different solely due to algorithmic selection, but still result in the same truth table (and be behaviorally the same). By running them through the same simplification algorithm, we can check if they have the same conjunctive normal form and thus represent the same expression.

```from sympy.logic.boolalg import ANFform
from sympy.logic import simplify_logic

sympy_soln = ANFform(s.index.names, s)

print(
f'{simplify_logic(sympy_soln) = }',
f'{simplify_logic(kmap_soln)  = }',
sep='\n'
)
```
```simplify_logic(sympy_soln) = (A | C) & (A | ~D) & (B | D | ~A) & (~A | ~B | ~C)
simplify_logic(kmap_soln)  = (A | C) & (A | ~D) & (B | D | ~A) & (~A | ~B | ~C)
```

Looks like triple checking our work paid off, as simplifying both of these expressions led to the same matching expression.

## Wrap Up#

And there you have it- solving a Karnaugh Map by leveraging `pandas` with some reshaping and styling. Hopefully this helped you visualize boolean functions & algebra a little bit differently and can flex those pandas manipulations more fluently! Until next time.