0.1 Discrete structures relation  (Page 13/13)

c. The reflexive closure of a quasi order is a partial order.

d. Every finite poset has a minimal element and a maximal element

10. List the ordered pairs in the relation R from A = {0,1, 2, 3} to B = {0, 1, 2, 3, 4} where (a, b) ∈ R if and only if

a. a>b.

b. a + b = 3.

c. a divides b.

d. a - b = 0.

e. gcd( a , b ) = 1.

f. lcm( a , b ) = 6.

11. Recursively define the relation { ( a , b ) | a=2b }, where a and b are natural numbers.

12. List unary relation on {1, 2, 3}.

13. Prove that there are 2 n2 binary relations on a set of cardinality n .

14. For each of the following relations on the set {1, 2, 3, 4}, decide whether it is reflexive, symmetric, antisymmetric and/or transitive.

a. {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}

b. {(1, 3), (1, 4), (2, 3), (3, 4)}

c. {(1, 1), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 3), (3, 4)}

15. Determine whether the relation R on the set of all integers is reflexive, symmetric, antisymmetric, and/or transitive, where ( x , y ) ∈ R if and only if

a. x is divisible by y .

b. x ≠ y.

c. y = x + 2 or y = x - 2.

d. x = y ² + 1 .

16. Let A be the set of people in your town. Let R 1 be the unary relation representing the people in your town who were registered in the last election  and R 2 be the unary relation representing the people in your town who voted in the last election.  Describe the 1-tuples in each of the following relations.

a. R 1 ∪ R 2.

b. R 1 ∩ R 2.

17. Draw the directed graph that represents the relation {( a , b ), ( a , c ), ( b , c ), ( c , b ), ( c , c ), ( c , d ), ( d , a ), ( d , b )}.

18. Let R be the parent-child relation on the set of people that is, R = { ( a, b ) | a is a parent of b }.  Let S be the sibling relation on the set of people that is, R = { ( a , b ) | a and b are siblings (brothers or sisters) }.  What are S o R and R o S ?

19. Let R be a reflexive relation on a set A .  Show that R n is reflexive for all positive integers n .

20. Let R be the relation on the set { 1, 2, 3, 4} containing the ordered pairs (1, 1), (1, 2), (2, 2), (2, 4), (3, 4), and (4, 1).  Find

a. the reflexive closure of R

b. symmetric closure of R   and

c. transitive closure of R .

21. Let R be the relation { ( a, b ) | a is a (integer) multiple of b } on the set of integers.  What is the symmetric closure of R ?

22. Suppose that a binary relation R on a set A is reflexive.  Show that   R*   is reflexive, where   R* = ${}_{i=1}^n{R}^i$ .

23. Which of the following relations on {1, 2, 3, 4} are equivalence relations?  Determine the properties of an equivalence relation that the others lack.

a. {(1, 1), (2, 2), (3, 3), (4, 4)}

b. {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}

c. {(1, 1), (1, 2), (1, 4), (2, 2), (2, 4), (3, 3), (4, 1), (4, 2), (4, 4)}

24. Suppose that A is a nonempty set, and f is a function that has A as its domain.  Let R be the relation on A consisting of all ordered pairs ( x , y ) where f(x) = f(y) .

a. Show that R is an equivalence relation on A .

b. What are the equivalence classes of R ?

25. Show that propositional equivalence is an equivalence relation on the set of all compound propositions.

26. Give a description of each of the congruence classes modulo 6.

27. Which of the following collections of subsets are partitions of {1, 2, 3, 4, 5, 6}?

a. {1, 2, 3}, {3, 4}, {4, 5, 6}

b. {1, 2, 6}, {3, 5}, {4}

c. {2, 4, 6}, {1, 5}

d. {1, 4, 5}, {2, 3, 6}

28. Consider the equivalence relation on the set of integers R = { ( x, y ) | x - y is an integer}.

a. What is the equivalence class of 1 for this equivalence relation?

b. What is the equivalence class of 0.3 for this equivalence relation?

29. Which of the following are posets?

a. ( Z,  =  )

b. ( Z, ≠)

c. ( A collection of sets, ⊆).

30. Draw the Hasse diagram for the divisibility relation on the following sets

a. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

b. {1, 2, 5, 8, 16, 32}

31. Answer the following questions concerning the poset ({{1}, {2}, {3}, {4}, {1, 3}, {1, 4}, {2, 4}, {3, 4}, {1, 2, 4}, {2, 3, 4}},⊆).

a. Find the maximal elements.

b. Find the minimal elements.

c. Is there a greatest element?

d Is there a least element?

e. Find all upper bounds of {{2}, {4}}.

f. Find the least upper bound of {{2}, {4}}, if it exists.

g. Find all lower bounds of {{1, 2, 4}, {2, 3, 4}}

h. Find the greatest lower bound of {{1, 2, 4}, {2, 3, 4}}, if it exists.