Section 1.2 Propositional Logic
29
Then a proof sequence for the argument could begin with the following steps:
1. (A′ ~ B′) ~ C hyp (hypothesis)
2. (A ` B)′ ~ C
1, De Morgan
3. (A ` B) S C
2, imp
The justification given for each step is not a required part of the proof sequence,
but it does confirm that the step is a legitimate one. Step 1 is a hypothesis. Step 2 is
derived from step 1 by applying one of De Morgan’s Laws. Step 3 is derived from
step 2 by using the implication rule that P S Q is equivalent to P′ ~ Q, where P is
the wff A ` B, and Q is the wff C.
The equivalence rules allow substitution in either direction. That is, in Example 11 we replaced A′ ~ B′ with (A ` B)′, but in some other proof sequence,
using the same rule, we might replace (A ` B)′ with A′ ~ B′.
inference rules say that if one or more wffs that match the first part of the
rule pattern are already part of the proof sequence, we can add to the proof sequence a new wff that matches the last part of the rule pattern. Table 1.12 shows
the propositional inference rules we will use, again along with their identifying
names.
tAbLe 1.12
Inference Rules
from
can derive
name/Abbreviation for Rule
P, P S Q
Q
Modus ponens—mp
P S Q, Q′
P′
Modus tollens—mt
P, Q
P ` Q
Conjunction—con
P ` Q
P, Q
Simplification—sim
P
P ~ Q
Addition—add
Unlike equivalence rules, inference rules do not work in both directions. We
cannot “reverse” the addition rule in Table 1.12; from P ~ Q, we cannot infer
either P or Q.
eXAMPLe 12
Suppose that A S (B ` C ) and A are two hypotheses of an argument. A proof sequence for the argument could begin with the following steps:
1. A S (B ` C ) hyp
2. A
hyp
3. B ` C
1, 2, mp
The justification at step 3 is that steps 1 and 2 exactly match the pattern required
for modus ponens, where P is A and Q is B ` C. Modus ponens says that Q can be
derived from P and P S Q.