search

bastikr / boolean.py

Implements boolean algebra in one module.
BSD 2-Clause "Simplified" License
76 stars 34 forks source link

Is the distribution rule not applied? #101

Open HA6Bots opened 3 years ago

HA6Bots commented 3 years ago

Thanks for the amazing library. However I had a query in regards to the simplification of the following expression: (a and not (b and c)) or (a and (b and c)) The expected output would be: a Looking through the code during the simplification process the distributive function doesn't appear to be called.

pombredanne commented 3 years ago

@HA6Bots Thanks! Would you care for a PR or for some pointers where you think this would be applied?

HA6Bots commented 3 years ago

Hi @pombredanne.

To be honest I'm not entirely sure where it should be applied because on its own the distribution law not would be enough to simplify the above expression.

See the screenshot below from this online boolean expression simplifier Capture

Their expression simplifier uses the distribution law, and then it's inverse, to manipulate the expression into a format where the absorption law can be used - allowing for the minimisation to continue till it gets the final result of a.

I attempted to recreate this library in C++ but I ran into the same roadblock as boolean.py (in terms of full minimisation). I've yet to find an open source boolean expression simplifier that fully minimises an expression fully. I wonder how they manage to achieve this on the website? Maybe via brute forcing different combinations of rules? Seems unlikely. I would love to figure this out though. It would be great to have an full open source boolean expression simplifier.

pombredanne commented 3 years ago

@HA6Bots a true boolean minimizer may not be possible ... or can take a lot of time! See https://en.wikipedia.org/wiki/Logic_optimization#Circuit_minimization_in_Boolean_algebra and https://en.wikipedia.org/wiki/Quine–McCluskey_algorithm#Complexity for a discussion For an Expresso implementation see @cjdrake https://github.com/cjdrake/pyeda for instance For a Quine-McCluskey implementation see @prekageo https://github.com/prekageo/optistate/blob/master/qm.py