Prove: [ P -> Q AND R -> S AND (P OR R) ] -> (Q OR S)
-> NOT, ---
1. P -> Q ___ hypothesis 2. R -> S ___ hypothesis 3. P OR
R ___ hypothesis 4. ~P OR Q ___ implication from hyp 1. 5. ~R OR S
___ implication from hyp 2 6. ~P OR Q OR S ___ addition to 4. 7. ~R
OR Q OR S ___ addition to 5. 8. Let T == (Q OR S) ___ substitution
9. (~P OR T) AND (~R OR T) ___ Conjunction 6,7 10. T OR (~P AND ~R)
___ Distribution from 9 11. T OR ~(P OR R) ___ De Morgan's theorem
12. Let M == (P OR R) ___ substitution
13. (T OR ~M) AND M ___ conjunction 11, hyp 3 From there, you
can use distribution to get (T AND M) OR (~M AND M). The
contradiction goes away leaving you with T AND M, which can
simplify to T.