2006离散数学a（答案）

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??000003123200011010?0?? A2=1??1??0?0??0??0000020111?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<=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

本文来源：https://www.bwwdw.com/article/rgsr.html