CMSC 250 Fall 2004 Homework 16 Due Never at the beginning of your discussion section You must write the solutions to the problems single sided on your own lined paper with all sheets stapled together and with all answers written in sequential order or you will lose points 1 Let R1 and R2 be the relation on 0 1 2 3 defined as follows Draw the directed graphs for R1 and R2 and indicate which relations are antisymmetric a R1 0 1 1 2 1 3 2 3 3 1 b R2 0 0 0 1 3 2 2 1 3 0 3 3 2 Let A a b c d e f g Let R be a binary relation on A with the following pairs related aRb dRe eRf gRe Write the following sets using ordered pair notation a R b The reflexive closure of R c The symmetric closure of R d The transitive closure of R 3 Redo number 3 representing each relation as a matrix 4 Redo number 3 representing each relation as a directed graph 5 Let R be a relation defined by 1 0 1 1 0 0 0 1 1 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 1 0 Write the matrices representing the reflexive and symmetric closures of R Is R asymmetric Is R antisymmetric Is R reflexive Is R irreflexive Give reasons for your answers 6 Let A 1 2 3 4 Let R be a binary relation defined on A defined by a1 Ra2 if a1 a2 Write the the relation using ordered pair notation and show that the relation is antisymmetric 7 Using the subset inclusion partial order relation give an example of two elements that are not comparable 8 Define a relation R on the set of all integers as follows x y Z xRy x y is even Is R a partial order relation Prove or give counterexample 1 9 Let A 1 2 3 4 5 6 Let R be the partial order relation defined by inclusion of subsets of A Write a chain C of maximal length contained in R 10 Let R be a partial order relation on A a b c d e f given by R a a b b c c d d e e f f a b a c a d a e a f b c b d b e b f d f e f Draw the Hasse diagram for R 11 In the following the relation R is an equivalent relation on the set A Find the distinct equivalence classes of R a X 1 0 1 and A P X R is defined on P X as follows For all sets s and t in P X s R t the sum of the elements in s equals the sum of the elements in t b A is the set of all strings of length 2 in 0 s 1 s and 2 s R is defined on A as follows For all strings s and t in A s R t the sum of the characters in s equals the sum of the characters in t 12 Let P be the set of all points in the Cartesian plane except the origin R is the relation defined as follows For all p1 and p2 in P p1 R p2 p1 and p2 lie on the same half line emanating from the origin Proof that the relation is and equivalence relation and describe the distinct equivalence classes 13 Let R be a binary relation on a set A and suppose R is symmetric and transitive Prove the following If for every x in A there is a y in A such that x R y then R is an equivalence relation 14 For each of the following either prove that it is a partial order relation or indicate why it is not a partial order relation a Define a relation R on the set Z of all integers as follows For all m n Z m R n every prime factor of m is a prime factor of n b Define a relation R on the set R of all real numbers as follows For all x y R x R y x2 y 2 15 Let A a b c d and let R be the relation R a a b b c c d d c b a d b a b d c d c a Is R a total order on A justify your answer 2
View Full Document
Unlocking...