# Relation between truth tables and trees

Given any argument, does the truth table necessarily contain more rows than the number of open branches in the completed tree?

My gut feeling tells me no because I could always find a complex argument in which the tree for that argument would have many branches. Is that right?

• This may be better answered on the mathematics forum. – Cort Ammon Mar 8 '15 at 16:26
• I'm not sure about "necessarily", but if you consider (p ∨ q) ∧ r the truth-table has 8 rows, three of which satisfying the formula, while a completed tree will show only two paths. – Mauro ALLEGRANZA Mar 8 '15 at 17:21

(For my proof, I'm assuming sentential logic.)

Given n sentence letters in argument A:

1. The truth table TbA for A will have 2n rows.
2. The truth tree TtA for A has an unbounded number of open branches.

Therefore, the TbA does not necessarily contain more rows than the number of open branches in TtA.

Proof: (1) is trivial but we can prove that the number of open branches are unbounded, i.e. (2), by induction on the disjunction operator like so:

First, consider the truth tree for P ∨ P: (Open branches: 2)

Next, consider the truth tree for P ∨ (P ∨ P): (Open branches: 3)

Finally, the truth tree for P ∨ (P ∨ (P ∨ P)): (Open branches: 4)

We already provided several counterexamples to the claim that a truth table necessarily contains more rows than the number of open branches in the completed tree, but we can generalize this phenomenon (at least in the disjunctive case) by noticing that the truth tree always branches at a disjunction. If there is no contradiction on one of the branches, the branch will remain open.

The following disjunction will yield n+1 open branches in TtA but only two rows in TbA: Where P is a sentence letter.The three above cases in fact show this disjunction where n = 1, 2, 3 respectively.

Truth trees generated with http://gablem.com/truth-tree-solver/sentential-logic.