(完整word版)《离散数学》期末试题及答案

326《离散数学》期末考试题(B)一、填空题(每小题3分，共15分)1.设,,},,{{babaA}，则A=()，A{}=()，)(AP中的元素个数|)(|AP().2.设集合A中有3个元素，则A上的二元关系有()个，其中有()个是A到A的函数.3.谓词公式))()(())()((yPyQyxQxPx中量词x的辖域为(),量词y的辖域为().4.设}24,12,8,6,4,3,2,1{24D，对于其上的整除关系“|”，元素()不存在补元.5.当n()时，n阶完全无向图nK是平面图，当当n为()时，nK是欧拉图.二．1.若nBmA||,||，则||BA()，A到B的2元关系共有()个，A上的2元关系共有()个.2.设A={1,2,3},f={(1,1),(2,1),(3,1)},g={(1,1),(2,3),(3,2)}和h={(1,3),(2,1),(3,1)}，则()是单射，()是满射，()是双射.3.下列5个命题公式中，是永真式的有()(选择正确答案的番号).(1)qqpp)(；(2))(qpp；(3))(qpp；(4)qqpp)(；(5)qqp)(.4.设D24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元()，4的补元()，6的补元().5.设G是(7,15)简单平面图，则G一定是()图，且其每个面恰由()条边围成，G的面数为().三．1.设}}{},,{{cbaA，}}{},,{},{{ccbaB，则)(BA，)(BA，)()(AP.2.集合},,{cbaA，其上可定义()个封闭的1元运算，()个封闭的2元运算，()个封闭的3元运算.3.命题公式1)(qp的对偶式为().4.所有6的因数组成的集合为().5.不同构的5阶根树有()棵.四、(10分)设BAf:且CBg:，若gf是单射，证明f是单射，并举例说明g不一定是单射.五、(15分)设},,,{dcbaA,A上的关系)},(),,(),,(),,(),,(),,(),,(),,(),,{(cdbdadccbcaccabaaaR,1.画出R的关系图RG.2.判断R所具有的性质.3.求出R的关系矩阵RM.六、(10分)利用真值表求命题公式))(())((pqrrqpA的主析取范式和主合取范式.七、(10分)边数30m的简单平面图G，必存在节点v使得4)deg(v.八、(10分)有六个数字，其中三个1，两个2，一个3，求能组成四位数的个数.《离散数学》期末考试题(B)参考答案一、1.{{a,b},a,b,}，{{a,b},a,b}，16.2.92,27.3.)()(xQxP,)()(yPyQ.4.2,4,6,12.5.4，奇数.二、1.22,2,mmnmn.2.g,g,g.3.1,2,4.4.8，不存在，不存在.5.连通，3，10.三、1.}}{},,{},,{},{{ccbbaaBA，}}{{cBA，{)(AP,{{a,b}},{{c}},{{a,b},{c}}}.2.27933,3,3.3.0)(qp.4.{-1，-2，-3，-6，1，2，3，6}.5.9.四、证对于任意Ayx,，若)()(yfxf，则))(())((yfgxfg，即))(())((ygfxgf.由于gf是单射，因此yx，于是f是单射.例如取},,{},3,2,1(},,{CBbaA，令)}2,(),1,{(baf，)},3(),,2(),,1{(g，这时)},(),,{(bagf是单射，而g不是单射.五、解1.R的关系图RG如下：2.(1)由于Rbb),(，所以R不是自反的.(2)由于Raa),(，所以R不是反自反的.(3)因为Rbd),(，而Rdb),(，因此R不是对称的.(4)因Racca),(),,(，于是R不是反对称的.abcd(5)经计算知RcdadccbcaccabaaaRR)},(),,(),,(),,(),,(),,(),,(),,{(，进而R是传递的.综上所述，所给R是传递的.3.R的关系矩阵0111011100000111RM.六、解命题公式))(())((pqrrqpA的真值表如下:p,q,r)(rqp)(pqrA1,1,11111,1,00101,0,11111,0,01110,1,11000,1,01110,0,11110,0,0111由表可知，))(())((pqrrqpA的主析取范式为).()()()()()(rqprqprqprqprqprqpAA的主合取范式为)()(rqprqpA.七、证不妨设G的阶数3n，否则结论是显然的.根据推论1知，63nm.若G的任意节点v的度数均有5)deg(v，由握手定理知nvmv5)deg(2.于是mn52，进而652363mnm.因此30m，与已知矛盾.所以必存在节点v使得4)deg(v.八、解设满足要求的r位数的个数有ar种，r=0，1，2，…，则排列计数生成函数xxxxxxxE1!21!3!21)(23265432121211219619431xxxxxx,因而38!412194a.