I have a large (~1k) number of boolean formulas like:
f1(x) = p1 AND p2 f2(x) = (p1 AND p2) OR p3 f3(x) = p4 OR !p5
The argument x is a set, and the predicates (the p's) assert that a certain condition is met on the set (typically, that x contains a certain value).
For every input, I have to evaluate all the formulas.
As an example, given a chair, f1 would say: the chair is red and the chair has a head rest, f2 would say f1 OR the chair was built before 1980 and so forth.
Some predicates invalidate the formulas statistically sooner than others in my data set; one of them would be, for example, the chair was built before 1900 (not many very old chairs are found).
If I scan all the formulas, find the pieces of them that are equal, like in this example, the first part of f1 and f2, is there a way to build a common parse tree that lets me use this information to make evaluating all the formulas faster?