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.