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.