离散数学试题与答案.docx

《离散数学试题与答案.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、试卷二试题与参考答案一、填空1、P：你努力，Q：你失败。2、“除非你努力，否则你将失败”符号化为；“虽然你努力了，但还是失败了”符号化为。2、论域D={1，2}，指定谓词PP(1,1)P(1,2)P(2,1)P(2,2)TTFF则公式xyP(y,x)真值为。3设A={2，3，4，5，6}上的二元关系R{x,y

2、xyx是质数}，则R=（列举法）。R的关系矩阵RM=。4、设A={1，2，3}，则A上既不是对称的又不是反对称的关系R=；A上既是对称的又是反对称的关系R=。5、设代数系统，其中A={a，b，c},*abcaabcbbbccccb则幺元是；

3、是否有幂等性；是否有对称性。6、4阶群必是群或群。7、下面偏序格是分配格的是。8、n个结点的无向完全图Kn的边数为，欧拉图的充要条件是。二、选择1、在下述公式中是重言式为（）A．(PQ)(PQ)；B．(PQ)((PQ)(QP))；C．(PQ)Q；D．P(PQ)。2、命题公式(PQ)(QP)中极小项的个数为（），成真赋值的个数为（）。A．0；B．1；C．2；D．3。3、设S{,{1},{1,2}}，则2S有（）个元素。A．3；B．6；C．7；D．8。4、设S{1,2,3}，定义SS上的等价关系R{a,b,c,d

4、a,bSS,c,dSS,adbc}则由R产

5、生的SS上一个划分共有（）个分块。A．4；B．5；C．6；D．9。5、设S{1,2,3}，S上关系R的关系图为则R具有（）性质。A．自反性、对称性、传递性；B．反自反性、反对称性；C．反自反性、反对称性、传递性；D．自反性。6、设,为普通加法和乘法，则（）S,,是域。A．S{x

6、xab3,a,bQ}B．S{x

7、x2n,a,bZ}C．S{x

8、x2n1,nZ}D．S{x

9、xZx0}=N。7、下面偏序集（）能构成格。8、在如下的有向图中，从V1到V4长度为3的道路有（）条。A．1；B．2；C．3；D．4。9、在如下各图中（）欧拉图。10、10、设R是实数集合，“

10、”为普通乘法，则代数系统是（）。A．群；B．独异点；C．半群。三、证明1、设R是A上一个二元关系，S{a,b

11、(a,bA)(对于某一个cA,有a,cR且c,bR)}试证明若R是A上一个等价关系，则S也是A上的一个等价关系。2、用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。3、若无向图G中只有两个奇数度结点，则这两个结点一定连通。m1(n1)(n2)24、设G是具有n个结点的无向简单图，其边数2，则G是Hamilton图。四、计算1、设是一个群，这里+6是模6加法，Z

12、6={[0]，[1]，[2]，[3]，[4]，[5]}，试求出的所有子群及其相应左陪集。2、权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。试卷二参考答案：一、填空1、PQ；PQ2、T3、R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6>}；11111111110001111111000004、R={<1,2>,<1,3>,<2,1>}；R={<1,1>,<

13、2,2>,<3,3>}5、a；否；有6、Klein四元群；循环群7、B1n(n1)8、2；图中无奇度结点且连通二、选择题目12345678910答案B、DD；DDBDABBBB、C三、明1、（1）S自反的aA，由R自反，(a,aR)(a,aR)，a,aS（2）S称的a,bAa,bS(a,cR)(c,bR)S定义(a,cR)(c,bR)R对称b,aSR传递（3）S的a,b,cAa,bSb,cS(a,dR)(d,bR)(b,eR)(e,cR)(a,bR)(b,cR)R传递a,cSS定义由（1）、（2）、（3）得；S是等价关系。2、明：P(x)：x是个舞蹈者；Q

14、(x)：x很有度；S(x)：x是个学生；a：王上述句子符号化：前提：x(P(x)Q(x))、S(a)P(a)：x(S(x)Q(x))⋯⋯3分①S(a)P(a)前提引入②x(P(x)Q(x))前提引入③P(a)Q(a)②US④P(a)①化⑤Q(a).③④假言推理I⑥S(a)①化⑦S(a)Q(a)⑤⑥合取⑧x(S(x)Q(x)⑦EG⋯⋯11分３、明：b1,b2B,(b1b2)f满射a1,a2A使f(a1)b1,f(a2)b2,且f(a1)f(a2),由于f是函数,a1a2又g(b1){x

15、(xA)(f(x)b1)},g(b2){x

16、(xA)(f(x)b2)}a

17、1g(b1),a2g(b2)但a1g(b2),a2g(b1)g(b