Common parse tree for several formulas 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?
This is the circuit minimization / logic optimization problem.   You have a circuit with some number of inputs (one per predicate p1, .., pn; or based on the representation of x)  and ~ 1k outputs (one per formula f1, .., fm).  Now the goal is to construct another equivalent circuit that computes the same output, as efficiently as possible.  That's a circuit minimization problem.  The problem is hard in general, but there are some heuristics and tools that may be effective in many situations (e.g., Espresso, Quine-McClusky, BDDs, and more).  I suggest reading about that subject and trying out one of those tools or techniques.