356
Relations, Functions, and Matrices
73. Binary relations on a set S are ordered pairs of elements of S. More generally, an n-ary relation on a set S
is a set of ordered n-tuples of elements of S. Decide which of the given items satisfy the relation.
a. r a unary relation on Z, x [ r 4 x is a perfect square
25, 39, 49, 62
b. r a ternary relation on N, (x, y, z) [ r 4 x
2
+ y
2
= z
2
(1, 1, 2), (3, 4, 5), (0, 5, 5), (8, 6, 10)
c. r a 4-ary relation on Z, (x, y, z, w) [ r 4 y = 0 x 0 and w ≥ x + z
2
(−4, 4, 2, 0), (5, 5, 1, 5), (6, −6, 6, 45), (−6, 6, 0, −2)
74. A ternary relation r is defined on the set S = (2, 4, 6, 8) by (x, y, z) [ r 4 x + y = z. List the 3-tuples
that belong to r.
75. If x is a real number, x ∙ 0, then a number y such that x # y = 1 is called the multiplicative inverse of
x. Given positive integers x and n, a positive integer y such that x # y ≡ 1 (mod n) is called the modular
multiplicative inverse of x modulo n. But
x # y ≡ 1 (mod n)
4 x # y − 1 = kn where k is an integer
4 xy − kn = 1
4 1 is a linear combination of x and n
4 gcd (x, n) = 1
4 x and n are relatively prime
Thus, if x and n are not relatively prime, the modular inverse of x does not exist. If they are relatively
prime, the modular inverse of x is the positive coefficient of x in the linear combination of x and n that
equals 1.
Use the Euclidean algorithm to find the modular multiplicative inverse of 21 modulo 25 (note that 21
and 25 are relatively prime).
76. Use the Euclidean algorithm to find the modular multiplicative inverse of 68 modulo 15 (see Exercise 75).
example 16
Ernie and his brothers run a woodworking shop in the hills of New Hampshire
that manufactures rocking chairs with padded cushion seats. The manufacturing
process can be broken down into a number of tasks, some of which have certain
other tasks as prerequisites. The following table shows the manufacturing tasks for
a rocking chair, the prerequisite tasks, and the number of hours required to perform
each task.
S e c t I o n 5 . 2 toPologiCal soRting
If r is a partial ordering on a set S, then some elements of S are predecessors of
other elements. If S is a set of tasks that are to be done, then the idea of x as a predecessor of y can be interpreted literally to mean that task x must be done before
task y. Thus partial orderings and Hasse diagrams are natural ways to represent
problems in task scheduling.
Relations, Functions, and Matrices
73. Binary relations on a set S are ordered pairs of elements of S. More generally, an n-ary relation on a set S
is a set of ordered n-tuples of elements of S. Decide which of the given items satisfy the relation.
a. r a unary relation on Z, x [ r 4 x is a perfect square
25, 39, 49, 62
b. r a ternary relation on N, (x, y, z) [ r 4 x
2
+ y
2
= z
2
(1, 1, 2), (3, 4, 5), (0, 5, 5), (8, 6, 10)
c. r a 4-ary relation on Z, (x, y, z, w) [ r 4 y = 0 x 0 and w ≥ x + z
2
(−4, 4, 2, 0), (5, 5, 1, 5), (6, −6, 6, 45), (−6, 6, 0, −2)
74. A ternary relation r is defined on the set S = (2, 4, 6, 8) by (x, y, z) [ r 4 x + y = z. List the 3-tuples
that belong to r.
75. If x is a real number, x ∙ 0, then a number y such that x # y = 1 is called the multiplicative inverse of
x. Given positive integers x and n, a positive integer y such that x # y ≡ 1 (mod n) is called the modular
multiplicative inverse of x modulo n. But
x # y ≡ 1 (mod n)
4 x # y − 1 = kn where k is an integer
4 xy − kn = 1
4 1 is a linear combination of x and n
4 gcd (x, n) = 1
4 x and n are relatively prime
Thus, if x and n are not relatively prime, the modular inverse of x does not exist. If they are relatively
prime, the modular inverse of x is the positive coefficient of x in the linear combination of x and n that
equals 1.
Use the Euclidean algorithm to find the modular multiplicative inverse of 21 modulo 25 (note that 21
and 25 are relatively prime).
76. Use the Euclidean algorithm to find the modular multiplicative inverse of 68 modulo 15 (see Exercise 75).
example 16
Ernie and his brothers run a woodworking shop in the hills of New Hampshire
that manufactures rocking chairs with padded cushion seats. The manufacturing
process can be broken down into a number of tasks, some of which have certain
other tasks as prerequisites. The following table shows the manufacturing tasks for
a rocking chair, the prerequisite tasks, and the number of hours required to perform
each task.
S e c t I o n 5 . 2 toPologiCal soRting
If r is a partial ordering on a set S, then some elements of S are predecessors of
other elements. If S is a set of tasks that are to be done, then the idea of x as a predecessor of y can be interpreted literally to mean that task x must be done before
task y. Thus partial orderings and Hasse diagrams are natural ways to represent
problems in task scheduling.