洛阳师范学院离散数学习题集(十五套)

《洛阳师范学院离散数学习题集(十五套)》由会员分享，可在线阅读，更多相关《洛阳师范学院离散数学习题集(十五套)（20页珍藏版）》请在金锄头文库上搜索。

1、本卷由 12 级计科班杨重路整理离散数学试题与答案试卷一一、填空20% （每小题2 分）1设7|),5()( |xExxBxNxxA且且（N：自然数集，E+正偶数）则BA。2A，B，C 表示三个集合，文图中阴影部分的集合表达式为。3设 P，Q 的真值为 0，R，S的真值为1，则)()(SRPRQP的真值 = 。4公式PRSRP)()(的主合取范式为。5若解释I 的论域 D 仅包含一个元素，则)()(xxPxxP在 I 下真值为。6设 A=1 ，2，3， 4 ，A 上关系图为则 R2 = 。7设 A=a ，b，c，d ，其上偏序关系R 的哈斯图为则 R= 。8图的补图为。A B C 9设 A=a

2、 ，b，c，d ，A 上二元运算如下：* a b c d a b c d a b c d b c d a c d a b d a b c 那么代数系统 的幺元是，有逆元的元素为，它们的逆元分别为。10下图所示的偏序集中，是格的为。二、选择20% （每小题2 分）1、下列是真命题的有（）Aaa；B ,；C,；D。2、下列集合中相等的有（）A4，3；B，3，4 ；C4，3，3 ；D 3， 4。3、设 A=1 ，2，3 ，则 A 上的二元关系有（）个。A 23 ；B 32 ；C332；D223。4、设 R，S 是集合 A 上的关系，则下列说法正确的是（）A若 R，S 是自反的，则SR是自反的；B若

3、R， S 是反自反的，则SR是反自反的；C若 R， S 是对称的，则SR是对称的；D若 R，S 是传递的，则SR是传递的。5、设 A=1 ，2，3， 4，P（A） （A 的幂集）上规定二元系如下|(|)(,|,tsAptstsR则 P（A）/ R=（）AA ； B P(A) ； C1，1 ，2 ， 1 ，2，3 ，1 ，2，3，4 ；D，2 ，2 ，3 ，2 ， 3，4 ，A 6、设 A=，1 ，1，3，1， 2，3 则 A 上包含关系“”的哈斯图为（）7、下列函数是双射的为（）Af : IE , f (x) = 2x ；Bf : NNN, f (n) = ；Cf : RI , f (x) =

4、 x ；Df :IN, f (x) = | x | 。（注： I整数集， E偶数集，N自然数集， R实数集）8、图中 从 v1到 v3长度为 3 的通路有（）条。A 0；B1；C2；D3。9、下图中既不是Eular 图，也不是Hamilton 图的图是（）10、在一棵树中有7 片树叶， 3 个 3 度结点，其余都是4 度结点则该树有（）个 4度结点。A1； B2；C3；D4 。三、证明26% 、 R 是集合 X 上的一个自反关系，求证：R 是对称和传递的，当且仅当和 在 R 中有 在 R 中。 （8 分）、 f 和 g 都是群 到的同态映射， 证明 是 的一个子群。其中 C=)()(|1xgx

5、fGxx且(8 分) 、 G= (|V| = v ，|E|=e ) 是每一个面至少由k（k3）条边围成的连通平面图，则2)2(kvke ， 由此证明彼得森图（Peterson）图是非平面图。 （11 分）四、逻辑推演16% 用 CP 规则证明下题（每小题8 分）1、FAFEDDCBA,2、)()()()(xxQxxPxQxPx五、计算18% 1、设集合A=a ，b，c，d上的关系R= , , , 用矩阵运算求出 R 的传递闭包t (R)。（9 分）2、如下图所示的赋权图表示某七个城市721,vvv及预先算出它们之间的一些直接通信线路造价， 试给出一个设计方案，使得各城市之间能够通信而且总造价最

6、小。（分）试卷二试题与答案一、填空20% （每小题 2 分）1、 P：你努力， Q：你失败。“除非你努力，否则你将失败”的翻译为； “虽然你努力了，但还是失败了”的翻译为。2、论域 D=1 ，2，指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式),(xyyPx真值为。2、 设 S=a1 ，a2 ，, ， a8，Bi是 S 的子集，则由B31所表达的子集是。3、 设 A=2 ， 3， 4， 5， 6 上的二元关系|,是质数xyxyxR，则R= （列举法）。R 的关系矩阵MR= 。5 、 设A=1， 2 ， 3 ， 则A上 既 不 是 对 称 的

7、又 不 是 反 对 称 的 关 系R= ； A上 既 是 对 称 的 又 是 反 对 称 的 关 系R= 。6、设代数系统 ，其中 A=a ，b，c, 则 幺 元 是； 是 否 有 幂 等性；是否有对称性。7、4 阶群必是群或群。8、下面偏序格是分配格的是。9、n 个结点的无向完全图Kn的边数为，欧拉图的充要条件是。10、公式RQPQPP)()(的根树表示为。* a b c a b c a b c b b c c c b 二、选择20% （每小题 2 分）1、在下述公式中是重言式为（）A)()(QPQP；B)()()(PQQPQP；CQQP)(；D)(QPP。2、命题公式)()(PQQP中极小

8、项的个数为（） ，成真赋值的个数为（） 。A0；B1；C2；D3 。3、设2, 1,1 ,S，则S2有（）个元素。A3；B6；C7；D8 。4、 设3,2, 1S，定义SS上的等价关系,|,cbdaSSdcSSbadcbaR则由R 产 生的SS上一个划分共有（）个分块。A4；B5；C6；D9 。5、设3,2, 1S，S 上关系 R 的关系图为则 R 具有（）性质。A自反性、对称性、传递性；B反自反性、反对称性；C反自反性、反对称性、传递性；D自反性。6、设,为普通加法和乘法，则（）,S是域。A,3|QbabaxxSB,2|ZbanxxSC,12|ZnnxxSD0|xZxxS= N 。7、下面偏

9、序集（）能构成格。8、在如下的有向图中，从V1到 V4长度为 3 的道路有（）条。A1；B2；C3；D4 。9、在如下各图中（）欧拉图。10、设 R 是实数集合，“”为普通乘法，则代数系统 是（） 。A群；B独异点；C半群。三、证明46% 1、 设 R 是 A 上一个二元关系，),(),(|,RbcRcaAcAbabaS且有对于某一个试 证明若 R 是 A 上一个等价关系，则S也是 A 上的一个等价关系。 （9 分）2、 用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11 分）3、 若BAf :是从A 到B 的函数，定义一个函数ABg2:对任意Bb有

10、)()( |)(bxfAxxbg， 证明：若 f 是 A 到 B 的满射，则 g 是从 B 到A2的单射。（10 分）4、 若无向图 G 中只有两个奇数度结点，则这两个结点一定连通。（8 分）5、 设 G 是具有n 个结点的无向简单图，其边数2)2)(1(21nnm ，则G 是Hamilton 图（ 8 分）四、计算14% 1、 设是一个群，这里+6是模 6加法， Z6=0 ，1 ，2 ，3，4 ，5 ，试求出 的所有子群及其相应左陪集。（7 分）2、 权数 1，4，9，16，25，36， 49，64，81，100 构造一棵最优二叉树。 （7 分）试卷三试题与答案一、填空 20% （每空 2

11、分）1、 设 f，g 是自然数集N 上的函数xxgxxfNx2)(,1)(,，则)(xgf。2、 设 A=a ，b，c ，A 上二元关系R= , , , 则 s（R）= 。3、 A=1 ，2，3，4， 5，6， A 上二元关系|,是素数yxyxT，则用列举法T= ；T 的关系图为；T 具有性质。4、 集合2,2,A的幂集A2= 。5、 P，Q 真值为 0 ；R，S真值为 1。则)()()(SRQPSRPwff的真值为。6、RRQPwff)(的主合取范式为。7、 设 P（x） ：x 是素数，E(x)： x 是偶数， O(x)：x 是奇数N (x,y)：x 可以整数y。则谓词),()()(xyNy

12、OyxPxwff的自然语言是。8、 谓词),(),(),(uyxuQzyPzxPzyxwff的前束范式为。二、选择 20% （每小题2 分）1、 下述命题公式中，是重言式的为（） 。A、)()(qpqp；B、)()()(pqqpqp；C、qqp)(；D、qpp)(。2、rqpwff)(的主析取范式中含极小项的个数为（） 。A 、2；B、 3；C、5；D、0；E、 8 。3、 给定推理)()(xGxFxP)()(yGyFUS)(xxFP)(yFES)( yGT I )(xxGUG)()()(xxGxGxFx推理过程中错在（） 。A、 -; B、 -; C、 - ; D、 - ; E、 -4、 设

13、 S1=1 ，2， , ， 8， 9，S2=2， 4，6，8，S3=1 ，3，5，7，9 ，S4=3 ，4，5 ，S5=3 ，5，在条件31SXSX且下 X 与（）集合相等。A、 X=S2或 S5 ；B、X=S4或 S5；C、X=S1，S2或 S4；D、X 与 S1，, ， S5中任何集合都不等。5、 设R和S是P上的关系，P是所有人的集合，,|,的父亲是yxPyxyxR，,|,的母亲是yxPyxyxS则RS1表示关系（） 。A、,|,的丈夫是yxPyxyx；B、,|,的孙子或孙女是yxPyxyx；C、；D、,|,的祖父或祖母是yxPyxyx。6、 下面函数（）是单射而非满射。A、12)(,:

14、2xxxfRRf；B、xxfRZfln)(,:；C、的最大整数表示不大于 xxxxfZRf,)(,:；D、12)(,:xxfRRf。其中 R 为实数集， Z 为整数集， R+，Z+分别表示正实数与正整数集。7、 设 S=1， 2，3 ，R 为 S上的关系，其关系图为则 R 具有（）的性质。A、 自反、对称、传递；B、什么性质也没有；C、反自反、反对称、传递；D、自反、对称、反对称、传递。8、 设2, 1,1 ,S，则有（）S。A、1,2 ；B、1,2 ；C、1 ；D、2 。9、 设 A=1 ,2 ,3 ，则 A 上有（）个二元关系。A、23； B、32； C、322； D、232。10、全体小

15、项合取式为（） 。A、可满足式；B、矛盾式；C、永真式；D、A，B，C 都有可能。三、用 CP 规则证明16% （每小题8 分）1、FAFEDDCBA,2、)()()()(xxQxxPxQxPx四、 （14% ）集合 X=, , , ，R=,|x1+y2 = x2+y1 。1、 证明 R 是 X 上的等价关系。（10 分）2、 求出 X 关于 R 的商集。（4 分）五、 （10% ）设集合 A= a ,b , c , d 上关系 R= , , , 要求1、写出 R 的关系矩阵和关系图。 （ 4 分）2、用矩阵运算求出R 的传递闭包。 （6 分）六、 （20% ）1、 （ 10 分）设 f 和 g 是函数，证明gf也是函数。2、 （ 10 分）设函数STfTSg:，证明STf :有一左逆函数当且仅当f 是入射函数。试卷四试题与答案一、填空 10% （每小题2 分）1、 若 P，Q，为二命题，QP真值为 0 当且仅当。