中国石油大学大学《离散数学》期末复习题及答案.docx

中国石油大学大学《离散数学》期末复习题及答案.docx

《中国石油大学大学《离散数学》期末复习题及答案.docx》由会员分享，可在线阅读，更多相关《中国石油大学大学《离散数学》期末复习题及答案.docx（24页珍藏版）》请在冰点文库上搜索。

中国石油大学大学《离散数学》期末复习题及答案

《离散数学》期末复习题

一、 填空题（每空 2 分，共 20 分）

1、集合 A 上的偏序关系的三个性质是、

和。

2、一个集合的幂集是指。

3、集合 A={b,c}，B={a,b,c,d,e}，则 A⋃B=。

4、集合 A={1,2,3,4}，B={1,3,5,7,9}，则 A⋂B=。

5、若 A 是 2 元集合, 则 2A 有个元素。

6、集合 A={1,2,3｝，A 上的二元运算定义为：

a* b = a 和 b 两者的最大值，则

2*3=。

7、设 A={a, b,c,d }, 则∣A∣=。

8、对实数的普通加法和乘法，是加法的幂等元，

是乘法的幂等元。

9、设 a,b,c 是阿贝尔群的元素，则-（a+b+c）=。

10、一个图的哈密尔顿路是。

11、不能再分解的命题称为，至少包含一个联结词的命题称

为。

12、命题是。

13、如果 p 表示王强是一名大学生，则┐p 表示。

14、与一个个体相关联的谓词叫做。

15、量词分两种：

和。

16、设 A、B 为集合，如果集合 A 的元素都是集合 B 的元素，则称 A 是 B

的。

17、集合上的三种特殊元是、

及。

18、设 A={a, b}，则 ρ（A） 的四个元素分别

是：

，，，。

19、代数系统是指由及其上的或

组成的系统。

20、设是代数系统，其中是* ,* 二元运算符，如果* ,* 都满

121212

足、，并且* 和* 满足，则称

12

是格。

12

21、集合 A={a,b,c,d}，B={b }，则 A \ B=。

22、设 A={1, 2}, 则∣A∣=。

23、在有向图中，结点 v 的出度 deg+（v）表示，入度 deg-（v）表示

以。

24、一个图的欧拉回路是。

25、不含回路的连通图是。

26、不与任何结点相邻接的结点称为。

27、推理理论中的四个推理规则

是、、、。

二、判断题（每题 2 分，共 20 分）

1、空集是唯一的。

2、对任意的集合 A，A 包含 A。

3、恒等关系不是对称的，也不是反对称的。

4、集合{1,2,3,3}和{1,2,2,3}是同一集合。

5、图 G 中，与顶点 v 关联的边数称为点 v 的度数，记作 deg（v）。

6、在实数集上，普通加法和普通乘法不是可结合运算。

7、对于任何一命题公式，都存在与其等价的析取范式和合取范式。

8、设（A,*）是代数系统，a∈A，如果 a*a＝a，则称 a 为（A，*）的等幂元。

9、设 f：

A→B， g：

B→C。

若 f，g 都是双射，则 gf 不是双射。

10、无向图的邻接矩阵是对称阵。

11、一个集合不可以是另一个集合的元素。

12、映射也可以称为函数，是一种特殊的二元关系。

13、群中每个元素的逆元都不是惟一的。

14、<{0,1,2,3,4},MAX,MIN>是格。

15、树一定是连通图。

16、单位元不是可逆的。

17、一个命题可赋予一个值，称为真值。

18、复合命题是由连结词、标点符号和原子命题复合构成的命题。

19、任何两个重言式的合取或析取不是一个重言式。

20、设 f：

A→B， g：

B→C。

若 f，g 都是满射，则 g◦f 不是满射。

21、集合{1,2,3,3}和{1,2,3}是同一集合。

22、零元是不可逆的。

23、一般的，把与 n 个个体相关联的谓词叫做一元谓词。

24、“我正在说谎。

”不是命题。

25、用 A 表示“是个大学生”，c 表示“张三”，则 A（c）：

张三是个大学生。

26、设 F＝{<3,3>,<6,2>}，则 F-1 ＝{<6,3>,<2,6>}。

27、欧拉图是有欧拉回路的图。

28、设 f：

A→B， g：

B→C。

若 f，g 都是单射，则 g◦f 也是单射。

三、计算题（每题 10 分，共 40 分）

1、设 A={c,d}, B={0,1,2}，则计算 A×B，B×A。

2、A = {a,b,c}，B = {1,2}，计算 A×B。

3、A = {a,b,c}，计算 A×A。

4、符号化命题“如果 2 大于 3，则 2 大于 4。

”。

5、符号化命题“并不是所有的兔子都比所有的乌龟跑得快”。

6、符号化命题“2 是素数且是偶数”。

7、设 A={a,b,c,d}，R 是 A 的二元关系，定义为：

R={,,,,

,,, }，写出 A 上二元关系 R 的关系矩阵。

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 的关系矩阵。

9、设有向图 G 如下所示，求各个结点的出度、入度和度数。

10、设有向图 G 如下所示，求各个结点的出度、入度和度数。

11、设无向图 G 如下所示，求它的邻接矩阵。

12、求命题公式┐（p∧┐q）的真值表。

13、设<2x+y, 5>=<10, x－3y>，求 x，y。

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。

15、例：

设 A={1, 2, 3, 4, 5}，B={3, 4, 5}, C={1, 2, 3}，A 到 B 的关系 R={|x+y=6}，B

到 C 的关系 S={|y－z=2}，求 R◦S。

S

16、集合 A={a, b, c}，B={1, 2, 3, 4, 5}，R 是 A 上的关系， 是 A 到 B 的关系。

R={, 

c>, , , }，S={, , , , }，求 R◦S，S–1◦R–1

17、A＝{1, 2, 3, 4, 5, 6}，D 是整除关系，画出哈斯图并求出最小元、最大元、极小元和极

大元。

18、设集合 A={a,b,c}，A 上的关系 R={, , }，求 R 的自反、对称、传递闭包。

19、求下图中顶点 v0 与 v5 之间的最短路径。

v1

1

v02

7

5

v3

3

2

v5

4

v2

1

v4

6

20、分别用三种不同的遍历方式写出对下图中二叉树点的访问次序。

四、证明题（每题 10 分，共 20 分）

1、若 R 和 S 都是非空集 A 上的等价关系，证明 R ⋂ S 是 A 上的等价关系。

2、证明苏格拉底论证：

凡人要死。

苏格拉底是人，苏格拉底要死。

3、P→Q，┐Q ∨ R，┐R，┐S ∨ P⇒┐S

4、在群中，除单位元 e 外，不可能有别的幂等元。

5、设 R 和 S 是二元关系，证明：

（R ⋂ S）-1=R-1 ⋂ S-1

6、证明：

（（Q∧S）→R）∧（S→（P∨R）） = （S∧（P→Q））→R.

7、设 I 是整数集合，k 是正整数，I 上的关系 R＝{|x, y ∈ I，且 x－y 可被 k 整除}，

证明 R 是等价关系。

8、证明（（p→q）→r）⇔ （（┐q∧p）∨r）

9、证明（P∨Q） ∧（P→R） ∧（Q→S）⇒S∨R

10、证明 P→ ┐Q，Q∨┐R，R∧┐S⇒ ┐P

11、证 （∀x）（P（x）∨Q（x）） ⇒┐（∀x）P（x） →（∃x）Q（x）

12、证明定理：

设是群，对于任意 a, b∈G，则方程 a x=b 与 y◦a=b ，在群内有唯一

解。

《离散数学》复习题参考答案

一、填空题（每空 1 分，共 20 分）

1、集合 A 上的偏序关系的三个性质是自反性、反对称性和传递性。

2、一个集合的幂集是指该集合所有子集的集合。

3、集合 A={b,c}，B={a,b,c,d,e}，则 A⋃B={a,b,c,d,e}。

4、集合 A={1,2,3,4}，B={1,3,5,7,9}，则 A⋂B={1,3}。

5、若 A 是 2 元集合, 则 2A 有4个元素。

6、集合 A={1,2,3｝，A 上的二元运算定义为：

a* b = a 和 b 两者的最大值，则 2*3=3。

7、设 A={a, b,c,d}, 则∣A∣= 4 。

8、对实数的普通加法和乘法， 0 是加法的幂等元， 1 是乘法的幂等元。

9、设 a,b,c 是阿贝尔群的元素，则-（a+b+c）=（-a）+（ -b）+（ -c）。

10、一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路。

11、不能再分解的命题称为原子命题，至少包含一个联结词的命题称为复合命题。

12、命题是能够表达判断（分辩其真假）的陈述语句。

13、如果 p 表示王强是一名大学生，则┐p 表示王强不是一名大学生。

14、与一个个体相关联的谓词叫做一元谓词。

15、量词分两种：

全称量词和存在量词。

16、设 A、B 为集合，如果集合 A 的元素都是集合 B 的元素，则称 A 是 B 的子集。

17、集合上的三种特殊元是单位元、零元及可逆元。

18、设 A={a, b}，则 ρ（A） 的四个元素分别是：

空集，{a}，{b}，{a, b}。

19、代数系统是指由集合及其上的一元或二元运算符组成的系统。

20、设是代数系统，其中是* ,* 二元运算符，如果* ,* 都满足交换律、结合律，并

121212

且* 和* 满足吸收律，则称是格。

1212

21、集合 A={a,b,c,d}，B={b }，则 A \ B={ a, c,d }。

22、设 A={1, 2}, 则∣A∣= 2 。

23、在有向图中，结点 v 的出度 deg+（v）表示以 v 为起点的边的条数，入度 deg-（v）表示以 v

为终点的边的条数。

24、一个图的欧拉回路是一条通过图中所有边一次且恰好一次的回路。

25、不含回路的连通图是树。

26、不与任何结点相邻接的结点称为孤立结点。

27、推理理论中的四个推理规则是全称指定规则 （US 规则）、全称推广规则 （UG 规则）、存

在指定规则 （ES 规则） 、存在推广规则 （EG 规则）。

二、判断题（每题 2 分，共 20 分）

1、√。

2、√。

3、×。

4、√。

5、√。

6、×。

7、√。

8、√。

9、×。

10、√。

11、×。

12、√。

13、×。

14、√。

15、√。

16、×。

17、√。

18、√。

19、×。

20、×。

21、√。

22、√。

23、×。

24、√。

25、√。

26、×。

27、√。

28、√。

1、空集是唯一的。

2、对任意的集合 A，A 包含 A。

3、恒等关系不是对称的，也不是反对称的。

4、集合{1,2,3,3}和{1,2,2,3}是同一集合。

5、图 G 中，与顶点 v 关联的边数称为点 v 的度数，记作 deg（v）。

6、在实数集上，普通加法和普通乘法不是可结合运算。

7、对于任何一命题公式，都存在与其等价的析取范式和合取范式。

8、设（A,*）是代数系统，a∈A，如果 a*a＝a，则称 a 为（A，*）的等幂元。

9、设 f：

A→B， g：

B→C。

若 f，g 都是双射，则 gf 不是双射。

10、无向图的邻接矩阵是对称阵。

11、一个集合不可以是另一个集合的元素。

12、映射也可以称为函数，是一种特殊的二元关系。

13、群中每个元素的逆元都不是惟一的。

14、<{0,1,2,3,4},MAX,MIN>是格。

15、树一定是连通图。

16、单位元不是可逆的。

17、一个命题可赋予一个值，称为真值。

18、复合命题是由连结词、标点符号和原子命题复合构成的命题。

19、任何两个重言式的合取或析取不是一个重言式。

20、设 f：

A→B， g：

B→C。

若 f，g 都是满射，则 g f 不是满射。

21、集合{1,2,3,3}和{1,2,3}是同一集合。

22、零元是不可逆的。

23、一般的，把与 n 个个体相关联的谓词叫做一元谓词。

24、“我正在说谎。

”不是命题。

25、用 A 表示“是个大学生”，c 表示“张三”，则 A（c）：

张三是个大学生。

26、设 F＝{<3,3>,<6,2>}，则 F-1 ＝{<6,3>,<2,6>}。

27、欧拉图是有欧拉回路的图。

28、设 f：

A→B， g：

B→C。

若 f，g 都是单射，则 g◦f 也是单射。

三、计算题（每题 10 分，共 40 分）

1、设 A={c,d}, B={0,1,2}，则 A×B={,,,,,}，B×A=

{<0,c>,<0,d>,<1,c>,<1,d>,<2,c>,<2,d>}。

2、A = {a,b,c}，B = {1,2}，A×B = {a,b,c} ×{1,2} = {,,,,,}。

3、A = {a,b,c}，A×A = {a,b,c} ×{a,b,c} =

{,,,,,,,,}。

4、符号化命题“如果 2 大于 3，则 2 大于 4。

”。

设 L（x,y）：

x 大于 y， a：

2， b：

3， c：

4，则命题符号化为 L（a,b）→L（a,c）。

5、符号化命题“并不是所有的兔子都比所有的乌龟跑得快”。

设 F（x）：

x 是兔子。

G（x）：

x 是乌龟。

H（x,y）：

x 比 y 跑得快。

该命题符号化为：

¬∀x∀y（F（x）

∧G（y）→H（x,y））。

6、符号化命题“2 是素数且是偶数”。

设 F（x）：

x 是素数。

 G（x）：

x 是偶数。

 a：

 2，则命题符号化为 F（a）∧G（a）。

7、设 A={a,b,c,d}，R 是 A 的二元关系，定义为：

R={,,,,

,,, }，写出 A 上二元关系 R 的关系矩阵。

解：

R 的关系矩阵为：

⎛1

ç1

ç1

⎝

ç1

1

0

1

1

0

0

0

1

0 ⎫

0 ⎪

0 ⎪

0 ⎪⎭

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

1

0

1

1

0

0

0

1

0 ⎫

0 ⎪

0 ⎪

0 ⎪⎭

9、设有向图 G 如下所示，求各个结点的出度、入度和度数。

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；

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；

deg（v5）＝1，deg+（v5）＝0，deg-（v5）＝1；

11、设无向图 G 如下所示，求它的邻接矩阵。

⎛ 0

ç

A（G） = ç

ç 0

ç

1 0 1 ⎫

⎪

1 0 1 ⎪

⎪

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

⎩ x - 3 y = 5

13、设<2x+y, 5>=<10, x－3y>，求 x，y。

解：

由定理列出如下方程组：

⎧2x + y = 10

⎨

求解得 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={|x+y=6}，B

到 C 的关系 S={|y－z=2}，求 R◦S。

解：

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>}

S

16、集合 A={a, b, c}，B={1, 2, 3, 4, 5}，R 是 A 上的关系， 是 A 到 B 的关系。

R={, 

c>, , , }，S={, , , , }，求 R◦S，S–1◦R–1

R◦S={, , , , , , }

（R◦S）-1={<1, a>, <4, a>, <5, a>, <2, b>, <2, c>, <4, c>, <5, c>}

1

R–={, , , , }，

S–1={<1, a>, <4, a>, <2, b>, <4, c>, <5, c>}

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 是整除关系，画出哈斯图并求出最小元、最大元、极小元和极

大元。

解：

4     6

5

2

3

1

1 是 A 的最小元，没有最大元，1 是极小元，4、5、6 都是 A 的极大元。

18、设集合 A={a,b,c}，A 上的关系 R={, , }，求 R 的自反、对称、传递闭包。

r（R）={,,,,}

s（R）={,,,,}

t（R）={,,,}

19、求下图中顶点 v0 与 v5 之间的最短路径。

v1

1

v02

7

5

v3

3

2

v5

4

v2

1

v4

6

解：

如下图所示 v0 与 v5 之间的最短路径为：

v0, v1, v2, v4 , v3, v5

最短路径值为 1+2+1+3+2=9

20、分别用三种不同的遍历方式写出对下图中二叉树点的访问次序。

先根遍历：

ABDEHCFIJGK 中根遍历：

DBHEAIFJCGK后根遍历：

DHEBIJFKGCA

四、证明题（每题 10 分，共 20 分）

1、若 R 和 S 都是非空集 A 上的等价关系，证明 RS 是 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，所以 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

证明：

.

所以.

6、证明：

（（Q∧S）→R）∧（S→（P∨R）） = （S∧（P→Q））→R.

证明：

左边：

（（Q∧S）→R）∧（S→（P∨R））

=（┐（Q∧S）∨R）∧（┐S∨（P∨R））

=（┐Q∨┐S∨R）∧（┐S∨P∨R）

=（┐Q∨┐S∨R）∧（┐S∨P∨R）

右边：

（S∧（P→Q））→R

= ┐（S∧（┐P∨Q））∨R

= （┐S∨（P∧┐Q））∨R

= （┐Q∨┐S∨R）∧（┐S∨P∨R）

所以 （（Q∧S） → R）∧（S→ （P∨R）） = （S∧（P→Q））→R.

7、设 I 是整数集合，k 是正整数，I 上的关系 R＝{|x, y ∈ I，且 x－y 可被 k 整除}，

证明 R 是等价关系。

证