trees

Tools for working with Boolean expression trees.

It should be noted that virtually all of the functionality within this module is presented with an easier-to-use interface in the expressions module.

trees.tree_node module

A node, and related classes, for use in expression trees.

class tt.trees.tree_node.BinaryOperatorExpressionTreeNode(operator_str, l_child, r_child)[source]

Bases: tt.trees.tree_node.ExpressionTreeNode

An expression tree node for binary operators.

__eq__(other)[source]

Return self==value.

__init__(operator_str, l_child, r_child)[source]

Initialize self. See help(type(self)) for accurate signature.

apply_de_morgans()[source]

Return a transformed node, with De Morgan’s Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all negated AND and OR operators transformed, following De Morgan’s Law.
Return type:ExpressionTreeNode
apply_idempotent_law()[source]

Returns a transformed node, with the Idempotent Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects

Returns:An expression tree node with the Idempotent Law applied to AND and OR operators.
Return type:ExpressionTreeNode

This transformation will apply the Idempotent Law to AND and OR expressions involving repeated operands. Here are a few examples:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and A').tree
>>> print(tree.apply_idempotent_law())
A
>>> tree = BooleanExpression('~B or ~~~B').tree
>>> print(tree.apply_idempotent_law())
~
`----B

In the latter of the two above examples, we see that this transformation will compare operands with negations condensed. This transformation will also prune redundant operands from CNF and DNF clauses. Let’s take a look:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and B and B and C and ~C and ~~C and D').tree
>>> print(tree.apply_idempotent_law())
and
`----and
|    `----and
|    |    `----and
|    |    |    `----A
|    |    |    `----B
|    |    `----C
|    `----~
|         `----C
`----D
apply_identity_law()[source]

Return a transformed node, with the Identity Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects.

This transformation will achieve the following effects by applying the Inverse Law to the AND and OR operators:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and 1').tree
>>> print(tree.apply_identity_law())
A
>>> tree = BooleanExpression('0 or B').tree
>>> print(tree.apply_identity_law())
B

It should also be noted that this transformation will also apply the annihilator properties of the logical AND and OR operators. For example:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and 0').tree
>>> print(tree.apply_identity_law())
0
>>> tree = BooleanExpression('1 or B').tree
>>> print(tree.apply_identity_law())
1
Returns:An expression tree node with AND and OR identities simplified.
Return type:ExpressionTreeNode
apply_inverse_law()[source]

Return a transformed node, with the Inverse Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with the Inverse Law applied to applicable clauses.
Return type:ExpressionTreeNode

This transformation will apply the Inverse Law to AND and OR expressions involving the negated and non-negated forms of a variable. Here are a few examples:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('~A and A').tree
>>> print(tree.apply_inverse_law())
0
>>> tree = BooleanExpression('B or !B').tree
>>> print(tree.apply_inverse_law())
1

Note that this transformation will not reduce expressions of constants; the transformation apply_identity_law will probably do what you want in this case, though.

This transformation will also reduce expressions in CNF or DNF that contain negated and non-negated forms of the same symbol. Let’s take a look:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A or B or C or ~B').tree
>>> print(tree.apply_inverse_law())
1
>>> tree = BooleanExpression('A and B and C and !B').tree
>>> print(tree.apply_inverse_law())
0
coalesce_negations()[source]

Return a transformed node, with consecutive negations coalesced.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all consecutive negations compressed into the minimal number of equivalent negations (either one or none).
Return type:ExpressionTreeNode
distribute_ands()[source]

Return a transformed nodes, with ANDs recursively distributed across ORed sub-expressions.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all applicable AND operators distributed across ORed sub-expressions.
Return type:ExpressionTreeNode
distribute_ors()[source]

Return a transformed nodes, with ORs recursively distributed across ANDed sub-expressions.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all applicable OR operators distributed across ANDed sub-expressions.
Return type:ExpressionTreeNode
evaluate(input_dict)[source]

Recursively evaluate this node.

This is an interface that should be defined in sub-classes. Node evaluation does no checking of the validity of inputs; they should be check before being passed here.

Parameters:input_dict (Dict{str: truthy) – A dictionary mapping expression symbols to the value for which they should be subsituted in expression evaluation.
Returns:The evaluation of the tree rooted at this node.
Return type:bool
operator

The actual operator object wrapped in this node.

Type:BooleanOperator
to_primitives()[source]

Return a transformed node, containing only NOTs, ANDs, and ORs.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all operators transformed to consist only of NOTs, ANDs, and ORs.
Return type:ExpressionTreeNode
class tt.trees.tree_node.ExpressionTreeNode(symbol_name, l_child=None, r_child=None)[source]

Bases: object

A base class for expression tree nodes.

This class is extended within tt and is not meant to be used directly.

If you plan to extend it, note that descendants of this class must compute the _is_cnf, _is_dnf, and _is_really_unary boolean attributes and the _non_negated_symbol_set and _negated_symbol_set set attributes within their initialization. Additionally, descendants of this class must implemented the __eq__ magic method (but not __ne__) as well as the private _copy transformation.

__eq__(other)[source]

Return self==value.

__init__(symbol_name, l_child=None, r_child=None)[source]

Initialize self. See help(type(self)) for accurate signature.

__ne__(other)[source]

Return self!=value.

__str__()[source]

Return str(self).

apply_de_morgans()[source]

Return a transformed node, with De Morgan’s Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all negated AND and OR operators transformed, following De Morgan’s Law.
Return type:ExpressionTreeNode
apply_idempotent_law()[source]

Returns a transformed node, with the Idempotent Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects

Returns:An expression tree node with the Idempotent Law applied to AND and OR operators.
Return type:ExpressionTreeNode

This transformation will apply the Idempotent Law to AND and OR expressions involving repeated operands. Here are a few examples:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and A').tree
>>> print(tree.apply_idempotent_law())
A
>>> tree = BooleanExpression('~B or ~~~B').tree
>>> print(tree.apply_idempotent_law())
~
`----B

In the latter of the two above examples, we see that this transformation will compare operands with negations condensed. This transformation will also prune redundant operands from CNF and DNF clauses. Let’s take a look:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and B and B and C and ~C and ~~C and D').tree
>>> print(tree.apply_idempotent_law())
and
`----and
|    `----and
|    |    `----and
|    |    |    `----A
|    |    |    `----B
|    |    `----C
|    `----~
|         `----C
`----D
apply_identity_law()[source]

Return a transformed node, with the Identity Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects.

This transformation will achieve the following effects by applying the Inverse Law to the AND and OR operators:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and 1').tree
>>> print(tree.apply_identity_law())
A
>>> tree = BooleanExpression('0 or B').tree
>>> print(tree.apply_identity_law())
B

It should also be noted that this transformation will also apply the annihilator properties of the logical AND and OR operators. For example:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and 0').tree
>>> print(tree.apply_identity_law())
0
>>> tree = BooleanExpression('1 or B').tree
>>> print(tree.apply_identity_law())
1
Returns:An expression tree node with AND and OR identities simplified.
Return type:ExpressionTreeNode
apply_inverse_law()[source]

Return a transformed node, with the Inverse Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with the Inverse Law applied to applicable clauses.
Return type:ExpressionTreeNode

This transformation will apply the Inverse Law to AND and OR expressions involving the negated and non-negated forms of a variable. Here are a few examples:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('~A and A').tree
>>> print(tree.apply_inverse_law())
0
>>> tree = BooleanExpression('B or !B').tree
>>> print(tree.apply_inverse_law())
1

Note that this transformation will not reduce expressions of constants; the transformation apply_identity_law will probably do what you want in this case, though.

This transformation will also reduce expressions in CNF or DNF that contain negated and non-negated forms of the same symbol. Let’s take a look:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A or B or C or ~B').tree
>>> print(tree.apply_inverse_law())
1
>>> tree = BooleanExpression('A and B and C and !B').tree
>>> print(tree.apply_inverse_law())
0
static build_tree(postfix_tokens)[source]

Build a tree from a list of expression tokens in postfix order.

This method does not check that the tokens are indeed in postfix order; undefined behavior will ensue if you pass tokens in an order other than postfix.

Parameters:

postfix_tokens (List[str]) – A list of string tokens from which to construct the tree of expression nodes.

Returns:

The root node of the constructed tree.

Return type:

ExpressionTreeNode

Raises:
coalesce_negations()[source]

Return a transformed node, with consecutive negations coalesced.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all consecutive negations compressed into the minimal number of equivalent negations (either one or none).
Return type:ExpressionTreeNode
distribute_ands()[source]

Return a transformed nodes, with ANDs recursively distributed across ORed sub-expressions.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all applicable AND operators distributed across ORed sub-expressions.
Return type:ExpressionTreeNode
distribute_ors()[source]

Return a transformed nodes, with ORs recursively distributed across ANDed sub-expressions.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all applicable OR operators distributed across ANDed sub-expressions.
Return type:ExpressionTreeNode
evaluate(input_dict)[source]

Recursively evaluate this node.

This is an interface that should be defined in sub-classes. Node evaluation does no checking of the validity of inputs; they should be check before being passed here.

Parameters:input_dict (Dict{str: truthy) – A dictionary mapping expression symbols to the value for which they should be subsituted in expression evaluation.
Returns:The evaluation of the tree rooted at this node.
Return type:bool
is_cnf

Whether the tree rooted at this node is in conjunctive normal form.

Type:bool
is_dnf

Whether the tree rooted at this node is in disjunctive normal form.

Type:bool
is_really_unary

Whether the tree rooted at this node contains no binary operators.

Type:bool
iter_clauses()[source]

Iterate the clauses in the expression tree rooted at this node.

If the normal form of the expression is ambiguous, then precedence will be given to conjunctive normal form.

Returns:Iterator of each CNF or DNF clause, rooted by a tree node, contained within the expression tree rooted at this node.
Return type:Iterator[ExpressionTreeNode]
Raises:RequiresNormalFormError – If this expression is not in conjunctive or disjunctive normal form.
iter_cnf_clauses()[source]

Iterate the clauses in conjunctive normal form order.

Returns:Iterator of each CNF clause, rooted by a tree node, contained within the expression tree rooted at this node.
Return type:Iterator[ExpressionTreeNode]
Raises:RequiresNormalFormError – If the expression tree rooted at this node is not in conjunctive normal form.
iter_dnf_clauses()[source]

Iterate the clauses in disjunctive normal form order.

Returns:Iterator of each DNF clause, rooted by a tree node, contained within the expression tree rooted at this node.
Return type:Iterator[ExpressionTreeNode]
Raises:RequiresNormalFormError – If the expression tree rooted at this node is not in disjunctive normal form.
l_child

This node’s left child; None indicates the absence of a child.

Type:ExpressionTreeNode or None
negated_symbol_set

A set of the negated symbols present in the tree rooted here.

Type:Set[str]
non_negated_symbol_set

A set of the non-negated symbols present in the tree rooted here.

Type:Set[str]
r_child

This node’s left child; None indicates the absence of a child.

Type:ExpressionTreeNode or None
symbol_name

The string operator/operand name wrapped in this node.

Type:str
to_cnf()[source]

Return a transformed node, in conjunctive normal form.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all operators transformed to consist only of NOTs, ANDs, and ORs.
Return type:ExpressionTreeNode
to_primitives()[source]

Return a transformed node, containing only NOTs, ANDs, and ORs.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all operators transformed to consist only of NOTs, ANDs, and ORs.
Return type:ExpressionTreeNode
class tt.trees.tree_node.OperandExpressionTreeNode(operand_str)[source]

Bases: tt.trees.tree_node.ExpressionTreeNode

An expression tree node for operands.

Nodes of this type will always be leaves in an expression tree.

__eq__(other)[source]

Return self==value.

__init__(operand_str)[source]

Initialize self. See help(type(self)) for accurate signature.

apply_de_morgans()[source]

Return a transformed node, with De Morgan’s Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all negated AND and OR operators transformed, following De Morgan’s Law.
Return type:ExpressionTreeNode
apply_idempotent_law()[source]

Returns a transformed node, with the Idempotent Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects

Returns:An expression tree node with the Idempotent Law applied to AND and OR operators.
Return type:ExpressionTreeNode

This transformation will apply the Idempotent Law to AND and OR expressions involving repeated operands. Here are a few examples:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and A').tree
>>> print(tree.apply_idempotent_law())
A
>>> tree = BooleanExpression('~B or ~~~B').tree
>>> print(tree.apply_idempotent_law())
~
`----B

In the latter of the two above examples, we see that this transformation will compare operands with negations condensed. This transformation will also prune redundant operands from CNF and DNF clauses. Let’s take a look:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and B and B and C and ~C and ~~C and D').tree
>>> print(tree.apply_idempotent_law())
and
`----and
|    `----and
|    |    `----and
|    |    |    `----A
|    |    |    `----B
|    |    `----C
|    `----~
|         `----C
`----D
apply_identity_law()[source]

Return a transformed node, with the Identity Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects.

This transformation will achieve the following effects by applying the Inverse Law to the AND and OR operators:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and 1').tree
>>> print(tree.apply_identity_law())
A
>>> tree = BooleanExpression('0 or B').tree
>>> print(tree.apply_identity_law())
B

It should also be noted that this transformation will also apply the annihilator properties of the logical AND and OR operators. For example:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and 0').tree
>>> print(tree.apply_identity_law())
0
>>> tree = BooleanExpression('1 or B').tree
>>> print(tree.apply_identity_law())
1
Returns:An expression tree node with AND and OR identities simplified.
Return type:ExpressionTreeNode
apply_inverse_law()[source]

Return a transformed node, with the Inverse Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with the Inverse Law applied to applicable clauses.
Return type:ExpressionTreeNode

This transformation will apply the Inverse Law to AND and OR expressions involving the negated and non-negated forms of a variable. Here are a few examples:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('~A and A').tree
>>> print(tree.apply_inverse_law())
0
>>> tree = BooleanExpression('B or !B').tree
>>> print(tree.apply_inverse_law())
1

Note that this transformation will not reduce expressions of constants; the transformation apply_identity_law will probably do what you want in this case, though.

This transformation will also reduce expressions in CNF or DNF that contain negated and non-negated forms of the same symbol. Let’s take a look:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A or B or C or ~B').tree
>>> print(tree.apply_inverse_law())
1
>>> tree = BooleanExpression('A and B and C and !B').tree
>>> print(tree.apply_inverse_law())
0
coalesce_negations()[source]

Return a transformed node, with consecutive negations coalesced.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all consecutive negations compressed into the minimal number of equivalent negations (either one or none).
Return type:ExpressionTreeNode
distribute_ands()[source]

Return a transformed nodes, with ANDs recursively distributed across ORed sub-expressions.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all applicable AND operators distributed across ORed sub-expressions.
Return type:ExpressionTreeNode
distribute_ors()[source]

Return a transformed nodes, with ORs recursively distributed across ANDed sub-expressions.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all applicable OR operators distributed across ANDed sub-expressions.
Return type:ExpressionTreeNode
evaluate(input_dict)[source]

Recursively evaluate this node.

This is an interface that should be defined in sub-classes. Node evaluation does no checking of the validity of inputs; they should be check before being passed here.

Parameters:input_dict (Dict{str: truthy) – A dictionary mapping expression symbols to the value for which they should be subsituted in expression evaluation.
Returns:The evaluation of the tree rooted at this node.
Return type:bool
to_primitives()[source]

Return a transformed node, containing only NOTs, ANDs, and ORs.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all operators transformed to consist only of NOTs, ANDs, and ORs.
Return type:ExpressionTreeNode
class tt.trees.tree_node.UnaryOperatorExpressionTreeNode(operator_str, l_child)[source]

Bases: tt.trees.tree_node.ExpressionTreeNode

An expression tree node for unary operators.

__eq__(other)[source]

Return self==value.

__init__(operator_str, l_child)[source]

Initialize self. See help(type(self)) for accurate signature.

apply_de_morgans()[source]

Return a transformed node, with De Morgan’s Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all negated AND and OR operators transformed, following De Morgan’s Law.
Return type:ExpressionTreeNode
apply_idempotent_law()[source]

Returns a transformed node, with the Idempotent Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects

Returns:An expression tree node with the Idempotent Law applied to AND and OR operators.
Return type:ExpressionTreeNode

This transformation will apply the Idempotent Law to AND and OR expressions involving repeated operands. Here are a few examples:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and A').tree
>>> print(tree.apply_idempotent_law())
A
>>> tree = BooleanExpression('~B or ~~~B').tree
>>> print(tree.apply_idempotent_law())
~
`----B

In the latter of the two above examples, we see that this transformation will compare operands with negations condensed. This transformation will also prune redundant operands from CNF and DNF clauses. Let’s take a look:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and B and B and C and ~C and ~~C and D').tree
>>> print(tree.apply_idempotent_law())
and
`----and
|    `----and
|    |    `----and
|    |    |    `----A
|    |    |    `----B
|    |    `----C
|    `----~
|         `----C
`----D
apply_identity_law()[source]

Return a transformed node, with the Identity Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects.

This transformation will achieve the following effects by applying the Inverse Law to the AND and OR operators:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and 1').tree
>>> print(tree.apply_identity_law())
A
>>> tree = BooleanExpression('0 or B').tree
>>> print(tree.apply_identity_law())
B

It should also be noted that this transformation will also apply the annihilator properties of the logical AND and OR operators. For example:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A and 0').tree
>>> print(tree.apply_identity_law())
0
>>> tree = BooleanExpression('1 or B').tree
>>> print(tree.apply_identity_law())
1
Returns:An expression tree node with AND and OR identities simplified.
Return type:ExpressionTreeNode
apply_inverse_law()[source]

Return a transformed node, with the Inverse Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with the Inverse Law applied to applicable clauses.
Return type:ExpressionTreeNode

This transformation will apply the Inverse Law to AND and OR expressions involving the negated and non-negated forms of a variable. Here are a few examples:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('~A and A').tree
>>> print(tree.apply_inverse_law())
0
>>> tree = BooleanExpression('B or !B').tree
>>> print(tree.apply_inverse_law())
1

Note that this transformation will not reduce expressions of constants; the transformation apply_identity_law will probably do what you want in this case, though.

This transformation will also reduce expressions in CNF or DNF that contain negated and non-negated forms of the same symbol. Let’s take a look:

>>> from tt import BooleanExpression
>>> tree = BooleanExpression('A or B or C or ~B').tree
>>> print(tree.apply_inverse_law())
1
>>> tree = BooleanExpression('A and B and C and !B').tree
>>> print(tree.apply_inverse_law())
0
coalesce_negations()[source]

Return a transformed node, with consecutive negations coalesced.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all consecutive negations compressed into the minimal number of equivalent negations (either one or none).
Return type:ExpressionTreeNode
distribute_ands()[source]

Return a transformed nodes, with ANDs recursively distributed across ORed sub-expressions.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all applicable AND operators distributed across ORed sub-expressions.
Return type:ExpressionTreeNode
distribute_ors()[source]

Return a transformed nodes, with ORs recursively distributed across ANDed sub-expressions.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all applicable OR operators distributed across ANDed sub-expressions.
Return type:ExpressionTreeNode
evaluate(input_dict)[source]

Recursively evaluate this node.

This is an interface that should be defined in sub-classes. Node evaluation does no checking of the validity of inputs; they should be check before being passed here.

Parameters:input_dict (Dict{str: truthy) – A dictionary mapping expression symbols to the value for which they should be subsituted in expression evaluation.
Returns:The evaluation of the tree rooted at this node.
Return type:bool
operator

The actual operator object wrapped in this node.

Type:BooleanOperator
to_primitives()[source]

Return a transformed node, containing only NOTs, ANDs, and ORs.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all operators transformed to consist only of NOTs, ANDs, and ORs.
Return type:ExpressionTreeNode