Truth Tree Catechism

Q: What is a truth tree?
A: A truth tree is a diagram that shows a set of compound propositions decomposed into literals following standard decomposition rules.

Q: What is a literal?
A: A simple proposition symbolized as a constant or variable, or the negation of the same.

Q: What does it mean to decompose a compound proposition?
A: It means to show the components that must be true for the decomposed proposition to be true. A fully decomposed proposition is broken down into literals.

Q: Why do some compound propositions branch when decomposed?
The branching shows that there is more than one way for the proposition to be true.

Q: What does consistency mean?
A: Consistent propositions can all be true at the same time.

Q: How does the truth tree show consistency?
A: If the propositions in the set are fully decomposed into literals on at least one branch without contradiction, the propositions are consistent.

Q: What does it mean to recover the truth values?
A: It means to show the truth values of the component propositions that make every proposition in the given set true.

Q: What does SM mean?
A: It stands for Set Member; a label for a proposition in the given set.

Q: What is the meaning of the number and the symbols at the end of a row?
A: It is the justification for the decomposition, showing the number of the compound proposition that is decomposed, and the abbreviation of the rule used to decompose it.

Q: What is the meaning of the Ο at the bottom of a truth tree branch?
A: It designates an open branch, meaning that there are no contradictions on that branch.

Q: What is the meaning of the numbers separated by an Χ at the bottom of a branch?
A: The X designates a closed branch; the numbers are the line numbers of the propositions that contradict on that branch.

Q: What is the benefit of using truth trees?
A: Truth trees do the same things as truth tables — showing consistency, equivalence, validity, etc. — but in a visual way. They are a tool used in higher-level logic.

Reductio Challenge

In formal proofs of validity, the reductio ad absurdum method can be used to make some proofs easier, and even some shorter. For example, consider this argument:

(~P ⊃ R) • (~Q ⊃ S)    ~(R S)    ∴ P • Q

The proof for this valid argument is 14 steps without the reductio (which I will let you try to solve on your own), but only 7 steps with the reductio, as shown here:

  1. (~P ⊃ R) • (~Q ⊃ S)
  2. ~(R ∨ S)   /  ∴  P • Q
  3. ~(P • Q)                     R.A.A.
  4. ~P ∨ ~Q                    3 De M.
  5. R ∨ S                         1, 4 C.D.
  6. (R ∨ S) • ~(R ∨ S)   5, 2 Conj.
  7. P • Q                          3-6 R.A.

The reasoning behind the reductio method is this: If assuming that a proposition is false leads to a self-contradiction, then the proposition must be true. This reasoning can itself be written as a propositional argument:

~P ⊃ (Q • ~Q)   ∴  P

This is a valid argument, as a shorter truth table will show. But the proof for this argument (if you are not allowed to use reductio) requires 13 steps, and it is rather difficult to solve. Any takers?

Two Strange Proofs

Mr. Nance,

Could you give real-world examples of the arguments to prove in Intermediate Logic Lesson 18, number 7) U / ∴ W ⊃ W, and number 8) X / ∴ Y ⊃ X, showing how they would be used, or explain them a bit? Thank you.

Thanks for the great question! These two arguments are unusual, so I am not surprised that you are asking about them.

A real-world example for #7 might be Esther 4:16, “I will go to the king which is against the law; if I perish, then I perish!” This argument form basically shows that any proposition implies a tautology.

An example for #8 could be, “God created all things. So even if evolution can be used to explain some fossils, it’s still true that God created all things.” The form of this argument shows that if a proposition is given, any other proposition implies it.

To be honest, my purposes for including those two problems were: 1) to show how very strange the conditional proof is, and 2) to show how this method can be used to simplify otherwise difficult proofs.


Conditional Proof Assumption

With the nine rules of inference and the ten rules of replacement taught in Lessons 13-17 of Intermediate Logic, any valid propositional argument can be proven. But for the benefit of the logic student, I introduce an additional rule in Lesson 18: the conditional proof. The conditional proof will often simplify a proof, especially one that has a conditional in the conclusion, making the proof shorter or easier to solve. Conditional proof starts with making an assumption. I want to clarify what happens with that assumption.

To use conditional proof, you start by assuming the antecedent of a conditional. If by using that assumption along with the other premises you are able to deduce the consequent, you can conclude the entire conditional using conditional proof. More briefly, if an assumed proposition p implies the proposition q, we can conclude if p then q.

One misconception new logic students often make is thinking that the assumption actually “comes from” some previous step in the proof. They think that the assumption must appear somewhere else in order to make it. This is not the case. The assumed antecedent doesn’t come from anywhere; it is quite simply assumed. I tell my students we get the antecedent from our imagination; from Narnia, Middle Earth, Badon Hill. With conditional proof, you are allowed to assume any antecedent you wish, as long as you use conditional proof correctly from that point on.


May Proofs Use the Same Line Twice?

Mr. Nance,

In the answer to Exercise 17a, problem #12, is there a typo? It has row 5 twice.

There is no mistake there. A given line may be used more than once in a proof, as I say at the end of Lesson 15, “Usually, though by no means always, every step in a proof is used and used once.” Line 5 is used twice, once to simplify to get ~L, and once to commute and simplify to get ~M. 


Guessing w/ Shorter Truth Tables for Consistency

Mr. Nance,

Two questions:
1.  If you guess on consistency must you guess again as in validity and equivalence?
2.  If you find it inconsistent once does that trump consistency no matter what?

Thanks so much in advance for your help.


1.  If you guess on consistency and get no contradiction, then you do not have to guess again. This is also true for validity and equivalence. In all three, if you guess, fill in truth values, and get no contradiction, then the question is answered (either that they are consistent, as in this case, or that the argument is invalid, or that the propositions are not equivalent).

2.  No, if you guess and get a contradiction (which looks like an inconsistency), then you must guess again, because the contradiction may mean that you just guessed wrong.

If you think about what consistency means, then all this makes sense. Consistency means the propositions can all be true. So if you assume they are true and can fill in the truth values without contradiction (even when you need to guess), then you have shown that they can be true.

Below is a short video in which I explain how shorter truth tables are used to determine consistency. 


Help Solving Proofs

If you are in Intermediate Logic and learning about proofs for the first time, or struggling through them again for the second or third time, here are some helpful suggestions for justifying steps in proofs, constructing proofs, or just getting better at proofs.

  1. Think about what a proof does. Recognize that the conclusion of a previous step becomes a proposition to use as a premise for a new step. Proofs are a series of connected arguments, conclusion of previous arguments becoming premises for new ones.
  2. If you are learning how to justify steps in proofs (that is, you are working on Exercise 14a:10-16, or 15a:1-6, or 16:11-18) and you are in the middle of a proof, ask yourself which steps you have not yet used. If you are trying to justify step 6, and the previous lines already used steps 1, 3 and 4, then you will probably use steps 2 and 5. Try reading them aloud, and listen for familiar patterns from the premises of the rules of inference.
  3. Rewrite the argument that you are trying to prove. This will help you more clearly see the premises you have and the conclusion you are aiming at. You also might recognize patterns for rules of inference and replacement that you need to use. Often, a proof is built around a single rule of inference or replacement, and the other steps are just needed to set the premises up. For example, if you read Exercise 17a problem 7 aloud, you might recognize the modus tollens. But it takes a couple of steps to set up the second premise of the modus tollens, and one step afterward to fix the double negation.
  4. In general, find the premises you have available to you (e.g. if you’re on step 5, the available premises are from steps 1-4), read them aloud, and listen for rule patterns. In fact, get used to the patterns of the rules by reading them aloud, using something other than p’s and q’s (e.g. for Disjunctive Syllogism say to yourself, “This or that, not this, therefore that.”
  5. Later proofs often use the procedures from earlier proofs. Exercise 17a problem 9 is built around a hypothetical syllogism, but you need to modify the proposition is line 1 to turn the conjunction into a disjunction so that the middles match for the H. S. To do that, you follow the procedures you used in problems 3 and 4.
  6. If you’re stuck, consider whether the next step might use the rule of Addition or Absorption. These are the rules that are often difficult to see when you need to use them. This is why in Exercise 14a:10-16, five of the seven proofs use one of these two rules, and in Exercise 15a, half of them use one of these rules. You need the practice.
  7. Another hint for if you are stuck constructing a proof is to try writing down every possible conclusion you can make from the available premises, and see if any of them help.
  8. You may have struggling through the assignment, succeeded writing some proofs but needed to look at the answer key for others. That’s okay. But I would suggest that you then go back and do the assignment again without looking. Practice makes habit.
  9. If it is still hard for you, if you are still not quite getting it, don’t sweat it. Take your time. Go drink some coffee and come back. Don’t say to yourself, “Well, I don’t get this, but I’ll just go on to the next lesson.” No. The lessons build on each other. If you are worried about getting through the entire text, stop worrying about it. You don’t need to cover it all. Better to learn a small amount of material well then a large amount of material poorly.
  10. If you need specific help (you’re stuck on a proof and you don’t know what to do), ask me. I would love to help. Message me on Facebook, or post a question on my Logic Facebook page.

Think about proofs like solving a puzzle, rather than thinking of it like homework. Make it a fun challenge.


Parentheses in Conditionals

Mr. Nance,

Could you please explain how the placement of the parentheses is determined in Test 1, Form A, #12 of Intermediate Logic? My student wrote “(M ⊃ P) ⊃ ~C,” but the answer key says “M ⊃ (P ⊃ ~C).”

The original proposition is,

“If we see a movie then if we eat popcorn then we do not eat candy.”

This proposition has the overall form pq, where p is the antecedent, “We see a movie” (abbreviated M) and q is the consequent. This consequent is another complete conditional: “If we eat popcorn then we do not eat candy.” This is the (P ⊃ ~C). Because it is a complete proposition in itself, this consequent gets placed in parentheses.

It will be important later to note that propositions of the form p ⊃ (qr) are equivalent to propositions of the form (p • q) ⊃ r. The given proposition could be understood in this way. “If we see a movie and eat popcorn, then we do not eat candy.” Notice in this form, “We see a movie and eat candy” is the antecedent, and it is a complete proposition in itself, and thus gets placed in parentheses.