sympy.logic - Part 1

As I have mentioned before, my first work for SymPy was for its logic module. Most of it took inspiration from the digital design and CS-Logic classes I took in my 3rd semester at college. In this post and the next I will try to explain some of the cool features of this module that I have used applied in useful ways.

Note - Quite a bit of this work was done just a few months back by Christopher Smith(smichr) and me, and hence is NOT included in the lastest version of SymPy(0.7.2), but will find its way into SymPy 0.7.3. Therefore, there is no documentation on the official website also. However, interested people can fork the SymPy source from its github repo - There is enough of in-code docs to help you.

I) Using the truth table to find SOP/POS form 

This is quite useful in digital design, and I myself used this quite a few number of times during my course.
Suppose you have to find the SOP (sum of products) form of a boolean function that has the following specs-
1. The variables (literals) are a,b,c and d.
2. The function MUST return True for the following combinations (in order-a,b,c,d)-
0,0,0,1
0,0,1,1
0,1,1,1
1,0,1,1
1,1,1,1
 where 0-false and 1-true
3. The function may give True or False (a dont-care) for the following combinations-
0,0,0,0
0,0,1,0
0,1,0,1

For those of you who may ask WHY we won't care. Simple- These combinations will never occur in our application if used rightly, OR we dont' care about the output even if they do. For example, a function that deals with binary representations of digits from 0-9 will not care about the inputs from 1001, as they will not occur in operation.
4. All the rest of the combinations must return False

Python session for this? Here it is -

>>> from sympy.logic import SOPform
>>> minterms = [[0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 1, 1]]
>>> dontcares = [[0, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 1]]
>>> SOPform(['a','b','c','d'], minterms, dontcares)

Output - Or(And(Not(a), d), And(c, d))

POS form?

>>> from sympy.logic import POSform
>>> POSform(['a','b','c','d'], minterms, dontcares)

Output - And(Or(Not(a), c), d)

II) Simplification of boolean expressions

Suppose you want to simplify a cumbersome boolean expression to something simple. How?

Use simplify_logic.

Example expression --> "AB(A + B)" [Symbols take their usual meaning]

On paper, you will have to take the following steps-

AB(A + B)
(A + B)(A + B)	DeMorgan's Law
A + BB	Distributive law. This step uses the fact that or distributes over and. It can look a bit strange since addition does not distribute over multiplication.
A	Complement, Identity.

SymPy console session?

>>> from sympy.logic import simplify_logic
>>> to_be_simplified = '~(A & B) & (~A | B)'
>>> simplify_logic(to_be_simplified)
Output - Not(A)

Period.

III) Conversion between cnf and dnf forms

Conversion of boolean expressions to CNF or DNF forms is also possible.

The code to do this is quite simple -

>>> from sympy.logic.boolalg import to_dnf

>>> from sympy.abc import A, B, C, D

>>> to_dnf(B & (A | C))

    

Output - Or(And(A, B), And(B, C))

sympy.abc generates 'symbols' - Variables that can be used to denote any value. The entire framework of SymPy is based on the concept of Symbols (hence, Symbolic-Py)

Thats all for now. In the next post, I will continue with some other features like boolean equality mapping and checking for true-ness of a statement given a set of statements (and using it to find redundancies in databases).