离散数学习题

第一章习题之答禄夫天创作

1.1判断下列语句是否为命题，若是命题请指出是简单命题还是

复合命题。

(1)6是无理数。

(2)5能被2整除。

(3)现在开会吗？

(4)x+5>0

(5)这朵花真是好看！

(6)2是素数当且仅当三角形有三条边。

(7)雪是黑色的当且仅当太阳是从东方升起。

(8)2000年10月1日天气晴好。

(9)太阳系以外的星球上有生物。

(10)小李在宿舍里。

(11)全体起立。

(12)4是2的倍数或是3的倍数。

(13)4是偶数且是奇数。

(14)李明和王华是同学。

(15)蓝色和黄色可以调配成绿色。

L.2将上题中的命题符号化，并讨论他们的真值。

1.3判断下列各命题的真值。

(1)若2+2=4,则3+3=6；

(2)若2+2=4,则3+36；

(3)若2+2#=4,则3+3=6；

(4)若2+20=4,则3+3工=6；

(5)2+2=4,当且仅当3+3=6；

(6)2+2=4,当且仅当3+3彳6；

(7)2+2,4,当且仅当3+3=6；

(8)2+2工4,当且仅当3+3,6；

1.4将下列命题符号化，并讨论其真值。

(1)如果今天是1号，则明天是2号；

(2)如果今天是1号，则明天是3号；

1.5将下列命题符号化。

(1)2是偶数不是素数；

(2)小王不单聪明而且用功；

(3)虽然天气冷。老王还是来了；

(4)他一边吃饭，一边看电视；

(5)如果天下大雨，他就乘公交汽车来；

(6)只有天下大雨，他才乘公交汽车来；

(7)除非天下大雨，否则他不乘公交汽车来；

(8)不经一事，不长一智；

1.5设p,q的真值为0,r,s的真值为1,求下列命题

公式的真值。

(1)Pv(qAr)；

(2)(p“r)△Jpvs);

(3)(pA(qvr)((pvq)A(rAs);

(4)「(Pv(q9以「p))).(r*s);

1.6设p：2+3=5o

q：大熊猫产在中国。

r：复旦大学在广州。

求下列复合命题的真值：

(1)(p—.q)-r

(2)(rf(pAq))^-|p

(3)~\rf(-|pVnqVr)

(4)(pAqAnr)—.((-|pV-|q—r)

1.7.用真值表判断下列公式的类型：方法不限。

(1)pf(pVqVr)

(2)(pf-|q)f-|q

(3)-|(qfr)Ar

(4)(pfq)f(~|qf-|p)

(5)(pAr)o-(npA-|q)

(6)((p-*q)A(q-*r))-*(p-*r)

(7)(pfq)—(r—s)

1.8用等值演算法证明下列等值式。

(1)(PAQ)A(PA^Q)=P；

⑵((p->q)A(P.r))o(p_>(qAr));

(3)「(p-q)o(q“)△[(P"))

1.9设A,B,C为任意的命题公式。

（1）已知AvC=BvC,问A=B吗？

⑵已知AACOB^C,问AoB吗?

⑶已知「Ao「B,问A=B吗？

。求下列命题公式的主析取范式，主合取范式，成真赋值，成假

赋值。

1.11通过求主析取范式判断下列各组命题公式是不是等值。

2有一探测队有3名队员，有一天取得一块矿样，3人的判断如

下：

甲说：这不是铁，也不是铜；

已说：这不是铁，是锡；

丙说：这不是锡，是铁；

经实验鉴定后发现，其中一人两个判断是正确的，一个人判断对

一半，一个人的判断全错了，根据以上的情况判断矿样的种类。

3判断下列的推理是不是正确，先将命题符号化，在写出前提和

结论，然后在进行判断。

(1)如果今天是1号，则明天是5号，今天是1号，所以明天是

5号。

(1)如果今天是1号，则明天是5号，明天是5号，所以今天是

1号。

(1)如果今天是1号，则明天是5号，明天不是5号，所以今天

不是1号。

(1)如果今天是1号，则明天是5号，今天不是1号，所以明天

不是5号。

4构造下面的推理的证明。

5如果他是理科学生，他必学好数学，如果他不是文科学生，他

必是理科学生，他没有学好数学，所以他不是文科学生。

判断上面的推理是不是正确，而且证明你的结论。

6给定命题公式如下；

上述公式的成真赋值A,成假赋值为B,公式的类型为C。

供选择的答案

:①无②全体赋值③010,100,101,111©010,100,

101,110,111

B:①无②全体赋值③000,001,011,④000,010,110

C:①重言式②矛盾式③可满足式

L17给定命题公式如下；

上述公式的主析取范式中含的极小项的个数为A,主合取范式含

的极大项的个数为B,成真值的赋值为C

供选择的答案

A①2②3③5④0⑤8

B①0②8③5④3

C①000,001,H0;②001,011,101,HO,111;③全体赋值④无

L18给定下列三组前提。

上述前提中，(1)的逻辑结论(有效结论)为A,(2)的逻辑

结论为B,(3)的逻辑结论C。

供选择的答案

A,B,C:①r②q③-1P④s⑤-1P丫->4⑥p.$⑦〃八"

1.19设计一个符合下列要求的室类照明控制的线路，在房间的门

外、门类及其床头分别装一个可以控制同一个电灯F的3个开关

A,B,C,当且仅当一个开关的搬键向上或3个开关的搬键都向上

时候电灯亮，则F的逻辑关系式可以化简为A

供选择的答案

A：®AVBVC@AVBVCV(AABAC)

.某电路中有一个灯泡和三个开关A,B,C。已知在且仅在下述四

种情况下灯亮：

(1)C的扳键向上，A,B的扳键向下。

(2)A的扳键向上，B,C的扳键向下。

(3)B,C的扳键向上，A的扳键向下。

(4)A,B的扳键向上，C的扳键向下。

设F为1暗示灯亮，p,q,r分别暗示A,B,C的扳键向上。

(a)求F的主析取范式。

(b)在联结词完备集人，八｝上构造F.

(c)在联结词完备集｛--i，一，一)上构造F.

.一个排队线路，输入为A,B,C,其输出分别为FA,FB,CF。本线路

中，在同一时间内只能有一个信号通过，若同时有两个和两个以

上信号申请输出时，则按A,B,C的顺序输出。写出FA,FB,CF在联

结词完备集｛I，V｝中的表达式。

第二章习题

在一阶逻辑中将下列命题符号化.

(1)鸟都会飞翔.

(2)其实不是所有人都爱吃糖.

(3)有人爱看小说.

(4)没有不爱看电影的人.

(a)自然数集合N(N中含0).

(b)整数集合Z.

(c)实数集合R.

(1)对于任意的X,均由G+l>=X2+2X+1

(2)存在x,使得x+2=0.

(3)存在x,使得5x=L

2.3在一阶逻辑中将下列命题符号化.

(1)每个大学生不是文科生就是理科生.

(2)有些人喜欢所有的花.

(3)没有不犯错误的人.

(4)在北京工作的人未必就是北京人.

(5)任何金属都可以溶解在某种液体中.

(6)凡对顶角都相等.

在一阶逻辑中将下面命题符号化，并分别讨论个体域限制为

(a),(b)时命题的真值：

(1)对于任意的X,均有x2~2=(x+我)(X-0)。

(2)存在x,使得x+5=9。

其中(a)个体域为自然数集合，(b)个体域为实数集合。

2.5将下列各式翻译成自然语言，然后再分歧领域中却定它们的

真值.

个体域分别为

(a)实数集合

⑹整数集合

(c)正整数集合

(d)(非。实数集合)

设个体域D={a,b,c},消去下列各式的量词：

(1)Vx3y(F(x)AG(y))

(2)VxVy(F(x)VG(y))

(3)VxF(x)-*VyG(y)

(4)Vx(F(x,y)-*3yG(y))

2.7.设个体域。={1,2},请给出两种分歧的解释［和I2,使得下

面公式在L下都是真命题，而在I?下都是假命题。

(1)VX(F(x)-*G(x))

(2)3x(F(x)AG(x).给定解释I如下：

(a)个体域D={3,4}°

(b),(x)为，(3)=4,1(4)=3。

(c)声(x,y)为声(3,3)=声(4,4)=0,弄(3,4)=弄(4,3)=1。

试求下列公式在I下的真值：

(1)Vx3yF(x,y)

(2)3xVyF(x,y)

(3)VxVy(F(x,y)-F(f(x),f(y)).在自然推理系统F中构

造下面推理的证明：

(1)前提：Vx(F(x)-*(G(a)AR(x))),3xF(x)

结论：3x(F(x)AR(x))

(2)前提：Vx(F(x)VG(x)),3xG(x)

结论：3xF(x)

(3)前提:Vx(F(x)VG(x)),Vx(-|G(x)V-iR(x)),VxR(x)

结论：VxF(x).在自然推理系统F中，证明下面推

理：

(1)每个有理数都是实数，有的有理数是整数，因此有的实

数是整数。

(2)有理数、无理数都是实数，虚数不是实数，因此虚数既

不是有理数、也不是无理数。

(3)不存在能暗示成分数的无理数，有理数都能暗示成分

数，因此有理数都不是无理数。

2.11(1)试给出解释，使得

在下具有分歧的真值

(2)试给出解释，使得

在下具有分歧的真值

给出解释，使下面的两个公式在解释下面为假，从而说明这两个

公式都不是逻辑有效式(用真式)

2.13设个体域,在口={a,b,c}

下D验证量词否定等值式

设个体域，在口={a,b,c}，消去下列公式中的量词。

(1)VxF(x)—>3yG(y)

(2)Vx(F(x)A3yG(y))

(3)3yVxH(x,y)

2.16求下列各式的前束范式，要求使用自由变换换名规则。

2.17构造下面推理的证明

(1)前提;3XF(X)TVy((F(y)vG(y))fR(y))

结论：3xF(x)

(3)前提：Vx(F(x)(G(y)A/?(%))),3xF(x)

结论：3x(F(x)AR(x))

2.18取个体域为整数集，给定下列各公式

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

供选择的答案

A:①(1),⑶，⑷，⑹②⑶，⑷，⑸③(1),(3),(4),(5)④

(3),(4),(6),(7)

B:①(2),⑶，⑹②(2),⑹，⑻③⑴，(2),(6),⑺④

⑵,(6),(8),(7)

在一阶逻辑中构造下面的推理证明

每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或

自行车，有的人不喜欢自行车，所以有的人不喜欢步行。

命题符号化：F(x):x喜欢步行,G(x):x喜欢坐汽车,H(x):x

喜欢自行车.

在上述推理中，(2)后用的推理规则为A,(4)后面用的推理

规则为B,(5)用的推理规则是(2)(4)所得到的推理规则C,

(8)用的推理规则是(5)和(7)得到的推理规则D

供选择的答案

A,B,C,D①UI,②EI,③UG,④EG,⑤拒取式⑥假言推理⑦析

取三段论

第三章习题集合与二元关系

3.1.选择适当的谓词暗示下列集合：

(1)小于5的非负整数

(2)奇整数集合

(3)10的整倍数的集合

2.用列元素法暗示下列集合：

(l)S]={x|x是十进制的数字}

(2)$2={x|x=2Vx=5}

(3)$3={x|x=x£ZA3〈x〈12}

(4)S={x|x£RAx2—1=0Ax>3}

4

(5)S={<x,y>|x,y£Z/\0WxW2ATWyWO}

5

3.2.设F暗示一年级大学生的集合，S暗示二年级大学生的集

合，M暗示数学专业学生的集合，R暗示计算机专业学生的集合，

T暗示听离散数学课学生的集合，G暗示星期一晚上介入音乐会的

学生的集合，H暗示星期一晚上很迟才睡觉的学生的集合。问下

列各句子所对应的集合表达式分别是什么？请从备选的答案中挑

出来。

(1)所有计算机专业二年级的学生在学离散数学课。

(2)这些且只有这些学离散数学课的学生或者星期一晚上去听音

乐会的学生在星期一晚上很迟才睡觉。

(3)听离散数学课的学生都没介入星期一晚上的音乐会。

(4)这个音乐会只有大学一、二年级的学生介入。

⑸除去数学专业和计算机专业以外的二年级学生都去介入了音

乐会。

备选答案：

①TWGUH②GUHUT③SARqT

@H=GUT⑤TGG=0⑥FUSqG

©G^FUS⑧S-(RLJMEG⑨GuS-(RDM)

.确定下列命题是否为真：

(1)0^0(2)0e0(3)0c{0)

(4)0e{0}

(5){a,b}c{a,b,c,{a,b,c}}

(6){a,b}£{a,b,c,{a,b}}

(7){a,b}c{a,b,{{a,b}}}

(8){a,b}W{a,b,{{a,b}}}

已知A={0,{⑶},求AXP(A)。

对于任意集合A,B,C,若AXBGAXC,是否一定有BMC成立？为

什么？

.设A,B,C,D是任意集合，

(1)求证(AAB)X(CAD)=(AXC)n(BXD)o

(2)下列等式中哪个成立？那些不成立?对于成立的给出证明，

对于不成立的举一反例。

(AUB)X(CUD)=(AXC)U(BXD)

(A-B)X(C-D)=(AXC)-(BXD)

.设A,B为任意集合，证明

若AXA=BXB,则A=Bo

列出从集合A={1,2}到8={1}的所有的二元关系。

列出集合人={2,3,4}上的恒等关系I,全域关系E,小于或等

AA

于关系L,整除关系D。

AA

.列出集合A={0,{0},{0,{0}},{0,{0},{0,{0}}}}

上的包含关系。

.设A={L2,4,6),列出下列关系R:

(l)R={<x,y>|x,y£A八x+yW2}

(2)R={〈x,y>|x,y£A/\|x-y1=1}

(3)R={<x,y>|x,yCAAx/yGA)

⑷R={<x,y>|x,yWAAy为素数}

.R是X上的二元关系，对于x£X定义集合

i

R(x)={y|xRy}o

ii

显然Ri(x)qX。如果X={-4,-3,-2,-1,0,1,2,3,4},且

令

R={<x,y>|x,yGXAx<y}

Rj{〈x,y>|x,yGXAy-l<x<y+2}

R={<x,y>|x,yGXAx2^y}

求R(0),R(1),R(0),R(-1),R(3)o

11223

.设A={0,1,2,3),R是A上的关系，且

R={<0,0>,<0,3>,<2,0>,<2,1>,<2,3>,<3,2>}

给出R的关系矩阵和关系图。

.设

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

B=<2,4>,<4,2>}

求AUB,AGB,domA,dom(AUB),ranA,ranB,ran(AClB),fid(A-

B).设

R={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>,<2,3>}求R°R,R

i,Rr{0,l},R[{l,2}]o

设

A={<0,{0}{0}}>,<{0},0»

求AT,A2,A3,A「{0},A[0],A「0,A「{{。}},A[{{0}}]。

设人=匕为",(1},R,R为A上的关系，其中

12

R={<a,a>,<a,b>,<b,d>}

R={<a,d>,<b,c>,<b,d>,<c,b>}

2

求RoR,RoR,R2,R3O

122112

.设八=匕,1),~,试给出A上两个分歧的关系R和R,使得R2=R,

1211

R3=R.证明定理7.4的⑴,(2),(4)o

22

.证明定理7.5的(2),(3)o

设R和R为A上的关系，证明：

12

(1)(RUR)i=R-lUR-i(2)(RDR)-i=RiCiR-i

12121212

第四章习题代数系统

4.1、列出以下运算的运算表：

(1)A={1,2,1},VxeA,ox是x的倒数，即ox=W.

(2)A={1,2,3,4},Vx,yGA有xoy=max(x,y),max(x,y)是x和y

之中较大的数。

4.2、判断下列集合对所给的二元运算是否封闭：

(1)整数集合Z和普通的减法运算

(2)非零整数集合Z*和普通的除法运算

(3)全体nXn实矩阵集合Mn(R)和矩阵加法及乘法运算，其中

心2

(4)全体nXn实可逆矩阵集合关于矩阵加法和乘法运算，其中

心2

(5)正实数集合R，和。运算，其中。运算定义为：

Va,beR>,aob=ab-a-b

(6)n£Z+,nZ={nz|zez).nZ关于普通的加法和乘法运算。

(7)A=n，2.。运算定义如下：Va,a£A,aoa^a.

(8)S={2x-l|xez+)关于普通的加法和乘法运算。

(9)S={O,1},S关于普通的加法和乘法运算。

(10)S={x|x=2n,n£Z+},S关于普通的加法和乘法运算

4.3、对于上题中封闭的二元运算判断是否适合交换律、结合律和

分配律。

4.4、对习题2中封闭的二元运算找出它的单位元，零元和所有可

逆元素的逆元。

、S=QXQ,Q为有理数集，*为5上的二元运算，V<a,b>,<x,y>eS

有

<a,b>*〈x,y>=<ax,ay+b>(1)*运算在S上是否

可交换，可结合？是否为幕等的？

(2)*运算是否有单位元，零元？如果有，请指出，并求S中所

有可逆元素的逆元。

4.6、R为实数集，定义以下六个函数f.^x,yeR有

16

f«x,y»=x+y,f«x,y»=x-y,

f3«x,y»=x•y,f।(<x,y»=max(x,y),

f5«X,y»=min(x,y),6f«x,y»=|x-y|

(1)指出哪些函数是R上的二元运算。

(2)对所有R上的二元运算说明是否为可交换、可结合、幕等

的。

(3)求所有R上二元运算的单位元、零元以及每一个可逆元素

的逆元。

4.7、令5=匕,动，上有四个二元运算：*,。，•和□，分别由表

10.8确定。

表10.8

(1)这四个运算中哪些运算满足交换律、结合律、累等律

(2)求每个运算的单位元、零元及所有可逆元素的逆元。

4.8、设S={1,2,10},问下面定义的运算能否与S构成代数系

统〈S,*〉?如果能构成代数系统则说明*运算是否满足交换律、结合

律，并求*运算的单位元和零元。

(1)x*y=gcd(x,y),gcd(x,y)是x与y的最大公约数。

(2)x*y=lcm(x,y),1cm(x,y)是x与y的最小公倍数。

(3)乂*丫=大于等于x和y的最小整数。

(4)x*y=质数p的个数，其中xWpWy.

4.9、下面各集合都是N的子集，它们能否构成代数系统V=<N,+>

的子代数：

(1){xlxENAx可以被16整除}

(2){xlxWNAx与8互质}

(3){xlxWNAx是40的因子}

(4){x|xWNAx是30的倍数}

4.10、设V=〈Z,+,->,其中+和•分别代表普通加法和乘法，对

下面给定的每个集合确定它是否构成V的子代数，为什么？

(1)S={2nn£Z}

1

(2)S={2n+l|n《Z}

2

(3)S={—1,0,1)

3

4.11、设VJ<{1,2,3},。，1>,其中x°y暗示取x和y之中较大的

数。V=<{5,6},*,6〉,其中x*y暗示取x和y之中较小的数。求出

2

V和V的所有子代数。指出哪些是平凡子代数，哪些是真子代

12

数。

第五章几个典型的代数系统

5.1.设A={0,l},试给出半群<AA,。>的运算表,其中。为函数的复

合运算。

5.2.设G={a+bi|a,b£Z},i为虚数单位，即i2=T.验证G关于复

数加法构成群。

5.3.设Z为整数集合,在Z上定义二元运算。如下：

Vx,yeZ,xoy=x+y-2

问Z关于。运算能否构成群？为什么？

5.4.设A={x设£RAX#0,1}.在A上定义六个函数如下：

f(x)=x,f(X)=XT,f(x)=『x,

123

f(x)=(l-x)-l,f(x)=(x-l)x1,f(x)=x(x-

456

1)T

令F为这六个函数构成的集合，。运算为函数的复合运算。

(1)给出。运算的运算表。

(2)验证〈F,。＞是一个群。

5.5.设6为群,且存在2£6,使得G={ak|k£Z},证明G是交换

群。

5.6.证明群中运算满足消去律.

5.7.设G为群,若YxeG有X2=e,证明G为交换群。

5.8.设G为群,证明e为G中唯一的幕等元。

5.9.证明4阶群必含2阶元。

设A={a+bi|a,beZ,i2=-1},证明A关于复数的加法和乘法构成

环，称为高斯整数环。

.(1)设R,R是环，证明R与R的直积RXR也是环。

I21212

(2)若R和R为交换环和含幺环,证明RXR也是交换环和

1212

含幺环。

.判断下列集合和给定运算是否构成环、整环和域，如果不克不

及构成，说明理由。

(1)A={a+bi|a,b£Z},其中i2=T,运算为复数的加法和乘

法。

(2)A={T,0,1},运算为普通加法和乘法。

(3)A=M(Z),2阶整数矩阵的集合，运算为矩阵加法和乘

2

法。

(4)A是非零有理数集合Q*,运算为普通加法和乘法。5.14.

设G是非阿贝尔群，证明G中存在元素a和b,aWb,且ab=ba.

5.15.设II是群G的子群,x£G,令

xllxi={xhx-i|heH),

证明XHXT是G的子群,称为H的共班子群。

5.16.设

.腓3(；凯")}

(1)G上的二元运算

为矩阵乘法，给出G的运算表

(2)试找出G的所有子群

(3)证明G的所有子群都是正规子群。

5.17.设G是有限群，K是G的子群，H是K的子群，证明

5.18.令G={Z,+}是整数加群。求商群Z/4Z,Z/12Z和4Z/12Z.

5.19.对以下各小题给定的群G和G以及f:G-G,说明f是否

1212

为群G到G的同态。如果是,说明G是否为单同态,满同态和同

12

构，并求同态像f(G)和同态核kerf.

1

(1)G=<Z,+>,G=<R*,・>，其中G为非零实数的集合，+

12

和•分别暗示数的加法和乘法。

’1淀偶数

f:ZfR*,f(x)=「1造奇数⑵

G=<Z,+>,G=<A,・>,其中+和・分别暗示数的加法和乘法

12

A={x|xWCA|x|=l},其中C为复数集合。

f:Z-*A,f(x)=cosx+isinx

(3)G=<R,+>,G=<A,->,+和•以及A的定义同(2).

12

f:RfA,f(x)=cosx+isinx

5.20.设f是群G到G的同构，证明f-是G到G的同构。

1221

.图中给出六个偏序集的哈斯图。判断其中哪些是格。如果不是格,

说明理由。

.下列各集合对于整除关系都构

成偏序集,判断哪些偏序集是格。

(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,,2],n£Z+3.(1)画出

Klein四元群的子群格。

(2)画出模12的整数群Z的子群格。

12

(3)画出3元对称群S的子群格。

3

4.设L是格,求以下公式的对偶式：

(l)aA(aVb)《a

(2)aV(bAc)《(aVb)A(aVc)

(3)bV(cAa)=<(bVc)Aa5.设L是格,a,b,c£L,且

b《c,证明

aVb=bAc

,L和1,求出他们的所有子格。

123

d

di

.4

也

LiLaL3

图13.10

7.针对图13.9中的每个格,如果格中的元素存在补元,则求出这些

补元。

8.说明图13.9中的每个格是否为分配格、有补格和布尔格,并说

明理由。

9.对以下各小题给定的集合和运算判断它们是哪一类代数系统(半

群,独异点,群,环,域,格,布尔代数)，并说明理由。

(l)S={0,1,-1),运算为普通加法和乘法。

(2)S={a,a,...,a},Va,aeS,a*a=a.这里的n是给定的

212nij2iji

正整数，且n22.

(3)S={0,1},*为普通乘法。

3

(4)S={1,2,5,7,10,14,35,70},。和*分别暗示求最小公倍数

4

和最大公约数运算。

(5)S={0,1,2},*为模3加法，。为模3乘法。

5

.设B是布尔代数,B中的表达式f是

(aAb)V(aAbAc)V(bAc)

(1)化简f.

⑵求f的对偶式f*o

.设＜B,八，VJ,0,1＞是布尔代数，在B中化简以下表达式：上定

义二元运算*,Va,bGB,

(1)(aAb)V(aAb,)V(azVb)

(2)(aAb)V(aA(bAc)')Vc2.对于

n=l,...,5,给出所有分歧构的n元格,并说明哪些是分配格、有补

格和布尔格。

3.设＜B,A,V,',0,1＞是布尔代数,在B上定义二元运算㊉，Vx,y

6B有

x㊉y=(x/\『)V(x'Ay)

问＜B,㊉〉能否构成代数系统？如果能，指出是哪一种代数系统。为

什么？

5.34.设G为循环群,f是群G到G的同态，证明f(G)也是循环

1121

群。

5.35.设G=〈a＞是15阶循环群。

(1)求出G的所有的生成元。

(2)求出G的所有子群。

5.36.设o,T是5元置换,且

fl2345^|fl2345^)

1453),，力4512)(1)计算

OT,TO,O-1,T-1,O-1TG

(2)将。T,T-1,O-1TO表成不交的轮换之积。

(3)将(2)中的置换暗示成对换之积,并说明哪些为奇置换，

哪些为偶置换。

5.37设A={1,2,5,10,11,22,55,110)是110的正因子集，〈A,

W〉构成的偏序集，其中W为整除关系。

(1)画出偏序集〈A,W〉的哈斯图。

(2)说明该偏序集是不是构成布尔代数，为什么？

第六章习题图论基础

6.1下列各组数中，那些能构成无向图的度数列？那些能构成无向简

单图的度数列？

(2)2,2,2,2,2

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

(4)1,3,3,3

6.2设有向简单图D的度数为2,2,3,3,入度列0,0,2,3,

试求D的除度列。

6.3设是4阶有向简单图，度数列为3,3,3,3.它的入度列9或

出度列)能为1,1,1,1吗？

6.4设()为一正整数序列，互不相同，问此序列

能构成n阶无向图的度数列吗？为什么？

6.5下面无向图中有几个顶点？

(1)16条边，每个顶点都是2度顶点.

(2)21条边，3个4度顶点，其余的都是3度顶点.

(3)24条边，各顶点的度数是相同的.

6.635条边，每个顶点的度数至少为3的图最多有几个顶点？

6.7设n阶无向简单图中，(G)=n-1,问(G)应为多少？

6.8一个n(n2)阶无向简单图G中，n为奇数，已知G中有r各奇度顶

点，问G的补图中有几个奇度顶点？

6.9设D是n阶有向简单图，是D的子图，已知的边数=n(n-

1),问D的边数m为多少？

6.10画出-----的所有非同构的子图，其中有几个是子图？生成子图中有

几个是连通图？

6.11设G为n阶简单图(无向图或有向图)，为G的补图，若G-----

一,则称G为自补图，一一的生成子图中有几个非同构的自补图？

.设无向图G有10条边，3度与4度顶点各2个，其余顶点的度

数均小于3,问G中至少有几个顶点？在最少顶点的情况下，写

出G的度数列、A⑹、8(G).

.设n阶图G中有m条边，证明：5(G)W2m/nWA(G).

•设无向图中有6条边，3度与5度顶点各一个，其余的都是2

度顶点，问该图有几个顶点？

.证明空间中不成能存在有奇数个面且每个面都有奇数条棱的多

面体。

•阶2-正则图有几种非同构的情况？

.设n阶无向图为3-正则图，且边数m与n满足2n-3=m,问这样的无向图有

几种非同构的情况？6.18画出3阶有完全图所有非同构的子图，问其中有几

个是生成子图？生成子图中有几个是自补图？

6.19设-------均为4阶无向简单图，他们均由两条边，他们能彼此均非同

构吗？为什莫？

6.20已知n阶无向图G中有m条边，各顶点的度数均为3,又已知2n—3

=m,问在同构的意义下，G是唯一的吗？又若G为简单时，是否唯一？

6.22在一一的边上涂上红色或蓝色，证明对于任意一种随意的涂法，总存在

红色---或蓝色----？

6.23试寻找3个4阶有向简单图-----，使得一一强连通图；一一为单向连

通图，但不是强连通图；而一一是弱连通图，但不是单向连通图，当然，更不

是强连通图.

------的连通图分支个数k一定为几？G-------1连通分支数也是定数吗？

6.25有向图D如图7.19所示.求D中长度为4的通路总数，并指出其中有多

少条是回路？又有几条是--一至卜一的通路？

.现有3个4阶4条边的无向简单图G,G,G,证明它们中至少有

123

两个是同构的。

.设G是n阶自补图，证明n=4k或n=4k+l,其中k为正整数。

.设G是n阶无向简单图，n》3且为奇数，证明G与停中奇度顶

点的个数相等。

.已知在完全二部图K中，rWs.

r,s

(DK中含有多少种非同构的圈？

r,s

(2)K中至多有多少个顶点彼此不相邻？

r,s

(3)K中至多有多少条边彼此不相邻？

r,s

(4)K的点连通度K为几？边连通度人为几？

r,s

第七章习题欧拉图

7.1画出完全2部图--------------------.

7.2