# Discrete Mathematics and Functions

See the attached file.

1. Let f be any function from R to R. Define a relation Rf by the rule: x Rf y if and only if f(x) = f(y). Show that Rf is an equivalence relation. (Hint 1: first consider a simple specific case, such as f(x) = x2. That is, x and y are related if and only if x2 = y2. Then consider the general case. Hint 2: Think about contour lines on a map.)

2: For the special case f(x) = x2 of Problem 2, what are the equivalence classes? (Hint: Check out some special cases. Which numbers are related to 0? Which numbers are related to 7? Which numbers are related to -5?)

3: Consider three sets A, B, and C, where A has 7 elements, B has 5 elements, and C has 2 elements. How many (ternary) relations are there on the sets A, B, C?

4. Suppose that the directed graph below were the reduced graph of a partial order relation. What edges would you have to add to this graph to create the full graph of the partial order relation? (You will probably want to sketch this on paper, but in responding, you don't have to provide an illustration, just list the edges to be added.)

5. Define a relation on the squares of a chessboard by saying that two squares are related if an only if a bishop can get from one square to the other by a sequence of legal moves? This is clearly an equivalence relation. How many equivalence classes are there?

Describe them.

(Info for non-chess players: a chessboard is the same thing as a checkerboard and is 8 x 8. A bishop can only move diagonally.)

Question for discussion: You may have noticed that I have freely batted around the word counterexample. What does this word mean? Can you give some examples of counterexamples from everyday life?

Â© BrainMass Inc. brainmass.com September 27, 2022, 4:39 pm ad1c9bdddfhttps://brainmass.com/computer-science/c/discrete-mathematics-functions-469335

## SOLUTION This solution is **FREE** courtesy of BrainMass!

See attached file.

Problem #1

Proof: To show that R_f is an equivalent relation, we need to prove the following properties.

Reflexive

For any xâˆˆR_f, we have f(x)=f(x) and thus x R_f x.

Symmetric

If x R_f y, then f(x)=f(y), then f(y)=f(x) and thus y R_f x.

Transitive

If x R_f y and y R_f z, then we have f(x)=f(y) and f(y)=f(z). Thus f(x)=f(z) and hence we get x R_f z.

Therefore, R_f is an equivalent relation.

Problem #2

From problem #1, the equivalent class is {x,-x} for each xâˆˆR because f(x)=x^2=ã€–(-x)ã€—^2=f(-x). So we have the following examples of equivalent class.

The equivalent class of 0 is {0}; the equivalent class of 7 is {7, -7}; the equivalent class of -5 is {5, -5}.

Problem #3

Answer: 70

The ternary relation has the form (a,b,c), where a is in A, b is in B and c is in C. From the condition, we have 7 choices of a, 5 choices of b and 2 choices of c. Thus the total number of ternary relation is 7*5*2 = 70.

Problem #4

We need to add 5 edges: (a,d), (a,a), (b,b), (c,c), (d,d).

The edge (a,d) is from a to d and this edge works for transitivity. The other 4 edges work for reflexivity.

Problem #5

There are two equivalent classes. One is the set of all white-color box and the other is the set of all black-color box. Because if a bishop stands in a white-color box, it can only move to any white-color box; if a bishop stands in a black-color box, it can only move to any black-color box.

Question for discuss

Counterexample is an example to prove false of a statement.

Statement: Every credit card has 16 digit account.

Counterexample: American express card is a credit card, but it has 11 digit account.

https://brainmass.com/computer-science/c/discrete-mathematics-functions-469335