离散数学题库

试题总汇

数理逻辑部分

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、D 4人百米竞赛。观众甲、乙、丙预报比赛的名次为,

(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)前提: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)午夜时屋里灯光灭了

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

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吗?

(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)?x F(x)∧G(x,y)

(3)?x?y(R(x,y)∨L(x,y))∧?x H(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?y L(x,y)

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

(1)?xF(x)∧??x G(x)

(2)?xF(x)∨??x G(x)

(3)?xF(x)→?x G(x)

(4)?xF(x)→?x G(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))

(4)?x(F(x)∧?G(x))

正确的答案是。

26、给出解释I,使下面两个公式在解释I下均为假,从而说明这两个公式都不是永真式(1)?x(F(x)∨G(x))→(?xF(x)∨?x G(x))

(2)(?xF(x)∧?x G(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

(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

?S3但X?S1,则E

(5)若X

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}

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

R2={|x,y∈X∧y -1< x< y +2},

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:

⑧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 )= -x 2+2x-1; ②f :R →Z +,f (x )=lnx ;

③f :R →Z ,f (x )=??x ,??x 表示不大于x 的最大整数; ④f :R →R ,f (x )=2 x+1;

⑤f :R +

→R +

,f (x )=x

x 1

2+

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)设有序对< x+2,4 > 与有序对<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 上的关系,其关系矩阵是

?

?

???

???????0001100000011001, 则(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 )的关系图。

离散数学题库

a b c d

e

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 )和B A ;

(2)构造一个从P (A )到B A 的双射函数。

代数系统部分

1、设Z +={x |x ∈Z ∧x>0},*表示求两个数的最小公倍数的运算,则 (1)4*6=A ; (2)*在Z +上B ;

(3)对于*运算的幺元是C ,零元是D ; (4)在Z +中E ; A :①24;②12;

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给出。

a b c d

a a

b

c d

b b b d d

c c

d c d

d d d d d

表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 个;

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,其运算表如下:

a b a b

a a a a a b

b a a b b a

f1f2

a b a b

a b a a a b

b a a b a b

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

yi

xi,那么当x≠y时,H(x,y)≥B 。

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

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

(5)如果接收到1000011,且知有一位出错,那么出错位是第E 位。

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;

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={};

在以上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。 17、(1)非同构的无向的4阶自补图有A 个; (2)非同构的无向的5阶自补图有B 个; A 、B :①0;②1;③2;④3;

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

离散数学题库

离散数学题库

离散数学题库

离散数学题库

离散数学题库

离散数学题库

g

d

图中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为 。

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 颗;

(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 ni i 3

;③∑=*-k i ni i 3

)2(;④2)2(3

+*-∑=k

i ni i ;

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 个;

(2)3个顶点非同构的根数为B 个;

(3)4个顶点非同构的根数为C 个;

(4)5个顶点非同构的根数为D 个;

A、B、C、D:

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

相关推荐