Determining If A Boolean Expression Can Be False

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:

1. We have any boolean expression S
2. Using a well documented algorithm, we convert it to Conjunctive Normal Form
3. Formula becomes (x_1,1 v x_1,2 v … v x_1,n) Λ (x_2,1 v x_2,2 v … v x_2,n) Λ … Λ (x_n,1 v x_n,2 v … v x_n,n)
4. Since we are trying to solve a setting of x_1,1 to x_n,n that results in false, that is the same thing as solving for a setting that results in true in the inverted expression
5. Now we have ¬((x_1,1 v x_1,2 v … v x_1,n) Λ (x_2,1 v x_2,2 v … v x_2,n) Λ … Λ (x_n,1 v x_n,2 v … v x_n,n))
6. Applying DeMorgan’s ¬(x_1,1 v x_1,2 v … v x_1,n) v ¬ (x_2,1 v x_2,2 v … v x_2,n) v … v ¬(x_n,1 v x_n,2 v … v x_n,n))
7. Applying DeMorgan’s again (¬x_1,1 Λ ¬x_1,2 Λ … Λ ¬x_1,n) v (¬x_2,1 Λ ¬x_2,2 Λ … Λ ¬x_2,n) v … v (¬x_n,1 Λ ¬x_n,2 Λ … Λ ¬x_n,n))
8. 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.
9. 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.

Cheers, Joseph