2023年7月19日发(作者：)

离散数学复习注意事项：

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

2、 第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。

3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。

离散数学综合练习题

一、选择题

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

A．2是常数。

B．这朵花多好看呀！

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

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

可符号化为（ ）。

A.

pqr

C.

pqr

为（ ）。

A.

pq

C.

pq

A.

(x)(P(x)Q(x))

C.

(x)(P(x)Q(x))

B.

pq

D.

pq

B.

(x)(P(x)∧Q(x))

D.

(x)(P(x)∧Q(x))

B.

pqr

D.

pqr

3．令p:今天下雪了，q:路滑，则命题“虽然今天下雪了，但是路不滑”可符号化4．设P(x):x是鸟，Q(x):x会飞，命题“有的鸟不会飞”可符号化为（ ）。

5.设P(x):x是整数，f(x):x的绝对值，L(x,y)：x大于等于y；命题“所有整数的绝对值大于等于0”可符号化为（ ）。

A.

x(P(x)L(f(x),0))

C.

xP(x)L(f(x),0)

A．x(F(x)G(x))

C．x(F(x)G(x))

A.

(pq)p

C.

p(qp)

B.

x(P(x)L(f(x),0))

D.

xP(x)L(f(x),0)

B．

x(F(x)G(x))

D．

x(F(x)G(x))

B.

p(qp)

D.

(pq)p

6.设F(x):x是人，G(x):x犯错误，命题“没有不犯错误的人”符号化为（ ）。

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

8．设R(x):x为有理数；Q(x):x为实数。命题“任何有理数都是实数”的符号化为（ ） A．(x)(R(x)Q(x)) B．(x)(R(x)Q(x))

C．(x)(R(x)Q(x)) D．x(R(x)Q(x))

9.设个体域D{a,b}，与公式xA(x)等价的命题公式是( )

A．A(a)A(b) B．A(a)A(b)

C．A(a)A(b) D．A(b)A(a)

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

A．x(P(x)Q(x))xP(x)xQ(x)

B．x(P(x)Q(x))xP(x)xQ(x)

C．x(P(x)Q(x))xP(x)xQ(x)

D．x(P(x)Q)xP(x)Q

11. 设个体域D{a,b}，与公式xA(x)等价的命题公式是( )

A．A(a)A(b) B．A(a)A(b)

C．A(a)A(b) D．A(b)A(a)

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

A.aX B.{a,}X

C.{{a,}}X D.{}X

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

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

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

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

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

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

A.{{b,c},{c}} B.

{{a},{b,c}}

C.{{a,b},{a,c}} D.

{{a,b},c}

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

A．xF(x)(x)G(x) B．xF(x)yG(y)

C．x(P(x)yQ(x,y)) D．xy(P(x)Q(x,y))

16.设M{x|f1(x)0},N{x|f2(x)0}，则方程f1(x)f2(x)0的解为（A．M∩N B．M∪ N

C．MN C．M-N

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

A.

(a1)1a B.

anamanm

C.

(ab)1a1b1 D.

(a1ba)na1bna

18.在整数集合Z上，下列定义的运算满足结合律的是（ ）。

。 ） A.

abb1

C.

abab1

B.

aba1

D.

abab1

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

( )

A. 50 B. 25

C. 10 D. 5

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

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

21.设集合A{1,2,3,4},A上的等价关系R{1,1,3,2,2,3,

4,4}UIA，则对应于R的划分是（ ）。

A.

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

C.

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

B.

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

D.

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

22.设集合A{1,2,3,4},A上的等价关系R{1,3,3,1,2,4,

4,2}UIA，则对应于R的划分是（ ）。

A.

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

C.

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

B.

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

D.

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

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

A.

(a1)1a

C.

anamanm

B.

(ab)1a1b1

D.

(a1ba)na1bna

24.A{1,2,L,10}，下列定义的运算关于集合A是不封闭的是（ ）。

A.

xymax{x,y}，即x,y的较大数

B.

xymin{x,y}，即x,y的较小数

C.

xygcd{x,y}，即x,y的最大公约数

D.

xylcm{x,y}，即x,y的最小公倍数

25. 设X{1,2,3},Y{a,b,c,d},f{1,a,2,b,3,c}，则f是

( )。

A．从X到Y的双射

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

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

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

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

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

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

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

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

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

A．链

B．钻石格

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

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

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

A．所有结点的度数≥2

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

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

D．无回路的连通图

31. 设A有5个元素，则其幂集P(A)的元素总个数为（ ）。

A. 32

C. 50

（ ）。

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

C. (1,1,1,2,3)

B.25

D. 5

32．若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是B. (1,2,3,4,5,5)

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

33. 设A{a,{a},{a,{a}}}则其幂集P(A)的元素总个数为（ ）。

A. 3

C. 8

B. 4

D. 16

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

A.

abab2ab

B.

abab

C.

ababab

D.

abab

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

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

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

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

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

36.下列不一定是树的是（ ）

．．．A. 无回路的连通图D B. 有n个结点，n-1条边的连通图

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

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

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

( )

A. 48 B. 24

C. 16 D. 12

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

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

A.有回路的连通图

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

40.二部图

K3,3是（ ）。

A.欧拉图

C.平面图

B. 哈密顿图

D. 完全图

B.不可以一笔画的图

D.无奇数度结点的连通图

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

A. B.

C.A. 3

C. 9

D.B. 6

D. 18

42.设简单无向图G是一个有6个顶点的3－正则图，则G有( )条边。 43．下列式子为矛盾式的是（ ）。

A．p(pq)

C．pp

B．pp

D．

(pq)pq

44.设集合A{a,b,c}，A上的关系R{a,a,a,c,c,a}，则R是（ ）

A．自反的 B．对称的

C．传递的 D．反对称的

45．设R1,R2是集合A{a,b,c,d}上的两个关系，其中R1{a,a,b,b,

则R2 是R1的b,c,d,d}，R2{a,a,b,b,c,b,b,c,d,d}，（ ）闭包。

A．自反

C．传递

B．对称

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

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

A．(x)(y)(F(z,x)G(y)) B．((x)F(x)(y)G(y))H(z)

C．(x)F(x,y)(y)G(y) D．(x)(F(x,y)(y)G(x,y))

47. 设R为实数集，函数f:RR，f(x)x22x5，则f是（ ）。

A．单射而非满射

C．双射

B．满射而非单射

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

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

A． B． C． D．

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

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

A． R={,,,}

C． R={,,,}

B． R={,}

D． R={} 参考答案：（若有问题，可以到1#402或打电话问）

一、选择题

AAAAB DACAA CCDBD BCDBC ABBDC CBDDA

ACCDD BBBDB CCCBB ADCCD

二、填空题

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

2. 命题公式(pq)p的成真指派为00 10 11，成假指派为_01__。

3．命题公式p(pq)的成真指派为00 01 11 , 成假指派为_ 10__。

4．公式(x)(y)(P(y)Q(x,z))(y)R(x,y)约束变元为 x,y ，自由变元为 x,z

。

5．公式x(P(x)yR(y))Q(x,z)约束变元为__x,y_，自由变元为_x,z_

。

6．设A{a,b,{a,b}}，B{a,b}，则BA，AB {{a,b}} 。

7．设A{1,2,3}，A上的关系R{1,2,2,1}，则对称闭包

s(R) {<1,2>,<2,1>} ，传递闭包t(R) {<1,2>,<2,1>,<1,1>,<2,2>}。

8.设*是集合S上的二元运算，若运算*满足__结合律_，并且存在__单位元_，则称S,*为独异点。

9． 设A{a,b,{a,b}}，B{a,b,c}，则AA，AB {{a,b},c} 。

10.一棵无向树的顶点数n与边数m的关系是 m=n-1 。6阶无向连通图至多有 6 棵不同构的生成树。

11．设f(x)x1，g(x)x2，则复合函数(fog)(x)=(x1)2,(gof)(x) =x21。

12.

Zn,是一个群，其中Zn{0,1,2,L,n1}，xy(xy)modn，则当n=6时，在Z6,中，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(AUB)={1,3,4,5} ran(AIB)= {3,5} 。

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

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

16．设R={<1,2>,<3,4>,<3,5>}和S={<2,1>,<3,3>,<5,5>}是集合A={1,2,3,4,5}上的两个关系，则RoS= {<1,1>,<3,5>} ，

S1oR1= {<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．设A{a,b,c,d}，A上的二元关系R{a,b,a,d,b,b}，则R的自反闭包r(R)RUIA，传递闭包t(R) R

23．命题公式(pq)p的成真赋值为 01 10 11 ，成假赋值为 00 。

24．公式(pq)(pq)的成真赋值是 00,11 。成假赋值 01 10

25．公式(pq)(pq)的成真赋值是 01 11 。成假赋值 00 10

26．公式(pq)(pq)的成假赋值是 01 10 。成假赋值 00 11

27．设个体域是实数集，命题x(x3x)的真值为 1 ；命题x(x210)的真值为 0 。

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

(gof)(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>，则RoS= {<1,5>,<3,2>,<2,5>} 。

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

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

31． 设Z6,为模6加群，其中Z6{0,1,2,3,4,5}，则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. 00 10 11， 01_

3. _00 01 11, 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.

(x1)2,,x21

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.

RUIA,

R

23. 01 10 11，00

24. 00，11 ,01，10

25. 01，11 ,00，10

26. 01 10 , 00 11

27. 1 , 0

28.

2x+4,2x+7

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. 已知命题公式(pq)(pr) （1）构造真值表

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

解题思路：（1）真值表

p q r

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

p

(pq)

pr

(pq)(pr)

1

1

1

1

0

0

0

0

0

0

1

1

1

1

1

1

0

0

0

0

0

1

0

1

1

1

0

0

0

1

0

1

（2）(pq)(pr)

(pqr)(pqr)(pqr)(pqr)

m0m1m5m72.已知命题公式(pq)(pr)

（1）构造真值表；

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

解：（1）真值表

p q r

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

pq

0

0

1

1

1

1

1

1

pr

0

1

0

1

1

1

1

1

(pr)

1

0

1

0

0

0

0

0

(pq)(pr)

1

1

1

0

0

0

0

0

（2）主析取范式 (pq)(pr)(pq)(pr)(pq)(pr)

((pq)(rr))(p(qq)r)((pqr)(pqr)(pqr)(pqr)m0m1m23．求公式(p(rp))(qp) 的主合取范式及主析取范式。

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

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.设f:RR,f(x)x22，g:RR,g(x)x4,h:RR,h(x)x31，

其中R表示实数集。

（1）求函数fog，gof；

（2）f,g,h哪些函数有反函数？如果有，求出这些反函数。

解：（1）gof(x)f(g(x))f(x4)(x4)22x28x14

fog(x)g(f(x))g(x22)x22

（2）g和h有反函数，g1:RR,g1(x)x4；

h1:RR,h1(x)3x1

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.设A{1,2,3,4,6,9,24,54}，为整除关系。

（1）画出偏序集的哈斯图；

（2）求A中的极大元；

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

解：（1）哈斯图

4

2

1

24

6

54

9

3

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

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

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

（1）v1到v4长度小于或等于4的通路数；

（2）v1到自身长度小于或等于4的回路数；

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

有向图的邻接矩阵为

10A00103A0021012000102，A0000101000243100104，A0001010043101

1001264001

010001（1）v1到v4长度小于或等于4的通路数为

ai1(i)1401348 （2）v1到自身长度小于或等于4的回路数为

ai14(i)1111114

10（3）P(D)00111111

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

11．设A{0,1,2}，给出幂集合P(A)对称差运算的运算表。

12．设Z6{0,1,2,3,4,5}，给出模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.设集合A{1，2，3，4，5，6}上的关系R={(1,1>,<1,3>,<1,6>,<2,2>,

<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的关系图为

6

4

5

1

3 2

10（2）R的关系矩阵

10001001001

01000010

1001由关系图可以看出R是等价关系。等价类为：

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

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

2. 设R{1,3,(1,4,2,2,3,1,3,3),4,1}是A={1,2,3,4}上的二元关系。

（1）画出R的关系图；

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

（3）讨论R的性质。

解：（1）R的关系图

1

3

4

2

00（2）R的关系矩阵

11011100

000000

（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．判断下图是否为二部图？若是，找出它的互补结点子集。它是否为哈密顿图？a若是，找出一条哈密顿回路。

bi

gc

hf

jd

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

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

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

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

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

四、证明题

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

前提：x(F(x)G(x))，x(F(x)H(x))，

xH(x)

结论：

xG(x)

证明：（1）x(F(x)H(x)) 前提引入

3

1

5

45

v8v7v3v1v5v6v29

（2）A,是格。因为偏序集中的任意两个元素均有上、下确界。 （2）F(x)H(x) （1）

（3）xH(x) 前提引入

（4）H(x) （3）

（5）F(x) （2）（4）析取三段论 ………（4分）

（6）x(F(x)G(x)) 前提引入

（7）F(x)G(x) （6）

（8）G(x) （5）（7）假言推理

（9）G(x) （8） ………（3分）

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

o是函数的复合运算。

证明：F,o是群。

证明：由于集合A是非空的，IAF，,因此F非空 。

(1)

f,gF,因为f和g都是A到A的双射函数，故fog也是A到A的双射函数，从而集合F关于运算 是封闭的。

(2)

f,g,hF,由函数复合运算的结合律有(fog)ohfo(goh)，故运算o 是可结合的。

(3)

A上的恒等函数IA也是A到A的双射函数即IAF,且fF有IAoffoIA,

故IA 是F,o中的幺元。

(4)

fF,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有fof1f1ofIA,因此f1是f的逆元

由此上知F,o是群

3．设代数系统VZ6,，Z6{0,1,2,3,4,5}，为模6加法。证明：Z6关于运算构成群。

证明：集合Z6显然非空。

(1)

a,bZ6,abZ6,从而集合Z6关于运算是封闭的。

(2)

a,b,cZ6,有(ab)ca(bc)，故运算 是可结合的。

(3)

aZ6,

a0a,故0是Z6,中的幺元。

(4)

aZ6,因为a(6a)0,因此6a是a的逆元

由此上知Z6,是群

4．设A是集合，P(A)是A的幂集合，是对称差运算， 证明

>构成群。

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

5．设A{x,y|x,y为正整数}，在A上定义二元关系R如下：x,yRu,v当且仅当xyuv。

证明：R是一个等价关系。

证明：

任取x,y

x,yAxyxyx,yRx,y

所以R自反的。

任取x,y,u,v

x,yRu,vxyuvuvxyu,vRx,y

所以R是对称的。

任取x,y,u,v,s,t

x,yRu,vu,vRs,txyuvuvst

xystx,yRs,t

所以R是传递的。

因此，R是等价关系。

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

（1）对于任意的aR， 都有aRa，

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

证明：R是等价关系

证明： 任取a,b,cR

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

a,aR,,所以R是自反的。

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

a,bRa,aRb,aR

所以R是对称的。

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

a,bRb,cRb,aRc,bR

b,cRb,aRc,aR

所以R是传递的。

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

1. 构造下列推理的证明。 如果今天是星期一，则要进行英语或离散数学考试。如果英语老师有会，则不考英语。今天是星期一，英语老师有会，所以进行离散数学考试。

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

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

3．如果甲是冠军，则乙或丙将得亚军；如果乙得亚军，则甲不能得冠军； 如果丁得亚军，丙不能得亚军；事实是甲已得冠军。因此丁不能得亚军。

参照作业：P54 17,18

4.用一阶逻辑推理证明

每个喜欢步行的人都不喜欢骑自行车，每个人或喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所以，有的人不喜欢步行（个体域为人类集合）

解: 令F(x):x喜欢步行,

G(x):x喜欢骑自行车,

H(x):x喜欢乘汽车

前提：x(F(x)G(x))，x(F(x)H(x))，

xH(x)

结论：

xG(x)

证明：（1）x(F(x)H(x)) 前提引入

（2）F(x)H(x) （1）

（3）xH(x) 前提引入

（4）H(x) （3）

（5）F(x) （2）（4）析取三段论

（6）x(F(x)G(x)) 前提引入

（7）F(x)G(x) （6）

（8）G(x) （5）（7）假言推理

（9）G(x) （8）

b会讲英语和汉语； c会讲英语、意大利语和俄语；d 会讲日语和汉语； e 会讲德国和意大利语；f 会讲法语、日语和俄语； g 会讲法语和德语。

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

解：用结点表示人，用边表能讲同一种语言，构

英

德英

俄

英

汉

日意

5．今有于a,b,c,d,e,f7个人，已知下列事实： a会讲英语；

ag法

示连接的两个人造出图G如下：

fbecd在G中存在着一条哈密顿回路如下，根据这条回路安排座位，就能够使每个人都能和他身边的人交谈。

汉

法

英

a英

c意

e德bgfd日

6． 一次学术会议的理事会共有20个人参加，他们之间有的互相认识但有的互相不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人？根据是什么？

7.设有7个城市v1，v2，……v7，任意两个城市之间直接通信线路及通信线路预算造价如带权图所示，试给出一个设计方案，使得各城市间能够通信，而且总造价最低。写出求解过程，并计算出最低总造价。

v115v6

v23v054v035441v5422v3v4解：带权图中边表示通信路，边上的数字表示修建该通信线路所需费用，于是求解此题便成为求权图中的最小生成树问题。

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

112233444555

v11v65v2v3v03v5212v4取(v1,v2)T,(v4,v5)T，(v3,v4)T，(v0,v4)T

(v0,v2)T，(v1,v6)T

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

图中最小生成树的权为:

w(v1,v2)+w(v4,v5)+w(v3,v4)+w(v0,v4)+w(v0,v2)+w(v1,v6)=1+1+2+2+3+5=14