CS 205 Homework 5
Spring 2021
1. Given an arbitrary relation R, suppose we compute two new relations: • R1, the reflexive closure of the transitive closure of R
• R2, the transitive closure of the reflexive closure of R Prove or disprove: R1 = R2 for all R.
2. Let A = {cat,dog,bird,rat} and R be a relation on A defined by {(x, y) : x and y have at least one letter in common}.
(a) Draw R as a directed graph.
(b) Is R reflexive, symmetric, and/or transitive?
3. Given a relation R on a set A, prove that if R is transitive, then so is R−1.
4. Suppose R and S are symmetric relations on a set A. Prove that R◦S is symmetric iff R ◦ S = S ◦ R.
5. Prove or disprove: for any set A, there exists a relation R on A such that R is both symmetric and antisymmetric.
6. Find all equivalence relations on {1, 2, 3}.
7. Showthatforn,m∈Z+,gcd(2n−1,2m−1)=2gcd(n,m)−1.
8. Suppose m,n ∈ Z+ are relatively prime. Prove that for all a,b ∈ Z, a≡b (modmn)iffa≡b (modm)anda≡b (modn).
1