The Logic Café
Reference

Chapter Eight — PD: Derivations for
Predicate Logic

 

It is recommended that you print this reference.

Contents: Section 1: The system PD; Section 2: The system PD+; Section 3: Strategy

This chapter provides the derivation system for our new language PL. There are few new rules to learn, but at least two are a bit more complicated than the old rules, so pay careful attention.

 

1. PD

There are two easy rules for PD. Both implement straightforward principles. For example, if one knows that Chris, a member of class, is male ('Mc' is true), then one can obviously conclude that someone is male: (%x)Mx. In general:

%I
input:

output:		 P(a/x)

 (%x)Px

Just as trivially, if you know that everyone in the universe of discourse is male, it follows that Chris, as a member of the universe of discourse, is male.

^E
input:

output:		 (^x)P

 P(a/x)

For example, these two rules may be used as follows:

Premise 1 (^x)(Tx>Jx)
Premise 2 Ta
1 ^E 3 Ta>Ja
2,3 >E 4 Ja
4 %I 5 (%y)Jy

 

The last two rules of PD are a bit more complicated. These use names in a slightly unusual way: as a name for an arbitrary element of some group (^I) or as illustrative of some member (%E). First consider our rule which argues from arbitrary members of a group.

^I
input:

output:		 P(a/x)

(^x)P

Provided 'a' is arbitrary in this sense:

  •  'a' does not occur in any premise or undischarged assumption.
  •  'a' does not occur in P.

As long as the provisos are met, then this thinking goes from input which means roughly that any arbitrary a is P to the conclusion that everything is P. Makes sense, right?

Here's an application of the rule on line 6:

Premise 1 (^x)(Tx>Jx)
Premise 2 (^y)(Jy>Cy)
1 ^E 3 Ta>Ja
2 ^E 4 Ja>Ca
3,4 HS 5 Ta>Ca
5 ^I 6 (^z)(Tz>Cz)

Finally consider reasoning from an illustrative assumption.

%E

input:


input:



output:

 
(%x)Px
P(a/x)

Q
Q
 

Provided 'a' is illustrative in this sense:

  •  'a' does not occur in any premise or undischarged assumption.
  •  'a' does not occur in P.
  •  'a' does not occur in Q.

The first input requires that something be a P. The assumption gives a temporary name to illustrate such an object. Once the name is removed from the subderivation, the sentence no longer depends on the assumption, so the subderivation may be terminated.

Here is an example:

Premise 1 (%y)(Ty&Lay)
Assumption 2 ....what if Tt&Lat
2 &E 3 ....then... Tt
3 %I 4 ....then... (%y)Ty
1,2-4 %E 5 (%y)Ty

 

2. PD+

PD+ includes all the rules of SD+ and all the rules of PD. In addition, there is one new rule of replacement: QN.

QN
(Quantifier Negation)
~(^x)P (%x)~P
or
~(%x)P (^x)~P

Any accessible line which includes a tilde and a quantifier, one immediately following the other, is a candidate for QN.

Notice that this rule makes sense. For example, if not everything is P, then something is not P. Right?

Consider this application:

Premise 1 ~(^x)(Ax v Bx)
1 QN 2 (%x)~(Ax v Bx)
2 DM 3 (%x)(~Ax&~Bx)

 

3. Strategy

Strategy for PD and PD+ is very much like that for SD and SD+. Recall our chart:

General Strategy
  1. Consider goals that may plausibly allow you to complete your derivation.
    • Usually you will be given an ultimate goal: what you are asked to derive.
    • Often during the course of a derivation, strategy will require intermediate goals -- other sentences required to complete the derivation.
  2. Do what is obvious to you if that will clearly help you toward your goal(s).
  3. Use introduction and elimination rules:
    • Consider the I-rules appropriate for the main connective of your goal sentence.
    • Consider the E-rules appropriate for the main connectives of any accessible sentence you may have already derived (this includes assumptions).
  4. When all else fails (in the attempt to derive your goal P), assume ~P and attempt to subderive a contradiction so you can justify P by ~E.

Now Recycle: After you have applied a rule go back to 1 and start the goal analysis anew. Continue the process until you are finished.

One first provides a goal, then considers "obvious" ways to reasonably proceed toward that goal. When steps are not so obvious, one considers the I-rules for the main connective of the goal at hand and E-rules for the main connective of any accessible sentences.

If all else fails, the "desperation" step is to use ~E: assume the negation of your goal.

In PD, we should be especially aware of the new I and E rules. Two of the four stand out for special treatment in tutorial 3. The idea there is summarized in the following chart.

 Strategy for ^I 

 Strategy for ^E

For the case where a goal has main connective '^', one first tries to prove the appropriate substitution instance as preliminary goal. Recall the example from the tutorial:

Premise 1 (^x)(Mx>Bxc)    
Premise 2 (^y)(Ty=Byc)  
  3    
  4    
  5    
  6    
  7    
  8 Ma>Ta???  
8 ^I 9 (^x)(Mx>Tx)???  

Line 8 contains the new preliminary  goal (in yellow). Notice that 'a' counts as arbitrary (and meets our provisos for ^I.)

For the case where an accessible sentence contains a sentence with main connective '%', one may usually make progress by

  1. making an assumption which is an appropriate substitution instance of the given accessible sentence, then
  2. working toward a new, preliminary goal the subderivation of the ultimate goal.

For example, recall:

Premise 1 (%y)(Ay>Lmm)               
Assumption 2 What if .... At>Lmm   
  3 then.........    
  4 then.........    
  5 then.........    
  6 then......... (^x)Ax>Lmm???  
1,2-6 %E 7 (^x)Ax>Lmm    

Line 2 assumes a substitution instance of the accessible existential sentence of line 1. Notice that the name, 't', substituted for 'y' is picked so that it satisfies the provisos to count as "illustrative". It's usually best to make such an assumption as soon as you get an accessible %-sentence.

Line 6 is the new goal. Notice that it's just the old goal but within the subderivation. If it can be derived, then "1,2-6 %E" finishes the derivation at line 7.

 

In PD+, one may use the rules MT,HS,DS and the rules of replacement including QN. These should count as "obvious" when they are applicable. But remember, only use these many short-cut rules when it's obvious that their use will likely prove useful. Otherwise one may get lost in repeated applications which go nowhere.

(Note: Unless your instructor objects, you may go ahead and use any of the shortcut rules from SD+, MT,HS,DS and the rules of replacement, even when working in PD.)

 

back to chapter eight
on to the next chapter
continue with this reference