This is a classic application of K-V map (Karnaugh Map). Just implemented the algorithm in python for 4 variables. The function accepts the Boolean function in SOP (sum of products) form and the names of the variables and returns a simplified reduced representation. Basically you need to create rectangular groups containing total terms in power of two like 8, 4, 2 and try to cover as many elements as you can in one group (we need to cover all the ones).
For example, the function
$
\begin{array}
f(A,B,C,D) = & A′B′C′D+A′B′CD+A′BC′D′+A′BC′D+A′BCD′+AB′C′D′+ \\
& AB′C′D+ABC′D′+ABCD′+ABCD
\end{array}
$
can be represented as
$f(A,B,C,D)=\sum(1,3,4,5,6,8,9,12,14,15)$.
As can be seen from the output of the next code snippet, the program outputs the simplified form $B\bar{D} + \bar{A}B\bar{C} + A\bar{B}\bar{C} + ABC + \bar{A}\bar{B}D$, where negation of a boolean variable $A$ is represented $\bar{A}$ and equivalently as $¬A$ in the code.
from collections import defaultdict
from itertools import permutations, product
def kv_map(sop, vars):
sop = set(sop)
not_covered = sop.copy()
sop_covered = set([])
mts = [] # minterms
# check for minterms with 1 variable
all_3 = [''.join(x) for x in product('01', repeat=3)]
for i in range(4):
for v_i in [0,1]:
if len(not_covered) == 0: continue
mt = ('' if v_i else '¬') + vars[i]
s = [x[:i]+str(v_i)+x[i:] for x in all_3]
sop1 = set(map(lambda x: int(x,2), s))
if len(sop1 & sop) == 8 and len(sop_covered & sop1) < 8: # if not already covered
mts.append(mt)
sop_covered |= sop1
not_covered = not_covered - sop1
if len(not_covered) == 0:
return mts
# check for minterms with 2 variables
all_2 = [''.join(x) for x in product('01', repeat=2)]
for i in range(4):
for j in range(i+1, 4):
for v_i in [0,1]:
for v_j in [0,1]:
if len(not_covered) == 0: continue
mt = ('' if v_i else '¬') + vars[i] + ('' if v_j else '¬') + vars[j]
s = [x[:i]+str(v_i)+x[i:] for x in all_2]
s = [x[:j]+str(v_j)+x[j:] for x in s]
sop1 = set(map(lambda x: int(x,2), s))
if len(sop1 & sop) == 4 and len(sop_covered & sop1) < 4: # if not already covered
mts.append(mt)
sop_covered |= sop1
not_covered = not_covered - sop1
if len(not_covered) == 0:
return mts
# check for minterms with 3 variables similarly (code omitted)
# ... ... ...
return mts
kv_map([1,3,4,5,6,8,9,12,14,15], ['A', 'B', 'C', 'D'])
mts
['B¬D', '¬AB¬C', 'A¬B¬C', 'ABC', '¬A¬BD']
The following animation shows how the above code (greedily) simplifies the Boolean function given in SOP form (the basic goal is to cover all the $1$s with minimum number of power-2 blocks).
Since the algorithm is greedy it may get stuck to some local minimum, that we need to be careful about (can be improved!).
