离散数学第五版课后答案.docx
《离散数学第五版课后答案.docx》由会员分享，可在线阅读，更多相关《离散数学第五版课后答案.docx（16页珍藏版）》请在冰点文库上搜索。
离散数学第五版课后答案
离散数学第五版课后答案
【篇一：
离散数学课后答案（四）】
txt>4.1习题参考答案
--------------------------------------------------------------------------------1、
根据结合律的定义在自然数集n中任取a,b,c三数，察看（a。
b）。
c=a。
（b。
c）是否成立？
可以发现只有b、c满足结合律。
晓津观点：
b）满足结合律，分析如下：
a）若有a,b,c∈n，则（a*b）*c=（a-b）-ca*（b*c）=a-（b-c）
在自然数集中，两式的值不恒等，因此本运算是不可结合的。
b）同上，（a*b）*c=max（max（a,b）,c）即得到a，b,c中最大的数。
a*（b*c）=max（a,max（b,c））仍是得到a,b,c中最大的数。
此运算是可结合的。
c）同上,（a*b）*c=（a+2b）+2c而a*（b*c）=a+2（b+2c）,很明显二者不恒等，因此本运算也不是可结合的。
d）运用同样的分析可知其不是可结合的。
--------------------------------------------------------------------------------2、
d）是不封闭的。
--------------------------------------------------------------------------------
其不满足交换律、满足结合律、不满足幂等律、无零元、无单位元
晓津补充证明如下：
（1）a*b=pa+qb+r而b*a=pb+qa+r当p,q取值不等时，二式不相等。
因此*运算不满足交换律。
（2）设a,b,c∈r
则（a*b）*c=p（pa+qb+r）+qc+r=p^2a+pab+pr+qc+r而a*（b*c）=pa+q（pb+qc+r）+r=pa+qpb+q^2c+qr+r二式不恒等，因此*运算是不满足结合律的。
（3）a*a=pa+qa+r≠a所以运算不满足幂等律。
（4）反证法。
设有单位元e,则应有
a*e=pa+qe+r=a,e*a=pe+qa+r=a,可知e=（a-pa-r）/q或e=（a-qa-r）/p当p,q,r,a取值不同时，可得不同的e,这与单位元若有时只是唯一的定理相矛盾。
（5）反证法。
设有零元o,则应有
a*o=pa+qo+r=o,o*a=po+qa+r=o，同上分析，零元不止一个，因此与零元唯一的定理相矛盾。
--------------------------------------------------------------------------------5、（a）:
可交换、具有幂等性、有幺元a、c是b的逆元
晓津答案：
可交换，但不具有幂等性。
幺元e=a,表中有a*a=a,b*c=a,c*b=a,则可得a的逆元是a,b有逆元c,c有逆元b.
（b）:
可交换、不具有幂等性、有幺元a,因为a*a=a,b*b=a,所以a有逆元a,b有逆元b.
（c）:
不可交换、具有幂等性,无幺元。
（d）:
可交换、不具有幂等性、有幺元a,a有逆元a.
--------------------------------------------------------------------------------6、
证明：
设a,b,c∈i+a*（b△c）=a^（b.c）
（a*b）△（a*c）=（a^b）.（a^c）=a^（b+c）可见：
a*（b△c）≠（a*b）△（a*c）根据：
a*（b△c）≠（a*b）△（a*c）可知*对△是不可分配的
--------------------------------------------------------------------------------7、解：
晓津证明如下：
（1）我们先证明n=1时,该运算*在z1上的运算是可结合的：
此时，设有a,b,c∈z1则有a=0,b=0,c=0（a*b）*c=（（（a.b）modn）.c）modn=0a*（b*c）=（a.（（b.c）modn））modn=0
两式相等，因此当n=1时，*运算是可结合的。
（2）由上可设当n=k时，*运算是可结合的。
（3）设n=k+1时，有：
（a*b）*c=（（（a.b）mod（k+1））.c）mod（k+1）=（a.b.cmod（k+1））mod（k+1）a*（b*c）=（a.（（b.c）mod（k+1）））mod（k+1）=（a.b.cmod（k+1））mod（k+1）
可见两式是完全相同的结果。
因此有当n=k+1时，*运算满足结合律。
所以对于任意n∈n,*在zn上是可结合的。
4.2节习题参考答案
--------------------------------------------------------------------------------1、解：
zn={0,1,2,3}
（1）我们先证明k=1时,该运算*在z1上的运算是可结合的：
此时，设有a,b,c∈z1则有a=0,b=0,c=0（a*b）*c=（（（a.b）modk）.c）modk=0a*（b*c）=（a.（（b.c）modk））modk=0
两式相等，因此当k=1时，*运算是可结合的。
（2）由上可设当k=k时，*运算是可结合的。
（3）设k=k+1时，有：
（a*b）*c=（（（a.b）mod（k+1））.c）mod（k+1）=（a.b.cmod（k+1））mod（k+1）a*（b*c）=（a.（（b.c）mod（k+1）））mod（k+1）=（a.b.cmod（k+1））mod（k+1）
可见两式是完全相同的结果。
因此有当k=k+1时，*运算满足结合律。
所以对于任意k∈k,*在zk上是可结合的。
由此可知其是个半群。
--------------------------------------------------------------------------------2、证明：
二元运算□是可结合的。
根据结合律：
（x□y）□z=x□（y□z）（x□y）□z=（x*a*y）*a*zx□（y□z）=x*a*（y*a*z）由于*满足结合律，故：
（x*a*y）*a*z=x*a*（y*a*z）=（x□y）□z=x□（y□z）=二元运算□是可结合的
--------------------------------------------------------------------------------3、构成一个半群,证明详见第一题，其具有封闭性、结合性。
--------------------------------------------------------------------------------4、
（1）、由运算。
可知，a。
b∈r，可知其在r上具有封闭性。
（2）、对于任意a,b,c∈r
（a。
b）。
c=（a+b+ab）。
c=a+b+ab+c+ac+bc+abca。
（b。
c）=a。
（b+c+bc）=a+b+c+bc+ab+ac+abc可见：
（a。
b）。
c=a。
（b。
c）即。
在r上是可结合的。
（3）因为[0]。
[i]=i,所以[0]是r,o上一个幺元根据上述r,o是独异点
晓津认为题中所给r,o中的o应为o；答案中的（3）幺元是0,而不是[0].--------------------------------------------------------------------------------5、
晓津证明如下：
反证法：
若v不是独异点，则v不存在幺元.而因为x是任意的，则当x=a时，有a*u=v*a=a
即此时u,v分别是a的右、左幺元。
因为在一个系统中若同时存在左右幺元，则二者必相等，因此此时u=v=e。
这与假设矛盾，因此由v是一个半群，又v具有幺元，得知v是独异点。
--------------------------------------------------------------------------------6、证明：
v=s,o是半群,故。
在s上是可结合的
x。
ol=ol。
x根据定义4.1.5可知：
ol。
x=ol
故x。
ol也是一个左零元
晓津不同意见：
可结合不等于可交换。
在这里应当把（x。
ol）看作一个元素，这整个元素是一个左零元。
另，题中s,o应为s，。
证明如下：
因为v是半群，所以运算是封闭的,可结合的。
若有x,y,ol∈s，则有x。
ol∈s
且有（x。
ol）。
y=x。
（ol。
y）=x。
ol即x。
ol是s中任意y的左零元。
--------------------------------------------------------------------------------7、解：
子半群如下：
v1=z1,,v2=z2,,v3=z3,,v4=z4,
其中v1,v2,v3,v4都是v的子独异点，因为这四个半群中均有幺元e=1。
--------------------------------------------------------------------------------8、证明如下：
设s,*为一个独异点，则它有一个幺元.
设在s,*中e是关于*的幺元，若对于任意a∈s，存在b∈s且b*a=e，则b是a的左逆元。
令左逆元的集合为l，则ls,所以*在l上是结合的。
对任意的a，b∈l,
则必存在x,y∈s,使a*x=e，b*y=e;则（a*b）*（y*x）=a*（b*y）*x=a*e*x=a*x=e;故a*b是y*x的左逆元，∴a*b∈l
∴*在l上是封闭的（本段证明由阮允准补充）
即l,*是一个半群。
因为e是s中关于*的幺元，所以它同时也是l中关于*的幺元。
因此l,*是一个子独异点。
--------------------------------------------------------------------------------9、
答：
从表中看：
4.3习题参考答案
证明：
根据定理
4.3.4，设g,*是一个群，对于a,b∈g。
必存在惟一的x∈g,使a*x=b
设a*b=g因为a*b=a*c所以a*c=g
由于b在a中是惟一的，而c在a中也是惟一。
所以b=c晓津的证明如下：
已知a,*为群，则对于任意a,必逆元a-1和幺元e，则有：
a-1*（a*b）=a-1*（a*c）即有
（a-1*a）*b=（a-1*a）*ce*b=e*c所以有b=c
证明：
根据定理
4.2.2设h,*是独异点，对于a,b∈h,且a,b均有逆元。
那么根据定义4.3.1，可知h，*是群
交换群就是*运算满足交换律的情况。
满足交换律就是a*b=b*a将（a*b）*（b*a）根据结合性可得
a*（b*b）*a=a*e*a=e
将（b*a）*（a*b）根据结合性可得b*（a*a）*b=b*e*b=e由于有
x*x=e，而上述两个运算的结果，可知a*b=b*a
根据定义4.3.4，可知其是一个交换群。
晓津证法如下：
设有任意a,b∈h，e为幺元，则根据已知条件有：
a*b=（e*a）*（b*e）=（b*b*a）*（b*a*a）=b*（（b*a）*（b*a））*a
（b*c）*c=a*c=cb*（c*c）=b*a=b（b*c）*c≠b*（c*c）故不是半群（本题答案由hybina提供，感谢hybina）
=b*e*a=b*a
可见a*b=b*a,即h,*是交换群。
证明：
关于此题的疑惑，假如a=1b=1那么
a*b=0,0不是正整数了。
那么g,*就不能满足封闭性了。
也有可能是我把题意给理解错了。
晓津观点，整数加群是指在整数集上进行加法运算的一个代数系统。
而不仅仅是正整数上进行加运算，0也是包含在这个集合中的，所以满足封闭性。
证明如下：
（1）因为任意a,b∈g，即a,b∈z，且a*b=a+b-2,可见a*b∈z，因此g,*是封闭的。
（2）设有任意a,b,c∈g，则（a*b）*c=（a+b-2）+c-2=a+b+c-4
a*（b*c）=a+（b+c-2）-2=a+b+c-4=（a*b）*c可见g上关于*运算是可结合的。
（3）在g,*中存在幺元e=2，验证如下：
对于任意a∈g，有a*e=a+2-2=a，e*a=2+a-2=a
（4）对于任意a∈g，存在逆元a-1=4-a,验证如下：
a*a-1=a+（4-a）-2=2;a-1*a=4-a+a-2=2。
因此可证，g，*是群。
4、设g=
{
（10）（10）（-10）（-10）（01）（0-1）（01）（0-1）
}
证明：
g关于矩阵乘法构成一个群。
运算表：
并且其具有单位元
1001
如何证明其具有结合性？
晓津认为，仍旧可从表上看出。
（表中色块表示（a*b）*d=a*（b*d）。
*表示矩阵乘法。
仅供理解用，证明时不必写出。
）
另外可以每个矩阵乘以它本身，就等于其单位元，根据题二的结论
x*x=单位元，则说明g,矩阵乘法是群。
晓津观点：
最后一步应找到每个元素有其逆元而不是单位元。
仍从表上可以找到,每个元素本身就是它的逆元。
因此g关于矩阵乘法
构成一个群。
问：
s,*是否构成群？
为什么？
关于普通乘法，很显然它也是可结合的。
为其逆元。
可见g,*构成群。
同学们有更好的理解和证法请不要独享啊。
其是群，因为右逆元存在的条件便是先存在着单位元（参见p80定义4.1.6），所以g,*存在幺元。
根据定理4.1.4，因为g,*是半群，所以其是可结合运算的，根据定理4.1.4，其必有左逆元=右逆元，所以其是一个群。
[4]=[3]4[5]=[3]5[1]=[3]6故g是六阶循环群。
littletree同学指出还有一个生成元：
[5]
因4=[5]2，6=[5]3,2=[5]4,3=[5]5,1=[5]6晓津答案：
a）
b）（i是一个群。
a）
从运算表中可以看其具有封闭性。
有幺元a，对于b有逆元c，对于c有逆元b。
同时可看出其具有结合性，如（a。
b）。
c=a。
（b。
c）=ab）其是循环群，b=bc=b2a=b3b是生成元。
还有c=cb=c2a=c3所以c也是生成元晓津证明如下：
（1）是指g中的有限阶群，题意是指任何一个有限阶群都是g的一个子群?
（2）还是指g中所包含的元素的阶是有限的且这些元素组成的集合是g的一个子群?
请兄弟mm们提供高见。
下面是阮允准同学的证明:
我认为是第2种理解。
证明如下：
设e是＜g，＊＞的幺元显然e∈h,
所以h是g的非空子集。
设任意的a,b∈h，则必有正整数m,n使am=e,
【篇二：
离散数学课后习题答案（左孝凌版）】
s=txt>1-1，1-2解：
a）是命题，真值为t。
b）不是命题。
c）是命题，真值要根据具体情况确定。
d）不是命题。
e）是命题，真值为t。
f）是命题，真值为t。
g）是命题，真值为f。
h）不是命题。
i）不是命题。
（2）解：
原子命题：
我爱北京天安门。
复合命题：
如果不是练健美操，我就出外旅游拉。
（3）解：
a）（┓p∧r）→qb）q→rc）┓pd）p→┓q（4）解：
a）设q:
我将去参加舞会。
r:
我有时间。
p:
天下雨。
q?
（r∧┓p）:
我将去参加舞会当且仅当我有时间和天不下雨。
b）设r:
我在看电视。
q:
我在吃苹果。
r∧q:
我在看电视边吃苹果。
c）设q:
一个数是奇数。
r:
一个数不能被2除。
（q→r）∧（r→q）:
一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。
（5）解：
a）设p：
王强身体很好。
q：
王强成绩很好。
p∧qb）设p：
小李看书。
q：
小李听音乐。
p∧qc）设p：
气候很好。
q：
气候很热。
p∨qd）设p：
a和b是偶数。
q：
a+b是偶数。
p→q
e）设p：
四边形abcd是平行四边形。
q：
四边形abcd的对边平行。
p?
qf）设p：
语法错误。
q：
程序错误。
r：
停机。
（p∨q）→r（6）解：
a）p:
天气炎热。
q:
正在下雨。
p∧qb）p:
天气炎热。
r:
湿度较低。
p∧rc）r:
天正在下雨。
s:
湿度很高。
r∨sd）a:
刘英上山。
b:
李进上山。
a∧be）m:
老王是革新者。
n:
小李是革新者。
m∨nf）l:
你看电影。
m:
我看电影。
┓l→┓m
g）p:
我不看电视。
q:
我不外出。
r:
我在睡觉。
p∧q∧rh）p:
控制台打字机作输入设备。
q:
控制台打字机作输出设备。
p∧q1-3
（1）解：
a）不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式）b）是合式公式
c）不是合式公式（括弧不配对）
d）不是合式公式（r和s之间缺少联结词）e）是合式公式。
（2）解：
a）a是合式公式，（a∨b）是合式公式，（a→（a∨b））是合式公式。
这个过程可以简记为：
a；（a∨b）；（a→（a∨b））同理可记
b）a；┓a；（┓a∧b）；（（┓a∧b）∧a）
c）a；┓a；b；（┓a→b）；（b→a）；（（┓a→b）→（b→a））d）a；b；（a→b）；（b→a）；（（a→b）∨（b→a））（3）解：
a）（（（（a→c）→（（b∧c）→a））→（（b∧c）→a））→（a→c））b）（（b→a）∨（a→b））。
（4）解：
a）是由c）式进行代换得到，在c）中用q代换p,（p→p）代换q.d）是由a）式进行代换得到，在a）中用p→（q→p）代换q.
e）是由b）式进行代换得到，用r代换p,s代换q,q代换r,p代换s.（5）解：
a）p:
你没有给我写信。
r:
pq∨b）p:
张三不去。
q:
李四不去。
r:
他就去。
（p∧q）→r
c）p:
我们能划船。
q:
我们能跑步。
┓（p∧q）d）p:
你来了。
q:
他唱歌。
r:
你伴奏。
p→（q?
r）（6）解：
p:
它占据空间。
q:
它有质量。
r:
它不断变化。
s:
它是物质。
这个人起初主张：
（p∧q∧r）?
s后来主张：
（p∧q?
s）∧（s→r）
这个人开头主张与后来主张的不同点在于：
后来认为有p∧q必同时有r，开头时没有这样的主张。
（7）解：
a）p:
上午下雨。
q:
我去看电影。
r:
我在家里读书。
s:
我在家里看报。
（┓p→q）∧（p→（r∨s））
b）p:
我今天进城。
q:
天下雨。
┓q→pc）p:
你走了。
q:
我留下。
q→p1-4（4）解：
a）
所以，p∧（q∧r）?
（p∧q）∧rb）
所以，p∨（q∨r）?
（p∨q）∨rｃ）
【篇三：
离散数学课后习题答案（焦占亚版）】
列句子中，哪些是命题？
哪些不是命题？
如果是命题，指出它的真值。
⑴中国有四大发明。
⑵计算机有空吗?
⑶不存在最大素数。
⑷21+3＜5。
⑸老王是山东人或河北人。
⑹2与3都是偶数。
⑺小李在宿舍里。
⑻这朵玫瑰花多美丽呀!
⑼请勿随地吐痰!
⑽圆的面积等于半径的平方乘以?
。
⑾只有6是偶数，3才能是2的倍数。
⑿雪是黑色的当且仅当太阳从东方升起。
⒀如果天下大雨，他就乘班车上班。
解：
⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。
2.将下列复合命题分成若干原子命题。
⑴李辛与李末是兄弟。
⑵因为天气冷，所以我穿了羽绒服。
⑶天正在下雨或湿度很高。
⑷刘英与李进上山。
⑸王强与刘威都学过法语。
⑹如果你不看电影，那么我也不看电影。
⑺我既不看电视也不外出，我在睡觉。
⑻除非天下大雨，否则他不乘班车上班。
解：
⑴本命题为原子命题；
⑵p：
天气冷；q：
我穿羽绒服；
⑶p：
天在下雨；q：
湿度很高；
⑷p：
刘英上山；q：
李进上山；
⑸p：
王强学过法语；q：
刘威学过法语；
⑹p：
你看电影；q：
我看电影；
⑺p：
我看电视；q：
我外出；r：
我睡觉；
⑻p：
天下大雨；q：
他乘班车上班。
3.将下列命题符号化。
⑴他一面吃饭，一面听音乐。
⑵3是素数或2是素数。
⑶若地球上没有树木，则人类不能生存。
⑷8是偶数的充分必要条件是8能被3整除。
⑸停机的原因在于语法错误或程序错误。
⑹四边形abcd是平行四边形当且仅当它的对边平行。
⑺如果a和b是偶数，则a+b是偶数。
号化为：
p∧q
⑵p：
3是素数；q：
2是素数；原命题符号化为：
p∨q
⑶p：
地球上有树木；q：
人类能生存；原命题符号化为：
?
p→?
q
⑷p：
8是偶数；q：
8能被3整除；原命题符号化为：
p?
q
⑸p：
停机；q：
语法错误；r：
程序错误；原命题符号化为：
q∨r→p
⑹p：
四边形abcd是平行四边形；q：
四边形abcd的对边平行；原命题符号化为：
p?
q。
⑺p：
a是偶数；q：
b是偶数；r：
a+b是偶数；原命题符号化为：
p∧q→r
4.将下列命题符号化，并指出各复合命题的真值。
⑴如果3+3=6，则雪是白的。
⑵如果3+3≠6，则雪是白的。
⑶如果3+3=6，则雪不是白的。
⑷如果3+3≠6，则雪不是白的。
⑸是无理数当且仅当加拿大位于亚洲。
⑹2+3=5的充要条件是是无理数。
（假定是10进制）
⑺若两圆o1，o2的面积相等，则它们的半径相等，反之亦然。
⑻当王小红心情愉快时，她就唱歌，反之，当她唱歌时，一定心情愉快。
解：
设p：
3＋3＝6。
q：
雪是白的。
⑴原命题符号化为：
p→q；该命题是真命题。
⑵原命题符号化为：
?
p→q；该命题是真命题。
⑶原命题符号化为：
p→?
q；该命题是假命题。
⑷原命题符号化为：
?
p→?
q；该命题是真命题。
⑸p：
3是无理数；q：
加拿大位于亚洲；原命题符号化为：
p?
q；该命题是假命题。
⑹p：
2+3＝5；q：
是无理数；原命题符号化为：
p?
q；该命题是真命题。
⑺p：
两圆o1,o2的面积相等；q：
两圆o1,o2的半径相等；原命题符号化为：
p?
q；该命题是真命题。
⑻p：
王小红心情愉快；q：
王小红唱歌；原命题符号化为：
p?
q；该命题是真命题。
习题1.2
1.判断下列公式哪些是合式公式，哪些不是合式公式。
⑴（p∧q→r）
⑵（p∧（q→r）
⑶（（?
p→q）?
（r∨s））
⑷（p∧q→rs）
⑸（（p→（q→r））→（（q→p）?
q∨r））。
解：
⑴⑶⑸是合式公
升级会员 