<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Introduction
In this notebook, we will demonstrate some of the differences between SymPy's logic module, and PyEDA's logic expressions.
Step1:  Create Variables
The xs array is a tuple of SymPy symbolic variables,
and the ys array is a PyEDA function array.
Step2:  Basic Boolean Functions
Create a SymPy XOR function
Step3:  Create a PyEDA XOR function
Step4:  SymPy atoms method is similar to PyEDA's support property
Step5:  SymPy's subs method is similar to PyEDA's restrict method
Step6:  Conversion to NNF
Conversion to negation normal form is also similar. One difference is that SymPy inverts the variables by applying a Not operator, but PyEDA converts inverted variables to complements (a negative literal).
Step7:  Conversion to DNF
Conversion to disjunctive normal form, on the other hand, has some differences. With only four input variables, SymPy takes a couple seconds to do the calculation. The output is large, with unsimplified values and redundant clauses.
Step8:  PyEDA's DNF conversion is minimal
Step9:  It's a little hard to do an apples-to-apples comparison, because 1) SymPy is pure Python and 2) the algorithms are probably different.
The simplify_logic function actually looks better for comparison
Step10:  Running this experiment from N=2 to N=6 shows that PyEDA's runtime grows significantly slower.
Step11:  Going a bit further, things get worse.
These numbers are from my laptop
<ASSISTANT_TASK:>
Python Code:
import sympy
import pyeda.boolalg.expr
import pyeda.boolalg.bfarray
Explanation: Introduction
In this notebook, we will demonstrate some of the differences between SymPy's logic module, and PyEDA's logic expressions.
End of explanation
xs = sympy.symbols(",".join("x%d" % i for i in range(64)))
ys = pyeda.boolalg.bfarray.exprvars('y', 64)
Explanation: Create Variables
The xs array is a tuple of SymPy symbolic variables,
and the ys array is a PyEDA function array.
End of explanation
f = sympy.Xor(*xs[:4])
Explanation: Basic Boolean Functions
Create a SymPy XOR function:
End of explanation
g = pyeda.boolalg.expr.Xor(*ys[:4])
Explanation: Create a PyEDA XOR function:
End of explanation
f.atoms()
g.support
Explanation: SymPy atoms method is similar to PyEDA's support property:
End of explanation
f.subs({xs[0]: 0, xs[1]: 1})
g.restrict({ys[0]: 0, ys[1]: 1})
Explanation: SymPy's subs method is similar to PyEDA's restrict method:
End of explanation
sympy.to_nnf(f)
type(sympy.Not(xs[0]))
g.to_nnf()
type(~ys[0])
Explanation: Conversion to NNF
Conversion to negation normal form is also similar. One difference is that SymPy inverts the variables by applying a Not operator, but PyEDA converts inverted variables to complements (a negative literal).
End of explanation
sympy.to_dnf(f)
Explanation: Conversion to DNF
Conversion to disjunctive normal form, on the other hand, has some differences. With only four input variables, SymPy takes a couple seconds to do the calculation. The output is large, with unsimplified values and redundant clauses.
End of explanation
g.to_dnf()
Explanation: PyEDA's DNF conversion is minimal:
End of explanation
from sympy.logic import simplify_logic
simplify_logic(f)
simplify_logic(f)
Explanation: It's a little hard to do an apples-to-apples comparison, because 1) SymPy is pure Python and 2) the algorithms are probably different.
The simplify_logic function actually looks better for comparison:
End of explanation
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
N = 5
sympy_times = (.000485,  .000957, .00202,  .00426, .0103)
pyeda_times = (.0000609, .000104, .000147, .00027, .000451)
ind = np.arange(N)  # the x locations for the groups
width = 0.35        # the width of the bars
fig, ax = plt.subplots()
rects1 = ax.bar(ind, sympy_times, width, color='r')
rects2 = ax.bar(ind + width, pyeda_times, width, color='y')
# add some text for labels, title and axes ticks
ax.set_ylabel('Time (s)')
ax.set_title('SymPy vs. PyEDA: Xor(x[0], x[1], ..., x[n-1]) to DNF')
ax.set_xticks(ind + width)
ax.set_xticklabels(('N=2', 'N=3', 'N=4', 'N=5', 'N=6'))
ax.legend((rects1[0], rects2[0]), ('SymPy', 'PyEDA'))
plt.show()
Explanation: Running this experiment from N=2 to N=6 shows that PyEDA's runtime grows significantly slower.
End of explanation
sympy.Equivalent(xs[0], xs[1], 0)
pyeda.boolalg.expr.Equal(ys[0], ys[1], 0)
sympy.ITE(xs[0], 0, xs[1])
pyeda.boolalg.expr.ITE(ys[0], 0, ys[1])
sympy.Or(xs[0], sympy.Or(xs[1], xs[2]))
pyeda.boolalg.expr.Or(ys[0], pyeda.boolalg.expr.Or(ys[1], ys[2]))
sympy.Xor(xs[0], sympy.Not(sympy.Xor(xs[1], xs[2])))
pyeda.boolalg.expr.Xor(ys[0], pyeda.boolalg.expr.Xnor(ys[1], ys[2]))
Explanation: Going a bit further, things get worse.
These numbers are from my laptop:
|  N | sympy    | pyeda    | ratio  |
|----|----------|----------|--------|
|  2 |  .000485 | .0000609 |   7.96 |
|  3 |  .000957 | .000104  |   9.20 |
|  4 |  .00202  | .000147  |  13.74 |
|  5 |  .00426  | .00027   |  15.78 |
|  6 |  .0103   | .000451  |  22.84 |
|  7 |  .0231   | .000761  |  30.35 |
|  8 |  .0623   | .00144   |  43.26 |
|  9 |  .162    | .00389   |  41.65 |
| 10 |  .565    | .00477   | 118.45 |
| 11 | 1.78     | .012     | 148.33 |
| 12 | 6.46     | .0309    | 209.06 |
Simplification
SymPy supports some obvious simplifications, but PyEDA supports more. Here are a few examples.
End of explanation
<END_TASK>