2022年2022年离散数学试题库 .pdf

《2022年2022年离散数学试题库 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学试题库 .pdf（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 模拟试题(一)一、单项选择题在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。1给定命题公式如下：)()(pqqp成真赋值的个数为（）。A1 2 3 4 2.设个体域 D=a,b，公式xxSxxP在 A 中消去量词后应为（）AxSxPB)()(bSaSbPaPCbSaPD)()(bSaSbPaP3若 R 和 S是集合 A 上的两个关系，则下述结论正确的是（）。A若 R和 S是自反的，则R S也是自反的 B若 R和 S是对称的，则R S也是对称的 C若 R和 S是反对称的，则R S也是反对成的 D若 R和 S是传递的，则R S也是传递的4设全集U=1,2,3,.

2、,20,A,B,C是其子集，其4|xxA，100|,076|22xxCxxxB则CBA（）。A16,17,18,19,20 B1,2,3,4,5 C10,11,12,13,14,15 D 1,2,3,4,5,6,7 5下面偏序集构成有界格的是（）。A 6全体自然数所组成的集合的最小元为（）。A负数最小的正数 0 1 7对任何 a A，形成的 A 上的等价关系R 的等价类 aR为（）。A空集非空集空集也可以为非空集 xxA 8设S=Q Q，其中Q 为有理数集合，定义S 上的二元运算“*”，,S，有bbyaxyxba,*,，则 是（）。A可交换的可结合的既是可交换的，又是可结合的不是可交换的，也不

3、是可结合的9.设有向图 D=的邻接矩阵为0100100001000121)(DA，则D中 v1到 v3长度为 4 的通路有（）条。A4 6 8 9 10.下面那种描述的图不一定是树（）。A无回路的连通图有 n 个顶点的n-1 条边每对顶点都有通路的图连通但删去一条边则不连通的图11.一颗二叉树后序遍历的结果是bdeca，中序遍历的结果是badce，则根结点的右子树有（）结点。A1 B2 C3 D4 12.设函数 f：NN（N 为自然数集），f(n)=n+1，下面四个命题为真的是()A.f是单射 B.f是满射 C.f是双射的 D.f非单射非满射13.设 S=0,1,则 S满足（）。A.在普通乘法

4、下封闭，在普通加法下不封闭 B.在普通加法和乘法下都封闭C在普通加法下封闭，在普通乘法下不封闭 D在普通加法和乘法下都不封闭名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 22 页 -2 14.下图中（）是欧拉图。A B C D 15.设集合 A=a，b，c，d，e，偏序关系 R的哈斯图如左图所示，则元素的关系不正确的是（）。Adc Bea C ba D ed二、填空题16.设无向图 G有 12 条边，有 6 个 3 度顶点，其余顶点度数均小于3，则 G种至少有顶点。17.在彼得森图中至少添加条边才能构成欧拉图。18.由 Huffman 算法，带权1,3,4,5,6 的最优二叉树

5、的权W(T)=。19.设 V=为代数系统，其中A=0,1,2,3,4。a,bA,a*b=(ab)mod5。关于运算“*”的幺元是。20设 Z 为整数集，a,bZ，有 a b=a+b-1，则 a 的逆元=。21集合 a,b,c,d上关系 R的关系图如左所示，则R的传递闭包（用集合表示）为。22.设 R是由方程 x+3y=12 定义的正整数集N 上的关系，即123,|,yxNyxyx，则 6,4,3,2R，3 在 R下的象是。23.若集合 A的基数|A|=10，则其幂集|P(A)|=。三、计算题24判断正整数集合Z+和下面的二元运算是否构成代数系统。如果是，则说明这个运算是否满足交换律、结合律和幂

6、等律，并求出单位元和零元。(1)a*b=min(a,b)(2)ab=(a/b)+(b/a)25.用主析取范式判断rqp与rpq是否等值。26.设，为上关系，关系矩阵为，(1)画出关系图。(2)求，。(3)求，。(4)指出具有的性质。(5)是偏序关系吗？能否画出哈斯图？abcdefg名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 22 页 -3 27求下图的最小生成树，写出过程，并计算权。四、证明题28在命题逻辑中构造下面推理的证明。前提：ps，qr，r，p q结论：s 29设无向图G 是由 k（k2）棵树组成的森林，已知G 中有 n 个结点，m 条边，证明m=n-k。30证明对于

7、任意集合A,B,C，有(A-B)-C=(A-C)-(B-C)五、应用题3175 名儿童到公园游乐场，他们在那儿可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20 人这三种东西都乘过，其中 55 人至少乘过其中的两种。若每样乘坐一次的而费用是0.50 元，公园游乐场总共收入70 元，试确定有多少儿童没有乘过其中任何一种。32有四个村庄的地下各有一个防空洞甲、乙、丙、丁，相邻两个防空洞之间有地道相通，且每个防空洞各有一条地道与地面相通，如下图所示（图中表示地道）。问能否从某一个防空洞开始，每个地道走一次且仅走一次后回到该防空洞。（要求有一定的分析过程）模拟试题(二)三、单项选择题在下列每小题的四

8、个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。1下列是两个命题变元p，q 的小项是（）A pp q Bp q Cp q Dp p q 2令 p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）A pq B pq Cp q Dpq 3下列语句中是命题的只有（）A 1+1=10 Bx+y=10 C sinx+siny0 D x mod 3=2 4下列等值式不正确的是（）A(x)A(x)(x)A(x)B(x)(B A(x)B(x)A(x)名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 22 页 -4 C(x)(A(x)B(x)(x)A(x)(x

9、)B(x)D(x)(y)(A(x)B(y)(x)A(x)(y)B(y)5谓词公式xP(x,y)t(Q(t,z)x yR(x,y,t)中量词t 的辖域是（）A t(Q(t,z)x yR(x,y,t)BQ(t,z)x yR(x,y,t)Cx yR(x,y,t)DQ(t,z)6设 R 为实数集，函数f：RR，f(x)=2x，则 f 是（）A满射函数 B入射函数C双射函数 D非入射非满射7设 A=a,b,c,d，A 上的等价关系R=,IA，则对应于R 的 A 的划分是（）A a,b,c,d B a,b,c,d C a,b,c,d Da,b,c,d 8设 A=?，B=P(P(A)，以下正确的式子是（）A

10、?,?B B?,?B C?,?B D?,?B 9设 X，Y，Z 是集合，“-”是集合相对补运算，下列等式不正确的是（）A(X-Y)-Z=X-(Y Z)B(X-Y)-Z=(X-Z)-Y C(X-Y)-Z=(X-Z)-(Y-Z)D(X-Y)-Z=X-(YZ)10设*是集合 A 上的二元运算，称z 是 A 上关于运算*的零元，若（）A z A，且有 x*z=z*x=z Bz A，且有 x*z=z*x=x C z A，且有 x*z=z*x=z DzA，且有 x*z=z*x=x 11在正整数Z+上，下列定义的运算中不可结合的只有（）A a*b=min(a,b)Ba*b=a+b C a*b=GCD(a,b

11、)(a,b 的最大公约数)Da*b=a(mod b)12设 R 为实数集，R+=x|x Rx0，*是数的乘法运算，是一个群，则下列集合关于数的乘法运算构成该群的子群的是（）A R+中的有理数 BR+中的无理数 C R+中的自然数 D1，2，3 13设 是环，则下列正确的是（）A 是交换群B 是加法群C 对*是可分配的D*对 是可分配的14图 1 所示的 6 个图中，强连通图为（）。A.(1)(2)(3)B.(4)(5)(6)C.(1)(3)(4)(6)D.(1)(5)(6)15设 G 是连通平面图，G 中有 6 个顶点 8 条边，则 G 的面的数目是（）A2 个面 B3 个面C4 个面 D5

12、个面二、填空题16 前束范式具有形式(Q1V1)(Q2V2),(QnVn)A，其中 Qi(1 i n)为，A为的谓词公式。17某集合 A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是。18设 Z 是整数集，在Z上定义二元运算*为 a*b=a+b+ab，其中+和是数的加法和乘法，则代数系统 的幺元是，零元是。19图 2 所示平面图有3 个面 R0,R1和 R2，其中 deg(R0)=。20图 3 中，结点 v2的度数是。图 2 图 3 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 22 页 -5 21.设 R为 A上的关系，则R的自反闭包为，对称闭包为。22.公式

13、)()(qpqp的主析取范式为。三、计算题23求出从 A=1,2 到 B=x,y 的所有函数，并指出哪些是双射函数，哪些是满射函数。24判断下面集合对于给定运算能否构成群，并简要说明理由。（1）实数集合R 关于运算，其中ab=2(a+b)（2）非零实数集合R*关于运算，其中ab=2ab25画出 5 个具有 5 个结点 5 条边的非同构的无向连通简单图。26在偏序集 中，其中 Z=1,2,3,4,6,8,12,24，是 Z 中的整除关系，画出其哈斯图，并求集合 D=2,3,4,6 的极大元，极小元，最大元，最小元，上界，下界，最小上界和最大下界。27求图 4 所示平面图G的对偶图，并判断G是否为

14、自对偶图。四、证明题28证明qprssprqqp图 4 29证明在无向图中顶点的连通关系是等价关系。五、应用题30对 100 名工作人员的调查结果表明，有32 人学过日语，20 人学过法语，45 人学过英语。其中15 人既学过日语又学过英语，7 人既学过日语又学过法语，10 人既学过法语又学过英语，30 人没有学过这 3 门语言中的任何一种。求至少学习过以上3 种语言中两种语言的人数。31设有 a,b,c,d,e,f,g 等七个人，已知a会讲英语；b 会讲英语、汉语；c 会讲英、俄语；d 会讲日、汉语；e 会讲德语、俄语；f 会讲法语、日语；g 会讲法语、德语。试用图论方法安排园桌座位，使每人

15、都能与其身边的人交谈。模拟试题(三)四、单项选择题在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。1一个公式在等价意义下，下面那个写法是唯一的（）。A析取范式B合取范式C主析取范式D以上答案都不对2令 p：今天下雨了，q：我上学，则命题“因为今天下雨了，所以我不上学了”可符号化为（）Apq Bpq Cp q Dpq 3谓词公式x(P(x,y)xQ(x,z)R(x,y,z)中量词的辖域是（）AQ(x,z)R(x,y,z)BR(x,y,z)CQ(x,z)D P(x,y)xQ(x,z)R(x,y,z)4设 R 为实数集，函数f：RR，f(x)=xe，则 f 是（）A满

16、射函数B单射函数C双射函数D非单射非满射5设 A=a,b,c,d，A 上的等价关系R=,IA，则对应于R 的 A 的划分是（）Aa,b,c,d Ba,b,c,d Ca,b,c,d Da,b,c,d 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 22 页 -6 6设 A=?，B=P(A)，以下正确的式子是（）A?,?A B?,?A C?,?B D?,?B 7设,G是群，Gba,则下列结论不正确的是（）A111)(ababBbax有惟一解Cyxayax，则Dbaab8在自然数集N 上，下列定义的运算中不满足结合律的（）Aa*b=min(a,b)Ba*b=a+b Ca*b=gcd(a

17、,b)(a,b 的最大公约数)Da*b=a-b 9不同构的有2条边的 4 阶无向简单图的个数为()A1 B2 C3 D 4 104 阶无向连通图G 是欧拉图，则它的度序列可能是（）A 1,2,3,4 B2,4,6,8 C1,2,4,6 D5,2,3,4 11下列命题中，。A海水是咸的当且仅当雪是白的B如果成都是直辖市，那么北京是中国的首都C若太阳从西边落下，则2 是奇数D夏天冷当且仅当冬天热12设 R是集合 A1,2,3,4上的二元关系，R,则 R不具有下面那种性质。A自反性B反自反性 C反对称性 D 传递性13.下面图中，（）是平面图.ABCD14 A1 B2 C 3 D4 15设简单图G

18、所有结点的度之和为12，则 G 一定有()。A3 条边B4 条边C5 条边D6 条边二、填空题16量词否定等值式)(xxA _。17.关于命题变项p,q,r的命题公式的主析取范式是76531mmmmm,则主合取范式是(用公式表示)_ .18.设 R=,，则 dom(R)=。19.设 G是连通的 n 阶 m条边 r 个面的可平面图，则反映结点数、边数、面数之间关系的欧拉公式是_。20.无向图 G=,V=a,b,c,d,E=e1,e2,e3,e4,其中 e1=(a,a),e2=(a,d),e3=(a,c),e4=(b,c),则它的关联矩阵为：21设S(x)x 是大学生；K(x)x 是运动员。则命题

19、：“有些运动员不是大学生”的符号化为。22设54321，A，AAR，224321，R求)(Rr=，)(Rs=23设 G 是完全二叉树，G 有 15 个点，其中8 个叶点，则G 的总度数为 _，分枝点数为_。三、计算题24 A=a,b,c,R1=,R2=,求：(1)R1-1 (2)名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 22 页 -7 12RR(3)R1在 A上的限制25.已知图 G有 10 条边,4 个 3 度结点,其余结点的度数均小于等于2,问该图至少有几个结点?为什么?26.下图是偏序集 的哈斯图，求abcdefgh27.命题公式 F 含有 3 个命题变项p,q,r，

20、其所有成真赋值为：000，001，110，111，求：(1)画出真值表；(2)写出主析取范式；(3)指出公式的类型28求下图的最小生成树，写出过程，并计算权。abcdefh12345567866四、证明题29证明对于具有k（k2）个连通分支的平面图G，有 n-m+r=k+1。其中 n,m,r 分别为 G 的顶点数，边数和面数。30设 A=1，2，3，4，关系)AA()AA(R，Ad,c,b,a|,R，cbdadcba，证明：R是等价关系五、应用题31下述逻辑推理是否有效？证明你的结论。所有羊都吃草，所有死羊都不吃草。所以，所有死羊都不是羊。32已知英文字符串adacatedecade，试用二进

21、制字符串代替此英文字符串，并保证该英文字符串与二进制串构成一一对应。模拟试题(四)一、单项选择题在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。1设命题公式G=(pq),H=p(q p)，则 G与 H的关系是()A.GH B.HG C.可满足 D.以上都不是2设集合 A=1,2,3,10，关于集合A 为不封闭的运算是（）。A.x*y=maxx,y B.x*y=minx,y C.x*y=x 与 y 的最大公约数 D.x*y=x 与 y 的最小公倍数3设论域 E=a,b，且 P(a,a)=T，P(a,b)=F，P(b,a)=T，P(b,b)=F 则在下列公式中真值为

22、T的是()A.xyP(x,y)B.xyP(x,y)C.xP(x,x)D.x yP(x,y)4设 A=a,a,下列式子中正确的有（）。A.aP(A)B.aP(A)C.aP(A)D.以上都不是5设 R,S 是集合 X=1,2,3,4 上的两个关系，其中R=,S=,。则 S是 R的（）闭包。A.自反 B.对称 C.传递 D.以上都不是6设 S=1,1/2,2,1/3,3,1/4,4，“*”为普通乘法，则 是（）。A.半群，但不是独异点 B.是独异点，但不是群 C.群 D.不是代数系统7设集合 A=a,b，A上的关系 R=,，则 R是（）（1）写出集合A,R;（2）求 A的极大元和极小元；（3）求 B

23、=e,f的上确界和下确界。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 22 页 -8 A.是等价关系但不是偏序关系 B.是偏序关系但不是等价关系C.既是等价关系又是偏序关系 D.既不是等价关系又不是偏序关系8G是连通的平面图，有5 个结点，6 个面，则 G的边数为（）A.6 B.5 C.11 D.9 9下面命题中，为真的是（）。A.完全图 Kn(n1)都是欧拉图 B.完全二部图Kn,m(n1,n 1)都是欧拉图 C.完全图 Kn(n3)都是哈密顿图 D.完全二部图Kn,m(n1,n 1)都是哈密顿图10设集合 A=a,b,c,d,B=1,2,3,4,则从 A到 B的函数 f=

24、,是（）。A.f是双射函数 B.f是入射函数C.f是满射函数 D.f即不是满射又是不是入射函数11设,G是群，Gba,则下列结论不正确的是（）A111)(ababBbax有惟一解Cyxayax，则Dbaab12在自然数集N 上，下列定义的运算中不满足结合律的（）Aa*b=min(a,b)Ba*b=a+b Ca*b=gcd(a,b)(a,b 的最大公约数)Da*b=a-b 13 在简单无向图G=(V,E)中，如果 V 中的每个结点都与其余的所有结点邻接，则该图称为()。A连通图B强连通图C完全图D 平凡图。14对一阶逻辑公式(,)(,)(,)xy P x yQ y zxP x y的说法正确的是(

25、).A x 是约束的，y 是约束的，z是自由的;Bx 是约束的，y 既是约束的又是自由的，z 是自由的;C x 是约束的，y 既是约束的又是自由的，z 是约束的;D x 是约束的，y 是约束的，z是约束的.15.下面图中，（）是平面图.ABCD二、填空题16已知集合A=,1,2，则 A的幂集为 _。17已知命题公式G=(p q)r,则 G的主合取范式是_ _。18在有理数集合Q 上定义二元运算“*”，x,yQ 有 x*y=x+y-xy，则当xQ，当 x-1 时，其逆元为。19设集合 A=a,b,c,d，A 上关系 R=,则关系 RoR-1=_。20设 A=0,2,3,4,5,8,B=10,12

26、,13,14,15,16,则 A到 B的一个双射函数为_。21无孤立结点的有限有向图是欧拉图的充要条件是_ _。22具有 16 个结点的完全有向图其边数一定为_。23设 a 是群 的幂等元，则a一定是。24设 G 是完全正则二叉树，G 有 15 个点，其中8 个叶点，则G 的总度数为 _，分枝点数为 _。三、计算题25设集合 A=1,2,3，试写出 A 上的所有等价关系。26.是否可以分别画出一个图，使各点的度与下面给出的序列一致。如可能，画出符合条件的图，如不可能，说明原因。（1）3，3，3，3，3，3（2）3，4，7，7，7，7（3）1，2，3，4，5，5 27.设 T 是如下的二叉树，写

27、出对T 进行先序遍历、中序遍历和后序遍历时访问节点的顺序。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 22 页 -9 28.设 R 是实数集，At=x|xR Ktxt+1，其中 K0=K2=0，K1=K3=-1，K4=-2，令 S=At|t=0,1,2,3,4。画出偏序集 的哈斯图，并求它的极大元、极小元、最大元和最小元。说明该偏序集构成什么格？29给定解释如下：（1）3,2D（2）2a（3）2)3(,3)2(ff（4）1)3(,0)2(:)(FFxF3,2,1),(:),(jijiGyxG1)3,3()2,2(:),(LLyxL0)2,3()3,2(LL求下列各式的值，并说

28、明理由：（1）),()(axGxFx（2）)(,()(xfxGxfFx（3）),(yxyLx四、证明题30设 A,B 为任意集合，E 为全集，证明：B(AB)A)=E。31证明：任何图（无向图或有向图）中，奇度顶点的个数是偶数。32设函数 f：A B，g：BC，f、g 都是双射函数。求证(fog)-1=g-1of-1。五、应用题33在谓词逻辑中构造下面推理的证明：所有不守信用的人都是不可信赖的，有些可以信赖的人是受过教育的。因此，有些受过教育的人是守信用的。（个体域：所有人的集合）34构造欧拉图，其结点数v 和边数 e 满足下述条件：（1）v,e 的奇偶性一样；（2）v,e的奇偶性相反。如果可

29、能，分别画出两个欧拉图；如果不可能，说明原因。模拟试题(五)一、单项选择题在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。1设 p:天下大雨，q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上班”的符号化形式为（）。ApqBqpCpq Dpq2设解释 I 如下，个体域D=a,b,F(a,a)=(b,b)=0,F(a,b)=F(b,a)=1，在解释I 下，下列公式中真值为1 的是（）。Ax yF(x,y)B xF(x,y)CxyF(x,y)Dx yF(x,y)3设 G 为 n 阶 m 条边的无向简单图，下列命题为假的是（）。AG 一定有生成树Bm 一定

30、大于 n CG 的边色数(G)DG 的最大度(G)n-1 4设 G 为完全二部图K2,3，下面命题中为真的是（）。AG 为欧拉图BG 为哈密尔顿图CG 为平面图DG 为正则图5对于任意集合X,Y,Z，则（）。名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 22 页 -10 AXY=XZY=Z BXY=XZY=Z CXY=X ZY=Z D XY=XZY=Z 6设 Z 是整数集合，“+”是一般加法，则下述函数中不是群 的自同态的是（）。Af(x)=xBf(x)=1000 xCf(x)=|x|Df(x)=0 7设 R 为实数集，定义*运算如下：a*b=|a+b+ab|，则*运算满足（）

31、。A结合律B交换律C有幺元D幂等律8设 G是一个哈密尔顿图，则G一定是()。A欧拉图 B树 C平面图 D 连通图9下面给出的集合中，哪一个是前缀码？()A0，10，110，101111 B01，001，000，1 Cb，c，aa，ab，aba D 1，11，101，001，0011 10设 G是有 n 个结点 m条边的连通平面图，且有k 个面，则k 等于()。A.m-n+2 Bn-m-2 Cn+m-2 Dm+n+2。11在自然数集N上，下列哪种运算是可结合的？（）A a*b=a-b Ba*b=maxa,b Ca*b=a+2b Da*b=|a-b|12集合 A=1,2,10 上的关系 R=|x+

32、y=10,x,yA，则 R满足（）。A自反性B对称性 C传递性，对称性 D 传递性13设 P=x|(x+1)24 且 xR,Q=x|5x2+16 且 xR,则下列（）正确。A QP B QP CPQ DP=Q 14Q是有理数集，（其中*为普通乘法）不能构成()。A群B独异点 C半群D.交换半群15若一棵完全二元（叉）树有2n-1 个顶点，则它（）片树叶。An B2n Cn-1 D 2 二、填空题16含 n 个命题变项的重言式的主合取范式含_个极大项。17在有理数集Q 上定义二元运算“*”，x,yQ 有 x*y=x+y-xy，则关于运算“*”的幺元是。xQ，当 x 1 时，其逆元为。18以 1，

33、1，1，2，2，3 为度数序列的非同构的无向树共有_棵。19已知 n 阶无向简单图G 有 m 条边，则 G 的补图 G 有_条边。20设 R=，则 ranR=_。21设 A=1,2,3,4，则 A 上有 _个不同的双射函数。22任一有向图中，度数为奇数的结点有_个。23令 R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为。24设 G=0,1,2,3，为模 4 加法，群 中的 4 阶元是。三、计算题25设 X=1,2,3,4，若是整数2|,yxyxH3,是正整数，yxyxS，求HSHSH,。26.有向图 D=如下图所示，名师资料总结-精品资料欢迎下载-名师

34、精心整理-第 10 页，共 22 页 -11 27.设 A=x|xR x 0,1。在 A 上定义 6 个函数如下：16151431211,1,1,1,xxxfxxxfxxfxxfxxfxxf令 F为这 6 个函数构成的集合，运算为函数的复合运算。（1）给出运算的运算表。（2）验证 是一个群。28（5 分）设图 G 有一棵树，它有n2个 2 度分支点，n3个 3 度分支点，,nk个 k 度分支点，求G 中叶结点数。四、证明题29设正整数的序偶集合A，在 A 上定义的二元关系R 如下：,Rxv=yu。证明R是一个等价关系。30证明在任何n 阶有向完全图中，所有结点入度的平方之和等于所有结点的出度平

35、方之和。五、应用题31将下列推理符号化并给出形式证明：鸟会飞，猴子不会飞，所以，猴子不是鸟。32）某城市拟在六个区之间假设电话网，其网点间的距离如下带权矩阵给出，试给出架设线路的最优方案，请画出图并计算出线路长。模拟试题(六)五、单项选择题在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。1、若 p：他聪明；q：他用功；则“他虽聪明，但不用功”，可符号化为,()A.p q B.p q C.p q D.p q 2、以下命题公式中，为永假式的是,()A.p(pqr)B.(p p)p 求：（1）D 中 v1到 v4的长度为 1,2,3 的通路各有几条？（2）D 中长度

36、3 的通路共有几条？其中几条是回路？名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 22 页 -12 C.(q q)p D.(q p)(p p)3、关于命题变元p 和 q 的大项 M01表示,()。A.p q B.p q C.p q D.p q 4、下列式子正确的是,()A.B.C.D.5、设 R,S 是集合 X=1,2,3,4 上的两个关系，其中R=,S=,。则 S是 R 的（）闭包。A.自反B.对称C.传递D.以上都不是6、设 A=a,b,c，则下列是集合A 的划分的是,()A.b,c,c B.a,b,a,c C.a,b,c D.a,b,c 7、.下列不是平面图的是,()8

37、、G 是连通的平面图，有9 个结点，11 个面，则 G 的边数为,（）A.16 B.15 C.17 D.18 9、在自然数集N 上，下列哪种*运算是可结合的,（）A.a*b=a-bB.a*b=maxa,bC.a*b=a+2bD.a*b=|a-b|10、不能构成代数系统的是,（）A.有理数集合Q，x*y=(x+y)/2 B.自然数集合N，x*y=2xyC.AR，x*y=|x-y|D.A=1,-2,3,2,-4,x*y=|y|六、填空题11、已知公式A 含有 3 个命题变项p，q，r，并且它的成假赋值为000，011，110，则 A 的主析取范式为_，A 的主合取范式为_12、令 p:a 能被 4

38、 整除，q：a 能被 2 整除，则命题“只有a 能被 4 整除，a 才能被 2 整除”符号化为_。13、集合，2,2的幂集为 _。14、设 f：R R,f(x)=x2-3x+2,，其中 R 为实数集，则f(1,3)f-1(6)=_ 15、完全二部图K3,4中，点连通度为_，边连通度为_，点色数为_，边色数 为_，匹配数1为_。名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 22 页 -13 七、解答题16、使用容斥原理解题：某班有 25 个学生，其中14 人会打篮球，12 人会打排球，6 人会打篮球和排球，5人会打篮球和网球，还有两人会打这三种球。已知6 个会打网球的人都会打篮

39、球或排球。求不会打球的人数。17、给出偏序集 上偏序关系R 的关系图（如下图所示）。（1）求偏序集 的哈斯图。（2）指出 A的最大、最小元（如果有的话），极大、极小元。（3）指出该偏序集是格吗？请说明理由18、一棵树有2n个结点度数为2，3n个结点度数为3，,，kn个结点度数为k，问它有几个度数为 1 的结点。19、已知某系统在通讯联络中只可能出现5 种字符 a,b,c,d,e，其概率分别为0.10，0.22，0.27，0.15，0.26，试画出赫夫曼树并设计赫夫曼编码。20、若 S=1,2,3,19,20,21，设 R 为 S 上的等价关系，且由x y(mod 5)所定义，即x y 能被10

40、 整除。（1）写出由R 导出的 S 的划分；（2）求出商集S/R；（3）设 I 为 S上的恒等关系，试求R I。四、证明题21如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI 语言而且学过C+语言。只要他学过DELPHI 语言或者C+语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。（10 分）22、设 A，B，C是任意集合，证明：（A-B）(B-A)=(A B)-(AB)（5 分）23设 R 是实数集合，S=（a,b）a0,a,b R,利用通常的加法和乘法在S 定义“*”如下：对S中的任意元素(a,b)，(

41、c,d)(a,b)*(c,d)=(ac,ad+b)证明 S对“*”运算做成群.（10 分）模拟试题(七)八、单项选择题在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。1、已知：已知|G|=18，其某一子群|H|=6，则|G：H|为,（）A、18 B、6 C、3 D、不确定值2、公式 p(qp)的类型为,()。a b d c e 名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 22 页 -14 A.永真式B.永假式C.可满足式D.一般命题公式3、设解释 R：论域 D 为实数集，a=0，f(x,y)=x-y，A(x,y)：xy.则下列公式在 R 下为

42、真的是,()A.xyz(A(x,y)A(f(x,z),f(y,z)B.x A(f(a,x),a)C.xy（A(f(x,y),x)D.xy(A(x,y)A(f(x,a),a)4、设 A=a,a,下列式子中正确的有,（）。A.a (A)B.a(A)C.a(A)D.以上都不是5、设集合 A=1,2,3 ，A 上的关系 R=,，则 R 不具有（）性质。A.自反性B.对称性C.传递性D.反对称性6、无向图 G 中有 16 条边，且每个结点的度数均为2，则结点数是,()A.8 B.16 C.4 D.32 7、xF(y,x)yG(y)的前束范式为,()A.)(),(yGxzFyx；B.)(),(yGxzFy

43、x；C.)(),(yGxzFyx；D.)(),(xGxzFyx；8、设,Sa b c d，在 S 上定义等价关系abbaIRS,，那么该等价关系对应的划分中有()个划分块。A.1 B.2 C.3 D.49、下列各图不是欧拉图的是,（）10、设 Z 为整数集合，*为 Z 上的二元运算，x*y=x+y-3,则 Z 关于*运算构成群，已知5*x=4，则x 为,()A.5/4 B.4/5 C.2 D.3 九、填空题11、已知公式A 含有 3 个命题变项p，q，r，并且它的成假赋值为001,010,100,101,111,则 A 的主析取范式为_，A 的主合取范式为_12、符号化命题：除非a能被 2 整

44、除，否则a 不能被 4 整除。_。13、在一个群 G,*中，若 G中的元素 a 的阶是 k，则 a-1的阶是 _.名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 22 页 -15 14、集合，2,的幂集为 _。15、设 A=，B=1,2,3，则 AB=。16、Q 为有理数集，Q 上定义运算*为 a*b=a+b-ab，则 的单位元是。17、完全二部图K4,5中，点连通度为_，边连通度为_，点色数为_，边色数 为_，匹配数1为_。十、解答题18、对 60 个学生参加课外活动的情况进行调查。结果发现，25 人参加物理小组，26 人参加化学小组，26 人参加生物小组。9 人既参加物理小

45、组又参加生物小组，11 人既参加物理小组又参加化学小组，8 人既参加化学小组又参加生物小组。8 人什么小组也没参加，请回答：（1）有多少人参加了 3 个小组？（2）只参加一个小组的有多少人？。19、无向树 T 有 1 个 2度顶点，3 个 3 度顶点,4 个 4 度顶点,1 个 5 度顶点,其余的都是树叶，则T有几片树叶？20、设 A=1,2,3,4,5,A上偏序关系R=,IA;(1)作出偏序关系 R 的哈斯图(2)令 B=1,2,3,5，求 B 的最大、最小元，极大、极小元，上界，上确界，下界，下确界。21、画出如下所示图的一棵最小生成树，并计算最小生成树的权重。(10 分)22、设 为模

46、6加群，求商群Z6/。四、证明题23、对任意集合A，B，C，证明：（A B）B=A B 24、在一阶逻辑自然推理系统F 中构造下面推理的证明每个喜欢步行的人都不喜欢骑自行车，每个人或者是喜欢骑自行车或者喜欢乘汽车，有的人不喜欢乘汽车，所以有的人不喜欢步行。（个体域为人的集合）。25、设正实数集合R+和实数集合R，+和 x 是普通加法和乘法，定义映射:fRR，,()lnxRf xx，证明,fRR是从到的同构。模拟试题(八)十一、单项选择题在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。1、若 p：天下大雨；q：他乘公共汽车上班；则“除非天下大雨，否则他不乘公共汽车

47、 上班。”可符号化为,()A.p q B.p q C.p q D.qp2、)(),(yyGxyxF的前束范式为,()名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 22 页 -16 A.)(),(yGxyFyx；B.)(),(yGxzFyx；C.)(),(yGxzFxy；D.),(),(yxGzxFyx；3、设谓词 P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式x(P(x)Q(x)在哪个个体域中为真()A.自然数 B.实数C.复数D.A-C均成立4、令 F(x):x 是兔子，G(x):x 是乌龟，H(x,y):x 比 y 跑得快，命题“并不是所有的兔子比乌龟跑得快”可以符

48、号化为,（）A.),()()(yxHyGxFyx；B.),()()(yxHyGxFyx；C.),()()(yxHyGxFyx；D.),()()(yxHyGxFyx5、设,1,1,2S，则)(SP有()个元素A.3 B.16 C.6 D.86、设3,2,1S，左图是S上关系 R1的关系图，则它具有()性质.A.自反的，对称的，传递的；B.反自反的，反对称的；C.自反的，传递的；D.自反的；7、设,RV，其中为普通乘法，对任意Rx令xx2)(1，22)(xx，xx1)(3，xx)(4，则其中有（）个是V的自同态，A.0 B.1 C.2 D.3 8、设 Z 是整数集合，则下面定义的二元运算不能使Z

49、与构成代数系统的是()A.ij=|i-j|,i,j Z B.ij=i j-j2，i,jZ C.ij=i/j,i,j Z D.ij=i2+j2+1,i,j Z 9、设,G是群，Gba,则下列结论不正确的是,（）A.111)(ababB.bax有惟一解C.yxayax则,D.baab10、设无向图G有 16 条边且每个顶点的度数都是2，则图 G有()个顶点。A.10 B.4 C.17 D.16 十二、填空题11、命题公式rqp)(的主析取范式中含极小项的个数为_，成真赋值为_。12、令 F(x)：x 是人。G(x)：x 犯错误。则命题“没有不犯错误的人”符号化为_ 13、设n阶无向简单图G中，1)

50、(nG，问)(G为_.14、素数阶群一定是_群,它的生成元是 _。15、全二部图)1,1(,mnKmn都是欧拉图，这个命题的真值为_;名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 22 页 -17 16、群，为模 6 加法运算，则子群 H 0,2,4 的所有的右陪集为_,_.17、集合 A 的一个划分，确定A 的元素间的关系为_ 18、设 Z 是整数集，在Z 上定义二元运算*为 a*b=a+b+a b，其中+和是数的加法和乘法，则代数系统 的幺元是，零元是。十三、解答题19、求rqp)(的主析取范式和主合取范式。20、用容斥原理解题：某班级有学生四十名，共有三门选修课可供选择