离散数学期末试卷

离散数学期末练习题-(带答案)

离散数学复习注意事项：

1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。

2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例

题及书后习题认真做一做。检验一下主要内容的掌握情况。

3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习

情况，要认真理解,注意做题思路与方法。

离散数学综合练习题

一、选择题

1．下列句子中，（）是命题。

A．2是常数。B．这朵花多好看呀！

C．请把门关上！D．下午有会吗？

2．令p:今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了”

可符号化为（）。





3．令

:p

今天下雪了，

:q

路滑，则命题“虽然今天下雪了，但是路不滑”可符号

化为（）。

A.

pq

B.

pq

C.

pq

D.

pq

4．设

()Px

:x是鸟，

()Qx

:x会飞，命题“有的鸟不会飞”可符号化为（）。

A.

()(()())xPxQx

B.

()(()xPx

∧

())Qx

C.

()(()())xPxQx

D.

()(()xPx

∧

())Qx

5.设

()Px

:

x

是整数，

()fx

:

x

的绝对值，

(,)Lxy

：

x

大于等于

y

；命题“所有整数

的绝对值大于等于0”可符号化为（）。

A.

(()((),0))xPxLfx

B.

(()((),0))xPxLfx

C.

()((),0)xPxLfx

D.

()((),0)xPxLfx

6.设

()Fx

:

x

是人，

()Gx

:

x

犯错误，命题“没有不犯错误的人”符号化为（）。

A．

(()())xFxGx

B．

(()())xFxGx

C．(()())xFxGxD．(()())xFxGx

7.下列命题公式不是永真式的是（）。

A.

()pqp

B.

()pqp

C.()pqpD.()pqp

8．设

()Rx

:x为有理数；

()Qx

:x为实数。命题“任何有理数都是实数”的符号化

为（）

A．

()(()())xRxQx

B．

()(()())xRxQx

C．

()(()())xRxQx

D．

(()())xRxQx

9.设个体域

{,}Dab

，与公式

()xAx

等价的命题公式是()

A．

()()AaAb

B．

()()AaAb

C．

()()AaAb

D．

()()AbAa

10.下列等价式不正确的是（）。

A．

(()())()()xPxQxxPxxQx

B．

(()())()()xPxQxxPxxQx

C．

(()())()()xPxQxxPxxQx

D．

(())()xPxQxPxQ

11.设个体域

{,}Dab

，与公式

()xAx

等价的命题公式是()

A．

()()AaAb

B．

()()AaAb

C．

()()AaAb

D．

()()AbAa

12.设X={,{},{,}}aa，则下列陈述正确的是（）。

B.

{,}aX

C.

{{,}}aX

D.

{}X

13.有向图D是连通图，当且仅当（）。

A.图D中至少有一条通路

B.图D中有通过每个顶点至少一次的通路

C.图D的连通分支数为一

D.图D中有通过每个顶点至少一次的回路

14.设A={a,b,c}，则下列是集合A的划分的是()

A.

{{,},{}}bcc

B.

{{},{,}}abc

C.

{{,},{,}}abac

D.

{{,},}abc

15.下列谓词公式中是前束范式的是（）。

A．

()()()xFxxGx

B．

()()xFxyGy

C．

(()(,))xPxyQxy

D．

(()(,))xyPxQxy

16.设

12

{|()0},{|()0}MxfxNxfx，则方程

12

()()0fxfx的解为（）。

A．M∩NB．M∪N

C．MNC．M-N

17.设,GA是群，则下列陈述不正确的是（）。

A.11()aaa

C.111()ababD.11()nnabaaba

18.在整数集合

Z

上，下列定义的运算满足结合律的是（）。

A.1abbB.1aba

C.1ababD.1abab

19.设简单图G所有结点的度数之和为50，则G的边数为（）。

()

A.50B.25

C.10D.5

20.设简单无向图G是一个有5个顶点的4－正则图，则G有（）条边。

A.4B.5C.10D.20

21.设集合

{1,2,3,4}A

,

A

上的等价关系

{1,1,3,2,2,3,R

4,4}

A

I，则对应于

R

的划分是（）。

A.

{{1},{2,3},{4}}

B.

{{1,3},{2,4}}

C.

{{1,3},{2},{4}}

D.

{{1},{2},{3},{4}}

22.设集合

{1,2,3,4}A

,

A

上的等价关系

{1,3,3,1,2,4,R

4,2}

A

I，则对应于

R

的划分是（）。

A.

{{1},{2,3},{4}}

B.

{{1,3},{2,4}}

C.

{{1,3},{2},{4}}

D.

{{1},{2},{3},{4}}

23.设

,GA

是群，则下列陈述不正确的是（）。

A.11()aaB.111()abab

aD.11()nnabaaba

24.

{1,2,,10}A

，下列定义的运算关于集合

A

是不封闭的是（）。

A.

max{,}xyxy

，即

,xy

的较大数

B.

min{,}xyxy

，即

,xy

的较小数

C.

gcd{,}xyxy

，即

,xy

的最大公约数

D.

{,}xylcmxy

，即

,xy

的最小公倍数

25.设

{1,2,3},{,,,},{1,,2,,3,}XYabcdfabc

，则

f

是

()。

A．从X到Y的双射

B．从X到Y的满射，但不是单射

C．从X到Y的单射，但不是满射

D．从X到Y的二元关系，但不是从X到Y的映射

26.设简单无向图G是一个有6个顶点的5－正则图，则G有()条边。

A.5B.6C.15D.30

27.图G如下图所示，以下说法正确的是()。

A．a是割点B．{b,c}是点割集

C．{b,d}是点割集D．{c}是割点

d

b

c

a

28.格L是分配格的充要条件是L不含与下面哪一个选项同构的子格（）。

A．链B．钻石格

C．五角格D.五角格与钻石格

29.下列图是欧拉图的是（D）。

30.给定一个有n个结点的无向树，下列陈述不正确的是（）。

A．所有结点的度数≥2

B．无回路但若增加一条新边就会变成回路

C．连通且1ev，其中e是边数，v是结点数

D．无回路的连通图

31.设

A

有5个元素，则其幂集

()PA

的元素总个数为（）。

A.32B.25

C.50D.5

32．若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是

（）。

A.(1,2,2,3,4,5)B.(1,2,3,4,5,5)

C.(1,1,1,2,3)D.(2,3,3,4,5,6)

33.设

{,{},{,{}}}Aaaaa

则其幂集

()PA

的元素总个数为（）。

A.3B.4

C.8D.16

34.在实数集合R上，下列定义的运算中不可结合的是（）。

A.2ababab







35.无向图G是欧拉图，当且仅当（）。

A.G的所有结点的度数全为偶数

B.G中所有结点的度数全为奇数

C.G连通且所有结点度数全为奇数

D.G连通且所有结点度数全为偶数

36.下列不一定

．．．

是树的是（）

A.无回路的连通图D

B.有n个结点，n-1条边的连通图

C.每对结点之间都有通路的图

D.连通但删去一条边则不连通的图

37.设简单图G所有结点的度数之和为48，则G的边数为

()

A.48B.24

C.16D.12

38．下面既是哈密顿图又是欧拉图的图形是（B）。

39.下列必为欧拉图的是（）

A.有回路的连通图B.不可以一笔画的图

C.有1个奇数度结点的连通图D.无奇数度结点的连通图

40.二部图

3,3

K是（）。

A.欧拉图B.哈密顿图

C.平面图D.完全图

41．下列所示的哈斯图所对应的偏序集中能构成格的是（C）。

A.B.

C.D.

42.设简单无向图G是一个有6个顶点的3－正则图，则G有()条边。

A.3B.6

C.9D.18

43．下列式子为矛盾式的是（）。

A．

()ppq

B．

pp

C．

pp

D．

()pqpq

44.设集合

{,,}Aabc

，A上的关系

{,,,,,}Raaacca

，则R是（）

A．自反的B．对称的

C．传递的D．反对称的

45．设

12

,RR是集合

{,,,}Aabcd

上的两个关系，其中

1

{,,,,Raabb

,,,}bcdd

，

2

{,,,,,,,,,}Raabbcbbcdd，则

2

R是

1

R

的（）闭包。

A．自反B．对称

C．传递D．自反、对称且传递闭包

46.下列公式是前束范式的是（）。

A．

()()((,)())xyFzxGy

B．

(()()()())()xFxyGyHz

C．

()(,)()()xFxyyGy

D．

()((,)()(,))xFxyyGxy

47.设R为实数集，函数

:fRR

，2()25fxxx，则

f

是（）。

A．单射而非满射B．满射而非单射

C．双射D．既不是单射，也不是满射

48．下列各图中既是欧拉图，又是汉密尔顿图的是（C）。

A．B．C．D．

49．下列四个格，是分配格的是（C）。

50．设集合A={a,b,c}上的关系如下，具有传递性的是（）。

A．R={,,,}B．R={,}

C．R={,,,}D．R={}

参考答案：（若有问题，可以到1#402或打电话问）

一、选择题

AAAABDACAACCDBDBCDBCABBDCCBDDA

ACCDDBBBDBCCCBBADCCD

二、填空题

1．命题公式()pq的成真指派为10，成假指派为_00，01，11__。

2.命题公式

()pqp

的成真指派为001011，成假指派为_01__。

3．命题公式

()ppq

的成真指派为000111,成假指派为_10__。

4．公式

()()(()(,))()(,)xyPyQxzyRxy

约束变元为x,y，自由变元

为x,z。

5．公式

(()())(,)xPxyRyQxz

约束变元为__x,y_，自由变元为_x,z_。

6．设

{,,{,}}Aabab

，

{,}Bab

，则

BA



，AB{{a,b}}。

7．设

{1,2,3}A

，A上的关系

{1,2,2,1}R

，则对称闭包

()sR

{<1,2>,<2,1>}，传递闭包

()tR

{<1,2>,<2,1>,<1,1>,<2,2>}。

8.设*是集合S上的二元运算，若运算*满足__结合律_，并且存在__单位元_，

则称

,*S

为独异点。

9．设

{,,{,}}Aabab

，

{,,}Babc

，则AA



，AB{{a,b},c}。

10.一棵无向树的顶点数

n

与边数

m

的关系是m=n-1。6阶无向连通

图至多有6棵不同构的生成树。

11．设()1fxx，2()gxx，则复合函数()()fgx=2(1)x,()()gfx=21x。

12.,

n

Z是一个群，其中{0,1,2,,1}

n

Zn，

()modxyxyn

，则当

n=6

时，在

6

,Z中，2的阶为___3___,3的阶为_2。

13．设是格，其中A={1,3,4，6，8，12，24}，≤为整除关系，则1的补元

是___24__，3的补元是_8_。

14．设A=｛<1，3>，<3，5>，<4，4>｝，B=｛<1,3>,<4,5>,<5,5>｝,那么

dom()AB={1,3,4,5}ran()AB={3,5}。

15.设A={l,2,3,4},A上的二元关系R={<1,2>,<2,3>,<3,2>}，S={,<2,3>，<4，

3>}，

则

RS

{<1,3>,<3,3>},1()RS{<3,1>,<3,3>}。

16．设={<1,2>,<3,4>,<3,5>}R和={<2,1>,<3,3>,<5,5>}S是集合={1,2,3,4,5}A上的

两个关系，则RS={<1,1>,<3,5>}，11SR={<1,1>,<5,3>}。

17．设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点

中，单位元是2，零元是6。

18．一棵无向树的顶点数n与边数m关系是m=n-1。设G是具有8个顶点的

树，则G中增加___21_条边才能把G变成完全图。

19．设复合函数gf是从A到C的函数，如果gf是满射，那么__g___必是满

射，如果gf是单射，那么_f_必是单射。

20．设是格，其中A={1,3,5,9,45}，≤为整除关系，则1的补元是___45___，

3的补元是_5_。

21．给出A={l，2}上的一个等价关系_{<1,1>,<2,2>}_，并给出其对应的划分

_{{1},{2}}______。

22．设

{,,,}Aabcd

，

A

上的二元关系

{,,,,,}Rabadbb

，则

R

的自

反闭包

()rR

A

RI，传递闭包

()tR

R

23．命题公式

()pqp

的成真赋值为011011，成假赋值为00。

24．公式

()()pqpq

的成真赋值是00,11。成假赋值0110

25．公式

()()pqpq

的成真赋值是0111。成假赋值0010

26．公式

()()pqpq

的成假赋值是0110。成假赋值0011

27．设个体域是实数集，命题

)3(xxx

的真值为1；命题2(10)xx

的真值为0。

28.设f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数

(fg)()x

2x+4,

(gf)(x)

2x+7。

29.给定集合A={1,2,3,4,5}，在集合A上定义两种关系：R={<1,2>,<3,4>,<2,2>},

S={<4,2>,<2,5>,<3,1>,<1,3>，则RS{<1,5>,<3,2>,<2,5>}。

30．设A={0，1，2，3，6}，{,|,(mod3)}RxyxyAxyxy则

domR={0，3，6}_，ranR=_{0，3，6}，

31．设

6

,Z为模6加群，其中

6

{0,1,2,3,4,5}Z，则2-3=0，4-2=4。

32．一个结点为n的无向完全图，其边的数目为n(n-1)/2，顶点的度为n-1。

33.已知

n

阶无向简单图G有

m

条边，则G的补图G中有m-n(n-1)/2条边。

参考答案：

1．_10_，00，01，11

2.001011，01_

3._000111,10

4._x,y，x,z__

5._x,y，x,z__

6.



,,

{{a,b}}

7.

{1,2,2,1}

，

{1,2,2,1,1,1,2,2}

8.结合律，单位元

9．



,,

{{a,b}，c}

10.n-1,6

11.2(1)x

,

,21x

12.

3,2

13._24__,_8__

14.{1,3,4,5}，_{3}

15.{<1,3>,<3,3>},{<3,1>,<3,3>}

16.

{1,1,3,5}

，

{1,1,5,3}

17.2,6

18.m=n-1,_21

19._g,_f_

20.45,_5_

21.

{1,1,2,2}

,

{{1},{2}}

22.

A

RI,

R

23.011011，00

24.00，11,01，10

25.01，11,00，10

26.0110,0011

27.1,0

28.24x,27x

29.{<1,5>,<3,2>,<2,5>}

30.{0，3，6},{0，3，6}

31.0,4

32.n(n-1)/2,n-1

33.m-n(n-1)/2

三、计算题（仅给出部分题目的解题思路，未给出答案自己完成）

1.已知命题公式

()()pqpr

（1）构造真值表

（2）求出公式的主析取范式

解题思路：（1）真值表

pqr

p()pqpr()()pqpr

0001001

0011001

0101100

0111100

1000100

1010111

1100100

1110111

（2）

()()pqpr

0157

()()()()pqrpqrpqrpqr

mmmm





2.已知命题公式

()()pqpr

（1）构造真值表；

（2）用等值演算法求公式的主析取范式。

解：（1）真值表

pq

r

pq

pr()pr()()pqpr

00

0

0011

00

1

0101

01

0

1011

01

1

1100

10

0

1100

10

1

1100

11

0

1100

11

1

1100

（2）主析取范式

012

()()

()()

()()

(()())(()r)

(()()(r)(r)

pqpr

pqpr

pqpr

pqrrpqq

pqrpqrpqpq

mmm













3．求公式

(())()prpqp

的主合取范式及主析取范式。

4．构造命题公式(p∧)r∨()pq的真值表。

5.一棵（无向）树有2结点的度为2，1个结点的度为3，3个结点的度为4,其

余都是叶结点，问该树有几个叶结点？

解：在一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结

点数减1。

根据这两点，可知树中各结点的度数总和=2*（树中点数-1），设树叶有x

个，

于是，2*2+3+3*4+x=2*（2+1+3+x-1）

得x=9。

6.一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问

T有几个顶点？

提示：类似上题求解。

7.设2:,()2fRRfxx，

:,()4gRRgxx

,3:,()1hRRhxx，

其中

R

表示实数集。

（1）求函数

fg

，

gf

；

（2）

,,fgh

哪些函数有反函数？如果有，求出这些反函数。

解：（1）22()(())(4)(4)2814gfxfgxfxxxx

22()(())(2)2fgxgfxgxx

（2）

g

和h有反函数，11:,()4gRRgxx；

11

3:,()1hRRhxx

8.设A＝{a，b，c}，R是A上的二元关系，且R＝{，}，求r(R)、

s(R)和t(R)。

解：r(R)=R∪IA={,,,,}

s(R)=R∪R-1={,}

t(R)=R∪R2∪R3={，，，}

9.设{1,2,3,4,6,9,24,54}A，为整除关系。

（1）画出偏序集

>的哈斯图；

（2）求A中的极大元；

（3）求子集B=｛3,6,9｝的上确界与下确界。

解：（1）哈斯图

（2）A中的极大元为24，54；极小元为1；最大元：无；最小元：1

（3）求子集B=｛3,6,9｝的上确界为54，下确界为3。

10.设有向图D如图所示，用邻接矩阵完成以下计算。

（1）

1

v到

4

v长度小于或等于4的通路数；

（2）

1

v到自身长度小于或等于4的回路数；

（3）求出D的可达矩阵，并说明D的连通性。

有向图的邻接矩阵为

1

6

2

3

4

2

9

5

1210

0010

0001

0010

A















，2

1231

0001

0010

0001

A















3

1243

0010

0001

0010

A















，4

1264

0001

0010

0001

A















（1）v

1

到v

4

长度小于或等于4的通路数为

4

()

14

1

01348i

i

a





（2）v

1

到自身长度小于或等于4的回路数为

4

()

11

1

11114i

i

a





（3）

1111

0111

()

0011

0011

PD















由可达矩阵可知D是单向连通的。

11．设

{0,1,2}A

，给出幂集合

()PA

对称差运算的运算表。

12．设

6

{0,1,2,3,4,5}Z，给出模6加运算的运算的运算表。

参看教材P167例9.4与9.5

14.设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，

4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解：r(R)=R∪IA

s(R)=R∪R-1

t(R)={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>,（2,2>,<5,5>}

15.下图为一连通赋权图，计算该图的最小生成树和权值。

四、简答题

1.设集合

}654321{，，，，，A

上的关系

{(1,1,1,3,1,6,2,2,R

2,5,3,1,3,3,3,6,4,4,5,2,5,5,6,1,6,3),6,6}

（1）画出

R

的关系图，并写出

R

的关系矩阵；

（2）

R

是否为等价关系？若是，写出

R

的所有等价类。

解：（1）R的关系图为

（2）R的关系矩阵

10100

01001

10100

00010

01001

















由关系图可以看出

R

是等价关系。等价类为：

[1][3][6]{1,3,6},[2]{2,5},[4]{4}

或写为：A/R={{1,3,6},{2,5},{4}}

2.设

{1,3,(1,4,2,2,3,1,3,3),4,1}R

是A=

{1,2,3,4}

上的二元关

系。

（1）画出R的关系图；

（2）写出R的关系矩阵；

（3）讨论R的性质。

解：（1）R的关系图

2

1

1

23

6

5

4

（2）R的关系矩阵

0011

0100

1000

1000













（3）R非自反、非反自传、对称、非反对称、非传递的

（4）R不是函数，不满足函数单值性的要求。

3．设A={1,2,3,4,5,6,7,8,9,10}，R是A上的二元关系，

R={|x,y∈A∧x+y=10}说明R具有哪些性质。

解：R={<1,9>,<2,8>,<3,7>,<4,6>,<5,5>,<9,1>,<8,2>,<7,3>,<6,4>}

易知R既不是自反也不是反自反的

R是对称的

R不是反对称的

R不是传递的。

4．判断下图是否为二部图？若是，找出它的互补结点子集。它是否为哈密顿图？

若是，找出一条哈密顿回路。

5.判断下图G是否是二部图？若是，找出它的互补结点子集。它是否为哈密顿

图？若是，找出一条哈密顿回路。

6.设{1,3,5,9,45}A，为A上的整除关系。

（1）,A是否为偏序集，若是，画出其哈斯图；

（2）,A是否为格？说明理由；

解：（1）,A是偏序集。哈斯图为：

4

3

h

f

i

g

a

b

e

c

d

j

1

v

2

v

6

v

7

v

5

v

8

v

3

v

1

3

5

9

4

（2）,A是格。因为偏序集中的任意两个元素均有上、下确界。

四、证明题

1．用一阶逻辑的推理理论证明：

前提：(()())xFxGx，(()())xFxHx，()xHx

结论：()xGx

证明：（1）

(()())xFxHx

前提引入

（2）

()()FxHx

（1）

（3）

()xHx

前提引入

（4）

()Hx

（3）

（5）

()Fx

（2）（4）析取三段论………（4分）

（6）

(()())xFxGx

前提引入

（7）

()()FxGx

（6）

（8）

()Gx

（5）（7）假言推理

（9）

()Gx

（8）………（3分）

2．设A是非空集合,F是所有从A到A的双射函数的集合,是函数的复合运算。

证明：,F是群。

证明：由于集合

A

是非空的，

A

IF

，

,

因此

F

非空。

(1)

,fgF

,因为

f

和

g

都是

A

到

A

的双射函数，故

fg

也是

A

到

A

的双射

函数，从而集合

F

关于运算是封闭的。

(2)

,,fghF

,由函数复合运算的结合律有

()()fghfgh

，故运算是可

结合的。

(3)

A

上的恒等函数

A

I

也是

A

到

A

的双射函数即

A

IF

,且

fF

有

AA

IffI

,故

A

I

是

,F

中的幺元。

(4)

fF

,因为

f

是双射函数，故其逆函数是存在的，也是

A

到

A

的双射函数，

且有11

A

ffffI

,因此1f是

f

的逆元

由此上知

,F

是群

3．设代数系统

6

,VZ，

6

{0,1,2,3,4,5}Z，为模6加法。证明：

6

Z关于

运算构成群。

证明：集合

6

Z

显然非空。

(1)

6

,abZ

,

6

abZ,

从而集合

6

Z

关于运算是封闭的。

(2)

6

,,abcZ

,有

()()abcabc

，故运算



是可结合的。

(3)

6

aZ

,0aa,故0是

6

,Z中的幺元。

(4)

6

aZ

,因为

(6)0aa

,因此

6a

是a的逆元

由此上知

6

,Z是群

4．设A是集合，P(A)是A的幂集合，



是对称差运算，证明



>构成群。

提示：参考2、3证明题完成。

5．设

{,|,Axyxy

为正整数

}

，在

A

上定义二元关系

R

如下：

,,xyRuv

当且仅当xyuv。

证明：

R

是一个等价关系。

证明：

任取

,xy

,,,xyAxyxyxyRxy

所以R自反的。

任取

,,,xyuv

,,,,xyRuvxyuvuvxyuvRxy

所以R是对称的。

任取,,,,,xyuvst

,,,,xyRuvuvRstxyuvuvst

,,xystxyRst

所以R是传递的。

因此，R是等价关系。

6.设R是A上的关系，如果R满足以下两条件：

（1）对于任意的a



R，都有aRa，

（2）若aRb,aRc,则有bRc，

证明：R是等价关系

证明：任取,,abcR

（1）由已知条件（1）得

,aaR,

,

所以R是自反的。

（2）由已知条件（1）、（2）得

,,,abRaaRbaR

所以R是对称的。

（3）由已知条件（1）、（2）得

,,,,abRbcRbaRcbR

,,,bcRbaRcaR

所以R是传递的。

五、应用题（仅给出第7题的参考答案,未给出参考答案的自己完成）

1.构造下列推理的证明。

如果今天是星期一，则要进行英语或离散数学考试。如果英语老师有会，则

不考英语。今天是星期一，英语老师有会，所以进行离散数学考试。

2.构造下列推理的证明。

小王是理科学生，则他的数学成绩很好。如果小王不是文科学生，则他一

定是理科学生。小王的数学成绩不好,所以小王是文科学生。

3．如果甲是冠军，则乙或丙将得亚军；如果乙得亚军，则甲不能得冠军；如

果丁得亚军，丙不能得亚军；事实是甲已得冠军。因此丁不能得亚军。

参照作业：P5417,18

4.用一阶逻辑推理证明

每个喜欢步行的人都不喜欢骑自行车，每个人或喜欢骑自行车或者喜欢乘汽车。

有的人不喜欢乘汽车，所以，有的人不喜欢步行（个体域为人类集合）

解:令():Fxx喜欢步行,():Gxx喜欢骑自行车,():Hxx喜欢乘汽车

前提：(()())xFxGx，(()())xFxHx，()xHx

结论：()xGx

证明：（1）

(()())xFxHx

前提引入

（2）

()()FxHx

（1）



（3）

()xHx

前提引入

（4）

()Hx

（3）

（5）

()Fx

（2）（4）析取三段论

（6）

(()())xFxGx

前提引入

（7）

()()FxGx

（6）



（8）

()Gx

（5）（7）假言推理

（9）

()Gx

（8）

5．今有于

,,,,,abcdef

7个人，已知下列事实：a会讲英语；

b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲日语和汉语；e会

讲德国和意大利语；f会讲法语、日语和俄语；g会讲法语和德语。

试问这七个人应如何排座位，才能使每个人都能和他身边的人交谈？

解：用结点表示人，用边表示连接的两个人

能讲同一种语言，构造出图G如下：

在G中存在着一条哈密顿回路如下，根

据这条回路安排座位，就能够使每个人都能

和他身边的人交谈。

6．一次学术会议的理事会共有20个人参加，他们之间有的互相认识但有的互

相不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能

否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人？根据是什

么？

7.设有7个城市

1

v，

2

v，……

7

v，任意两个城市之间直接通信线路及通信线路预

算造价如带权图所示，试给出一个设计方案，使得各城市间能够通信，而且

总造价最低。写出求解过程，并计算出最低总造价。

a

b

c

d

e

f

g

英

英

英

汉

俄

法

德

意

日

英

英

汉

意

法

德

日

a

b

f

g

d

e

c

2

v

3

v

4

v

1

1

2

4

5

5

5

4

3

3

2

1

v

0

v

40

v

4

6

v

5

v

解：带权图中边表示通信路，边上的数字表示修建该通信线路所需费用，于是

求解此题便成为求权图中的最小生成树问题。

按避圈算法，对图中各边的权值按由小到大的顺序排序，

5

取

12

(,)vvT,

45

(,)vvT，

34

(,)vvT，

04

(,)vvT

02

(,)vvT

，16

(,)vvT

则求解最小生成树如下图所示：

图中最小生成树的权为:

12

(,)wvv+

45

(,)wvv+

34

(,)wvv+

04

(,)wvv+

02

(,)wvv+

16

(,)wvv=

1+1+2+2+3+5=14

5

v

4

v3

v

2

v

1

3

1

1

v

0

v

2

2

6

v

5