离散数学第四版答案.docx

资源描述

离散数学第四版答案.docx

《离散数学第四版答案.docx》由会员分享，可在线阅读，更多相关《离散数学第四版答案.docx（20页珍藏版）》请在冰点文库上搜索。

离散数学第四版答案.docx

离散数学第四版答案

【篇一：

离散数学课后习题答案第四章】

xt>4．判断下列集合对所给的二元运算是否封闭：

（1）整数集合z和普通的减法运算。

封闭,不满足交换律和结合律，无零元和单位元

（2）非零整数集合普通的除法运算。

不封闭

（r）和矩阵加法及乘法运算，其中n2。

（3）全体n?

n实矩阵集合

封闭均满足交换律，结合律，乘法对加法满足分配律；

加法单位元是零矩阵，无零元；

乘法单位元是单位矩阵，零元是零矩阵；

（4）全体n?

n实可逆矩阵集合关于矩阵加法及乘法运算，其中n2。

不封闭

（5）正实数集合和运算，其中运算定义为：

不封闭因为1?

（6）

n关于普通的加法和乘法运算。

封闭，均满足交换律，结合律，乘法对加法满足分配律

加法单位元是0，无零元；

乘法无单位元（n?

1），零元是0；n?

1单位元是1

（7）a={a1,a2,?

an}n运算定义如下：

封闭不满足交换律，满足结合律，

（8）s=关于普通的加法和乘法运算。

封闭均满足交换律，结合律，乘法对加法满足分配律

（9）s={0,1},s是关于普通的加法和乘法运算。

加法不封闭，乘法封闭；乘法满足交换律，结合律

（10）

s=,s关于普通的加法和乘法运算。

加法不封闭，乘法封闭，乘法满足交换律，结合律

5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。

见上题

7．设*为z?

上的二元运算?

x,y?

，

x*y=min（x，y）,即x和y之中较小的数.

（1）求4*6，7*3。

4,3

（2）*在z上是否适合交换律，结合律，和幂等律？

满足交换律，结合律，和幂等律

（3）求*运算的单位元，零元及z?

中所有可逆元素的逆元。

单位元无，零元1,所有元素无逆元

8．s?

qq为有理数集，*为s上的二元运算，a,b,x,ys有

a，b*x，y=ax，ay+b

（1）*运算在s上是否可交换，可结合？

是否为幂等的？

不可交换：

x,y*a,b=xa，xb+y?

a，b*x，y

可结合：

（a,b*x,y）*c,d=ax，ay+b*c,d=axc，axd+（ay+b）

a,b*（x,y*c,d）=a,b*xc,xd+y=axc，a（xd+y）+b

（a,b*x,y）*c,d=a,b*（x,y*c,d）

不是幂等的

（2）*运算是否有单位元，零元？

如果有请指出，并求s中所有可逆元素的逆元。

设a,b是单位元，x,ys，a,b*x,y=x,y*a,b=x,y

则ax,ay+b=xa,xb+y=x,y，解的a,b=1,0，即为单位。

设a,b是零元，x,ys，a,b*x,y=x,y*a,b=a,b

则ax,ay+b=xa,xb+y=a,b，无解。

即无零元。

x,ys，设a,b是它的逆元a,b*x,y=x,y*a,b=1,0

ax,ay+b=xa,xb+y=1,0

a=1/x,b=-y/x

所以当x?

0时，?

x,y?

1y,?

xx?

10．令s={a，b}，s上有四个运算：

*，

分别有表10.8确定。

（a）（b）（c）（d）

（1）这4个运算中哪些运算满足交换律，结合律，幂等律？

（a）交换律，结合律，幂等律都满足，零元为a,没有单位元；

（b）满足交换律和结合律，不满足幂等律，单位元为a,没有零元

a,b?

（c）满足交换律,不满足幂等律,不满足结合律

（b?

b）?

（b?

b）?

（a?

b）?

没有单位元,没有零元

（d）不满足交换律，满足结合律和幂等律

没有单位元,没有零元

（2）求每个运算的单位元，零元以及每一个可逆元素的逆元。

见上

（a?

b）?

16．设v=〈n，+，〉，其中+，分别代表普通加法与乘法，对下面给定的每个集合确定它是否构成v的子代数，为什么？

（1）s1=

（2）s2=是不是加法不封闭

（3）s3={-1，0，1}不是，加法不封闭

第十一章部分课后习题参考答案

8.设s={0，1，2，3}，为模4乘法，即

y=（xy）mod4?

x,y∈s,x

问〈s，〉是否构成群？

为什么？

y=（xy）mod4?

s,是s上的代数运算。

解：

（1）?

x,y∈s,x

（2）?

x,y,z∈s,设xy=4k+r0?

3（xy）z=（（xy）mod4）z=rz=（rz）mod4

=（4kz+rz）mod4=（（4k+r）z）mod4=（xyz）mod4

同理x（yz）=（xyz）mod4

y）z=x1）=（1（yz），结合律成立。

所以，（x（3）?

x∈s,（xx）=x,，所以1是单位元。

（4）1?

1,3?

3,0和2没有逆元

所以，〈s，

9.设z为整数集合，在z上定义二元运算。

如下：

x,y∈z,xoy=x+y-2

问z关于o运算能否构成群？

为什么？

〉不构成群

解：

（1）?

x,y∈z,xoy=x+y-2?

z,o是z上的代数运算。

（2）?

x,y,z∈z,

（xoy）oz=（x+y-2）oz=（x+y-2）+z-2=x+y+z-4

同理（xoy）oz=xo（yoz），结合律成立。

（3）设e是单位元，?

x∈z,xoe=eox=x,即x+e-2=e+x-2=x,e=2

（4）?

x∈z,设x的逆元是y,xoy=yox=e,即x+y-2=y+x-2=2,

所以，x?

所以〈z，o〉构成群

10?

11.设g=?

01?

10?

01?

，证明g关于矩阵乘法构成一个群．

解：

（1）?

x,y∈g,易知xy∈g,乘法是z上的代数运算。

（2）矩阵乘法满足结合律

10?

（3）设?

01?

是单位元，

（4）每个矩阵的逆元都是自己。

所以g关于矩阵乘法构成一个群．

14.设g为群，且存在a∈g,使得

g={ak∣k∈z}

证明：

g是交换群。

证明:

x,y∈g，设x?

ak,y?

al，则

xy?

akal?

ak?

al?

alak?

所以，g是交换群

17.设g为群，证明e为g中唯一的幂等元。

22证明:

设e0?

g也是幂等元，则e0?

e0，即e0?

e0e，由消去律知e0?

18.设g为群，a,b,c∈g,证明

∣abc∣=∣bca∣=∣cab∣

证明：

先证设（abc）k?

（bca）k?

设（abc）k?

e,则（abc）（abc）（abc）?

（abc）?

e，

即a（bc）（abc）（abc）?

a（bc）aa?

左边同乘a?

1，右边同乘a得

（bca）（bca）（bca）?

（bca）?

（bac）k?

1ea?

反过来，设（bac）k?

e,则（abc）k?

由元素阶的定义知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣

19.证明：

偶数阶群g必含2阶元。

证明：

设群g不含2阶元，?

g，当a?

e时，a是一阶元，当a?

e时，a至少是3阶元,因为群g时有限阶的，所以a是有限阶的，设a是k阶的,则a?

1也是k阶的，所以高于3阶的元成对出现的，g不含2阶元，g含唯一的1阶元e,这与群g是偶数阶的矛盾。

所以，偶数阶群g必含2阶元

20.设g为非abel群，证明g中存在非单位元a和b,a≠b,且ab=ba.

证明：

先证明g含至少含3阶元。

若g只含1阶元,则g={e},g为abel群矛盾；

若g除了1阶元e外,其余元a均为2阶元，则a2?

e，a?

a,b?

g,a?

a,b?

b,（ab）?

ab,所以ab?

1b?

（ba）?

ba，

与g为abel群矛盾；

所以，g含至少含一个3阶元，设为a，则a?

a2，且a2a?

aa2。

令b?

a2的证。

21.设g是mn（r）上的加法群，n≥2，判断下述子集是否构成子群。

（1）全体对称矩阵是子群

（2）全体对角矩阵是子群

（3）全体行列式大于等于0的矩阵.不是子群

（4）全体上（下）三角矩阵。

是子群

22.设g为群，a是g中给定元素，a的正规化子n（a）表示g中与a可交换的元素构成的集合，即n（a）={x∣x∈g∧xa=ax}

证明n（a）构成g的子群。

证明：

ea=ae,e?

n（a）?

x,y?

n（a）,则ax?

xa,ay?

a（xy）?

（ax）y?

（xa）y?

x（ay）?

x（ya）?

（xy）a,所以xy?

n（a）

由ax?

xa，得x?

1axx?

1xax?

1,x?

1ae?

eax?

1，即x?

1a?

ax?

1，所以x?

n（a）

【篇二：

离散数学第四版课后答案（第9章）】

1有5片树叶.

分析设t有x个1度顶点（即树叶）.则t的顶点数

x,t

的边数m?

x.由握手定理得方程.

2m?

2（4?

x）?

d（v

）?

13?

由方程解出x?

所求无向树t的度数列为1,1,1,1,1,2,2,3,3,3.由这个度数列可以画多棵非同构的无向树,图9.6给出的4棵都具有上述度数列,且它们是非同构的.

9.2t中有5个3度顶点.

分析设t中有x个3度顶点,则t中的顶点数n?

x,边数m?

x,由握手定理得方程.

由方程解出x=5.

所求无向树t的度数列为1,1,1,1,1,2,2,3,3,3.由这个度数列可以画多棵非同构的无向树,图9.6给出的4棵都具有上述度数列,且它们是非同构的.

9.2t中有5个3度顶点.

要析设t中有x个3度顶点,则t中的顶点数n?

x,边数m?

x,由握手定理得方程.

2m?

12?

2x?

d（v）?

3x?

2m?

12?

2x?

d（v）?

3x?

由此解出x?

5,即t中有5个3度顶.t的度数列为1,1,1,1,1,1,1,3,3,3,3,3.由于t中只有树叶和3度顶点,因而3度顶点可依次相邻,见图9.7所示.还有一棵与它非同构的树,请读者自己画出.

9.3加k?

1条新边才能使所得图为无向树.

分析设具有k个连通分支的森林为g,则g有k个连通分支t,t

tk,ti全为树,i?

1,2,?

k.加新边不能在ti内部加,否则

必产生回路.因而必须在不同的小树之间加新边.每加一条新边后,所得到的森林就减少一个连通分支.恰好加k?

1条新边,就使得图连通且无回路,因而是树.在加边过程中,只需注意,不在同一人连通分支中加边.下面给出一种加边方法,取v为t中顶点,加新边（v,v

）i?

1,2,?

1,则所得图为树,

见图9.8给出的一个特例.图中虚线边为新加的边.

9.4不一定.

分析n阶无向树t具有n?

1条边,这是无向树t的必要条件,但不是充公条件.例如,阶圈（即n?

1个顶点的初级回路）和一个孤立点组成无向简单图具有n?

1条边,但它显然不是树.

9.5非同构的无向树共有2棵,如图9.9所示.

分析由度数列1,1,1,1,2,2,4不难看出，唯一的4度顶点必须与2度顶点相邻，它与1个2度顶点相邻，还是与两个2度顶点都相邻，所得树是非同构的，再没有其他情况.因而是两棵非同构的树.

9.6有两棵非同构的生成树,见图9.10所示.

分析图9.10是5阶图

（5个顶点的图）,5阶非同构的无向树只有3棵,理由如下.5阶无向树中,顶点数n?

5,边数m?

4,各顶点度数之和为8,度数分配方案有3种,分别为

①1,1,1,1,4;②1,1,1,2,3;③1,1,2,2.2.

每种方案只有一棵非同构的树.图9.10所示的5阶图的非同构的生成树的度数列不能超出以上3种,也就是说,它至多有3棵非同构的生成树,但由于图中无4度顶点,所示,不可能有度数列为①的生成树,于是该图最多有两棵非同构的

生成树.但在图9.10中已经找出了两个非同构的生成树,其中

（1）的度数列为③,

（2）的度数列为②,因而该图准确地有两棵非同构的生成树.

9.7基本回路为:

c基本回路系统为{c基本割集为:

cbad,ce?

ead,cg?

gfa,ch?

hfab.

ce,cg,ch}.

sb?

{b,c,h},s

sa?

{a,e,c,g,h},sd?

{d,e,c}

sb,sd,sf}

{f,g,h}

基本回路系统为{s

vi,vj

vj）

则v

i,j

在生成树t中,且在t中,

之间存在唯一的路径?

与e?

（v

vj）

组成的回路为g中对

应弦e的基本回路.

vj）,则e为t中桥,于是t

（将e从t

中支掉）,产生两棵小树t和t,则

se?

{e|e在g中且e的两端点分别在

t1和t2中}

中另外的边全是

se为树枝e对应的基本割集.显然e?

se,se

弦.注意,两棵小树t和t,中很可能有平凡的树（一个顶

点）.

得两棵小树如图9.11中

（1）所示.g中一个端点在

（树枝）,e,c,g,h,它们全是弦,

ti中,另一个端点在t2中的边为a

于是s

{a,e,c,g,h}

得两棵小树如图9.11中

（2）所示,其中有一棵为

平凡树.g中一个端点在t中,另一个端点在t中的边数除树

枝b外,还有弦c,h,所以,s

{b,c,h}

产生的两棵小树如图9.11中（3）所示.g中一个

端点在t中,另中一个端点在t中的边,除树枝d外,还有两条

弦c,e,所示,s

{d,c,e}

产生的两棵小树如图9.11中（4）所示.由它产生

的基本割集为s

{f,g,h}

9.8按kruskal求最小生成树的算法,求出的图9.3

（1）的最小生成树t为图9.12中

（1）所示,其w（t）?

（2）的最小生成树t为图9.12中

（2）所示,其w（t）?

11.

9.9b

b2,b4为前缀码.

分析在b

b2,b4中任何符号串都不是另外符号串的前串,

因而它们都是前缀码.而在b中,1是11,101的前缀,因而b

不是前缀码.在b中,a,是aa,ac等的前缀,因而b也不是前缀码.

【篇三：

离散数学课后答案（第1,2,4章）武汉大学出版社】

）否

（2）否

（3）是，真值为0

（4）否

（5）是，真值为1

2、

（1）p：

天下雨q：

我去教室┐p→q

（2）p：

你去教室q：

我去图书馆p→q

（3）p，q同

（2）q→p

（4）p：

2是质数q：

2是偶数p∧q

3、

（1）0

（2）0

（3）1

4、

（1）如果明天是晴天，那么我去教室或图书馆。

（2）如果我去教室，那么明天不是晴天，我也不去图书馆。

（3）明天是晴天，并且我不去教室，当且仅当我去图书馆。

习题1.2

1、

（1）是

（2）是

（3）否

（4）是

（5）是

（6）否

2、

（1）（p→q）→r，p→q，r，p，q

（2）（┐p∨q）∨（r∧p），┐p∨q，r∧p，┐p，q，r，p

（3）（（p→q）∧（q→p））∨┐（p→q）），（p→q）∧（q→p），┐（p→q），p→q，（q→p），p→q，p，q，q，p，p，q

3、

（1）（（p→q）→（q→p））→（p→q）

（2）（（p→q）∨（（p→q）→r））→（（p→q）∧（（p→q）→r））

（3）（q→p∧┐p）→（p∧┐p→q）

4、（p→q）∨（（p∧q）∨（┐p∧┐q））∧（┐p∨q）

习题1.3

1、

（1）i（p∨（q∧r））=i（p）∨（i（q）∧i（r））=1∨（1∧0）=1

（2）i（（p∧q∧r）∨（┐（p∨q）∧┐（r∨s）））=（1∧1∧0）∨（┐（1∨1）∧┐（0∨1））=0∨（0∧0）=0

（3）i（（p←→r）∧（┐q→s））=（1←→0）∧（┐1→1）=0∧1=0

（4）i（（p∨（q→r∧┐p））←→（q∨┐s））=（1∨（1→（0∧┐1）））←→（1∨┐1）=1←→1=1

（5）i（┐（p∧q）∨┐r∨（（q←→┐p）→r∨┐s））=┐（1∧1）∨┐0∨（（1←→┐1）→（0∨┐1））=0∨1∨1=1

2、

（1）

pqp→qq∧（p→q）q∧（p→q）→p

00101

01110

10001

11111

（2）

pqrq∧r┐（p∨（q∧r））p∨qp∨r（p∨q）∧（p∨r）原式000010000

001010100

010011000

011101110

100001110

101001110

110001110

111101110

（3）

pqrp∨qq∧pp∨q→q∧pp∧┐r原式

00000100

00100100

01010001

01110001

10010011

10110001

11011111

11111100

3、

（1）原式=f→q=t原式为永真式

（2）原式=┐t∨（┐（┐p∨q）∨（┐┐q∨┐p））=（p∧┐q）∨（q∨┐p）

=（p∧┐q）∨┐（p∧┐q）=t原式为永真式

（3）原式=┐（p∧q）←→┐（p∧q）=t原式为永真式

（4）原式=p∧（q∨r）←→p∧（q∨r）=t原式为永真式

（5）原式=┐（p∨┐q）∨q=（┐p∧q）∨q=q原式为可满足式

（6）原式=┐（p∧q）∨p=┐p∨┐q∨p=t∨┐q=t原式为永真式

（7）原式=（┐p∨p∨q）∧┐p=（t∨q）∧┐p

=t∧┐p=┐p原式为可满足式

（8）原式=┐（（p∨q）∧（┐q∨r））∨（┐p∨r）=（p∧┐q）∨（q∧┐r）∨（┐p∨r）=（（p∧┐q）∨┐p）∨（（q∧┐r）∨r）

=（（p∨┐p）∧（┐q∨┐p））∨（（q∨r）∧（┐r∨r））

=（┐q∧┐p）∨（q∨r）=t原式为永真式

4、

（1）左=┐p∨┐q∨p=┐┐p∨（┐p∨┐q）=右

（2）左=┐（┐p∨q）=右

（3）左=┐（p∧q）∨p=┐p∨┐q∨p=t∨┐q=右

（4）左=┐（p→q）∨┐（q→p）=（p∧┐q）∨（q∧┐p）=中

=（（p∧┐q）∨q）∧（（p∧┐q）∨┐p）

=（p∨q）∧（┐q∨q）∧（p∨┐p）∧（┐q∨┐p）

=（p∨q）∧┐（p∧q）=右

（5）左（pq）（rq）（pq）q右

（1）左qpq右

（2）（p（qr））（（pq）（pr））

（pqr）（pq）（pr）

（pqr）（pq）pr

（pqr）（（pp）（qp））r

（pqr）（qpr）

（pqr）（pqr）

故p（qr）（pq）（pr）

（3）.（pq）（ppq）

（pq）p（pq）

（pq）（pp）（pq）

（pq）（pq）

故pqppq

（4）.（（pq）q）pq

（（pq）q）pq

（pq）（qq）pq

（pq）（pq）

故（pq）qpq

（5）.（（pp）q）（（pp）r）（qr）

（qr）qr

qrqr

故（（pp）q）（（pp）r）qr

（6）左（qf）（rf）

（qf）（rf）

rq右

（1）原式（pqr）

（2）原式pqp（pqp）

（3）原式p（qrp）pqr（pqr）

（1）原式（pqp）

（2）原式（pqr）pq（（pqr）pq）

（3）原式pq（rp）（pq（rp））

（1）（pq）（（p（pq））r）p

（2）（pqr）（pr）

（3）（pf）（qt）

习题1.4

（1）原式（pq）（（pq）（qp））

（pq）（qp）

（pq）qp

qp,既是析取范式又是合取范式

（2）原式（（pq）（pq））（（pq）（pq））

（pq）（pq）析取范式

p（qq）合取范式

（3）原式pqs（pq）析取范式

（p（pq））qs

pqs合取范式

（4）原式ppqqr既是析取范式又是合取范式

（1）原式pqr为真的解释是：

000，001，011，100，101，110，111

故原式的主析取范式为:

（pqr）（pqr）（pqr）（pqr）（pqr）（pqr）（pqr）

（2）原式（pq）r

（pq（rr））（（pp）r）

（pqr）（pqr）（pq）（pr）

（pqr）（pqr）（p（qq）r）（p（qq）r）

（pqr）（pqr）（pqr）（pqr）（pqr）（pqr）

（pqr）（p

展开阅读全文