Section 1.2 Propositional Logic
37
18. [A S (B S C )] ` (A ~ D′) ` B S (D S C )
19. (A′ S B′) ` B ` (A S C ) S C
20. (A S B) ` [B S (C S D)] ` [A S (B S C )] S (A S D)
21. [A S (B S C )] S [B S (A S C )]
22. (A ` B) S (A S B′)′
23. (A S C ) ` (C S B′) ` B S A′
24. [A S (B ~ C )] ` C′ S (A S B)
Use propositional logic to prove the validity of the arguments in Exercises 25–33. These will become additional
derivation rules for propositional logic, summarized in Table 1.14.
25. (P ~ Q) ` P′ S Q
26. (P S Q) S (Q′ S P′)
27. (Q′ S P′) S (P S Q)
28. P S P ` P
29. P ~ P S P (Hint: Instead of assuming the hypothesis, begin with a version of Exercise 28; also make use
of Exercise 27.)
30. [(P ` Q) S R] S [P S (Q S R)]
31. P ` P′ S Q
32. P ` (Q ~ R) S (P ` Q) ~ (P ` R) (Hint: First rewrite the conclusion.)
33. P ~ (Q ` R) S (P ~ Q) ` (P ~ R) (Hint: Prove both P ~ (Q ` R) S (P ~ Q) and P ~ (Q ` R) S
(P ~ R); for each proof, first rewrite the conclusion.)
tAbLe 1.14
More Inference Rules
from
can derive
name/Abbreviation for Rule
P S Q, Q S R
P S R [Example 16]
Hypothetical syllogism—hs
P ~ Q, P′
Q [Exercise 25]
Disjunctive syllogism—ds
P S Q
Q′ S P′ [Exercise 26]
Contraposition—cont
Q′ S P′
P S Q [Exercise 27]
Contraposition—cont
P
P ` P [Exercise 28]
Self-reference—self
P ~ P
P [Exercise 29]
Self-reference—self
(P ` Q) S R
P S (Q S R) [Exercise 30]
Exportation—exp
P, P′
Q [Exercise 31]
Inconsistency—inc
P ` (Q ~ R)
(P ` Q) ~ (P ` R) [Exercise 32]
Distributive—dist
P ~ (Q ` R)
(P ~ Q) ` (P ~ R) [Exercise 33]
Distributive—dist
For Exercises 34–42, use propositional logic to prove the arguments valid; you may use any of the rules in Table
1.14 or any previously proved exercise.
34. A′ S (A S B)