I think mathjax works nowadays in pretty much all browsers. It looks cleaner and uses less bandwith. If this is acceptable please merge #57.

On the 3.6 release of boolean.py, there is no source distribution, only a wheel:

https://pypi.org/project/boolean.py/#files

@bastikr could you enable Travis so we get continuous builds?
https://travis-ci.org/bastikr/boolean.py
I committed a basic travis config with fa12f8e

This is not a bug but a suggestion. I implemented an alternative expression tokenizer using an Aho-Corasick automaton. This allows to lex against a list of known symbols and resolve expressions that would be otherwise ambiguous and may help other boolean.py users.
You can find it there: https://github.com/nexB/license-expression/tree/56709dc901c97a3722247d4e4158e95594fd69a1/src/license_expression

Three tests are failing and maked with @expectedfailure for now. See here, here and there

The essence of these bugs is that parsing the same fairly complex expression with or without simplify=True and building the same expression in Python then invoking .simplify() creates different expressions. Somehow the results of parsing and building the expression in code is not the same.
I cannot pinpoint exactly where this comes from. The bug exists in the no-new-stamement branch but also in master. And was there in master before we started the recent improvements.
I added the .pretty() method with a debug flag to try to digg more into the problem but I did find anything fishy yet.
Ideally we would need a test on a smaller expression that exhibit the same buggy behaviour.

From @Kronuz in #7 :

First, bool(TRUE) could also be (and currently) is True, but bool(FALSE) should, I think, also be False, but it isn't. I added bool() (and nozero() for Python 2) to TRUE and FALSE classes.

In https://github.com/bastikr/boolean.py/blob/master/boolean/boolean.py#L860:

if all(arg in self.args for arg in item.args):
    args = tuple(arg for arg in self.args if arg not in expo)

It uses an undefined variable item. What is this supposed to do?

I just removed the all() test, leaving only this:

args = tuple(arg for arg in self.args if arg not in expo)

But I'm not sure what that check was intended for (originally).

boolean.TRUE.subs({}) fails... also boolean.parse('unknown').subs({}) I fixed that and also added support to specify a default symbol when calling subs() (which is a fallback for symbols not in the map); for example: boolean.parse('unknown').subs({}, default=boolean.FALSE) == boolean.FALSE

5e15815

Hello!
Here is a test case to trigger a bug in normalize function. normalize function produces the result which says that s=true is enough to satisfy the whole expression, which is wrong.

import unittest
from helpers import boolean
from helpers.boolean import  AND, normalize


class Test(unittest.TestCase):
    def test(self):
        expr_str = '((s+dd)*(s+ts)*(s+fs)*(s+se)*(ff+fs+se))+(dd*ff*se)'
        expr = boolean.parse(expr_str)
        and_literals = normalize(AND, expr)

        print('\n'.join([str(x) for x in and_literals]))

The output is:
dd+s
ff+fs+s
ff+s+ts
s+se
s+se+ts

I am utilizing this code in a project of mine and am finding I have some really long boolean logic when I finish. I am relying heavily on the simplification component in order to make my whole project work but I realize that it doesn't seem to work as well as Wolfram Alpha. Here is a simple test.

logic = "( a & ~b & ~c )|( a & ( b | c ))"

According to Wolfram Alpha this evaluates to just 'a' but boolean.BooleanAlgebra(logic, simplify=True) doesn't change the results at all. This is a big issue for me. Has anyone else experienced the simplification not working effectively sometimes?

To further show this you can simplify this expression.
logic = "(~b & ~c) | (b | c)"
The result should be 1 or TRUE but the boolean parser gives a clearly wrong answer of "b|c|~c". But how can you ever have "c or not c"? That is clearly wrong.

b | c | (~b & ~c) | (b | c)
--|---|--------------------
T | T | T
T | F | T
F | T | T
F | F | T

from @Kronuz in #7:

Finally, I'm using the Boolean expressions to pass Boolean rules and parsing them (and simplifying them) and then, how do I tell the expression to use certain symbols as True or False to give me end result of the evaluated symbols?

I currently added some changes to eval() to be able to pass a mapping of symbols to TRUE/FALSE during the evaluation. eval() received **evalkwargs, which I guessed it was for the purpose of passing that mapping of symbols, as it only seemed intuitive it would, but it didn't do anything with them. Also, once expressions are flagged as canonical, eval() a second time doesn't do anything. So I changed eval() to save the dictionary object in **evalkwargs in a variable so next time I call eval() it returns immediately only if the saved evalkwargs is equal to the passed one (thus it's already been processed under that evalkwargs context as canonical) and I also use the passed evalkwargs in the Symbol's eval() as the symbol mapping to look for the value of symbol, so it returns either TRUE or FALSE, if it's there, or the symbol itself (self), if it's not.

So I guess it could be interesting to define if a Symbol is True or False rather than always treating a Symbol as True.

@Kronuz Could you elaborate on the need for this vs. wrapping such a Symbol in a False expression?

Is there any possibility parse only AND, OR and NOT operators? For example I cannot parse a query C OR C++ because of the ++ in the string.

In the recent/latest doc, sphinx is not generating things correctly:
``
System Message: WARNING/2 ((x|y) & (x|(\sim y)) = x)
latex exited with error [stdout] This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013/Debian) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2011/06/27> Babel <3.9h> and hyphenation patterns for 78 languages loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty (/usr/share/texlive/texmf-dist/tex/latex/ucs/utf8x.def)) (/usr/share/texlive/texmf-dist/tex/latex/ucs/ucs.sty (/usr/share/texlive/texmf-dist/tex/latex/ucs/data/uni-global.def)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsmath.sty For additional information on amsmath, use the `?’ option. (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amstext.sty (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsgen.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsbsy.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsopn.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amscls/amsthm.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amssymb.sty (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amsfonts.sty)) (/usr/share/texlive/texmf-dist/tex/latex/tools/bm.sty) (./math.aux) (/usr/share/texlive/texmf-dist/tex/latex/ucs/ucsencs.def) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsa.fd) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsb.fd) ! Misplaced alignment tab character &. l.12 $(x|y) &amp; (x|(\sim y)) = x$ [1] (./math.aux) ) (see the transcript file for additional information) Output written on math.dvi (1 page, 324 bytes). Transcript written on math.log.

It does not make to me to have simplify=True by default in parse and other places.
This should be an explicit operation instead

In the tokenize() method of BooleanAlgebra, would it be possible to change the tokens without inheriting the whole method and changing just the tokens, e.g.:

def tokenize(self, expr, TOKENS=None):
    ...
    TOKENS = TOKENS or {
         # current TOKENS
    }
    ...

Or perhaps define the current tokens outside the method and make them the default TOKENS instead of None above.

This makes it less likely that in future versions the inheriting class becomes outdated.

Cheers, Lars

The name of this package (boolean.py) is unconventional. This leads to problems when using common Python dev tools. E.g. running liccheck with $ liccheck -s license_check.ini -r requirements.txt leads to pkg_resources.DistributionNotFound: The 'boolean-py==3.7' distribution was not found and is required by the application

Even if these cases are already in normal form, applying cnf/dnf shouldn't make them wrong. For boolean variables x and y, x & y does not have the same truth table as x | y.

>>> alg = BooleanAlgebra()

>>> alg.cnf(alg.OR(Symbol("x"), Symbol("y")))
AND(Symbol('x'), Symbol('y'))

>>> alg.dnf(alg.AND(Symbol("x"), Symbol("y")))
OR(Symbol('x'), Symbol('y'))

>>> alg.cnf(alg.parse("a|b"))
AND(Symbol('a'), Symbol('b'))

>>> alg.dnf(alg.parse("a&b"))
OR(Symbol('a'), Symbol('b'))

When using UUIDs in tokens, the tokens are rejected because of the - character in them. I can subclass BooleanAlgebra and override tokenize but it is a lot of duplication for allowing an additional character in the token. It would be nice if one could specify the allowable character set.

The operators +, * and ~ are somewhat uncommon when dealing with booleans in Python.
In #7 @Kronuz mentioned this:

Secondly, I added &, | and ! as alternatives for parsing Boolean expressions and __and__() and __or__() to Expression (I print the strings something as "a&(b|c)" instead of "a*(b+c)" as our developers are more familiar with the "&" and "|" notation, but supporting both doesn't hurt.

I am interested in supporting these more common operators as well as plain text and, or and not when parsing and providing a string representation of an expression.
Ideally the operators in use should be configurable with an argument to the parser and stored in the objects to reuse when returning later a string representation. And possibly also injected somehow when creating expression from scratch.

The exception messages returned from parse are often not really useful not meaningful. We should improve this. Also several TypeError exceptions are returned as is while parsing

For example:

>>> parse("~A*~(~A+~B)")
AND(NOT(Symbol('A')), NOT(OR(NOT(Symbol('A')), NOT(Symbol('B')))))

By adding:

term  = term.literalize()

after

term = self.__class__(*args, eval=False)

to the method DualBase.eval, this fixes the problem:

>>> parse("~A*~(~A+~B)")
FALSE

I have not reviewed the code for DualBase.eval to check that this will not cause any problems.

In issue #32, @bastikr said:

I agree let's remove the __new__ functions. The only one we might consider keeping is the one for Function since it checks that the number of arguments is correct.

So, this issue is for eventually removing all __new__() that can be removed.

The search for boolean.py yields no result

Index of Packages Matching 'boolean.py'
There were no matches.

This is really weird

Hi, first off, Thanks for this great module. It's proving to be quite useful for my research use-cases and probably to others with similar ones.

I'm trying to parse some boolean expressions involving the XOR, XNOR, NAND operators but the parser fails to parse the said expressions since they're not recognised as known operators.

In the current scenario, an expression involving such operators would need to be simplified by hand (since XOR, XNOR, NAND translate into forms of AND, OR, NOT eventually) before the boolean.py parser can handle them. Is there any simpler way to achieve this?

Thanks!

The top level license is a simplified, 2-Clause BSD license.
The code has these "Released under revised BSD license." ... which typically means this is a 3-Clause-BSD

We should update this terse statement to be clearer.

I would like to be able to represent an expression as a string with the boolean operators I want and not the default + and *.

I've ran into a problem while using simplify with a few expressions, even though they are valid and have not apparent reason to cause these errors.

One thing I noticed is that if I remove the 'not' symbol from them, they'll work "correctly"

Cases where "TypeError: '_FALSE' object is not callable" is raised:

(0)&~((1)|(0))
(1)&(~((0)|(1)))
(0)&(~((0)|(0)))&(1)

Cases where "TypeError: '_TRUE' object is not callable" is raised:

(~((0)&(0)))&(1)&(0)&(1)
(0)|(0)|(~((1)&(0)&(0)&(0)&(0)))
(~((1)&(0)&(1)&(1)))|(0)|(~((0)|(0)|(1)))

I like this tokenizer better than using tokenize.

I thought standard tokenize module would be optimized in C, but it's fully written in Python and since it has so much more than we actually need, I'm sure it's not as efficient. Furthermore, I'd go as far as yielding the token, tokstr and the position, it being either an offset or a (row, col) pair, which for most cases would be enough:

def tokenizer(expr, symbol_class=boolean.Symbol):
    if not isinstance(expr, basestring):
        raise TypeError("expr must be string but it is %s." % type(expr))

    TOKENS = {
        '*': boolean.TOKEN_AND,
        '&': boolean.TOKEN_AND,
        'and': boolean.TOKEN_AND,
        '|': boolean.TOKEN_OR,
        '+': boolean.TOKEN_OR,
        'or': boolean.TOKEN_OR,
        '~': boolean.TOKEN_NOT,
        '!': boolean.TOKEN_NOT,
        'not': boolean.TOKEN_NOT,
        '(': boolean.TOKEN_LPAR,
        '[': boolean.TOKEN_LPAR,
        ']': boolean.TOKEN_RPAR,
        ')': boolean.TOKEN_RPAR,
        'true': boolean.TRUE,
        '1': boolean.TRUE,
        'false': boolean.FALSE,
        '0': boolean.FALSE,
        'none': boolean.FALSE,
    }

    length = len(expr)
    offset = 0
    while offset < length:
        tok = expr[offset]

        sym = tok.isalpha() or tok == '_'
        if sym:
            offset += 1
            while offset < length:
                char = expr[offset]
                if char.isalnum() or char in ('.', ':', '_'):
                    offset += 1
                    tok += char
                else:
                    break
            offset -= 1

        try:
            yield TOKENS[tok.lower()], tok, offset
        except KeyError:
            if sym:
                yield symbol_class(tok), tok, offset
            elif tok not in (' ', '\t', '\r', '\n'):
                raise TypeError("Unknown token %s at position %s." % (tok, offset))

        offset += 1

This prevents the use of tokenize and StringIO, and to me is easier to understand, since it's so simple. Users can always use their own tokenizers anyway.

Here is the traceback that reveals that for Symbol(object) constructor to be usable the constructor object should implement lt (and probably others comparison operators)
(I raise RuntimeError when lt is called in my object):

Traceback (most recent call last):
  expr = (expr * s) if val else (expr * ~s)
File "boolean.py", line 245, in __mul__
  return self.algebra.operations.AND(self, other)
File "boolean.py", line 462, in __new__
  return cls(*args, eval=False).eval()
File "boolean.py", line 797, in eval
  args.sort()
File "boolean.py", line 240, in __gt__
  return not self.__lt__(other)
File "boolean.py", line 596, in __lt__
  return self.args[0].__lt__(other)
File "boolean.py", line 426, in __lt__
  return self.obj.__lt__(other.obj) # 2 named symbols.
File "parser_expr.py", line 45, in __lt__
  raise RuntimeError()

The problem is that if you do not implement __lt__, etc. then the default __lt__ is used -- and this can result in the wrong result when normalize boolean expressions to dnf.
Let me know if you need a complete example revealing this.
Regards,)

I was pointed here by StackOverflow (http://stackoverflow.com/questions/7990554/where-might-i-find-a-method-to-convert-an-arbitrary-boolean-expression-into-conj)

I am trying to use your boolean.py module but I cannot import it. Under both Python 2.7 and 3.2 I get the following error:

>>> import boolean
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "boolean.py", line 45
    def __new__(cls, arg, *, eval=True):
                           ^
SyntaxError: invalid syntax

I presume this syntax is to swallow up any remaining arguments, but it not valid syntax in recent versions of Python. Is it OK to give this argument a name, such as *varargs ?

Will be "assigning to myself" and submitting a PR shortly.

This should have the same semantics as the stdlib string.replace():

string.replace(s, old, new[, maxreplace])

    Return a copy of string s with all occurrences of substring old replaced by new. 
    If the optional argument maxreplace is given, the first maxreplace occurrences are replaced.

This is more or less what subs() does but subs is too complex for my case and I do not need recursivity.

I need a simpler lower level way to do only one replacement at a time and not many. There are a few wrinkles in the subs code too where iterating on items() could be replaced by a cleaner and more efficient get() that could be cleaned up too.

@bastikr It dawned on me that there is a little used object called BooleanAlgebra?

I am not sure I grok entirely its purpose, but it seems to have been designed as a central configuration and entry point.
In particular it holds the base elements for TRUE and FALSE and the default Symbol class.
I wonder if we should use this class more and instead of passing a symbol_class to parse, passing it an algebra.
Also we could have it hold the strings to use for __str__ and __repr__ for operators, parens, etc. I very much want and need to have custom serializations that would not use the default *+~.
Also the parse function could become also a method of this?

So a custom algebra is something where you could redefine what is the parsing or tokenization logic,what are the base elements, the Symbol class to use and how expressions are serialized.

I am just throwing out some ideas, but there is a few quirks in the current design that tickle me.

@Kronuz you take is appreciated too

I would like to collect this so we can either put this in a wiki page or the README.
I do use it in this project https://github.com/nexB/license-expression/ eventually reused in many other places.

@Kronuz @bastikr what do you think? How and where do you use it?

On Arch Linux and its derivates, users can also install boolean.py using this AUR. It would be nice if this was reflected in the README and other docu :)

I had to package it there because its a dependency for reuse.

If you have any feedback about the AUR package, please let me know!

Running make doctest in the doc dir fails on Python 3 because the doc uses print statements instead of function calls.

@bastikr could you enable the wiki on this repo? I would like to document the release procedure there. Alternatively I can just push a README.hacking with development-related doc.

Not sure if this a bug or not, but:

>>> alg = boolean.BooleanAlgebra()
>>> alg.parse("A").get_symbols()
[Symbol('A')]
>>> alg.parse("~A").get_symbols()
[]
>>> alg.parse("~A|B").get_symbols()
[Symbol('B')]
>>> alg.parse("~(A|B)").get_symbols()
[Symbol('A'), Symbol('B')]

So the literal NOT(A) is not retrieved by get_symbols

Maybe i missed something completely, but i could not figure out how to actually use the boolean expressions to boolean values to calculate the result, so i implemented something myself:

from operator import and_ as and_operator, or_ as or_operator
from boolean import BooleanAlgebra, AND, OR, NOT, Symbol

class Symbol_(Symbol):

    def __call__(self, **kwargs):
        return kwargs[self.obj]

class NOT_(NOT):

    def __call__(self, **kwargs):
        return not self.args[0](**kwargs)

class OR_(OR):

    def __call__(self, **kwargs):
        """ reduce is used as in e.g. OR(a, b, c, d) == OR(A, OR(b, OR(c, d)))"""
        return reduce(or_operator, (a(**kwargs) for a in self.args))

class AND_(AND):

    def __call__(self, **kwargs):
        """ reduce is used as in e.g. AND(a, b, c, d) == AND(A, AND(b, AND(c, d)))"""
        return reduce(and_operator, (a(**kwargs) for a in self.args))

class CallableBooleanAlgebra(BooleanAlgebra):

    def __init__(self, *args, **kwargs):
        super(CallableBooleanAlgebra, self).__init__(Symbol_class=Symbol_,
                                                     OR_class=OR_,
                                                     AND_class=AND_,
                                                     NOT_class=NOT_,
                                                     *args, **kwargs)

if __name__ == "__main__":

    algebra = CallableBooleanAlgebra()
    exp = algebra.parse("!(x|y&(x|!z))")
   
    #call expression with keyword arguments matching the symbols:
    assert  exp(x=False, y=False, z=True) == True

I have written basic tests and checked whether the original tests pass (with some basic modifications) by replacing BooleanAlgebra with CallableBooleanAlgebra (import CallableBooleanAlgebra as BooleanAlgebra).

Compliments for the tight implementation of boolean that made this relatively easy.

So my questions are:

• Is this functionality already there but did or completely miss it (making this a fun but somewhat useless exercise)?
• If not, is this something to add to the baseclasses (AND, OR, NOT, Symbol) themselves (but i can imagine this complicating subclassing a bit),
• Is there any interest in adding this to the repo in some other way?

Also comments, improvements, etc. are very welcome!

Cheers, Lars

Using + and * may be correct mathematically but is utterly confusing when programming.
As a programmer I want simple and intuitive. We should make & and | the default AND and OR operators respectively.

This is a small issue, i wouldn't say anything if it didn't happen to me ;-)

    def __lt__(self, other):
        comparator = Expression.__lt__(self, other)
        if comparator is not NotImplemented:
            return comparator
        if isinstance(other, Symbol):
            return self.obj < other.obj   # <= this might raise exception
        return NotImplemented

could be more robust (probably, can't oversee all the consequences), with:

    def __lt__(self, other):
        comparator = Expression.__lt__(self, other)
        if comparator is not NotImplemented:
            return comparator
        if isinstance(other, Symbol):
            try:
                return self.obj < other.obj
            except Exception:
                return NotImplemented
        return NotImplemented

This is called in simplify. For now i will override Symbol.lt in my code.

Cheers, Lars

@Kronuz @bastikr I am not sure that I have a need to build boolean expression using overloaded operators in Python and this introduces subtle bias and behaviors in many places.

Do you have a use for them? (as opposed to build an expression from a parsed string or building an expression from nested Python objects)

This would mean dropping the dunder methods from here:

__and__ , __mul__ , __invert__ , __or__ and __add__ and possibly __nonzero__ and __bool__

Parsing search strings such as 'a &&& b' or even 'a & & b' generates a result of
AND( Symbol('a'), Symbol('yes') )
When realistically, neither expression makes that much sense syntactically. Looking at the code, there only seems to be checking for repeated Symbol objects. Is this a design decision that was made during development? I see this leading to potential instances where a user would send in an incorrect search string that evaluates to an unintended result.

@bastikr I see this old commit d6f169e
I wonder if you had plans to re-instate some of it? or?
In particular there is code for minimization.... yummy

Is there a way to make this work with numbers as tokens? My use case for this is querying "ids", like 1234, 56, etc.

a or b c is not a valid expression but does not raise an Exception on parsing.
Instead we get this: OR(Symbol('a'), Symbol('b'), Symbol('c')) which is incorrect.

I am interested to feed a pre-tokenized sequence to the parser instead of a string. Items would be either an operator (and, or not) or a parens. Any other item should be considered a symbol.

This could also support @Kronuz improvement mentioned here #7 :

Thirdly, I also extended the parser so it takes symbols that contain underscores and dots. What characters make a symbol could/should be made configurable by the user instead, perhaps by using a regexp of allowed symbol names.

@bastikr now that you have a proper setup, you could push to Pypi... Or I can handle it. Your call
@rossant recently released pipo a tool supposed this real easy: https://github.com/rossant/pipo/ and https://pypi.python.org/pypi/pipo/