Transcript Predicate Logic Truth Trees

Chapter Twelve
Predicate Logic Truth Trees
1. Introductory Remarks
The trees for sentential logic give us decidability—there is a
mechanical decision procedure that a machine could follow
to determine the validity or invalidity of each argument in
sentential logic.
Introductory Remarks, continued
The truth trees for predicate logic do not give us decidability
as there can be no such decision procedure for predicate
logic.
This is called Church’s undecidability result.
Introductory Remarks, continued
If an argument in predicate logic is valid, a machine will be
able to decide it is valid in a finite number of steps.
But if an argument is invalid a machine might not be able to
show it is invalid in a finite number of steps.
Introductory Remarks, continued
Given a tree in predicate logic, three things might occur:
1) All paths will close, so the argument is valid.
2) There will be at least one open path, and no way to apply
the tree rules to any line in that path, so the argument is
invalid.
3) The tree may seem to grow infinitely, in which case we
cannot determine if the argument is invalid.
Introductory Remarks, continued
Since we cannot predict if we have an infinitely growing tree
we cannot know whether a particular argument that meets
condition (3) is invalid or not.
2. General Features of the
Method
We use a form of indirect proof. We begin by testing an
argument by listing its premises and the negation of its
conclusion.
The only new rules we need are two of the four QN rules and
UI and EI.
UI and EI will always be applied to constants.
General Features of the Method,
continued
If we incorporate the identity sign into our symbolism trees
become more difficult to construct.
3. Specific Examples of the Method
There are four new rules for predicate trees that supplement
those for sentential trees: these concern the use of denial,
connectives, UI and EI.
Specific Examples of the Method,
continued
There are two methods for doing predicate trees:
A. The adherence to a prescribed order.
B. The unrestricted order.
4. Some Advantages of the Trees
For longer natural deduction proofs trees will usually involve
fewer steps.
We can also break down certain sentences more easily than
we can in proofs.
5. Example of an Invalid Argument with
at Least One Open Path
If we apply the tree rules until we can no longer apply them
and end with at least one open path we have an invalid
argument.
We can then read off the truth-values of the atomic sentences
and construct a counterexample to the argument.
6. Metatheoretic Results
Invalidity in a domain: An argument is invalid in a domain if
we can find a counterexample in it.
A domain with n members is said to be of cardinality n.
Metatheoretic Results, continued
1. The tree method will mechanically yield a correct
decision on every argument on which it yields
any decision at all, and it will yield a correct
decision on all valid arguments.
Metatheoretic Results, continued
2. We should be able to figure out a method such
that with the method of expansion we could know
that if we choose a domain of a certain size, a
valid argument will show up valid for the domain
and hence for all domains of cardinality greater
than zero.
Metatheoretic Results, continued
3. If the argument we are testing by trees is invalid,
the method may fail, and the method of expression
equally fails. Even for some argument we know to
be invalid, the truth tree method will not yield a
decision.
Metatheoretic Results, continued
Points 1-3 are in effect Church’s undecidability
results.
7. Strategy and Accounting
When predicate truth trees branch, the rules apply
serially to each open path.
Key Terms
• Cardinality of a domain
• Church’s undecidability result
• Flowchart for predicate trees
• Infinitely growing tree
• Invalid argument
• Invalidity in a domain