So I recently learned about the boolean satisfaction problem in an article that linked it to super mario brothers. Anyways, I was wondering why you can't solve the problem in the following way.
- Write your expression in DNF.
- Check to see if any of the clauses (terms with ors or just variables--no ands) have just regular variables or just the negation of variables or some combination.
- If only one clause has just regular variables or regular variables with negation, set all booleans to 1 or 0 depdending upon whether or not it's the negation case or the regular case. This will satisfy all other clauses.
- If 1 clause has all regular vars, and the other all negations then it's not solvable.
- If none of these types occur, simply set the values all to one.
Am I missing something here?