发布时间 : 星期日 文章中国石油大学大学《离散数学》期末复习题及答案更新完毕开始阅读
8、设A={1,2,3,4}，R是A的二元关系，定义为：R={<1,1>,<1,2>,<2,1>,<3,2>, <3,1>,<4,3>,<4,2>, <4,1>}，写出A上二元关系R的关系矩阵。 解：R的关系矩阵为：
?1?1?1?1?101100010?0?0?0??
deg(v1)＝3，deg+(v1)＝1，deg-(v1)＝2； deg(v2)＝deg+(v4)＝deg-(v2)＝0； deg(v3)＝3，deg+(v3)＝2，deg-(v3)＝1； deg(v4)＝2，deg+(v4)＝1，deg-(v4)＝1；
9、设有向图G如下所示，求各个结点的出度、入度和度数。
10、设有向图G如下所示，求各个结点的出度、入度和度数。
答：
deg(v1)＝3，deg+(v1)＝2，deg-(v1)＝1； deg(v2)＝3，deg+(v2)＝2，deg-(v2)＝1； deg(v3)＝5，deg+(v3)＝2，deg-(v3)＝3； deg(v4)＝deg+(v4)＝deg-(v4)＝0；
11、设无向图G如下所示，求它的邻接矩阵。
deg(v5)＝1，deg+(v5)＝0，deg-(v5)＝1；
?0?1A(G)???0??1101??010?
101??010?
12、求命题公式┐(p∧┐q)的真值表。 p 0 0 1 1 q 0 1 0 1 ┐q 1 0 1 0 p∧┐q 0 0 1 0 ┐ (p∧┐q) 1 1 0 1 13、设<2x+y, 5>=<10, x－3y>，求x，y。 解：由定理列出如下方程组：
?2x?y?10 ??x?3y?5求解得x=5，y=0。
14、R1、R2是从{1, 2, 3, 4, 5}到{2, 4, 6}的关系，若R1＝{<1, 2>, <3, 4>, <5, 6>}，R2={<1, 4>, <2, 6>}，计算domR1，ranR1，fldR1，domR2，ranR2，fldR2。
解：domR1={1, 3, 5}，ranR1={2, 4, 6}，fldR1=dom R1∪ran R1={1, 2, 3, 4, 5, 6}； domR2={1, 2}，ranR2={4, 6}，fldR2=dom R2∪ran R2={1, 2, 4, 6}。
15、例：设A={1, 2, 3, 4, 5}，B={3, 4, 5}, C={1, 2, 3}，A到B的关系R={
解：R={<1, 5>, <2, 4>, <3, 3>}, S={<3, 1>, <4, 2>, <5, 3>}，从而R?S={<1, 3>, <2, 2>, <3, 1>} 或者因<1, 5>∈R，<5, 3>∈S，所以<1, 3>∈ R?S；因<2, 4>∈R，<4, 2>∈S，所以<2, 2> ∈R?S；因<3, 3>∈R，<3, 1>∈S，所以<3, 1> ∈R?S；从而R?S={<1, 3>, <2, 2>, <3, 1>} 16、集合A={a, b, c}，B={1, 2, 3, 4, 5}，R是A上的关系，S是A到B的关系。R={
S–1?R–1={<1, a>, <2, b>, <2, c>, <4, a>, <4, c>, <5, a>, <5, c>}。
17、A＝{1, 2, 3, 4, 5, 6}，D是整除关系，画出哈斯图并求出最小元、最大元、极小元和极大元。 解：
5 1 4 6 2 –
3
1是A的最小元，没有最大元，1是极小元，4、5、6都是A的极大元。
18、设集合A={a,b,c}，A上的关系R={
19、求下图中顶点v0与v5之间的最短路径。 v1 1 4 7 5 1 v33 v4 2 v5 6 v0 2 v2 解：如下图所示v0与v5之间的最短路径为：v0, v1, v2, v4 , v3, v5 最短路径值为1+2+1+3+2=9
20、分别用三种不同的遍历方式写出对下图中二叉树点的访问次序。
先根遍历：ABDEHCFIJGK 中根遍历：DBHEAIFJCGK 后根遍历：DHEBIJFKGCA
四、证明题（每题10分，共20分）
1、若R和S都是非空集A上的等价关系，证明R?S是A上的等价关系。
证明：?a∈A，因为R和S都是A上的等价关系，所以xRx且xSx。故x R?S x。从而R?S是自反的。
?a,b∈A，aR?Sb，即aRb且aSb。因为R和S都是A上的等价关系，所以bRa且bSa。
故b R?S a。从而R?S是对称的。
?a,b,c∈A，a R?S b且b R?S c，即aRb，aSb，bRc且bSc。因为R和S都是A上的等
价关系，所以aRc且aSc。故a R?S c。从而R?S是传递的。 故R?S是A上的等价关系。
2、证明苏格拉底论证：凡人要死。苏格拉底是人，苏格拉底要死。
设： H(x)：x是人。M(x)：x是要死的。s：苏格拉底。本题要证明：(?x)(H(x)→M(x))∧H(s)?M(s) 证明：
⑴ (?x)(H(x)→M(x))
⑵ H(s)→M(s) ⑶ H(s) ⑷ M(s)
P US⑴ P ⑵、⑶
3、P→Q，┐Q?R，┐R，┐S?P?┐S 证明：
(1) ┐R 前提 (2) ┐Q?R 前提 (3) ┐Q （1），（2） (4) P→Q 前提 (5) ┐P （3），（4） (6) ┐S?P 前提 (7) ┐S （5），（6）
4、在群
因为e?e=e，所以e是幂等元。设a?G且a?a=a，则有a=e?a=(a –1 ?a)?a=a –1?(a?a)=a–1 ?a=e， 即a=e。
5、设R和S是二元关系，证明：(R?S)-1=R-1?S-1 证明：
.