Boolean expressions not simplified correctly

[kevin-cfs]

I am utilizing this code in a project of mine and am finding I have some really long boolean logic when I finish. I am relying heavily on the simplification component in order to make my whole project work but I realize that it doesn't seem to work as well as Wolfram Alpha. Here is a simple test.

logic = "( a & ~b & ~c )|( a & ( b | c ))"

According to Wolfram Alpha this evaluates to just 'a' but boolean.BooleanAlgebra(logic, simplify=True) doesn't change the results at all. This is a big issue for me. Has anyone else experienced the simplification not working effectively sometimes?

To further show this you can simplify this expression.
logic = "(~b & ~c) | (b | c)"
The result should be 1 or TRUE but the boolean parser gives a clearly wrong answer of "b|c|~c". But how can you ever have "c or not c"? That is clearly wrong.

b | c | (~b & ~c) | (b | c)
--|---|--------------------
T | T | T
T | F | T
F | T | T
F | F | T

[kevin-cfs]

Update:

It seems that when you take an expression and run the simplify() function on it then it will sometimes give different results than parsing the string form of it will.

#######################################################################
import boolean

algebra = boolean.BooleanAlgebra()
a, b = algebra.symbols(*'ab')

logic = (a&b)|(~a|~b)
print(str(logic))
print(str(logic.simplify()))
print(str(algebra.parse(str(logic), simplify=True)))

logic = logic.simplify()
print(str(logic.simplify()))
print(str(algebra.parse(str(logic), simplify=True)))
#######################################################################

In this example we have a very simple case that tests out the difference between the simplify() function and the algebra.parse() function. And these are the results.

print 1 ==> (a&b)|(~a|~b)
print 2 ==> ~a|b|~b
print 3 ==> ~a|b|~b
print 4 ==> ~a|b|~b
print 5 ==> 1

As you can see. Both simlify() and algebra.parse() make an attempt to simplify the expression and it has technically made progress but clearly isn't finished. Both of them manage to do the same amount of work on the original input. Next you take the output an run it through this process again but this time when the shorter logic of '~a|b|~b' is parsed with the algebra object from a string it actually does get simplified further. This does not happen in every case but I have found it to be true here in this one.

I would love for this to work properly every time because I cannot even rely on running these statements multiple times in order to get these expressions worked down. I have to use this simplification process thousands of times with logic that contains tens of terms. If it fails to work on these small examples it will surely work on the much larger ones.

[pombredanne]

@kevin-cfs Thank you for the report!
The gist of the issue is that this implement a simplification algorithm, not a full boolean minimization (e.g. not Quine-McCluskey type algo as in https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm ). This likely explains why "( a & ~b & ~c )|( a & ( b | c ))" may not be minimized.
That would be possible but a significant piece of work. Ideally integrating an existing library like @tpircher https://github.com/tpircher/quine-mccluskey would likely be the best option.

On a separate note, if the following happens:...

It seems that when you take an expression and run the simplify() function on it then it will sometimes give different results than parsing the string form of it will.

then that would likely be a bug. In general I always prefer to use expression strings or build them from nested AND/OR/NOT rather than build them from Python variables and operators.

In earnest, the support of Python-level operators such as in your a, b = algebra.symbols(*'ab');logic = (a&b)|(~a|~b) is likely a source of subtle issues. Parsing a string is always a better option IMHO.

[kevin-cfs]

That’s great. Thanks so much for that explanation. I am already using strings since I have about 18,000 boolean arguments that can be combined in all sorts of ways and it is easier for me to create a string for every combination rather than 18,000 different variables all encapsulated in different combinations. I’ll have a look at this project and see if I can integrate it into my code. Currently yours looks very intuitive in terms of the inputs. This one is even harder to set up. But here’s hoping I figure it out. Kevin Burt Systems Engineer CFS Consulting C - 226-808-6705 www.cfsolutions-inc.com<http://www.cfsolutions-inc.com/> [cid:[email protected]] [cid:[email protected]] [1]<https://marketplace.bmc.com/companies/cfs-consulting-inc> [facebookcirclesig] <https://www.facebook.com/ControlMExperts> [linkedincirclesig] <https://www.linkedin.com/company/cfs-consulting-inc> [twittercirclesig] <https://twitter.com/controlmexperts> From: Philippe Ombredanne [mailto:[email protected]] Sent: October 25, 2019 10:11 AM To: bastikr/boolean.py <[email protected]> Cc: Kevin Burt <[email protected]>; Mention <[email protected]> Subject: Re: [bastikr/boolean.py] Boolean expressions not simplified correctly (#92) @kevin-cfs<https://github.com/kevin-cfs> Thank you for the report! The gist of the issue is that this implement a simplification algorithm, not a full boolean minimization (e.g. not Quine-McCluskey type algo as in https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm ). This likely explains why "( a & ~b & ~c )|( a & ( b | c ))" may not be minimized. That would be possible but a significant piece of work. Ideally integrating an existing library like @tpircher<https://github.com/tpircher> https://github.com/tpircher/quine-mccluskey would likely be the best option. On a separate note, if the following happens:... It seems that when you take an expression and run the simplify() function on it then it will sometimes give different results than parsing the string form of it will. then that would likely be a bug. In general I always prefer to use expression strings or build them from nested AND/OR/NOT rather than build them from Python variables and operators. In earnest, the support of Python-level operators such as in your a, b = algebra.symbols(*'ab');logic = (a&b)|(~a|~b) is likely a source of subtle issues. Parsing a string is always a better option IMHO. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub<#92?email_source=notifications&email_token=ALJUKPAQH527Y3X67MJJ64LQQL473A5CNFSM4JEDNDG2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOECIPGWY#issuecomment-546370395>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/ALJUKPGUCTSVZI7M3OFL2QTQQL473ANCNFSM4JEDNDGQ>.

[pombredanne]

The ideal case would be to add full minimization here in boolean.py. If you care about it, you contribution would be much welcomed!