Questions About Complete Truth Tables

Question

Why do you need a complete truth table to prove that a sentence is a tautology when you can just make a partial truth table starting with labeling the sentence as false and if it's impossible, the sentence must be a tautology?

Take ∼D ∨ D for instance. I make a partial truth table and I assume the statement is false. If I try to fill in the rest of the line, I find that not D and D have to be true at the same time in order to make the statement false. This is a contradiction, therefore it's impossible for the statement to be false so it must always be true (a tautology).

Answer 1

Ok, so you were thinking about:

Take ∼D ∨ D for instance. I make a partial truth table and I assume the statement is false. If I try to fill in the rest of the line, I find that not D and D have to be true at the same time in order to make the statement false. This is a contradiction, therefore it's impossible for the statement to be false so it must always be true (a tautology).

Well, you're (perhaps) intuiting resolution here. But the catch is that before you can identify terms like ∼D ∨ D you need to transform the formula to an appropriate representation where these terms are "sufficiently obvious"; as causative mentioned in a comment: where can you see terms like that in e.g. ((P→Q)→P)→P? And (in the worst case) doing this transformation may actually be as much work as computing the full truth table!

For example, for the formula I just mentioned, you'd need to transform it as follows:

((P→Q)→P)→P =
¬(¬(¬P ∨ Q) ∨ P) ∨ P =
(¬¬(¬P ∨ Q) ∧ ¬P) ∨ P =
((¬P ∨ Q) ∧ ¬P) ∨ P =
(¬P ∨ Q ∨ P) ∧ (¬P ∨ P)

Now you can actually see the kind of terms you were talking about... but how many steps did that take? This final form is a formula in CNF (conjunctive normal form). On a CNF formula, checking non-falsifiability is indeed fairly trivial: each conjunct needs to be true, and inside each conjunct that only happens if there are terms like ¬P ∨ P.

---

Having said that, there are some ways to speed up building a truth table, although not quite the one you envisaged. These happen implicitly when build a reduced BDD. Without getting to the details on that here, for ((P→Q)→P)→P you can reason as follows: if P=1, then it doesn't matter what the value of Q is, because the formula looks like (...)→1, which is always 1. In case where P=0, the formula becomes ((0→Q)→0)→0, which is again 1, because (0→Q)=1 regardless of the value of Q and then you just have to do a constant calculation ((1)→0)→0 = 0→0 = 1.

The trick here is that when you do a Shannon expansion you can further simplify the formula on each "branch" (more jargon-y called cofactors) in case there are "obvious" simplifications. (Building a reduced BDD essentially forces these simplifications.)

Answer 2

Let's see if this is what you mean. You want to show that a formula F is a tautology. The usual way is to build a truth table with one row for each combination of variable assignments in F, and if F is true in every row of this truth table, then F is a tautology. You are proposing, in order to show that F is a tautology, instead show that ~F is a contradiction using a truth table. The trouble is, to show that ~F is a contradiction using a truth table, you still need to build a truth table with one row for every combination of variable assignments in ~F, and show that all of those rows are false. It's not enough to just show that one row in ~F is false, because then ~F might still be true for a different assignment of variables, which would make F false for that assignment.