Repository: sympy/sympy
Pull request: SOPform and POSform accepts terms as integers
<!-- Your title above should be a short description of what
was changed. Do not include the issue number in the title. -->

#### References to other Issues or PRs
<!-- If this pull request fixes an issue, write "Fixes #NNNN" in that exact
format, e.g. "Fixes #1234". See
https://github.com/blog/1506-closing-issues-via-pull-requests . Please also
write a comment on that issue linking back to this pull request once it is
open. -->
Closes #11464 
Closes #14700 

#### Brief description of what is fixed or changed
`SOPform` and `POSform` can now take integers and dicts as inputs as well as lists of binary numbers.

I also ended up fixing an issue with the minimization code, which didn't always result in fewest terms as outlined in #14700 

Good thing is that I now sort of understand the Quine-McCluskey algorithm.

#### Other comments
There is basically no code left from #11464 but better to have a liberate interpretation of building on previous PRs.

#### Release Notes

<!-- Write the release notes for this release below. See
https://github.com/sympy/sympy/wiki/Writing-Release-Notes for more information
on how to write release notes. The bot will check your release notes
automatically to see if they are formatted correctly. -->

<!-- BEGIN RELEASE NOTES -->
* logic 
   * `SOPform` and `POSform` can now use integers and dicts to indicate terms.
  * Boolean simplification algorithm fixed to reduce the number of terms.
<!-- END RELEASE NOTES -->


Problem statement:
boolalg.SOPform() does not give the simplest form.
Hi, developers of Sympy.

@mpraiser and I were using `boolalg.SOPform()` to get the smallest sum of products. But it does not seem to give the *smallest* sum of products.

```python
In [136]: v
Out[136]: [A, B, C, D, E, F, G, H]

In [137]: q
Out[137]: 
(B ∧ D ∧ H ∧ ¬F) ∨ (B ∧ H ∧ ¬C ∧ ¬D) ∨ (B ∧ H ∧ ¬C ∧ ¬F) ∨ (B ∧ H ∧ ¬D ∧ ¬G) ∨
 (B ∧ H ∧ ¬F ∧ ¬G) ∨ (C ∧ G ∧ ¬B ∧ ¬D) ∨ (C ∧ G ∧ ¬D ∧ ¬H) ∨ (C ∧ G ∧ ¬F ∧ ¬H)
 ∨ (D ∧ F ∧ H ∧ ¬B) ∨ (D ∧ F ∧ ¬G ∧ ¬H) ∨ (B ∧ D ∧ F ∧ ¬C ∧ ¬H) ∨ (D ∧ E ∧ F ∧
 ¬B ∧ ¬C) ∨ (D ∧ F ∧ ¬A ∧ ¬B ∧ ¬C) ∨ (D ∧ F ∧ ¬A ∧ ¬C ∧ ¬H) ∨ (A ∧ B ∧ D ∧ F ∧
 ¬E ∧ ¬H)

In [138]: qq
Out[138]: 
(B ∧ D ∧ H ∧ ¬F) ∨ (B ∧ H ∧ ¬C ∧ ¬D) ∨ (B ∧ H ∧ ¬D ∧ ¬G) ∨ (C ∧ G ∧ ¬B ∧ ¬D) ∨
 (C ∧ G ∧ ¬D ∧ ¬H) ∨ (C ∧ G ∧ ¬F ∧ ¬H) ∨ (D ∧ F ∧ H ∧ ¬B) ∨ (D ∧ F ∧ ¬G ∧ ¬H) 
∨ (B ∧ D ∧ F ∧ ¬C ∧ ¬H) ∨ (D ∧ E ∧ F ∧ ¬C ∧ ¬H) ∨ (D ∧ F ∧ ¬A ∧ ¬C ∧ ¬H) ∨ (A 
∧ B ∧ C ∧ G ∧ ¬E ∧ ¬H)

In [139]: list(boolalg.truth_table(q, v)) == list(boolalg.truth_table(qq, v))
Out[139]: True

In [140]: len(q.args)
Out[140]: 15

In [141]: len(qq.args)
Out[141]: 12
```

`q` is the result `boolalg.SOPform()` gives me and it contains 15 product terms. `qq` is the result from another logic simplification program written by @mpraiser and it contains 12 product terms. They share the same truth table, but `qq` is obviously *simpler* than `q` since it contains less product terms than `qq`.

And when `boolalg.simplify_logic()` is performed on `q` and `qq`, they yield the same result as `q` as if `q` is the *simplest* already.

```python
In [155]: boolalg.simplify_logic(q, "dnf") == q
Out[155]: True

In [156]: boolalg.simplify_logic(qq, "dnf") == q
Out[156]: True
```

How can I solve this? Thanks:)

Hints from issue discussion:
Can you show the code you used to generate the above outputs? It's difficult to investigate this seeing only the output.

Commit message: Incorporated function into standard SOPform and POSform

Patch to review:
diff --git a/sympy/logic/boolalg.py b/sympy/logic/boolalg.py
index 8bbea2125c94..2633a5644c25 100644
--- a/sympy/logic/boolalg.py
+++ b/sympy/logic/boolalg.py
@@ -493,7 +493,7 @@ def diff(self, *symbols, **assumptions):
         return Derivative(self, *symbols, **assumptions)
 
     def _eval_derivative(self, x):
-        from sympy.core.relational import Eq, Relational
+        from sympy.core.relational import Eq
         from sympy.functions.elementary.piecewise import Piecewise
         if x in self.binary_symbols:
             return Piecewise(
@@ -1869,6 +1869,12 @@ def _rem_redundancy(l1, terms):
 
     return essential
 
+def _binary_from_list_or_number(lon, bits):
+        def tobin(n, bits):
+            return [(n >> k) & 1 for k in reversed(range(0, bits))]
+        if isinstance(lon, int):
+            return tobin(lon, bits)
+        return list(lon)
 
 def SOPform(variables, minterms, dontcares=None):
     """
@@ -1897,6 +1903,20 @@ def SOPform(variables, minterms, dontcares=None):
     >>> SOPform([w, x, y, z], minterms, dontcares)
     (y & z) | (z & ~w)
 
+    The terms can also be represented as integers:
+
+    >>> minterms = [1, 3, 7, 11, 15]
+    >>> dontcares = [0, 2, 5]
+    >>> SOPform([w, x, y, z], minterms, dontcares)
+    (y & z) | (z & ~w)
+
+    Or a combination:
+
+    >>> minterms = [1, 3, 7, 11, [1, 1, 1, 1]]
+    >>> dontcares = [[0, 0, 0, 0], 2, 5]
+    >>> SOPform([w, x, y, z], minterms, dontcares)
+    (y & z) | (z & ~w)
+
     References
     ==========
 
@@ -1907,8 +1927,9 @@ def SOPform(variables, minterms, dontcares=None):
     if minterms == []:
         return false
 
-    minterms = [list(i) for i in minterms]
-    dontcares = [list(i) for i in (dontcares or [])]
+    bits = len(variables)
+    minterms = [_binary_from_list_or_number(i, bits) for i in minterms]
+    dontcares = [_binary_from_list_or_number(i, bits) for i in (dontcares or [])]
     for d in dontcares:
         if d in minterms:
             raise ValueError('%s in minterms is also in dontcares' % d)
@@ -1949,6 +1970,20 @@ def POSform(variables, minterms, dontcares=None):
     >>> POSform([w, x, y, z], minterms, dontcares)
     z & (y | ~w)
 
+    The terms can also be represented as integers:
+
+    >>> minterms = [1, 3, 7, 11, 15]
+    >>> dontcares = [0, 2, 5]
+    >>> POSform([w, x, y, z], minterms, dontcares)
+    z & (y | ~w)
+
+    Or a combination:
+
+    >>> minterms = [1, 3, 7, 11, [1, 1, 1, 1]]
+    >>> dontcares = [[0, 0, 0, 0], 2, 5]
+    >>> POSform([w, x, y, z], minterms, dontcares)
+    z & (y | ~w)
+
     References
     ==========
 
@@ -1959,8 +1994,9 @@ def POSform(variables, minterms, dontcares=None):
     if minterms == []:
         return false
 
-    minterms = [list(i) for i in minterms]
-    dontcares = [list(i) for i in (dontcares or [])]
+    bits = len(variables)
+    minterms = [_binary_from_list_or_number(i, bits) for i in minterms]
+    dontcares = [_binary_from_list_or_number(i, bits) for i in (dontcares or [])]
     for d in dontcares:
         if d in minterms:
             raise ValueError('%s in minterms is also in dontcares' % d)
diff --git a/sympy/logic/tests/test_boolalg.py b/sympy/logic/tests/test_boolalg.py
index 6c737c3fcb6a..4631f9b84993 100644
--- a/sympy/logic/tests/test_boolalg.py
+++ b/sympy/logic/tests/test_boolalg.py
@@ -226,6 +226,21 @@ def test_simplification():
         Or(And(Not(w), z), And(y, z)))
     assert POSform([w, x, y, z], minterms, dontcares) == And(Or(Not(w), y), z)
 
+    minterms = [1, 3, 7, 11, 15]
+    dontcares = [0, 2, 5]
+    assert (
+        SOPform([w, x, y, z], minterms, dontcares) ==
+        Or(And(Not(w), z), And(y, z)))
+    assert POSform([w, x, y, z], minterms, dontcares) == And(Or(Not(w), y), z)
+
+    minterms = [1, [0, 0, 1, 1], 7, [1, 0, 1, 1],
+        [1, 1, 1, 1]]
+    dontcares = [0, [0, 0, 1, 0], 5]
+    assert (
+        SOPform([w, x, y, z], minterms, dontcares) ==
+        Or(And(Not(w), z), And(y, z)))
+    assert POSform([w, x, y, z], minterms, dontcares) == And(Or(Not(w), y), z)
+
     # test simplification
     ans = And(A, Or(B, C))
     assert simplify_logic(A & (B | C)) == ans


Code review comments:
diff_hunk: @@ -1869,6 +1869,12 @@ def _rem_redundancy(l1, terms):
 
     return essential
 
+def _binary_from_list_or_number(lon, bits):
+        def tobin(n, bits):
path: sympy/logic/boolalg.py
text: @user1:
You can use/modify `ibin` from iterables.

@author:
Thanks!

diff_hunk: @@ -1869,6 +1869,12 @@ def _rem_redundancy(l1, terms):
 
     return essential
 
+def _binary_from_list_or_number(lon, bits):
+        def tobin(n, bits):
+            return [(n >> k) & 1 for k in reversed(range(0, bits))]
+        if isinstance(lon, int):
+            return tobin(lon, bits)
+        return list(lon)
path: sympy/logic/boolalg.py
text: @user1:
it doesn't look like a check is done that the list has `bits` bits in it; that should probably be verified

@author:
OK! I was thinking that _maybe_ it also secretly supported some sort of generator, since the original code plainly made `list` out of everything. But that may in hindsight be to support tuples etc.

Indeed makes sense!