Given a truth table, force a contradiction Suppose I have a formula, and a lying witness is attempting to make it evaluate to False.


  Given a truth table $c(F_1,…, F_n)$, how could you force a lying
   witness to contradict herself?


A contradiction is simply when the witness's statements are logically impossible; i.e. that $x_1,x_2$ are each True, but $x_1 \space AND\space x_2$ is False.


How can I characterize the set of all formula for which I force the witness to contradict herself?
What complexity class does this problem fall in?
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.