2004年4月北京市高教自考“离散数学”试题

一、单项选择题 (本大题共8小题，每小题2分，共16分)
 1.设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为 [  ]
 A.p→q  B.q→p
 C.┐q→p  D.┐p→q
 2.下面4个推理定律中，不正确的为 [  ]
 A.A=>(A∨B) (附加律)  B.(A∨B)∧┐A=>B (析取三段论)
 C.(A→B)∧A=>B (假言推理)D.(A→B)∧┐B=>A (拒取式)
 3.下列四组数据中，不能成为任何4阶无向简单图的度数序列的为 [  ]
 A.1,1,1,2 B.1,1,1,3
 C.2,2,2,2 D.1,2,2,4
 4.在同构意义下，以下命题为真的是 [  ]
 A.K3是K3,3的子图  B.K3是K4的子群
 C.K3是K3,4的子图  D.K3是K2,3的子图
 5.若X是Y的子集，则一定有 [  ]
 A.X不属于Y  B.X∈Y
 C.X真包含于Y  D.X∩Y=X
 6.设S={1,2,3,4}，R={<1,1>,<2,2>,<3,3>}，则R的性质是 [  ]
 A.自反、对称、传递的  B.自反、对称、反对称的
 C.对称、反对称、传递的  D.只有对称性
 7.下述*运算为实数集上的运算，其中可交换且可结合的运算是 [  ]
 A.a*b=a+2b  B.a*b=a+b-ab
 C.a*b=a D.a*b=|a+b|
 8.下面关于循环群的命题中的假命题是 [  ]
 A.循环群是Abel群
 B.循环群有有限个多个生成元
 C.无限循环群的子群都是无限循环群
 D.n阶循环群的有唯一的d阶子群，其中d是n的正因子

第二部分 非选择题 (共84分)

二、填空题 (本大题共10小题，每空3分，共30分)
 9.设个体域D={1,2}，命题Vxヨy(x+y=3)的真值为___________。
10.公式p→(q→r)在联结词全功能集{┐，∧}中等值形式之一为____________________。
11.完全二部图Kr,s(r≤s)的边连通度为___________。
12.命题“设G为任意的n阶简单的哈密尔图，则Vu，v∈V(G)，均有d(u)+d(v)≥n”的真值为___________。
13.设A={φ}，B={φ,{φ}}，则P(A)∩P(B)=___________。
14.设A={2,3,4}，B={4,5,6}，R是从A到B的关系，且xRy<=>x与y互质，那么R=____________________。
15.设B={1,2}，G=<P(B),⊕>为群，其中⊕为集合的对称差运算，那么方程X⊕{1}={2}的解是___________。
16.设σ=(134)(256)，τ=(25)(1643)，则στ=____________________。

三、简答题 (本大题共8小题，每小题5分，共40分)
17.用等值演算法求公式((p∨q)∧(p→q))←→(q→p)的主合取范式与主析取范式。
18.在个体域D={a,b,c}消去公式Vx(F(x)∧ヨyG(y))的量词。
19.有向图D=<V,E>如图所示，
 (1)D中v1到v4的长度为1,2,3,4的通路各有几条？
 (2)D中长度≤4的通路共有几条？其中几条是回路？
20.无向图G如图所示，在图G外，画出G的所有非同构的生成树各一棵。
21.设R是自然数集合N上的关系，且xRy<=>x+2y=10。
 (1)求dom R；
 (2)说明R具有的性质(自反、反自反、对称、反对称、传递)。
22.设偏序关系R的关系图如右所示，
 (1)画出R的哈斯图；
 (2)求出该偏序集的极大，极小、最大、最小元。
23.设G=<Z24，⊕>为模24整数加群，
 (1)求G的所有生成元。
 (2)求G的所有非平凡的子群。
24.设R=<Z,+>为整数加群，f:Z→Z，f(x)=5x，
 (1)验证f为R的自同态
 (2)说明f是否为单同态，满同态，为什么？

四、证明题 (本大题共4小题，每小题5分，共20分)
25.在一阶谓词逻辑中构造下面推理的证明。
 前提：Vx(F(x)∨G(x))，Vx(F(x)→H(x))，
 结论：Vx(┐H(x)→G(x))。
26.证明右边的无向图不是平面图。
27.证明：关系R在A上是对称的当且仅当R=R-1。
28.设V=<A,*>是代数系统，证明如果V中存在零元，则零元是唯一的。