15.
A FIRST RULE SET FOR DIRECT
DERIVATIONS
You have already been working
with derivations in order to show that two expressions are
equivalent. Now we are going to work with derivations to show
that an intended conclusion necessarily follows from a given set of
premises. What is called natural deduction takes advantage of the
fact that not only can expressions be rewritten but that there are
certain relationships, first seen with our truth tables, that allow us
to introduce or eliminate our operators. Actually there are three
techniques we will look at, but the first involves what is called a
direct derivation, and to develop some facility with it we will limit
ourselves just to what happens when we want to either eliminate or
introduce our operators for conjunction (&) and disjunction (v).
P Q || P
& Q | P P Q || P | Q | P &
Q P Q || P v Q | ~P | Q P Q || P |
P v Q
1
1
1 1 1
1 1
1
1 1
1 1
0 1 1
1 1 1
1
0
0 1 1
0 1
0
0 1
0 1
0 0 1
0 1 1
0
1
0 0 0
1 0 1
0 0
1 1
1 1 0
1 0 1
0
0
0 0 0
0 0
0
0 0
0 0
1 0 0
0 0 0
Whenever we have two expressions said to be true at the same time, we
can see that either one would be true by itself.
P & Q |-
P Simp (short for "simplification")
Whenever we have two expression true independently, we can see that
they would be true together.
P, Q |- P
& Q Conj (short for "conjunction")
Whenever we have a statement that tells us one of true things has to be
true (even though both could be), ruling out means that we know the
other must be true. (Be careful not to turn this around and say
that knowing one is true means the other is false. We are working
with what is called inclusive disjunction,
as when we say you could take cream or sugar with your coffee, but you
could well take both. Exclusive
disjunction, as when we say you may take either coffee or tea,
does mean knowing one is true makes the other false, but we do not
ordinarily symbolize this relationship unless it is clearly necessary
to do so, and we do this by saying "x or y but not both x and
y.")
P v Q, ~P
|- Q DS (short for "disjunctive syllogism')
Whenever we have an expression true we could always tack on another
expression, which could be true or false, as an alternative and have the resulting disjunction
true. For instance, given that you are a student, I could say
that you are either a student or a movie star and still be correct.
P |- P v
Q Add (short for "addition')
In the application of these rules it does not matter, given our
commutation rule, whether we eliminate the left term or the right, and
it does not matter whether we introduce a term to the left or to the
right of the signal. And, as before, we build in the rule of
double negation.
What
certainly does matter is that, unlike our equivalence or
replacement rules, these new inference
rules apply only to a complete expression. If we have an
expression such as P v (Q & R),
for example, we may not use the simplification rule to say P v Q. (This is one of the
most common mistakes made by students getting started with derivations.)
To see how we may work with these derivations using only the four rules
above and the equivalence rules we have already seen, we will take two
patterns from your last set of exercises.
P v (Q & R),
~Q
|- P v R
1. P v
(Q & R)
2.
~Q
\show P v R
3. (P v
Q) & (P v R) 1, Dist
4. P v
Q
3, Simp
5.
P
2,4, DS note how we have two call lines to invoke
6. P v
R
5, Add
P & (Q v
R), ~R
|- P & Q
1.
P & (Q v R)
2.
~R
\show P & Q
3.
P
1, Simp
4.
Q v
R
1, Simp
5.
Q
2,4
6.
P &
Q
3,5, Conj
EXERCISES (ON YOUR OWN)
Provide direct derivations using just the
equivalence and inference
rules we we have worked with so far.
1. P -> (Q & R), ~P -> S,
~S |- P & Q
2. ~(P v ~Q), P v S, ~T
|- Q v T
3.
(P v Q) -> (R v S), P
& ~R |- S
4.
(P & Q) -> (R
& S), P, Q |- S
5. P
-> Q, Q -> R, S->T, P v S, ~T |- R
Go
to the answer key