COT3100 01 Fall 2002 S Lang Optional Assignment 6 40 pts Assigned 11 16 2002 post date 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 an 1 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 R r R s R t R 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 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 following statements for arbitrary relations R and T defined over a set A Be sure to give reason to each of 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 4 3 1 2
View Full Document
Unlocking...