SOLUTIONS OF HOMEWORK 1 SPRING 03
DUE DATE: 12 FEB 2003.
Solution 1 (Exercise 39 page 16)
p / q / r / ~p / ~q / ~pΛq / qΛr / (~pΛq) Λ (qΛr) / ((~pΛq) Λ (qΛr)) Λ ~qT / T / T / F / F / F / T / F / F
T / T / F / F / F / F / F / F / F
T / F / T / F / T / F / F / F / F
T / F / F / F / T / F / F / F / F
F / T / T / T / F / T / T / T / F
F / T / F / T / F / T / F / F / F
F / F / T / T / T / F / F / F / F
F / F / F / T / T / F / F / F / F
Since all the truth values of ((~pΛq) Λ (qΛr)) Λ ~q are False,((~pΛq) Λ (qΛr)) Λ ~q is a contradiction.
Solution 2
((~pΛq) Λ (qΛr)) Λ ~q (Given)
((~pΛq) Λ(rΛq)) Λ ~q (By Commutative Law)
(~pΛq) Λ((rΛq) Λ ~q) (By Associative Law)
(~pΛq) Λ(r Λ( qΛ~q) (By Associative Law)
(~pΛq) Λ(rΛc) (By Negation Law)
(~pΛq) Λ c (By Universal Bound Law)
c (By Universal Bound Law)
Solution 3 (Exercise 48 page 16)
P / Q / R / P XOR Q / Q XOR R / (P XOR Q) XOR R / P XOR ( Q XOR R)T / T / T / F / F / T / T
T / T / F / F / T / F / F
T / F / T / T / T / F / F
T / F / F / T / F / T / T
F / T / T / T / F / F / F
F / T / F / T / T / T / T
F / F / T / F / T / T / T
F / F / F / F / F / F / F
Since the Truth values of (( p xor q) xor r) and (p xor (q xor r )) are same.
Therefore (p xor q) xor r ≡ p xor (q xor r).
Solution 4 (Exercise 32 page 28)
a) p→(q→r)) ↔((p Λ q) → r)
≡ [~ p V (q→r)] ↔ [~(pΛq) V r]
≡ [~ p V (~q V r)] ↔ [~(pΛq) V r]
≡ (~[~pV(~qVr)] V [~(pΛq) V r] )Λ ~[~(pΛq) V r] V [~p V (~q V r)])
b) p→(q→r)) ↔((p Λ q) → r)
≡ (~[~pV(~qVr)] V [~(pΛq) V r]) Λ ~[~(pΛq) V r] V [~p V (~q V r)] ) (from part a)
≡( ~([~pV(~qVr)] Λ ~ [~(pΛq) V r]) Λ (~(~[(pΛq) Λ ~ r] Λ ~ [~p V (~q V r)]))
≡ (~(~[p Λ ~(~qVr)] Λ [(pΛq) Λ ~ r]) )Λ (~(~[(pΛq) Λ ~ r] Λ [p Λ ~(~q V r)]))
≡ (~(~[p Λ (q Λ ~r)] Λ [(pΛq) Λ ~ r])) Λ( ~(~[(pΛq) Λ ~ r] Λ [p Λ (q Λ ~r)])).
Solution 5
Exercise 25 page 40
Form: p → q
q → r
Therefore p → r
Valid using hypothetical syllogism.
Exercise 27 page 40
Form: p → q
q
Therefore p
Invalid, converse error.
Exercise 28 page 40
Form: p → q
~p
Therefore ~q
Invalid, inverse error.
Exercise 29 page 40
Form: p → q
q
Therefore p
Invalid, converse error.
Exercise 30 page 40
Form: p Λ q
Therefore q
Valid using conjunctive simplification.
Exercise 31 page 40
Form: p → q
q → r
Therefore pVq → r
Valid using proof of division into cases.
Solution 6
~(~pΛq) →(~qVp) ≡ (~pΛq) V (~qVp) (Because p→q ≡ ~pVq)
≡ (qΛ~p) V (~qVp) (By Commutative Law)
≡ ~(~qVp) V (~qVp) (By De Morgan’s Law)
≡ t (By Negation Law)
Solution 7
((pΛq) →r) →(~r→(~pV~q)) ≡ (~(pΛq)Vr) →(rV(~pV~q)) (Because p→q ≡ ~pVq)
≡ ~(~(pΛq)Vr) V (rV(~pV~q)) (Because p→q ≡ ~pVq)
≡~(~(pΛq)Vr) V ((~pV~q) V r) (By Commutative Law)
≡~(~(pΛq)Vr) V (~(pΛq) V r) (By De Morgan’s Law)
≡ t (By Negation Law)
Solution 8
(p →q) →r ≡ (p V r) Λ(q→r) (Given)
L.H.S is (p →q) →r ≡ (~p V q) →r (Because (p →q) ≡(~p V q))
≡ ~(~p V q) V r (Because (p →q) ≡(~p V q))
≡ (pΛ~q) V r (By De Morgan’s Laws)
≡ (p V r) Λ (~q V r) (By Distributive Law)
≡ (p V r) Λ(q→r) (R.H.S) (Because (p →q) ≡(~p V q))
Solution 9
p →(q V r) ≡ (p → q) V (p→r) (Given)
L.H.S is p → (q V r) ≡ ~p V (q V r) (Because (p →q) ≡(~p V q))
≡ (~pV~p) V (qVr) (By Idempotent Law)
≡ ~p V (~pV(qVr)) (By Associative Law)
≡ ~pV((~pVq)Vr)) (By Associative Law)
≡ ~pV((qV~p)Vr) (By Commutative Law)
≡ ~pV(qV(~pVr)) (By Associative Law)
≡ (~pVq) V (~pVr) (By Associative Law)
≡ (p → q) V (p→r) (R.H.S) (Because (~pVq) ≡ (p→q))
Solution 10
~(p→q) ≡ ~q Λ (p V q) ( Given)
L.H.S ~(p→q) ≡ ~(~p V q) (Because (p →q) ≡(~p V q))
≡ (p Λ ~q) (By De Morgan’s Law)
≡ (~q Λ p) (By Commutative Law)
R.H.S ~q Λ (p V q) ≡ (~qΛp) V (~qΛq) (By Distributive Property)
≡ (~qΛp) V c (By Negation Law)
≡ (~qΛp) (By Identity Law)
Therefore L.H.S = R.H.S (Hence proved)