Python sympy : Using simplfy on boolean expression results with non simplified expression

user_13258289 0
Viewed 937

I'm trying to simplify a boolean expression with sympy but I'm facing an issue:

from sympy.logic import simplify_logic,to_cnf,to_dnf
from sympy import Symbol,S

# Simplified to: 
#'deputy | mayor | (city & director) | (city & manager) | (director & investment & of)'
# Which seems as non simplifed expression
str(simplify_logic(eval('(city&manager)|(city&director)|(deputy)|(mayor)|(director&of&investment)')))

But this :

# Simplified to: 
# 'sales & (director | manager)'
# Which is simplified!
str(simplify_logic(eval('(sales&manager)|(sales&director)')))

How can I simplify the first expression?

Thank you!

EDIT : by simplifed I mean an expression with a minimum number of operators

PS: all words are defined as symbols:

for word in words:
    vars()[word]=Symbol(word)
sympy boolean python
1 Answers

In light of the question, I guess you'd expect result such as:

'(city&(manager|director))|(deputy)|(mayor)|(director&of&investment)'

When delving into the simplify_logic function, we see the form parameter:

string ('cnf' or 'dnf') or None (default). If 'cnf' or 'dnf', the simplest expression in the corresponding normal form is returned; if None, the answer is returned according to the form with fewest args (in CNF by default)

So, basically what happens is that the expression inputted is converted to either DNF or CNF form.

In our case, the expression is converted to DNF form, as it has fewer arguments.

Bouncing back to the start - the expression we'd expect is NOT a valid DNF or CNF form, so we won't get it.

Because DNF is an OR of ANDs, and sub-part expression (city&(manager|director)) doesn't satisfy this (there is OR between manager and director).

However, the other expression is simplified to:

sales & (director | manager)

Because it's a valid CNF form.

"Simplify" by minimizing boolean function

Usually, simplification algorithms don't minimize the number of operands, rather than number of operators (logic gates), this usually means shorter-expression (doesn't necessarily - sometimes even longer).

These are a few algorithms used for boolean function minimization:

  1. Karnaugh map (warning: it isn't suited for more than six input variables and practical only for up to four variables)
  2. Quine–McCluskey algorithm (practical only for functions with a limited number of input variables and output functions)

The sympy provides an implementation in SOPform (smallest Sum of Products form) and POSform (smallest Product of Sums form).

  1. Espresso algorithm

And a tool Espresso logic minimization, included in pyeda:

Example usage of espresso_exprs function to minimize multiple expressions:

>>> f1 = Or(~a & ~b & ~c, ~a & ~b & c, a & ~b & c, a & b & c, a & b & ~c)
>>> f2 = Or(~a & ~b & c, a & ~b & c)
>>> f1m, f2m = espresso_exprs(f1, f2)
>>> f1m
Or(And(~a, ~b), And(a, b), And(~b, c))
>>> f2m
And(~b, c)
user_141488640
Related