Scribd
Upload
17 views13 pages

Binary Relations on Set {0,1}

The document contains 48 questions about binary relations and partially ordered sets. It defines various relations on sets and asks questions about their properties, such as whether they are reflexive, symmetric, transitive, etc. It also involves constructing relations, their powers, inverses and compositions. Questions also involve representing relations as matrices and directed graphs. There are questions about partially ordered sets that involve drawing Hasse diagrams and finding maximal/minimal elements, joins, meets and topological sorts.

Uploaded by

Jose D. Elvena Jr.
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
17 views13 pages

Binary Relations on Set {0,1}

The document contains 48 questions about binary relations and partially ordered sets. It defines various relations on sets and asks questions about their properties, such as whether they are reflexive, symmetric, transitive, etc. It also involves constructing relations, their powers, inverses and compositions. Questions also involve representing relations as matrices and directed graphs. There are questions about partially ordered sets that involve drawing Hasse diagrams and finding maximal/minimal elements, joins, meets and topological sorts.

Uploaded by

Jose D. Elvena Jr.
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd

Chapter 8

1. List all the binary relations on the set 01.


Ans: There are 16 binary relations:
 (00) (01) (10)
(11) (00)(01) (00)(10) (00)(11)
(01)(10) (01)(11) (10)(11) (00)(01)(10)
(00)(01)(11) (00)(10)(11) (01)(10)(11) (00)(01)(10)(11)

2. List the reflexive relations on the set 01.


Ans: 8, 13, 14, 16.

3. List the irreflexive relations on the set 01.


Ans: 1, 3, 4, 9.

4. List the symmetric relations on the set 01.


Ans: 1, 2, 5, 8, 9, 12, 15, 16.

5. List the transitive relations on the set 01.


Ans: 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 16.

6. List the antisymmetric relations on the set 01.


Ans: 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14.

7. List the asymmetric relations on the set 01.


Ans: 1, 3, 4.

8. List the relations on the set 01 that are reflexive and symmetric.
Ans: 8, 16.

9. List the relations on the set 01 that are neither reflexive nor irreflexive.
Ans: 2, 5, 6, 7, 10, 11, 12, 15.

Use the following to answer questions 10-23:

In the questions below determine whether the binary relation is: (1) reflexive, (2) symmetric,
(3) antisymmetric, (4) transitive.

10. The relation R on 123… where aRb means a  b.


Ans: 1, 3, 4.

11. The relation R on wxyz where R  (ww)(wx)(xw)(xx)(xz)(yy)(zy)(zz).


Ans: 1.

Page 104
12. The relation R on Z where aRb means  a  b   1.
Ans: 1, 2.

13. The relation R on Z where aRb means a2  b2.


Ans: 1, 2, 4.

14. The relation R on abc where R  (aa)(bb)(cc)(ab)(ac)(cb).


Ans: 1, 3, 4.

15. The relation R on A  xyz where R  (xx)(yz)(zy).


Ans: 2.

16. The relation R on Z where aRb means a  b.


Ans: 2.

17. The relation R on Z where aRb means that the units digit of a is equal to the units digit of
b.
Ans: 1, 2, 4.

18. The relation R on N where aRb means that a has the same number of digits as b.
Ans: 1, 2, 4.

19. The relation R on the set of all subsets of 1234 where SRT means S  T.
Ans: 1, 3, 4.

20. The relation R on the set of all people where aRb means that a is at least as tall as b.
Ans: 1, 4.

21. The relation R on the set of all people where aRb means that a is younger than b.
Ans: 3, 4

22. The relation R on the set (ab)  ab  Z where (ab)R(cd) means a  c or b  d.
Ans: 1, 2.

23. The relation R on R where aRb means a  b  Z.


Ans: 1, 2, 4.

Page 105
24. A company makes four kinds of products. Each product has a size code, a weight code,
and a shape code. The following table shows these codes:
Size Code Weight Code Shape Code
1 42 27 42
2 27 38 13
3 13 12 27
4 42 38 38
Find which of the three codes is a primary key. If none of the three codes is a primary
key, explain why.
Ans: Shape code.

25. If X (Fran Williams, 617885197, MTH 202, 248B West), find the projections P13(X)
and P124(X).
Ans: P13(X)  (FranWilliamsMTH 202) P124(X) 
(FranWilliams617885197248BWest).

Use the following to answer questions 26-31:

In the questions below suppose R and S are relations on abcd, where R 


(ab)(ad)(bc)(cc)(da) and S  (ac)(bd)(da).

26. Construct R2.


Ans: (aa)(ac)(bc)(cc)(db)(dd).

27. Construct R3.


Ans: (ab)(ac)(ad)(bc)(cc)(da)(dc).

28. Construct S2.


Ans: (ba)(dc).

29. Construct S3.


Ans: (bc).

30. Construct R  S.
Ans: (ac)(ba)(db)(dd).

31. Construct S  R.
Ans: (aa)(ad)(dc).

Page 106
Use the following to answer questions 32-41:

In the questions below find the matrix that represents the given relation. Use elements in the
order given to determine rows and columns of the matrix.

32. R on 1234 where aRb means  a  b   1.

Ans: .

33. R on wxyz where R  (ww)(wx)(xw)(xx)(xz)(yy)(zy)(zz).

Ans: .

34. R on 21012 where aRb means a2  b2.

Ans: .

35. R on 1234612 where aRb means a  b.

Ans: .

Page 107
36. R on 124816 where aRb means a  b.
Ans:

37. R on 124816 where aRb means a  b.

Ans: .

38. R2, where R is the relation on on 1234 such that aRb means  a  b   1.

Ans: .

39. R2, where R is the relation on wxyz such that R 


(ww)(wx)(xw)(xx)(xz)(yy)(zy)(zz).

Ans: .

40. R1, where R is the relation on 1234 such that aRb means  a  b   1.
Ans:

Page 108
41. , where R is the relation on wxyz such that R 
(ww)(wx)(xw)(xx)(xz)(yy)(zy)(zz).

Ans: .

42. If , determine if R is: (a) reflexive (b) symmetric (c) antisymmetric

(d) transitive.
Ans: (a) Yes. (b) No. (c) No. (d) No.

43. If , determine if R is: (a) reflexive (b) symmetric (c) antisymmetric

(d) transitive.
Ans: (a) Yes. (b) No. (c) Yes. (d) Yes.

44. Draw the directed graph for the relation defined by the matrix ,

Ans:

Page 109
45. Draw the directed graph for the relation defined by the matrix .

Ans:

46. Draw the Hasse diagram for the relation R on A  2346101216 where aRb means a
 b.

Ans:

47. Draw the Hasse diagram for the relation R on A  2345681040 where aRb means a
 b.

Ans:

Page 110
48. Suppose A  23691012141820 and R is the partial order relation defined on A
where xRy means x is a divisor of y.
(a) Draw the Hasse diagram for R.
(b) Find all maximal elements.
(c) Find all minimal elements.
(d) Find lub(29).
(e) Find lub(310).
(f) Find glb(1410).

Ans: (a) (b) 12141820. (c) 23. (d) 18.


(e) Does not exist. (f) 2.

49. The diagram shown is the Hasse diagram for a partially ordered set. Referring to this
diagram:
(a) List the maximal elements
(b) List the minimal elements
(c) Find all upper bounds for fg
(d) Find all lower bounds for df
(e) Find lub(gjm)
(f) Find glb(de)
(g) Find the greatest element
(h) Find the least element
(i) Use a topological sort to order the elements of the poset represented by this Hasse
diagram.

Ans: (a) ab. (b) lm. (c) b. (d) hijm. (e) g. (f) None. (g) None. (h) None.
(i) For example: mkijlhgfecdba.

Page 111
50. Find the transitive closure of R if MR is .

Ans: . .

51. Find the transitive closure of R if MR is .

Ans: .

52. If R  (12)(14)(23)(31)(42), find the reflexive closure of R.


Ans: (11)(12)(14)(22)(23)(31)(33)(42)(44).

53. If R  (12)(14)(23)(31)(42), find the symmetric closure of R.


Ans: (12)(13)(14)(21)(23)(24)(31)(32)(41)(42).

54. If R  (xy)  x and y are bit strings containing the same number of 0s, find the
equivalence classes of
(a) 1.
(b) 00.
(c) 101.
Ans: (a) All strings that contain no 0s (including the empty string). (b) All strings with
exactly two 0s. (c) All strings with exactly one 0.

55. Find the smallest equivalence relation on 123 that contains (12) and (23).
Ans: (11)(12)(13)(21)(22)(23)(31)(32)(33).

56. Find the smallest partial order relation on 123 that contains (11), (32), (13).
Ans: (11)(22)(33)(32)(13)(12).

57. What is the covering relation of the partial ordering on the set
1234681224?
Ans: (12)(13)(24)(26)(36)(48)(412)(612)(824)(1224).

Page 112
58. What is the covering relation of the partial ordering (ab)  a divides b on the set
24681012?
Ans: (24)(26)(210)(48)(412)(612).

59. Find the join of the 3-ary relation

and the 4-ary relation

with respect to the last two fields of the first relation and the first two fields of the
second relation.
Ans:

60. Find the transitive closure of R on abcd where R 


(aa)(ba)(bc)(ca)(cc)(cd)(da)(dc).
Ans: (aa)(ba)(bc)(bd)(ca)(cc)(cd)(da)(dc)(dd).

61. Which of the following are partitions of 123…10?


(a) 2468, 1359, 710.
(b) 1248, 25710, 369.
(c) 3810, 1259, 478.
(d) 12…10.
(e) 12…10.
Ans: a, d, e.

Page 113
62. Suppose R is the relation on N where aRb means that a ends in the same digit in which b
ends. Determine whether R is an equivalence relation on N.
Ans: Yes.

63. Suppose the relation R is defined on the set Z where aRb means that ab  0. Determine
whether R is an equivalence relation on Z.
Ans: No (not reflexive, not transitive).

64. Suppose A is the set composed of all ordered pairs of positive integers. Let R be the
relation defined on A where (ab)R(cd) means that a  d  b  c.
(a) Prove that R is an equivalence relation.
(b) Find [(24)].
Ans: (a) Reflexive: a  b  b  a; Symmetric: if a  d  b  c, then c  b  d  a;
Transitive: if a  d  b  c and c  f  d  e, then a  d  (d  e)  (b  c)  (c  f),
therefore a  e  b  f, or a  f  b  e. (b) [(24)]  (ab)  b  a  2.

65. Suppose that R and S are equivalence relations on a set A. Prove that the relation R  S is
also an equivalence relation on A.
Ans: Reflexive: for all a  A, aRa and aSa; hence for all a  A, a(R  S)a. Symmetric:
suppose a(R  S)b; then aRb and aSb; by symmetry of R and S, bRa and bSa;
therefore b(R  S)a. Transitive: suppose a(R  S)b and b(R  S)c; then aRb, aSb,
bRc, and bSc; by transitivity of R and S, aRc and aSc; therefore a(R  S)c.

66. Let R be the relation on A  12345 where R 


(11)(13)(14)(22)(31)(33)(34)(41)
(43)(44)(55) Write the matrix for R.

Ans: .

Page 114
67. Let R be the relation on A  12345 where R 
(11)(13)(14)(22)(31)(33)(34)(41)
(43)(44)(55) Draw the directed graph for R.

Ans:

68. Let R be the relation on A  12345 where R 


(11)(13)(14)(22)(31)(33)(34)(41)
(43)(44)(55) Find the equivalence classes for the partition of A given by R.
Ans: 13425.

Use the following to answer questions 69-71:

In the questions below give an example or else prove that there are none.

69. A relation on abc that is reflexive and transitive, but not antisymmetric.
Ans: (aa)(bb)(cc)(ab)(ba).

70. A relation on 12 that is symmetric and transitive, but not reflexive.
Ans: (11).

71. A relation on 123 that is reflexive and transitive, but not symmetric.
Ans: (11)(22)(33)(12).

72. Suppose  A   n. Find the number of binary relations on A.


Ans: .

73. Suppose  A   n. Find the number of symmetric binary relations on A.


Ans: 2n(n  1)2.

Page 115
74. Suppose  A   n. Find the number of reflexive, symmetric binary relations on A.
Ans: 2n(n  1)2.

Page 116

Common questions

Powered by AI

A relation is an equivalence relation if it is reflexive, symmetric, and transitive. Reflexivity means every element is related to itself, symmetry means if a is related to b, b is related to a, and transitivity means if a is related to b and b is related to c, then a is related to c .

The formula for the number of symmetric binary relations on a set with 'n' elements is 2^(n(n+1)/2). This is because in an n x n matrix representation of relations, only the upper triangle, including the diagonal, needs to be considered for symmetry, which contains n(n+1)/2 elements .

There are 16 binary relations on the set {0,1}. These relations are: ∅, {(0,0)}, {(0,1)}, {(1,0)}, {(1,1)}, {(0,0),(0,1)}, {(0,0),(1,0)}, {(0,0),(1,1)}, {(0,1),(1,0)}, {(0,1),(1,1)}, {(1,0),(1,1)}, {(0,0),(0,1),(1,0)}, {(0,0),(0,1),(1,1)}, {(0,0),(1,0),(1,1)}, {(0,1),(1,0),(1,1)}, and {(0,0),(0,1),(1,0),(1,1)} .

A binary relation is transitive if whenever aRb and bRc, then aRc. For the set {0,1}, the transitive relations are ∅, {(0,0)}, {(0,1)}, {(1,0)}, {(1,1)}, {(0,0),(0,1)}, {(0,0),(1,0)}, {(0,0),(1,1)}, {(0,1),(1,1)}, {(1,0),(1,1)}, {(0,0),(0,1),(1,0)}, {(0,0),(1,0),(1,1)}, and {(0,0),(0,1),(1,0),(1,1)} .

The transitive closure of R is {(a, a), (b, a), (b, c), (b, d), (c, a), (c, c), (c, d), (d, a), (d, c), (d, d)}. The transitive closure adds any direct connections through intermediary elements. For example, b connects to c and c connects to d, so b must connect to d. Similarly, by extending pathways, the closures (b, d) and (d, d) are included .

The relation is reflexive as any number a ends with the same digit as itself, symmetric as if a ends in the same digit as b, b ends in the same digit as a, and transitive as if a ends in the same digit as b and b ends in the same digit as c, then a ends in the same digit as c .

A Hasse diagram is a graphical representation of a partially ordered set, demonstrating only the cover relationships. For the set {2, 3, 4, 6, 10, 12} with a division relation, a Hasse diagram omits implied transitive relations and shows direct division links, omitting elements like (2, 6), which can be inferred through (2, 4) and (4, 6).

The smallest equivalence relation containing (1,2) and (2,3) is {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}. To satisfy reflexivity, add (1,1), (2,2), and (3,3). For symmetry, include (2,1) and (3,2). To ensure transitivity, include (1,3) and (3,1), completing the requirements of an equivalence relation .

The shape code is the primary key. A primary key is a field in a table that uniquely identifies each row/record in that table. In the provided list of codes, only the shape codes do not have any duplicates, uniquely identifying each product .

The relation R on Z, where aRb means |a - b| ≤ 1, is reflexive because for any integer a, |a - a| = 0 ≤ 1, so aRa holds. It is symmetric because if |a - b| ≤ 1, then |b - a| is also ≤ 1, which implies bRa holds whenever aRb does .

You might also like