boolean package

Boolean Algebra.

This module defines a Boolean Algebra over the set {TRUE, FALSE} with boolean variables and the boolean functions AND, OR, NOT. For extensive documentation look either into the docs directory or view it online, at https://booleanpy.readthedocs.org/en/latest/.

Copyright (c) Sebastian Kraemer, basti.kr@gmail.com and others

SPDX-License-Identifier: BSD-2-Clause

Submodules

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) Sebastian Kraemer, basti.kr@gmail.com and others

SPDX-License-Identifier: BSD-2-Clause

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

Bases: DualBase

Boolean AND operation, taking two or more arguments.

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

You can subclass to define alternative string representation by overriding self.operator.

For example:

>>> class AND2(AND):
...     def __init__(self, *args):
...         super(AND2, self).__init__(*args)
...         self.operator = 'AND'
class 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.

class boolean.boolean.BooleanAlgebra(TRUE_class=None, FALSE_class=None, Symbol_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.

conjunctive_normal_form(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)

disjunctive_normal_form(expr)

Return a disjunctive normal form of the expr expression.

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 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 two 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):

    (A & B) & C = A & (B & C) = A & B & C
    (A | B) | C = A | (B | C) = A | B | C
    
  • Annihilation:

    A & 0 = 0, A | 1 = 1
    
  • Idempotence (e.g. removing duplicates):

    A & A = A, A | A = A
    
  • Identity:

    A & 1 = A, A | 0 = A
    
  • Complementation:

    A & ~A = 0, A | ~A = 1
    
  • Elimination:

    (A & B) | (A & ~B) = A, (A | B) & (A | ~B) = A
    
  • Absorption:

    A & (A | B) = A, A | (A & B) = A
    
  • Negative absorption:

    A & (~A | B) = A & B, A | (~A & B) = A | B
    
  • Commutativity (output is always sorted):

    A & B = B & A, A | B = B | A
    

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 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
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 subexpressions symbols recursively. This includes duplicates.

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.

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

Return an expression where all subterms of this expression are by the new expression using a substitutions mapping of: {expr: replacement}

Return the provided default value if this expression has no elements, e.g. is empty.

Simplify the results if simplify is True.

Return this expression unmodified if nothing could be substituted. Note that a possible usage of this function is to check for expression containment as the expression will be returned unmodified if if does not contain any of the provided substitutions.

property symbols

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

class 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 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 boolean.boolean.OR(arg1, arg2, *args)

Bases: DualBase

Boolean OR operation, taking two or more arguments

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

You can subclass to define alternative string representation by overriding self.operator.

For example:

>>> class OR2(OR):
...     def __init__(self, *args):
...         super(OR2, self).__init__(*args)
...         self.operator = 'OR'
exception 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 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.