Philosophy Stack Exchange is a question and answer site for those interested in the study of the fundamental nature of knowledge, reality, and existence. It only takes a minute to sign up.
Sign up to join this community
I just got the hang of using truth tables as a method to test for validity and invalidity. Now I'm learning the natural deduction method, and been told that it can test for validity, but not invalidity as the truth table method can. Why is this the case?
As a side note, it's hard to wrap my mind around how something can test for something but not its "opposite." Perhaps validity and invalidity are not contradictions but more like contraries? I don't know.
Natural Deduction is a proof system that is sound and complete for e.g. classical propositional calculus.
Sound means that if a formula is provable with ND, it is valid.
In general, a proof system is not an algorithm, i.e. if we start from a formula and we do not know if it is valid or not, the simple fact that we are not able to find a proof does not mean that the proof does not exist: maybe, we are simply not clever enough to find it.
Truth table, instead, is an algorithm to test validity for propositional calculus; this means that, applying it to a formula whatever, it always comes to an end with a result: if all rows have TRUE, the formula is valid; if there is some FALSE value, the formula is not valid.
Truth tables can become large if there are many sentence letters That is when natural deduction might find a solution in a more economical manner. That assumes one can derive a line in a natural deduction proof that corresponds to the desired conclusion. If not, one has to keep looking. A truth table, although potentially large, would let one know one does not have to continue.
Here is how the authors of forallx describe the situation in Chapter 20: Soundness and Completeness, page 149:
Now that we know that the truth table method is interchangeable with the method of derivations, you can chose which method you want to use for any given problem. Students often prefer to use truth tables, because they can be produced purely mechanically, and that seems ‘easier’. However, we have already seen that truth tables become impossibly large after just a few sentence letters. On the other hand, there are a couple situations where using proofs simply isn’t possible. We syntactically defined a contingent sentence as a sentence that couldn’t be proven to be a tautology or a contradiction. There is no practical way to prove this kind of negative statement. We will never know if there isn’t some proof out there that a statement is a contradiction and we just haven’t found it yet. We have nothing to do in this situation but resort to truth tables. Similarly, we can use derivations to prove two sentences equivalent, but what if we want to prove that they are not equivalent? We have no way of proving that we will never find the relevant proof. So we have to fall back on truth tables again.
P. D. Magnus, Tim Button with additions by J. Robert Loftis remixed and revised by Aaron Thomas-Bolduc, Richard Zach, forallx Calgary Remix: An Introduction to Formal Logic, Winter 2018. http://forallx.openlogicproject.org/
