Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

  1. Write your expression in DNF.
  2. 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.
  3. 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.
  4. If 1 clause has all regular vars, and the other all negations then it's not solvable.
  5. If none of these types occur, simply set the values all to one.

Am I missing something here?

share|cite|improve this question
...please, contain the article or at least the reference, thanks. – hhh Mar 21 '12 at 11:45
up vote 4 down vote accepted

"Writing in DNF" can, in some cases, extend the formula to solve exponentially. Wikipedia has an example.

share|cite|improve this answer
Oh I see. That's not very good then. – Chris Dugale Mar 21 '12 at 7:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.