My first hunch was that determining if a boolean expression can be false was NP complete. After trying to prove it, I came up for a proof that it’s actually in P:
- We have any boolean expression S
- Using a well documented algorithm, we convert it to Conjunctive Normal Form
- Formula becomes (x1,1 v x1,2 v … v x1,n) Λ (x2,1 v x2,2 v … v x2,n) Λ … Λ (xn,1 v xn,2 v … v xn,n)
- Since we are trying to solve a setting of x1,1 to xn,n that results in false, that is the same thing as solving for a setting that results in true in the inverted expression
- Now we have ¬((x1,1 v x1,2 v … v x1,n) Λ (x2,1 v x2,2 v … v x2,n) Λ … Λ (xn,1 v xn,2 v … v xn,n))
- Applying DeMorgan’s ¬(x1,1 v x1,2 v … v x1,n) v ¬ (x2,1 v x2,2 v … v x2,n) v … v ¬(xn,1 v xn,2 v … v xn,n))
- Applying DeMorgan’s again (¬x1,1 Λ ¬x1,2 Λ … Λ ¬x1,n) v (¬x2,1 Λ ¬x2,2 Λ … Λ ¬x2,n) v … v (¬xn,1 Λ ¬xn,2 Λ … Λ ¬xn,n))
- Now we can determine a setting that results in true, by using the ANDed group that doesn’t contain a contradiction. If all the ANDed groups, contain contradictions, then there is no setting that results in true.
- This setting from step 8 that results in true for ¬S will result in false for S
This came up at work because we were trying to determine if a boolean expression could become false. Knowing this would allow us to make a decision on how to handle the query.
If I have made an error, let me know! If you’re confused about one of the steps, feel free to ask.