14.  USING CONSISTENCY TREES FOR PROPOSITIONAL LOGIC


The use of truth tables to test for validity appeared early on in the development of modern symbolic logic, but a more recent technique with clear advantages has come into general use as well.  This is the use of consistency trees (sometimes called refutation trees).

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.  We begin by lining up the original premises and then we say the conclusion is false (we negate it) in order to see whether the resulting pattern allows all the expressions to be consistent.  If so, the form is not valid by definition (it is possible for the premises to be true and the conclusion false).

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    (again negating the original conclusion)
/   \
~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 law
/                      \
~P              Qv~(Rv~P)
         /             \
          Q      ~(Rv~P)
                     ~R
                      P

We can see all the possibilities for decomposing an expression without quantifiers 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

EXERCISES  (ON YOUR OWN)


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

Go to the answer key