Discrete Structures Problems

week11.pdf

Home >Mathematics homework help >Discrete Structures Problems

A. Doerr

Week 11 An Introduction to the Concept of Relations Think of your family tree. It consists of your brothers, sisters, cousins, second cousins, aunts, uncles, parents, grandparents, great grandparents etc. On this set of relatives there is defined a relation (ship), that is, person a appears above person b in your family tree if and only if person a is an ancestor of person b. Think of an ancestor, say your great grandmother, and picture your family tree diagram with her listed at the top of the page and all her descendants listed below. This is an example of a “mathematical” diagram or graph called a tree or a partial ordering diagram. The ordering is called partial because, for example, you and your siblings and your cousins are all on the same level. Note there is a direction in this graph, namely from the top down so this is a directed graph. Another mental image. Think of the administrative structure of a business, from the CEO at the top to the next layer of VP’s to the Managers etc. Again, this is a partial ordering under the relation; person appears above person b if and only if person a is the boss of person b. Note there is a direction in this graph, namely from the top down so this is a directed graph. A third image. Think of all the major field courses you need to take for your degree. Certainly some of them are prerequisites of others. Draw a”tree”; here it might be more readable to draw the tree from the bottom to the top. That is, course x appears below course y in this list of courses tree if and only if course x is a prerequisite of course y. Each of the above are graphs or models of different situations. But, on reflection we can visualize similarities in the graphs of these diverse situations. In the next several sections we would like to learn how to describe the above and other situations mathematically. One of the key notations we will use in the next several weeks is that of the Cartesian product of two sets. Let’s recall the definition of this concept before we proceed. Definition: Let A and B be any two sets the Cartesian product of A and B, denoted A X B (read as A cross B), is the set of all ordered pairs (a, b) where a takes on all elements from the set a and b takes on all elements from the set B. In notation:  A X B = (a,b) a A , b B  Some comments:

1. If A = {1, 2} and B = {a, b, c} then A X B = {(1, a), (2,a), (1, b), 2, b), (1, c), 2, c)} and |A X B | = |A| x |B| = 2x3 = 6

2. In general, if |A| = n and |B| = m the |A X B| = nm 3. R X R is the “algebraic” description of the xy-plane, and R X R is also

written as R2 which is read as R two. Of course Before you begin to read the following, think again about the concepts of functions and that of graphs of functions. Let’s recall some basic facts about functions.

A. Doerr

1. In high school we first learned how to manipulate linear equations algebraically. Next, we learned through an example, like y = 2x + 3, what this meant and then how to graph this function.

2. Next, you probably learned the “functional notation”, for example f(x) = 2x + 3. 3. A third notation for the same function you learned in an earlier part of this course,

namely, define f: R  R by the formula f(x) = 2x + 3. In this notation concepts like, domain, codomain, composition and the precise definition of a function were discussed.

4. We could talk about this very same function the following way. A function, f from R to R is the subset of the xy- plane, that is of R x R where f = {(x,y)| x R and y = 2x + 3}. Here the focus is that f is a set of ordered pairs of real numbers (x, y) with certain restrictions. What are they?

So discussions about the function f(x) = 2x + 3 centered about how to describe it algebraically and then how to graph it. In discrete graph theory our discussions parallel that of the above (let’s call the above continuous graph theory). We will define the analogue of the definition of a function namely that of a relation, then graph it. The resulting graph is called a directed graph of the relation. Precise definitions, examples and illustrations follow in the notes below and in the text. Compare the definition of relation given below to item 4 above. Is every function (from A to B) a relation (from A to B)? YES. Is every relation (from A to B) a function (from A to B)? NO A Procedure for studying the sections on relations from the text

1. In section 9.1 of the text, study examples 1 through 6. Temporarily skip properties of relations in section 1. Study this when you cover partial ordering relations in section 6.

2. Skip section 9.2 of the text. Study section 9.3 of the text, representing relations

using digraphs through example 9. At this point you should be able to write the relation as a set of ordered pairs of each of the graphs in exercises 23 through 28 of section 9.3. This is also covered in section 6.2 of the notes “Graphs of relation” which begins on page 8 below. Here are a couple of examples which are in the text:

Example 1. I will describe the graph given in exercise 24, section 9.3 on representing relations, as a set of ordered pairs. Keep in mind I must give you 2 things a set A, and the relation, R which acts on A. Looking at the graph in exercise 24 we see that the set A is the set {a, b, c}. Next we have to define relation R on A (Note, that is R is a subset of A x A, that is, R is a relation from A to A). So here is the description. Define R on A by R = {(a, a), (b, b), (c, c), (b, a), (a, c), (b, c)}. Note, there is a directed edge, an “arrow” for each ordered pair, since there are 6 directed edges in the graph there should be 6

A. Doerr

ordered pairs. Can you represent this relation by a 3 by 3 yes/no matrix? You should be able to do so after you study section 3. Example 2. Describe exercise 27, of section 9.3 of the text as a set of ordered pairs. I first note there are 9 directed edges so I should list 9 ordered pairs. Let A = {a, b, c, d}. Define the relation R on A by R = {(a, a),(b, b),(d, d),(a, b),(b, a),(a, c),(c, a),(b, c),(c, b)}. Can you write the yes/no matrix of R? See section 3.

3. There are 3 key properties listed in section 9.1 of the text. The properties are: reflexive, antisymmetric and transitive. Study these definitions. The definitions of these terms are also given in section 6.3 of the notes page 11. The reason for theses definitions is to introduce a special type of relation called a partial ordering relation. When a relation is a partial ordering relation we can draw a much cleaner version of its graph called a partially ordered graph or a Hasse graph. This topic is covered in the text in section 3 week 13 but you may wish to study it now through the notes in section 6.3, page 11 below.

4. Next go to section 3 of the text, Representing Relations Using Matrices. The

parallel section in the notes is section 6.4. You might find this helpful. The remark given in the notes, Section 6.4, after Theorem 6.4.1 on page 17 gives a convenient, and much faster way of determining the yes/no matrix of a relation. I will write the (yes/no) matrix of example 1 above using this method.

Example 3. Write the yes/no or Boolean matrix of the relation given in example 1. First from the notes we realize that there is a 1 (a true) for each ordered pair (or directed edge) in the relation R. Since R contains 6 ordered pairs there are 6 1’s in the matrix. We will use the texts notation for the matrix of R, namely MR. Since the domain and the codomain are the same set A = {a, b, c} we will prefix both the rows and the columns of MR by the elements in A in the order listed, namely a, b, c. For ease in typing I will first

write the matrix in table form as

a b c

a 1 0 1

b 1 1 1

c 0 0 1

so MR =

1 0 1

1 1 1

0 0 1

        

For more practice of matrices of relations read the following:

Examples:

1. Let A = {1, 2, 3} and let B = {x, y} and let S be the relation from A to B defined by S = {(1, x), (2,x), (2,y), (3, y)} Then the (yes/no)matrix of S is called MS where MS is a 3 by 2 matrix. To easily find this matrix first list a 3 x 2 matrix

A. Doerr

_ _

         . Next write the domain of S, namely A, as a additional column before this matrix and write the codomain of S, namely B as a additional row above this matrix. Now your matrix looks like this

1 _ _

2 _ _

3 _ _

x y

         . Next, since the pair (1,x) belong to the relation indicate a “yes” or 1 in the row 1 and

column x of the matrix. Since the pair (1, y) does not belong to the given relation indicate a no or 0 in column 1, row y. Since there are four pairs in the given relation there are four 1’s in the matrix. So your matrix looks like

1 1 0

2 1 1

3 0 1

x y

         . The additional column and row were just used for assistance so MS =

1 0

1 1

0 1

        

2. Let A ={a,b,c,d} and let R = {(a, a) (b, b), ( c, c), (a, b), (b, c), (d, a), (d, b)} be a relation on A

(i.e. from A to A). First we observe that the domain and the codomain are the same set , namely A. The (yes/no) matrix of R is 4 x 4 matrix because both the domain, A, and the codomain, A, each contain 4 elements. This matrix has seven 1’s in it because the relation has 7 pairs. So MR is

1 1 0 0

0 1 1 0

0 0 1 0

1 1 0 0

a b c d

             . Often this matrix is simply written as

1 1 0 0

0 1 1 0

0 0 1 0

1 1 0 0

             .

3. Note, given the matrix in example you should be able to work “backwards” to find the relation,

That is, if A ={a, b, c, d} and if the matrix of R is MR =

1 1 0 0

0 1 1 0

0 0 1 0

1 1 0 0

           

. What is R?

Example 4. Describe the relation, S on the set A = {1, 2, 3, 4} whose yes/no matrix is

MS =

1 0 1 0

0 1 0 1

1 0 0 1

0 0 1 1

           

. There are 8 ones in this matrix so there are 8

ordered pairs in

A. Doerr

the relation S. If you prefix the first column and the first row of the matrix by the elements of the set A you can then read off the ordered pairs of S and you will find that S = {(1, 1),(1, 3),(2, 2),(2, 4),(3, 1),(3, 4),(4, 3),(4, 4)}. Can you now write the digraph of S? Try it. How many directed edges are in the graph?

5. From the above we can see all relations on a set A can be represented/described any one of three ways: by a set of ordered pairs, by a digraph and by a “yes/no” matrix.

6. Now go back and cover the rest of the material in sections 1 through 3

Example 5. Consider the relation S whose digraph is Figure 6.2.3. What information does this give us? Certainly we know that s is a relation of a set A, where A ={1 , 2, 3} and S = {(l, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 3)}. There are 6 directed edges so there are 6 ordered pairs in S. The directed graph also tells us that the yes/no or Boolean matrix must be a 3 x 3 matrix since there are 3 nodes and the matrix contains 6 1’s.

MS =

0 1 1

1 0 1

        

The material below parallels that of your text in sections 1 through 6. The intention in giving you this material is to provide you with additional examples and exercises. Some of the notation is slightly different than that of the text so be careful. 1. In the text, capital letters namely R and S are used for relations while in the notes lowercase letters r and s are used. 2. In the text, MR is used for the yes/no matrix of the relation R while in the notes the capital R is used for the relation r. 3. In the text R* is used for the transitive closure of R, while in the notes below r+ is used for the transitive closure of r. 4. (WARNING) For composition of the relations R and S the text uses the notation

A. Doerr

S R to indicate that R is the first relation and S is the second, just like for functions. While in notes rs is used for the composition and r is the first relation and s is the second. 5. In the text the matrix of the relation S R is written as MS R and MS R = MRMS (or simply as MRMS if it is clear that the operation is Boolean. See page 495. In the notes the matrix of the relation rs is written as SR and the order of product of the matrices is the same, namely SR. 6. The text uses  for the “logical operation”, that is, Boolean addition. For example in the text we would say, 1  1 = 1. In the notes Boolean addition is written (as in chapter 10 of the text) as 1 + 1 = 1. As was mentioned in week 1 of the notes read both  and + in this context as OR. Also the text uses the symbol  to “flag” the reader that Boolean/logical arithmetic is to be used, where in the notes no symbol is used as in basic algebra. That is, SR means use Boolean arithmetic. 6 GOALS One understands a set of objects completely only if the structure of that set is made clear by the interrelationships between its elements. For example, the individuals in a crowd can be compared by height, by nationality, or through several other criteria. In mathematics, such comparisons are called relations. The goal of this chapter is to develop the language, tools, and concepts of relations. 6.1 Basic Definitions In Chapter I we introduced the concept of the Cartesian product of sets. Let's assume that a person owns three shirts and two pairs of slacks. More precisely, let A = {blue shirt, tan shirt, mint green shirt} and B = {gray slacks, tan slacks}. Then certainly A X B is the set of all possible combinations (six) of shirts and slacks that the individual can wear. However, the individual may wish to restrict himself or herself to combinations which are color coordinated, or "related." This may not be all possible pairs in A X B but will certainly be a subset of A X B. For example, one such subset may be {(blue shirt, gray slacks), (blue shirt, tan slacks), (mint green shirt, tan slacks)}. Definition: Relation. Let A and B be sets. A relation from A into B is any subset of A X B. Example 6.1.1. Let A = {1, 2, 3} and B = {4, 5}. Then {(l, 4), (2, 4), (3, 5)} is a relation from A into B. Of course, there are many others we could describe; 64, to be exact. Example 6.1.2. Let A = {2, 3, 5, 6} and define a relation r from A into A by (a, b)  r if and only if a divides evenly into b. So r ={(2, 2), (3, 3), (5, 5), (6, 6), (2, 6), (3, 6)}. Definition: Relation on a Set. A relation from a set A into itself is called a relation on A.

A. Doerr

Sometimes it is helpful to illustrate a relation. Consider Example 6. 1. 1. A picture of r can be drawn as in Figure 6. 1. 1. The arrows indicate that I is related to 4 under r. Also, 2 is related to 4 under r, and 3 is related to 5, while the upper arrow denotes that r is a relation from the whole set A into the set B. A typical element in a relation r is an ordered pair (x, y). In some cases, r can be described by actually listing the pairs, which are in r, as in the previous examples. This may not be convenient if r is relatively large.

Other notations are used depending on personal preference or past practice. Consider the following relations on the real numbers:

r = {(x, y) | y is the square of x}, and s = {(x,y) | x  y}.

The notation (4, 16) r or (3, 7.2)  s makes sense in both cases. However, r would be more naturally expressed as r(x) = x

2 or r(x) = y, where y = x

2 . But this notation

when used for s is at best awkward. The notation x  y is clear and self-explanatory; it is a better notation to use than (x, y) s. Many of the relations we will work with "resemble" the relation  , so x s y is a commonly used way to express the fact that x is related to y through the relation s. RELATION NOTATION Let s be a relation from a set A into a set B. Then the fact that (x,y)  S is frequently written x s y. Let A = {2, 3, 5, 8}, B = {4, 6, 16}, and C = {1, 4, 5, 7}; let r be the relation "divides," denoted by |, from A into B; and let s be the relation  from B into C. So r = {(2, 4), (2, 6), (2, 16), (3, 6), (8, 16)} and s = {(4,4), (4, 5), (4, 7), (6, 7)}. Notice from Figure 6.1.2 that we can, for certain elements of A, go through elements in B to results in C. That is:

2 | 4 and 4  4. 2 | 4 and 4  5. 2 | 4 and 4  7.

2 | 6 and 6  7. 3 | 6 and 6  7.

A. Doerr

Based on this observation, we can define a new relation, call it rs, from A into C. In order for (a, c) to be in rs, it must be possible to travel along a path in Figure 6.1.2 from a to c. In other words, (a, c) rs if and only if  bB such that arb and bsc. The name rs was chosen solely because it reminds us that this new relation was formed by the two previous relations r and s. The complete listing of all elements in rs is {(2, 4), (2, 5), (2, 7), (3, 7)}. We summarize in a definition.

Definition: Composition. Let r be a relation from a set A into a set B, and let s be a relation from B into a set C. The composition of r and s, written rs, is the set of pairs of the form (a, c)  A X C, where (a, c)  rs if and only if there exists b  B such that (a, b)  r and (b, c)  s. Be careful, in these notes r is the first relation and s is the second in the notation rs. Some texts would write this as “sr” or sr just like function notation. In the Rosen text the notation SR means R is the first relation and S the second. Note, he also uses upper case letters for relations. Remark: A word of warning to those readers familiar with composition of functions. (For those who are not, disregard this remark. It will be repeated at an appropriate place in Chapter 7.) As indicated above, the traditional way of describing a composition of two relations is rs where r is the first relation and s the second. However, function composition is traditionally expressed "backwards"; that is, as sr (or sr), where r is the first function and s is the second. EXERCISES FOR SECTION 6.1 A Exercises 1. For each of the following relations r defined on P, determine which of the given ordered pairs belong to r.

(a) x r y iff x | y ; (2, 3), (2, 4), (2, 8), (2, 17)

(b) x r y iff x  y ; (2, 3), (3, 2), (2, 4), (5, 8) (c) x r y iff y = x2 ; (1, 1), (2,3), (2, 4), (2, 6)

2. The following relations are on {1, 3, 5}. Let r be the relation x r y iff y = x + 2 and s the relation x s y iff x  y.

(a) Find rs. (b) Find sr. (c) Illustrate rs and sr via a diagram. (d) Is the relation (set) rs equal to the relation sr? Why?

A. Doerr

3. Let A = {1, 2, ... , 5} and define r on A by xry iff x + 1 = y. We define r 2

= rr, r 3 = r

2 r, etc. Find:

(a) r (b) r 2 (c) r

4. Given s and t, relations on Z, s = {(l, n) : n  } and t = {(n, 1): n  }, what are st and ts? B Exercises 5. Let  be the relation on the power set P(S) of a finite set S of cardinality n. Define  by (A,B)   iff A  B = 0.

(a) Consider the specific case n = 3, and determine the cardinality of the set  . (b) What is the cardinality of p for an arbitrary n? Express your answer in terms of n. (Hint:

There are three places that each element of S can go.)

6. Let r 1 , r 2 , and r 3 be relations on any set A. Prove: If r 1  r 2 , then r 1 r 3  r 2 r 3 6.2 Graphs of Relations In this section we will give a brief explanation of procedures for graphing a relation. A graph is nothing more than an illustration that gives us, at a glance, a clearer idea of the situation under consideration. A road map indicates where we have been and how to proceed to reach our destination. A flow chart helps us to zero in on the procedures to be followed to code a problem. The graph of the function y = 2x + 3 in algebra helps us to under stand how the function behaves. Indeed, it tells us that the graph of this function is a straight line. The pictures of relations in the previous section gave us an added insight into what a relation is. They indicated that there are several different ways of graphing relations. We will investigate two additional methods. Example 6.2.1. Let A = {0, 1, 2, 3}, and let r be the relation {(0, 0), (0, 3), (1, 2), (2, 1), (3, 2), (2, 0)}. The elements of A are called the vertices of the graph. Place the vertices, enclosed in a circle or denoted by a point. Connect vertex a to vertex b with an arrow, called an edge of the graph, going from vertex a to vertex b if and only if a r b. This type of graph of a relation r is called a directed graph or digraph. The result is Figure 6.2. 1.

A. Doerr

The actual location of the vertices is immaterial. The main idea is to place the vertices in such a way that the graph is easy to read, a help to you. Obviously, after a rough-draft graph of a relation, we may decide to relocate and/or order the vertices so that the final result will be neater. Figure 6.2.1 could be presented as in Figure 6.2.2.

A vertex of a graph is also called a node, a point, or a junction. An edge of a graph is also referred to as an arc, a line, or a branch. Do not be concerned if two graphs of a given relation look different. It is a nontrivial problem to determine if two graphs are graphs of the same relation. Example 6.2.2. Consider the relation s whose digraph is Figure 6.2.3. What information does this give us? Certainly we know that s is a relation of a set A, where A ={1 , 2, 3} and s = {(l, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 3)}.

A. Doerr

Example 6.2.3. Let B = {a, b}, and let A = P(B) = {  , {a},{b}, {a,b}}. Then  is a relation on A whose digraph is Figure 6.2.4.

This graph is helpful insofar as it reminds us that each set is a subset of itself (How?) and shows us at a glance the relationship between the various subsets in P(B). Some relations, such as this one, can also be conveniently depicted by what is called a Hasse, or ordering, diagram. To read a Hasse diagram for a relation on a set A, remember:

(1) Each vertex of A must be related to itself, so the arrows from a vertex to itself are not necessary. (2) If vertex b appears above vertex a and if vertex a is connected to vertex b by an edge, then a r b, so direction arrows are not necessary. (3) If vertex c is above vertex a and if c is connected to a by a sequence of edges, then a r c. (4) The vertices (or nodes) are denoted by points rather than by "circles."

The Hasse diagram of the directed graph depicted in Figure 6.2.4 is Figure 6.2.5.

Example 6.2.4. Consider the relation s whose Hasse diagram is Figure 6.2.6. How do we read this diagram? What is A? What is s? What does the digraph of s look like? Certainly A = {a, b, c, d, e} and a s c, c s d, a s d, a s e, etc., so

s = {(a, a), (b, b), (c, c), (d, d), (e, e), (a, c), (a, d), (a, e), (a, b), (c, d), (c, e), (d, e), (b, e)}. The digraph for s is Figure 6.2.7. It is certainly more complicated to read than the Hasse diagram.

A. Doerr

EXERCISES FOR SECTION 6.2 A Exercises

1. Let A = {1, 2, 3, 4}, and let r be the relation on A. Draw the digraph and the Hasse diagram of r. 2. Let B = {2, 3, 4, 6, 12, 36, 48}, and let s be the relation I, "divides," on B. Draw the Hasse diagram of s. 3. Draw the Hasse diagram of the relation  on P(A), where A = {a, b, c}. 4. (a) Let A be the set of strings of 0s and 1s of length 3 or less. Define the relation of d on A by x d y if x is contained within y. For example, (01) d (101). Draw the Hasse diagram for this relation. (b) Do the same for the relation p defined by x p y if x is a prefix of y. For example, (10) p (101), but (01) p (101) is false. 5. Draw the digraph for the relation p in Exercise 5 of Section 6. 1, where S ={a, b}. Explain why a Hasse diagram could not be used to depict  .

6.3 Properties of Relations Consider the set B = {1, 2, 3, 4, 6, 12, 36, 48} and the relations "divides" and  on B. We notice that these two relations on B have several properties in common. In fact:

(1) Every element in B divides itself and is less than or equal to itself. This is called the reflexive property. (2) If we search for "two" elements from B where the first divides the second and the second divides the first, then we are forced to choose the same first and second number. The reader can verify that a similar result is true for the relation  on B. This is called the antisymmetric property. (3) Next if we choose three numbers from B such that the first divides (or is  ) the second and the second divides (or is  ) the third, then this forces the first number to divide (or be  ) the third. This is called the transitive property.

A. Doerr

Sets on which relations are defined which satisfy the above properties are of special interest to us. More detailed definitions follow. Definitions: Reflexive, Antisymmetric, and Transitive. Let Abe a set and r a relation on A, then:

(1) r is called reflexive if and only if a r a for all a  A. (2) r is called antisymmetric if and only if whenever a r b and a  b then b r a is false; or equivalently whenever a r b and b r a then a = b. (The reader is encouraged to think about both conditions since they are frequently used.) (3) r is called transitive if and only if whenever a r b and b r c then a r c.

A word of warning about antisymmetry: Students frequently find it difficult to understand this definition. Keep in mind that this term is defined through an "If ... then . . ." statement. The question that you must ask is: Is it true that whenever there are elements a and b from A where a r b and a  b, it follows that b is not related to a? If so, then the relation r is antisymmetric. Another way to determine whether a relation is antisymmetric is to examine its graph. The relation is not antisymmetric if there exists a pair of vertices that are connected by edges in both directions. Note that the negative of antisymmetric is not symmetric. We will define the symmetric property later. Definition: Partial Ordering. A relation on a set A that is reflexive, antisymmetric, and transitive is called a partial ordering on A. A set on which there is a partial ordering relation defined is called a partially ordered set or poset. Example 6.3.1. Let A be a set. Then 91(A) together with the relation  is a poset. To prove this we show that the three properties hold:

(1) Let B  P(A). We must show that B  B. This is true by definition of subset. Hence, the relation is reflexive.

(2) Let B 1 , B 2 P(A) and assume (Why?) that B 1  B 2 and B 1  B 2 Could it be that B 2  B 1 ? No. Why? Hence, the relation is antisymmetric.

(3) Let B 1 , B 2 , B 3  P(A) and assume that B 1  B 2 and B 2  B 3 . Does it follow that B 1

 B 3 ? Yes. Hence, the relation is transitive. Example 6.3.2. Consider the relation s defined by the Hasse diagram in Figure 6.2.6. A relation defined by a Hasse diagram is always a partial ordering. Let's convince ourselves of this.

(1) First, s is reflexive. If this is not clear draw the digraph of the above relation.

(2) Next, s is antisymmetric. From the diagram, can we find two different elements, say c 1 and

c 2 , such that c 2 s c 1 and c 1 s c 2 ? No. If this argument is not clear, try the following: From the

diagram find "two" elements such that the first is related through s to the second and the second is related to the first. The only elements that work are pairs of identical elements. (3) Finally, s is transitive. How do we show this? We must show that for any three elements chosen such that the first is related to the second and the second is related to the third, then the first must be related to the third. Consider, for example, the three elements c, d, and e. From the diagram, c s d and d s e, so the hypothesis is satisfied. We must show that c s e. This is true from the diagram. How? If this is not clear, the digraph of s may be helpful. Does this one example show transitivity?

Another property that is frequently referred to is that of symmetry. Definition: Symmetry. Let r be a relation on a set A. r is called symmetric if and only if whenever a r b, it follows that b r a.

A. Doerr

Consider the relation = defined on  . Certainly a = b implies that b = a so = is a symmetric relation on  . Surprisingly, = is also an antisymmetric relation on  . This is due to the fact that the condition of the antisymmetry property, a = b and a  b, is a contradiction. Remember, a conditional proposition is always true when the condition is false. So a relation can be both symmetric and antisymmetric on a set! Again recall that these terms are not negatives of each other. Definition: Equivalence Relation. A relation r on a set A is called an equivalence relation if and only if it is reflexive, symmetric, and transitive. The classic example of an equivalence relation is the relation = on  . In fact, the term equivalence relation is used because those relations which satisfy the definition behave quite like the = relation. Example 6.3.3. Let Z* be the set of nonzero integers. One of the most basic equivalence relations in mathematics is the relation q on  X * defined by (a, b) q (c, d) if and only if ad = bc. We will leave it to the reader to, verify that q is indeed an equivalence relation. Two ordered pairs, (a, b) and (c, d), are related if the fractions a|b and c|d are numerically equal. Example 6.3.4. Consider the relation s described by the digraph in Figure 6.3. 1. This relation is reflexive (Why?), not symmetric (Why?), and not transitive (Why?). Is s an equivalence relation? A partial ordering? A classic example of a partial ordering relation is  on R. Indeed, when graphing partial ordering relations, it is natural to "plot" the elements from the given poset starting with the "least" element to the "greatest" and to use terms

like "least," "greatest," etc. Because of this the reader should be forewarned that many texts use the  notation when describing an arbitrary partial ordering. This can be quite confusing for the novice, so we continue to use the general notation r, s, etc., when speaking of relations. EXERCISES FOR SECTION 6.3 A Exercises 1. (a) Let B = {a, b} and A = P(B). Draw the Hasse diagram for  on A. (b) Let A = {1, 2, 3, 6}. Show that "divides," is a partial ordering on A. Draw the Hasse diagram. (c) Compare the graphs of parts a and b. 2. (a) Repeat Exercise 1 (a) for B = {a, b, c}. (b) Repeat Exercise 1 (b) for A = {1, 2, 3, 5, 6, 10, 15, 30}. 3. (a) Consider the relations defined by the digraphs in Figure 6.3.2.

A. Doerr

Determine whether the given relations are reflexive, symmetric, antisymmetric, or transitive. Try to develop procedures for determining the validity of these properties from the graphs. (b) Which of the above are graphs of equivalence relations or of partial ordering of relations?

4. Determine which of the following are equivalence relations and/or partial ordering relations for the given sets: (a) A = {lines in the plane}; x r y if and only if x is parallel to y. (b) A = R; x r y if and only if |x-y|  7. 5. Consider the following relation on {1, 2, 3, 4, 5, 6}. r = {(i, j): | i – j | = 2}.

A. Doerr

(a) Is r reflexive? (b) Is r symmetric? (c) Is r transitive? (d) Draw a graph of r.

6. For the set of cities on a map, consider the relation x r y if and only if city x is connected by a road to

city y. A city is considered to be connected to itself, and two cities are connected even though there are cities on the road between them. Is this an equivalence relation or a partial ordering? Explain.

7. Let A = {0, 1, 2, 3} and let r = {(0,0), (1,1), (2,2), (3,3), (1,2), (2, 1), (3, 2), (2, 3), (3, 1), (1, 3)}

(a) Show that r is an equivalence relation on A. (b) Let a  A and define c (a) = {b  A | a r b}. c(a) is called the equivalence class of the element a under r. Find c(a) for each element a A. (c) Show that {c(a) | a  A} (d) Let r be an equivalence relation on an arbitrary set A. Prove that the set of all equivalence classes constitutes a partition of A.

8. Define r on the power set of {1, 2, 3} by A r B  # A = # B. Prove that r is an equivalence relation.

What are the equivalence classes under r? 9. Consider the following relations on Z8 = {0, 1,…,7}. Which are equivalence Relations?

For the equivalence relations, list the equivalence classes. a. a r b iff the English spellings of a and b begin with the same letter. b. a s b iff a – b is a positive integer. c. a t b iff a – b is an even integer.

10. Define t on A = {1, 2, . . . , 9} by x t y iff x + y = 10. Is t an equivalence relation on A? If yes, list its equivalence classes. If not, why not? B Exercises 10. In this exercise, we prove that implication is a partial ordering. Let A be any set of Propositions.

(a) Verify that q  q is a tautology, thereby showing that  is a reflexive relation on A. (b) Prove that  is antisymmetric on A. Note: we do not use = when speaking of propositions,

but rather,  . (c) Prove that  is transitive on A. (d) Given that qi is the proposition n = 1 on N, draw the Hasse diagram for the relation  on

{q1, q2,…,q8}.

C Exercise (e) Let S = {a, b, c, d, e, f, g,} be a poset [S,  ] with the Hasse diagram shown in Figure 6.3.3. Another relation r  S x S is defined as follows: (x,y) r if and only if there exists z S such that z  x and z  y in the poset [S,  ]

(a) Prove that r is reflexive. (b) Prove that r is symmetric. (c) A compatible with respect to relation r is any subset Q of set S such that x Q and y Q

 (x, y) r. A compatible Q is a maximal compatible if Q is not a proper subset of another compatible. Give all maximal compatibles with respect to relation r defined above.

(d) Discuss a characterization of the set of maximal compatibles for relation r when [S,  ] is a general finite poset. What conditions, if any, on a general finite poset [S,  ] will make r an equivalence relation?

A. Doerr

6.4 Matrices of Relations We have discussed two of the many possible ways of representing a relation, namely as a digraph or as a set of ordered pairs. In this section we will discuss the representation of relations by matrices and some of its applications. Definition: Adjacency Matrix. Let A and B be finite sets of orders m and n, respectively, and let r be a relation from A into B. Then r can be represented by a matrix R called the adjacency matrix (or the Boolean matrix, or the relation matrix) of r. To construct the matrix R, proceed as follows: Let A = {a1, a2,… am} and B = {b1, b2,…,bn}. Then R is an m x n matrix whose ith jth entry is

ijR = i j1 if a r b ;

0 otherwise

  

Example 6.4.1. Let A = {2, 5, 6} and let r be the relation {(2, 2), (2, 5),(5, 6), (6, 6)} on A. Since r is a relation from A into the same set A (the B of the definition), we have a1 = 2, a2 = 5, and a3 = 6, and b1, = 2, b2 = 5, and b3 = 6. Next, since:

2r2, we have R11 = 1; 2r5, we have R12 = 1; 5r6, we have R23 = 1; and 6r6, we have R33 = 1.

All other entries of R are 0. So

R =

1 1 0

0 0 1

        

From the definition of r we note that r2 = {(2, 2) (2, 5) (2, 6) (5, 6) (6, 6)}. The adjacency matrix of r2 is

A. Doerr

R 2

1 1 1

0 0 1

        

We do not write R 2 only for notational purposes. In fact, R 2 can be obtained from the matrix product RR; however, we must use a slightly different form of arithmetic.

Definition: Boolean Arithmetic. Boolean arithmetic is the arithmetic defined on {0, 1} using Boolean addition and Boolean multiplication, defined as:

0 + 0 = 0 0 + 1 = 1 + 0 = 1 1 + 1 = 1 0 · 0 = 0 0 · 1 = 1 · 0 = 0 1 · 1 = 1

From Chapter 3 it is clear that this is the "arithmetic of logic," where + replaces "or" and · replaces "and." Example 6.4.2.

If R =

0 1 0 0

1 0 1 0

0 1 0 1

0 0 1 0

           

and S =

0 1 1 1

0 0 1 1

0 0 0 1

0 0 0 0

           

then RS =

0 0 1 1

0 1 1 1

0 0 1 1

0 0 0 1

           

and SR =

1 1 1 1

0 1 1 1

0 0 1 0

0 0 0 0

           

using Boolean arithmetic.

Theorem 6.4.1 Let A1, A2, and A3 be finite sets where r1 is a relation from A1 into A2 and r2 is a relation from A2 into A3. If R1 and R2 are the adjacency Matrices of r1 and r2, respectively, then the product R1R2 is the adjacency matrix of the composition r1r2. Remark:

A convenient help in constructing the adjacency matrix of a relation from a set A into a set B is to write the elements from A in a column preceding the first column of the adjacency matrix, and the elements of B in a row above the first row. Initially, the matrix in Example 6.4.1 would be relation from a set A into a set B is to write the elements from A in a column preceding the first column of the adjacency matrix, and the elements of B in a row above the first row. Initially, the matrix in Example 6.4.1 would be

2 5 6

. . .2

        

A. Doerr

and Rij is I if and only if (ai, bj)  r. So that, since the pair (2, 5) r, the entry of R corresponding to the row labeled 2 and the column labeled 5 in the matrix is a 1. Example 6.4.3. This final example gives an insight into how relational database programs can systematically answer questions pertaining to large masses of information. Matrices R (on the left) and S (on the right) define the relations r and s where arb if software a can be run with operating system b, and bsc if operating system b can run on computer c.

xDOS RT12 UNDOS RSTX

1986 1 0 1 0

1 1 0 0

1 0 0 1

/ 0 0 1 1

Dbass

Rock

Pf bug

     

           

     

PC-TI VIX Winesap

1 1 0

12 0 1 0

0 0 1

0 1 1

xDOS

UNDOS

RSTX

            

       

 

Although the relationship between the software packages and computers is not implicit from the data given, we can easily compute this information. The matrix of rs is RS, which is

PC-TI VIX Winesap

1986 1 1 1

1 1 0

1 1 1

/ 0 1 1

Dbass

Rock

Pf bug

        

      

    

 

This matrix tells us at a glance which software will run on the computers listed. In this case, all software will run on all computers with the exception of Pf/bug, which will not run on the PC-IT, and Dbass, which will not run on the Winesap. EXERCISES FOR SECTION 6.4 A Exercises

1. Let A 1 = {l, 2, 3, 4}, A 2 ={4, 5, 6}, and A 3 = {6, 7, 8}. Let r, be the relation from A 1 into A 2 defined

by r 1 = {(x, y) | y - x = 2}, and let r 2 be the relation from A 2 into A 3 defined by r 2 ={(x,y) | y-x =1}.

(a) Determine the adjacency matrices of r 1 and r 2

(b) Use the definition of composition to find r 1 r 2 .

2. (a) Determine the adjacency matrix of each relation given via the digraphs in Exercise 3 of Section 6.3. (b) Using the matrices found in part a above, find r2 of each relation in Exercise 3 of Section 6.3. (c) Find the digraph of r2 directly from the given digraph and compare your results with those of part b. 3. Suppose that the matrices in Example 6.4.2 are relations on {1, 2, 3, 4}.

What relations do R and S describe? 4. Let D = days of the week (M-F),

W = {l, 2, 3} employees of a programming tutorial center, and V = languages offered

A. Doerr

= {A (da), B (asic), C(obol), F(ortran), L(isp), P(ascal)}. We define s (schedule) from D into W by d s w if w is scheduled to work on day d. We also define r from W into V by w r l if w can tutor students in language l. If

1 2 3

S =

1 0 1

0 1 1

1 0 1

0 1 0

1 1 0

   

            

            

and R =

A B C F L P

1 0 1 1 0 0 1

2 1 1 0 1 0 1

3 0 1 0 0 1 1

   

     

     

 

determine SR and give an interpretation of this relation. 5. How many different reflexive, symmetric relations are there on a set with three elements? (Hint: Consider the possible matrices.) 6. Let A = {a, b, c, d}. Let r be the relation on A with adjacency matrix

a b c d

1 0 0 0

0 1 0 0

1 1 1 0

0 1 0 1

           

 



        

(a) Explain why r is a partial ordering on A. (b) Draw its Hasse diagram. 7. Define relations p and q on { 1, 2, 3, 4} by p = {(a, b):| a-b|=1 and q = {(a, b) : a – b is even }.

(a) Represent p and q as both graphs and matrices.

(b) Determine pq, p 2 , and q 2 and represent them clearly in any way. B Exercises

8. (a) Prove that if r is a transitive relation on a set A, then r 2  r. (b) Find an example of a transitive relation for which r  r. 9. Given two n X n relation matrices R and S defined on the same set, we say that

ij ij if R S for all 1 i, j .R S n    (a) Prove that  is a partial ordering on all n x n relation matrices. (b) Prove that R  S  R 2  S 2 , but the converse is not true. (c) If R and S are matrices of equivalence relations and R  S, how are the equivalence classes defined by R related to the equivalence classes defined by S?

6.5 Closure Operations on Relations In Section 6.1, we studied relations and one important operation on relations, namely composition. This operation enabled us to generate new relations from previously known relations. In Section 6.3, we discussed some key properties of relations. We now wish to consider the situation of constructing a new

A. Doerr

relation r 

from a previously known relation r where, first, r 

contains r and, second, r 

satisfies the transitive property. Consider a telephone network in which the main office a is connected to, and can communicate to, individuals b and c. Both b and c can communicate to another person, d; however, the main office cannot communicate with d. Assume communication is only one way, as indicated. This situation can be described by the relation r = {(a, b), (a, c), (b, d), (c, d)}. We would like to change the system so that the main office a can communicate with person d and still maintain the previous system. We, of course, want the most economical system.

This can be rephrased as follows: Find the smallest relation r 

which contains r as a subset and which is

transitive; r 

= {(a, b), (a, c), (b, d),(c, d), (a, d)}. Definition: Transitive Closure. Let A be a set and r be a relation on A. The transitive closure of r, denoted

by r 

, is the smallest relation that contains r as a subset and that is transitive. Example 6.5.1. Let A = {1, 2, 3, 4}, and let S = {(l, 2), (2, 3), (3, 4)} be a relation on A. This relation is

called the successor relation on A since each element is related to its successor. How do we compute S 

By inspection we note that (1, 3) must be in S 

. Let's analyze why. This is so since (1, 2)  S and (2, 3)  S, and the transitive property forces (1,3) to be in S  . In general, it follows that if (a, b)  S and (b, c) S, then (a, c)  S  . This condition is exactly the membership requirement for the pair (a, c) to be in the composition S S = S2. So every element in S2 must be an element in S

 . So far, S

 contains at least S

 S2. In particular, for this example, since S = {(l, 2), (2, 3), (3, 4)} and S2 = {(l, 3), (2, 4)}, we have S  S2 = {(l, 2), (2, 3), (3, 4), (1, 3), (2, 4)}. Is the relation S  S2 transitive? Again, by inspection, (1, 4) is not an element of S  S2, but it must be an element of S

 since (1, 3) and (3, 4) are required to be in S

 . From above, (1, 3) S2 and (3, 4)  S,

and the Composite S2 S = S 3

produces (1, 4). This shows that S 3  S  . This process must be continued

until the resulting relation is transitive. If A is finite, as is true in this example, the transitive closure will be

obtained in a finite number of steps. Here, S 

= S  S 2  S 3 .

Theorem 6.5.1. If S is a relation on a set A and if #A = n, then the transitive closure S 

= S  S 2  S

3 ....

nS . Let's now consider the matrix analogue of the transitive closure. Example 6.5.2. Consider the relation r={(l, 4), (2, 1), (2, 2), (2, 3),(3, 2), (4, 3), (4, 5), (5, I)} on the set A={1, 2, 3, 4, 5}. The matrix R of r is

0 0 0 1 0

1 1 1 0 0

0 1 0 0 0

0 0 1 0 1

1 0 0 0 0

              

Recall that r2, r3 . . . can be determined through computing the matrices R2, R3…..Here,

A. Doerr

R2 =

0 0 1 0 1

1 1 1 1 0

1 1 1 0 0

1 1 0 0 0

0 0 0 1 0

              

R3 =

1 1 0 0 0

1 1 1 1 1

1 1 1 1 0

0 0 0 1 0

              

R4 =

1 1 1 1 0

1 1 1 1 1

1 1 0 0 0

              

R5 =

1 1 1 1 1

1 1 1 1 0

              

How do we relate 5

  i i i

r to the powers of R?

Theorem 6.5.2. Let R 

be the matrix of r 

, the transitive closure of r, which is a relation on a set of n

elements. Then R 

= R + R 2

+…+R n

where addition is done using Boolean arithmetic.

Using this theorem, we find R 

is the 5 x 5 matrix consisting of all Is, thus, r 

is all of A x A. WARSHALL'S ALGORITHM Let r be a relation on the set {1, 2, . . . , n } with relation matrix R. The matrix of the transitive closure R+, can be computed by the equation R+ = R + R2 +…+ Rn. By using ordinary polynomial evaluation

methods, you can compute R+ with n -1 matrix multiplications: R 

= R (I + R (I +R (I + R) ... )). For

example, if n = 3, R 

= R (I + R (I + R)). Warshall's algorithm makes use of the fact that if T is a relation matrix, T + T = T due to the fact that I + I

= I in Boolean arithmetic. Let Sk = R + R 2

+…+R k

. Then

R=S 1 2

1 1 2( ) ( )S I S R I R R R S      2 2

2 2( ) ( )( )S I S R R I R R    

2 2 3 3 4( ) ( ) ( )R R R R R R     

2 3 4R R R R    4S

4 4 8( )S I S S  Note how each matrix multiplication doubles the number of terms that have been added to the sum that you

currently have computed. In algorithmic form, we can compute R 

as follows.

A. Doerr

Algorithm 6.5.1:Warshall's Algorithm-Version l. Let R be a known relation matrix and let R 

be its transitive closure matrix, which is to be computed.

1.0. T:= R 2.0. Repeat

2.1 S:= T 2.2 T:= S(I + S)(*using Boolean arithmetic*) Until T = S

3.0. Terminate with R 

= T. Notes:

(a) Often the higher-powered terms in Sn do not contribute anything to R 

. When the condition T = S becomes true in Step 2, this is an indication that no higher-powered terms are needed.

(b) To compute R 

using Version I of Warshall's Algorithm, you need to perform no more than

2log n   matrix multiplications, where [x] is the least integer that is greater than or equal to x.

For example, if r is a relation on 25 elements, no more than 2log 25   = 5 matrix multiplications are needed.

A second, improved version of Warshall's Algorithm reduces computation time to the time that it takes to perform one matrix multiplication.

Algorithm6.5.2: WarshaII's Algorithm-Version 2. Let R be a known relation matrix and let R 

be its transitive closure matrix, which is to be computed.

1.0 T := R 2.0 FOR k:= 1 to n DO

FOR i:= I to n DO FORj:= 1 to n DO T[i,j] : = T[i, j] + (T[i, k]  T[k, j])

3.0 Terminate with R 

= T. EXERCISES FOR SECTION 6.5 A Exercises

1. Let A and S be as in Example 6.5. 1. Compute S 

as in Example 6.5.2. Verify your results by checking

against the relation S 

obtained in Example 6.5. 1.

2. Let A and r be as in Example 6.5.2. Compute the relation r 

as in Example 6.5. 1. Verify your results.

3. (a) Write the digraphs of the relations S, S 2

, S 3

, and S 

of Example 6.5. 1.

(b) Verify that in terms of the graph of S, a S 

b if and only if b is reachable from a using a path of any finite nonzero length. 4. Let r be the relation represented by the digraph in Figure 6.5.1.

(a) Find r 

(b) Determine the digraph of r 

directly from the digraph of r. (c) Verify your result in part b by computing the digraph from your result in part a.

A. Doerr

5. (a) Define reflexive closure and symmetric closure by imitating the definition of transitive closure.

(b) Use your definitions to compute the reflexive and symmetric closures of Examples 6.5.1 and 6.5.2.

(c) What are the transitive reflexive closures of these examples? (d) Convince yourself that the reflexive closure of the relation < on the set of positive integers P is

 .

6. What common relations on Z are the transitive closures of the following relations? (a) aSb if and only if a +1 = b. (b) aRb if and only if |a – b|= 2.

B Exercise

7. (a) Let A be any set and r a relation on A. Prove (r 

) 

= r 

. (b) Is the transitive closure of a symmetric relation symmetric and reflexive? Explain.

SUPPLEMENTARY EXERCISES FOR CHAPTER 6, Section 6.1

1. Give an example to illustrate how the relation "is a grandparent of" is a composition of the relation "is a parent of" on people.

2. Three students, Melissa, John, and Ted, would like to set up a tutorial program in the languages Pascal, FORTRAN, and COBOL. Melissa is proficient in all three languages, John in Pascal and FORTRAN, and Ted in just FORTRAN.

(a) Let S = {three students}, L = {three Languages}, and let p be the relation "is proficient in the language of." Describe this relation as a set of ordered pairs and illustrate the relation by a diagram similar to that of Figure 6. 1. 1.

(b) Two P.C. s are available for tutoring purposes; one has software for Pascal and FORTRAN, and the second only for Pascal. Describe by a composite relation which student can tutor on each machine. Illustrate this composite relationship.

Section 6.2 3. Let A = {- 1, 0, 1, 2}. List the ordered pairs and draw the digraphs of each of the following relations on A.

(a) r = {(x, y) | y = x + 1}

(b) s = {(x, y) | x 2

= y 2

} (c) t = {(x, y) |x  y}

4. List the ordered pairs and draw the digraph of the relation s 2

for the relation s of Exercise 2, Section 6.2.

A. Doerr

5. In Figure 6.2, 1, assume the nodes stand for four separate cities where a manufacturer has warehouses, while the arrows represent one-way streets. Where should the manufacturer place his main office? Where is the least desirable location? How can we interpret the arrows in both directions between nodes I and 2? 6. The problem of computer compatibility is an important one. In Figure 6.2.2 interpret the four nodes as representing computers, and an arrow from one node to another as "is compatible with." Note that some software does not go both ways.

(a) Is there any one computer that is not compatible with any other? (b) Is it possible to create a network where any computer could be linked with any other using at most two links? If not, what software should be created to enhance compatibility? (c) If an arrow from a node to itself is interpreted as "high flexibility" of the system, does this affect your answer in part b?

Section 6.3 7. In Figure 6.3.2 (vii), interpret the four nodes as representing people, and an arrow from one node to another as "being friendly toward." Note that some friendships are not mutual.

(a) Is there any individual in this group unfriendly to everyone else? (b) If this group were a committee, who is most likely to be the chairperson; that is, who is friendly toward the most people? (c) If an arrow from one vertex to itself is interpreted as "great personality," does your answer to part b still hold? (d) The four people are to be seated at a round table. A person is to be seated between two people only if he is friendly toward both of them. Does a seating arrangement exist? Is there more than one?

8. Let A = {a, b, c, d, e} and let r, s, and t be the following relations on A:

r = { (a, a), (a, b), (b, b), (b, c), (c, c), (c, d), (d, d), (d, e), (e, e),(e, a)} s = {(a, a), (a, b), (a, d), (b, a), (b, b), (b, d), (c, c), (d, a), (d, b),(d, d), (e, e)} t = {(a, a), (a, b), (b, b), (c, b), (c, c), (d, d), (e, a), (e, b), (e, c),(e, d), (e, e)} (a) Which relation is a partial ordering? Draw its Hasse diagram. (b) Which relation is an equivalence relation? List its equivalence classes.

9. Demonstrate that the relation "living in the same house" on the set of people in a given city is an equivalence relation. State the necessary assumption for this to be the case.

10. Let A ={00, 01, 10, 11}, the set of strings of 0’s and 1’s with length two. Given r and s defined by

xry  x and y differ in exactly one position (for example 01 r 11, but not 10 r 01 , and

xsy  x and y have the same number of 0’s. (a) Draw a directed graph of r. (b) Which of the adjectives, reflexive, symmetric, antisymmetric, and transitive, describe r? Explain your answers. (c) Which of the adjectives, reflexive, symmetric, antisymmetric, and transitive, describe s? (d) Describe with a directed graph the relation rs.

11. Determine whether the following relations are partial orderings and/or equivalence relations on the given set:

(a) C = {students in this class}; x r y iff x and y have the same grade point average. (b) C = {students in this class}; x s y iff x is taller than y. (c) Rephrase (slightly) the relation in part b so it is a partial ordering relation.

10. Let A = {a, b, c, d}. Draw the graph of a relation where the relation is:

(a) reflexive, symmetric, but not transitive. (b) transitive, but not symmetric and not reflexive. (c) both an equivalence relation and a partial ordering.

A. Doerr

Section 6A 13. How many symmetric relations can there be on a four-element set? Hint: Think of the possible relation matrices. 14. Let A ={1, 2, 3, 4, 5,6} and let p={(i, j)| i divides j} be a relation on A. RELATIONS AND GRAPHS

(a) List the elements in p. (b) Determine the relation matrix of p. (c) Construct the digraph and the Hasse diagram of p.

15. Let A = {a, b, c}. The following matrices describe relations on A:

1 1 0 1 0 1

( ) 1 1 0 (ii) 0 0 0

0 0 1 1 1 1

                  

(a) Draw the graph of the relation. (b) Describe each relation as a set of ordered pairs.

for each relation r. Section 6.5 16. Let the relation s on the set {a, b, c, d, e} be given by the matrix

a b c d e

0 0 0 0 0

1 0 1 0 0

0 1 0 0 0

0 0 1 0 0

1 1 0 0 0

           

          

    

(a) Draw the digraph of s. (b) Find the transitive closure of s. Give the adjacency matrix or the digraph or the set of ordered pairs.

17. Consider the relation r on {1, 2, 3, 4} whose Boolean matrix is

1 2 3 4

1 0 0 1 1

2 0 1 0 0

3 0 0 1 0

4 1 0 0 0

     

       

   

    

(a) Draw the graph of r. (b) Determine whether r is reflexive, symmetric, antisymmetric, and/or transitive. Explain fully.

A. Doerr

18. In a small town a bank (b), school (s), town hall (t), and shopping mall (m) are connected by a series of narrow one-way streets: a street from the town hall to the bank, one from the bank to the school, one from the school to the shopping mall, and one from the shopping mall to the town hall. (a) Draw a digraph of this system of roads.

(b) Find the matrix representation of the digraph in part a. (c) Assuming that the given streets cannot be widened, assist the mayor in planning the construction of new roads to increase traffic flow. Assume that if there is a one-way street from point a to b and one from point b to c, there should be one from point a to c. (d) If you have not done so yet, draw the matrix representation and the graph of your answer to part c and interpret the results for the mayor.

19. The ambassadors of four countries are to meet with the ambassador of the United States (A 1 ) to discuss

world problems. Some countries are friendly to each other, some are not, and in certain situations the friendship is one-way. The U.S. ambassador's daughter (who obviously took a discrete structures course) assists her father in diagnosing this complex situation and, using the relation "is friendly toward," has come up with the following digraph.

(a) Is there any person friendly to no one? (b) Who should be the chairman of this committee; that is, who is friendly to most people? (c) The U.S. ambassador would like to graph all friendships that can be developed through intermediaries on the committee. That is, if person a is friendly toward person b and person b is friendly toward person c, then a can communicate to c through b. Draw this digraph. Can the U.S. ambassador communicate to every person on the committee through some person(s)? If not, what friendships should he develop to do so?

Solutions to the above sections CHAPTER 6 Section 6.1 1. (a) (2, 4), (2, 8) (b) (2, 3), (2, 4), (5, 8) (c) (1, 1), (2, 4) 3. (a) r = {(1, 2), (2, 3), (3, 4), (4,5)} (b) r2 = {(1, 3), (2, 4), (3, 5)} = {(x, y) : y = x + 2, x, y  A} (c) r3 = {(1, 4), (2, 5)} = {(x, y) : y = x + 3, x, y  A} 5. (a) When n = 3, there are 27 pairs in the relation. (b) Imagine building a pair of disjointed subsets of S. For each element of S there are three places that I can go: into the first set of the ordered pair, into the second set, or into neither set. Therefore the number of pairs in the relation is 3n, by the product rule.

A. Doerr

Section 6.2 1. There are 4 “arrows” missing from the graph on the left can you draw them in.

3. See Figure 13.1.1 of Section 13. 1

5. A Hasse diagram cannot be used because not every set is related to itself. Also, {a} and {b} are related in both directions. Section 6.3 1.

3. (a) (i) reflexive (ii) reflexive (iii) non reflexive not symmetric not symmetric symmetric

not antisymmetric antisymmetric not antisymmetric transitive transitive transitive

(iv) not reflexive (v) reflexive (v) reflexive symmetric symmetric not symmetric antisymmetric not antisymmetric antisymmetric

transitive transitive transitive (vii) not reflexive not symmetric not antisymmetric not transitive

(b) Graphs ii and vi show partial ordering relations. Graph v is of an equivalence relation. 5. (a) No, since for example | 1 – 1 | = 0  2. (b) Yes, since | i – j | = | j - i | (c) No, since | 2 – 4 | = 2 and | 4 – 6 | = 2, but | 2 – 6 | = 4  2. (d)

A. Doerr

7. (b) c(0) = {0}, c(l) = {1, 2, 3} = c(2) = c(3) (c) c(0)  c(l) = A and c(0)  c(l) =  (d) Let A be any set and let r be an equivalence relation on A. Let a be any element of A. a  c(a) since r is reflexive, so each element of A is in some equivalence class. Therefore, the union of all equivalence classes equals A. Next we show that any two equivalence classes are either identical or disjoint and we are done. Let c(a) and c(b) be two equivalence classes, and assume that c(a)  c(b)   . We want to show that c(a) = c(b). To show that c(a)  c(b), let x  c(a). x . c(a)  arx. Also, there exists an element, y, of A that is in the intersection of c(a) and c(b) by our assumption. Therefore, ary and bry  ary and yrb (r is symmetric)  arb (transitivity of r) Next, arx and arb  xra and arb  xrb  brx  x  c(b). Similarly, c(b)  c(a). # 9. (a) Equivalence Relation c(O) = {O}, c(l) = {1}, c(2) = {2,3} = c(3), c(4) = {4,5} = c(5), c(6)= {6,7} =c(7) (b) Not an Equivalence Relation (c) Equivalence Relation c(0) = {0,2,4,6} = c(2) = c(4) = c(6) c(l) = {1,3,5,7} = c(3) = c(5) = c(7) 11. (b) The proof follows from the biconditional equivalence in Table 3. 4. 2. (c) Apply the chain rule. (d)

A. Doerr

Section 6.4

1. (a)

4 5 6

1 0 0 0

2 1 0 0

3 0 1 0

4 0 0 1

   

           

       

and

6 7 8

4 0 0 0

5 1 0 0

6 0 1 0

and

     

    

     

(b)

6 7 8

1 0 0 0

2 0 0 0

3 1 0 0

4 0 1

    

      

     

 

 



3. R: xry if and only if |x – y| = l, S: xsy if and only if x is less than y.

5. The diagonal entries of the matrix for such a relation must be 1. When the three entries above the

diagonal are determined, the entries below are also determined. Therefore, the answer is 2 3

7. (a)

1 2 3 4

1 0 1 0 0

2 1 0 1 0

3 0 1 0 1

4 0 0 1 1

     

           

     

1 2 3 4

1 1 0 1 0

2 0 1 0 1 and

3 1 0 1 0

4 0 1 0

   

        

    

  

(b)

1 2 3 4

1 0 1 0 1

2 1 0 1 0 PQ =

3 0 1 0 1

4 1 0 1 0

      

    

    

      

2 2

1 2 3 4

1 1 0 1 0

2 0 1 0 1 P =

3 1 0 1 0

4 0 1 0

            

           

9. (a) Reflexive: R ij = R ij for all i, j, therefore R ij  R ij .

A. Doerr

Antisymmetric: Assume R ij  S ij , nd S ij  R ij , for all 1  i, j  n  R ij = S ij for all 1  i, j  n  R = S.

Transitive: Assume R, S, and T are matrices where R ij  S ij , and S ij  T ij for all 1  i, j  n.

Then R ij  T ij for all 1  i, j  n, and so R  T.

(b) (R2)ij = Ri1R1j + Ri2R2j + … + RinRnj ≤ Si1S1j + Si2S2j + … + SinSnj = (S

2)ij  R2 ≤ S2 To verify that the converse is not true we need only one example. For n = 2, let R12 = 1 and all other entries equal 0, and let S be the zero matrix. Since R2 and S2 are both the zero matrix, R2 ≤ S2, but since R12 > S12, R ≤ S is false.

(c) The matrices are defined on the same set A = {a1, a2, …, an}. Let c(ai), i = 1, 2, …, n be the equivalence classes defined by R and let d(ai) be those defined by S. Claim: c(ai)  d(ai). Let aj  c(ai)  airaj  Rij = 1  Sij = 1  aisaj  aj  d(ai).

Section 6.5

3. (a)

(b) Example, l s+ 4 and using the relation s one can go from I to 4 using a path of length 3.

5. (a) Definition: Reflexive Closure. Let r be a relation on A. A reflexive closure of r is the smallest reflexive relation that contains r. Theorem: The reflexive closure of r is the union of r with {(x, x): x G A}

7. (a) By the definition of transitive closure, r+ is the smallest relation which contains r; therefore,

it is transitive. The transitive closure of r+, (r+)+, is the smallest transitive relation that contains r+. Since r+ is transitive, (r+)+ = r+. (b) The transitive closure of a symmetric relation is symmetric, but it may not be reflexive. If one element is not related to any elements, then the transitive closure will not relate that element to others.

A. Doerr

Supplementary Exercises-Chapter 6 1. If Andy is the parent of Barbara and Barbara is the parent of Charles, then Andy is the grandparent of Charles. 3. (a) r = {(-1,0), (0, 1), (1,2)} (b) s = {(-1, -1), (-1, 1), (0, 0), (1, -1), (1, 1), (2, 2)}

(c) t = {(-1, 0), (-1, 1), (-1, 2), (0, -1), (0, 1), (0, 2),(1, -1), (1,0), (1,2), (2, -1), (2, 0), (2, 1)} 5. His main office should be at node 2. The least desirable location is at node 1. The arrows in both

directions between nodes I and 2 represent a two-way street. 7. (a) No.

(b) Person a is friendly toward the most people so he/she would be chairperson. (c) If "great personality" has any effect then person b becomes chairperson. (d) A seating arrangement does not exist, since persons c and d are only friendly toward one person each and they have to be seated between two people they are friendly toward.

9. In order for the relation "living in the same house" to be an equivalence relation we must assume that a person lives in only one house. 11. (a) r is an equivalence relation.

(b) s is neither since s is not reflexive. (c) In order for s to be a partial ordering we rephrase it slightly: xsy iff x taller than y or x equals y. Why would xsy iff x is the same height as or taller than y be wrong?

13. There are 16 places in the adjacency matrix for a relation on four elements, but for a symmetric relation those entries below the diagonal will be the same as above. Hence we are only concerned with 16 - 6 = 10 places. Each of the remaining entries may take on a value of either 0 or 1, so by the rule of products we have 210 possible symmetric relations on a four element set.

15.

(b) (i) {(a, a), (a, b), (b, a), (b, b), (c, c)} (ii) {(a, a), (a, c), (c, a), (c, b), (c, c)}

1 1 0

0 0 1

        

(ii) R2 =

1 1 1

0 0 0

1 1 1

        

A. Doerr

17. (a)

(b) r is not reflexive, not symmetric, not antisymmetric, and not transitive.

1 0 1 1

0 1 0 0

0 0 1 0

1 0 1 1

           

19. (a) A5 is friendly to no one. (b) The U.S. Ambassador (Ai) should be the chairman of this committee, since he is friendly

toward the most people. (c) The U.S. Ambassador can communicate to everyone on the committee.