已用)2009离散数学考试试题A
中山大学软件学院2009级软件工程专业（2009春季学期）
《离散数学》期末试题(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
(2) Find all the minimal elements, the maximal elements, the least element and the greatest
element of the poset
(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
C D E 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.
Fig. 1. The transport network for question 7
Fig. 2. The graph for question 8