20130118

The Rest of the Rules

This brings us to the point where we can look at a couple of logical fallacies that are often encountered in the real world.  Computer scientists (who are by nature superior to most humans) would never commit such obvious blunders, but it surprising how frequently these crop up.

Fallacy #1:                     !PHI         PHI -> PSI
                                                 !PSI

For example, "If it snowed last night, class will be cancelled.  It didn't snow last night, so class will not be cancelled."



Fallacy #2:                     PSI         PHI -> PSI
                                                 PHI

For example, "If Skippy and Buffy broke up, Skippy will quit the We-Love-The-Gap Club.  Skippy quit the We-Love-The-Gap Club, so Skippy and Buffy broke up."



There is of course one more combination to consider.  Suppose PHI -> PSI and !PSI are both propositions in our proof.  In this case, we can ask if it is possible for PHI to be true.  If it were, then by Modus Ponens we would be able to add PSI  to our proof, and then by ^i we would be able to add PSI ^ !PSI.  But since PSI ^ !PSI must be false, we should not be able to add this to our proof.  It was our supposition that PHI is true that got us into trouble, so we can conclude that PHI must be false.

This argument motivates a second form of -> elimination, the Modus Tollens (Method of Denial) rule.  This rule is not given a symbolic representation in Natural Deduction, and is identified by the abbreviation MT.  If the justification given above seems a little more complex than the ones we have used before, you are right.  This rule is not as basic as the others, and we will see later that it can be derived from other, more fundamental rules.

"MT"                           !PSI         PHI -> PSI
                                              !PHI


The page http://www.cut-the-knot.org/do_you_know/falsity.shtml has some quotes and puzzles related to the implication operator.



The "Implication-Introduction" Rule  ("->i")

To introduce an implication, we start by making a temporary assumption that some proposition PHI is true.  To indicate that this proposition is not known to be true in the main proof, we create a box that surrounds the assumption and all following lines of the proof, until we decide to close the box (see below).

Using the assumption, the premises, and other available propositions (see below for a brief discussion on which propositions are available), we apply the rules of Natural Deduction.  At any time, we may decide to close the assumption box.  Suppose the proposition on the last line of the box is PSI.  We can now add the proposition PHI -> PSI to our proof.

The reasoning for this is that we have shown that if PHI is true, then PSI must also be true.  This corresponds exactly to the meaning of PHI -> PSI, so we can add the latter as a true statement within our proof.

The notation for this rule is

       +--------+
        |   PHI    |
        |     ...     |
        |   PSI    |
       +--------+
    ____________

    PHI -> PSI


The propositions that are available for use in the box are all the preceding propositions in the proof, except for ones that are in closed assumption boxes.  Once an assumption box is closed, we are not permitted to "reach inside" and pull out a proposition.

Consider the following Natural Deduction proof:

     +-----------------------+
1.   |   p          assumption    |
     +-----------------------+
2.   p -> p           ->i, 1

This is a perfectly valid proof - but what does it prove?  

It proves the validity of the sequent
                    |-   p -> p

Now this looks a little odd - it is a sequent with no premises.  In fact, there is nothing wrong with this, and if you think about it you will see that valid sequents with no premises are in a way the most powerful of all - the premises of a sequent give us a starting point for our proof, some building blocks (another way to look at it is to think of the premises as restrictions on the state of the world).  A proof that has no premises doesn't need any starting point, doesn't need to place any conditions on the state of the world in order to prove the truth of its conclusion - its conclusion is true in every possible situation.

A valid sequent with no premises is called a theorem.  Theorems can be simple or complex, and we will see that they are crucial in the analysis of whether the Natural Deduction logic system corresponds in any way to the real world.

Consider this sequent:

p -> q   |-   !q  -> !p

Here is a proof of this

1.  p -> q            premise
     +----------------
2.   |  !q                assumption
3.   |  !p                Modus Tollens, 1, 2
     +----------------
4.   !q -> !p            ->i, 2-3

It turns out that we can prove this sequent in the other direction also.  In other words

!q -> !p   |-    p -> q

is a valid sequent.  I will leave this proof to you.

In a situation like this, where we have two formulas PHI and PSI, and   PHI |-  PSI   and PSI |- PHI   are both valid sequents, we say that PHI and PSI are provably equivalent and we write
PHI -||- PSI


The "Or Elimination" Rule  ("Ve")

If a proof contains the proposition PHI V PSI, we know that at least one of PHI and PSI is true, but we cannot be sure which.  To apply this knowledge and introduce a new proposition CHI based on this one, we need to show that CHI is true no matter which of PHI and PSI is true. 

As a natural language example to illustrate this concept, consider these premises:
      
       "If I am happy, I will want to watch House"
       "If I am sad, I will want to watch Grey's Anatomy"
       "If I want to watch House, I will turn on the TV"
       "If I want to watch Grey's Anatomy, I will turn on the TV"
       "Either I am happy, or I am sad"

From these premises, it is clear that I will turn on the TV

The pictoral representation of this rule is too difficult to do with ASCII.  Sorry.

Example:     (p -> q) V (p -> r) |-  p -> (q V r)

1.   (p -> q) V (p -> r)               premise
      +---------------
2.   |  p                                       assume
      |   +-------------
3.   |   |  p -> q                           assume
4.   |   |  q                                   ->e, 2, 3
5.   |   |  q V r                             Vi1, 4
      |   +-------------
      |   +-------------
6.   |    |  p -> r                           assume
7.   |    |  r                                   ->e, 2, 6
8.   |    |  q V r                            Vi2, 7
      |    +-------------
9.   |    q V r                                Ve, 1, 3-5, 6-8
      +-----------------
10.  p -> ( q V r)


When we are inside an assumption box, we can use or copy any previous proposition that is not inside a closed assumption box.  We cannot use or copy any proposition that occurs only inside a previous, closed, assumption box.



The Copy Rule

At any time, we can  introduce a copy of an earlier proposition (unless it only occurs inside a closed assumption box).

Example:

Here is a proof of the sequent  p |-  q -> p

1.   p                           premise
      +-------------
2.    |   q                      assume
3.    |   p                      copy, 1
      +-------------
4.   q -> p                   ->i, 2-3


Rules for Negation

Definition: a contradiction is a proposition which must always be false.  The classic example is PHI ^ !PHI, but there are infinitely many other contradictions.  For example, since all theorems are necessarily (and provably) true, the negation of any theorem must be false.  So !(PHI -> PHI) is also a contradiction.

In Natural Deduction we use a symbol to represent contradictions:       |     , which is called "bottom".   One of the points of natural deduction that many people find hard to accept that if a sequent contains a contradiction among its premises, then it is valid to put any proposition as the conclusion.  That is,"   |    |- PHI " is always a valid sequent.  There are a couple of ways to see why this makes sense.  The "|-" symbol means "if the premises are true, then the conclusion must also be true".  We can turn this around a bit and restate it as "if the premises are true, it is not possible to find a situation in which the conclusion is false".  (We won't be absolutely sure that these two versions are equivalent until we have shown that propositional logic is sound and complete - i.e. that the things we can prove are exactly the things that are true.)  Now the "   |    |- PHI " sequent makes more sense: since the premise can never be true, we don't have to worry about proving that the conclusion is true or false.

Another way to approach this is to actually prove the sequent "   |    |- PHI " using only the other rules of N.D.  - we did this in class.  The text presents this as a basic rule, and shows how some of the other rules can be derived from it.  It is equally possible to take the other rules as being basic, and to derive this rule from them.

As a rule of N.D., this is called "bottom elimination" and looks like

                   |   
        ____________                |  e
                PHI


Since a contradiction is necessarily false, and our proofs consist of propositions that are necessarily true, it is not immediately clear how we can introduce a contradiction into a proof.  However, we have a rule for doing it:

       PHI       !PHI               !e
                  | 

For reasons that I don't know, the text refers to this as the "NOT elimination" rule rather than as the "Bottom introduction" rule.


Derived Rules

Using the rules that ND provides as fundamental rules, we can derive other useful rules for use in our proofs.  We have already seen one of these: Modus Tollens.  You should review and understand the derivation of MT from the other rules.

It is also possible to derive the "double negation introduction" rule

             PHI
            !!PHI

from the "NOT elimination" rule.

Two new rules that we derive are probably the most frequently used rules in all ND proofs:  Proof by Contradiction and The Law of the Excluded Middle.

Proof by Contradiction

This looks almost identical to the "NOT introduction" rule, and is in fact easily derived from it.  The rule looks like this

      +-------+
       |  !PHI  |
       |    ...     |
       |     |      |
      +-------+
                           
          PHI

The sense of this is that if we want to prove that PHI is true, we start by assuming !PHI and show that this leads to a contradiction.  Since we do not accept a contradiction as part of a valid proof, the assumption we made must have been false.  This yields !!PHI, which we simplify to PHI.

We usually abbreviate Proof by Contradiction to PBC.

Law of the Excluded Middle

Or in Latin, tertium non datur.  We normally abbreviate this law as LEM.  LEM says that for any proposition PHI, either PHI is true or PHI is false.  The rule looks like this

                        
  PHI V !PHI

which as you can see has nothing above the line - i.e. we can introduce the proposition PHI V !PHI into our proofs at any time, with no required premises or previous occurrences of any of the symbols that might happen to be in PHI.

You should review the derivation and applications of  PBC and LEM.


We spent some time in class talking about intuitionistic logicians who do not accept LEM or PBC in their proofs.  Their reasons cannot really be summarised in just a few words, but one of their fundamental ideas is that you should not state anything in a proof unless you actually have a proof of it.  When we use LEM, we don't give a proof of either PHI or !PHI, we just assert that one of them must be true.  Intuitionistic logicians say that we need to prove this by giving an explict proof of either PHI or !PHI.