O'Reilly logo

Good Math by Mark C. Chu-Carroll

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Branching Proofs

The two truth-tree proofs we’ve seen so far have both been single-branch proofs. In practice a lot of interesting proofs, particularly in number theory and geometry, turn out to be single-branch. Some proofs, though, do need branching. To see how that works, we’re going to look at another tautology: the transitivity of implication. If we know that statement A implies statement B, and we also know that statement B implies a third statement, C, then it must be true that A implies C. In logical form, (A B B C) (A C).

The following figure shows the truth-tree proof of this. We’ll walk through the steps together. The strategy in this proof is similar to what we did in our proof of the law of the excluded middle. We want ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required