Lambda the Ultimate

I am trying to build an efficient data structure for representing boolean expressions in Erlang. I am having trouble producing a good data structure in a functional context, although there are very fast data structures for imperative languages like C. The data structure is to be used for a functional SAT solver.

A boolean expression (always in conjunctive normal form) can be described as a set of variables, such as {p,q,r...} where each variable in the set is mapped to one of three values true|false|indetermined yielding something like {{p->ind},{q->true},{r->ind},...}.

The expression is described as a set of sets of literals, where a literal is a variable with a possible negation (~). So we have something like {{~p,q},{~q,r}} which describes a formula that would usually be written (~p v q)&(~q v r). Each of the inner sets has the property that if one of its literals evaluates to true then the whole set can be removed from the outer set.

To being with we can represent the expression as a list of lists where the variable-name, negation and value are all stored in one tuple. [[{name,negation,value}]]

Now if we assign a value to a variable we then need to traverse every sublist ensuring a consistent assignment is made for every occurrence of the varia ble in the expression. However, as a reward for this effort we can easily check each sublist to see whether one of its members evaluates to true (meaning the sublist can be removed).

Alternately we could represent the expression as a list of lists where just the variable name and negation are recorded {name,negation} and have the assignment values stored as a separate mapping. This makes assignments fast and safer, but we still need to traverse every sublist to see that it does not now contain a literal evaluating to true. Is there a better way, I suspect that I am thinking about it in the wrong way. Thanks.