I'm sorry to tell you that your problem is NP-complete, and therefore there is no efficient solution. Your problem is NP because any proposed solution can be verified in polynomial time. It is NP-complete because the known NP-complete problem 3SAT can be reduced to your problem. See http://en.wikipedia.org/wiki/Boolean_satisfiability_problem for a description of 3SAT. To see how to represent it with your format, first include a bunch of equations of the form Xi + Yi = 1 so that Yi represents (NOT Xi). Then string together a series of equations where the sum of 3 terms is >= 1, meaning at least one of them is true.

That said, there is lots of research on how to tackle this kind of problem. A term I'd suggest googling for is "Constraint Satisfaction".