Consistency trees (also called refutation trees)

are a particularly useful way of having a visual display of whether an argument form is valid.  The concept behind them is simple enough:  if I have expressions such as P and ~P they cannot both be true.

We can show this by positioning one over the other and then showing the effect of the inconsistency below this.

P
~P
x

Suppose I have expressions such P -> Q and ~P & ~ Q.   Since any implication could also be expressed as the disjunction ~P v Q  (remember the equivalence we call material implication), we could see the first expression as breaking up ("decomposing") into two branches.  The second expression has to be rewritten with one atomic formula over the other.

P -> Q
~P & ~Q
~P
~Q
/     \
                                                   ~P   Q  (rewriting the first expression)
         x

                                                                                                
In this display we see that only one branch involves inconsistency and so is "closed".  Since there is still an "open" branch we can say that the expressions are consistent (meaning, they can be true at the same time).

How can we use trees to test for the validity of an argument form?  Let's go back to the definition of validity: in a valid pattern we cannot have true premises and a false conclusion.  In an invalid argument these could exist together--they would be consistent.   Let's look at two different patterns.

P -> Q, P |- Q

P -> Q
P
                                                           ~ Q    (negating the original conclusion)
/    \
~P   Q
           x    x    valid

P -> Q, Q |- P

P -> Q
Q
~P
/   \
~P  Q
                         invalid

                                                                

In the top display both branches close, so we know the form is valid.  In the bottom display one branch remains open, so we know the form is not valid (in fact, it represents the formal fallacy of affirming the consequent)

Every expression can be rewritten as either a conjunction with its parts lined up or as a disjunction with branches.  This might take several steps.

~(P & ~(Q v (R v ~P)))
                                                               ~P  v (Q v ~(R v ~P))     here we're using DeMorgan's laws
/                      \
~P              Qv~(Rv~P)
         /             \
          Q      ~(Rv~P)
                     ~R
                      P

We can see all the possibilities for decomposing a wff in this chart:
 
 
P & Q  P v Q   P-> Q P<-> Q ~(P&Q) ~(PvQ) ~(P->Q) ~(P<->Q)
    P   /    \   /     \   /     \   /     \     ~P      P   /      \
    Q P     Q ~P    Q  P    ~P ~P   ~Q    ~Q     ~Q P       ~P



Q   ~Q


~Q      Q


Please note that the idea of trees is also explained at the Hurley website.

Practice exercises


Use both reverse-method truth tables and consistency trees to test the following argument forms for validity.

1.    P v (Q & R), ~Q  |- P v R
2.    P & (Q v R), ~R  |- P & Q
3.    P -> (Q & R), ~(P v Q) |- R
4.    ~P -> (Q v R), ~(P & Q) |- ~R

Provide derivations for the forms that are valid.