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)
     | ('var', names, indices)
     | ('not', ast)
     | ('implies', ast, ast)
     | ('ite', ast, ast, ast)
     | (func, ast, ...)

bool := 0 | 1

names := (name, ...)

indices := (index, ...)

func := 'or'
      | 'nor'
      | 'and'
      | 'nand'
      | 'xor'
      | 'xnor'
      | 'equal'
      | 'unequal'
      | 'onehot0'
      | 'onehot'
      | 'majority'
      | 'achillesheel'

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 to an Expression point
• Not() — Expression negation operator
• Or() — Expression disjunction (sum, OR) operator
• And() — Expression conjunction (product, AND) operator
• Nor() — Expression NOR (not OR) operator
• Nand() — Expression NAND (not AND) operator
• Xor() — Expression exclusive or (XOR) operator
• Xnor() — Expression exclusive nor (XNOR) operator
• Equal() — Expression equality operator
• Unequal() — Expression inequality operator
• Implies() — Expression implication operator
• ITE() — Expression If-Then-Else (ITE) operator
• OneHot0()
• OneHot()
• Majority()
• AchillesHeel()
• Mux()

Interface Classes:

• Expression
  • ExprConstant
  • ExprLiteral
    • ExprVariable
    • ExprComplement
  • ExprNot
  • ExprOrAnd
    • ExprOr
    • ExprAnd
  • ExprNorNand
    • ExprNor
    • ExprNand
  • ExprExclusive
    • ExprXor
    • ExprXnor
  • ExprEqualBase
    • ExprEqual
    • ExprUnequal
  • ExprImplies
  • ExprITE
• NormalForm
  • DisjNormalForm
  • ConjNormalForm
    • DimacsCNF

Interface Functions

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

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 an 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)

Convert an arbitrary object into an Expression.

pyeda.boolalg.expr.ast2expr(ast)

Convert an abstract syntax tree to an Expression.

pyeda.boolalg.expr.expr2dimacscnf(expr)

Convert an expression into an equivalent DIMACS CNF.

pyeda.boolalg.expr.upoint2exprpoint(upoint)

Convert an untyped point to an Expression point.

Operators

Primary Operators

pyeda.boolalg.expr.Not(arg, simplify=True)

Expression negation operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.Or(*args, simplify=True)

Expression disjunction (sum, OR) operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.And(*args, simplify=True)

Expression conjunction (product, AND) operator

If simplify is True, return a simplified expression.

Secondary Operators

pyeda.boolalg.expr.Nor(*args, simplify=True)

Expression NOR (not OR) operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.Nand(*args, simplify=True)

Expression NAND (not AND) operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.Xor(*args, simplify=True)

Expression exclusive or (XOR) operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.Xnor(*args, simplify=True)

Expression exclusive nor (XNOR) operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.Equal(*args, simplify=True)

Expression equality operator

If simplify is True, return a simplified expression.

pyeda.boolalg.expr.Unequal(*args, simplify=True)

Expression inequality operator

If simplify is True, return a simplified expression.

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

Expression implication operator

If simplify is True, return a simplified expression.

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

Expression If-Then-Else (ITE) operator

If simplify is True, return a simplified expression.

High Order Operators

pyeda.boolalg.expr.OneHot0(*args, simplify=True, conj=True)

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(*args, simplify=True, conj=True)

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(*args, simplify=True, conj=False)

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(*args, simplify=True)

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)

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

Boolean function represented by a logic expression

See also

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

An expression is a tree data structure with operators at the branches, and constants/literals at the leaves. A literal is a variable or its complement.

There are two ways to construct an expression:

• Convert another function representation.
• Use operators on existing expressions.

Use the exprvar function to create expression variables, and use the Python ~|&^ operators for NOT, OR, AND, XOR. Additionally, expressions overload >> for IMPLIES.

For example:

>>> a, b, c, d, p, q = map(exprvar, 'abcdpq')
>>> f = ~a | b & c ^ d
>>> g = p >> q

To create unsimplified expressions, use class constructors:

>>> ExprOr(0, a)
Or(0, a)

To create simplified expressions, use function form operators with simplify=True, or Python ~|&^ operators:

>>> Or(0, a)
a
>>> 0 | a
a

to_unicode()

Return a string representation using Unicode symbols.

to_latex()

Return a string representation using Latex.

__rshift__(g)

Boolean implication operator

\(f\)	\(g\)	\(f \implies g\)
0	0	1
0	1	1
1	0	0
1	1	1

invert()

Return an inverted expression.

simplify()

Return a simplified expression.

simplified

Return True if the expression is simplified.

factor(conj=False)

Return a factored expression.

A factored expression is one and only one of the following:

• A literal.
• A disjunction / conjunction of factored expressions.

Parameters

conj : bool

Always choose a conjunctive form when there’s a choice

depth

Return the depth of the expression tree.

Expression depth is defined recursively:

1. A leaf 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.

to_ast()

Return the expression converted to an abstract syntax tree.

expand(vs=None, conj=False)

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

flatten(op)

Return a factored, flattened expression.

Use the distributive law to flatten all nested expressions:

\[a + (b \cdot c) = (a + b) \cdot (a + c)\]\[a \cdot (b + c) = (a \cdot b) + (a \cdot c)\]

op : ExprOr or ExprAnd

The operator you want to flatten. For example, if you want to produce an ExprOr expression, flatten all the nested ExprAnds.

to_dnf(flatten=True)

Return the expression in disjunctive normal form.

to_cdnf(flatten=True)

Return the expression in canonical disjunctive normal form.

to_cnf(flatten=True)

Return the expression in conjunctive normal form.

to_ccnf(flatten=True)

Return the expression in canonical conjunctive normal form.

cover

Return the DNF expression as a cover of cubes.

absorb()

Return the DNF/CNF expression after absorption.

\[a + (a \cdot b) = a\]\[a \cdot (a + b) = a\]

reduce()

Reduce the DNF/CNF expression to a canonical form.

encode_inputs()

Return a compact encoding for input variables.

encode_dnf()

Encode as a compact DNF.

encode_cnf()

Encode as a compact CNF.

tseitin(auxvarname='aux')

Convert the expression to Tseitin’s encoding.

complete_sum()

Return a DNF that contains all prime implicants.

equivalent(other)

Return True if this expression is equivalent to other.

to_dot(name='EXPR')

Convert to DOT language representation.

class pyeda.boolalg.expr.ExprConstant

Expression constant

class pyeda.boolalg.expr.ExprLiteral

An instance of a variable or of its complement

class pyeda.boolalg.expr.ExprVariable(bvar)

Expression variable

class pyeda.boolalg.expr.ExprComplement(exprvar)

Expression complement

class pyeda.boolalg.expr.ExprNot(arg)

Expression NOT operator

class pyeda.boolalg.expr.ExprOrAnd(*args)

Base class for Expression OR/AND expressions

class pyeda.boolalg.expr.ExprOr(*args)

Expression OR operator

class pyeda.boolalg.expr.ExprAnd(*args)

Expression AND operator

class pyeda.boolalg.expr.ExprNorNand(*args)

Base class for Expression NOR/NAND expressions

class pyeda.boolalg.expr.ExprNor(*args)

Expression NOR operator

class pyeda.boolalg.expr.ExprNand(*args)

Expression NAND operator

class pyeda.boolalg.expr.ExprExclusive(*args)

Expression exclusive (XOR, XNOR) operator

class pyeda.boolalg.expr.ExprXor(*args)

Expression Exclusive OR (XOR) operator

class pyeda.boolalg.expr.ExprXnor(*args)

Expression Exclusive NOR (XNOR) operator

class pyeda.boolalg.expr.ExprEqualBase(*args)

Expression equality (EQUAL, UNEQUAL) operators

class pyeda.boolalg.expr.ExprEqual(*args)

Expression EQUAL operator

class pyeda.boolalg.expr.ExprUnequal(*args)

Expression UNEQUAL operator

class pyeda.boolalg.expr.ExprImplies(p, q)

Expression implication operator

class pyeda.boolalg.expr.ExprITE(s, d1, d0)

Expression if-then-else ternary operator

Normal Forms

class pyeda.boolalg.expr.NormalForm(nvars, clauses)

Normal form expression

class pyeda.boolalg.expr.DisjNormalForm(nvars, clauses)

Disjunctive normal form expression

class pyeda.boolalg.expr.ConjNormalForm(nvars, clauses)

Conjunctive normal form expression

class pyeda.boolalg.expr.DimacsCNF(nvars, clauses)

Wrapper class for a DIMACS CNF representation