Ì Exam ple 8.2.11: Determine which of the following arguments are
valid-contruct proofs for the valid arguments.
(a) A B
A C
C B
∧
⇒
∴ ∧
(b) A B
A C
C B
∨
⇒
∴ ∨
(c) A B
A C
C
B
⇒
⇒
∴ ⇒
(d) A
B C
D
C
B
A
A
D
B
B
⇒ ∨
⇒ ¬
⇒ ¬
∴ ∧ ¬
(
)
Solu tion
(a) Given
A B
A C
C B
∧
⇒
∴ ∧
1.
A B
∧
P
2.
A C
→
3.
A
(1), Sim pli fi ca tion
4.
C
(2), (3), Modus Ponens
Therefore the given argument is INVALID.
(b) Given
A B
A C
C B
∨
⇒
∴ ∨
1.
A B
∨
P
2.
A C
⇒
P
3.
¬ →
B
A
(2), Impli ca tion
4.
¬ →
B C
(2), (3), Hyp. Syll.
5.
B C
∨
(4), Impli ca tion
Hence the argument is VALID.
(c) Given
A B
A C
C
B
⇒
⇒
∴ ⇒
274
Theory of Automata, Formal Languages and Computation