试卷代号：1009 座位号■■ 国家开放大学（中央广播电视大学）2015年春季学期“开放本科”期末考试 离散数学（本）试题（半开卷）】 2015年7月 题 号 二 三 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题（每小题3分，本题共15分） 1.若集合A={1,2,3},则下列表述正确的是(). A.{1,2,3}∈A B.AC{1,2} C.{1,2,3}二A D.{1,2}∈A 2.已知无向图G有10条边，则G的结点度数之和为(). A.10 B.20 C.30 D.5 3.无向图G是棵树，边数为10，则G的结点数是( A.5 B.10 C.9 D.11 4.设A(x):x是金属，B(x):x是金子，则命题“有的金属是金子”可符号化为(). A.(3 x)(A(x)AB(x)) B.(Hx)(A(x)→B(x) C.(Y x)(A(x)AB(z)) D.7(3x)(A(x)∧B(x)) 5.下面的推理正确的是( ) A.(1)(Hx)F(x)+G(x) 前提引人B.(1)(3x)F(x)+G(x) 前提引人 (2)F(y)→G(y) US(1) (2)F(y)+G(y) US(1) C.(1)(3x)(F(x)→G(x)) 前提引人D.(1)(]x)(F(x)+G(x)) 前提引人 (2)F(y)+G(y) ES(1) (2)F(y)+G(x) ES(1) 89
试卷代号 :1009 座位号仁口 国家开放大学(中央广播电视大学)2015 年春季学期"开放本科"期末考试 离散数学(本) 试题(半开卷} 2015 一、单项选择题{每小题 分，本题共 15 分} 1.若集合 A= {l， 3} 则下列表述正确的是( ). A. {1 ,2 3}εA B. AC{l ,2} c. {l, 2 , 3 } cA D. {l, 2}εA 2. 已知无向图 10 条边，则 的结点度数之和为( ). A.10 B.20 C.30 D.5 3. 元向图 是棵树，边数为 10 ，则 的结点数是( ). A.5 B.10 C. 9 D. 11 4. A(x) :x 是金属 B(x) :x 是金子，则命题"有的金属是金子"可符号化为( ). A. ( 3 x)(A(x) B(x)) c. ( V x) (A(x) B(x)) 5. 下面的推理正确的是( ). A. (1)( V x)F(x)• G(x) (2)F(y)• G(y) B.寸 (V x)(A(x)• B(x)) D. 寸(丑 x)(A(x) ^ -, B(x)) 前提引人 B. (1)( 3 x)F(x)• G(x) US(1) (2)F(y)• G(y) 前提引人 US(1) C. (1)( 3 x)(F(x)• G(x)) 前提引人 D. (1) ( 3 x)(F(x)• G(x)) 前提引入 (2)F(y)• G(y) ES(1) (2)F(y)• G(x) ES(I) 89
得分 评卷人 二、填空题（每小题3分，本题共15分） 6.设A={1,2},B={a,b,c},作f:A→B,则不同的函数个数为 7.有n个结点的无向完全图的边数为 8.设无向图G中存在欧拉回路，则G的奇数度数的结点数为 个. 9.设G是有8个结点的连通图，结点的度数之和为24，则可从G中删去 条边后使之变成树， 10.设个体域D={a,b,c},则谓词公式(Hx)A(x)消去量词后的等值式为 得 分 评卷人 三、逻辑公式翻译（每小题6分，本题共12分） 11.将语句“学生的主要任务是学习”翻译成命题公式. 12.将语句“我们下午2点或者去礼堂看电影或者去教室看书.”翻译成命题公式· 得 分 评卷人 四、判断说明题（判断各题正误，并说明理由。每小题7分，本题共 14分) 13.不存在集合A与B,使得A∈B与A二B同时成立. 14.完全图K4(如下图)是平面图. 得 分 评卷人 五、计算题（每小题12分，本题共36分）】 15.设偏序集的哈斯图如下图所示，B为A的子集，其中B={a,b,c},试 (1)写出R的关系表达式： (2)画出关系R的关系图； 90
|得分|评卷人| | 二、填空题{每小题 分，本题共 15 分} 6. A= {1 , 2} ,B= {a 叶，作 /:A 则不同的函数个数为 7. 个结点的无向完全图的边数为 8. 设元向图 中存在欧拉回路，则 的奇数度数的结点数为 个. 9. 是有 个结点的连通，图，结点的度数之和为 24 ，则可从 中删去 条边后使之变成树. 10. 设个体域 D={a ，c} 则谓词公式(V x)A(x) 消去量词后的等值式为 三、逻辑公式翻译{每小题 分，本题共 12 分} 1.将语句"学生的主要任务是学习"翻译成命题公式. 12. 将语句"我们下午 点或者去礼堂看电影或者去教室看书"翻译成命题公式. |得分|评卷人| | 四、判断说明题{判断备题正误，并说明理由。每小题 分，本题共 14 分} 13. 不存在集合 使得 AεB ACB 同时成立. 14. 完全图 如下图〉是平面图. |得分|评卷人| | 五、计算题{每小题 12 分，本题共 36 分} 90 15. 设偏序集 的哈斯图如下图所示 的子集，其中 B= {a ，c}， (1)写出 的关系表达式; (2) 画出关系 的关系图;
(3)求出B的最大元素、极小元素、上界. d b 16.设图G=,V={v1,2,34,5},E={(01,2),(0,),(U,5),(v2,u）, (,s)},试 (1)画出G的图形表示； (2)写出其邻接矩阵； (3)求出每个结点的度数； (4)画出图G的补图的图形， 17.求P→(Q∧R)的析取范式与主合取范式. 得分 评卷人 六、证明题（本题共8分】 18.设A,B,C均为任意集合，试证明：A∩(B-C)=(A∩B)-(A∩C). 91
(3) 求出 的最大元素、极小元素、上界. d b C 1U((((1 E U U U U U U U U U |得分|评卷人| | 六、证明题{本题共 分} 18. A.B.C 均为任意集合，试证明 :A (B-C)=(AnB) (An C). 91
试卷代号：1009 国家开放大学（中央广播电视大学）2015年春季学期“开放本科”期末考试 离散数学（本） 试题答案及评分标准（半开卷） (供参考) 2015年7月 一、单项选择题（每小题3分，本题共15分】 1.C 2.B 3.D 4.A 5.C 二、填空题（每小题3分，本题共15分）】 6.9 7.n(n-1)/2 8.0 9.5 10.A(a)∧A(b)∧A(c) 三、逻辑公式翻译（每小题6分，本题共12分） 11.设P:学生的主要任务是学习. (2分) 则命题公式为：P. (6分) 12.设P:我们下午2点去礼堂看电影， Q:我们下午2点去教室看书· (2分) 则命题公式为：一(P+Q) (6分) 注：或者(P∧Q)V(PA-Q) 四、判断说明题（每小题7分，本题共14分） 13.错误. (3分) 例：设A={a},B={a,{a} (5分) 则有A∈B且A二B. (7分) 说明：举出符合条件的反例均给分· 14.正确. (3分) 完全图K,是平面图， (5分) 92
试卷代号 :1009 国家开放大学(中央广播电视大学 )2015 年春季学期"开放本科"期末考试 离散数学(本) 试题答案及评分标准(半开卷) (供参考) -、单项选择题{每小题 分，本题共 15 分} l. C 2. B 3. D 二、填空题{每小题 分，本题共 15 分} 6.9 7.n(n 1)/2 8.0 9.5 10. A(a) A(b) A(c) 三、逻辑公式翻译{每小题 分，本题共 12 分} 1.设 P: 学生的主要任务是学习. 则命题公式为 :P. 12. P: 我们下午 点去礼堂看电影， 也我们下午 点去教室看书. 则命题公式为 :--， (p......Q). 注:或者 (-， Q) V (P ^ -,Q) 四、判断说明题(每小题 分，本题共 14 分} 13. 错误. 92 例:设 A={a} B= 忡，{ a} } 则有 AεB ACB. 说明:举出符合条件的反例均给分- 14. 正确. 完全图 K4 是平面图， 4.A 5. C 2015 (2 分〉 (6 分) (2 分) (6 分) (3 分) (5 分) (7分〉 (3 分) (5 分)
如K,可以如下图示嵌入平面. (7分) 五、计算题（每小题12分，本题共36分） 15.(1)R={,,,,,,,, }. (4分) (2)关系图 (8分) (3)集合B无最大元素、极小元素为a、上确界为d. (12分) 16.解： (1)关系图 (3分) (2)邻接矩阵 010117 0 1001 000.01 (6分) 1100 0 10100 93
K4 可以如下图示嵌入平面. (7 分〉 五、计算题{每小题 12 分，本题共 36 分) 15. (l )R={ . c>. ， }. (2) 关系图 (3) 集合 元最大元素、极小元素为 、上确界为 d. 16. 解: (1)关系图 (2) 邻接矩阵 o 1 0 1 1 10010 o 0 0 0 1 1 1 000 II 0 1 0 0 V1 ν3 (4 分) (8 分) (1 2 分) (3 分〉 (6 分) 93
(3)deg(v1)=3 deg(v2)=2 deg(v3)=1 deg(v)=2 deg(vs )=2 (9分) (4)补图 (12分) 17.P-(QAR) PV(Q∧R)析取范式 (2分) PVQ)A(PVR) (5分) ÷(PVQ)V(RAR)∧(=PVR) (7分) (-PVQ)V(RA-R)A(-PVR)V(QA-Q) (9分) (PVQVR)A(-PVQV-R)A(-PVRVQ)A(-PVRV-Q) (11分) (-PVQVR)∧(-PVQV-R)∧(-PV-QVR) 主合取范式 (12分) 六、证明题（本题共8分）】 18.证明： 设S=A∩(B-C),T=(A∩B)-(A∩C) 若x∈S,则x∈A且x∈B一C,即x∈A,并且x∈B且xgC, (2分) 所以x∈(A∩B)且x(A∩C),得x∈T, (3分) 所以S三T. (4分) 反之，若x∈T,则x∈(A∩B)且xE(A∩C), (5分) 即x∈A,x∈B,且xgC,则得x∈B一C, (6分) 即得x∈A∩(B一C),即x∈S,所以T二S. (7分) 因此T=S. (8分) 另，可以用恒等式替换的方法证明， 94
(3)deg( Vl) = 3 deg( V2) =2 deg( )=1 deg( )=2 deg( )=2 (4) 00 170 (Q 八 R) ~PV (Q^ 的析取范式 (-.P V Q) 八(....， PV R) V1 (....， P V Q) V (R ^ ....,R) ^ (-,P V R) 。(-，PVQ) V (R 八-，R).^ (--,P V R) V (Q ^ -,Q) V3 (， V QV R) ^ (....,P V QV -,R) ^ (...,PV RV Q) ^ (-,P V R V ....,Q) (-,P V QV R) 八(-、PVQV -，R)八(-， PV ....， QVR) 主合取范式 六、证明题(本题共 分} 18。证明 94 S=An (B- C) , T=(A B) -(A C) , xES zεA xEB-C xEA 并且 xEB e;C , 所以 xE (Anm ~(A C) ，得 zε 所以 SCT. 反之，若 xET xE (An B) e; (AnC) , zξ A xEB e; 则得 zε B-C 即得 zε Ar (B-C) ，所以 TCS. 因此 T=S. 另，可以用恒等式替换的方法证明. (9 分) (1 分) (2 分) (5 分) (7 分) (9 分〉 (1 分) (1 分) (2 分) (3 分) (4 分〉 (5 分) (6 分) (7 分〉 (8 分)
