Given a truth table, force a contradiction
It appears the question that you are asking is:


  What is the set of formula for which a witness attempting to prove the formula false will always fail?


That is, you are asking whether a formula is valid: whether it is true for every interpretation. A formula is valid if and only if its negation is unsatisfiable, which according to this resource is Co-NP complete.