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 N-dimensional point corresponds to one vertex of an N-dimensional 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 N-dimensional Boolean space
  • num2upoint() — Convert an integer into an untyped point in an N-dimensional Boolean space.
  • num2term() — Convert an integer into a min/max term in an N-dimensional 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 N-dimensional Boolean space
  • iter_upoints() — Iterate through all untyped points in an N-dimensional Boolean space
  • iter_terms() — Iterate through all min/max terms in an N-dimensional Boolean space
  • vpoint2point() — Convert a vector point into a point in an N-dimensional Boolean space

Interface Classes:

Interface Functions

pyeda.boolalg.boolfunc.num2point(num, vs)[source]

Convert num into a point in an N-dimensional 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 3-dimensional space formed by variables \(a\), \(b\), \(c\). Each vertex corresponds to a 3-dimensional point as summarized by the table:

         6-----------7  ===== ======= =================
        /|          /|   num   a b c        point
       / |         / |  ===== ======= =================
      /  |        /  |    0    0 0 0   {a:0, b:0, c:0}
     4-----------5   |    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}
     |   2-------|---3    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  0-----------1      ===== ======= =================

Note

The a b c column is the binary representation of num written in little-endian order.

pyeda.boolalg.boolfunc.num2upoint(num, vs)[source]

Convert num into an untyped point in an N-dimensional 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 N-dimensional 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 N-dimensional 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 3-dimensional space formed by functions \(f\), \(g\), \(h\). Each vertex corresponds to a min/max term as summarized by the table:

         6-----------7  ===== ======= ========== ==========
        /|          /|   num   f g h    minterm    maxterm
       / |         / |  ===== ======= ========== ==========
      /  |        /  |    0    0 0 0   f' g' h'   f  g  h
     4-----------5   |    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
     |   2-------|---3    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  0-----------1      ===== ======= ========= ===========

Note

The f g h column is the binary representation of num written in little-endian order.

pyeda.boolalg.boolfunc.point2upoint(point)[source]

Convert point into an untyped point.

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 N-dimensional 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 N-dimensional 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 N-dimensional 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 N-dimensional Boolean space.

The vpoint argument is a mapping from multi-dimensional 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) and exprvar('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.

__invert__()[source]

Boolean negation operator

\(f\) \(f'\)
0 1
1 0
__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
__add__(other)[source]

Concatenation operator

The other argument may be a Function or an farray.

__mul__(num)[source]

Repetition operator

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}\).

iter_domain()[source]

Iterate through all points in the domain.

iter_image()[source]

Iterate through all elements in the image.

iter_relation()[source]

Iterate through all (point, element) pairs in the relation.

restrict(point)[source]

Restrict a subset of support variables to \(\{0, 1\}\).

Returns a new function: \(f(x_i, \ldots)\)

\(f \: | \: x_i = b\)

vrestrict(vpoint)[source]

Expand all vectors in vpoint before applying restrict.

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 zero-dimensional point; a contradiction must return None.

satisfy_all()[source]

Iterate through all satisfying input points.

satisfy_count()[source]

Return the cardinality of the set of all satisfying input points.

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.

is_one()[source]

Return whether this function is one.

Note

This method will only look for a particular “one form”, and will NOT do a full search for a tautology.

static box(obj)[source]

Convert primitive types to a Function.

unbox()[source]

Return integer 0 or 1 if possible, otherwise return the Function.