Discrete Mathematics

1. (a) Let S denote the set of all binary strings of length 8. Define a binary relation ρ on S as follows:
   xρy ⇔ (x and y start and end with the same bit (0 or 1)).
   Argue that ρ is an equivalence relation. Into how many equivalence classes does ρ partition S?
   (b) Let ρ be a binary relation defined on a set S. The inverse of ρ is denoted by ρ−1 and is defined as: x ρ−1 y ⇔ y ρ x. Show that ρ ∩ ρ−1 is an equivalence relation, if ρ is reflexive and transitive.
2. Let ρ be a binary relation on a set S. For A ⊆ S, define
   #A = {x | x ∈ S ∧ (∀y)(y ∈ A ⇒ x ρ y)}
   A# = {x | x ∈ S ∧ (∀y)(y ∈ A ⇒ y ρ x)}
   (a) Prove that if ρ is symmetric, then #A = A#.
   (b) Let A ⊆ B ⊆ S. Argue that #B ⊆ #A and B# ⊆ A#.
3. (a) Let f : S → T and g : T → U denote two bijections. Argue that (g ◦ f)−1 = f−1 ◦ g−1.
   (b) Let f : S → T denote a function. If there exists a function g : T → S, such that g ◦ f = iS, then g is said to be a left inverse of f. Argue that a function f has a left inverse if and only if it is injective.
4. Let f : S → T denote a function. Let A and B denote two subsets of S.
   (a) Argue that f(A ∩ B) ⊆ f(A) ∩ f(B).
   (b) Show that f(A ∩ B) = f(A) ∩ f(B), if and only if f is an injective function.
5. (a) Consider the function A : N × N → N defined below:
   A(0,y) = 1, for all y ∈ N
   A(1,0) = 2
   A(x,0) = x + 2,for all x ≥ 2
   A(x + 1,y + 1) = A(A(x,y + 1),y),for all x,y ∈ N.
   Derive a closed form expression for A(x,1), x ≥ 1.

(b) In a programming class of 7 students, the instructor wants each student to modify the program from a previous assignment; however, no student should work on his or her own assignment. In how many ways can the instructor assign programs to the students?

Sample Solution