CSE2133 - Discrete Mathematics¶

Sets and Functions¶

Q2(a): Show that if A, B and C are sets, then \(\overline{A\cap B\cap C}=\bar A\cup\bar B\cup\bar C\): (i) by showing each side is a subset of the other side; (ii) using a membership table.
Q2(d): Find the domain and range of these functions: (i) the function that assigns to each bit string the number of ones in the string minus the number of zeros; (ii) the function that assigns to each bit string twice the number of zeros; (iii) the function that assigns the number of bits left over when a bit string is split into bytes (which are blocks of 8 bits); (iv) the function that assigns to each positive integer the largest perfect square not exceeding this integer.
Q2(e): Suppose that Hilbert's Grand Hotel is fully occupied on the day the hotel expands to a second building which also contains a countably infinite number of rooms. Show that the current guests can be spread out to fill every room of the two buildings of the hotel.

Q2(a): Show that if A, B and C are sets, then \(\overline{A\cap B\cap C}=\bar A\cup\bar B\cup\bar C\): (i) by showing each side is a subset of the other side; (ii) using a membership table.
Q2(d) [4]: Find the domain and range of these functions: (i) the function that assigns to each bit string the number of ones in the string minus the number of zeros; (ii) the function that assigns to each bit string twice the number of zeros; (iii) the function that assigns the number of bits left over when a bit string is split into bytes; (iv) the function that assigns to each positive integer the largest perfect square not exceeding this integer.
Q2(e) [2]: Suppose that Hilbert's Grand Hotel is fully occupied on the day the hotel expands to a second building which also contains a countably infinite number of rooms. Show that the current guests can be spread out to fill every room of the two buildings of the hotel.

Q2(a) [6]: Let \(A=\{a,b,c\}\), \(B=\{1,2,3\}\), \(C=\{w,x,y,z\}\), \(D=\{4,5,6\}\) and the functions \(f:A\to B\), \(g:B\to C\), and \(h:C\to D\) be determined as \(f=\{(a,2),(b,1),(c,2)\}\), \(g=\{(1,y),(2,x),(3,w)\}\) and \(h=\{(x,4),(y,6),(z,4),(w,5)\}\). (i) Determine if each function is onto, one-to-one. Explain. (ii) Find the composition function \(h\circ g\circ f\).
Q2(b) [4]: Prove that (i) \((A\cup B)\cap(A\cup B')=A\); (ii) \((A\cup B)\setminus(A\cap B)=(A\setminus B)\cup(B\setminus A)\).

Q2(a): Define Set, Power Set and Proper Set. Using membership table show that \(\overline{A\cup(B\cap C)}=(\bar C\cup\bar B)\cap\bar A\). Assume that A, B and C are sets.
Q2(b): Suppose that \(A=\{2,4,6\}\), \(B=\{2,6\}\), \(C=\{4,6\}\) and \(D=\{4,6,8\}\). Determine which of these sets are subsets of other three sets.
Q2(c): Determine whether each of the following pairs of sets is equal: (i) \(\{1,3,3,3,5,5,5,5,5\}\) and \(\{5,3,1\}\); (ii) \(\{\{1\}\}\) and \(\{1,\{1\}\}\).
Q3(b): Let f and g be the functions from the set of integers to the set of integers defined by \(f(x)=2x+3\) and \(g(x)=3x+2\). What is the composition of f and g? What is the composition of g and f?

Q2(a) [6]: Let \(A=\{a,b,c\}\), \(B=\{1,2,3\}\), \(C=\{w,x,y,z\}\), \(D=\{4,5,6\}\) and the functions \(f:A\to B\), \(g:B\to C\), and \(h:C\to D\) are determined as \(f=\{(a,2),(b,1),(c,2)\}\), \(g=\{(1,y),(2,x),(3,w)\}\) and \(h=\{(x,4),(y,6),(z,4),(w,5)\}\). Find the composition function \(h\circ g\circ f\).

Q3(a) [5]: Define Set, Power Set and Proper Set. Using membership table show that \(\overline{A\cup(B\cap C)}=(\bar C\cup\bar B)\cap\bar A\). Assume that A, B, C are sets.
Q5(a) [6]: Let \(A=\{a,b,c\}\), \(B=\{1,2,3\}\), \(C=\{w,x,y,z\}\), \(D=\{4,5,6\}\) and the functions \(f:A\to B\), \(g:B\to C\), and \(h:C\to D\) be determined as \(f=\{(a,2),(b,1),(c,2)\}\), \(g=\{(1,y),(2,x),(3,w)\}\) and \(h=\{(x,4),(y,6),(z,4),(w,5)\}\). (i) Determine if each function is onto, one-to-one. Explain. (ii) Find the composition function \(h\circ g\circ f\).
Q5(b) [4]: Let \(A=\{1,2,3\}\), \(B=\{a,b,c\}\), \(C=\{x,y,z\}\). Consider the relation R from A to B and S from B to C: \(R=\{(1,b),(2,a),(2,c),(3,b)\}\); \(S=\{(a,y),(c,z),(c,y),(b,x)\}\). Find (i) the composition relation \(R\circ S\); (ii) the matrices \(M_R\), \(M_S\), \(M_{R\circ S}\).

Q3(a) [2+4]: Define Set, Power Set and Proper Set. Suppose that \(U=\{0,1,2,3,4,5,6,7,8,9,10\}\), \(A=\{1,2,3,4,5\}\) and \(B=\{4,5,6,7,8\}\). Find (i) \(A\cup B\); (ii) \(A\cap B\); (iii) Complement of B; (iv) \(A-B\).
Q3(b) [4]: What is the Cartesian product \(A\times B\times C\), where \(A=\{2,4\}\), \(B=\{3,5\}\), and \(C=\{x,y,z\}\)?
Q3(c) [4]: Let f and g be the functions from the set of integers to the set of integers defined by \(f(x)=2x+3\) and \(g(x)=3x+2\). What is composition of f and g and what is the composition of g and f?