3

I am trying to simplify a boolean expression involving a couple of hundreds boolean variables to a OR of Ands form (DNF). In addition, there are don't care terms can be represented by another boolean expression.

I found there are a couple of Python packages, such as SymPy, can be used to boolean expression minimization. However, it can not handle don't care terms in expressions format.

For example, 

>>> from sympy.logic import SOPform
>>> from sympy import symbols
>>> w, x, y, z = symbols('w x y z')
>>> minterms = [[0, 0, 0, 1], [0, 0, 1, 1],
...             [0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 1, 1]]
>>> dontcares = [[0, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 1]]
>>> SOPform([w, x, y, z], minterms, dontcares)
Or(And(Not(w), z), And(y, z))

The SOPform function can deal with dontcares terms, but it requires the terms in truth table format, which is not suitable for my case due to the large number of variables.

The other function simplify_logic accepts expression format, but do not have the option of dontcares terms.

>>> from sympy.logic import simplify_logic
>>> from sympy.abc import x, y, z
>>> from sympy import S
>>> b = (~x & ~y & ~z) | ( ~x & ~y & z)
>>> simplify_logic(b)
And(Not(x), Not(y))

Is there a way in Python can take care of minimization of boolean expression with dont care terms in expression format?

Thank you!

icehouse
  • 39
  • 2
  • Putting a boolean expression with that many variables in DNF is likely to be completely impossible simply due to how huge the DNF would be, even ignoring concerns like NP-hardness. – user2357112 Oct 24 '20 at 02:41

1 Answers1

1

The problem here is to make the code more scalable so that it can handle large inputs.

I will assume that the input minterms and dontcares are in integer format (which is the only other format I know apart from truth table format)

N = 4           # number of boolean variables
minterms = [1, 3, 7, 11, 15]
dontcares = [0, 2, 5]

Convert to truth table format:

  1. First convert decimal to binary (see here) 
    >>> num = 2
>>> f'{num:b}'
'10'
  2. Since there are N variables, which is 4 in this case, we need to pad extra zeros. (see here) 
    >>> '10'.zfill(4)
'0010'
  3. Lastly convert this to an list of ints 
    >>> [int(i) for i in '0010']
[0, 0, 1, 0]

Combining these three steps into a single function, we get

def convert(num, N):
    return [int(i) for i in f'{num:b}'.zfill(N)]

After this the process is straight forward. To generate N symbols, we can simply use for loop and add numerical suffix to the symbolic variables. And finally apply simplify_logic on the output from SOPform.

X = [symbols(f'x{i+1}') for i in range(N)]
# [x1, x2, x3, x4]

minterms_new = [convert(t, N) for t in minterms]
dontcares_new = [convert(t, N) for t in dontcares]
ans = SOPform(X, minterms_new, dontcares_new)

print(ans)
# (x3 & x4) | (x4 & ~x1)

print(simplify_logic(ans))
# x4 & (x3 | ~x1)
impopularGuy
  • 805
  • 9
  • 15