Discrete Mathematics Assignment - Units 1 to 3
Unit 1 - Relations, Closures, Induction, Number Theory
Q1. A={0,1,2,3,4}, B={0,1,2,3}
If a <= b: {(0,0),(0,1),(0,2),(0,3),(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)}
If a+b >= 3: {(0,3),(1,2),(1,3),(2,1),(2,2),(2,3),(3,0),(3,1),(3,2),(3,3),(4,0),(4,1),(4,2),(4,3)}
Q2. A={1,2,3,4}, B={x,y,z}, R={(1,x),(1,z),(3,y),(4,x),(4,z)}
Matrix: [[1,0,1],[0,0,0],[0,1,0],[1,0,1]]
Inverse: {(x,1),(z,1),(y,3),(x,4),(z,4)}
Domain={1,3,4}, Range={x,y,z}
Q3. A={1,2,3,4}, B={2,4,6,7}, xRy: x divides y
R={(1,2),(1,4),(1,6),(1,7),(2,2),(2,4),(2,6),(3,6),(4,4)}
R^-1: {(2,1),(4,1),(6,1),(7,1),(2,2),(4,2),(6,2),(6,3),(4,4)}
Matrix: [[1,1,0,0],[1,0,0,1],[1,1,1,0],[1,0,0,0]]
Q4. 1) xy perfect square -> equivalence relation
2) x+y=10 -> symmetric only
Q5. If R is equivalence, R^-1 is also equivalence.
Q6. (N, divides) is a partial order.
Q7. R={(a,a),(a,c),(c,b),(c,d),(d,b)}, S={(b,a),(c,c),(c,d),(d,a)}
RS = SR = {(b,a),(b,c),(c,b),(c,d),(d,a),(d,c)}
Matrix: [[0,0,0,0],[1,0,1,0],[0,1,0,1],[1,0,1,0]]
Q8. MR=[[1,0,1],[1,0,1],[1,0,0]], MS=[[1,1,0],[0,1,0],[0,0,1]]
RS=[[1,1,1],[1,1,1],[1,0,1]]
RS=[[1,0,0],[0,0,0],[0,0,0]]
SR=[[1,0,1],[1,0,1],[1,0,0]]
RS=[[1,1,1],[1,1,1],[1,1,0]]
RXORS=[[0,1,1],[1,1,1],[1,0,1]]
Q9. (a,b)R(c,d) if a+d=b+c -> equivalence.
Page 1
Discrete Mathematics Assignment - Units 1 to 3
Q14. 1+2+...+2^n = 2^{n+1}-1 by induction.
Q15. gcd(252,105)=21; gcd(1220,516)=4; gcd(1701,3768)=3
Unit 2 - Counting
Q16. 2^7=128 bit strings of length 7.
Q17. LLLDDD = 26^3 * 10^3 = 17,576,000.
Q18. (1) 18*325=5850 (2) 18+325=343
Q19. Start 00: 2^5=32; End 111: 2^4=16; Overlap 2^2=4; Total=44.
Q20. P(5,3)=60.
Q21. P(100,3)=970,200.
Q22. 'ABC' as block: 6! = 720.
Q23. C(10,3)*C(15,3)=54,600.
Unit 3 - Logic & Proofs
Q24. 2^{2n}-1 divisible by 3.
Q25. 9^n-2^n divisible by 7.
Q26. p->q: Converse q->p; Inverse ~p->~q; Contrapositive ~q->~p.
Q27. (a) and (c) are propositions.
Q28. Contingent.
Q29. Sum of rationals is rational.
Page 2
Discrete Mathematics Assignment - Units 1 to 3
Q30. Tautology.
Q31. sqrt(2) irrational -> 2 - sqrt(2) irrational.
Q32. p->q == ~q->~p.
Q33. If 3n+2 odd n odd.
Q34. Contingent.
Q35. Snow statement: converse, contrapositive, inverse listed.
Q36. Even x x^2 even.
Q37. Distributive, De Morgan laws.
Q38. f(n)=3 constant.
Q39. Division result 2^{32}+1, remainder 0.
Q40. Sum of squares formula proven by induction.
Page 3