离散数学复习材料

1．（10分）求(PQ)(PR)的主析取范式与主合取范式。

(PR )解 (PQ)((PQ)(PR))((PR)(PQ))

（1分，这里等价式的变换用其他方法也正确）

((PQ)(PR))((PR)(PQ)) （1分） ((PQ)(PR))((PR)(PQ)) （1分） (PR)(PQ)(QR) （1分）

(PQR)(PQR)(PQR)

(PQR)(PQR)(PQR) （1分）

M1M3M4M5 （2分） m0m2m6m7 （1分）

(PQR)(PQR)(PQR)(PQR) （2分） （说明：若用真值表做，真值表正确共6分，结果每个2分，共4分；中间

一步因为笔误出错，方法思路正确的扣2分）

2．（15分）在谓词逻辑中构造下面推理的证明：“前提：每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车，有的人不喜欢骑自行车。结论：有的人不喜欢步行。”

解：论域：所有人的集合。A(x)：x喜欢步行；B(x)：x喜欢坐汽车；C(x)：x喜欢骑自行车；则推理化形式为： （每个题设正确得1分）

x(A(x)B(x))，x(B(x)∨C(x))，xC(x)

下面给出证明： （下面每步1分，共10分） (1)xC(x) P (2)xC(x) (3)C(c)

T(1)，E T(2)，ES P T(4)，US T(3)(5)，I P T(7)，US T(6)(8)，I T(9) ，EG

1 / 5

xA(x)

（2分）

(4)x(B(x)∨C(x)) (5)B(c)∨C(c) (6)B(c)

(7)x(A(x)B(x)) (8)A(c)B(c) (9)A(c)

(10)xA(x)

3．（15分）设正整数的序偶集合A，在A上定义的一个二元关系R如下：

x,y,u,vR当且仅当xvyu。

(1) 证明R是一个等价关系。 (10分)

(2) 若A={<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 4>, <2, 6>, <4, 1>, <4, 2>}，试写出R所决定的A上的划

分。(5分)

证明：(1) xvyu a. 自反性

xu yv

（3分）

x,yA, b. 对称性

xxx,yRx,y yy

（3分）

x,yRu,v c. 传递性

xuuxu,vRx,y yvvy

（4分）

若a,bRc,d且c,dRe,f，则

acceae且，显然，，即a,bRe,f bddfbf (2) {{<1,1>, <2,2>}, {<1,2>, <2,4>}, {<1,3>, <2,6>}, {<2,1>, <4,2>}, {<4,1>}}

（5个分块各1分，共5分）

4．（15分）设函数f：R×RR×R，f定义为：f()＝。

(1)证明f是单射。 (2)证明f是满射。

证明：(1)对任意的x，y，x1，y1∈R，若f()＝f()，则＝，x＋y＝x1＋y1，x－y＝x1－y1，从而x＝x1，y＝y1，故f是单射。

（5分，写出单射定义的给2分）

(2)对任意的∈R×R，令x＝，所以f是满射。

（5分，写出满射定义的给2分）

5． （10分）设I是所有整数的集合，在I上定义运算*如下：

uwuwuwuwuwuw，y＝，则f()＝<＋，－>＝222222x, yI, xyxy2

证明：I, >是群。

2 / 5

证明：a. 封闭性 （2分）

 x, yI, x*y b. 结合性

x

y2 I

（3分）

x*y)*z x, y,zI, (x(*y)z2xy z x*(y*z)x(y*z)2xyz2

故， (x*y)*zx*(y*z) c. 单位元是2 d.

6．（15分）设Z6,6是一个群，这里6是模6加法，Z6{[0],[1],[2],[3],[4],[5]}。

(1) 试写出Z6,6的每个子群；(6分) (2) 写出每个子群的左陪集形成的划分；(6分)

(3) Z6,6是否构成循环群？若是，试写出所有生成元。(3分)

解 (1) 1阶子群：<{[0]}, +6> 2阶子群：<{[0], [3]}, +6>

(1分) (2分) (2分) (1分) (1分) (2分) (2分) (1分) (1分)

（2分） （3分）

xI，x的逆元存在，为x14xI

3阶子群：<{[0], [2], [4]}, +6> 6阶子群：

(2) 1阶子群：{{[0]}, {[1]}, {[2]}, {[3]}, {[4]}, {[5]}} 2阶子群：{{[0], [3]}, {[1], [4]}, {[2], [5]}} 3阶子群：{{[0], [2], [4]}, {[1], [3], [5]}} 6阶子群：{ Z6 } (3) 是循环群。 生成元有: [1], [5]

(每个1分, 共2分)

7．（10分）有向简单图G=＜V, E＞中，V＝{ a, b, c, d, e }且 E={ , , , , , , , }, 画出该有向图；写出对应的邻接矩阵；求出可达矩阵；判断该图的连通性（回答强连通、弱连通或者单侧连通）。

3 / 5

解 该有向图：

邻接矩阵为： 可达矩阵为：

（3分，错1条线扣1分，扣完为止）

（2分，错1个位置，扣1分，扣完为止） （3分，错1个位置扣1分，扣完为止）

（2分）

该有向图为弱连通

8．（5分）设有33盏灯，拟公用一个电源，则至少需要多少个5插头的接线板?

解 把33盏灯看成树叶，将5插头的接线板看成分枝点，这样本问题可理解为求一个完全5叉树的分枝点的个数i的问题。

由定理7.8.1知， 有

（1分）

(51)i331

由此得

i＝8

所以至少需要8个5插头的接线板。

（2分）

（1分）

（说明：只画出图给出正确结果的扣2分）

9．（10分）设A{2,3,5,7,14,15,21}，其偏序关系

R{2,14,3,15,3,21,5,15,7,14,7,21,2,2,3,3

5,5,7,7,14,14,15,15,21,21}

求A,R的哈斯图和B{2,7,3,21,14}的极大元、极小元、最大元和最小元。（图中结点有箭头扣3分，少一条边扣1分）

解 COV A{2,14,3,15,3,21,5,15,7,14,7,21}，

（2分） （2分）

A,R的哈斯图如图所示。

4 / 5

故B的极小元集合是{2,7,3}。

（2分） （2分） （1分） （1分）

B的极大元集合为{14,21}。 B无最大元。 B无最小元。

2012高数II期末考试复习要点 题型 选择，填空，解答

重点 后半期所学内容：三重积分，曲线积分，曲面积分，级数

复习要点

1、 向量的数量积的计算；

2、 显函数的一阶偏导数、二阶偏导数的计算； 3、 空间曲面的切平面的计算；

4、 简单三重积分的计算，注意利用函数的奇偶性与区域的对称性； 5、 利用球面坐标计算三重积分； 6、 简单的第一型曲线积分的计算； 7、 第二型曲线积分的计算；（直接计算法，与Green公式） 8、 第二型曲线积分与路径无关的条件； 9、 第一类曲面积分的计算（直接计算法），注意利用函数的奇偶性与区域的对称性； 10、 空间曲面所围立体的体积； 11、 第二类曲面积分的计算；（投影面的转换法或两类曲面积分之间的联系计算，直接计算与利用Gauss公式计算） 12、 求幂级数的收敛域、和函数；

13、 幂级数在某些特殊点的收敛性的判断（阿贝尔定理）； 14、 简单函数展开为幂级数；

15、 函数展开为Fourier级数，Fourier级数的收敛定理。

5 / 5