Discrete

Problem 4 (25 points) 1. (12 points) Consider the relations below. For each one explain whether the relation is reflexive, symmetric and transitive a) (3 pts) Let A be the set of all strings of length 4 consisting of the digits 0, 1, 2. Let the relation R consist of pairs of strings (s, t) in A such that the sum of the digits in s equals the sum of the digits in t. b) (3 pts) Let B be the set of all binary 0/1 strings of length 4. Let the relation R2 consist of pairs of strings (s, t) in B such that endpoints of s are the same as the endpoints of t c) (3 pts) R-((x, y), where x and y are real numbers such that x+y d) (3 pts) R -[(m, n), where m and n are integers such that there is a prime number p that divides both m 4). and n ((0, 1), (0, 2), (I, 1), (1, 3) (2, 2), (3, 0)), 2. (3 pts) Find the transitive closure of R 3. (10 points) Consider the two relations R - ((a, b: b-a+3) and S- (a, b): b-a+3) defined on the set of positive integers a) (2 pts) List the first 5 pairs of each relation. b) (3 pts) List the first 5 pairs of RS and SR c) (5 pts) Find an algebraic characterization of the pairs (a, b) belonging to each of RS and SR