How about support for a NOT operator in Parse::BooleanLogic?
I guess most of the requirement can be taken care of with user interpretation of operands, e.g. the solver callback interpreting "NOT" or "!" prefixes to operands. However, the lack of NOT can put a burden on a human constructing the expression.
E.g.: someone who wants to do this: