discrete math test review

Math 2305 Review Questions for Test 2 Covering Chapters 3

1. Let 2

{ : 36}S n n=   and R be a relation from S to S defined by {( , ) : (mod 3)}R m n m n= 

a. List all numbers in S .

b. List all points in R . c. Specify which of the properties (R), (AR), (S), (AS), and (T) the relation satisfies.

d. Draw a digraph, G , for this relation.

e. Name each edge of your digraph, then create a table to show the function : ( ) ( ) ( )E G V G V G →  for .R

f. Give a closed path of length 2, 3, and 4 respectively. g. Give a cycle if there is any. h. Give an acyclic if there is any.

i. How many loops does G have?

j. Give the adjacency matrix of G .

k. Find the converse relation, R 

, and the adjacency matrix of the converse relation. l. Specify which of the properties (R), (AR), (S), (AS), and (T) the converse relation satisfies.

2. Let {1, 2, 3, 4}S = and R be a relation from S to S defined by {( , ) : }R m n m n S= +  . Do the same problems listed

in #1.

3. Draw a picture of the digraph G with a vertex set ( ) { , , , }V G w x y z= , an edge set ( ) { , , , , , , }E G a b c d e f g= , and

 given by the following table:

e a b c d e f g

( )e ( , )x w ( , )w x ( , )x x ( , )w z ( , )w y ( , )w z ( , )z y

Which of the following vertex sequence describe paths in the digraph? a. x w z y b. w x x w z y c. y z w x x

4. Let 1

R and 2

R be relations on a set S . Prove or disprove.

a. Must 1 2

R R be reflexive if 1

R and 2

R are?

b. Must 1 2

R R be symmetric if 1

R and 2

R are?

c. Must 1 2

R R be transitive if 1

R and 2

R are?

5. Let A = 

 



 

1 2 4

-1 3 0 and B =



 



 

2 2

1 -1 . Determine if AB and BA are defined. Find the product which is defined.

6. If A and B are matrices, is always AB=BA? Explain.

7. Let A =

−



  





  

3 2 1

4 0 5

1 3 3

and B = −





  





  

2 1 7

1 0 2

3 3 4

. Find -3A+5BT.

8. Given

Perform the indicated operations:

a. Find 2A-BT. b. Find AB c. Find BA

9. For the matrix, draw a digraph having the matrix:

0 0 2 1

3 0 1 0

0 1 0 0

0 0 0 1

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

.

1 2 3 4 0

3 0 , , 2 0 0

0 4

A B

  −  

= − =      

 

10. Write a matrix for the graph:

11. True or false, please explain: Let {0,1, 2, 3, 4, 5, 6, 7, 8}S =

a. {{6,1}, {2,5,8}, {4,2}, {4,3,0}, {3,7}} is a partition of S .

b. {{6,1}, {5,8}, {4,2}, {3,7}} is a partition of S .

c. {{6,1}, {5,8}, {4,2,0},{3,7}} is a partition of S .

12. Let ~ be an equivalent relation on a set S . Prove that the following assertions are equivalent: ,s t S 

a. ~s t ;

b. [ ] [ ]s t= ;

c. [ ] [ ]s t   .

13. Let ( ) cos , 2

n f n n

 =  . A relation on is defined as ~m n if and only if ( ) ( ), ,f m f n m n=   .Prove that ~

is an equivalence relation. Then find all equivalence classes. 14. Given m=2167, n=-400, find q and r satisfying the Division Algorithm.

15. Use x   to find DIV n m and MOD n m for

a. n=31, m=7 b. n=-31, m=7

16. Let ', ', , ,m n m n  and p P . Prove that if ' (mod )m m p and ' (mod )n n p ,then

a. ' ' (mod )m n m n p+  +

b. ' ' (mod )m n m n p  

17. List numbers in (5)Z and 5

[ ] ,n n . Then complete the 5

+ and 5  tables in (5)Z :

5 + 0 1 2 3 4

5  0 1 2 3 4

0 0

1 1

2 2

3 3

4 4

a. Find the additive identity and multiplicative identity of (5)Z .

b. Find the additive inverse of each element of (5)Z .

c. Find the multiplicative inverse of each element of (5)Z .

d. Find 5

2 2+

e. Find 5

2 2

f. Find x in (5)Z : 5

2 0x+ =

g. Find x in (5)Z : 5

2 0x =

18. Prove that the following statements are equivalent: Let m and n be integers and p be positive integer.

a. m n− is divisible by .p

b. m divided by p and n divided by p have the same remainder.

c. m n− is a multiple of .p

1 v