pyeda.boolalg.expr — Expressions

The pyeda.boolalg.expr module implements Boolean functions represented as expressions.

Data Types:

abstract syntax tree

A nested tuple of entries that represents an expression. It is defined recursively:

ast := ('const', bool)
     | ('lit', uniqid)
     | (nary, ast, ...)
     | ('not', ast)
     | ('impl', ast, ast)
     | ('ite', ast, ast, ast)

bool := 0 | 1

uniqid := nonzero int

nary := 'or'
      | 'and'
      | 'xor'
      | 'eq'

Interface Functions:

  • exprvar() — Return a unique Expression variable
  • expr() — Convert an arbitrary object into an Expression
  • ast2expr() — Convert an abstract syntax tree to an Expression
  • expr2dimacscnf() — Convert an expression into an equivalent DIMACS CNF
  • upoint2exprpoint() — Convert an untyped point into an Expression point
  • Not() — Expression negation operator
  • Or() — Expression disjunction (sum, OR) operator
  • And() — Expression conjunction (product, AND) operator
  • Xor() — Expression exclusive or (XOR) operator
  • Equal() — Expression equality operator
  • Implies() — Expression implication operator
  • ITE() — Expression If-Then-Else (ITE) operator
  • Nor() — Expression NOR (not OR) operator
  • Nand() — Expression NAND (not AND) operator
  • Xnor() — Expression XNOR (not XOR) operator
  • Unequal() — Expression inequality (not EQUAL) operator
  • OneHot0()
  • OneHot()
  • NHot()
  • Majority()
  • AchillesHeel()
  • Mux()

Interface Classes:

Interface Functions

pyeda.boolalg.expr.exprvar(name, index=None)[source]

Return a unique Expression variable.

A Boolean variable is an abstract numerical quantity that may assume any value in the set \(B = \{0, 1\}\). The exprvar function returns a unique Boolean variable instance represented by a logic expression. Variable instances may be used to symbolically construct larger expressions.

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. If the name parameter is a single str, it will be converted to (name, ). The index parameter is optional; when empty, it will be converted to an empty tuple (). If the index parameter is a single int, it will be converted to (index, ).

Given identical names and indices, the exprvar function will always return the same variable:

>>> exprvar('a', 0) is exprvar('a', 0)
True

To create several single-letter variables:

>>> a, b, c, d = map(exprvar, 'abcd')

To create variables with multiple names (inner-most first):

>>> fifo_push = exprvar(('push', 'fifo'))
>>> fifo_pop = exprvar(('pop', 'fifo'))

See also

For creating arrays of variables with incremental indices, use the pyeda.boolalg.bfarray.exprvars() function.

pyeda.boolalg.expr.expr(obj, simplify=True)[source]

Convert an arbitrary object into an Expression.

pyeda.boolalg.expr.ast2expr(ast)[source]

Convert an abstract syntax tree to an Expression.

pyeda.boolalg.expr.expr2dimacscnf(ex)[source]

Convert an expression into an equivalent DIMACS CNF.

pyeda.boolalg.expr.upoint2exprpoint(upoint)[source]

Convert an untyped point into an Expression point.

See also

For definitions of points and untyped points, see the pyeda.boolalg.boolfunc module.

Operators

Primary Operators

pyeda.boolalg.expr.Not(x, simplify=True)[source]

Expression negation operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.Or(*xs, simplify=True)[source]

Expression disjunction (sum, OR) operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.And(*xs, simplify=True)[source]

Expression conjunction (product, AND) operator

If simplify is True, return a simplified expression.

Secondary Operators

pyeda.boolalg.expr.Xor(*xs, simplify=True)[source]

Expression exclusive or (XOR) operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.Equal(*xs, simplify=True)[source]

Expression equality operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.Implies(p, q, simplify=True)[source]

Expression implication operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.ITE(s, d1, d0, simplify=True)[source]

Expression If-Then-Else (ITE) operator

If simplify is True, return a simplified expression.

High Order Operators

pyeda.boolalg.expr.Nor(*xs, simplify=True)[source]

Expression NOR (not OR) operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.Nand(*xs, simplify=True)[source]

Expression NAND (not AND) operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.Xnor(*xs, simplify=True)[source]

Expression exclusive nor (XNOR) operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.Unequal(*xs, simplify=True)[source]

Expression inequality operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.OneHot0(*xs, simplify=True, conj=True)[source]

Return an expression that means “at most one input function is true”.

If simplify is True, return a simplified expression.

If conj is True, return a CNF. Otherwise, return a DNF.

pyeda.boolalg.expr.OneHot(*xs, simplify=True, conj=True)[source]

Return an expression that means “exactly one input function is true”.

If simplify is True, return a simplified expression.

If conj is True, return a CNF. Otherwise, return a DNF.

pyeda.boolalg.expr.Majority(*xs, simplify=True, conj=False)[source]

Return an expression that means “the majority of input functions are true”.

If simplify is True, return a simplified expression.

If conj is True, return a CNF. Otherwise, return a DNF.

pyeda.boolalg.expr.AchillesHeel(*xs, simplify=True)[source]

Return the Achille’s Heel function, defined as: \(\prod_{i=0}^{n/2-1}{X_{2i} + X_{2i+1}}\).

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.Mux(fs, sel, simplify=True)[source]

Return an expression that multiplexes a sequence of input functions over a sequence of select functions.

Interface Classes

Expression Tree Nodes

class pyeda.boolalg.expr.Expression(node)[source]

Boolean function represented by a logical expression

See also

This is a subclass of pyeda.boolalg.boolfunc.Function

The Expression class is useful for type checking, e.g. isinstance(f, Expression).

Do NOT create an Expression using the Expression constructor.

to_ast()[source]

Convert this node to an abstract syntax tree.

depth

Return the depth of the expression.

Expression depth is defined recursively:

  1. An atom node (constant or literal) has zero depth.
  2. A branch node (operator) has depth equal to the maximum depth of its children (arguments) plus one.
simplify()[source]

Return a simplified expression.

simple

Return True if the expression has been simplified.

to_nnf()[source]

Return an equivalent expression is negation normal form.

to_dnf()[source]

Return an equivalent expression in disjunctive normal form.

to_cnf()[source]

Return an equivalent expression in conjunctive normal form.

complete_sum()[source]

Return an equivalent DNF expression that includes all prime implicants.

expand(vs=None, conj=False)[source]

Return the Shannon expansion with respect to a list of variables.

cover

Return the DNF expression as a cover of cubes.

encode_inputs()[source]

Return a compact encoding for input variables.

encode_dnf()[source]

Encode as a compact DNF.

encode_cnf()[source]

Encode as a compact CNF.

tseitin(auxvarname='aux')[source]

Convert the expression to Tseitin’s encoding.

equivalent(other)[source]

Return True if this expression is equivalent to other.

to_dot(name='EXPR')[source]

Convert to DOT language representation.

class pyeda.boolalg.expr.Atom(node)[source]

Atom Expression

class pyeda.boolalg.expr.Constant(node)[source]

Constant Expression

class pyeda.boolalg.expr.Literal(node)[source]

Literal Expression

class pyeda.boolalg.expr.Complement(node)[source]

Complement Expression

class pyeda.boolalg.expr.Variable(bvar)[source]

Variable Expression

class pyeda.boolalg.expr.Operator(node)[source]

Operator Expression

class pyeda.boolalg.expr.NaryOp(node)[source]

Operator with N arguments

class pyeda.boolalg.expr.OrAndOp(node)[source]

Either an OR or AND operator (a lattice op)

class pyeda.boolalg.expr.OrOp(node)[source]

OR Operator

class pyeda.boolalg.expr.AndOp(node)[source]

AND Operator

class pyeda.boolalg.expr.XorOp(node)[source]

XOR Operator

class pyeda.boolalg.expr.EqualOp(node)[source]

Equal Operator

class pyeda.boolalg.expr.NotOp(node)[source]

NOT Operator

class pyeda.boolalg.expr.ImpliesOp(node)[source]

Implies Operator

class pyeda.boolalg.expr.IfThenElseOp(node)[source]

If-Then-Else (ITE) Operator

Normal Forms

class pyeda.boolalg.expr.NormalForm(nvars, clauses)[source]

Normal form expression

class pyeda.boolalg.expr.DisjNormalForm(nvars, clauses)[source]

Disjunctive normal form expression

class pyeda.boolalg.expr.ConjNormalForm(nvars, clauses)[source]

Conjunctive normal form expression

class pyeda.boolalg.expr.DimacsCNF(nvars, clauses)[source]

Wrapper class for a DIMACS CNF representation