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 (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}) - 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 - 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})) - 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})) - 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})) - 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.

Cheers, Joseph