离散数学试题

1/18

试题总汇

数理逻辑部分

1、判断下列句子中哪些是命题

（1）2是素数

（2）血是黑色的

（3）2+3=5

（4）明年10月1日是晴天

（5）3能被2整除

（6）这朵花多好看呀！

（7）明天下午有会吗？

（8）请关上门！

（9）X+y>5

（10）地球外的星球上也有人

2、将下列命题符号化

（1）3不是偶数

（2）2是素数和偶数

（3）李芳学过英语或日语

（4）如果角A和角B是对顶角，则角A等于角B

（5）李平虽然聪明，但不用功

（6）李平不但聪明，而且用功

（7）小王是游泳冠军或者百米赛跑冠军

（8）小王现在在宿舍或者在图书馆

（9）选小王或者小李中的一人当班长

（10）如果我上街，我就去书店看看，除非我很累

（11）如果明天天气好，我们去郊游。否则，不去郊游

（12）你爱我，我就嫁给你

3、判断下列命题公式是否等值

（1）（p∨q）与p∨q

（2）（p∨q）与p∧q

4、验证下列等值式

（1）p→（q→r）（p∧q）→r

（2）p（p∧q）∨（p∧q）

5、用等值演算法解决下面问题：

A、B、C、D4人百米竞赛。观众甲、乙、丙预报比赛的名次为，

（1）甲：C第一，B第二。（2）乙：C第二，D第三。（3）丙：A第二，D第四。

比赛结束后发现甲、乙、丙每人报告的情况都是给对一半。试问，实际名次如何？

6、求下面命题公式的主析取范式和主合取范式

（1）（（p∨q）→r）→p

7、利用真值表求主析取范式和主合取范式

（1）（p∧q）∨r

8、逻辑推理证明

（1）前提：p→r，q→s，p∨q。结论：r∨s。

2/18

（2）前提：p∨q，p→r，s→t，s→r，t。结论：q

（3）前提：p→（q→r），s→p，q。结论：s→r。

（4）前提：p→（（r∧s）→q），p，s。结论：q

9、给定语句如下：

（1）15是素数

（2）10能被2整除，3是偶数

（3）你下午有会吗？

（4）2x+3>0

（5）2是素数或是合数

（6）这个男孩真勇敢呀！

（7）如果2+2=6，则5是奇数

（8）只有4是偶数，3才能被2整除

（9）明年5月1日是晴天

（10）圆的面积等于半径的平方与



的乘积

以上10个语句中，是简单命题的为A，是复合命题的为B，是真命题的为C，是假命题的

为D，真值待定（真值客观存在，只是现在不知道）的命题为E。

A：①（1）、（4）、（8）②（4）、（6）、（9）、（10）③（1）、（9）、（10）

B：①（3）、（10）②（2）、（5）、（7）、（8）③（7）、（8）

C：①（2）、（5）、（9）、（10）②（7）、（8）、（10）③（2）、（9）、（10）④（5）、（7）、（8）、

（10）

D：①（1）、（2）、（8）②（1）、（2）③（1）、（5）

E：①（4）、（9）②（9）③（7）、（8）

10、判断公式类型

（1）（p∧q）→（p∨q）

（2）（p



q）



（（p→q）∧（q→p））

（3）（p→q）∧q

（4）（p∧p）



q

（5）p→（p∨q）

（6）（p∨p）→（（q∧q）∧r）

（7）（（p→q）→p）



p

（8）（p∧q）∨（p∧q）

（9）（p∨q∨r）



（p∧q∧r）

（10）（p∧q）∧r

11、给定命题公式如下：（p→q）→（p∨q）

该命题公式的主析取范式中含极小项的个数为A，主合取范式中含极大项的个数为B，成真

赋值个数为C，成假赋值个数为D。

A、B、C、D：（1）0,（2）1,(3)2,(4)3,(5)4

12、一公安人员审查一件盗窃案，已知的事实如下：

（1）甲或乙盗窃了录音机

（2）若甲盗窃了录音机，则作案时间不能发生在午夜前

（3）若乙的证词正确，则午夜时屋里灯光未灭

（4）若乙的证词不正确，则作案时间发生在午夜前

（5）午夜时屋里灯光灭了

推理证明，谁盗窃了录音机。

3/18

13、设p=1，q=0，r=1，s=0，有下列命题公式

（1）（p∧q）→（s∧r）

（2）（p∧q∧r∧s）∨(s→q)

（3）（p∧q∧r）



（p∨s）

那么，（1）的真值为；（2）的真值为；（3）的真值为；

14、对于下面的语句，

（1）只要4＜3，就有3＞2

（2）只要4＜3，就有3≤2

（3）只有4＜3，才有3＞2

（4）只有4＜3，才有3≤2

（5）除非4＜3，否则3＞2

（6）4≥3仅当3≤2

（7）4＜3当且仅当3＞2

则，他们的真值是（1）（2）（3）（4）（5）

（6）（7）。

15、设A是含n个命题变项的公式，下面4个结论中，哪个是错误的？

（1）若A的主析取范式中含2n个极小项，则A是重言式

（2）若A的主合取范式中含2n个极大项，则A是矛盾式

（3）若A的主析取范式中不含任何极小项，则A的主析取范式为0

（4）若A的主合取范式中不含任何极大项，则A的主合取范式为0

16、已知命题公式A含有3个命题变项，其成真赋值为000，010，100，110。

则A的主析取范式为，主合取范式为。

17、判断下列语句是否为命题，如是命题请指出是简单命题还是复合命题，并讨论真值

（1）2是无理数

（2）5能被2整除

（3）现在开会吗？

（4）x+5＞0

（5）这朵花真好看呀！

（6）2是素数当且仅当三角形有3条边

（7）血是黑色的当且仅当太阳从东方升起

（8）2008年10月1日天气晴朗

（9）太阳系以外的星球上有生物

（10）小李在宿舍里

（11）全体起立

（12）4是2的倍数或是3的倍数

（13）4是偶数且是奇数

（14）李明与王华是同学

（15）蓝色和黄色可以调配成绿色

18、将下列命题符号化，并讨论其真值

（1）如果今天是1号，则明天是2号

（2）如果今天是1号，则明天是3号

19、设A、B、C为任意的命题公式

（1）已知A∨CB∨C，问AB吗？

4/18

（2）已知A∧CB∧C，问AB吗？

（3）已知AB，问AB吗？

20、设计一个符合如下要求的室内照明控制线路：在房间的门外、门内及床头分别装有控制

同一个电灯F的3个开关A、B、C。当且仅当一个开关的键向上或3个开关的键都向上时

电灯亮。则F的逻辑关系式可化简为。

（1）A∨B∨C（2）A∨B∨C∨（A∧B∧C）（3）A∨B∨（A∧C）

（4）C∨（A∧B）

21、将下列语句用谓词表达式符号化

（1）2是素数且是偶数

（2）如果2大于3，则2大于4

（3）凡是有理数均可表成分数

（4）有的有理数是整数

（5）没有不吃饭的人

（6）素数不全是奇数

（7）一切人都不一样高

（8）有的自然数无先驱数

（9）有些人喜欢所有的花

（10）任何金属都可以溶解在某种液体中

（11）凡是对顶角都相等

22、指出下列各合式公式中的指导变项、量词的辖域、个体变项的自由出现和约束出现

（1）x（F（x）→yH（x，y））

（2）xF（x）∧G（x，y）

（3）xy（R（x，y）∨L（x，y））∧xH（x，y）

23、给定解释I如下：

1）D

I

={2，3}

2）D

I

中特定元素a=2

3）函数f（x）为f（2）=3，f（3）=2

4）谓词F（x）为F（2）=0，F（3）=1；

G（x，y）为G（i，j）=1，i，j=2，3；

L（x，y）为L（2，2）=L（3，3）=1；L（2，3）=L（3，2）=0

在解释I下，求下列各式的值。

（1）x（F（x）∧G（x，a））

（2）x（F（f（x））∧G（x，f（x）））

（3）xyL（x，y）

24、求下列公式的前束范式

（1）xF（x）∧xG（x）

（2）xF（x）∨xG（x）

（3）xF（x）→xG（x）

（4）xF（x）→xG（x）

25、设F（x）：x是人，G（x）：x爱吃糖。有人给出语句“不是所有人都爱吃糖”的4种谓

词表达式：

（1）x（F（x）∧G（x））

（2）x（F（x）→G（x））

（3）x（F（x）∧G（x））

5/18

（4）x（F（x）∧G（x））

正确的答案是。

26、给出解释I，使下面两个公式在解释I下均为假，从而说明这两个公式都不是永真式

（1）x（F（x）∨G（x））→（xF（x）∨xG（x））

（2）（xF（x）∧xG（x））→x（F（x）∧G（x））

27、取个体域为整数集，给定下列公式

（1）xy（x*y=0）

（2）xy（x*y=1）

（3）yx（x*y=2）

（4）xyz（x–y=z）

（5）x–y=-y+x

（6）xy（x*y=y）

（7）x（x*y=x）

（8）xy（x+y=2y）

在上面的公式中，真命题的为A，假命题的为B。

A：①（1）、（3）、（4）、（6）；②（3）、（4）、（5）；

③（1）、（3）、（4）、（5）；④（3）、（4）、（6）、（7）

B：①（2）、（3）、（6）；②（2）、（6）、（8）；

③（1）、（2）、（6）、（7）；④（2）、（6）、（8）、（7）

集合部分

1、下列命题

（1）



；（2）；（3）

｛｝；（4）｛｝

正确的是；错误的是。

2、计算一下幂集

（1）P（）；（2）P（｛｝）；（3）P（｛，｛｝｝）；（4）P（｛1，｛2，3｝｝）

3、证明

（1）（A-B）∪B=A∪B；

4、化简

（（A∪B∪C）∩（A∪B））-（（A∪（B-C））∩A

5、已知：AB=AC，证明：A=B

6、求在1到1000之间不能被5和6，也不能被8整除的数的个数

7、某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会

打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另一种球（指篮球或排

球），求不会打这三种球的人数。

8、设F表示一年级大学生的集合，S表示二年级大学生的集合，R表示计算机科学系学生

的集合，M表示数学系学生的集合，T表示选修离散数学的学生的集合，L表示爱好文学的

学生的集合，P表示爱好体育运动的学生的集合，则下列各句子所对应的集合表达式分别是：

（1）所有计算机科学系二年级的学生都选修离散数学。A

（2）数学系的学生或者爱好文学或者爱好体育运动。B

（3）数学系一年级的学生都没有选修离散数学。C

6/18

（4）只有一、二年级的学生才爱好体育运动。D

（5）除去数学系和计算机科学系二年级的学生外都不选修离散数学。E

A、B、C、D、E：

①T（M∪R）∩S；②R∩ST；③（M∩F）∩T=；

④ML∪P；⑤PF∪S；⑥S-（M∪R）P

9、设S1=｛1，2，…，8，9｝，S2=｛2，4，6，8｝，S3=｛1，3，5，7，9｝，

S4=｛3，4，5｝，S5=｛3，5｝。确定在以下条件下X可能与S1,…,S5中哪个集合相等。

（1）若X∩S5=，则A

（2）若XS4但X∩S2=，则B

（3）若XS1但XS3，则C

（4）若X-S3=，则D

（5）若X



S3但XS1，则E

A、B、C、D、E：

①X=S2或者S3；②X=S4或者S5；③X=S1，S2或者S4；

④X与其中任何集合都不等；⑤X=S2；⑥X=S5；⑦X=S3或者S5；

⑧X=S2或者S4；

10、设A、B、C为任意集合，判断下述命题是否恒真，如果恒真给出证明，否则举出反例。

（1）A∪B=A∪CB=C

（2）AB=AB=

（3）A∩（B-C）=（A∩B）-（A∩C）

（4）（A∩B）∪（B-A）=B

11、设A、B为集合，试确定下列各式成立的充分必要条件：

（1）A–B=B

（2）A–B=B-A

（3）A∪B=A∩B

12、求使得以下集合等式成立时，a，b，c，d应该满足的条件：

（1）｛a，b｝=｛a，b，c｝

（2）｛a，b，a｝=｛a，b｝

（3）｛a，｛b，c｝｝=｛a，｛d｝｝

（4）｛｛a，b｝，｛c｝｝=｛｛b｝｝

（5）｛｛a，｝，b，｛c｝｝=｛｛｝｝

13、计算A∩B、A∪B、A-B、AB

（1）A=｛｛a，b｝，c｝，B=｛c，d｝

（2）A={{a，{b}}，c，｛c｝，｛a，b｝}，B=｛｛a，b｝，c，｛b｝｝

（3）A=｛x|x∈N∧x<3｝，B=｛x|x∈N∧x≥2｝

（4）A=｛x|x∈R∧x<1｝，B=｛x|x∈Z∧x<1｝

（5）A=｛x|x∈Z∧x<0｝，B=｛x|x∈Z∧x≥2｝

7/18

14、设|A|=3，|P（A）|=64，|P（A∪B）|=256，

求：|B|，|A∩B|，|A-B|，|AB|

15、设A=｛1，2｝，求：P（A）×A

16、设A、B、C、D为任意集合，判断以下等式是否成立，若成立给与证明，否则，举出

反例。

（1）（A∩B）×（C∩D）=（A∩C）×（B∩D）

（2）（A∪B）×（C∪D）=（A∪C）×（B∪D）

（3）（A-B）×（C-D）=（A-C）×（B-D）

（4）（AB）×（CD）=（AC）×（BD）

17、设F、G是N上的关系，其定义为：

F=｛|x，y∈N∧y=x2｝；G=｛|x，y∈N∧y=x+1｝；

求：G-1、FG、GF、F↑｛1，2｝、F[｛1，2｝]

18、设F=｛，<｛a｝，｛a，｛a｝｝>｝，求：FF，F↑｛a｝，F[｛a｝]。

19、设A=｛a，b，c，d｝，R=｛，，，｝。给出R、r（R）、s

（R）、t（R）的关系图。

20、设A=｛1，2，3｝，求出A上的所有的等价关系

21、设A=｛1，2，3，…，11，12｝，R为A上整除关系，画出哈斯图。

22、画出的哈斯图。

23、R是X上的二元关系，对于x∈X定义集合：R（x）={y|xRy}

显然R（x）X。如果X={-4，-3，-2，-1，0，1，2，3，4}，且令

R1=｛|x，y∈X∧x

R2=｛|x，y∈X∧y-1

R3=｛|x，y∈X∧x2≤y｝，

则下列集合满足

（1）R1（0）=A

（2）R2（0）=B

（3）R3（3）=C

（4）R1（1）=D

（5）R2（-1）=E

A、B、C、D、E：

①；②｛-4，-3，-2，-1｝；③｛-2，-1｝；④｛-1，0，1｝；

⑤｛-1，0｝；⑥｛1，2，3｝；⑦｛2，3，4｝；⑧｛0，1，2，3｝；

⑨｛1，2，3，4｝；⑩以上结果都不对

24、设S=｛1，2，3｝，定义S×S上的等价关系R，

，∈S×S有：～a+d=b+c

则由R产生了S×S的一个划分。在该划分中共有A个划分块，

其中最大的块有B个元素，并且含有元素C。最小的划分块有D块，每块含

有E个元素。

A、B、D、E：

①1；②2；③3；④4；⑤5；⑥6；⑦9；

C：

8/18

⑧1；⑨<1，2>；⑩<2，2>

25、设S=｛0，1｝，F是S中的字符构成的长度不超过4的串的集合，即

F=｛，0，1，00，01，…，1111｝，其中表示空串。

在F上定义偏序关系R：x，y∈F，

有∈Rx是y的前缀。

例如，00是001的前缀，但01不是001的前缀。

（1）偏序集的哈斯图是A；

（2）的极小元是B；

（3）的最大元是C；

（4）GF，G=｛101，1001｝，则G的最小上界是D，最大下届是E。

A：①链；②树；③既不是链，也不是树；

B、C、D、E：

④；⑤0；⑥0、1和；⑦不存在；⑧10；⑨1；⑩1111

26、设S=｛1，2｝，则S上可定义A个不同的二元关系，其中B个等价关系，

C个偏序关系，Is是D，是E。

A、B、C：

①1；②2；③3；④4；⑤8；⑥16；

D、E：

⑦等价关系但不是偏序关系；⑧偏序关系但不是等价关系；

⑨等价关系和偏序关系；⑩既不是等价关系也不是偏序关系；

27、下面给定5个函数，其中单射而非满射的有A，满射而非单射的有B，

双射的有C，既不单射，又不满射的有D。

设R为实数集合，Z为整数集合，R+、Z+分别表示正实数和正整数集合。

①f：R→R，f（x）=-x2+2x-1；

②f：R→Z+，f（x）=lnx；

③f：R→Z，f（x）=x，x表示不大于x的最大整数；

④f：R→R，f（x）=2x+1；

⑤f：R+→R+，f（x）=

x

x12

28、对于给定集合A和B，构造从A到B的双射函数。

（1）A=Z，B=N，其中Z，N分别表示整数集和自然数集；

（2）A=[



，2



]，B=[-1，1]的实数区间

29、（1）设S=｛1，2｝，R为S上的二元关系，且xRy。如果R=Is，则A；如果R是数

的小于等于关系，则B；如果R=Es，则C。

（2）设有序对与有序对<5，2x+y>相等，则x=D，y=E。

A、B、C：

①x与y可任意选择1或2；②x=1，y=1；③x=1，y=1或2；x=y=2；

④x=2，y=2；⑤x=y=1或x=y=2；⑥x=1，y=2；⑦x=2，y=1；

D、E：

⑧3；⑨9；⑩-2

30、设S=<1，2，3，4>，R为S上的关系，其关系矩阵是

9/18

























0001

1000

0001

1001

，

则（1）R的关系表达式是A；

（2）domR=B；ranR=C；

（3）RR中有D个有序对；

（4）R-1的关系图中有E个环。

A：①｛<1，1>，<1，2>，<1，4>，<4，1>，<4，3>｝；

②｛<1，1>，<1，4>，<2，1>，<4，1>，<3，4>｝；

B、C：

③｛1，2，3，4｝；④｛1，2，4｝；⑤｛1，4｝；⑥｛1，3，4｝；

D、E：

⑦1；⑧3；⑨6；⑩7

31、设S=｛1，2，…，9，10｝，是S上的整除关系，则的哈斯图是A，其中

最大元是B，最小元是C，最小上界是D，最大下界是E。

A：①一棵树；②一条链；③以上都不对；

B、C、D、E：

④；⑤1；⑥10；⑦6，7，8，9，10；⑧6；⑨0；⑩不存在

32、设R的关系图如所示，试给出r（R）、s（R）、t（R）的关系图。

abcde

33、画出下列集合关于整除关系的哈斯图。

（1）｛1，2，3，4，6，8，12，24｝

（2）｛1，2，…，8，9｝

34、设A=｛a，b｝，B=｛0，1｝，

（1）求P（A）和BA；

（2）构造一个从P（A）到BA的双射函数。

代数系统部分

1、设Z+=｛x|x∈Z∧x>0｝，*表示求两个数的最小公倍数的运算，则

（1）4*6=A；

（2）*在Z+上B；

（3）对于*运算的幺元是C，零元是D；

（4）在Z+中E；

A：①24；②12；

10/18

B：③只满足交换率；④只满足结合律；

⑤满足交换率、结合律和幂等律；

C、D：⑥0；⑦1；⑧不存在；

E：⑨不存在逆元；⑩只有唯一的逆元

2、在有理数集合Q上定义二元运算*，x，y∈Q有

x*y=x+y-xy

则（1）2*（-5）=A，7*1/2=B。

（2）*在Q上是C；

（3）关于*的幺元是D；

（4）Q中满足E；

A、B：①4；②7；③-13；

C：④可结合的；⑤不可结合的；

D：⑥1；⑦0；

E：⑧所有的元素都有逆元；⑨只有唯一的逆元；

⑩x∈Q，x



1时，有逆元x-1。

3、设V1=，V2=，其中S1=｛a，b，c，d｝，S2={0，1，2，3}。和*由运

算表1和表2给出。

abcd

aabcd

bbbdd

ccdcd

ddddd

表1



*0123

00110

11121

21232

30123

表2



定义同态：S1→S2，且

（a）=0，（b）=1，（c）=0，（d）=1，

则（1）V1中的运算A，其幺元是B，V2中的运算*C；

（2）是D，V1在下的同态像是E；

A、C：①满足交换律，不满足结合律；②不满足交换律，满足结合律；

③满足交换律，满足结合律；

B：④a；⑤d；

D：⑥单同态；⑦满同态；⑧以上两者都不是；

E：⑨；⑩<｛0，1｝，*>

4、设V1=<｛1，2，3｝，，1>，其中xy表示取x和y之中较大的数，V2=<｛5，6｝，*，

6>，其中x*y表示取x和y之中较小的数。

（1）V1含有A个子代数，其中平凡的真子代数有B个；

11/18

V2含有C个平凡的子代数。

（2）积代数V1×V2中有D个元素，其幺元是E。

A、B、C、D：

①0；②1；③2；④3；⑤4；⑥5；⑦6；

E：⑧<1，5>；⑨<1，6>；⑩<3，6>

5、设S=｛a，b｝，则S上可以定义A个二元运算，其中有4个运算f1，f2，f3，f4，

其运算表如下：

abab

aaaaab

baabba

f1f2

abab

abaaab

baabab

f3f4

则只有B满足交换律，C满足幂等律，D有幺元，E有零元。

A：①4；②8；③16；④2；

B、C、D、E：

⑤f1和f2；⑥f1、f2和f3；⑦f3和f4；

⑧f4；⑨f1；⑩f2；

6、设S=｛1，2，…，9，10｝，问下面定义的二元运算*是否为S上的二元运算？

（1）x*y=gcd（x，y），x与y的最大公约数；

（2）x*y=lcm（x，y），x与y的最小公倍数；

（3）x*y=大于等于xy的最小整数；

（4）x*y=max（x，y）；

（5）x*y=质数P的个数，其中x≤p≤y。

7、设V=是代数系统，其中R*为非零实数的集合。分别对下述小题讨论运算

是否可交换、可结合，并求幺元和所有可逆元素的逆元。

8、某二进制通信编码由4个数据位x1、x2、x3、x4和3个校验位x5、x6、x7构成，它们

的关系如下：

x5=x1x2x3；x6=x1x2x4；x7=x1x3x4；

其中为异或运算。

（1）设S为所有满足上述关系的码字的集合，且x，y∈S，

有xy=(x1y1,x2y2，…,x7y7)，那么是一个A。

（2）设x，y∈S，定义H（x，y）=





7

1

)(

i

yixi，那么当x≠y时，H（x，y）≥B。

（3）使用该种码可查出接收码中包含的所有k≤C位错误。

（4）使用该种码可纠正接收码中包含的所有k≤D位错误。

（5）如果接收到1000011，且知有一位出错，那么出错位是第E位。

12/18

A：①半群，但不是群；②群；③环，但不是域；④域；⑤前4种都不对；

B、C、D、E：

①1；②2；③3；④4；⑤5；⑥6；⑦7；⑧0；

9、对以下定义的集合和运算判断它们是不是代数系统。如果是，是哪一种？

（1）S1=｛1，1/2，2，1/3，3，1/4，4｝，*为普通乘法，则S1是A；

（2）S2=｛a1，a2，…，an｝，n≥2，ai∈R，i=1，2，…，n，

ai，aj∈S2，有aiaj=ai，则S2是B；

（3）S3=｛0，1｝，*为普通乘法，则S3是C；

（4）S4=｛1，2，3，6｝，为整除关系，则S4是D；

（5）S5=｛0，1｝，+、*分别为模2加法和乘法，则S5是E。

A、B、C、D、E：

①半群，但不是独异点；②是独异点，但不是群；③群；

④环，但不是域；⑤域；⑥格，但不是布尔代数；⑦布尔代数；

⑧代数系统，但不是以上7种；⑨不是代数系统；

10、图6-5给出一个格L，则

（1）L是A元格；

（2）L是B；

（3）b的补元是C，a的补元是D，1的补元是E。

A：①5；②6；

B：③分配格；④有补格；⑤布尔格；⑥以上都不对；

C、D、E：

⑦不存在；⑧c和d；⑨0；⑩c；

11、设是布尔代数，

（1）a，b∈B，公式f为b∧（a∨（a′∧（b∨b′）））,在B中化简f；

（2）在B中等式（a∧b′）∨（a′∧b）=0成立的条件是什么？

12、对以下定义的集合和运算判断它们能否构成代数系统？如果能，请说明是构成哪一种代

数系统？

（1）S1=｛0，1，2，…，n｝，+为普通加法，则S1是A；

（2）S2=｛1/2，0，2｝，*为普通乘法，则S2是B；

（3）S3=｛0，1，2，…，n-1｝，n为任意给定的正整数，且n≥2，*为模n乘法，为模n

加法，则S3是C；

（4）S4=｛0，1，2，3｝，≤为小于等于关系，则S4是D；

（5）S5=Mn（R），+为矩阵加法，则S5是E；

A、B、C、D、E：

①半群，不是独异点；②独异点，不是群；③群；

④环，不一定是域；⑤域；⑥格，不是布尔代数；⑦布尔代数；

⑧代数系统，不是以上7种；⑨不是代数系统；

13、（1）设G=｛0，1，2，3｝，若为模4乘法，则构成A；

（2）若为模4加法，则是B阶群，且是C。

G中的2阶元是D，4阶元是E。

A：①群；②半群，不是群；

B：③有限；④无限；

C：⑤Klein群；⑥置换群；⑦循环群；

D、E：⑧0；⑨1和3；⑩2；

13/18

14、（1）设是布尔代数，则L中的运算∧和∨A，运算∨的幺

元是B，零元是C，最小的子布尔代数是由集合D构成；

（2）在布尔代数L中的表达式

（a∧b）∨（a∧b∧c）∨（b∧c）

的等价式是E；

A：

①适合德.摩根律、幂等律、消去律和结合律；

②适合德.摩根律、幂等律、分配律和结合律；

③适合结合律、交换律、消去律和分配律；

B、C：④0；⑤1；

D：⑥｛1｝；⑦｛0，1｝；

E：

⑧b∧（a∨c）；⑨（a∧c）∨（a∧b′）；⑩（a∨b）∧（a∨b∨c）∧（b∨c）；

15、下列各集合对于整除关系都构成偏序集，判断哪些偏序集是格？

（1）L=｛1，2，3，4，5｝；

（2）L=｛1，2，3，6，12｝；

（3）L=｛1，2，3，4，6，9，12，18，36｝；

（4）L=｛1，2，22，…，2n｝；

16、设A=｛1，2，3，4，5｝，构成群，其中为集合的对称差。

（1）求解方程｛1，3｝X=｛3，4，5｝；

（2）令B=｛1，4，5｝，求由B生成的循环子群；

17、设A=｛1，2，5，10，11，22，55，110｝是110的正因子集，构成偏序集，

其中≤为整除关系。

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

（2）说明该偏序集是否构成布尔代数，为什么？

18、在图6-7所示的3个有界格中哪些元素有补元？如果有，请指出该元素的所有的补元。

P154

图论部分

1、（1）（3，3，2，3）、（5，2，3，1，4）能成为图的度数序列吗？为什么？

（2）已知图G有10条边，4个3度顶点，其余顶点的度数均小于等于2，问G中至少有多

少个顶点？为什么？

2、（1）画出4个顶点3条边的所有可能非同构的无向简单图；

（2）画出3个顶点3条边的所有可能非同构的有向简单图；

3、给定下列各图：

（1）G1=，其中，V1=（a，b，c，d，e），E1={（a，b），（b，c），（c，d），（a，

e）}；

（2）G2=，其中，V2=V1，E2={（a，b），（b，e），（e，b），（a，e），（d，e）}；

（3）G3=，其中，V3=V1，E3={（a，b），（b，e），（e，d），（c，c）}；

（4）G4=，其中，V4=V1，E4={，，，，，

}；

（5）G5=，其中，V5=V1，E5={，，，，}；

（6）G6=，其中，V6=V1，E6={，，，，}；

14/18

在以上6个图中，A为简单图，B为多重图。

A：①（1），（3），（6）；②（3），（4），（5）；

③（1），（2），（4）；④（1），（4）

B：①（2），（4），（5）；②（2），（5）；③（4），（5）

4、给定下列各顶点度数序列：

（1）（2，2，2，2，2）；

（2）（1，1，2，2，3）；

（3）（1，1，2，2，2）；

（4）（0，1，3，3，3）；

（5）（1，3，4，4，5）；

以上5组数中，A可以构成无向简单图的度数序列。

A：①（1），（3），（4）；②（1），（2）；③（1），（3）；④（3），（4），（5）；

5、完全图K4的所有非同构的生成子图中，0条边的有A个；1条边的有B个；

2条边的有C个；3条边的有D个；4条边的有E个；5条边的有F个；

6条边的有G个；

A、B、C、D、E、F、G：

①0；②1；③2；④3；⑤4；⑥5；

6、设G为9阶无向图，每个顶点的度数不是5就是6，证明：G中至少有5个6度顶点或

者至少6个5度顶点。

7、画出5阶7条边的所有非同构的无向简单图。

8、下列各组数中，哪些能构成无向图的度数列？哪些能构成无向简单图的度数列？

（1）1，1，1，2，3；

（2）2，2，2，2，2；

（3）3，3，3，3；

（4）1，2，3，4，5；

（5）1，3，3，3；

9、设有向简单图D的度数列为2，2，3，3，其中入度列为0，0，2，3，

出度列为。

10、设D是4阶有向简单图，度数列为3，3，3，3，它的入度列能为1，1，1，1吗？

（能或者不能）

11、下面各无向图中有几个顶点？

（1）16条边，每个顶点都是2度顶点；

（2）21条边，3个4度顶点，其余都是3度顶点；

（3）24条边，各顶点的度数是相同的；

12、一个n（n≥2）阶无向简单图G中，n为奇数，已知G中有r个奇数度顶点，问G的

补图G中有几个奇数度顶点？

13、画出K4的所有非同构的字图，其中有几个是生成子图？生成子图中有几个是连通图？

14、画出3阶有向完全图所有非同构的子图，问其中有几个是生成子图？生成子图中又有几

个是自补图？

15、设G1、G2、G3均为4阶无向简单图，它们均有两条边，它们能彼此均非同构吗？为

什么？

16、在K6的边上涂上红色或蓝色。证明对于任意一种随意的涂法，总存在红色K3或者蓝

色K3。

15/18

17、（1）非同构的无向的4阶自补图有A个；

（2）非同构的无向的5阶自补图有B个；

A、B：①0；②1；③2；④3；

18、给定有向带权图如图所示，P175

a

b

c

f

g

d

e

图中b到a的最短路径的权为A；b到d的最短路径的权为B；

b到e的最短路径的权为C；b到g的最短路径的权为D；

A、B、C、D：

①4；②5；③6；④7；⑤8；⑥9；⑦10；

19、某中学有3个课外小组：物理组、化学组、生物组。今有张、王、李、赵、陈5名同学。

若已知：

（1）张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员；

（2）张为物理组成员，王、李、赵为化学组成员，王、李、赵、陈为生物组成员；

（3）张为物理组和化学组成员，王、李、赵、陈为生物组成员；

问在以上3中情况下能否各选出3名不兼职的组长？

20、在图8-17所示的各图中，A为欧拉图，B为哈密顿图。

P185

A、B：

①（a），（b），（c）；②（d），（e），（f）；③（c），（e）；

④（b），（c），（d），（e），（f）；⑤（b），（c），（d），（e）；

21、在图8-18所示的各图中，是二部图的为A，在二部图中存在完美匹配的是B，

它的匹配数是C。

P186

A、B：

①（a）；②（b）；③（c）；④（d）；⑤（e）；⑥（f）；

⑦（a），（b）；⑧（b），（f）；⑨（c），（d），（e）；⑩（d），（e）；

C：①1；②2；③3；④4；

22、图8-19所示的平面嵌入中，面数为A，次数最高的面的次数为B，

次数最低的面的次数为C，总次数为D。

A、B、C：

①5；②6；③7；④8；⑤9；⑥10；⑦11；⑧1；

D：①24；②26；③28；

23、画出完全二部图K13，K24，K22。

24、完全二部图Krs中，边数为，匹配数1为。

16/18

25、今有工人甲、乙、丙去完成三项任务a、b、c。已知甲能胜任a、b、c三项任务；乙能

胜任a、b两项任务；丙能胜任b、c两项任务。你能给出一种安排方案，使每个工人各去完

成一项他们能胜任的任务吗？

26、画一个无向欧拉图，使它具有：

（1）偶数个顶点，偶数条边；

（2）奇数个顶点，奇数条边；

（3）偶数个顶点，奇数条边；

（4）奇数个顶点，偶数条边；

27、画一个无向图，使它是：

（1）是欧拉图，是哈密顿图；

（2）是欧拉图，不是哈密顿图；

（3）不是欧拉图，是哈密顿图；

（4）不是欧拉图，不是哈密顿图；

28、今有a、b、c、d、e、f、g7个人，已知如下事实：

a：会讲英语；

b：会讲英语和汉语；

c：会讲英语、意大利语和俄语；

d：会讲日语和汉语；

e：会讲德语和意大利语；

f：会讲法语、日语和俄语；

g：会讲法语和德语；

试问：这7个人要围成一圈，应如何排座位，才能使每个人都能和他身边（相邻）的人交谈？

29、彼得森图如图8-23所示。证明它不是二部图，也不是欧拉图，更不是平面图。

P189

30、证明图8-24所示图G是哈密顿图，但不是平面图。

P189

31、图8-25所示图G为平面图，试给出它的一个平面嵌入，它是极大平面图吗？

P189

32、（1）完全图Kn（n≥1）都是欧拉图，这个命题真值为A；

（2）完全图Kn（n≥1）都是哈密顿图，这个命题真值为B；

（3）完全二部图Knm（n≥1，m≥1）都是欧拉图，这个命题真值为C；

（4）完全二部图Knm（n≥1，m≥1）都是哈密顿图，这个命题真值为D；

A、B、C、D：①真；②假；

33、6个顶点11条边的所有可能的非同构的连通的简单的非平面图有A个，

其中有B个含子图K33，有C个含与K5同胚的子图。

A、B、C：

①1；②2；③3；④4；⑤5；⑥6；⑦7；⑧8；

34、图9-3所示的图G中，实线边所构成的子图是G的一颗生成树T，求T对应的基本回

路和基本回路系统，基本割集和基本割集系统

P193

35、（1）求带权为1、3、4、5、6的最优二元树；

（2）求带权为2、3、5、7、8、8的最优二元树；

36、计算非同构无向树的个数。

（1）2个顶点非同构无向树的有A颗；

17/18

（2）4个顶点非同构无向树的有B颗；

（3）6个顶点非同构无向树的有C颗；

（4）7个顶点非同构无向树的有D颗；

A、B、C、D：

①1；②2；③4；④6；⑤7；⑥8；⑦9；⑧10；⑨11；⑩12；

37、（1）在一棵树中有7片树叶，3个3度顶点，其余都是4度顶点，

则该树有A个4度顶点；

（2）在一棵树中有2个4度顶点，3个3度顶点，其余都是树叶，

则该树有B片树叶；

（3）一棵树中有ni个顶点的度数为i，i=2，3，…，k，而其余的顶点都是树叶，

则该树中有C片树叶。

A、B：

①1；②2；③3；④4；⑤5；⑥6；⑦7；⑧8；⑨9；⑩10；

C：

①



k

i

ni

2

；②





k

i

nii

3

；③





k

i

nii

3

)2(；④2)2(

3





k

i

nii；

38、图9-16给出两个带权图。

P200

（1）图（a）中最小生成树的权为A；

（2）图（b）中最小生成树的权为B；

①10；②14；③15；④21；⑤22；⑥24；⑦25；⑧26；⑨27；⑩28；

39、用Huffman算法求带权为2、3、5、7、8的最优二元树T。

（1）T的权为A；

（2）T中有B片树叶，C个2度顶点，D个3度顶点，E个4度顶点，

（3）T的高度为F。

A：①40；②45；③50；④55；⑤60；

B、C、D、E、F：

①0；②1；③2；④3；⑤4；⑥5；⑦6；⑧7；⑨8；

40、（1）求一个带权为1、2、3、4、5、5.5、7.5的最优三元树，其权为A；

（2）求一个带权为1.5、2.5、3、4、5、6的最优三元树，其权为B；

A、B：

①30；②35；③37；④45；⑤47；⑥48；⑦48.5；⑧50；⑨52；⑩55；

41、设无向树T有3个3度、2个2度顶点，其余顶点都是树叶，树叶顶点数为。

42、设无向树T有7片树叶，其余顶点的度数均为3，求T中3度顶点数？画出所有具有此

种度数的非同构的无向树。

45、画出度数列为1，1，1，1，2，2，4的所有非同构的7阶无向树。

46、在图9-20所示的无向图G中，实线边所示的子图为G的一棵生成树T，求G对应于T

的基本回路系统和基本割集系统。

P203

47、求图9-21所示两个带权图的最小生成树，并计算它们的权。

P203

48、计算非同构的根数的个数。

（1）2个顶点非同构的根数为A个；

18/18

（2）3个顶点非同构的根数为B个；

（3）4个顶点非同构的根数为C个；

（4）5个顶点非同构的根数为D个；

A、B、C、D：

①1；②2；③3；④4；⑤5；⑥6；⑦7；⑧8；⑨9；⑩10；