2023离散数学a（答案）

本文格式为Word版，下载可任意编辑——2023离散数学a（答案）2023年下半年《离散数学》（闭卷）70学时

离散数学（A卷）

闭卷、70学时

一、填空选择题(每空1分，共26分)

1、给定命题公式如下：p?(q??r)。该公式的成真赋值为A,成假赋值为B,公式的类型为C。

供选择的答案

A：①无；②全体赋值；

③010，100，101，111；④010，100，101，110，111。

B：①无；②全体赋值；③000，001，011；④000，010，110。C：①重言式；②矛盾式；③可满足式。

（?x)(P(y)?Q(x,y))?(?y)R(x,y)中，?x的辖域是P(z)→Q(x,z)，2、在公式

?y的辖域是R(x,z)。

3、设Z+={x∣x∈Z∧X>0},π1,π2,π3是Z+的3个划分。

π1={{x}∣x∈Z+},π2={S1,S2},S1为素数集,S2=Z+-S1.π3＝{Z+},(1)3个划分块中最多的是A,最少的是B.+++

(2)划分π1对应的是Z上的C,π2对应的是Z上的D,π3对应的是Z上的E.供选择的答案

A:(①),B:(③)①π1,②π2,③π3.C:(⑧),D:(⑨),E:(⑤)

④整除关系；⑤全域关系；⑥包含关系；⑦小于等于关系；⑧恒等关系；⑨含有两个等价类的等价关系；⑩以上关系都不是。

x?3xf(x)?{4、设f：R→R,g：R→R,g(x)=x+2,则f°g(x)为?2x?3f(x)?{(x?2)?222?2x?3x?1xf(x)?{，g°f(x)为，g°f：R→R0x?3x?12是A，f-1B,g-1C.供选择的答案

A；①单射不满射；②满射不单射；③不单射也不满射；④双射；B：（①），C：（②）：①不是反函数；②是反函数；

任课班级：114051-4、111051-2任课教师：孙明

1

2023年下半年《离散数学》（闭卷）70学时

5、①设G={0，1，2，3}，若⊙为模4乘法，则构成A.②若⊕为模4加法，则是B阶群，且是C。G中的2阶元是D，4阶元是E。供选择的答案

A；①群；②半群，不是群；B：③有限；④无限。

C：⑤Klein四元群；⑥置换群；⑦循环群；D（⑩），E（⑨）：⑧0；⑨1和3；⑩2。

6、设（A,∨,∧）是代数系统，二元运算∨和∧对于A是封闭的。假使对于A中任意的元素a，b，c满足交换律、结合律和吸收律，则称（A，∨，∧）是格。

7、6个顶点11条边的所以可能的非同构的连通的简单的非平面图有

4个，其中有2个含子图K3,3,有2个含与K5同胚子图。

二、计算题：（每题5分，任选6题，共30分）

321、计算幂集P(A)。A?{xx?R?x?2x?x?2?0}

答：P(A)={ф,{-1},{1},{2},{-1,1},{-1,2},{1,2},{-1,1,2}}

2、设S＝{1，2，3，4}，R是S上的二元关系，其关系矩阵为?1001??1000?求①R的关系表达式。

?R??②domR=?,ranR=?

?0001?③R°R中有几个有序对？???1000?④R-1的关系图中有几个环？

答：①关系表达示：{,,,,}

②domR={1,2,3,4},ranR={1,4}③7④1

3、S＝Q╳Q，Q为有理数集，*为S上的二元运算，任意，，

∈S有*＝①*运算在S上具有哪些主要性质；

②*运算有无单位元，零元？假使有请指出，并求S中所有可逆元素的逆元。

答：*运算不是可交换的；可结合的；在a=0且b∈Q或者〈1，0〉时满

足幂等律。〈1，0〉为*运算的单位元。对任意〈a,b〉∈Q×Q，只要

a0都存在逆元；不存在零元。

任课班级：114051-4、111051-2任课教师：孙明

2

2023年下半年《离散数学》（闭卷）70学时

4、有向图D如图1-1所示，

求D中长度为4的通路总数是多少？

并指出其中有多少条是回路？

其

图1-1

?0?0答：A???0??0?0?4?0A=?0??000003123200011010?0??A2=1??1??0?0??0??0000020231?1??A3=1??2??0?0??0??0000011123?1??2??3?4?2??从A4可看出，D中长度为4的通路有23条，其中7条为回路。3??5?5、当n和m为何值时，完全二部图Kn,m是

①欧拉图；②哈密顿图；③平面图；④非平面图。

答：①n和m都是正偶数；②n=m且n>=2；③n=3，m>=3

6、设无向树T由7片树叶，其余顶点的度数均为3，求T中3度顶点数，能画出几棵具有此种度数的非同构的无向树？

答：T中有5个3度顶点。设T中有x个3度顶点，则T中的顶点数n=7+x,边数m=n-1=6+x,由握手定理的方程2m=12+2x=3x+7,解出x=5,T的度数列为1，1，1，1，1，1，1，3，3，3，3，3。有两棵非同构的树。

7、在图1-2所示的无向图G中，黑线边所示的子图为G的一棵生成树T,求G的对应于T的基本回路系统。

对应生成树的弦分别为e6,e7,e8,e10,e11。

设它们对应的基本回路分别为C1,C2,C3,C4,C5，从对应的弦开始，按逆时针（也可都按顺时针）的顺序写出它们，分别为

C1＝e6e4e5C2＝e7e2e1C3＝e8e9e2e1C4＝e10e3e5e2C5＝

e11e3e5e2e9

此图的圈秩为5，基本回路系统为{C1,C2,C3,C4,C5}。

任课班级：114051-4、111051-2任课教师：孙明

3

2023年下半年《离散数学》（闭卷）70学时

三、证明题（每题6分，任选4题，共24分）

1、设H1和H2是群的两个互不包含的子群，证明G中存在一个元素，

它既不属于H1，也不属于H2。

证明：由于H1?H2,所以存在a∈H1,且a?H2，又由于H2?H1，所以存在

b∈H2,且b?H1，显然a*b∈G，由于a∈H1,是的子群，可推出b∈H1,这与b?H1矛盾。同理可证，a*b?H2

2、证明欧拉图中必没有割边。

证明：主要利用“无向图中，奇度顶点的个数为偶数〞这一结论用反证法，设欧拉图中含有割边。由于欧拉图中每一个顶点的度数为偶数，所以割边的两个端点也是偶数度顶点。删去割边后，构成两个连通分支，每个连通分支都含有割边的一个端点；此时每一个连通分支中仅有一个奇数度顶点，这与已知矛盾。所以，欧拉图中没有割边。

3、设是格，任取a∈L,令S＝{x∣x∈L∧x≤a}

证明是L的子格。

证明：对于任意的x,y∈S，必有x?a和y?a,所以x∨y?a,x∧y?a，故x∨y∈S,x∧y∈S,因此是的子格。

4、设G是6阶无向简单图，证明G或它的补图中存在3个顶点彼此相邻。证明：设6个顶点的简单图为G,考察G中的任意一个顶点a，那么，另

外5个顶点中的任何一个顶点，要么在图G中与a邻接，要么在图G’中与a邻接。这样，就把5个结点分成两类，将会必有一类至少含有三个顶点。不妨假设其中的3个顶点为b，c，d。该图必是图G*的子图（这里图G*可能是G或者是G’）。假使边(b,c),(c,d),(b,d)中有一条边在G*择优3个顶点邻接。假使边(b,c),(c,d),(b,d)都不在G*中，那么必在G*的补图（或是图G’或者是G）中，因此，必有3个顶点邻接。

5、设n阶m条边的平面图是自对偶图，证明m=2n-2.证明；设G*图是G的对偶图，所以G必为连通的平面图，且n*=r,m*=m,r*=n

于是n=n*=r，由欧拉公式可知，n-m+r=2=n-m+n得m=2n-2

6、验证K5和K3,3都是微小非平面图。答：画图举例。

四、应用题（每题10分，共20分）

1、在自然推理系统F中，证明下面推理：每个喜欢步行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车。所以有的人不喜欢步行。（个体域为人类集合）。解：设P(x)：x喜欢步行；Q(x)：x喜欢乘汽车；R(x)：x喜欢骑自行车；此题符号化为前题：?x(P(x)→┐R(x)),?x(R(x)∨Q(x))，?x┐Q(x)结论：?x┐P(x)①?x┐Q(x)前提引入②?x(R(x)∨Q(x))前提引入

任课班级：114051-4、111051-2任课教师：孙明

4

2023年下半年《离散数学》（闭卷）70学时

③┐Q(c)①EI规则

④R(c)∨Q(c)②UI规则

⑤?x(P(x)→┐R(x))前提引入⑥P(c)→┐R(c)⑤UI规则⑦R(c)③④析取三段论⑧┐P(c)⑥⑦拒取式⑨?x┐P(x)⑧EG规则

2、今有n个人，已知他们中的任何二人和起来认识其余的n-2个人。证明：当n≥3时，这n个人能排成一列，使得中间的任何人都认识两旁的人，而两旁的人认识左边（或右边）的人。而当n≥4时，这n个人能排成一个圆圈，使得每个人都认识两旁的人。

解：设n个人分别为V1,V2,V3,?,Vn,?V={V1,V2,V3,?,Vn}为顶点集。若Vi

与Vj认识，就在代表它们的顶点间连一条无向边，得边集E，于是的无向简单图G=。对于任意Vi,Vj∈V，假设Vi与Vj不相邻，则对任意Vk∈V，（ki,kj）必与Vi或Vj相邻。否则与已知条件矛盾。不妨假设，VK与Vi相邻，与Vj不相邻。那么Vk与Vi所代表的两个人都不认识Vj所代表的人，这与已知矛盾。所以VK与Vi相