离散数学测试题答案

测试题

离散数学

一、选择题

1.G是一棵根树，则（）o

A.G一定是连通的B、G一定是强连通的

C.G只有一个顶点的出度为。D.G只有一个顶点的入度为1

2.下面哪个语句不是命题（）o

A.中国将成功举办2008年奥运会B、一亿年前地球发生了大灾难

C.我说的不是真话D.哈密顿图是连通的

3、设R是实数集合，在上定义二元运算*:a,b€R,a*b=a+b-ab,则

下面的论断中正确的是（）。

A.0是*的零元B、1是*的幺元

C.0是*的幺元D.*没有等塞元

4.下面说法中正确的是（）。

A.所有可数集合都是等势的B、任何集合都有与其等势的真子集

C.有些无限集合没有可数子集D.有理数集合是不可数集合

5.无向完全图K3的不同构的生成子图有（）个。

A.6B.5C.4D.3

6.下面哪一种图不一定是无向树

A.无回路的连通图

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

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

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

7、设集合A={{1,2,3},{4,5},{6,7,8}},则下列各式为真的是（to

A.lAB.{{4,5}}A

C.{1,2,3}(AD.((A

8、在有界格中,若一个元素有补元，则补元（）o

A.必惟一B、不惟一

C.不一定惟一D.可能惟一

9、设集合A={1,2,3,…,10},下面定义的哪种运算关于集合A是不封闭

的？（）

A.x*y=max{x,y}

B.x*y=min{x,y}

C.x*y=GCD(x,y),即x,y的最大公约数

D.x*y=LCM（x,y）,即x,y的最小公倍数

10、集合X中的关系R,其矩阵是，则关于R的论述中正确的是（）o

A.R是对称的B、R是反对称的

C.R是反自反的D.R中有7个元素

11.下列各组数中，哪个可以构成无向图的度数列（）o

A.l,1,1,2,2B.2,2,2,2,3

C.l,2,2,4,6D.2,3,3,3

12.是定义在Z上的二元运算，，则的幺元和零元分别是（）o

A.不存在，0B.0,1

C.1,不存在D.不存在，不存在

13.设为自然数，且

I若x为奇数

/W=-若x为偶数

12

则/（。）和r（{。}）分别是（）o

A.O,0B.0,{0}

C.{0},{0}D.{0},0

14.下列命题公式中是矛盾式的有（）o

A.(〃一＞—1〃)一＞—\pB.-i(qtp)八p

C.(—＞pfq)f(qT—1〃)D.(。vq)f;•

15.下列各Hasse图中，是格的有（）。

A.B.

C.D.

16.下列命题公式中是永假式的有（）o

A.(〃—＞―i〃)一＞—1〃B.Tq-»〃)A〃

C.(r?f夕)f(Ffp)D・(pvq)Tr

17.设命题公式((P((Q((P)),记作G,则使G的真值指派为。的P,Q的取

值是()o

A.(0,0)B.(0,l)C.(l,0)D.(l,l)

18.与命题公式P((Q(R)等值的公式是()o

A.(P(Q)(RB.(P(Q)(RC.(P(Q)(RD.P((Q(R)

19.命题公式伊9乂「是()o

A.永真式B.永假式C.可满足式D.合取范式

（）o

A.充分条件B.必要条件C.充分必要条件D.既非充分也非必

要条件

30.设,则与V能构成强连通图的边集合是（）。

A..E={<a,d>,<>,<b,d>,<c,b>,<d,c>}

B.E={<a,d>,<b、a>,<Z?,c>,</?,J>,<d,c>}

C.E={<a.c>,<b,a>,<Z?,c>,<d,a>,<d,c>}

D.E={<a,b>,vayc>,va,d>,<b,d>,<c,d>}

31.相邻矩阵具有对称性的图一定是（）。

A.有向图B.无向图C.混合图D.简单图

32.无向图G是欧拉图，当且仅当（）o

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

数

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

为奇数

33.设为连通平面图且有r个面，则r=（）。

A.m—n+2B.n-m—2C.n+m-2D.m+n+2

34.设G是由5个结点组成的完全图，则从G中删去（）条边可以得到

树。

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

35.由5个结点可构成的根树中，其叉数m最多为（）o

A.2B.3C.5D.4

36.下图是（）。

A.完全图B.哈密顿图C.欧拉图D.平面图

37.设集合A={1,2,3,…,10},在集合A上定义的运算，不是封闭的为

()o

A.a,bA,ab=lcm{a,b}(最小公倍数)B.a,bA,

ab=gcd{a,b}(最大公约数)

C.a,bA,ab=max{a,b}D.a,bA,

ab=min{a,b}

38.在自然数N上定义的二元运算。满足结合律的是()o

A.a(b=a—bB.a(b=a+2bC.a(b=max{a,b}D.a(b=(a-b(

39.下列代数系统(G,*)中，其中*是加法运算.()不是群。

A.G为整数集合B.G为偶数集合

C.G为有理数集合D.G为自然数集合

4。设(1,(2,(3是三个置换,其中(1=(12)(23)(13),(2=(24)(1

4),(3=(1324)

则3可以表成()o

A.B.(l(2C.D.(2(l

41.下列图表示的偏序集中，是格的为()。

A.B.

C.D.

42.设是布尔代数，，则下式不成立的是()o

A.QB=OB.67+/?=1C.a+b=aD.4+分=1

43.布尔代数式=()o

A.a+加B.Z?+cQ.b+cD.b+c

44.设集合A={1,2},B={a,b,c},C={c,d},则Ax(B(C)=()。

A.{<c,l>,<2,c>}B.{<l,c>,<2,c>}C.{<c,l>,<c,2>}

D.{<l,c>,<c,2>}

45.设A={0,a},B={l,a,3},则A(B的恒等关系是()。

A.{<0,0><l,l>,<3,3>,<a,a>}B.{<O,O>,<1,1>,<3,3>}

C.{<l,l>,<a,a>,<3,3>}D.{<0,l>,<l,a>,<a,3>,<3,0>}

46.设A={a,b,c},R={<a,a>,<b,b>},则R具有性质()。

A.自反的B.反自反的C.反对称的D.等价的

47.设集合是从A到B的函数，

,则(是()。

A.双射B.满射但不是单射C.单射但不是满射D.非单射也非满射

48.下列式子中正确的是()0

A.=0B.C.{a,b}D.{}

49.有向图的邻接矩阵中，行元素之和是对应结点的（）,列元素之和

是对应结点的()。

A.度数B出度C.最大度数D.入度

50.给定无向图如下所示，下面给出的顶点集子集中，不是点割集的是

()o

A.{b,d}BJd}

C.{e}D.{f,h}

51.谓词公式xA(x)xA(x)的类型是()o

A.永真式B.矛盾式

C.非永真式的可满足式D.不属于(A),(B),(C)任何类型

52.谓词公式取真值为1的充分必要条件是()。

A.对任意y,使P(v)都取真值1

B.存在一个y0,使P(y0)取真值1

C.存在某些y,使P(y)都取真值1

D.存在y0,使P(yO)取真值。

53.设G是群，当6有()个元素时，不能肯定G是交换群。

A.4B.5C.6D.7

54.若集合A={a,b,c},(为空集合，则下列表示正确的是()o

A.{a}AB.{a}AC.aAD.A

55.设A,B,C都是集合，如果A(C=B(C,则有()。

A.A=BB.ABC.当A-C=B-C时，有A=BD.当C=U

时，有AB

56.设Sl=(,S2={(},S3=P({(}),S4=P((),以下命题为假的是()。

A.S2(S4B.S1(S3,C.S4(S2D.S4(S3

57.设G是有6个元素的循环群,a是生成元素，则G的子集()是

子群。

A.{a}B.{a,e}C.{e,a3}D.{e,a,a2}

58.设集合A={a,b,c,d,e},半序关系R的哈斯图

如下，假设A的子集B={c,d,e},则元素c为B的()o

A.下界B.最大下界

C.最小上界D.以上答案都不对

59.设G((x(yP(x,y)(Q(z,w),下面三个命题为真的是()。

A.G是前束范式B.G不是前束范式

C.G不是一阶公式D.G是永真式

60.对任意集合S,S((=S,满足()o

A.塞等律B.零一律C.同一律D.互补律

61.设命题公式，则使公式G取真值为1的P,Q,R赋值分别是()0

A.0,0,0

B.0,0,1

C.O,1,0

D.l,0,0

62.设a是集合A的元素，则以下正确的是()o

A.Qq{a}

B.{a}qA

C.a^A

D.{rz}eA

63.设集合A{1,2,3,4},B:{2,4,6,9},则集合A,B的对称差A，B=

()o

A.{1,3}

B.{2,4,61

C.{1,3,6,9}

D.{1,2,3,4,6,9}

64.有向完全图D=<V,E>,则图D的边数是()0

A.|E|(|E|-1)/2

B.|V|(|V|-1)/2

C.|E|(|E|-1)

D.|V|(|V|-1)

65.设G是有n个结点，m条边的连通阻，必须删去G的()条边，才

能确定G的一棵生成树。

A.m-n+1

B.n-m

C.m+n+1

D.n—m+1

66.设N为自然数集合，＜N,＞在下面4种运算下不构成代数系统的

是（）。

A.xy=x+y—2xyB.xy=x+y

C.xy=xyD.xy=|x|+|y|

67.已知图G的相邻矩阵为，则6有（）。

A.6个点，度为4B.5个点，度为6

C.4个点，度为3D.4个点，度为6

68.设集合A={1,2,3,……,10）,半序关系（是A上的整除关系，则

半序集（A,（）上的元素1。是集合A的（）。

A.最大元B.最小元C.极大元D.极小元

二、填空题

1.代数格（L,（,（）中的运算（和（满足的算律有、、

2.A是含有3个元素的集合，在A上可以定义个不同的等价关系。

3.R是实数集合,R中的关系g=kx2,x＞}从R到R的函数（填

“是”或“不是”）。

4.vG,*＞是群，|G|＞1,则G中的零元o

5、当n是____________值时，无向完全图Kn是欧拉图。

6、I是整数集合，代数系统〈I,X＞（X是通常乘法）的幺元是______,-1

的逆元是___________o

7、元素数目不超过_______的格一定是链。

8、公式T/，vQ)c(〃人⑵的主合取范式为o

9、的有效结论是__________o

1。、已知公式A(p,q,r)的主合取范式为MAMAM，它的主析取

范式为(写成编码形式)。

11.设A={a,b},B={0,l,2},则可定义种不同的从A到B的单射。

12.已知集合A={(,1,2},则A的塞集合((A六o

13.设〈A,<>是分配格，若对任意的a,c,c£A,如果有aAb=aAc,aV

b=aVc成立，则abo

14、仅当n时，Kn为平面图。

15.p->q的主合取范式是_________________________o

16.语句“我在说谎"命题。(填“是”或“不是”)。

17.设A={a,b,c,d}>R是定义在A上的关系,R={<a,b>,<c,d>,<a,d>},

贝Ur(R)=o

18.一个树林G有三棵树，G的顶点数是20,则G的边数为

19.P(P(0))=o

20.整数加法群<Z,+>中1的阶是________________o

21.设有向图D=VV,E>的邻接矩阵为A(D)=，则(E(=o

22.语句“这句话是错的”命题。(填“是”或“不是

23.设命题公式G=P(((Q(R),则使G取真值为1的指派

是，，o

24.已知命题公式为G=((P(Q)(R,则命题公式G的析取范式

是。

25.公式的自由变元是,约束变元是

26.谓词逻辑公式的前束范式是

27.设个体域D={a,b},消去公式中的量词，则

28.换名规则施于变元，代入规则施于变元。

29.设图G=<V,E>和G(=〈V(,E(>,若，则G(是G的

真子图，若，则G(是G的生成子图。

30.在无向图中，结点间的连通关系具有性,性,

性，是关系

31.无环有向图D的关联矩阵M(D)中，第i行值为1的元素个数为结点

vi的

第j列值为-1的元素个数为结点%的

32.设G是完全二叉树，G有15个结点，其中有8个是树叶，则G有

条边，G的总度数是，G的分支点数是,G中度数为3

的结点数是

33.连通有向图D含有欧拉回路的充分必要条件

是

34.设G是有n个结点的简单图，若G中每对结点的度数之

和，则G一定是哈密顿图

35.设G是有n个结点，m条边的连通图,要确定G的一颗生成树,

必须删去G的条边

36.一个有向树T称为根树，若,其中,称

为树根,

称为树叶

37.在代数系统(N,+)中，其单位元是，有逆

兀.O

38.设A是非空集合，集合代数(P(A),(,。中，P(A)对运算(的单位元

是,P(A)对运算(的单位元是。

39.把置换表成轮换的乘积是，表成对换

的乘积是。

40.设G是由6个元素构成的循环群，a是G的一个生成元素，则G有

个子群，G的生成元是。

41.非空集合L,其上定义二元运算(和(，如果是交换群，(L,()

是，而且满足分配律，则L对二元运算(和(构

成环。

42.设L是一个集合，(和(是L上两个二元运算，如果这两个二元运算满足

律，律和律，则(L,(,()是格。

43.在布尔代数中，有成立.则该式的对偶式也一定

成立。

44.设RI,R2是集合A={1,2,3,4}上的二元关系，其中R1=

{<1,1>,<1,2>,<2,4>},R2={<l,4>,<2,3>,<2,4>,<3,2>},ljllJR1(R2

=o

45.设R,S都是集合A上的等价关系，则对称闭包

s(R(S)=o

46.图的通路中边的数目称为.结点不重复的通路是通

路.边不重复的通路是通路。

47.将谓词公式中的约束变元换名___。

48.写出下列集合的子集：BHO；C-(o

49.设全集合E

{1,2,3,4,5},A={1,2,3},B={2,5},A(B=,~B=。

〜A〜B=o

50.设A,B代表集合，命题A(B((((((的真值为。

51.设集合A={a,b,c},B={a,b},则P(A)-

P(B)=,P(B)-P(A)=o

52.设人={=,(,(,(,(}选择适当的符号填在各小题的横线上.(1)(1,2,3,4)

N;(2)o

53.关于格的命题P：aA(bVc),求P的对偶命题P*=o

54.计算Z6的所有理想o

55.求的真值_____________o

56.判定公式((P(Q(((R(Q()(((P(R((Q)的类型__________。

57.将命题公式化为只含(和(的尽可能简单的等值式o

58.设n(A)=m，则A上有个不同的自反关系。

59.设集合A={a,b,c,d(,A上的关系R={(a,a),(a,c),(b,d)),则关系

R2=o60.设集合A中有4个元素，则A上的不同的等

价关系的个数为个。

三、判断题

1.空间中的平行六面体是平面图。()

2.每个顶点的度都是偶数的无向图一定是欧拉图。()

3、顶点数目相同，边数也相同的两个无向图一定同构。()

4.函数的逆关系还是函数。()

5.A,B,C制S是集合，如果AUB-AUC,贝ijB三C。（）

6、设R是环,A,B是R的两个理想，且B包含于A,则A/B是R/B的理

想，并且

R/B/（A/B）同构于R/Ao（）

7.的对偶是。（）

8.设G是有r个面的连通平面图，顶点数和边数分别是n和m,则

n-m+r=2°（）

9.n阶有向完全图有n（n-1）条边。（）

1。.在代数系统中，若，则。（）

11.设无向图T是树，则T中一定没有简单回路。（）

12.能够画在一张平面上的图是平面图。

13.设是代数系统,B是S的非空子集，则是的子代数。（）

14.循环群的子群仍然是循环群。（）

15.格不一定是布尔代数。（）

16.1+101=110是命题。（）

17.“全体立正是命题"o（）

18.“明天是否开大会？”是命题。（）

19.“如果天气好，则我去散步”是命题。（）

20.判断亿,（）是否为格？其中（是数的小于或等于关系。（）

21.设R是实数集，“+”为数的加法，“X”定义为.试问R对二元

运算+和X是否构成环。（）

22.设集合人={18的正整数因子},(为整除关系，说明＜A,(，是否是偏序

关系。()

23.是对的。()

24.(是(的子集。()

25.如果S(T=S(M,则丁=乂。()

26.已知S={2,a,{3},4},R={{a},3,4,l}〃J{a}(S0()

27.整数集合Z和普通的减法运算是封闭的。()

28.在R中定义二元运算：*,a*b=a+b+ab,对于任意a,b属于R,则

＜R,*＞是独异点。()

29.整数集合{1,2,3,4,6,12}关于整除关系构成了偏序集，并且该偏序集

是格。()

四、证明题

1.设〈G,*＞是群，具有幺元e,如果对G的任意元素a,都有

a2=e,贝kG,*＞是交换群

2.形式证明

3.证明：P((Q(R)(P(Q(R.

4.试证明:

5.试证明：

6.证明：(

7.设G是图，无回路，但若外加任意一条边于G后，就形成一回路.

试证明G必为树.

8.设B是任意集合，试验证(P(B),()是群.P(B)是集合B的希集，(是集合

的对称差运算,

9.给定代数系统(G,+,*),二元运算见表一，表二.

表二

+abcD*abcD

AabcDaaaaa

BbadCbabcd

CcDaBcacdb

DdCbAdadbc

证明(G,+,*)是域.

10.证明如果非空集合A上的二元关系R和S是偏序关系，则也是A上

的偏序关系.

11.试证A-(B—C)=(A-B)((A(C)

12.设非空集合A,验证()是布尔代数，

13.试证明属于关系不满足传递性，即对于任意的集合A,B,C若A€B且

BCC不一定有

AWC

14.设A,B为两个集合，证明A—8=人当且仅当ACB=。

15.设R,S都是非空集合A上的二元关系，且他们是对称的，证明:

RoS具有对称性当且仅当RoS=SoR.

16.已知g:A->B,f:B->C

1)已知fog是单射的且g是满射的，证明f是单射的

2)已知fog是满射的且f是单射的，证明g是满射的

17.设A是传递集，证明A+也是传递集。

18.设G是n阶无向简单图，其直径为d(G)=2,o(G)-n-2,证明G的边

数m>2n-4

19.V=〈S,*>是可交换半群，若a,b€S是V中得得等元，证明a*b也是V

中的塞等元

20.设L是格,证明对于任意a,b,c,d€L有：(aAb)V(cAd)<(aVc)

A(bVd)

五、计算题

L无向树T有2个2度顶点，1个3度顶点，3个4度顶点，其他的都是

树叶，问T中有多少片树叶？

2.设公式，其中P(x):x>2,

Q(x):x=0,F是永假式，个体域是{1,2},求公式A(x)的真值

3.设集合乂={1,2,3,4),X中的关系为

F={<1,1>,<1,2>,<1,4>,<2,1>,<2,2>,<3,3>,<4,1>,<4,4>}

写出F的关系矩阵与其关系图，F有哪些性质？

4.(1)n(n>1)阶无向完全图与有向完全图各有多少条边为什么？

(2)完全二部图K中共有多少条边为什么？

(3)每个顶点的度都为k的无向图称为k正则图，问：n阶k

正则图中共有多少条边为什么？

5.设集合1=g，b},在L中规定+和・如下：

a+a=a,a+b=b+a=b,b+b=b

a•a^a,a•b-b•a-a,b•b三b

问vL,+,•>能构成代数系统吗？若可以，写出该代数系统的运算表。

该代数系统有什么特性？

6.设多重集A={{},{,1},{1,1,}},B={{,1},{1}}.计算AB,AB,

A-B

7.设集合M={1,2,3,4,5},(和(是M上的两个置换，(=,(=(1

45)(23),用轮换的形式写出((，(()(-1((-lo

8.对集合L,规定对于x,yEL,x<y当且仅当x是y的因子。问下面哪

几个偏序集是格为什么？

(1)L={1,2,3,4,6,12}

出1={1,2,3,48,12,14}

(3)L={1,2,3,4,5,6,7,8,9,10}

9.在全总个体域中符号化下列命题。

(1)是金子总是要发光的。

(2)并非所有微笑的人都是高兴的。

(3)平面图的色数不超过4

10.若无向图G是欧拉图，G中是否存在割边为什么

11.设集合，区是定义在A上的二元关系，，写出R的关系矩阵并求

R的对称闭包。

12.设集合A={2,3,4,6,8,12,24},R为A上的整除关系。

(1)画出半序集(A,R)的哈斯图；

(2)写出集合A中的最大元、最小元、极大元、极小元；

(3)写出A的子集B={2,3,6,12}的上界、下界、最小上界，最大下界。

13.令X-｛,，…，｝,YH,，…，｝o问

⑴有多少个不同的由X到Y的关系？

⑵有多少个不同的由X到Y的函数？

⑶当n,m满足什么条件时，存在单射，且有多少个不同的单射？

14.在全总个体域中符号化下列命题。

(1)在中国工作的人并非都是中国人。

(2)有的人在微笑但内心不高兴。

(3)每种金属都可以溶解在某种液体种。

15.将下列命题符号化：

(1)虽然交通堵塞，但是老王还是准时到达火车站；

(2)张力是三好学生或优秀共青团员

(3)老李或小刁中有一个人去广州出差

16.判定公式P(Q与(P(Q是否等值.

17.用等值演算法判定公式P(((Q(R"P(Q(R是永真式？永假式？

18.求公式的主合取范式和主析取范式.

19.化简下式：(A(B(C)(((A(B(C)

20.设命题P,Q的真值为0,命题R,S的真值为1,求命题公式的真

值.

21.将下列命题符号化：

(1)每个母亲都爱自己的孩子；

(2)所有的人都呼吸；

(3)有某些实数是有理数.

22.指出下列公式

VxVy(7?(x,y)vL(y,z))AZ1X77(X,y)

中量词的每次出现辖域，并指出变元的每次出现是约束出现，还是自由出

现，以与公式的约束变元，自由变元.

23.给定解释I:

①D={2,3};

②D中特定元素a=2;

③函数为〃2)=3J⑶=2

④谓词F(x)为F⑵=0,F⑶=1

G(x,y)为G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=l

L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0

求在解释I下各公式的真值.

(1)VxR(x)AG(A,a)；

(2)Vx3yL(x,y);

24.讨论公式的类型.

25.将公式F化为前束范式.

26.判定下面二图是否同构？

27.设G=(V,E)是一个无向图，

E={<Vj,V2>,<v2,v3>,<匕，匕>»<V,,V5>,<v5,v4>,<v3,v4>,<V7,V8>}

(1)画出G的图解；

⑵指出与V3邻接的结点，以与与V3关联的边;

(3)指出与e1关联的结点；

(4)该图是否有孤立结点和孤立边？

(5)求出各结点的度数，并判断是不是完全图？

(6)G=〈V,E>的(V(,(E(各是多少？

28.给定下列六个图(如图)，

Gi=〈Vi,Ei>,其中Vi={a,b,c,d,e},Ei={(a,b),(b,c),(c,d),(a,e)}

G2=〈V2,E2>淇中V2=Vi,E2={(a,b),(b,e),(e,b),(a,e),(d,e)}

G3=〈V3,E3>,其中V3=V],E3={(a,b),(b,e),(e,d),(c,c)}

=<V4,E4>,其中

V4=V1,E4={<a,b>,<b,c>,<c,a>,<a,d>,<d,a>,<d,e>}

G5=<V5,E5>,其中

V5=Vi,E5={<a,b>,<b,a>,<b,c>,<c,d>,<d,e>,<e,a>}

G6=〈V6,E6>,其中V6=V1,E6={<a,a>,<a,b>,<b,c>,<e,c>,<e,d>}

试问：

(1)哪些图是有向图？哪些图是无向图?

(2)哪些是简单图？

(3)哪些是强连通图？哪些是单侧连通图？哪些是弱连通图?

29.求图G的点割集、割点、边割集和割边.

30.已知有关人员a,b,c,d,e,f,g的有关信息：

a：说英语；

b:说英语或西班牙语；

c;说英语，意大利语和俄语；

d:说日语和西班牙语

e:说德语和意大利语；

f：说法语、日语和俄语；

g：说法语和德语.

试问上述7人中是否任意两人都能交谈(如果

必要，可由其余5人中组成的译员链帮助)

31.在具有n个结点的完全图Kn中，需要删去多少条边才能得到树.

32.画出具有下列条件的有5个结点的图.

(1)没有哈密顿问路，也不能适当指定各边的方向，使其具有欧拉

回路；

(2)有哈密顿回路，但是不能适当指定各边的方向，使其具有欧拉回

路；

⑶没有哈密顿回路，但是能适当指定各边的方向，使其具有欧拉回路;

(4)有哈密顿回路，也能适当指定各边的方向，使其具有欧拉回路.

33.通常数的加法运算可看作正整数N+上的二元运算.下列集合是N+的

子集，加法运算在这些子集上封闭吗？为什么？

(1)是15的因子}⑵邑={m是1%勺倍麴

(3)§3={“6整的,24整除〃1

;运算*是否有单位元和富等元？若有单位元的话，哪些元素有逆元？

35.是布尔代数，，化简,

36.设是定义在Z5(={0」,2,3,4})上的多项式(即系数是Z5的元素的多

项式)，试计算P(x)+Q(x),P(x)Q(x).

37.回答下列代数系统是环吗？是交换环吗？

(l)(Zm,+,*),其中Zm={0,l,2,…,m—l},+和*是模m加法和

乘法.

(2)(Mn(R),+,(),其中Mn(R)是n阶实矩阵全体，+,(分别是矩阵的加

法和乘法.

38.设集合A={a,b},R是P(A)上的包含关系，写出R的表达式和关系

矩阵.

39.设A={1,2,3},用列举法给出A上的恒等关系IA,全关系EA,A上的小

于关系

与其逆关系和关系矩阵.

40.设A={1,2,3,4},R是A上的二元关系，其关系矩阵为

Io()r

1000

MR=

“0001

1000

试求⑴R的关系表达式；⑵Dom(R)和Ran(R);

(3)RR中有多少个有序对(4)R-的关系图中有多少条自回路

41.设集合判定下列关系，哪些是自反的，对称的，反对称的，传递的？

R[={<a,a>,<h,a>},&={<aya>,<>,<

&={<c,d>),/?4={<a,a>,<b,b>,<c,c>),/?5={<a,c>,<b,d>),

42.设A={1,2,3,4,5,6},定义A上的二元关系

R={<1,1>,<1,4>,<2,2>,<2,3>,<2,6>,<3,2>,<3,3>,<3,6>,

<4,1>,<4,4>,<5,5>,<6,2>,<6,3>,<6,6>}

判定R是否为等价关系？(2)若是等价关系，写出A的关于R的等价

类.

43.设集合A={a,b,c,d},定义R={<a,b>,<b,a>,<b,c>,<c,d>},求

r(R),s(R),t(R).

44.求谓词公式的真值.其中44(3,Q(x):x(l,R(x):x(2.

f((3)=1,f(1)=5,f(5)=(3.a：5.

个体域D=((3,1,5).

45.化简

46.设集合人=匕,可旧={1,2,3}©=息},求(人乂8)乂(3,AXBXC,BxA.

47.用列举法表示以下集合：

(1)A={AJXGAA2<7);(2)4={A|XWNA|3-A|<3}；

2

(3)iA={G/?A(x+1)<0}

48.列出下列集合的各元子集，并求骞集

(1)A={a,b,c)(2)A={1,{2,3}}(3)A={0,{0}}

49.A={a,b,c},B={l,2},令al=P(A),a2=A->B,构造一个al到a2的双射

函数，再构造一个

a2到al的双射函数

50.由f:A->B导出A上的等价关系定义为：

R={<x,y>|xCAAy€AAf(x)=f(y)}

设WNUN且

fl(n)=nf2(n)=1n为奇数f3(n)=0n为偶数

f3(n)=j,n=3k+j,j=0,1,2,k€Nf4(n)=j,n=6k+j,j=0,l,---,5,k€N

Rk为fk导出的N上的等价关系,k=l,2,3,4

1)求商集N/Rkk=l,2,3,4

2)求14={10卜也€琳在fl,f2,f3,f4下的象!

51.对图给出的二叉树分别进行先根遍历、中根遍历和后根遍历。

更多课程资料请到大学课程网学习

测试题答案

离散数学

一、选择题

l.A2.C3.C4.A.5.D6.C7.D8.C9.D

10.D

11.B12.D13.B14.B15.B16.B17.C18.B

19.A20.D

21.C22.A23.D24.A25.C26.C,A27.B28.A

29.B30.A

31.B32.C33.A34.C35.D36.B37.A38.C

39.D40.D

41.C42.D43.B44.B45.C46.A47.B48.D

49.BQ50.A

51.B52.A53.D54.B55.C56.A57.C58.C

59.B60.C

61.D62.B63.C64.D65.A66.A67.D68.C

二、填空题

1.交换律、结合律、吸收律

2.5

3.不是

4.不存在

5.奇数

6.1,-1

7.3

8.

9.R

10.mlVm2Vm4vm6Vm7

11.6

12、((A)={(,{ft,{1},{2},{(,1},{(,2},{1,2},A}

13=

14.奇数

15.

16.不是

17、{<a,b>,<c,d>,<a,d>,<a,a>,<b,b>,<c,c>,<d,d>}

18、17

19、{cp,{cp}}

20、无限

21.7

22.不是

23.(1,0,0,)(1,0,1)(1,1,1)

24.P((Q(R

25.y,xx,z

26.

27.

28.约束自由

29.

30.自反性对称性传递性等价.

31.出度入度

32.142876

33.D中每个结点的入度=出度.

34.大于或等于n

35.m+l—n

36.若有向图T恰有一个结点的入度为0,其余结点入度为1入度为。的

结点入度为1的结点.

37.0仅有单位元0.

38.(A.

39.(123)(56)(13)(12)(56)(不唯一)

40.4a,a5

41.(L,()半群二元运算(对运算(

42.交换律结合律吸收律

43.

44.{<1,4>,<1,3>}

46.45.R(S

47.通路出度初级简单.

48.V〃(P(〃)TR(u)vQ(〃,z))A3v7?(v)—>w)

49.??{}????

50.{2},{1,3,4},{1,3,4,5}

51.0

52.{{c},{a,c},{b,c},{a;b,c}};

53.

54.（aAb）V（aAc）

55.{0},{0,3},{0,2,4}{0,l,2,3,4,5）

56.1

57.永真式

57.

582,n2~m

59.R2={（a,a）,（a5c）}

60.15

三、判断题

1.正确（从同构的角度说明理由）

2.错误（举反例）

3.错误（举反例）

4.错误（从同构的角度说明理由）

5.错误（举反例）

6.正确

7.错误

8.正确

9.正确

10.错误

12.11.正确

13.错误

14.错误

15.正确

16.正确

17.否

18.否

19.否

20.是

21.是

22.否

23.是

24.错误

25.真

26.假

27.错误

28.正确

29.是

30.是

四、证明题

证明：由条件，所以，则对任意的％b,

a*b=a7*b-]

另外，由，得

两边同时左乘以，右乘以，利用结合律，得

b*a=a*b

所以，＜G,*＞是交换群

2.证明：

(1)“AS前提引入

(2)P(1)化简

(3)s(1)化简

(4)p->qVr前提引入

(5)qVr(2)(4)分离

(6)s->-ir前提引入

(7)-ir(3)(6)分离

(8)q(5)(7)析取三段论

3.证明

P(QR)

P(QR)(等值蕴含式)

P(QR)(等值蕴含式)

(PQ)R(结合律)

(PQ：1R(摩根律)

PQR(等值蕴含式)

所以，P((Q(R)((P(Q)(R

4.证明

(1)SCP规则

(2)SPP

⑶P(1),(2)析取三段论

⑷P(QR)P

(5)QR⑶，⑷假言推理

(6)QP

(7)R(5),⑹假言推理

5.证明

(1)QRP

(2)RP

(3)Q(1),(2)析取三段论

(4)(PQ)P

(5)PQ⑷置换

(6)Q(3),(5)析取三段论

6.证明

前提:

结论：

(1)-(Vx(A(x)fB(x)))附加前提

⑵3x(-i(A(x)tB(x)))(1)”

⑶—i(/4(c)—>B(。))(2),ES

⑷A(c)(3),T,E

⑸B(c)(3),T,E

(6)BxA(y)(4),EG

⑺3X4(A)-VxB(x)P

(8)VXB(A)(6),(7),T,E

(9)B(c)(8),US

(10)—iB(c)A6(c)(5),(9)矛盾式

7.由树的定义可知，只需证G连通即可.任取不相邻两点u,v,由题设，加

上边vu,v>就形成一回路，于是去掉边vu,v>,从U到V仍有路U,…,V,即

u,v连通，由u,v的任意性可知，G是连通的，故G必是树.

8.证明

对任意集合C,D,E(P(B),有

(C㊉。)㊉E=[(CC~0D(3I~CWE

=[((Cn〜D)。(DA~Q)n〜0U[En~((Cn〜。)u(Qfl~C))]

=(cn~on~E)u(~cnDn~E)u(£n~cn~o)u(cnon©

C㊉(。㊉E)=C㊉[(Oc〜七)。(牙1~O)]

=(cn1~((Dn~E)51~r>))U~cni(r>n~石)5殖~D)]

=(cn~£n~£)u(cnon£)u(~cnon~£)u(~cn~on&

所以，故(P(B),()是半群.

0£?(8),任意。£尸(8),

0㊉C=(0-C)U(C-0)=C=C^0

所以(是二元运算(的单位元.

,任意元素C,二元运算(的逆元是它自身.

可见，(P(B),0是群.

1。.9.用运算表知(G,+)是可结合的和可交换的，a是运算+的单位元，任

一元素的逆元是它自身；所以(G,+)是交换群；容易验证｛G一值｝,*｝也是

交换群.且*对+是可分配的.故(G,+,*)是域.

证明①，所以有自反性；

②因为R,S是反对称的,

所以.R(S有反对称性.

③，因为R,S是传递的，

<x,y>£AcSA<y,z>£RcS

<=><x,y>GRA<x,y>GSA<y,z>G7?A<y,z>GS

<=><x,y>GR/\<y,z>GR/\<x,y>GSA<y,z>GS

=<x,z>wR八<x,z>eS<=><x,z>eRnS

所以，有传递性.

总之，R是偏序关系.

11.证明对任意先

XGA-(I3-C)

nxeA八xm(Be-C)=>xeAA(x5vxeC)

=(xwA△x任8)v(xw4八xwC)=>xw(A-B)D(AcC)

A—(B—C)c(A—B)u(AcC)

同理，有

xe(A-B)<j(Ar>C)=>xeA-(B-C)

所以，A-(B-C)=(A-B)((A(C)

12.证明因为集合A非空，故P(A)至少有两个元素，显然(，(是P(A)

上的二元运算.由定理，任给B,C,D(P(A),

HiBD=DCCD=DC

H2B(CD)=(BC)(BD)

B(CD)=(BC)(BD)

H3P(A)存在(和A,(B(P(A),有B((=B,B(A=B

H4,(B(P(A),B(A,存在A(~B,有

BA~B)=AB(A〜B)

所以(P(A),jC~,0,A)是布尔代数.

13.证明：本题也就是要证明：(1)AWBAB€C-〉AWC不为永真

式。

则就任意举一个反例：A反1},B={2,{1}},C={{2,{1}}}

其中AWB且B€C

很显然AC

故(1)式不为永真式

命题得证。

14.证明：A—B=A

AD~B=A

=>AA-BAB=AAB

=>AnB=0

AClB=0

=>(AAB)U〜B=~B

=>AU〜B=~B

=>ACl(AU~B)=An~B

=>AU(AA-B)=A-B

=>A=A-B

证明：

1)必要性

对于任意vx,y>€RoS

<=><y.x>RoS

<=>存在z(<y,z>€SA<z,x>€R)

存在z(<z,y>€SA<x,z>€R)

<=><x,y>€SoR

所以RoS=SoR.

2)充