12.  DERIVATIONS USING EQUIVALENCE RULES

For most students, the real challenge of symbolic logic comes with presenting step-by-step proofs or derivations to show that any two expressions have the same truth value (that they are equivalent) or that any given valid argument form really has to be so.  We are going to begin with showing proofs for equivalence.

To do this we are going to look at some of the things we can see from a truth table.  Whenever we are connecting any two expressions with either & (expressing conjunction) or v  (expressing disjunction) or with <-> (expressing a biconditional), the order in which we have the expressions will not matter.  (This was definitely not true when we used the arrow to express a conditional!)
A
 B
 A & B
 B & A
 A v B
 B v A
 A <-> B
 B <-> A
1
 1
 1
 1
 1
 1
 1
 1
1
 0
 0
 0
 1
 1
 0
 0
0
 1
 0
 0
 1
 1
 0
 0
0
 0
 0
 0
 0
 0
 1
 1

Knowing this, we can then set up the first of our equivalence rules, which we label commutation ("Com" for short).
       P & Q  ::  Q & P         Com
       P v Q  ::  Q v P           Com
       P <-> Q  ::  Q <-> P    Com

What this means is that whenever we have one expression that has the same truth value as another, we may substitute the first for the second.  We might apply this in the following way:  
        1.  [(Q & P) -> R] <-> [(S v R) -> T]      / show  [(R v S) -> T] <-> [(P & Q) -> R]
        2.  [(P & Q) -> R] <-> [(S v R) -> T]     1,  Com
        3.  [(P & Q) -> R] <-> [(R v S) -> T]     2,  Com
        4.  [(R v S) -> T] <-> (P & Q) -> R       3,  Com

What we did each time was apply the rule to a particular part of the entire expression (what was given in the first line) until we had arrived at the intended expression (indicated by what followed "show").   The lines are numbered (we use the term "call lines"), and we always indicate what line we work with as well as the rule applied in what is called the justification for the move from one line to the next.

A second equivalence rule follows from the fact that if we have only "and" or "or" in an expression with more than two terms, we could group the terms differently and again not have changed the truth value.  We label this our association rule ("Assoc" for short).

       (P & Q) & R  ::  P & (Q & R)     Assoc
       (P v Q) v R  ::   P v (Q v R)         Assoc

Less obvious at first is what happens when we have an expression such as P v (Q & R) or P & (Q v R).  Let's again use truth tables to see what goes on when we "distribute" the first term in each expression.

P
 Q
 R
 P v (Q & R)
 (P v Q) & (P v R)
 P & (Q v R)
 (P & Q) v (P & R)
1
 1
 1
        1
                  1
         1
                   1
1
 1
 0
        1
                  1
         1
                   1
1
 0
 1
        1
                  1
         1
                   1
1
 0
 0
        1
                  1
         0
                   0
0
 1
 1
        1
                  1
         0
                   0
0
 1
 0
        0
                  0
         0
                   0
0
 0
 1
        0
                  0
         0
                   0
0
 0
 0
        0
                  0
         0
                   0

This leads to our distribution rule  ("Dist" for short).

       P v (Q & R)   ::   (P v Q) & (P v R)     Dist
       P & (Q v R)  ::   (P & Q) v (P & R)    Dist

When we are negating an expression, it seems obvious enough that negating the negation takes us back to where we began.  So we have a rule of double negation ("DN" for short).

       P  ::  ~~P     DN

What happens when we negate something inside a parenthesis is maybe less obvious.  The mathematician who first pointed this out was named Augustus de Morgan, and the rule we have is named DeMorgan's Law  ("DM" for short) in his honor.  When we say it's false that Alice will both study and pass it is the same as saying that either she will not study or she will not pass (and both could be true)  When we say it's false that Alice will either study or pass it's the same as saying that she will not study and she will not pass (neither is true).

P
 Q
 ~(P & Q)
 ~P v ~Q
 ~(P v Q)
 ~P & ~Q
1
 1
           0
       0     
         0
 0
1
 0
           1
 1
          0
 0
0
 1
           1
 1
          0
 0
0
 0
           1
 1
          1
 1

       ~(P & Q)  ::  ~P v ~Q     DM
       ~(P v Q)   ::   ~P & ~Q    DM

We also build the idea of double negation into the application of this rule so that, for instance, we can move directly from ~(P v ~Q) to ~P & Q without having first to write ~P&~~Q.

Another rule we want to look at that involves negation expresses the idea of contraposition, as when we say that you will pass only if you study means that once we know you are not studying we can say you will not pass.  One expression is the contrapositive of the other, but since it is more often referred to as the transposition rule we indicate it as "Trans."
P
 Q
 P -> Q
 ~Q -> ~P
1
 1
 1
 1
1
 0
 0
 0
0
 1
 1
 1
0
 0
 1
 1

       P -> Q  =  ~Q -> ~P      Trans      (again, to save steps, we allow the idea of double negation to be built into the application of this rule as well as into all the other equivalence or replacement rules that appear here)

Working with biconditionals we have another equivalence we may consider.  First, when we say that Alice will pass if and only she studies, it is the same as saying both she will pass if she studies and she will pass only if she studies.  This rule we will refer to as material equivalence ("Equiv" for short).

       P <-> Q   ::   (P -> Q)  &  (Q -> P)     Equiv
      
The last equivalence rule that we will accept for the present (there are more) involves something you may have noted earlier.  When we say you will pass only if you study it means the same as saying you will not pass unless you study.  By negating the antecedent we can turn the conditional into a disjunction.  (Be careful in the application of this rule.  What is negated is to the left of the arrow or the wedge.)  We call this material implication ("Impl" for short).

P
 Q
 P -> Q
 ~P v Q
1
 1
 1
 1
1
 0
 0
 0
0
 1
 1
 1
0
 0
 1
 1

       P -> Q   ::  ~P v Q      Impl 

DERIVATIONS TO PROVE EQUIVALENCE

The idea of two expressions being equivalent is that one can be shown to turn into the other.  A derivation to show equivalence then has two parts.  Let's look at the example below.

We want to show that (P & Q) -> R  does mean exactly the same as P -> (Q -> R).  We will go from one to the other, then back again

1.  (P & Q) -> R      /  show  P -> (Q -> R)              1.  P -> (Q -> R)       / show  (P & Q) -> R
2.  ~(P & Q) v R      1,  Impl                                  2.  ~P v (Q -> R)      1,  Impl
3.  (~P v ~Q) v R     2,  DM                                   3.  ~P v (~Q v R)      2,  Impl
4.  ~P v (~Q v R)     3,  Assoc                               4.  (~P v ~Q) v R      3,  Assoc
5.  P ->  (~Q v R)    4,  Impl                                   5.  ~(~P v ~Q) -> R  4.  Impl
6.  P ->  (Q -> R)     5,  Impl                                  6.  (P & Q) -> R       5.  DM 


EXERCISES  (TO DO ON YOUR OWN)

A.  Symbolize each of the following pairs of English sentences and decide whether they are in fact providing exactly the same logical information (disregarding the tense of the verbs).  Indicate by "yes" or "no"  and explain how you would know.

1.  Alice will pass if she studies.  Alice will not pass unless she studies.
2.  Alice will pass only if she studies.   Either Alice has studied or she did not pass.
3.  If Alice passes she will graduate and she will transfer.   If Alice does not transfer then either she will not have passed or not have graduated.
4.  Unless Alice graduates and transfers we will know she did not pass.   If Alice did pass then she must have graduated and transferred.

B.  For each of the following pairs of equivalent expressions, present two derivations as in the model above.

1.  A -> (B & C)  and  (~A v  B) & (~A v C)
2.  A <-> B  and  (~A v B) & (A v ~B)

Go to the answer key.












PROGRESS REPORT



Progress report
Your Name:





Your E-Mail:





What section have you now completed?





Do you have any questions or comments?