2023年7月19日发(作者：)

2006年下半年《离散数学》（闭卷）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

-1

B ,g -1

C.

供选择的答案

A；①单射不满射；②满射不单射；③不单射也不满射；④双射；

B：（①），C：（

②）：①不是反函数；②是反函数；

任课班级：114051-4、

111051-2

任课教师：孙明 1 2006年下半年《离散数学》（闭卷）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②dom R=?,ran R=?

0001③R°R中有几个有序对？

1000④R-1的关系图中有几个环？

答：①关系表达示：{<1,1>,<1,4>,<2,1>,<4,1>,<3,4>}

②dom R={1,2,3,4},ran R={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，只要a<>0都存在逆元<1/a,-b/a>；不存在零元。

任课班级：114051-4、

111051-2

任课教师：孙明 2 2006年下半年《离散数学》（闭卷）70学时

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

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

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

其

图1-1

00答：A00040A=00110100 A2=110001 A3=120001

2342从A4可看出，D中长度为4的通路有23条，其中 7条为回路。

355、当n和m为何值时，完全二部图Kn,m是

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

答：①n和m都是正偶数；②n=m且n>=2；③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＝e6e4e5

C2＝e7e2e1C3＝e8e9e2e1

C4＝e10e3e5e2

C5＝

e11e3e5e2e9

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

任课班级：114051-4、

111051-2

任课教师：孙明 3 2006年下半年《离散数学》（闭卷）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

2006年下半年《离散数学》（闭卷）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，（k<>i,k<>j）必与Vi或Vj相邻。否则与已知条件矛盾。不妨假设，VK与Vi相邻，与Vj不相邻。那么Vk与Vi所代表的两个人都不认识Vj所代表的人，这与已知矛盾。所以VK与Vi相邻，也与Vj相邻。因此， Vi与Vj都与其余的n-2个顶点相邻，从而deg(Vi)+deg(Vj)=n-2+n-2=2n-4,由于n3,则2n-4n-1。由定理15.7可知，G中存在哈密顿通路。当n4由于2n-4n由定理15.7的推论可知，G是哈密顿图。

图1-2

任课班级：114051-4、

111051-2

任课教师：孙明 5