""" Boolean Algebra. Tests Copyright (c) Sebastian Kraemer, basti.kr@gmail.com and others SPDX-License-Identifier: BSD-2-Clause """ import unittest from unittest.case import expectedFailure from boolean import ( TOKEN_AND, TOKEN_FALSE, TOKEN_LPAR, TOKEN_NOT, TOKEN_OR, TOKEN_RPAR, TOKEN_SYMBOL, TOKEN_TRUE, BooleanAlgebra, ParseError, Symbol, ) from boolean.boolean import ( PARSE_INVALID_EXPRESSION, PARSE_INVALID_NESTING, PARSE_INVALID_OPERATOR_SEQUENCE, PARSE_INVALID_SYMBOL_SEQUENCE, PARSE_UNKNOWN_TOKEN, ) class BooleanAlgebraTestCase(unittest.TestCase): def test_creation(self): algebra = BooleanAlgebra() expr_str = "(a|b|c)&d&(~e|(f&g))" expr = algebra.parse(expr_str) assert str(expr) == expr_str def test_parse_with_mixed_operators_multilines_and_custom_symbol(self): class MySymbol(Symbol): pass expr_str = """(a or ~ b +_c ) and d & ( ! e_ | (my * g OR 1 or 0) ) AND that """ algebra = BooleanAlgebra(Symbol_class=MySymbol) expr = algebra.parse(expr_str) expected = algebra.AND( algebra.OR( algebra.Symbol("a"), algebra.NOT(algebra.Symbol("b")), algebra.Symbol("_c"), ), algebra.Symbol("d"), algebra.OR( algebra.NOT(algebra.Symbol("e_")), algebra.OR( algebra.AND( algebra.Symbol("my"), algebra.Symbol("g"), ), algebra.TRUE, algebra.FALSE, ), ), algebra.Symbol("that"), ) assert expr.pretty() == expected.pretty() assert expr == expected def test_parse_recognizes_trueish_and_falsish_symbol_tokens(self): expr_str = "True or False or None or 0 or 1 or TRue or FalSE or NONe" algebra = BooleanAlgebra() expr = algebra.parse(expr_str) expected = algebra.OR( algebra.TRUE, algebra.FALSE, algebra.FALSE, algebra.FALSE, algebra.TRUE, algebra.TRUE, algebra.FALSE, algebra.FALSE, ) assert expr == expected def test_parse_can_use_iterable_from_alternative_tokenizer(self): class CustomSymbol(Symbol): pass class CustomAlgebra(BooleanAlgebra): def __init__(self, Symbol_class=CustomSymbol): super(CustomAlgebra, self).__init__(Symbol_class=Symbol_class) def tokenize(self, s): "Sample tokenizer using custom operators and symbols" ops = { "WHY_NOT": TOKEN_OR, "ALSO": TOKEN_AND, "NEITHER": TOKEN_NOT, "(": TOKEN_LPAR, ")": TOKEN_RPAR, } for row, line in enumerate(s.splitlines(False)): for col, tok in enumerate(line.split()): if tok in ops: yield ops[tok], tok, (row, col) elif tok == "Custom": yield self.Symbol(tok), tok, (row, col) else: yield TOKEN_SYMBOL, tok, (row, col) expr_str = """( Custom WHY_NOT regular ) ALSO NEITHER ( not_custom ALSO standard ) """ algebra = CustomAlgebra() expr = algebra.parse(expr_str) expected = algebra.AND( algebra.OR( algebra.Symbol("Custom"), algebra.Symbol("regular"), ), algebra.NOT( algebra.AND( algebra.Symbol("not_custom"), algebra.Symbol("standard"), ), ), ) assert expr == expected def test_parse_with_advanced_tokenizer_example(self): import tokenize from io import StringIO class PlainVar(Symbol): "Plain boolean variable" class ColonDotVar(Symbol): "Colon and dot-separated string boolean variable" class AdvancedAlgebra(BooleanAlgebra): def tokenize(self, expr): """ Example custom tokenizer derived from the standard Python tokenizer with a few extra features: #-style comments are supported and a colon- and dot-separated string is recognized and stored in custom symbols. In contrast with the standard tokenizer, only these boolean operators are recognized : & | ! and or not. For more advanced tokenization you could also consider forking the `tokenize` standard library module. """ if not isinstance(expr, str): raise TypeError("expr must be string but it is %s." % type(expr)) # mapping of lowercase token strings to a token object instance for # standard operators, parens and common true or false symbols TOKENS = { "&": TOKEN_AND, "and": TOKEN_AND, "|": TOKEN_OR, "or": TOKEN_OR, "!": TOKEN_NOT, "not": TOKEN_NOT, "(": TOKEN_LPAR, ")": TOKEN_RPAR, "true": TOKEN_TRUE, "1": TOKEN_TRUE, "false": TOKEN_FALSE, "0": TOKEN_FALSE, "none": TOKEN_FALSE, } ignored_token_types = ( tokenize.NL, tokenize.NEWLINE, tokenize.COMMENT, tokenize.INDENT, tokenize.DEDENT, tokenize.ENDMARKER, ) # note: an unbalanced expression may raise a TokenError here. tokens = ( ( toktype, tok, row, col, ) for toktype, tok, ( row, col, ), _, _ in tokenize.generate_tokens(StringIO(expr).readline) if tok and tok.strip() ) COLON_DOT = ( ":", ".", ) def build_symbol(current_dotted): if current_dotted: if any(s in current_dotted for s in COLON_DOT): sym = ColonDotVar(current_dotted) else: sym = PlainVar(current_dotted) return sym # accumulator for dotted symbols that span several `tokenize` tokens dotted, srow, scol = "", None, None for toktype, tok, row, col in tokens: if toktype in ignored_token_types: # we reached a break point and should yield the current dotted symbol = build_symbol(dotted) if symbol is not None: yield symbol, dotted, (srow, scol) dotted, srow, scol = "", None, None continue std_token = TOKENS.get(tok.lower()) if std_token is not None: # we reached a break point and should yield the current dotted symbol = build_symbol(dotted) if symbol is not None: yield symbol, dotted, (srow, scol) dotted, srow, scol = "", 0, 0 yield std_token, tok, (row, col) continue if toktype == tokenize.NAME or (toktype == tokenize.OP and tok in COLON_DOT): if not dotted: srow = row scol = col dotted += tok else: raise TypeError( "Unknown token: %(tok)r at line: %(row)r, column: %(col)r" % locals() ) test_expr = """ (colon1:dot1.dot2 or colon2_name:col_on3:do_t1.do_t2.do_t3 ) and ( plain_symbol & !Custom ) """ algebra = AdvancedAlgebra() expr = algebra.parse(test_expr) expected = algebra.AND( algebra.OR( ColonDotVar("colon1:dot1.dot2"), ColonDotVar("colon2_name:col_on3:do_t1.do_t2.do_t3"), ), algebra.AND(PlainVar("plain_symbol"), algebra.NOT(PlainVar("Custom"))), ) assert expr == expected def test_allowing_additional_characters_in_tokens(self): algebra = BooleanAlgebra(allowed_in_token=(".", "_", "-", "+")) test_expr = "l-a AND b+c" expr = algebra.parse(test_expr) expected = algebra.AND(algebra.Symbol("l-a"), algebra.Symbol("b+c")) assert expr == expected def test_parse_raise_ParseError1(self): algebra = BooleanAlgebra() expr = "l-a AND none" try: algebra.parse(expr) self.fail("Exception should be raised when parsing '%s'" % expr) except ParseError as pe: assert pe.error_code == PARSE_UNKNOWN_TOKEN def test_parse_raise_ParseError2(self): algebra = BooleanAlgebra() expr = "(l-a + AND l-b" try: algebra.parse(expr) self.fail("Exception should be raised when parsing '%s'" % expr) except ParseError as pe: assert pe.error_code == PARSE_UNKNOWN_TOKEN def test_parse_raise_ParseError3(self): algebra = BooleanAlgebra() expr = "(l-a + AND l-b)" try: algebra.parse(expr) self.fail("Exception should be raised when parsing '%s'" % expr) except ParseError as pe: assert pe.error_code == PARSE_UNKNOWN_TOKEN def test_parse_raise_ParseError4(self): algebra = BooleanAlgebra() expr = "(l-a AND l-b" try: algebra.parse(expr) self.fail("Exception should be raised when parsing '%s'" % expr) except ParseError as pe: assert pe.error_code == PARSE_UNKNOWN_TOKEN def test_parse_raise_ParseError5(self): algebra = BooleanAlgebra() expr = "(l-a + AND l-b))" try: algebra.parse(expr) self.fail("Exception should be raised when parsing '%s'" % expr) except ParseError as pe: assert pe.error_code == PARSE_UNKNOWN_TOKEN def test_parse_raise_ParseError6(self): algebra = BooleanAlgebra() expr = "(l-a AND l-b))" try: algebra.parse(expr) self.fail("Exception should be raised when parsing '%s'" % expr) except ParseError as pe: assert pe.error_code == PARSE_UNKNOWN_TOKEN def test_parse_raise_ParseError7(self): algebra = BooleanAlgebra() expr = "l-a AND" try: algebra.parse(expr) self.fail("Exception should be raised when parsing '%s'" % expr) except ParseError as pe: assert pe.error_code == PARSE_UNKNOWN_TOKEN def test_parse_raise_ParseError8(self): algebra = BooleanAlgebra() expr = "OR l-a" try: algebra.parse(expr) self.fail("Exception should be raised when parsing '%s'" % expr) except ParseError as pe: assert pe.error_code == PARSE_INVALID_OPERATOR_SEQUENCE def test_parse_raise_ParseError9(self): algebra = BooleanAlgebra() expr = "+ l-a" try: algebra.parse(expr) self.fail("Exception should be raised when parsing '%s'" % expr) except ParseError as pe: assert pe.error_code == PARSE_INVALID_OPERATOR_SEQUENCE def test_parse_side_by_side_symbols_should_raise_exception_but_not(self): algebra = BooleanAlgebra() expr_str = "a or b c" try: algebra.parse(expr_str) except ParseError as pe: assert pe.error_code == PARSE_INVALID_SYMBOL_SEQUENCE def test_parse_side_by_side_symbols_should_raise_exception_but_not2(self): algebra = BooleanAlgebra() expr_str = "(a or b) c" try: algebra.parse(expr_str) except ParseError as pe: assert pe.error_code == PARSE_INVALID_EXPRESSION def test_parse_side_by_side_symbols_raise_exception(self): algebra = BooleanAlgebra() expr_str = "a b" try: algebra.parse(expr_str) except ParseError as pe: assert pe.error_code == PARSE_INVALID_SYMBOL_SEQUENCE def test_parse_side_by_side_symbols_with_parens_raise_exception(self): algebra = BooleanAlgebra() expr_str = "(a) (b)" try: algebra.parse(expr_str) except ParseError as pe: assert pe.error_code == PARSE_INVALID_NESTING class BaseElementTestCase(unittest.TestCase): def test_creation(self): from boolean.boolean import BaseElement algebra = BooleanAlgebra() assert algebra.TRUE == algebra.TRUE BaseElement() self.assertRaises(TypeError, BaseElement, 2) self.assertRaises(TypeError, BaseElement, "a") assert algebra.TRUE is algebra.TRUE assert algebra.TRUE is not algebra.FALSE assert algebra.FALSE is algebra.FALSE assert bool(algebra.TRUE) is True assert bool(algebra.FALSE) is False assert algebra.TRUE == True assert algebra.FALSE == False def test_literals(self): algebra = BooleanAlgebra() assert algebra.TRUE.literals == set() assert algebra.FALSE.literals == set() def test_literalize(self): algebra = BooleanAlgebra() assert algebra.TRUE.literalize() == algebra.TRUE assert algebra.FALSE.literalize() == algebra.FALSE def test_simplify(self): algebra = BooleanAlgebra() assert algebra.TRUE.simplify() == algebra.TRUE assert algebra.FALSE.simplify() == algebra.FALSE def test_simplify_two_algebra(self): algebra1 = BooleanAlgebra() algebra2 = BooleanAlgebra() assert algebra1.TRUE.simplify() == algebra2.TRUE assert algebra1.FALSE.simplify() == algebra2.FALSE def test_dual(self): algebra = BooleanAlgebra() assert algebra.TRUE.dual == algebra.FALSE assert algebra.FALSE.dual == algebra.TRUE def test_equality(self): algebra = BooleanAlgebra() assert algebra.TRUE == algebra.TRUE assert algebra.FALSE == algebra.FALSE assert algebra.TRUE != algebra.FALSE def test_order(self): algebra = BooleanAlgebra() assert algebra.FALSE < algebra.TRUE assert algebra.TRUE > algebra.FALSE def test_printing(self): algebra = BooleanAlgebra() assert str(algebra.TRUE) == "1" assert str(algebra.FALSE) == "0" assert repr(algebra.TRUE) == "TRUE" assert repr(algebra.FALSE) == "FALSE" class SymbolTestCase(unittest.TestCase): def test_init(self): Symbol(1) Symbol("a") Symbol(None) Symbol(sum) Symbol((1, 2, 3)) Symbol([1, 2]) def test_isliteral(self): assert Symbol(1).isliteral is True def test_literals(self): l1 = Symbol(1) l2 = Symbol(1) assert l1 in l1.literals assert l1 in l2.literals assert l2 in l1.literals assert l2 in l2.literals self.assertRaises(AttributeError, setattr, l1, "literals", 1) def test_literalize(self): s = Symbol(1) assert s.literalize() == s def test_simplify(self): s = Symbol(1) assert s.simplify() == s def test_simplify_different_instances(self): s1 = Symbol(1) s2 = Symbol(1) assert s1.simplify() == s2.simplify() def test_equal_symbols(self): algebra = BooleanAlgebra() a = algebra.Symbol("a") a2 = algebra.Symbol("a") c = algebra.Symbol("b") d = algebra.Symbol("d") e = algebra.Symbol("e") # Test __eq__. assert a == a assert a == a2 assert not a == c assert not a2 == c assert d == d assert not d == e assert not a == d # Test __ne__. assert not a != a assert not a != a2 assert a != c assert a2 != c def test_order(self): S = Symbol assert S("x") < S("y") assert S("y") > S("x") assert S(1) < S(2) assert S(2) > S(1) def test_printing(self): assert str(Symbol("a")) == "a" assert str(Symbol(1)) == "1" assert repr(Symbol("a")) == "Symbol('a')" assert repr(Symbol(1)) == "Symbol(1)" class NOTTestCase(unittest.TestCase): def test_init(self): algebra = BooleanAlgebra() self.assertRaises(TypeError, algebra.NOT) self.assertRaises(TypeError, algebra.NOT, "a", "b") algebra.NOT(algebra.Symbol("a")) assert (algebra.NOT(algebra.TRUE)).simplify() == algebra.FALSE assert (algebra.NOT(algebra.FALSE)).simplify() == algebra.TRUE def test_isliteral(self): algebra = BooleanAlgebra() s = algebra.Symbol(1) assert algebra.NOT(s).isliteral assert not algebra.parse("~(a|b)").isliteral def test_literals(self): algebra = BooleanAlgebra() a = algebra.Symbol("a") l = ~a assert l.isliteral assert l in l.literals assert len(l.literals) == 1 l = algebra.parse("~(a&a)") assert not l.isliteral assert a in l.literals assert len(l.literals) == 1 l = algebra.parse("~(a&a)", simplify=True) assert l.isliteral def test_literalize(self): parse = BooleanAlgebra().parse assert parse("~a") == parse("~a").literalize() assert parse("~a|~b") == parse("~(a&b)").literalize() assert parse("~a&~b") == parse("~(a|b)").literalize() def test_simplify(self): algebra = BooleanAlgebra() a = algebra.Symbol("a") assert ~a == ~a assert algebra.Symbol("a") == algebra.Symbol("a") assert algebra.parse("~~a") != a assert (~~a).simplify() == a assert (~~~a).simplify() == ~a assert (~~~~a).simplify() == a assert (~(a & a & a)).simplify() == (~(a & a & a)).simplify() assert algebra.parse("~~a", simplify=True) == a algebra2 = BooleanAlgebra() assert algebra2.parse("~~a", simplify=True) == a def test_cancel(self): algebra = BooleanAlgebra() a = algebra.Symbol("a") assert (~a).cancel() == ~a assert algebra.parse("~~a").cancel() == a assert algebra.parse("~~~a").cancel() == ~a assert algebra.parse("~~~~a").cancel() == a def test_demorgan(self): algebra = BooleanAlgebra() a = algebra.Symbol("a") b = algebra.Symbol("b") c = algebra.Symbol("c") assert algebra.parse("~(a&b)").demorgan() == ~a | ~b assert algebra.parse("~(a|b|c)").demorgan() == algebra.parse("~a&~b&~c") assert algebra.parse("~(~a&b)").demorgan() == a | ~b assert (~~(a & b | c)).demorgan() == a & b | c assert (~~~(a & b | c)).demorgan() == ~(a & b) & ~c assert algebra.parse("~" * 10 + "(a&b|c)").demorgan() == a & b | c assert algebra.parse("~" * 11 + "(a&b|c)").demorgan() == (~(a & b | c)).demorgan() _0 = algebra.FALSE _1 = algebra.TRUE assert (~(_0)).demorgan() == _1 assert (~(_1)).demorgan() == _0 def test_order(self): algebra = BooleanAlgebra() x = algebra.Symbol(1) y = algebra.Symbol(2) assert x < ~x assert ~x > x assert ~x < y assert y > ~x def test_printing(self): algebra = BooleanAlgebra() a = algebra.Symbol("a") assert str(~a) == "~a" assert repr(~a) == "NOT(Symbol('a'))" expr = algebra.parse("~(a&a)") assert str(expr) == "~(a&a)" assert repr(expr), "NOT(AND(Symbol('a') == Symbol('a')))" class DualBaseTestCase(unittest.TestCase): maxDiff = None def test_init(self): from boolean.boolean import DualBase a, b, c = Symbol("a"), Symbol("b"), Symbol("c") t1 = DualBase(a, b) t2 = DualBase(a, b, c) t3 = DualBase(a, a) t4 = DualBase(a, b, c) self.assertRaises(TypeError, DualBase) for term in (t1, t2, t3, t4): assert isinstance(term, DualBase) def test_isliteral(self): from boolean.boolean import DualBase a, b, c = Symbol("a"), Symbol("b"), Symbol("c") t1 = DualBase(a, b) t2 = DualBase(a, b, c) assert not t1.isliteral assert not t2.isliteral def test_literals(self): from boolean.boolean import DualBase a, b, c = Symbol("a"), Symbol("b"), Symbol("c") t1 = DualBase(a, b) t2 = DualBase(a, b, c) t3 = DualBase(a, a) t4 = DualBase(a, b, c) for term in (t1, t2, t3, t4): assert a in term.literals for term in (t1, t2, t4): assert b in term.literals for term in (t2, t4): assert c in term.literals def test_literalize(self): parse = BooleanAlgebra().parse assert parse("a|~(b|c)").literalize() == parse("a|(~b&~c)") def test_annihilator(self): algebra = BooleanAlgebra() assert algebra.parse("a&a").annihilator == algebra.FALSE assert algebra.parse("a|a").annihilator == algebra.TRUE def test_identity(self): algebra = BooleanAlgebra() assert algebra.parse("a|b").identity == algebra.FALSE assert algebra.parse("a&b").identity == algebra.TRUE def test_dual(self): algebra = BooleanAlgebra() assert algebra.AND(algebra.Symbol("a"), algebra.Symbol("b")).dual == algebra.OR assert algebra.OR(algebra.Symbol("a"), algebra.Symbol("b")).dual == algebra.AND assert algebra.parse("a|b").dual == algebra.AND assert algebra.parse("a&b").dual == algebra.OR def test_simplify(self): algebra1 = BooleanAlgebra() algebra2 = BooleanAlgebra() a = algebra1.Symbol("a") b = algebra1.Symbol("b") c = algebra1.Symbol("c") _0 = algebra1.FALSE _1 = algebra1.TRUE # Idempotence assert (a & a).simplify() == a # Idempotence + Associativity assert (a | (a | b)).simplify() == a | b # Annihilation assert (a & _0).simplify() == _0 assert (a | _1).simplify() == _1 # Identity assert (a & _1).simplify() == a assert (a | _0).simplify() == a # Complementation assert (a & ~a).simplify() == _0 assert (a | ~a).simplify() == _1 # Absorption assert (a & (a | b)).simplify() == a assert (a | (a & b)).simplify() == a assert ((b & a) | (b & a & c)).simplify() == b & a # Elimination assert ((a & ~b) | (a & b)).simplify() == a # Commutativity + Non-Commutativity sorted_expression = (b & b & a).simplify() unsorted_expression = (b & b & a).simplify(sort=False) assert unsorted_expression == sorted_expression assert sorted_expression.pretty() != unsorted_expression.pretty() sorted_expression = (b | b | a).simplify() unsorted_expression = (b | b | a).simplify(sort=False) assert unsorted_expression == sorted_expression assert sorted_expression.pretty() != unsorted_expression.pretty() expected = algebra1.parse("(a&b)|(b&c)|(a&c)") result = algebra1.parse("(~a&b&c) | (a&~b&c) | (a&b&~c) | (a&b&c)", simplify=True) assert result == expected expected = algebra1.parse("(a&b)|(b&c)|(a&c)") result = algebra2.parse("(~a&b&c) | (a&~b&c) | (a&b&~c) | (a&b&c)", simplify=True) assert result == expected expected = algebra1.parse("b&d") result = algebra1.parse("(a&b&c&d) | (b&d)", simplify=True) assert result == expected expected = algebra1.parse("b&d") result = algebra2.parse("(a&b&c&d) | (b&d)", simplify=True) assert result == expected expected = algebra1.parse("(~b&~d&a) | (~c&~d&b) | (a&c&d)", simplify=True) result = algebra1.parse( """(~a&b&~c&~d) | (a&~b&~c&~d) | (a&~b&c&~d) | (a&~b&c&d) | (a&b&~c&~d) | (a&b&c&d)""", simplify=True, ) assert result.pretty() == expected.pretty() expected = algebra1.parse("(~b&~d&a) | (~c&~d&b) | (a&c&d)", simplify=True) result = algebra2.parse( """(~a&b&~c&~d) | (a&~b&~c&~d) | (a&~b&c&~d) | (a&~b&c&d) | (a&b&~c&~d) | (a&b&c&d)""", simplify=True, ) assert result.pretty() == expected.pretty() def test_absorption_invariant_to_order(self): algebra = BooleanAlgebra() a, b = algebra.symbols("a", "b") e = (~a | ~b) & b & ~a args = [ ~a | ~b, ~a, b, ] result_original = e.absorb(args) args[1], args[2] = args[2], args[1] result_swapped = e.absorb(args) assert len(result_original) == 2 assert len(result_swapped) == 2 assert result_original[0] == result_swapped[1] assert result_original[1] == result_swapped[0] @expectedFailure def test_parse_complex_expression_should_create_same_expression_as_python(self): algebra = BooleanAlgebra() a, b, c = algebra.symbols(*"abc") test_expression_str = """(~a | ~b | ~c)""" parsed = algebra.parse(test_expression_str) test_expression = ~a | ~b | ~c # & ~d # print() # print('parsed') # print(parsed.pretty()) # print('python') # print(test_expression.pretty()) # we have a different behavior for expressions built from python expressions # vs. expression built from an object tree vs. expression built from a parse assert parsed.pretty() == test_expression.pretty() assert parsed == test_expression @expectedFailure def test_simplify_complex_expression_parsed_with_simplify(self): # FIXME: THIS SHOULD NOT FAIL algebra = BooleanAlgebra() a = algebra.Symbol("a") b = algebra.Symbol("b") c = algebra.Symbol("c") d = algebra.Symbol("d") test_expression_str = """ (~a&~b&~c&~d) | (~a&~b&~c&d) | (~a&b&~c&~d) | (~a&b&c&d) | (~a&b&~c&d) | (~a&b&c&~d) | (a&~b&~c&d) | (~a&b&c&d) | (a&~b&c&d) | (a&b&c&d) """ parsed = algebra.parse(test_expression_str, simplify=True) test_expression = ( (~a & ~b & ~c & ~d) | (~a & ~b & ~c & d) | (~a & b & ~c & ~d) | (~a & b & c & d) | (~a & b & ~c & d) | (~a & b & c & ~d) | (a & ~b & ~c & d) | (~a & b & c & d) | (a & ~b & c & d) | (a & b & c & d) ).simplify() # we have a different simplify behavior for expressions built from python expressions # vs. expression built from an object tree vs. expression built from a parse assert parsed.pretty() == test_expression.pretty() @expectedFailure def test_complex_expression_without_parens_parsed_or_built_in_python_should_be_identical(self): # FIXME: THIS SHOULD NOT FAIL algebra = BooleanAlgebra() a = algebra.Symbol("a") b = algebra.Symbol("b") c = algebra.Symbol("c") d = algebra.Symbol("d") test_expression_str = """ ~a&~b&~c&~d | ~a&~b&~c&d | ~a&b&~c&~d | ~a&b&c&d | ~a&b&~c&d | ~a&b&c&~d | a&~b&~c&d | ~a&b&c&d | a&~b&c&d | a&b&c&d """ parsed = algebra.parse(test_expression_str) test_expression = ( ~a & ~b & ~c & ~d | ~a & ~b & ~c & d | ~a & b & ~c & ~d | ~a & b & c & d | ~a & b & ~c & d | ~a & b & c & ~d | a & ~b & ~c & d | ~a & b & c & d | a & ~b & c & d | a & b & c & d ) assert parsed.pretty() == test_expression.pretty() @expectedFailure def test_simplify_complex_expression_parsed_then_simplified(self): # FIXME: THIS SHOULD NOT FAIL algebra = BooleanAlgebra() a = algebra.Symbol("a") b = algebra.Symbol("b") c = algebra.Symbol("c") d = algebra.Symbol("d") parse = algebra.parse test_expression_str = "".join( """ (~a&~b&~c&~d) | (~a&~b&~c&d) | (~a&b&~c&~d) | (~a&b&c&d) | (~a&b&~c&d) | (~a&b&c&~d) | (a&~b&~c&d) | (~a&b&c&d) | (a&~b&c&d) | (a&b&c&d) """.split() ) test_expression = ( (~a & ~b & ~c & ~d) | (~a & ~b & ~c & d) | (~a & b & ~c & ~d) | (~a & b & c & d) | (~a & b & ~c & d) | (~a & b & c & ~d) | (a & ~b & ~c & d) | (~a & b & c & d) | (a & ~b & c & d) | (a & b & c & d) ) parsed = parse(test_expression_str) assert test_expression_str == str(parsed) expected = (a & ~b & d) | (~a & b) | (~a & ~c) | (b & c & d) assert test_expression.simplify().pretty() == expected.pretty() parsed = parse(test_expression_str, simplify=True) # FIXME: THIS SHOULD NOT FAIL # we have a different simplify behavior for expressions built from python expressions # vs. expression built from an object tree vs. expression built from a parse assert parsed.simplify().pretty() == expected.simplify().pretty() expected_str = "(a&~b&d)|(~a&b)|(~a&~c)|(b&c&d)" assert str(parsed) == expected_str parsed2 = parse(test_expression_str) assert parsed2.simplify().pretty() == expected.pretty() assert str(parsed2.simplify()) == expected_str expected = algebra.OR( algebra.AND( algebra.NOT(algebra.Symbol("a")), algebra.NOT(algebra.Symbol("b")), algebra.NOT(algebra.Symbol("c")), algebra.NOT(algebra.Symbol("d")), ), algebra.AND( algebra.NOT(algebra.Symbol("a")), algebra.NOT(algebra.Symbol("b")), algebra.NOT(algebra.Symbol("c")), algebra.Symbol("d"), ), algebra.AND( algebra.NOT(algebra.Symbol("a")), algebra.Symbol("b"), algebra.NOT(algebra.Symbol("c")), algebra.NOT(algebra.Symbol("d")), ), algebra.AND( algebra.NOT(algebra.Symbol("a")), algebra.Symbol("b"), algebra.Symbol("c"), algebra.Symbol("d"), ), algebra.AND( algebra.NOT(algebra.Symbol("a")), algebra.Symbol("b"), algebra.NOT(algebra.Symbol("c")), algebra.Symbol("d"), ), algebra.AND( algebra.NOT(algebra.Symbol("a")), algebra.Symbol("b"), algebra.Symbol("c"), algebra.NOT(algebra.Symbol("d")), ), algebra.AND( algebra.Symbol("a"), algebra.NOT(algebra.Symbol("b")), algebra.NOT(algebra.Symbol("c")), algebra.Symbol("d"), ), algebra.AND( algebra.NOT(algebra.Symbol("a")), algebra.Symbol("b"), algebra.Symbol("c"), algebra.Symbol("d"), ), algebra.AND( algebra.Symbol("a"), algebra.NOT(algebra.Symbol("b")), algebra.Symbol("c"), algebra.Symbol("d"), ), algebra.AND( algebra.Symbol("a"), algebra.Symbol("b"), algebra.Symbol("c"), algebra.Symbol("d") ), ) result = parse(test_expression_str) result = result.simplify() assert result == expected def test_parse_invalid_nested_and_should_raise_a_proper_exception(self): algebra = BooleanAlgebra() expr = """a (and b)""" with self.assertRaises(ParseError) as context: algebra.parse(expr) assert context.exception.error_code == PARSE_INVALID_NESTING def test_subtract(self): parse = BooleanAlgebra().parse expr = parse("a&b&c") p1 = parse("b&d") p2 = parse("a&c") result = parse("b") assert expr.subtract(p1, simplify=True) == expr assert expr.subtract(p2, simplify=True) == result def test_flatten(self): parse = BooleanAlgebra().parse t1 = parse("a & (b&c)") t2 = parse("a&b&c") assert t1 != t2 assert t1.flatten() == t2 t1 = parse("a | ((b&c) | (a&c)) | b") t2 = parse("a | (b&c) | (a&c) | b") assert t1 != t2 assert t1.flatten() == t2 def test_distributive(self): algebra = BooleanAlgebra() a = algebra.Symbol("a") b = algebra.Symbol("b") c = algebra.Symbol("c") d = algebra.Symbol("d") e = algebra.Symbol("e") assert (a & (b | c)).distributive() == (a & b) | (a & c) t1 = algebra.AND(a, (b | c), (d | e)) t2 = algebra.OR( algebra.AND(a, b, d), algebra.AND(a, b, e), algebra.AND(a, c, d), algebra.AND(a, c, e) ) assert t1.distributive() == t2 def test_equal(self): from boolean.boolean import DualBase a, b, c = Symbol("a"), Symbol("b"), Symbol("c") t1 = DualBase(a, b) t1_2 = DualBase(b, a) t2 = DualBase(a, b, c) t2_2 = DualBase(b, c, a) # Test __eq__. assert t1 == t1 assert t1_2 == t1 assert t2_2 == t2 assert not t1 == t2 assert not t1 == 1 assert not t1 is True assert not t1 is None # Test __ne__. assert not t1 != t1 assert not t1_2 != t1 assert not t2_2 != t2 assert t1 != t2 assert t1 != 1 assert t1 is not True assert t1 is not None def test_order(self): algebra = BooleanAlgebra() x, y, z = algebra.Symbol(1), algebra.Symbol(2), algebra.Symbol(3) assert algebra.AND(x, y) < algebra.AND(x, y, z) assert not algebra.AND(x, y) > algebra.AND(x, y, z) assert algebra.AND(x, y) < algebra.AND(x, z) assert not algebra.AND(x, y) > algebra.AND(x, z) assert algebra.AND(x, y) < algebra.AND(y, z) assert not algebra.AND(x, y) > algebra.AND(y, z) assert not algebra.AND(x, y) < algebra.AND(x, y) assert not algebra.AND(x, y) > algebra.AND(x, y) def test_printing(self): parse = BooleanAlgebra().parse assert str(parse("a&a")) == "a&a" assert repr(parse("a&a")), "AND(Symbol('a') == Symbol('a'))" assert str(parse("a|a")) == "a|a" assert repr(parse("a|a")), "OR(Symbol('a') == Symbol('a'))" assert str(parse("(a|b)&c")) == "(a|b)&c" assert repr(parse("(a|b)&c")), "AND(OR(Symbol('a'), Symbol('b')) == Symbol('c'))" class OtherTestCase(unittest.TestCase): def test_class_order(self): # FIXME: this test is cryptic: what does it do? algebra = BooleanAlgebra() order = ( (algebra.TRUE, algebra.FALSE), (algebra.Symbol("y"), algebra.Symbol("x")), (algebra.parse("x&y"),), (algebra.parse("x|y"),), ) for i, tests in enumerate(order): for case1 in tests: for j in range(i + 1, len(order)): for case2 in order[j]: assert case1 < case2 assert case2 > case1 def test_parse(self): algebra = BooleanAlgebra() a, b, c = algebra.Symbol("a"), algebra.Symbol("b"), algebra.Symbol("c") assert algebra.parse("0") == algebra.FALSE assert algebra.parse("(0)") == algebra.FALSE assert algebra.parse("1") == algebra.TRUE assert algebra.parse("(1)") == algebra.TRUE assert algebra.parse("a") == a assert algebra.parse("(a)") == a assert algebra.parse("(a)") == a assert algebra.parse("~a") == algebra.parse("~(a)") assert algebra.parse("~(a)") == algebra.parse("(~a)") assert algebra.parse("~a") == ~a assert algebra.parse("(~a)") == ~a assert algebra.parse("~~a", simplify=True) == (~~a).simplify() assert algebra.parse("a&b") == a & b assert algebra.parse("~a&b") == ~a & b assert algebra.parse("a&~b") == a & ~b assert algebra.parse("a&b&c") == algebra.parse("a&b&c") assert algebra.parse("a&b&c") == algebra.AND(a, b, c) assert algebra.parse("~a&~b&~c") == algebra.parse("~a&~b&~c") assert algebra.parse("~a&~b&~c") == algebra.AND(~a, ~b, ~c) assert algebra.parse("a|b") == a | b assert algebra.parse("~a|b") == ~a | b assert algebra.parse("a|~b") == a | ~b assert algebra.parse("a|b|c") == algebra.parse("a|b|c") assert algebra.parse("a|b|c") == algebra.OR(a, b, c) assert algebra.parse("~a|~b|~c") == algebra.OR(~a, ~b, ~c) assert algebra.parse("(a|b)") == a | b assert algebra.parse("a&(a|b)", simplify=True) == (a & (a | b)).simplify() assert algebra.parse("a&(a|~b)", simplify=True) == (a & (a | ~b)).simplify() assert ( algebra.parse("(a&b)|(b&((c|a)&(b|(c&a))))", simplify=True) == ((a & b) | (b & ((c | a) & (b | (c & a))))).simplify() ) assert algebra.parse("(a&b)|(b&((c|a)&(b|(c&a))))", simplify=True) == algebra.parse( "a&b | b&(c|a)&(b|c&a)", simplify=True ) assert algebra.Symbol("1abc") == algebra.parse("1abc") assert algebra.Symbol("_abc") == algebra.parse("_abc") def test_subs(self): algebra = BooleanAlgebra() a, b, c = algebra.Symbol("a"), algebra.Symbol("b"), algebra.Symbol("c") expr = a & b | c assert expr.subs({a: b}).simplify() == b | c assert expr.subs({a: a}).simplify() == expr assert expr.subs({a: b | c}).simplify() == algebra.parse("(b|c)&b|c").simplify() assert expr.subs({a & b: a}).simplify() == a | c assert expr.subs({c: algebra.TRUE}).simplify() == algebra.TRUE def test_subs_default(self): algebra = BooleanAlgebra() a, b, c = algebra.Symbol("a"), algebra.Symbol("b"), algebra.Symbol("c") expr = a & b | c assert expr.subs({}, default=algebra.TRUE).simplify() == algebra.TRUE assert ( expr.subs({a: algebra.FALSE, c: algebra.FALSE}, default=algebra.TRUE).simplify() == algebra.FALSE ) assert algebra.TRUE.subs({}, default=algebra.FALSE).simplify() == algebra.TRUE assert algebra.FALSE.subs({}, default=algebra.TRUE).simplify() == algebra.FALSE def test_normalize(self): algebra = BooleanAlgebra() expr = algebra.parse("a&b") assert algebra.dnf(expr) == expr assert algebra.cnf(expr) == expr expr = algebra.parse("a|b") assert algebra.dnf(expr) == expr assert algebra.cnf(expr) == expr expr = algebra.parse("(a&b)|(c&b)") result_dnf = algebra.parse("(a&b)|(b&c)") result_cnf = algebra.parse("b&(a|c)") assert algebra.dnf(expr) == result_dnf assert algebra.cnf(expr) == result_cnf expr = algebra.parse("(a|b)&(c|b)") result_dnf = algebra.parse("b|(a&c)") result_cnf = algebra.parse("(a|b)&(b|c)") assert algebra.dnf(expr) == result_dnf assert algebra.cnf(expr) == result_cnf expr = algebra.parse("((s|a)&(s|b)&(s|c)&(s|d)&(e|c|d))|(a&e&d)") result = algebra.normalize(expr, expr.AND) expected = algebra.parse("(a|s)&(b|e|s)&(c|d|e)&(c|e|s)&(d|s)") assert expected == result def test_get_literals_return_all_literals_in_original_order(self): alg = BooleanAlgebra() exp = alg.parse("a and b or a and c") assert [ alg.Symbol("a"), alg.Symbol("b"), alg.Symbol("a"), alg.Symbol("c"), ] == exp.get_literals() def test_get_symbols_return_all_symbols_in_original_order(self): alg = BooleanAlgebra() exp = alg.parse("a and b or True and a and c") assert [ alg.Symbol("a"), alg.Symbol("b"), alg.Symbol("a"), alg.Symbol("c"), ] == exp.get_symbols() def test_literals_return_set_of_unique_literals(self): alg = BooleanAlgebra() exp = alg.parse("a and b or a and c") assert set([alg.Symbol("a"), alg.Symbol("b"), alg.Symbol("c")]) == exp.literals def test_literals_and_negation(self): alg = BooleanAlgebra() exp = alg.parse("a and not b and not not c") assert set([alg.Symbol("a"), alg.parse("not b"), alg.parse("not c")]) == exp.literals def test_symbols_and_negation(self): alg = BooleanAlgebra() exp = alg.parse("a and not b and not not c") assert set([alg.Symbol("a"), alg.Symbol("b"), alg.Symbol("c")]) == exp.symbols def test_objects_return_set_of_unique_Symbol_objs(self): alg = BooleanAlgebra() exp = alg.parse("a and b or a and c") assert set(["a", "b", "c"]) == exp.objects def test_normalize_blowup(self): from boolean import AND, NOT, OR from collections import defaultdict # Subclasses to count calls to simplify class CountingNot(NOT): def simplify(self): counts["CountingNot"] += 1 return super().simplify() class CountingAnd(AND): def simplify(self, sort=True): counts["CountingAnd"] += 1 return super().simplify(sort=sort) class CountingOr(OR): def simplify(self, sort=True): counts["CountingOr"] += 1 return super().simplify(sort=sort) counts = defaultdict(int) # Real-world example of a complex expression with simple CNF/DNF form. # Note this is a more reduced, milder version of the problem, for rapid # testing. formula = """ a & ( (b & c & d & e & f & g) | (c & f & g & h & i & j) | (c & d & f & g & i & l & o & u) | (c & e & f & g & i & p & y & ~v) | (c & f & g & i & j & z & ~(c & f & g & i & j & k)) | (c & f & g & t & ~(b & c & d & e & f & g)) | (c & f & g & ~t & ~(b & c & d & e & f & g)) ) """ algebra = BooleanAlgebra( NOT_class=CountingNot, AND_class=CountingAnd, OR_class=CountingOr, ) expr = algebra.parse(formula) cnf = algebra.cnf(expr) assert str(cnf) == "a&c&f&g" # We should get exactly this count of calls. # before we had a combinatorial explosion assert counts == {"CountingAnd": 44, "CountingNot": 193, "CountingOr": 2490} class BooleanBoolTestCase(unittest.TestCase): def test_bool(self): algebra = BooleanAlgebra() a, b, c = algebra.Symbol("a"), algebra.Symbol("b"), algebra.Symbol("c") expr = a & b | c self.assertRaises(TypeError, bool, expr.subs({a: algebra.TRUE})) self.assertRaises(TypeError, bool, expr.subs({b: algebra.TRUE})) self.assertRaises(TypeError, bool, expr.subs({c: algebra.TRUE})) self.assertRaises(TypeError, bool, expr.subs({a: algebra.TRUE, b: algebra.TRUE})) result = expr.subs({c: algebra.TRUE}, simplify=True) result = result.simplify() assert result == algebra.TRUE result = expr.subs({a: algebra.TRUE, b: algebra.TRUE}, simplify=True) result = result.simplify() assert result == algebra.TRUE class CustomSymbolTestCase(unittest.TestCase): def test_custom_symbol(self): class CustomSymbol(Symbol): def __init__(self, name, value="value"): self.var = value super(CustomSymbol, self).__init__(name) try: CustomSymbol("a", value="This is A") except TypeError as e: self.fail(e) class CallabilityTestCase(unittest.TestCase): def test_and(self): algebra = BooleanAlgebra() exp = algebra.parse("a&b&c") for a in [True, False]: for b in [True, False]: for c in [True, False]: assert exp(a=a, b=b, c=c) == (a and b and c) def test_or(self): algebra = BooleanAlgebra() exp = algebra.parse("a|b|c") for a in [True, False]: for b in [True, False]: for c in [True, False]: assert exp(a=a, b=b, c=c) == (a or b or c) def test_not(self): algebra = BooleanAlgebra() exp = algebra.parse("!a") for a in [True, False]: assert exp(a=a) == (not a) def test_symbol(self): algebra = BooleanAlgebra() exp = algebra.parse("a") for a in [True, False]: assert exp(a=a) == a def test_composite(self): algebra = BooleanAlgebra() exp = algebra.parse("!(a|b&(a|!c))") for a in [True, False]: for b in [True, False]: for c in [True, False]: assert exp(a=a, b=b, c=c) == (not (a or b and (a or not c))) def test_negate_A_or_B(self): algebra = BooleanAlgebra() exp = algebra.parse("!(a|b)") for a in [True, False]: for b in [True, False]: assert exp(a=a, b=b) == (not (a or b))