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

课程代码：02324

第一部分 选择题 (共16分)

一、单项选择题 (本大题共8小题，每小题2分，共16分)
 1.设p:天下大雨，q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上班”的符号化形式为 [  ]
 A.p→q  B.q→p
 C.p→┐q  D.┐p→q
 2.设解释I如下，个体域D={a,b},F(a,a)=(b,b)=0,F(a,b)=F(b,a)=1，在解释I下，下列公式中真值为1的是 [  ]
　　A.VxヨyF(x,y) B.ヨxVyF(x,y)
 C.VxVyF(x,y)  D.┐ヨxヨyF(x,y)
 3.设G为n阶m条边的无向简单图，下列命题为假的是 [  ]
　　A.G一定有生成树 B.m一定大于n
 C.G的边色数χ'≥Δ(G) D.G的最大度Δ(G)≤n-1
 4.设G为完全二部图K2,3，下面命题中为真的是 [  ]
 A.G为欧拉图 B.G为哈密尔顿图
 C.G为平面图 D.G为正则图
 5.对于任意集合X,Y,Z，则 [  ]
 A.X∩Y=X∩Z=>Y=Z  B.X∪Y=X∪Z=>Y=Z
 C.X－Y=X－Z=>Y=Z  D.X⊕Y=X⊕Z=>Y=Z
 6.下面等式中唯一的恒等式是 [  ]
 A.(A∪B∪C)-(A∪B)=C  B.A⊕A=A
 C.A-(B×C)=(A-B)×(A-C) D.A×(B-C)=(A×B)-(A×C)
 7.设R为实数集，定义*运算如下：a*b=|a+b+ab|，则*运算满足 [  ]
 A.结合律  B.交换律
 C.有幺元  D.幂等律
 8.在有补格L中，求补 [  ]
 A.是L中的一元运算 B.一定有唯一的补元
 C.不一定是L中的一元运算 D.可能没有补元

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

二、填空题 (本大题共10小题，每空3分，共24分)
 9.含n个命题变项的重言式的主合取范式为_________________________。
10.设个体域为整数集合Z，命题Vxヨy(x+y=3)的真值为___________。
11.以1，1，1，2，2，3为度数序列的非同构的无向树共有___________棵。
12.已知n阶无向简单图G有m条边，则G的补图G有__________条边。
13.设R={<{1},1>，<1,{1}>，<2,{3}>，<{3},{2}>}，则domR⊕ranR=_____________________。
14.设A={1,2,3,4}，则A上有____________个不同的双射函数。
15.设σ=(1345)(2678)是8元置换，则σ-1=___________。
16.设B为布尔代数，a,b,c∈B，则((a∧b)∧(a∨c))∨a的化简式为____________________。

三、简答题 (本大题共8小题，每小题5分，共40分)
17.设p：2+2=4，q=3+3=7，4+4=8，求下列个复合命题的真值。
 (1)(p∧q)←→r
 (2)(p←→r)←→(q←→r)
 (3)(p∨┐q)→(q→r)
 (4)┐q→(p←→r)
 (5)(p∨q)→(┐p∧q∧r)
18.求公式Vx(┐ヨyF(x,y)→ヨzG(x,z))的前束范式。
19.已知无向图G有12条边，1度顶点有2个，2度、3度、5度顶点各1个，其余顶点度数均为4，求4度顶点的个数。
20.已知连通的平面图G的阶数n=6，边数m=8，面数r=4。求G的对偶图G*的阶数n*，边数m*，面数r*。
21.设A={{a,{b}},c,{c},{a,b}}，B={{a,b},{b}}，计算
 (1)A∩B
 (2)A⊕B
 (3)P(B)
22.对于下面给定集合A和B，构造A到B的双射函数。
 (1)A=Z，B=N，其中Z，N分别表示整数集和自然数集。
 (2)A=[π,2π]，B=[-1,1]是实数区间。
23.设代数系统V=<Z6，×>，Z6={0,1,...,5}，×为模6乘法。
 (1)给出×运算的运算表。
 (2)求出所有可逆元素关于×运算的逆元。
 (3)说明V构成什么代数系统。
24.设Zn为模6加群，f:Z12→Z3，f(x)=(x)=mod 3，则f为同态映射。
 (1)验证f是否为单同态和满同态。
 (2)令H={x|f(x)=0}，计算H。

四、证明题 (本大题共4小题，每小题5分，共20分)
25.在命题逻辑中构造下面推理的证明。
 前提：p→s，q→r，┐r，p∨q
 结论：r
26.设G为n(n≥3)阶无向简单图，证明G或G的补图G必连通。
27.设A，B，C为集合，证明A∩(B－C)=(A－C)∩(B－C)
28.设群G中含有2阶元a，证明G中与a可交换的元素构成G的子群。