Vectors and Vector Operations



6. Relations

When we were talking about logic earlier we considered predicates. These were rules (or functions) that took one or more objects and returned a value of true or false depending on whether or not the object(s) had some property or were related in some fashion. Consider, for example, the "Is-the capital-of" predicate.

"Is-the-capital-of"(x, y) =

For example,

"Is-the-capital-of"(Lansing, Michigan) = true

"Is-the-capital-of"(Detroit, Michigan) = false

When we talked about predicates they were used in forming statements that could be classified as true or false. In this chapter we are going to be looking at predicates again. However, now they are called relations. In programming languages =, ≠, and ≥ are called the relational operators. These are a special type of predicate that take two objects of the same type and return true or false. The predicates in this chapter are similar to the relational operators in that they take two objects of the same type and return true or false. We shall concentrate on two special types of relations, namely equivalence relations and partial orderings.

6.1 Equivalence Relations

In this section we shall be looking at equivalence relations. These are generalizations of equality. An equivalence relation determines whether two objects are the same in some respect or have some common property. Often this means that one object can be substituted for the other in various situations.

Before giving a precise definition of an equivalence relation, let's look at some examples of relations that are equivalence relations.

Example 1. Fractions. A fraction is the ratio of two integers with a non-zero denominator q. For example, , and are typical fractions. Note that we would usually write = . What we mean is that we think of them as representing the same number. Technically speaking they are different objects. For example, might represent cutting a pie in two equal pieces and taking one while might represent cutting a pie in four equal pieces and taking two. The fact that we end up with the same amount of pie in both cases is why we often think of and as the same. In general two fractions and represent the same number if pm = qm.

The reason for this is the following. Consider the following four scenarios.

i. Think of cutting a pie into q pieces and taking p of them. This is represented by the fraction .

ii. Now take an identical pie and cut it into qm pieces and take pm pieces. This is represented by the fraction . We get the same amount of pie as in the first case. So should be equal to .

iii. Again, take an identical pie and cut it into m pieces and taking n of them. This is represented by the fraction .

iv. Finally, take an identical pie and cut it into qm pieces and take qn pieces. This is represented by the fraction . We get the same amount of pie as in the third case. So should be equal to .

Now compare the the second and fourth cases. In both of these cases we have cut the pie into qm pieces. We will get the same amount of pie if pm = qn. So we are led to the conclusion that and represent the same number if pm = qn.

We write if pm = qn, although we don't mean and are the same object. For example, we write .

Example 2. Equivalent algebraic expressions. In high school algebra one does a lot of work with equivalent algebraic expressions. For example, (x + 1)(x + 2) and x2 + 3x + 2 are equivalent algebraic expressions and we usually write (x + 1)(x + 2) = x2 + 3x + 2. This does not mean they are the same. It only means that we get the same result if we substitute the same number into each. For example, if we substitute x = 3 into each we get (3 + 1)(3 + 2) = (4)(5) = 20 and 32 + (3)(3) + 2 = 9 + 9 + 2 = 20 which are the same. One place where one substitutes an expression which is equivalent for another is when one is solving equations. For example, if we are solving the equation x2 + 3x + 2 = 2 the we can substitute (x + 1)(x + 2) for x2 + 3x + 2 to get (x + 1)(x + 2) = 0 and then conclude that x = - 1 or x = - 2.

Example 3. Equivalent logical expressions. A logical expression is a combination of logical variables (e.g. p, q, etc), logical operations (e.g. and, or, not, etc.), logical constants (0 and 1) and parentheses. For example, (pq)', p' + q' and p ( q are logical expressions. Two logical expressions are equivalent if they have the same truth table. For example, (pq)' and p' + q' are equivalent since their truth tables are the same. We have been writing (pq)' = p' + q' to indicate that they are equivalent. One place where one substitutes an expression which is logically equivalent to another is when one is designing a logic circuit where all we care about is the logical value of the output. If one part of the circuit is represented by p' + q' then we can substitute a NAND gate (pq)'.

Example 4. Numbers congruent mod 12. Earlier we have seen several situations where we mod the result of an arithmetic calculation involving additions, subtractions and multiplications by some number p to get the final result. In this case, during the calculation we can replace any number by another number that has the same remainder when we divide by p. In this context the two numbers are equivalent.

To make this concrete, let's suppose p = 12. Thus we are working with numbers on a clock. We say two integers n and m are equivalent mod 12 if they have the same remainder when we divide by 12, i.e. n mod 12 = m mod 12. Let's write n ( m if this is the case. For example 15 ( 27 since both have a remainder 3 when we divide by 12. In terms of clocks, the clock reads the same if 15 hours pass as if 27 hours pass. However, 15 29 since 15 has remainder 3 when we divide by 12 and 29 has a remainder 5 when we divide by 12. The clock does not read the same if 15 hours pass as if 29 hours pass. Equivalence mod 12 is another example of an equivalence relation.

Example 5. ( for expressions. Earlier when we were comparing algorithms we defined what it meant for two expressions to be of the same order as n ( (. If Sn and Tn are two expressions involving n and 0 < < ( then they are of the same order as n ( ( and we write Sn = ((Tn). For example, n2 + 3n + 2 = ((n2), but n ( ((n2). Being of the same order is another example of an equivalence relation.

Example 6. Congruence for Triangles. Two triangles (ABC and (DEF are congruent if corresponding angles are equal and the lengths of corresponding sides are equal, i.e. (A = (D, (B = (E, (C = (F, = , = and = . Here denotes the length of the line segment joining A and B. Congruence of triangles is another example of an equivalence relation.

Example 7. Similarity for Triangles. Two triangles (ABC and (DEF are similar if corresponding angles are equal and the lengths of pairs of corresponding sides are proportional, i.e. (A = (D, (B = (E, (C = (F and = = . Similarity of triangles is another example of an equivalence relation.

Example 8. Same number of elements for sets. In some situations we consider two sets A and B as equivalent if they have the same number of elements. Let's write A ( B if A and B have the same number of elements. For example, {a, b, c} ( {e, f, g} but {a, b, c}  {e, f}. This is also an equivalence relation.

Example 8. Have the same two parents. We say two people are siblings in the strong sense if both parents are the same. This is an equivalence relation.

Example 9. Give the same output for the same input. We say two C++ functions are equivalent if they return the same value if they are given the same arguments.

People reflecting on examples such as these noticed that all these relations had three properties in common. Relations that have these three properties are now called equivalence relations.

Definition 1. A relation is an equivalence relation if it has the following three properties.

i. It is transitive

ii. It is symmetric

iii. It is reflexive

A relation ( is transitive if whenever one has both a ( b and b ( c then one also has a ( c. A relation ( is symmetric if whenever one has a ( b then one also has b ( a. A relation ( is reflexive if a ( a for every object a.

Often it is easy to verify that a certain relation has these three properties and is, therefore, an equivalence relation. In other cases verifying one or the other of these properties may require some work. This is particularly true of the transitive property. Let's see how these definitions work for the examples above.

Example 10 - Equivalent logical expressions. Two logical expressions are equivalent if they have the same value for every combination of values of the variables appearing in them. Let's show this is transitive. Suppose P, Q and R are logical expression with P = Q and Q = R. Then P and Q have the same value for every combination of values of the variables and Q and R also have the same value for every combination of values of the variables. Therefore, P and R have the same value for every combination of values of the variables. So P = R. This shows the relation is transitive. Now let's show it is symmetric. Suppose P = Q. Then P and Q have the same value for every combination of values of the variables. Therefore, Q and P have the same value for every combination of values of the variables. So Q = P. This shows the relation is symmetric. Finally to show reflexive, we must show P = P for any P. This is true since P and P have the same value for any combination of values of the variables. So the relation is reflexive. So equivalence of logical expressions meets the three requirements of an equivalence relation.

This proof that equivalence of logical expressions is an equivalence relation works with minor modifications for most of the other relations in the examples above since they say that two objects bear the relation to each other if something computed from each is the same. However, with equality of fractions one needs to use a different argument.

Example 11 – Equality of fractions. In this case means pm = nq. Let's show this is transitive. Suppose and . Then pm = nq and ns = mr. If we multiply the first by s and the second by q we get pms = nqs and nqs = mqr. So pms = mqr. Dividing by m gives ps = qr. So . This shows the relation is transitive. Now let's show it is symmetric. We must show implies . The first implies pm = nq and to show the second we need nq = pm. However, these are the same so the relation is symmetric. Finally to show reflexive, we must show . To show this we must show pq = pq. Since this is true the relation is reflexive. So equality for fractions meets the three requirements of an equivalence relation.

Equivalence Classes

Often when we have an equivalence relation we really want to treat equivalent objects as equal. For example, if we are dealing with fractions then we might want to treat and as the same object. Equivalence classes is one way to do this in a systematic fashion.

Let’s suppose we have an equivalence relation and let’s denote it by (. So if two objects x and y are related we write x ( y. An equivalence class is a set of objects that are all related to each other. We include in the set all objects related to the objects in the set. One way to form an equivalence class is to pick an object and form the set of all objects related to x. This is called the equivalence class of x and denoted by [ x ]. Thus

[ x ] = {y: x ( y}

Let’s look at some examples.

Example 1 (continued) fractions.

-----------------------

|p |q |pq |(pq)' |p' |q' |p' + q' |

|0 |0 |0 |1 |1 |1 |1 |

|0 |1 |0 |1 |1 |0 |1 |

|1 |0 |0 |1 |0 |1 |1 |

|1 |1 |1 |0 |0 |0 |0 |

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download