MATH 11: Introduction to Discrete Structures Homework 2 Spring 2024
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Spring 2024
MATH 11: Introduction to Discrete Structures
Homework 2
Problem 1. (20 points) Consider the set A = {a,b,c, d}, and relation
R = {(a, a), (a,b), (a,c), (b, d), (d, a), (b,c), (c,b), (b,b), (d, d)}.
(a) (5 points) Draw the directed graph representing R.
(b) (5 points) Find the reflexive closure of R.
(c) (5 points) Find the symmetric closure of R.
(d) (5 points) Find the transitive closure of R.
Problem 2. (10 points) Recall that a relation is called antisymmetric if for all x,y ∈ A, if (x,y) ∈ R and (y,x) ∈ R, thenx = y.
Consider the set A = {a,b,c}, and the relation R = {(a, a), (a,b), (a,c), (b,c), (c,b)}. Explain why R does not have an antisymmetric closure.
Problem 3. (25 points) Given the set A = {1,2,3}, define a relation R ⊆ A × A that satisfies the required properties. You can either explicitly list the elements in R or draw the directed graph representing it.
(a) (5 points) R is symmetric and reflexive, but not transitive.
(b) (5 points) R is transitive and reflexive, but not symmetric.
(c) (5 points) R is transitive but not reflexive and not symmetric.
(d) (5 points) R is transitive, reflexive and symmetric.
(e) (5 points) R is not transitive, not reflexive and not symmetric.
Problem 4. (15 points) Consider the set A = {0,1,2,3,4,5,6,7,8,9} of residues modulo 10. Each relation on A below possesses the properties of being transitive, reflexive, and symmetric. Determine the corresponding partition of A into equivalence classes for each relation.
Example. The relation R is defined as follows: aRb if and only if a = b (mod 10). This relation consists of pairs of elements {(0,0), (1,1), . . . , (9,9)}, indicating that each element is equivalent only to itself. The corresponding partition of A is a disjoint union of ten one-element sets:
A = {0} ⊔ {1} ⊔ {2} ⊔ {3} ⊔ {4} ⊔ {5} ⊔ {6} ⊔ {7} ⊔ {8} ⊔ {9}.
(a) (5 points) aRb if and only if a = b (mod 5).
(b) (5 points) aRb if and only if a = b (mod 2).
(c) (5 points) aRb if and only if a = b (mod 3).
2024-04-29