离散数学试题(60学时).docxVIP

离散数学试题A一、解答题(本大题共7小题, 每小题5分, 共35分)1. 用命题逻辑推证语句:“如果你不走, 那么我和她都不留”与“如果我和她有一个留下, 那么你就得必须走”具有相同的逻辑含义.2. 设给定解释I如下: 个体域DI= {3, 6, 8}, 谓词P(x): x≤3, G(x): x5,R(x): x≤9,求下列谓词公式的真值. (写出判断过程, 仅给出结果而无过程不得分)(1)x(R(x)P(x))∨G(5).(2)x(P(x)∨G(x)).3. 设A={a,b,c},A上二元关系R={a,a,a,c,b,a},用关系矩阵法求最小的自然数m,n,mn使得Rm=Rn, 并求其传递闭包与对称闭包.4. 设(R*, )为代数系统, 其中R*=R{0}, 是数的乘法, 下述映射f是否为R*到R*的同态.(1) f(x) = x2,(2) f (x) =x,(3) f (x) = [x].5. 设无向图G各结点的度数都是3,且结点数n与边数m之间有下面的关系:2n?3= m.(1)G中结点数n与边数m各是多少？(2) 在同构的意义下能否画出G的一个二部图？若能, 请画出一个二部图.6. 设函数f : AB, g : BC, h : CD, 其中A={a, b, c}, B={x, y, z}, C={1, 2, 3, 4}, D={, , }, f ={a, y, b, x, c, y}, g ={x, 2, y, 1, z, 4}, h ={1, , 2, , 3, , 4, }.判断(1)f, g, h各是什么类型的函数？(2)hgf是什么类型的函数？它有反函数吗？为什么？7. 设平面图G有两个连通分支, 一个为K3, 另一个为K4. 请画出G的对偶图G*, 问G*是欧拉图吗？为什么？是哈密顿图吗？为什么？(针对判断结果, 给出详细的理由)二、计算题(本大题共5小题, 每小题5分, 共25分)1. 设集合A={, {a, b}}, B={a, {}}, (A), (B)为其幂集, 计算 (A)∩(B).2. 设G=, G上的运算是矩阵乘法. 已知(G, )构成群. 在群(G, )中, 指出每个元素的阶; 找出每一元素的逆元, 求出G的全部子群.3. 设R={1, 1, 1, 3, 2, 1, 2, 2, 3, 3, 4, 3, 4, 4}是集合A={1, 2, 3, 4}上的二元关系.(1) 画出R的关系图;(2) 写成R的关系矩阵; (3) 说明R是否具有自反、反自反、对称、反对称、传递性质.4. 求命题公式(P(Q∧R))∧(P(QR))的主合取范式.5. 设集合A={1, 2, 3, 6, 9, 18}, ≤为整除关系.(1) 画出A, ≤的哈斯图;(2) 求子集B={3, 6, 9}的极大元、极小元、最大元、最小元.三、证明题(本大题共2小题, 每小题10分, 共20分)1. 设(G1,), (G2,)都是群(G,)的子群.(1) 证明: (G1∩G2,)也是(G1,), (G2,)及(G,)的子群.(2)若|G1|=5, |G2|=6, 问|G1∩G2|是多少？为什么？2. 给定集合A={a, b, c}, (A)是A的幂集, ((A), ∪)为代数系统, 在(A)上又定义二元关系R如下:XRY当且仅当X∩{b} = Y∩{b}, X, Y(A).∩、∪分别为集合的并、交运算, 求证:(1)R是(A)上的等价关系;(2)R是(A)上的关于∪的同余关系;(3) 求商集(A)/R.四、应用题(本大题共2小题, 每小题10分,共20分)1. 对下面推理进行符号化, 并构造其证明.会操作计算机的人都认识26个英文字母; 文盲都不认识26个英文字母; 有的文盲是很聪明的. 所以有的很聪明的人不会操作计算机.(个体域D: 所有人的集合. 设F(x): x会操作计算机, G(x): x认识26个英文字母, H(x): x是文盲, R(x): x是很聪明的)2. 设有n个人P1,P1,…, Pn,其中某些人在做决策时能够互相影响, 而这种影响一般是单方面的, 即如果Pi影响Pj, 那么Pj不一定影响Pi. 并且每个人不影响他自己. 另外可以考虑二级影响, 即如果存在一条从Pi到Pj长度为2的路径, 则Pi对Pj有二级影响. 类似地, 如果存在一条从Pi到Pj长度为r的路径, 那么Pi对Pj有r级影响.如图给出了一个设计组中6个成员之间描述影响关系的有向图. 问设计组中哪些不同成员之间有二级影响?保证设计组中成员没有影响的最小级数是多少？离散数学答案A一、解答题(本大题共7小题, 每小题5分, 共35分)1.设P: 你走, Q: 我留, R: 她留. 则两命题分别符号化为：PQ∧R, Q∨RP.由于PQ∧R P∨(Q