30 Q Theory ofComputer Science
Solution
Let B(x) denote 'x is a baby'.
Let lex) denote 'x is illogical'.
Let D(x) denote 'x is despised'.
Let C(x) denote 'x can manage crocodiles'.
Then the premises are:
(i) Vx (B(x) ::::} I(x))
(ii) Vx (C(x) ::::} ,D(x))
(iii) Vx (l(x) ::::} D(x))
The conclusion is Vx (B(x) ::::} , C(x)).
1. Vx (B(x) ::::} I(x))
Premise (i)
2. Vx (C(x) ::::} ,D(x))
Premise (ii)
3. Vx (l(x) ::::} D(x))
Premise (iii)
4. B(x) ::::} I(x)
1, Universal instantiation
5. C(x) ::::} ,D(x)
2, Universal instantiation
6. I(x) ::::} D(x)
3, Universal instantiation
7. B(x)
Premise of conclusion
8. I(x)
4,7 Modus pollens
9. D(x)
6,8 Modus pollens
10. ,C(x)
5,9 Modus tollens
11. B(x) ::::} , C(x)
7,10 Conditional proof
12. Vx (B(x) ::::} ,C(x))
11, Universal generalization.
Hence the conclusion is valid.
EXAMPLE 1.34
Give an indirect proof of
(, Q, P ::::} Q, P v S) ::::} S
Solution
We have to prove S. So we include (iv) ,S as a premise.
1. P v S
Premise (iii)
2. ,S
Premise (iv)
3. P
1,2, Disjunctive syllogism
4. P ::::} Q
Premise (ii)
5. Q
3,4, Modus ponens
6. ,Q
Premise (i)
7. Q /\ ,Q
5.6, Conjuction
8. F
1 8
We get a contradiction. Hence (, Q, P ::::} Q, P v S) ::::} S.
http://engineeringbooks.net