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
3( E x)A(x) 4′
(4x) 3A(x) 4′
Negation—neg
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
P S Q, Q S R
P S R
Hypothetical syllogism—hs
P ~ Q, P′
Q
Disjunctive syllogism—ds
P S Q
Q′ S P′
Contraposition—cont
Q′ S P′
P S Q
Contraposition—cont
P
P ` P
Self-reference—self
P ~ P
P
Self-reference—self
(P ` Q) S R
P S (Q S R)
Exportation—exp
P, P′
Q
Inconsistency—inc
P ` (Q ~ R)
(P ` Q) ~ (P ` R) Distributive—dist
P ~ (Q ` R)
(P ~ Q) ` (P ~ R) Distribution—dist
803
Derivation Rules for Propositional
and Predicate Logic
A A
A p p e n d i x