电大1009-离散数学2015年1月份试题-开放本科期末考试试卷

PAGE3PAGE3一、单项选择题（每小题3分，本题共15分）1．若集合A＝{b,c,d}，则下列表述正确的是()．A．{b,c,d}AB．A{c,d}C．{b,c,d}AD．{b,c}A2．已知无向图G的邻接矩阵为，则G有（）．A．6点，10边B．5点，12边C．6点，5边D．5点，6边3．无向图G是个棵树，结点数为10，则G的边数是（）．A．9B．10C．11D．124．设A（x）：x是人，B（x）：x是工人，则命题“有人是工人”可符号化为（）．A．(x)(A(x)∧B(x))B．┐(x)(A(x)→B(x))C．(x)(A(x)∧B(x))D．┐(x)(A(x)∧┐B(x)) 5．下面的推理正确的是（）．A．(1)（x）F（x）→G（x）前提引入(2)F（y）→G（y）US（1）．B．(1)（x）（F（x）→G（x））前提引入(2)F（y）→G（y）US（1）．C．(1)（x）F（x）→G（x）前提引入(2)F（y）→G（y）US（1）．D．(1)（x）(F（x）→G（x））前提引入(2)F（y）→G（x）ES（1）． 二、填空题（每小题3分，本题共15分）6．设A={a，b，c}，B={1，2，3}，作f：A→B，则不同的函数个数为．7．任一无向图中，度数为奇数的结点的个数为．8．设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为6，则在G-S中的连通分支数不超过．9．设G是有8个结点的连通图，结点的度数之和为28，则可从G中删去条边后使之变成树．10．设个体域D＝{1,2}，则谓词公式(x)P(x)∨（x）Q（x）消去量词后的等值式为．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“小张和小李都可以完成这项工作”翻译成命题公式．12．将语句“a是偶数当且仅当a能被2整除．”翻译成命题公式．四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．存在集合A与B，使得AB与AB同时成立．14．完全图K5是平面图．五、计算题（每小题12分，本题共36分）15．设A={2,3,6,12,24,36}，B为A的子集，其中B={6,12}，R是A上的整除关系，试（1）写出R的关系表达式；（2）说明R为偏序关系；（3）画出关系R的哈斯图；（4）求出B的最大元素、极大元素、上确界．16．．设图G=<V，E>，V={v1，v2，v3，v4，v5}，E={(v1,v2)，(v1,v3)，(v1,v5)，(v2,v3)，(v2,v4)，(v2,v5)，(v3,v4)，(v3,v5)，(v4,v5)}，试（1）画出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出图G的补图的图形．17．求P→（Q∧R）的合取范式与主合取范式．六、证明题（本题共8分）18．对任意集合A，B和C，若有C，则有：AB的充分必要条件是CACB．

离散数学（本）2015年1月份试题参考解答一、单项选择题（每小题3分，本题共15分）1．D2．D3．A4．C5．B二、填空题（每小题3分，本题共15分）6．277．偶数8．69．710．(P(1)∧P(2))∨(Q（1）∨Q（2))三、逻辑公式翻译（每小题6分，本题共12分）11．设P：小张可以完成这项工作，Q：小李可以完成这项工作．（2分）则命题公式为：P∧Q．（6分）12．设P：a是偶数，Q：a能被2整除．（2分）则命题公式为：P↔Q．（6分）四、判断说明题（每小题7分，本题共14分）13．正确．（3分）例：设A={a}，B={a，{a}}（5分）则有AB且AB．（7分）说明：举出符合条件的例均给分．14．错误．（3分）完全图K5是有5个结点10条边，因35-6<10，即e3v-6对K5不成立，（5分）故K5不是平面图．（7分）五、计算题（每小题12分，本题共36分）15．（1）因为在集合A={2,3,6,12,24,36}中，集合A上的整除关系R为：R={<2,2>,<3,3>,<6,6>,<12,12>,<24,24>,<36,36>,<2,6>,<3,6>,<2,12>,<3,12>,<6,12>,<2,24>,<3,24>,<6,24>,<12,24>,<2,36>,<3,36>,<6,36>,<12,36>}．（3分）（2）R中的每个有序对的第一个元素都可以整除第二个元素，即R为整除关系．每个数可以整除自身，则关系R是自反的；由R的元素可看出，若xy，当存在<x,y>R，就有<y,x>R，则说明关系R是反对称的；由R的元素可看出，若存在<x,y>R，<y,z>R,就有<x,z>R，则说明关系R是传递的．所以A上的整除关系R为偏序关系．（6分）说明：只要指出R是自反的、反对称的、传递的，即可给分．（3）关系R的哈斯图如图一所示：（9分）图一（4）集合B的最大元素12、极大元素12、上确界为12（12分）v1v2vv1v2v3v4图二v5（3分）（2）邻接矩阵（6分）（3）deg(v1)=3deg(v2)=4deg(v3)=4deg(v4)=3v1vv1v2v3v4图三v5（4）补图如图三所示：（12分）17．P→（Q∧R）P∨(Q∧R)（2分）(P∨Q)∧(P∨R)合取范式（5分）(P∨Q)∨(R∧R)∧(P∨R)（7分）(P∨Q)∨(R∧R)∧(P∨R)∨(Q∧Q)（9分）(P∨Q∨R)∧(P∨Q∨R)∧(P∨R∨Q)∧(P∨R∨Q)（11分）(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)主合取范式（12分）六、证明题（本题共8分） 18．证明：已知C，即存在c∈C，设AB，则对任意<c，a>∈CA，有c∈C，a∈A，（1分）可得c∈C，a∈B，（2分）即有<c，a>∈CB，（3分）所以CACB．（4分）再设CACB，则对任意a∈A，由<c，a>∈CA可得<c，a>∈CB，（5分）即有c∈C，a∈B，（6分）所以AB，