2006离散数学a(答案)

1、2006 2006 （闭卷）70 学时任课班级：114051-4任课班级：114051-4、111051-2任课教师：孙明 PAGE 5离散数学（A 卷）闭卷、70 学时一、填空选择题 (每空1分，共26分)1p q rA,B,C。供选择的答案A：无；全体赋值；010，100，101，111；010，100，101，110，111。B：无；全体赋值；000，001，011；000，010，110。C：重言式；矛盾式；可满足式。2、在公式（x)(P( y) Q(x, y) (y)R(x, y) 中， x 的辖域是 P(z)Q(x,z) ，y的辖域是R(x,z)。3Z+=xxZX0,1, ,2是

2、Z+的 3 个划分。3 =xxZ+=S,S,S,S=Z+-SZ+,121212133AB.划分对应的是Z+上的C,对应的是Z+上的D,对应的是Z+123上的 E.供选择的答案A:( ) , .1,23C:( ),E:( )整除关系；全域关系；包含关系；小于等于关系；恒等关系；含有两个等价类的等价关系；以上关系都不是。4 、 设 f f (x) x x gRR,g(x)=x+2,则 fg(x) 为(x22x 3x122x 3f (x) 2x f(x)f (x) 0 x fRRB是A，f-1,g-1C.B供 选 择 的 答 案 A；单射不满射；满射不单射；（，C（ ：不是反函数；是反函数；BC5、

3、设 G=0，1，2，3，若为模 4 乘法，则构成 A.BC4 阶群，且是。G 中的 2 阶元是 D，E4 阶元是。E供 选 择 的 答 案 A；群；B：；无限。C：Klein；（，（ 0；13；2。6、设（A,）是代数系统，二元运算和对于A是封闭的。如果对于A中任意的元素满足交换、结合和吸收，则称是格。7、6 个顶点 11 条边的所以可能的非同构的连通的简单的非平面图有4个，其中有2个含子图有 2个含与K5同胚子图。二、计算题（每题5分，任选6题，共30分）1P(A)AxxR 3 2x2 x2答：P(A)=,-1,1,2,-1,1,-1,2,1,2,-1,1,22、设 S1，2，3，4，R 是

4、 S 上的二元关系，其关系矩阵为10011000求R 的关系表达式。Rdom R=?,ran R=? 00011000RR 中有几个有序对？的关系图中有几个环？答：关系表达示：,domR=1,2,3,4,ranR=1,4 7 13、SQQ，Q 为有理数集，*为 S 上的二元运算，任意，S 有*运算在 S 上具有哪些主要性质；*S 逆元。答： *a=0bQ或者1，01，0为*运算的单位元。对任意 a,bQQ，只要a0 都存在逆元；不存在零元。4D1-1图 1-1D4并指出其中有多少条是回路？其A 000A 000020001101010100000000201111120000000011121

5、323003001A4= 002000342 4 23 7 条为回路。3555、当 n 和 m 为何值时，完全二部图 Kn,m 是欧拉图；哈密顿图；平面图；非平面图。答：nmn=mn=2；n=3，m=36T73，T3能画出几棵具有此种度数的非同构的无向树？53Tx3Tn=7+x, 边数m=n-1=6+x,由握手定理的方程2m=12+2x=3x+7,解出x=5,T的度数列为 1，1，1，1，1，3，3，3，3，3。有两棵非同构的树。71-2GGT,求G 的对应于 T 的基本回路系统。对应生成树的弦分别为 e6,e7,e8,e10,e11。设它们对应的基本回路分别为 C1,C2,C3,C4,C5，

6、从对应的弦开始，按逆时针（也可都按顺时针）的顺序写出它们，分别为 e11e3e5e2e9此图的圈秩为 5，基本回路系统为C1,C2,C3,C4,C5。三、证明题（每题6 分，任选4 题，共24 分）1和21设HH 是群的两个互不包含的子群证明G 中存在一个元素，1和21H H 1H1 H2,aH1,aH，又因为，所以存在HHH111bH2,bH aH ,是的子111群，可推出 bH1,这与 bH1 矛盾。同理可证，a*bH22、证明欧拉图中必没有割边。设欧拉图中含有割边。由于欧拉图中每一个顶点的度数为偶数，所以割边的两个端点也是偶数度顶点。删去割边后，构成两个连通分支，每个连通分支都含有割边的

7、一个端点；此时每一个连通分支中仅有一个奇数度顶点，这与已知矛盾。所以，欧拉图中没有割边。3、设aL,SxxL证明L 的子格。x,ySxa和ya,所以ya,xyayS, xyS,因此是的子格。4G 6 G 3 6 G a，那么，另5 G a 邻接，要么在图a 5 个结点分成两类，将会必有一类至少含有三个顶点。不妨假3 的子图（这里图G 或者是 。如果边(b,c),(c,d),(b,d)中有一条边在 *择优 3 个顶点邻接。如果边 (b,c),(c,d),(b,d)G*G*的补图（G）中，因3 个顶点邻接。5nmm=2n-2.G*G G 于是 n=n*=r，由欧拉公式可知，n-m+r=2=n-m+

8、n 得 m=2n-26K5和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 结论： x P(x)x Q(x)前提引入x(R(x)Q(x)前提引入 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 n3nn4nnV,V,V,Vn,V=V,V,V,VnV123123iVE，于是的无向简单图jG=V,VVV与VVV（ki,kj）ijijkViVVjK相邻，与Vj不相邻。