28
Formal Logic
derivation rules should be kept to a minimum in order to make the formal system
manageable. We would like the system to have the smallest set of rules that still
allows it to be complete.
Derivation rules for Propositional Logic
The derivation rules for propositional logic fall into two categories, equivalence
rules and inference rules. Equivalence rules allow individual wffs to be rewritten, while inference rules allow new wffs to be derived from previous wffs in the
proof sequence.
equivalence rules state that certain pairs of wffs R and S are equivalent.
Remember from Section 1.1 that R 3 S means that R 4 S is a tautology and
that S can be substituted for R in any wff with no change to the truth value of that
wff. Equivalence rules are therefore truth-preserving; a true wff remains true if
such a substitution is done within it.
Table 1.11 lists the equivalence rules we will use in our formal system for
propositional logic. (Additional rules could be formulated based on other tautologies, but we are trying to keep our rule set to a minimum.) Each is given a name
to make it easier to identify its use in a proof sequence. We saw the commutative
and associative rules, as well as De Morgan’s laws, in Section 1.1. There they were
given for statement letters only, here they are given for any wffs P, Q, R, but they
are still tautologies.
pRaCtiCe 9 Prove the implication rule.
That is, prove that
(P S Q) 4 (P′ ~ Q)
is a tautology.
tAbLe 1.11
equivalence Rules
expression
equivalent to
name/Abbreviation for Rule
P ~ Q
P ` Q
Q ~ P
Q ` P
Commutative—comm
(P ~ Q) ~ R
(P ` Q) ` R
P ~ (Q ~ R)
P ` (Q ` R)
Associative—ass
(P ~ Q)′
(P ` Q)′
P′ ` Q′
P′ ~ Q′
De Morgan’s Laws—De
Morgan
P S Q
P′ ~ Q
Implication—imp
P
(P′)′
Double negation—dn
P 4 Q
(P S Q) ` (Q S P)
Definition of equivalence—equ
eXAMPLe 11
Suppose that one hypothesis of a propositional argument can be symbolized as
(A′ ~ B′) ~ C