2012离散数学A卷

( 密 封 线 内 不 答 题 ) ???????????????密??????????????????封???????????????线??????????????

诚信应考,考试作弊将带来严重后果!

华南理工大学期末考试

《Discrete Mathematics》

note: 1. 考前请将密封线内填写清楚; 2. 所有答案请直接答在答题纸上; 3.考试形式:闭卷;

4. 本试卷共 4 大题,满分100分, 考试时间120分钟。 1.

Choose an answer to the following question. (10 x 2’ = 20’) (1) Which is a proposition? ( )

A) Is the water boiling? B) x > 1.5 C) There will be no water on the earth after 5000 years. D) Help me. (2) The implication is true for all possible assignments of truth values to p

Name Student ID _____________ ________ and q except for which assignment?( ) A)p false, q true B)p true, q false C)p false, q false D)p true, q true

(3)Which of these statements is a correct translation of the statement: “No Computer Science Major is taking any courses” where C(x) is the statement x is a Computer Science Major, and T(x, y) is the statement x is taking y. Assume that the universe for x is the set of all students and the universe for y is the set of all courses. ( )

A)C)

B) D)

(4) Function f is defined as f:Z?Z,f(x)?x?2x, so f is ( )

A)onto B) both onto and one-to-one C)one-to-one D) neither onto nor one-to-one (5) Supposed a binary relation R (Figure 1) on the set A = { 1, 2, 3 }, R is ( )

A) irreflexive, symmetric, non-transitive 1 C) irreflexive, antisymmetric, transitive Figure 1. D) reflexive, antisymmetric, non-transitive

2 3 B) reflexive, antisymmetric, transitive

(6) Which of these arguments is true?( )

A) (P(S), subset of) is a poset and also total ordered B) (Z+,|) is totally ordered

《 Discrete Mathematics 》试卷第 1 页 共 8 页

C) The divisibility relation(可整除) “ | ” is a partial ordering on the set of positive integers.(Z+,|) is a poset. D) (N, >=) is well-ordered (7) (A?B)?C = ( )

A) (A – C) ? B B) (A?C)?(B?C) C) A – (B?C) D) (A?C)∩(B?C)

(8) Which statement is correct? ( )

A) There are 2n 1s and n (n-2) 0s in the adjacency matrix for Cn. B) Cn is always bipartite .

C) Qn has n2n edges and 2n vertices. D) Kn has n (n+1)/2 edges and n vertices.

(9) How many planar graphs in the following graphs? ( )

A) 4 B) 3 C) 2 D) 1

(10) Which statement is wrong? ( )

A. If a directed graph is strongly connected, it must be an Euler graph. B. A graph with cut edge cannot be an Euler graph.

C. If a graph is an Euler graph, it must be a strongly connected graph. D. A graph with cut vertex cannot be a Hamilton graph.

2. Fill in the blanks. (10 x 2’ = 20’)

(1) If p?q is true, the truth value of p?q ?q is

(2) Let C(x): x is a computer. D(x): x is a peripheral equipment. P(x, y): x can communicate with y. Express the sentence “some computers can’t communicate with some peripheral equipment” as a logical expression as______________.

(3) Let l be “Lois works late”, let j be “John works late”, and let e be “they will

《 Discrete Mathematics 》试卷第 2 页 共 8 页

eat at home”. Express the statement “If Lois or John do not work late, then they will eat at home” __________________

(4)A={ l,m,n },B={ a,b,c },C={ x,y,z }. R:A→B,S:B→C,and R={ }, S={< a,y>,}, SоR =______________.

(5) A = { ?, {?}}, ?(A) is the power set of A. ?(A)=______________. (6) R is the real number domain. For ?x?R, f(x)?x?2, g(x)?x?2 and

h(x)?3x. Hence, h?(g?f)? _______________. (7) R is “ more than or equal to” relation on Z×Z,then R-1=________.

(8) R is the relation “brother or sister”, xRy represents “x is the brother or sister of y”, ① irreflexive ② reflexive ③ symmetric ④ antisymmetric ⑤ transitive. R has the properties _____. (9) The complete bipartite graph Km, n has ____ cut edges. (10) The sum of the weights of the minimum spanning tree for the graph in the right hand side is _____.

3. Computation and Analysis. (6 x 6’ = 36’) (1) Prove the equivalence of predicate:

(?x)(?y)(P(x)?Q(y))?(?x)P(x)?(?y)Q(y)

《 Discrete Mathematics 》试卷第 3 页 共 8 页

(2) Given the premises ?A∨B, ?C→?B, C→D, how to get the conclusion A→D?

(3) Suppose A = {a , b, c, d}, a relation on A is R = {, , , }. Please use the zero-one matrix to find the transitive closure of R.

《 Discrete Mathematics 》试卷第 4 页 共 8 页

?0?1MR???0??0100001000?0??1??0?

(4) Can the following graph be drawn in one stroke ? Why ?

(5) Find out whether G and H are isomorphic. No matter what the judgment is, please give your explanation and argument.

《 Discrete Mathematics 》试卷第 5 页 共 8 页

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4