Discrete Mathematics教学习题（华南理工）Tutorial09-Answer.pdfVIP

Discrete Mathematics I (Semester 2, 2013-2014) Tutorial 09 Refer to Chapter 5.6 Date: May-2014 1. Determine whether the following relations are partial order: a) “a is taller than b” on the set of all people in the world b) “a=b or a is an ancestor of b” on the set of all people in the world c) (R, =) d) (Z, ≠) e) 1 1 1 f) 1 1 1     1 1 0  0 1 0  0 0 1  0 0 1      g) h) Answer: a) No b) Yes c) Yes d) No e) No f) Yes g) No h) No 2. Let (S, R) be a poset. Show that (S, R-1) is also a poset. (S, R-1) is called the dual of (S, R). Answer: As R is reflexive: , we have , ∀a ∈ S ( , a)a ∈ R ( ,∴a)a ∈ R − 1 Discrete Mathematics I – Tutorial 9 1 Hence, R − 1 is reflexive. As R is antisymmetric: For a∀b, ∈ S If and then a=b ( ,a)b ∈ R ( , b)a ∈ R Give − 1 and − 1 , show b=a ( , b)a ∈ R ( , )a b ∈ R − 1 implies ( , b)a ∈ R ( ,a)b ∈ R − 1 implies ( , )a b ∈ R ( , b)a ∈ R Therefore, a=b Hence: R − 1 is antisymmetric. As R is transitive: For a b∀,c , ∈ S Ifa b R and t