<< Chapter < Page | Chapter >> Page > |
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.
Notification Switch
Would you like to follow the 'Discrete structures' conversation and receive update notifications?