Disclaimer: Listed here is a selection of the many possible sorts of problems. The actual test is apt to make a different selection.
1.
Let S5 be the set of all binary strings of length 5 (such as 11001).
Let E be the equivalence relation on S5 for which sEt if and only if
s and t have the same first three bits.
(For example, 11011 E 11010.)
(a) Find [10101], the equivalence class of the string 10101.
(b) How many equivalence classes are there altogether? (Support your
answer.)
(c) Let A = {4, 5, 6, 7} and let P = {{5, 7}, {4, 6}}. Then
P is a partition of A. Give the matrix (relative to numerical order
on A) of the equivalence relation R on A for which A/R = P.
2.
(a) Assume that R is a transitive relation.
Show that whenever (x, y) is in R o R, then (x, y) is also in R.
(b) Assume that Q is a relation and that Q o Q is a subset of Q.
Prove that Q is transitive.
3. Let f(n) = sqrt(4n), and let g(n) = lg 4n. Determine whether f is O(g) and whether g is O(f). (Notation: sqrt(w) is the square root of w. And lg n is the logarithm of n to the base 2.)
4.
Assume that E is an equivalence relation on a set S.
Assume that aEb.
(a) Show that [a] is a subset of [b].
(b) Show that [b] is a subset of [a].
5.
Prove by induction that for all positive integers n,
1(1!) + 2(2!) + ... + n(n!) = (n + 1)! - 1.
Click here for answers, after you have done the problems.