pyeda.boolalg.expr — Expressions

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

Interface Functions:

• exprvar()
• expr()
• ast2expr()
• expr2dimacscnf()
• upoint2exprpoint()
• Not()
• Or()
• And()
• Nor()
• Nand()
• Xor()
• Xnor()
• Equal()
• Unequal()
• Implies()
• ITE()
• 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, we recommend using 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.

Logic Factory Functions

Primary Operators

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

Factory function for Boolean NOT expression.

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

Factory function for Boolean OR expression.

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

Factory function for Boolean AND expression.

Secondary Operators

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

Alias for Not(Or(...))

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

Alias for Not(And(...))

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

Factory function for Boolean XOR expression.

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

Factory function for Boolean XNOR expression.

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

Factory function for Boolean EQUAL expression.

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

Factory function for Boolean UNEQUAL expression.

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

Factory function for Boolean implication expression.

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

Factory function for Boolean If-Then-Else expression.

High Order Operators

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

Return an expression that means:

At most one input variable is true.

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

Return an expression that means:

Exactly one input variable is true.

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

Return an expression that means:

The majority of the input variables are true.

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

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

to_unicode()

Return a string representation using Unicode symbols.

to_latex()

Return a string representation using Latex.

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