离散数学期末复习

练习一、填空题1、设1N是偶数集合，2N是奇数集合，3N是质数集合.则有12NN=,13NN=__________.2、设{,,},{(,),(,)},AabcRaaab则()____________,()________.sRtR3、在代数系统(,)N中，其单位元是.4、群(,),(ZZ是整数集合）是一个循环群，其生成元是_______________5、若G是n个结点m条边的简单无向图.V是次数为k的结点，则(GVGV中去掉结点的图）中有________个结点，__________条边.6、设,PQ为命题，复合命题“如果P则Q”称为PQ与的__________,记作___________.8.22,,,abSabcdcd是所有形式的矩阵的集合，其中是有理数，*是矩阵的乘法，代数系统(,)S中的单位元素是零元素是.9、若G是n个结点，m条边的连通图.要确定G的一棵生成树，必须删去G中的边数为.10、若个体域为整数集，公式(0)yxxy的真值为（填F或T）二选择题1、下列四个式子，错误的是（）A．B．0C．{0}D．2、已知PQ且PQ，下列结论正确的是（）A．是不可能成立的B可能成立C.P必须是空集D.Q必须是全集3、设{,,},{(,),(,),(,)},AabcRaabbab则R具备关系中的哪个性质（）A．传递性B.对称性C.自反性D.以上均不对4、在自然数集合N上，下列运算中可结合的是（）A.ababB.max(,)ababC.2ababD.abab5、任何图中必有偶数个（）A．引入次数为奇数的结点B.引出次数为奇数的结点C.次数为偶数的结点D.次数为奇数的结点.6、一棵树有两个4次结点，三个3次结点，其余结点都是叶子，则叶子结点数目为（）A.7B.8C.9D.107、对于树，下列结论正确的是（）A.树不是连通图B.存在回路C.无回路的连通图D.结点数与边数相同.8、谓词公式()(()()())()xRxyTyPxx中变元是（）A.自由变元B约束变元C.既是自由变元又是约束变元D.不是自由变元是约束变元9、集合{0}的所有子集为是（）A．B．{0}，C．{}D．{{0}}，10．设集合{,,}Aabc，{(,),(,),(,)}Raaabba，则R具备（）A自反性B对称性C反对称性D传递性11．使PQ的成为F的指派为（）A（F，F）B（F，T）C（T，F）D（T，T）12．设:fAB,若A与B都为有限集且f为单射，则必有（）AABBABCABDAB三、求解或证明下列各题886688(,6012345,6,7.(,.ZZZ1.设)是一个群.这里是模的加法，，，，，，试写出)的所有子群A={01}B={,,},{,,}.()abcCbdeABC2.设，，试求：3.在实数集R上定义二元运算“*”如下：,xyxyxy试问：（1）xy是否满足结合律，交换律？（写出验证过程）（2）是否有单位元及逆元？若有请求出.（3）,)R（为半群，可换半群，群？4.求G=(RP)(Q(PR))特异析取范式.5.证明:()()().PQRPRQR6、设{,,},Aabc.{(,),(,),(,)}Raabccb1．写出R的关系矩阵；2．求出R的自反闭包r(R)、对称闭包s(R)、传递闭包t(R).7、判断图形：试判定所给无向图G的类型.(若是用Y表示，若不是用N表示).1．是完全图；（）2．是欧拉图；（）3．是汉密尔顿图；（）4．是平面图；（）5．是二步图.（）8．如图给出的赋权图表示六个城市,,,,,abcdef及架起城市间直接通讯线路的预测造价。试画图给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。8.1000,01009.1mn10.F3.（1）满足结合律，交换律；（4分）（2）单位元0，逆元1(1)1xxxx；（3分）（3）是半群，可换半群.非群.（3分）4.()(()()()()()()4()()()8((((1)()0))))GRPQPQRRPQPQRRPQPQRQQRPQPQPQRPPRRPRQR（分）（分）（分）五.（1）100001010（4分）（2）(){(,),(,),(,),(,),(,)}rRaabbccbccb，(){(,),(,),(,)}sRaabccb(){(,),(,),(,),(,),(,)}tRaabbccbccb.（6分）六．要设计一个方案使各城市间能够通讯且总造价最小，即要求该图连通、无回路、边权之和最小的子图即最小生成树，由避圈法或破圈法可得：其最小生成树为：右图---------------------8分其树权即最小造价为：1+2+3+5+7=18。---------------------10分