试卷代号：1009 座位■■ 中央广播电视大学2009一2010学年度第一学期“开放本科”期末考试（半开卷） 离散数学（本）试题 2010年1月 题 号 三 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题（每小题3分，本题共15分）》 1.若集合A={a,{a}},则下列表述正确的是(). A.aCA B.{a}二A C.{a,{a}}∈A D.0∈A 2.命题公式(PVQ)的合取范式是(). A.(P∧Q) B.(PAQ)V(PVQ) C.(PVQ) D.(P∧Q) 3.无向树T有8个结点，则T的边数为(）. A.6 B.7 C.8 D.9 67
试卷代号:1009 座位号巨口 中央广播电视大学2009-2010学年度第一学期“开放本科”期末考试(半开卷) 离散数学(本) 试题 2010年 1月 题 号 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题{每小题 3分 ，本题共 15分) 1.若集合 A={ a, W }，则下列表述正确的是( ) A.<“}(-A B.{{{a}}} CA C. {a，{a}}任A D.必 任A 2.命题公式(尸VQ)的合取范式是 ( )。- A. (PAQ) B. (PAQ)V(PVQ) C. (PVQ) D. ，(，PA ，Q) 3.无向树 T有 8个结点，则 T的边数为( ). A. 6 B. 7 C. 8 D.9
4.图G如图一所示，以下说法正确的是(). A.a是割点 B.{b,c}是点割集 C.{b,d}是点割集 图 D.{c}是点割集 5.下列公式成立的为( A.PQ台PVQ B.P+7Q台P→Q C.Q→P→P D.P∧(PVQ)→Q 得分 评卷人 二、填空题（每小题3分，本题共15分） 6.设集合A={2,3,4},B={1,2,3,4},R是A到B的二元关系， R={|x∈A且y∈B且x≤y} 则R的有序对集合为 7.如果R是非空集合A上的等价关系，a∈A,b∈A,则可推知R中至少包含 等元素 8.设G=是有4个结点，8条边的无向连通图，则从G中删去 条边，可 以确定图G的-一棵生成树. 9.设G是具有n个结点m条边k个面的连通平面图，则m等于 10.设个体域D={1,2},A(x)为“x大于1”，则谓词公式（3x)A(x)的真值为 68
4.图G如图一所示，以下说法正确的是 ( A. a是割点 B. ( b,:}是点割集 C. (b, d}是点割集 D.{。}是点割集 5.下列公式成立的为( ). A. ，尸八 ，Q 片 尸VQ B. P- ”Q 拱 ， 尸~Q C. Q-P=>尸 D. ，PA (PV Q)=:>Q 图一 得 分 评卷人 二、填空题(每小题 3分.本题共 15分) 6.设集合A=(2, 3, 4),B=(1, 2, 3, 4},R是 A 到 B的二元关系， R=(IxEA且 YEB且x镇少 则R的有序对集合为 7.如果 R 是 非 空 集 合 A 上 的 等 价 关 系，aEA,bC- A，则 可 推 知 R 中 至少 包 含 等元素. 8.设 G= 是有 4个结点，8条边的无向连通图，则从 G中删去_ 条边，可 以确定图 G的一棵生成树. 9.设G是具有n个结点m条边k个面的连通平面图，则 m等于 10.设 个 体 域 D= 68 (1, 2},A(x)为“x大于 1"，则谓词公式 (3x)A(x)的真值为
得分评卷人 三、逻辑公式翻译（每小题6分，本题共12分） 11.将语句“今天考试，明天放假.”翻译成命题公式. 12.将语句“我去旅游，仅当我有时间.”翻译成命题公式. 得 分 评卷人 四、判断说明题（每小题7分，本题共14分】 判断下列各题正误，并说明理由. 13.如果图G是无向图，且其结点度数均为偶数，则图G是欧拉图. 14.若偏序集的哈斯图如图二所示，则集合A的最大元为a,最小元是f. 图二 得分 评卷人 五、计算题（每小题12分，本题共36分） 15.设集合A={(1},1,2},B={1,{1,2}},试计算 (1)(A-B); (2)(A∩B): (3)A×B. 16.设G=,V={,2,,w4},E={(h,),(2,h),(h,4),(,w)},试 (1)给出G的图形表示； (2)写出其邻接矩阵； (3)求出每个结点的度数； (4)画出其补图的图形 69
得 分 评卷人 三、逻辑公式翻译(每小题 6分 .本题共 12分 ) 11.将语句“今天考试，明天放假.”翻译成命题公式. 12.将语句“我去旅游，仅当我有时间.”翻译成命题公式. 得 分 评卷人 四、判断说明题 (每小题 7分，本题共 14分) 判断下列各题正误，并说明理由. 13.如果图G是无向图，且其结点度数均为偶数，则图G是欧拉图. 14.若偏序集的哈斯图如图二所示，则集合 A的最大元为a，最小元是f. 图二 得 分 评卷人 五、计算题(每小题 12分 。本题共 36分) 15.设集合 A二{{1},1,2},B = {1，{1,2}}，试计算 (1) (A一B); (2) (A门B); (3)AXB. 16.设 G= ,V={VI 9V2 9V3 9V4}，E={(v1,v3),(vz,v3),(V2 ,V4)，(v3 I V4 )}，试 (1)给出G的图形表示; (2)写出其邻接矩阵; (3)求出每个结点的度数; (4)画出其补图的图形
17.设谓词公式（3x)(A(x,y)→（Vx)B(y,x,x),试 (1)写出量词的辖域； (2)指出该公式的自由变元和约束变元. 得 分 评卷人 六、证明题（本题共8分） 18.设A,B是任意集合，试证明：若A×A=BXB,则A=B. 70
17.设谓词公式 (3 x) (A(x, y)-(d z)B勿,x,z))，试 (1)写出量词的辖域; (2)指出该公式的自由变元和约束变元. 得 分 评卷人 六、证明题 (本题共 8分) 18.设 A,B是任意集合，试证明:若 AXA=BXB，则 A=B
试卷代号：1009 中央广播电视大学2009一2010学年度第一学期“开放本科”期末考试（半开卷） 离散数学（本） 试题答案及评分标准 (供参考) 2010年1月 一、单项选择题（每小题3分，本题共15分）》 1.A 2.C 3.B 4.B 5.D 二、填空题（每小题3分，本题共15分） 6.{,,,,,} 7., 8.5 9.n十k-2 10.真（或T,或1） 三、逻辑公式翻译（每小题4分，本题共12分） 11.设P:今天考试，Q:明天放假， (2分) 则命题公式为：PAQ, (6分) 12.设P:我去旅游，Q:我有时间， (2分) 则命题公式为：P+Q (6分) 四、判断说明题（每小题7分，本题共14分） 13.错误. (3分) 当图G不连通时图G不为欧拉图. (7分) 14.错误 (3分) 集合A的最大元与最小元不存在，4是极大元，f是极小元. (7分) 71
试卷代号:1009 中央广播电视大学2009-2010学年度第一学期“开放本科”期末考试(半开卷) 离散数学(本) 试题答案及评分标准 (供参考) 2010年 1月 一 、单项选择题(每小题 3分，本题共 15分) l. A 2. C 3. B 4. B 5.D 二、填空题(每小题 3分.本题共 15分) 6.{ , ，，，，} 7. ， 8.5 9. n+k一2 10.真(或 T，或 1) 三、逻辑公式翻译(每小题 4分 ，本题共 12分 ) n.设 尸:今天考试，Q:明天放假. 则命题公式为:尸八Q. 12.设 P:我去旅游，Q:我有时间， 则命题公式为:P-Q. 四、判断说明题(每小题 7分，本题共 14分) 13.错误· 当图G不连通时图G不为欧拉图. 14.错误. 集合 A 的最大元与最小元不存在，“是极大元 ，.f是极小元. (2分) (6分) (2分) (6分) (3分) (7分) (3分) <7分) 71
五、计算题（每小题12分，本题共36分） 15.(1)A-B={1},2} (4分) (2)A∩B={1} (8分) (3)A×B=(,,,,,} (12分) 16.(1)G的图形表示为（如图三）： 图三 (3分) (2)邻接矩阵： 00101 0011 (6分) 1101 011 0 (3)1,2,,u4结点的度数依次为1,2,3,2 (9分) (4)补图如图四所示： 1 0 图四 (12分) 72
五、计算题【每小题 12分，本题共36分) 15.(1)A-B ={{1),2) (4分) (2 )A门B 二{1) (8分) (3)AXB= (，,,，，} (12分) 16.(1) G的图形表示为(如图三): 图三 (3分) (2)邻接矩阵: 0 1 0 1 1 0 1 1 (6分) (3 )V1 ,'U2 ,'U3 ,YJ;结点的度数依次为 1,2,3,2 (4)补图如图四所示 : (9分) 图四 (12分)
17.(1)x量词的辖域为(A(x,y)→(Hz)B(y,x,z)), (3分) Hz量词的辖域为B(y,x,z), (6分) (2)自由变元为(A(x,y)+(H)B(y,x,z))中的y, (9分） 约束变元为x与之， (12分) 六、证明题（本题共8分） 18.证明：设x∈A,则∈AXA, (1分) 因为AXA=BXB,故∈BXB,则有x∈B, (3分) 所以A二B (5分) 设x∈B,则∈BXB, (6分) 因为AXA=BXB,故∈AXA,则有x∈A,所以BCA. (7分) 故得A=B. (8分) 73
17.(1)3x量词的辖域为(A(x,y)- ( d z)B(y,x,z)) dz量词的辖域为B(y,x,z), (2)自由变元为(A(x, y)一(V z)B勺,x,z))中的夕， 约束变元为 x与 z. (3分) (6分) (9分) (12分) 六、证明题 (本题共 8分) 18.证明:设 xEA，则 EAXA, 因为 AXA=BXB，故EBXB，则有 xEB, 所以AFB. 设 xEB，则EBXB, 因为 AXA=BXB，故EAXA，则有 xEA，所以 BMA. 故得A=B. (1分) (3分) (5分) (6分) (7分) (8分)