( 密 封 线 内 不 答 题 ) ???????????????密??????????????????封???????????????线??????????????
诚信应考,考试作弊将带来严重后果！
华南理工大学期末考试
《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={
(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 = {
《 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 页