Simplifying $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$ to $A'B'D+A'C'D+AB'C'+ABC+BD'$ (and another)

Question

I have been at this for hours using boolean algebra (not K-maps) and always end up so close but cannot reach the solutions.

This is one expression: $$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 \tag{1a}$$ and its simplification is $$A'B'D + A'C'D + AB'C' + ABC + BD' \tag{1b}$$

This is the second: $$A'B'C'D' + A'B'C'D + A'BC'D + A'BCD + AB'C'D' + AB'C'D \\ + AB'CD' + ABC'D' + ABC'D + ABCD \tag{2a}$$ and this is the simplification: $$BD + AC’ + B’C’ \tag{2b}$$

Can these be done using boolean algebra

---

Edit This is one of my attempts at the second expression:

Answer 1

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!).