ssg.ext.boolean.boolean module

Boolean expressions algebra.

This module defines a Boolean algebra over the set {TRUE, FALSE} with boolean variables called Symbols and the boolean functions AND, OR, NOT.

Some basic logic comparison is supported: two expressions can be compared for equivalence or containment. Furthermore you can simplify an expression and obtain its normal form.

You can create expressions in Python using familiar boolean operators or parse expressions from strings. The parsing can be extended with your own tokenizer. You can also customize how expressions behave and how they are presented.

For extensive documentation look either into the docs directory or view it online, at https://booleanpy.readthedocs.org/en/latest/.

Copyright (c) 2009-2020 Sebastian Kraemer, basti.kr@gmail.com and others SPDX-License-Identifier: BSD-2-Clause

class ssg.ext.boolean.boolean.AND(arg1, arg2, *args)

Bases: DualBase

Boolean AND operation, taking 2 or more arguments.

It can also be created by using “&” between two boolean expressions.

You can subclass to define alternative string representation. For example:: >>> class AND2(AND): … def __init__(self, *args): … super(AND2, self).__init__(*args) … self.operator = ‘AND’

sort_order = 10

class ssg.ext.boolean.boolean.BaseElement

Bases: Expression

Abstract base class for the base elements TRUE and FALSE of the boolean algebra.

pretty(indent=0, debug=False)

Return a pretty formatted representation of self.

sort_order = 0

class ssg.ext.boolean.boolean.BooleanAlgebra(TRUE_class=None, FALSE_class=None, Symbol_class=None, Function_class=None, NOT_class=None, AND_class=None, OR_class=None, allowed_in_token=('.', ':', '_'))

Bases: object

An algebra is defined by: - the types of its operations and Symbol. - the tokenizer used when parsing expressions from strings.

This class also serves as a base class for all boolean expressions, including base elements, functions and variable symbols.

cnf(expr)

Return a conjunctive normal form of the expr expression.

definition()

Return a tuple of this algebra defined elements and types as: (TRUE, FALSE, NOT, AND, OR, Symbol)

dnf(expr)

Return a disjunctive normal form of the expr expression.

normalize(expr, operation)

Return a normalized expression transformed to its normal form in the given AND or OR operation.

The new expression arguments will satisfy these conditions: - operation(*args) == expr (here mathematical equality is meant) - the operation does not occur in any of its arg. - NOT is only appearing in literals (aka. Negation normal form).

The operation must be an AND or OR operation or a subclass.

parse(expr, simplify=False)

Return a boolean expression parsed from expr either a unicode string or tokens iterable.

Optionally simplify the expression if simplify is True.

Raise ParseError on errors.

If expr is a string, the standard tokenizer is used for tokenization and the algebra configured Symbol type is used to create Symbol instances from Symbol tokens.

If expr is an iterable, it should contain 3-tuples of: (token_type, token_string, token_position). In this case, the token_type can be a Symbol instance or one of the TOKEN_* constant types. See the tokenize() method for detailed specification.

symbols(*args)

Return a tuple of symbols building a new Symbol from each argument.

tokenize(expr)

Return an iterable of 3-tuple describing each token given an expression unicode string.

This 3-tuple contains (token, token string, position): - token: either a Symbol instance or one of TOKEN_* token types. - token string: the original token unicode string. - position: some simple object describing the starting position of the

original token string in the expr string. It can be an int for a character offset, or a tuple of starting (row/line, column).

The token position is used only for error reporting and can be None or empty.

Raise ParseError on errors. The ParseError.args is a tuple of: (token_string, position, error message)

You can use this tokenizer as a base to create specialized tokenizers for your custom algebra by subclassing BooleanAlgebra. See also the tests for other examples of alternative tokenizers.

This tokenizer has these characteristics: - The expr string can span multiple lines, - Whitespace is not significant. - The returned position is the starting character offset of a token.

• A TOKEN_SYMBOL is returned for valid identifiers which is a string

without spaces. These are valid identifiers:

• Python identifiers.

• a string even if starting with digits

• digits (except for 0 and 1).

• dotted names : foo.bar consist of one token.

• names with colons: foo:bar consist of one token.

These are not identifiers: - quoted strings. - any punctuation which is not an operation

• Recognized operators are (in any upper/lower case combinations):

  • for and: ‘*’, ‘&’, ‘and’

  • for or: ‘+’, ‘|’, ‘or’

  • for not: ‘~’, ‘!’, ‘not’

• Recognized special symbols are (in any upper/lower case combinations):

  • True symbols: 1 and True

  • False symbols: 0, False and None

class ssg.ext.boolean.boolean.DualBase(arg1, arg2, *args)

Bases: Function

Base class for AND and OR function.

This class uses the duality principle to combine similar methods of AND and OR. Both operations take 2 or more arguments and can be created using “|” for OR and “&” for AND.

absorb(args)

Given an args sequence of expressions, return a new list of expression applying absorption and negative absorption.

See https://en.wikipedia.org/wiki/Absorption_law

Absorption: A & (A | B) = A, A | (A & B) = A Negative absorption: A & (~A | B) = A & B, A | (~A & B) = A | B

distributive()

Return a term where the leading AND or OR terms are switched.

This is done by applying the distributive laws:

A & (B|C) = (A&B) | (A&C) A | (B&C) = (A|B) & (A|C)

flatten()

Return a new expression where nested terms of this expression are flattened as far as possible.

E.g. A & (B & C) becomes A & B & C.

simplify(sort=True)

Return a new simplified expression in canonical form from this expression.

For simplification of AND and OR fthe ollowing rules are used recursively bottom up:

• Associativity (output does not contain same operations nested)

• Annihilation

• Idempotence

• Identity

• Complementation

• Elimination

• Absorption

• Commutativity (output is always sorted)

Other boolean objects are also in their canonical form.

subtract(expr, simplify)

Return a new expression where the expr expression has been removed from this expression if it exists.

class ssg.ext.boolean.boolean.Expression

Bases: object

Abstract base class for all boolean expressions, including functions and variable symbols.

AND = None

FALSE = None

NOT = None

OR = None

Symbol = None

TRUE = None

args = ()

get_literals()

Return a list of all the literals contained in this expression. Include recursively subexpressions symbols. This includes duplicates.

get_symbols()

Return a list of all the symbols contained in this expression. Include recursively subexpressions symbols. This includes duplicates.

iscanonical = False

isliteral = False

literalize()

Return an expression where NOTs are only occurring as literals. Applied recursively to subexpressions.

property literals

Return a set of all literals contained in this expression. Include recursively subexpressions literals.

property objects

Return a set of all associated objects with this expression symbols. Include recursively subexpressions objects.

simplify()

Return a new simplified expression in canonical form built from this expression. The simplified expression may be exactly the same as this expression.

Subclasses override this method to compute actual simplification.

sort_order = None

subs(substitutions, default=None, simplify=False)

Return an expression where the expression or all subterms equal to a key expression are substituted with the corresponding value expression using a mapping of: {expr->expr to substitute.}

Return this expression unmodified if nothing could be substituted.

Note that this can be used to tested for expression containment.

property symbols

Return a list of all the symbols contained in this expression. Include recursively subexpressions symbols. This includes duplicates.

class ssg.ext.boolean.boolean.Function(*args)

Bases: Expression

Boolean function.

A boolean function takes n (one or more) boolean expressions as arguments where n is called the order of the function and maps them to one of the base elements TRUE or FALSE. Implemented functions are AND, OR and NOT.

pretty(indent=0, debug=False)

Return a pretty formatted representation of self as an indented tree.

If debug is True, also prints debug information for each expression arg.

For example:

>>> print(BooleanAlgebra().parse(
...    u'not a and not b and not (a and ba and c) and c or c').pretty())
OR(
  AND(
    NOT(Symbol('a')),
    NOT(Symbol('b')),
    NOT(
      AND(
        Symbol('a'),
        Symbol('ba'),
        Symbol('c')
      )
    ),
    Symbol('c')
  ),
  Symbol('c')
)

class ssg.ext.boolean.boolean.NOT(arg1)

Bases: Function

Boolean NOT operation.

The NOT operation takes exactly one argument. If this argument is a Symbol the resulting expression is also called a literal.

The operator “~” can be used as abbreviation for NOT, e.g. instead of NOT(x) one can write ~x (where x is some boolean expression). Also for printing “~” is used for better readability.

You can subclass to define alternative string representation.

For example:

>>> class NOT2(NOT):

… def __init__(self, *args): … super(NOT2, self).__init__(*args) … self.operator = ‘!’

cancel()

Cancel itself and following NOTs as far as possible. Returns the simplified expression.

demorgan()

Return a expr where the NOT function is moved inward. This is achieved by canceling double NOTs and using De Morgan laws.

literalize()

Return an expression where NOTs are only occurring as literals.

pretty(indent=1, debug=False)

Return a pretty formatted representation of self. Include additional debug details if debug is True.

simplify()

Return a simplified expr in canonical form.

This means double negations are canceled out and all contained boolean objects are in their canonical form.

class ssg.ext.boolean.boolean.OR(arg1, arg2, *args)

Bases: DualBase

Boolean OR operation, taking 2 or more arguments

It can also be created by using “|” between two boolean expressions.

You can subclass to define alternative string representation. For example:

>>> class OR2(OR):

… def __init__(self, *args): … super(OR2, self).__init__(*args) … self.operator = ‘OR’

sort_order = 25

exception ssg.ext.boolean.boolean.ParseError(token_type=None, token_string='', position=-1, error_code=0)

Bases: Exception

Raised when the parser or tokenizer encounters a syntax error. Instances of this class have attributes token_type, token_string, position, error_code to access the details of the error. str() of the exception instance returns a formatted message.

class ssg.ext.boolean.boolean.Symbol(obj)

Bases: Expression

Boolean variable.

A Symbol can hold an object used to determine equality between symbols.

pretty(indent=0, debug=False)

Return a pretty formatted representation of self.

sort_order = 5