COT3100.01, Fall 2002 Assigned: 11/16/2002 (post date)COT3100.01, Fall 2002 Assigned: 11/16/2002 (post date)S. Lang (Optional*) Assignment #6 (40 pts.) Due date: 11/26 by 8:45 am in class*This assignment is optional in the following sense:(1) You need to understand the materials contained in this assignment because they provide useful exercises on the last segment of the course; and(2) If you turn in the assignment within the first 15 minutes of the last class (on 11/26), your score on the assignment can be used to replace the lowest score of your earlier assignments (i.e., out of the 6 assignments including this one, the lowest score will be dropped).First, we define some terms and notations.Definition. Consider a binary relation R A B. The inverse of R, denoted R–1, is a binary relation B A such that R–1 = {(b, a) | (a, b) R}, that is, R–1 contains pairs of elements which have the reverse order as they are in relation R. (In some text R–1 is called the converse of R, denoted Rc.)Definition. Let R A A denote a binary relation. The following relations defined over A are called closures:(a) The reflexive closure of R is r(R) = R {(a, a) | a A}.(b) The symmetric closure of R is s(R) = R R–1.(c) The transitive closure of R is t(R) = R R2 R3 ..., where R2 = R R, R3 = R2 R, etc., where denotes relation composition. Thus, (a, b) t(R) (a, b) Rn, for some n 1 there exist a1, a2, …, an A, an = b, for some n 1, such that (a, a1), (a1, a2), …, (an1, an) R,i.e., there exists a direct path of n edges connecting a to b in the digraph for the relation R.It can easily be seen that the names of these closures are justified in that for any binary relation R, r(R) is reflexive, s(R) is symmetric, and t(R) is transitive. In fact, the relation r(R) is the smallest relation containing R and is also reflexive; s(R) is the smallest relation containing R and is symmetric; t(R) is the smallest relation containing R and is transitive. Also, we can define the composition of these closures, e.g., tr(R) = t(r(R)), rs(R) = r(s(R)), etc. The following figures show a binary relation R depicted by its digraph representation, and the corresponding closures (edges added due to closure are in red color):Now, answer the following questions neatly and concisely. All proofs need to be justified by using the appropriate definitions, theorems, and logical reasoning. Answer keys of assignments Rs(R)r(R)t(R)given in previous semesters provide useful sample problems and solutions: http://www.cs.ucf.edu/courses/cot3100.fall00/section1/homework/key3fa00.doc and http://www.cs.ucf.edu/courses/cot3100.spr2000/section1/homework/key3sp00.doc. 1. (12 pts.) Let A denote an arbitrary non-empty set, and R and T denote arbitrary binary relations defined over A. Determine if each of the following statements is true or false, and give a brief explanation of your answer. In the cases of a false statement, use A = {a, b, c} and appropriate relations over A for your counter-example.(a) If R T, then s(R) s(T).(b) If R is transitive and T is transitive, then R T is transitive.(c) If R = T–1, then T = R–1.(d) If R T is irreflexive, then R is irreflexive.2. (4 pts.) Let A, B, and C denote 3 sets. Prove that A (B C) = (A B) (A C). (Hint: Start with (x, y) A (B C) x A and y (B C). Eventually, show this is equivalent to(x, y) (A B) (A C).)3. (6 pts.) Given the set A = {1, 2, 3, 5, 8}, define a relation T over A such that T = {(a, b)| a A, b A, and |a b| is a prime integer}. Answer the following two questions.(a) Use a directed graph to depict the relation T defined above.(b) Determine if relation T satisfies each of the properties: reflexive, anti-symmetric, and transitive. Give a brief explanation for your answer.4. (12 pts.) Given the following laws concerning arbitrary relations R and T (and their inverses) defined over set A: (R–1)–1 = R; (R T)–1 = R–1 T–1; (R T)–1 = R–1 T–1; (R T) (R–1 T–1).Use the above laws, and other related theorems and definitions to prove each of the followingstatements for arbitrary relations R and T defined over a set A. Be sure to give reason to eachof the proof steps.(a) r(R) R = R R2.(b) s(R T) = s(R) s(T).(c) t(R) R = R t(R). 5. (6 pts.) The following directed graph depicts a binary relation R defined over the set A = {1, 2, 3, 4}. (a) Determine if R satisfies each of the following properties: reflexive, irreflexive, symmetric, and anti-symmetric. Give a brief explanation for your answer.(b) Determine each of the following sets: R2, R3, R4, and the transitive closure t(R). (Note that since the digraph has 4 vertices, t(R) = R R2 R3 R4, a finite union.)43
View Full Document
Unlocking...