Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Parsing and computing boolean set definitions

Say I have a set S defined as a string, e.g. as follows:

S = '(A or B) and not(A and C)'

where A, B and C are finite sets, e.g.:

A = {0, 1}
B = {0, 2}
C = {1, 3}

If we analyze S step by step, we have:

(A or B)   = {0, 1, 2}
(A & C)    = {1}
not(A & C) = {0, 2, 3}

which gives us the final result:

S = {0,2}

How can I compute the elements of S given its definition as a general boolean formula?

I don't quite know how to start addressing this problem. On one hand I wonder if I need to use a full lexical parser. Also, after some reading I also found two concepts that seem that highly related, but don't know how they would apply:

  • Canonical Normal Forms
  • De Morgan's laws
like image 807
Amelio Vazquez-Reina Avatar asked Mar 11 '14 02:03

Amelio Vazquez-Reina


People also ask

What is set Boolean?

In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include false and true. In logic, mathematics and theoretical computer science, a Boolean domain is usually written as {0, 1}, or.

What are the three different types of boolean operators?

Boolean operators form the basis of mathematical sets and database logic. They connect your search words together to either narrow or broaden your set of results. The three basic boolean operators are: AND, OR, and NOT.

What is Boolean data in computer?

Boolean is a data type where the data only has two possible variables: true or false. In terms of computer science, Boolean is an identification classifier for working out logical truth values and algebraic variables.

What are the three different types of boolean operators in Python?

There are three logical operators that are used to compare values. They evaluate expressions down to Boolean values, returning either True or False . These operators are and , or , and not and are defined in the table below.


2 Answers

There is no need to write your own parser if you're willing to transform S in to a string suitable for use with eval(). Change S from '(A or B) and not(A and C)' into an equivalent T that uses Python's in-operator '(x in A or x in B) and not(x in A and x in C)'.

Compute the result by looping over the universe of elements and testing whether they match the above expression. Here's a worked-out example at the interactive prompt:

>>> T = '(x in A or x in B) and not(x in A and x in C)'
>>> sets = {'A': {0, 1}, 'B': {0, 2}, 'C': {1, 3}}
>>> universe = {x for s in sets.values() for x in s}
>>> {x for x in universe if eval(T, sets, {'x': x})}
set([0, 2])

To make the transformation automatically, create a namespace for the set variables where variable lookups do a set membership test. Putting it all together gives you a simple and clean set-expression evaluator:

class SetVariables(dict):
    'Transform a variable lookup into a membership test'
    def __getitem__(self, var):
        s = dict.__getitem__(self, var)
        return self.x in s

def set_eval(expr, **sets):
    'Evaluation a set expression for the given sets'
    universe = {x for s in sets.values() for x in s}
    expr = compile(expr, '', 'eval')
    variables = SetVariables(sets)
    results = set()
    for x in universe:
        variables.x = x
        if eval(expr, {}, variables):
            results.add(x)
    return results

if __name__ == '__main__':
    print set_eval(expr = '(A or B) and not(A and C)',
                   A = {0, 1},
                   B = {0, 2},
                   C = {1, 3}
                  )

Hope this solves your problem and saves you from having to write your own parser :-)

like image 58
Raymond Hettinger Avatar answered Oct 21 '22 09:10

Raymond Hettinger


What I would do is to use the shunting yard algorithm to convert this to Reverse Polish Notation and then use this simple algorithm to evaluate the espression.

No need for a proper parser then, you only need to recognize each word, parens and special character composing the definition with no need of "understanding the structure of the sentence".

like image 34
radomaj Avatar answered Oct 21 '22 09:10

radomaj