《离散数学》期末试题(A卷)
(考试形式:闭卷 考试时间:2小时)
《中山大学授予学士学位工作细则》第六条
考试作弊不授予学士学位
方向： 姓名： 学号：
出卷： 复核：
1. (10 points) A, B and C are sets, prove or disprove the following statements.
(1). if A – B = A – C, then B = C
(2). if A ´ B = A ´ C, A ¹ Æ, then B = C
2. (10 points) Write each of the following statements in terms of propositional variables, predicates, quantifiers and logical connectives. You can choose any propositional variables and predicates freely.
(1). If I like the course or the teacher, I will attend the class. (statement and its negation)
(2). For all students of our school, someone studies hard and has good score, someone studies hard and does not have good score.
Note: The first question is expressed in propositional logic, the second is expressed in predicate logic.
3. (15 points) Let A={a,b,c,d,e}, a relation R on A is {(a,b), (b,b), (b,c), (b,d), (c,d), (d,d), (d,e), (e,d)}.
(1) Give the digraph and matrix of relation R;
(2) Compute R2, reflexive closure r(R) and symmetric closure s(R).
4. (15 points) Let SÎZ+ and A=S×S. Define the following relation R on A:
(a,b) R (a′,b′) if and only if ab′=a′b
(1) Show that R is an equivalent relation;
(2) Let S={1,2,3,4,5,6,7,8,9}, compute the equivalent class [(2,4)].
5. (10 points) Let function f(x, y)=( x+3y, 2x+y), (x, y)ÎR×R, prove that f is bijection.
6. (15 points) Let A={2, 4, 5, 6, 8, 10, 12, 20, 120}, R is the relation of divisibility on A.
(1) Draw the Hasse diagram of the poset <A, R>;
(2) Find all the minimal elements, the maximal elements, the least element and the greatest element of the poset <A, R> if they exist;
(3) Let B = {2, 4, 6}, find the upper bound, the lower bound, the least upper bound and the greatest lower bound of B if they exist.
7. (15 points) Use the labeling algorithm (Ford-Fulkerson’s) to find a maximum flow for the following transport network in Fig. 1. Use of figures is required to show the variety of flows during the procedure.
8. (10 points) Use Kruskal’s algorithm to find a minimal spanning tree of graph in Fig. 2. The sequence of edges-selecting is ordered to be shown up.
