11.1: Introduction

Truth-trees for propositional logic can be extended to predicate logic. We use them to find counterxamples to show an argument is valid or that a formula is an MQT-necessity.

Extending truth-tres to predicate logic requires two new decomposition rules for each new operator.

QN: (from the Quantifier Negation rules)

1.   ~ ($x) F   X

         .

         .

         .

     ("x) ~ F

2.   ~ ("x) F   X

         .

         .

         .

     ($x) ~ F

EI: (Existential Instantiation)

3.   ($x) F(x)   X a

       .

       .

       .

       F(a)

($x)is the main operator.

F(x) is a formula containing free occurrences of variable x.

F(a) is that formula with those occurrences of x replaced by the constant 'a'

NB: 'a' has not occurred before in this branch of the truth-tree.

Keep track of the new constant by writing it beside the tick that marks the decomposition of the existential formula.

The idea is that the formula claims that F(x) is true of something. So make it true of 'a'.  'a' has to be a new constant because we don't know that F is going to be true for the constants that have already been used.

UI: (Universal Instantiation)

4.   ("x) F(x)   \ a

       .

       .

       .

       F(a)

("x)is the main operator.

F(x) is a formula containing free occurrences of variable x.

F(a) is that formula with those occurrences of x replaced by the constant 'a'

'a' is any constant at all.

Keep track of the new constant by writing it beside the BACKSLASH that marks the ongoing decomposition of the universal formula.

The idea is that the formula claims that F(x) is true of everything. So make it true of 'a'.  The decomposition is ongoing because new instantiations are always possible from the universal formula: eg. F(b), F(c), ...

This fact is marked by the use of the backslash rather than the X.

A rule of thumb for Predicate Logic is to apply decomposition rules according to the following preference order

1. Propositional Logic Rules  

2. QN 

3. EI

4. UI

Follow this example:

P     (($x) Fx & ($x) Gx)    X

NC    ~ ($x) ( Fx & Gx )     X

3     ($x) Fx                X a    

4     ($x) Gx                X b

5     ("x) ~ ( Fx & Gx )     \ a b, QN

6     Fa                     3, EI

7     Gb                     4, EI

8     ~ ( Fa & Ga )          5, UI

9     ~ ( Fb & Gb )          5, UI

            / \

10       ~Fa  ~Ga            8, ~&

          X    / \

11           ~Fb ~Gb         9, ~&

                  X

Ascend the open path to get values for a counterexample. This will give you

                F    G

          a    1     0

          b    0     1

In predicate Logic, this means we have a putative counterexample. We must test finite world counterexamples by eliminating quantifiers. Thus:

P     (Fa v Fb) & (Ga v Gb)

      ( 1 v 0 ) & ( 0 v 1 )

          1     &     1

                1

C     (Fa & Ga) v (Fb & Gb)

      ( 1 & 0 ) v ( 0 & 1 )

          0     v     0

                0

So this is a counterexample.

When every operator has been decomposed once and the tree is still open, before you conclude that there is a counterexample, ask yourself:

     HAS EVERY UNIVERSAL QUANTIFIER BEEN DECOMPOSED TO EVERY CONSTANT?

If not, then do so, until it becomes clear - this must be a matter of judgement - that the tree cannot close. Then try counterexamples.

When the universal quantifiers have all been  decomposed to every individual constant, we have a total universal instantiation (TUI).  

For every MQT-necessity there is a closed tree, though it may not be trivial to find it. We know we have found a counterexample only when we have tested a purported counterexample against the formula and have found the expansion of the formula to be false in that case.