Fixing Issue 3155

[Sachin Joglekar]

Something that I suggested as a comment on my CustomFunction pull request- Can 'solve' function be extended to be able to solve boolean functions to convert them to the simplest form? initially thought of adding a separate function for this, but then thought that extending 'solve' would be a better idea.

As I am able to generate the simplest form of a function (SOP) from its truth table, I could go one step further by finding out the truth table of a function and using it to find its simplest form. If there are any better ways to do it, I could look it up too.

[Aaron Meurer]

I would use a separate function (solve_boolean() or something like
that). The problem with using solve is that there's no way to tell if
a Symbol is supposed to be a boolean Symbol, other than that it lives
in a boolean expression (see
http://code.google.com/p/sympy/issues/detail?id=1887#c26). So
something like solve(x) would be ambiguous.

Also, solve() currently accepts boolean expressions as assumptions, so
there may be some ambiguity there.

Actually, if all you're doing is simplifying them, wouldn't simplify()
be better than solve()? Can you give an explicit example of what you
are suggesting?

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/sympy/-/132XAqK9qcoJ.
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to
> sympy+un...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/sympy?hl=en.

[Sachin Joglekar]

I could make a separate function to simplify boolean expressions. Something like

>>> simplify_bool('(x & y) | (x & ~y)')

'x'

OR

instead of returning an expression(string) return a boolean function itself.

[Aaron Meurer]

I would check to see if something like that already exists first (I
don't remember if it does), and if it doesn't, this is how I would do
it. And it should definitely return the boolean function itself, not
the string.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To view this discussion on the web visit

> https://groups.google.com/d/msg/sympy/-/o6YZzKcF7y8J.

[Bharath M R]

I am not sure that its an easy task. The truth tables grow exponentially and you

will reach a stage where you cannot use the truth tables. I think it is a NP-hard

problem.

But there are a lot of approximate algorithms. One of the algorithms that I learnt

was using Binary decision diagrams. You can implement the algorithm, but it is

a greedy algorithm and might not give decent results.

Thanks,

Bharath M R

[Sachin Joglekar]

I do recognise the fact about that truth tables beyond a certain number of bits would be a problem. But I guess mine gives good results upto 10-12 bits with decent time(tested). But I don't think anyone needing to solving more complex functions than that would use sympy/python. In any case, I have submitted a pull request for the same. In future, if a better algorithm is implemented, mine can be substituted. But I will look at the algo you mentioned. 
(Just tested for 15 bits, but did take like half a second or so)