离散期末习题

第一章1.下列语句中不是命题的是（）。A.3是奇数B.请勿吸烟C.我是中学生D.4+352.与命题公式)(RQP等价的公式是（）A.RQP)(B.RQP)(C.)(RQPD.)(RQP3.与命题PVQ相等价的公式是（）A.PVQB.PQC.PQD.（PQ）4.下列命题为真命题的是（）A.苹果是水果当且仅当太阳从西方升起。B.如果两平行线有交点，那么相似三角形的面积相等。C.若光合作用需要光，则呼吸不需要空气。D.1是质数当且仅当2是质数。5．命题公式rqqpp是永（）式。6．求下列各式的主析取范式与主合取范式A.RQPB.QPRPC.RQQPD.RPQPRQPE.QPQP7．QP的主析取范式中，含有（）个小项。8.用推理规则证明：SRSRBABAPPDCDC,,,。第二章1.求谓词公式：))(),(()),,(),((yFzyyRzxyzQyxPx的前束范式2.求谓词公式：),()()),()(),()((xyRyzxQzyxPx的前束范式3.设C(x):x是人，G(x):x需要关爱，则命题“每个人都需要关爱”可符号化为。第三章1．设8,7,6,5,4,3,2,1A，下列选项正确的是（）。A．A1B．A3,2,1C．A5,4D．A2．下列集合运算中（）是正确的。A.B.,C.,,D.,3．设A、B是集合，其中4,1A，4,2B，则BPAP。4．幂集)))(((PPP是。5．设集合3,2,1,0E，则下面集合与E相等的是（）。A．03xRxB．92xRxC．0652xxRxD．30xNx6．下面有关集合之间的包含和属于关系的说法，正确的是（）。Ⅰ．Ⅱ．,,Ⅲ．bababa,,,,Ⅳ．cbababa,,,,,A．Ⅰ和ⅡB．Ⅰ和ⅢC．Ⅰ和ⅣD．Ⅱ、Ⅲ和Ⅳ7.设A为n个元素的集合，则A上有（）个二元关系。A．n2B．nn2C．2nD．n8.对于一个只有4个不同元素的集合A来说，A上的不同的二元关系的总数为（）。A．4B．16C．162D．429.设A、B是集合，其中4,1A，4,2B，求BA2，AB2，22AB。10.设P={x,x,x,y,y,y,y,t,t,x,t,y},Q={x,y,y,x,y,t,t,y,s,x,s,t},求P∪Q，domP,domQ,ranP,ranQ,ranP∩Q,domP∪Q。11.设S={1，2，3}，R为S上的关系，其关系图如下，则R具有（）的性质。A、自反、对称、传递；B、什么性质也没有；C、反自反、反对称、传递；D、自反、对称、反对称、传递。12.设R是非空集合A上的关系，则R的对称闭包Rs=（）。A.1RRB.RIAC.AIRD.1RR13.设集合,,cbaA，R是A上的二元关系，且accbbaR,,,,,，则R的对称闭包Rs=。14.集合cbaA,,上的关系,,,,,cbccbaR的传递闭包Rt。15.设集合cbaA,,，R是A上的二元关系，bccabaaaR,,,,,,,，试求：(1)AP；(2)R的关系图与关系矩阵RM；(3)Rr、Rs、Rt。16.设集合,,,dcbaA，R是A上的二元关系，且cadccbabbaR,,,,,,,,,，用Warshall算法求出关系R的传递闭包。17.设A、B是集合，若2A，3B，则A到B的函数有个。18.设A、B是集合，若2A，3B，则A到B的入射函数有个。第五章1.下列代数系统*,G中，（）不构成群。A．01,1G，*是模11乘法B．9,5,4,3,1G，*是模11乘法C．G为有理数集，*是普通加法D．G为有理数集，*是普通乘法2.设*,G是独异点，并且对于G中的每一个元素x，都有exx*，其中e是幺元，证明：*,G是一个阿贝尔群。课本：5-4习题（1），（3）5-5习题（5）5-8习题（1），（2），（4），（6）(11)第七章1.任何简单图中顶点的度数之和等于边数的倍。2.给定下列序列，可构成无向简单图的顶点度数序列的是（）。A.3,2,2,1,1B.2,2,2,1,1C.3,3,3,1,0D.5,4,4,3,13.设D是有n个结点的有向完全图,则图D的边数为()A.)1(nnB.)1(nnC.2/)1(nnD.2/)1(nn4.无向图G是欧拉图,当且仅当（）。A.G的所有结点的度数都是偶数B.G的所有结点的度数都是奇数C.G连通且所有结点的度数都是偶数D.G连通且G的所有结点度数都是奇数。5.下列图形中为欧拉图的是（）。6.在如下各图中（）欧拉图。7.设无向树T由3个3度顶点，2个2度顶点。其余顶点都是树叶，则T有（）片树叶。A.3B.4C.5D.68.设无向树T由4个2度顶点，3个3度顶点，3个4度顶点。其余顶点都是树叶，则T有片树叶。9.求出下列各图的的距离矩阵D(G)与可达矩阵P(G)。10.求下图的最小生成树，并求出最小生成树的树权。1234567e2e7v4e4v1v2v3e1e3e6e511．Gladbrook饲料公司有7个谷物箱，要通过谷物管道将它们连接起来，以使谷物能从任意一个箱子转移到其它箱子，为了使建造费用最少，希望建造尽可能少的管道，在两个箱子之间建造管道的费用(以10万美元计)由下表给出，其中“-”表示不能建造管道，应该怎样建造管道才能使费用最少。1-4-62-32-52-313-7-224-41-5-1-6-27-