1

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

7
  • One line where the 1st formula is TRUE and the 2nd is FALSE will suffice to disprove equivalence. Apr 1 at 15:15
  • 1
    A full truth table with all lines TRUE is necessary to show tautologueness. Apr 1 at 15:15
  • @MauroALLEGRANZA why can't we just show that the sentence being false is impossible (which means all lines must be true)? Apr 1 at 15:30
  • 1
    @Fizz 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) Apr 1 at 16:20
  • 1
    @IWantToLearn that's more along the lines of a deductive proof, not a truth table. Try showing (X -> (Y -> Z)) -> ((X -> Y) -> (X -> Z)). It's a tautology, show it with a truth table or with your method.
    – causative
    Apr 1 at 19:25
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.)

1
  • IF this is still confusing, you could ask separately what's the relationship between CNF (and DNF) and truth tables. I'm not sure I should go on lecturing about topics that were not asked about explicitly.
    – Fizz
    Apr 2 at 13:44
0

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.

4
  • Could you give an example of a statement where there are many roads to a false statement (which would force me to show the existence of multiple contradictions to prove a tautology)? When I assume the examples in my textbook for a tautology are false, there's always only 1 path to falsity so I only need to show the existence of 1 contradiction. Apr 1 at 16:35
  • @IWantToLearn Can you give an example where there is "1 path to falsity"?
    – causative
    Apr 1 at 16:54
  • 1
    To prove ∼ D ∨ D is a tautology I have to show it being false is an impossibility. There's only 1 way the statement can be false, namely if both disjuncts are false. This is an impossibility. I take it that "you still need to build a truth table with one row for every combination of variable assignments" doesn't apply to this case b/c I don't have to worry about any other path to the statement being false. There's only 1. Apr 1 at 22:19
  • @IWantToLearn: I have to wonder why you accepted this answer if you disagree with it... I will grant (causative) that you were not entirely clear in your original Q what you mean by "partial table". But after the example you gave, it was clear to me you were not talking merely about rows but about "columns" too, i.e. the irrelevance of some variables "shrinks" the tables both row- and column-wise, so to speak. The problem is that you can't really figure out which variables those (D's in your example) are while just building a truth table... you need a somewhat different method for that.
    – Fizz
    Apr 2 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.