Topic DS: How to prove things with Sentential logic
2 Some rules
In
section DS01
you learned three rules. This section
and the next describe the remainder of the rules of
our system. There are 9 more rules, for a total of 12
rules in all.
If you are impatient, here is a list of
all of the rules.
At this point, there won't be much discussion about
why the rules are the way they are, or whether the
rules should be the way they are. We'll get to that in
Topic RS. For now, just work on learning what the
rules are, and how the rules work.
2.1 Rules for '&'
The
conjunction elimination rule, &E was mentioned
earlier, in
section DS01.
Let us state this rule carefully.
&E
(Conjunction Elimination)
If you have derived (φ&ψ),
you can write down
φ or
ψ,
depending on
everything (φ&ψ)
depends on.
According to this rule, if one of the lines of a derivation
is
a conjunction, (φ&ψ),
then you can add a new line which is
φ
or you can add a line which is ψ.
The greek letters 'φ'
and
'ψ'
stand for any well-formed formula of sentential logic.
Note that the dependencies of the new line are just the
same
as the dependencies of the original line. That is what the
rule
means when it says that the formula you write down depends
on "on everything (φ&ψ)
depends on."
&E helps you simplify things. You can eliminate the
symbol
'&' and write down only part of a formula. That is why
&E
is called an "elimination" rule.
But sometimes you might not want to eliminate '&', but
to add it into a derivation. Sometimes you might want to
write down a formula which contains a '&' when that
'&'
wasn't there before. There is a rule for that:
&I
(Conjunction Introduction)
If you have derived
φ and
ψ, you can write
down (φ&ψ),
depending on everything
φ and
ψ depend
on.
For most of the connectives, the rules in the system come
in pairs like these rules for '&'. There is an
elimination rule,
and an introduction rule. The elimination rule lets you get
rid of a symbol, and the introduction rule lets you add a
symbol when the symbol was not there before.
Rule &I says that if one of the lines of a derivation
is φ
and
one of the lines in the derivation is ψ
then you can add a
new line which is their conjunction: (φ&ψ).
The dependencies
of the new line are the same as all of the dependencies for
the line with φ
put together with all of the dependencies for
the line with ψ.
Here are two brief examples:
Exercise
2.1a
Is this a correct derivation?
Exercise 2.1b
Show (A & B) 
(B & A).
Exercise 2.1c
How many lines are there in the longest
derivation in our system?
2.2
Rules for '↔'
The
rules for '↔'
are straightforward. Here is an example
of a use of the biconditional elimination rule:
And, unsurprisingly then, here is the introduction rule:
Thus
↔E
lets you change a biconditional into the
conjunction of two conditionals. And
↔I
lets you
move in the opposite direction. The dependencies
work just as they do for &E: the new dependencies
are the same as the old dependencies. For both
↔E
and
↔I,
you just write down the same dependencies
as before.
Stated explictly:
↔I
(Biconditional Introduction)
If you have derived ((φ→ψ)&(ψ→φ)),
you can write down (φ↔ψ),
depending on everything ((φ→ψ)&(ψ→φ))
depends on.
↔E (Biconditional
Elimination)
If you have derived (φ↔ψ),
you can write down ((φ→ψ)&(ψ→φ))
depending on everything (φ↔ψ)
depends on.
You have now seen half of the rules in the system:
&I, &E, A, →E,
↔E,
and
↔I.
We will get to the
rest of the rules in a moment. But first, you
should try deriving a few things.
Exercise
2.2a
Show the following:
(A
↔
B), (B & C)
A
(A →
A)
(A
↔
A)
(A
↔
B), (B
↔
C), A
C
2.3
Rules for '→'
and the Rule of Assumption
Rule
→E was introduced in
section DS01:
→E
(Conditional Elimination or Modus Ponens)
If you have derived (φ→ψ)
and φ,
you can write down ψ,
depending on everything (φ→ψ)
and φ depend on.
Sometimes a rule like →E is called, using a Latin
expression,
Modus
Ponens.
But we'll just call it
Conditional Elimination,
or
→E
for short. An example of a use of such a rule in English
would be:
If John has measles then Harry has measles.
John has measles.
Therefore, Harry has measles.
As this seems clearly to be an example of good reasoning,
you can see why we might like to have version of this rule
in
our logical system.
The introduction rule, →I, is a little different from the
other rules
you have seen. One important difference is that →I permits
you
to
decrease
the number of dependencies.
Consider this short example showing B 
(A → (A&B)).
Notice that dependency of line 4 is only line 2,
while line 3 has two dependencies: line 1 and line 2.
Applying the rule →I yields the conditional on line 4
depending on everything line 3 depends on
except
line 1.
Since line 3 depends on 1 and 2, line 4 depends on just 2.
The idea behind →I is that if you can show ψ
given an
assumption φ,
then you have shown that if φ
then ψ,
that is (φ→ψ).
Here is the rule stated explicitly:
→I
(Conditional Introduction)
If you have assumed φ, and you have derived ψ,
you can write down (φ→ψ),
depending on everything ψ depends on except φ.
Rule →I provides a powerful, direct way to derive
a conditional, (φ→ψ).
You simply assume φ
and then,
using that assumption try to derive ψ.
If you succeed,
you will have thereby shown (φ→ψ).
And this conclusion
will no longer depend on the assumption
φ.
Assuming
φ
was just a temporary measure.
One point to keep in mind. Rule →I applies when
you have
assumed φ
and
derived ψ.
Be careful:
assuming and deriving are not the same. You have
derived a formula when it is a line of the derivation
you are working on. You have assumed a formula
when it is written down in your derivation using the
Rule of Assumption. The Rule of Assumption was
explained in section DS01. Here it is again:
A (Rule of
Assumption)
You can write down any SL wff, depending on itself.
Exercise 2.3a
Can you give an example of a derivation where
you assume a formula which you have not derived?
Exercise
2.3b
Is this a correct derivation?
Exercise 2.3c
What is wrong with the following derivation?
Exercise 2.3d
Show
the following:
(P → (Q → R))
((P
→ Q) →
(P
→ R))
(A→A)
((A&B)→A)