REVIEW FOR SECTION 3

teacher image

Now that we are at the end of the course the additional skill that you need to have developed is to demonstrate through a step-by-step proof that an intended conclusion does follow from the premises given.

We most often will use direct derivations by which the statements in the premises lead to new statements through the application of either inference or equivalence (replacement) rules.  A key difference in the application of these rules is that equivalence rules can be used either for an entire statement or just for part of it while an inference rule can be used only with the main connective in the expression.  We may then think of inference rules as introducing or eliminating a connective (operator).
P & Q  |-  P     Simplification  (Simp)
P, Q  |-  P & Q      Conjunction  (Conj)
P v Q, ~P  |- Q      Disjunctive syllogism  (DS)
P  |- P v Q     Addition  (Add)
P -> Q, P |- Q       Modus ponens  (MP)
P -> Q, ~Q  |- ~P      Modus tollens  (MT)
P -> Q, Q -> R |- P -> R     Hypothetical syllogism  (HS)
(x)Fx  |-  Fa     Universal instantiation  (UI)
Fa  |- (x)Fx      Universal generalization  (UG)   normally this requires that the name in question cames from a previous application of the UI rule; the exception is when in a conditional proof we establish a statement such as Fa -> Ga  and then go to (x)(Fx - Gx) 
(Ex)Fx  |- Fa    Existential instantiation  (EI)    the name brought into play must be new--not appearing either in the statement of the argument fom or in a previous step
Fa |- (Ex)Fx     Existential generalization  (EG)

We also may work with an indirect derivation or proof (IP) by imagining or hypothesizing  that the intended conclusion is false (HIP), then discharging this hypothesis by showing that a contradiction appears.  We indent the steps in which this happens to make it clear that the information on those lines may be used only within this part of the derivation, which we call a subordinate derivation.  Indirect derivations may be used for all situations (something not true of direct derivations, which require that the premises do allow an immediate application of the rules).

For proofs in which the object is to establish that a conditional is true (a conditional proof or CP), we assume or hypothesize its antecedent (HCP) and then show that the conclusion will follow.

To demonstrate both an indirect and a conditional proof, let's imagine that we eliminated HS (hypothetical syllogism) from our package of inference rules but we still wanted to work through the following:  P->Q, Q->R |- P->R

an indirect proof (assume the conclusion is false and show                    a conditional proof  (assume the antecedent is true and
that this leads to a contradiction)                                                         show that the consequent follows)

1.  P -> Q                                                                                           1.  P -> Q
2.  Q -> R                 /   show P -> R                                                             2. Q  -> R     /   show P -> R
     |  3.  ~(P -> R)     HIP                                                                           |  3.  P     HCP
     |  4.  ~(~P v R)     3,  Impl                                                                     |  4.  Q     1,3,  MP
     |  5.   P & ~R       4,  DM                                                                      |  5.  R      2,4,  MP
     |  6.   P                5,  Simp                                                               6.  P -> R     3-5,  CP
     |  7.   Q                1,6,  MP
     |  8.   R                2,7,  MP
     |  9.   R&~R          8,9,  Conj
10.  P -> R                3-10, IP

The reasoning for an indirect proof is that a false conclusion (such as a contradiction) could follow from a series of valid steps only if a premise were false, and in this case we take it to be the negated conclusion set up as a new assumption.  In the line following the subordinate proof we "discharge the hypothesis" by asserting the intended conclusion.  Note that the justification indicates the calls lines from the hypothesis through to the contradiction.

The reasoning for a conditional proof, which can be very short, is that by assuming the antecedent true and then working through other steps we know that the consequent must be true as well, and this means we have established that the conditional itself is true.  Note that the justification lists the call lines from the assumed antecedent through to the consequent.

In your final exam you will be given a number of short arguments that you will need to (1) translate into symbolic logic notation, (2) examine for validity using either the reverse method truth table or a consistency tree (unless otherwise directed), and provide derivations when the arguments in fact are valid.  red flagThe most common mistakes to watch out for are
--going by the English word order in expressing a conditional relationship (always rethink what is the sufficient condition expressed or what is the necessary condition expressed, and make sure the sufficient condition is to the left of the arrow or the necessary condition to the right)
--failing to note what is the main connective (and that could be a quantifier or it could be a curl in front of a parenthesis)  in attempting to apply an inference rule
       an example would be attempting to go directly from (x)Fx & (x)Gx to Fa & Ga without first eliminating the ampersand
--not respecting the new name rule in any application of existential instantiation (EI)
       an example would be going from (Ex)Fx & (Ex)Gx to Fa & Ga, even after first eliminating the ampsersand
--not following the proper sequence in instantiating an expression with more than one quantifier involved  (we must move from the left inward, and we generalize outward from the right, even though here we are free to choose which name to work with first)