《离散数学》课程教学资源（试卷习题）试卷（答案）01

一、填空20%（每小题2分） 1、{0,1,2,3,4,6:2、(B⊕C)-A:3、1:4、(-PVSVR)A(Pv-SvR) 5、1:6、{,,2,2>,2,4:7、{a.b>,,eR由R对称性知,∈R 由R传递性得∈R “-”若eR,∈R有eR任意a,beX,因∈R 若∈R∈R所以R是对称的 若∈R,∈R则eRAeR∴eR即R 是传递的。 2、证a,beC,有f(a)=g(a,fb)=gb),又fb)=-f(b),g(b)=g'(b) ∴fb-)=-(b)=g(b)=gb-) fa★b-)-f(a)*f-(b)-g(a)*g(b-)-g(a★b-) .a★b-eC 是的子群。 3、证： 6

60105dfca3d04de78d0fae2fb259d7ed.doc 6 一、填空 20% （每小题 2 分） 1、{0，1，2，3，4，6}； 2、(B  C) − A ；3、1； 4、(P  S  R)  (P  S  R) ； 5、1；6、{, , , }；7、{,,,,}  IA ；8、 9、a ；a , b , c ,d ；a , d , c , d ；10、c; 二、选择 20% （每小题 2 分） 题目 1 2 3 4 5 6 7 8 9 10 答案 C D B、C C A D C A D B A 三、证明 26% 1、 证： “” a,b,c  X 若 , R 由 R 对称性知 ,R “ ” 若 R ， R 有 R 任意 a,b  X ，因 R 若 R  R 所以 R 是对称的。 若 R ， R 则 R   b,c R  R 即 R 是传递的。 2、 证 a,b C ，有 f (a) = g(a), f (b) = g(b) ，又 ( ) ( ), ( ) ( ) 1 1 1 1 f b f b g b g b − − − − = = ( ) ( ) ( ) ( ) −1 −1 −1 −1  f b = f b = g b = g b  f (a ★ b ) f (a)* f (b) g(a)* g(b ) g(a 1 1 1 = = = − − − ★ ) −1 b a ★ b C −1  是 的子群。 3、 证：

①设G有r个面，则2e=立d)2k,即r≤2。面v-e+r=2故 2=-e+r5-e+华即得e52.（8分 k-2 3微得南国为=5=1v=0,送：5不之 所以彼得森图非平面图。(3分) 二、逻辑推演16% 1、证明： ①A P(附加前提)》 ②AVB TOI ③AVB→CAD p ④CAD T②③】 ⑤D T④I ©DVE T⑤I ⑦DVE→F ⑧F T⑥⑦1 ⑨A→F CP 2、证明 ①rPx) P(附加前提) ②P(c) US① ③x(P(x)→Qx》p ④P(c)→Q(c) US③

60105dfca3d04de78d0fae2fb259d7ed.doc 7 ① 设 G 有 r 个面，则 e d F rk r i =  i  =1 2 ( ) ， 即 k e r 2  。 而 v −e + r = 2 故 k e v e r v e 2 2 = − +  − + 即得 2 ( 2) − −  k k v e 。（8 分） ②彼得森图为 k = 5,e = 15,v = 10，这样 2 ( 2) − −  k k v e 不成立， 所以彼得森图非平面图。（3 分） 二、 逻辑推演 16% 1、 证明： ① A P（附加前提） ② A  B T①I ③ A B →C  D P ④ C  D T②③I ⑤ D T④I ⑥ D  E T⑤I ⑦ D E → F P ⑧ F T⑥⑦I ⑨ A → F CP 2、证明 ① xP(x) P（附加前提） ② P(c) US① ③ x(P(x) → Q(x)) P ④ P(c) → Q(c) US③

60105dfca3d04de78d0fae2fb259d7ed.doc ⑤Q(c) T②④I ⑥xQx) UG⑤ ⑦VxPx)→VxQ(x) CP 三、计算18% 1、解： 010 0 1010 101 0 0101 MR= 0 00 1 Me =MRoMR= 0000 0000 0000 0101 1010 Me=MeMR= 0000 000 0 1010 1111 0101 1111 Me =MRoMR= 0000 MI(R)=MR+Me +Me+Me 0001 0000 0000 .t(R)={,,,,,,, ,} 2、解：用库斯克(Kruskal)算法求产生的最优树。算法略。结果如图： 1 2 23 V6 9 9W3 V7 5174 树权C(T=23+1+4+9+3+17=57即为总造价。 8

60105dfca3d04de78d0fae2fb259d7ed.doc 8 ⑤ Q(c) T②④I ⑥ xQ(x) UG⑤ ⑦ xP(x) → xQ(x) CP 三、 计算 18% 1、 解：               = 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 M R ，               = = 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 M R 2 M R M R                = = 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 M R 3 M R 2 M R  ，               = = 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 M R 4 M R 3 M R                = + + + = 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 3 4 Mt(R) M R M R M R M R  t (R)={ , , , , , , , , } 2、 解： 用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图： 树权 C(T)=23+1+4+9+3+17=57 即为总造价