pyeda.boolalg.boolfunc
— Boolean Functions¶
The pyeda.boolalg.boolfunc
module implements the fundamentals of
Boolean space, variables and functions.
Data Types:
 point
 A dictionary of
Variable => {0, 1}
mappings. For example,{a: 0, b: 1, c: 0, d: 1}
. An Ndimensional point corresponds to one vertex of an Ndimensional cube.  untyped point
 An untyped, immutable representation of a point,
represented as
(frozenset([int]), frozenset([int]))
. The integers are Variable uniqids. Index zero contains a frozenset of variables mapped to zero, and index one contains a frozenset of variables mapped to one. This representation is easier to manipulate than the point, and it is hashable for caching purposes.  term
 A tuple of \(N\) Boolean functions, intended to be used as the input of either an OR or AND function. An OR term is called a maxterm (product of sums), and an AND term is called a minterm (sum of products).
Interface Functions:
num2point()
— Convert an integer into a point in an Ndimensional Boolean space.num2upoint()
— Convert an integer into an untyped point in an Ndimensional Boolean space.num2term()
— Convert an integer into a min/max term in an Ndimensional Boolean space.point2upoint()
— Convert a point into an untyped point.point2term()
— Convert a point into a min/max term.iter_points()
— Iterate through all points in an Ndimensional Boolean space.iter_upoints()
— Iterate through all untyped points in an Ndimensional Boolean space.iter_terms()
— Iterate through all min/max terms in an Ndimensional Boolean space.vpoint2point()
— Convert a vector point into a point in an Ndimensional Boolean space.
Interface Classes:
Interface Functions¶

pyeda.boolalg.boolfunc.
num2point
(num, vs)[source]¶ Convert num into a point in an Ndimensional Boolean space.
The vs argument is a sequence of \(N\) Boolean variables. There are \(2^N\) points in the corresponding Boolean space. The dimension number of each variable is its index in the sequence.
The num argument is an int in range \([0, 2^N)\).
For example, consider the 3dimensional space formed by variables \(a\), \(b\), \(c\). Each vertex corresponds to a 3dimensional point as summarized by the table:
67 ===== ======= ================= / / num a b c point /  /  ===== ======= ================= /  /  0 0 0 0 {a:0, b:0, c:0} 45  1 1 0 0 {a:1, b:0, c:0}     2 0 1 0 {a:0, b:1, c:0}     3 1 1 0 {a:1, b:1, c:0}  23 4 0 0 1 {a:0, b:0, c:1}  /  / 5 1 0 1 {a:1, b:0, c:1} c b  /  / 6 0 1 1 {a:0, b:1, c:1} / / / 7 1 1 1 {a:1, b:1, c:1} +a 01 ===== ======= =================
Note
The
a b c
column is the binary representation of num written in littleendian order.

pyeda.boolalg.boolfunc.
num2upoint
(num, vs)[source]¶ Convert num into an untyped point in an Ndimensional Boolean space.
The vs argument is a sequence of \(N\) Boolean variables. There are \(2^N\) points in the corresponding Boolean space. The dimension number of each variable is its index in the sequence.
The num argument is an int in range \([0, 2^N)\).
See
num2point()
for a description of how num maps onto an Ndimensional point. This function merely converts the output to an immutable (untyped) form.

pyeda.boolalg.boolfunc.
num2term
(num, fs, conj=False)[source]¶ Convert num into a min/max term in an Ndimensional Boolean space.
The fs argument is a sequence of \(N\) Boolean functions. There are \(2^N\) points in the corresponding Boolean space. The dimension number of each function is its index in the sequence.
The num argument is an int in range \([0, 2^N)\).
If conj is
False
, return a minterm. Otherwise, return a maxterm.For example, consider the 3dimensional space formed by functions \(f\), \(g\), \(h\). Each vertex corresponds to a min/max term as summarized by the table:
67 ===== ======= ========== ========== / / num f g h minterm maxterm /  /  ===== ======= ========== ========== /  /  0 0 0 0 f' g' h' f g h 45  1 1 0 0 f g' h' f' g h     2 0 1 0 f' g h' f g' h     3 1 1 0 f g h' f' g' h  23 4 0 0 1 f' g' h f g h'  /  / 5 1 0 1 f g' h f' g h' h g  /  / 6 0 1 1 f' g h f g' h' / / / 7 1 1 1 f g h f' g' h' +f 01 ===== ======= ========= ===========
Note
The
f g h
column is the binary representation of num written in littleendian order.

pyeda.boolalg.boolfunc.
point2term
(point, conj=False)[source]¶ Convert point into a min/max term.
If conj is
False
, return a minterm. Otherwise, return a maxterm.

pyeda.boolalg.boolfunc.
iter_points
(vs)[source]¶ Iterate through all points in an Ndimensional Boolean space.
The vs argument is a sequence of \(N\) Boolean variables.

pyeda.boolalg.boolfunc.
iter_upoints
(vs)[source]¶ Iterate through all untyped points in an Ndimensional Boolean space.
The vs argument is a sequence of \(N\) Boolean variables.

pyeda.boolalg.boolfunc.
iter_terms
(fs, conj=False)[source]¶ Iterate through all min/max terms in an Ndimensional Boolean space.
The fs argument is a sequence of \(N\) Boolean functions.
If conj is
False
, yield minterms. Otherwise, yield maxterms.

pyeda.boolalg.boolfunc.
vpoint2point
(vpoint)[source]¶ Convert vpoint into a point in an Ndimensional Boolean space.
The vpoint argument is a mapping from multidimensional arrays of variables to matching arrays of \({0, 1}\). Elements from the values array will be converted to \({0, 1}\) using the int builtin function.
For example:
>>> from pyeda.boolalg.expr import exprvar >>> a = exprvar('a') >>> b00, b01, b10, b11 = map(exprvar, "b00 b01 b10 b11".split()) >>> vpoint = {a: 0, ((b00, b01), (b10, b11)): ["01", "01"]} >>> point = vpoint2point(vpoint) >>> point[a], point[b00], point[b01], point[b10], point[b11] (0, 0, 1, 0, 1)
The vpoint mapping is more concise if
B
is an farray:>>> from pyeda.boolalg.expr import exprvar >>> from pyeda.boolalg.bfarray import exprvars >>> a = exprvar('a') >>> B = exprvars('b', 2, 2) >>> vpoint = {a: 0, B: ["01", "01"]} >>> point = vpoint2point(vpoint) >>> point[a], point[B[0,0]], point[B[0,1]], point[B[1,0]], point[B[1,1]] (0, 0, 1, 0, 1)
The shape of the array must match the shape of its values:
>>> from pyeda.boolalg.bfarray import exprvars >>> X = exprvars('x', 2, 2) >>> vpoint = {X: "0101"} >>> point = vpoint2point(vpoint) Traceback (most recent call last): ... ValueError: expected 1:1 mapping from Variable => {0, 1}
Interface Classes¶

class
pyeda.boolalg.boolfunc.
Variable
(names, indices)[source]¶ Base class for a symbolic Boolean variable.
A Boolean variable is an abstract numerical quantity that may assume any value in the set \(B = \{0, 1\}\).
Note
Do NOT instantiate a
Variable
directly. Instead, use one of the concrete implementations:pyeda.boolalg.bdd.bddvar()
pyeda.boolalg.expr.exprvar()
,pyeda.boolalg.table.ttvar()
.A variable is defined by one or more names, and zero or more indices. Multiple names establish hierarchical namespaces, and multiple indices group several related variables.
Each variable has a unique, positive integer called the uniqid. This integer may be used to identify a variable that is represented by more than one data structure. For example,
bddvar('a', 0)
andexprvar('a', 0)
will refer to two different Variable instances, but both will share the same uniqid.All variables are implicitly ordered. If two variable names are identical, compare their indices. Otherwise, do a string comparison of their names. This is only useful where variable order matters, and is not meaningful in any algebraic sense.
For example, the following statements are true:
a == a
a < b
a[0] < a[1]
a[0][1] < a[0][2]

name
¶ Return the innermost variable name.

qualname
¶ Return the fully qualified name.

class
pyeda.boolalg.boolfunc.
Function
[source]¶ Abstract base class that defines an interface for a symbolic Boolean function of \(N\) variables.

__or__
(g)[source]¶ Boolean disjunction (sum, OR) operator
\(f\) \(g\) \(f + g\) 0 0 0 0 1 1 1 0 1 1 1 1

__and__
(g)[source]¶ Boolean conjunction (product, AND) operator
\(f\) \(g\) \(f \cdot g\) 0 0 0 0 1 0 1 0 0 1 1 1

__xor__
(g)[source]¶ Boolean exclusive or (XOR) operator
\(f\) \(g\) \(f \oplus g\) 0 0 0 0 1 1 1 0 1 1 1 0

support
¶ Return the support set of a function.
Let \(f(x_1, x_2, \dots, x_n)\) be a Boolean function of \(N\) variables.
The unordered set \(\{x_1, x_2, \dots, x_n\}\) is called the support of the function.

usupport
¶ Return the untyped support set of a function.

inputs
¶ Return the support set in name/index order.

top
¶ Return the first variable in the ordered support set.

degree
¶ Return the degree of a function.
A function from \(B^{N} \Rightarrow B\) is called a Boolean function of degree \(N\).

cardinality
¶ Return the cardinality of the relation \(B^{N} \Rightarrow B\).
Always equal to \(2^{N}\).

restrict
(point)[source]¶ Restrict a subset of support variables to \(\{0, 1\}\).
Returns a new function: \(f(x_i, \ldots)\)
\(f \:  \: x_i = b\)

compose
(mapping)[source]¶ Substitute a subset of support variables with other Boolean functions.
Returns a new function: \(f(g_i, \ldots)\)
\(f_1 \:  \: x_i = f_2\)

satisfy_one
()[source]¶ If this function is satisfiable, return a satisfying input point. A tautology may return a zerodimensional point; a contradiction must return None.

iter_cofactors
(vs=None)[source]¶ Iterate through the cofactors of a function over N variables.
The vs argument is a sequence of \(N\) Boolean variables.
The cofactor of \(f(x_1, x_2, \dots, x_i, \dots, x_n)\) with respect to variable \(x_i\) is: \(f_{x_i} = f(x_1, x_2, \dots, 1, \dots, x_n)\)
The cofactor of \(f(x_1, x_2, \dots, x_i, \dots, x_n)\) with respect to variable \(x_i'\) is: \(f_{x_i'} = f(x_1, x_2, \dots, 0, \dots, x_n)\)

cofactors
(vs=None)[source]¶ Return a tuple of the cofactors of a function over N variables.
The vs argument is a sequence of \(N\) Boolean variables.
The cofactor of \(f(x_1, x_2, \dots, x_i, \dots, x_n)\) with respect to variable \(x_i\) is: \(f_{x_i} = f(x_1, x_2, \dots, 1, \dots, x_n)\)
The cofactor of \(f(x_1, x_2, \dots, x_i, \dots, x_n)\) with respect to variable \(x_i'\) is: \(f_{x_i'} = f(x_1, x_2, \dots, 0, \dots, x_n)\)

smoothing
(vs=None)[source]¶ Return the smoothing of a function over a sequence of N variables.
The vs argument is a sequence of \(N\) Boolean variables.
The smoothing of \(f(x_1, x_2, \dots, x_i, \dots, x_n)\) with respect to variable \(x_i\) is: \(S_{x_i}(f) = f_{x_i} + f_{x_i'}\)
This is the same as the existential quantification operator: \(\exists \{x_1, x_2, \dots\} \: f\)

consensus
(vs=None)[source]¶ Return the consensus of a function over a sequence of N variables.
The vs argument is a sequence of \(N\) Boolean variables.
The consensus of \(f(x_1, x_2, \dots, x_i, \dots, x_n)\) with respect to variable \(x_i\) is: \(C_{x_i}(f) = f_{x_i} \cdot f_{x_i'}\)
This is the same as the universal quantification operator: \(\forall \{x_1, x_2, \dots\} \: f\)

derivative
(vs=None)[source]¶ Return the derivative of a function over a sequence of N variables.
The vs argument is a sequence of \(N\) Boolean variables.
The derivative of \(f(x_1, x_2, \dots, x_i, \dots, x_n)\) with respect to variable \(x_i\) is: \(\frac{\partial}{\partial x_i} f = f_{x_i} \oplus f_{x_i'}\)
This is also known as the Boolean difference.

is_zero
()[source]¶ Return whether this function is zero.
Note
This method will only look for a particular “zero form”, and will NOT do a full search for a contradiction.
