Solu tion
1.
P
M
→
P
2.
¬ M
P
3.
¬ P
(1), (2), Modus Tollens
4.
P Q
∨
P
5.
Q
Sim pli fi ca tion of (4)
6.
Q R
→
P
7.
R
Modus Ponens
8.
R P Q
∧ ∨
(
)
(
,
)
Q P Q P Q
⇒ ∧
Hence proved.
Ì Exam ple 8.2.4: Demonstrate that S is a valid inference from the
premises P
Q Q R S
P
→ ¬
∨ ¬ →
,
,
and ¬ R.
Solu tion:
1.
Q R
∨
P
2.
¬ R
P
3.
Q
(1), (2), Disj. Syll.
4.
P
Q
→ ¬
P
5.
¬ P
(3), (4), Contrapositive, Modus Tollens
6.
¬ →
S
P
P
7.
S
(5), (6), Modus Tollens
Ì Exam ple 8.2.5: Show that ¬
→ ⇒ ¬
Q P Q
P
,
.
Solu tion
1.
P Q
→
P
2.
¬ → ¬
Q
P
T, (1) and con tra pos i tive [
]
P Q
Q
P
→ ⇔ ¬ → ¬
3.
¬ Q
P
4.
¬ P
T, (2), (3) and Modus Ponens. [
,
]
P Q P Q
→
⇒
Ì Exam ple 8.2.5: Show that R S
∨ is a valid conclusion from the premises
C D C D
H
∨
∨ → ¬
,
, ¬ →
∧ ¬
H
A
B
(
) and (
) (
).
A
B
R S
∧ ¬ →
∨
268
Theory of Automata, Formal Languages and Computation