离散数学习题答案(通用8篇)
离散数学习题答案 篇1
一、(10分)某项工作需要派A、B、C和D 4个人中的2个人去完成,按下面3个条件,有几种派法?如何派?
(1)若A去,则C和D中要去1个人;
(2)B和C不能都去;
(3)若C去,则D留下。
解设A:A去工作;B:B去工作;C:C去工作;D:D去工作。则根据题意应有:ACD,(B∧C),CD必须同时成立。因此
(ACD)∧(B∧C)∧(CD)
(A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D)
(A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))
(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)
∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)
F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D)
(A∧C)∨(B∧C∧ D)∨(C∧D)
T
故有三种派法:B∧D,A∧C,A∧D。
二、(15分)在谓词逻辑中构造下面推理的证明:某学术会议的每个成员都是专家并且是工人,有些成员是青年人,所以,有些成员是青年专家。
解:论域:所有人的集合。S(x):x是专家;W(x):x是工人;Y(x):x是青年人;则推理化形式为:
x(S(x)∧W(x)),xY(x)x(S(x)∧Y(x))
下面给出证明:
(1)xY(x)P
(2)Y(c)T(1),ES
(3)x(S(x)∧W(x))P
(4)S(c)∧W(c)T(3),US
(5)S(c)T(4),I
(6)S(c)∧Y(c)T(2)(5),I
(7)x(S(x)∧Y(x))T(6),EG
三、(10分)设A、B和C是三个集合,则AB(BA)。
证明:ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)
x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB)
(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A))
(BA)。
四、(15分)设A={1,2,3,4,5},R是A上的二元关系,且R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>},求r(R)、s(R)和t(R)。
解r(R)=R∪IA={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}
s(R)=R∪R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>} R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>}
R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>}
R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>}=R
t(R)=Ri={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,i14232-
15>}。
五、(10分)R是非空集合A上的二元关系,若R是对称的,则r(R)和t(R)是对称的。
证明对任意的x、y∈A,若xr(R)y,则由r(R)=R∪IA得,xRy或xIAy。因R与IA对称,所以有yRx或yIAx,于是yr(R)x。所以r(R)是对称的。
下证对任意正整数n,R对称。
因R对称,则有xRyz(xRz∧zRy)z(zRx∧yRz)yRx,所以R对称。若Rn对称,则xRn1yz(xRnz∧zRy)z(zRnx∧yRz)yRn1x,所以Rn1对称。因此,对任意正整数n,Rn对称。对任意的x、y∈A,若xt(R)y,则存在m使得xRy,于是有yRx,即有yt(R)x。因此,t(R)是对称的。
六、(10分)若f:A→B是双射,则f:B→A是双射。
证明因为f:A→B是双射,则f是B到A的函数。下证f是双射。
对任意x∈A,必存在y∈B使f(x)=y,从而f(y)=x,所以f是满射。
对任意的y1、y2∈B,若f(y1)=f(y2)=x,则f(x)=y1,f(x)=y2。因为f:A→B是函数,则y1=y2。所以f是单射。
综上可得,f:B→A是双射。
七、(10分)设是一个半群,如果S是有限集,则必存在a∈S,使得a*a=a。
证明因为是一个半群,对任意的b∈S,由*的封闭性可知,b=b*b∈S,b=b*b∈S,…,bn∈S,…。
因为S是有限集,所以必存在j>i,使得bi=bj。令p=j-i,则bj=bp*bj。所以对q≥i,有bq=bp*bq。
因为p≥1,所以总可找到k≥1,使得kp≥i。对于bkp∈S,有bkp=bp*bkp=bp*(bp*bkp)=…=232-1-1-1-1-1-1-1-1-1mm222nbkp*bkp。
令a=bkp,则a∈S且a*a=a。
八、(20分)(1)若G是连通的平面图,且G的每个面的次数至少为l(l≥3),则G的边数m与结点数n有如下关系:
m≤
rl(n-2)。l2l证明设G有r个面,则2m=
2)。d(f)≥lr。由欧拉公式得,n-m+r=2。于是,m≤l2(n-ii
1(2)设平面图G=
证明设G=
离散数学考试试题(B卷及答案)
一、(10分)证明(P∨Q)∧(PR)∧(QS)S∨R
证明因为S∨RRS,所以,即要证(P∨Q)∧(PR)∧(QS)RS。
(1)R附加前提
(2)PRP
(3)PT(1)(2),I
(4)P∨QP
(5)QT(3)(4),I
(6)QSP
(7)ST(5)(6),I
(8)RSCP
(9)S∨RT(8),E
二、(15分)根据推理理论证明:每个考生或者勤奋或者聪明,所有勤奋的人都将有所作为,但并非所有考生都将有所作为,所以,一定有些考生是聪明的。
设P(e):e是考生,Q(e):e将有所作为,A(e):e是勤奋的,B(e):e是聪明的,个体域:人的集合,则命题可符号化为:x(P(x)(A(x)∨B(x))),x(A(x)Q(x)),x(P(x)Q(x))x(P(x)∧B(x))。
(1)x(P(x)Q(x))P
(2)x(P(x)∨Q(x))T(1),E
(3)x(P(x)∧Q(x))T(2),E
(4)P(a)∧Q(a)T(3),ES
(5)P(a)T(4),I
(6)Q(a)T(4),I
(7)x(P(x)(A(x)∨B(x))P
(8)P(a)(A(a)∨B(a))T(7),US
(9)A(a)∨B(a)T(8)(5),I
(10)x(A(x)Q(x))P
(11)A(a)Q(a)T(10),US
(12)A(a)T(11)(6),I
(13)B(a)T(12)(9),I
(14)P(a)∧B(a)T(5)(13),I
(15)x(P(x)∧B(x))T(14),EG
三、(10分)某班有25名学生,其中14人会打篮球,12人会打排球,6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数。
解设A、B、C分别表示会打排球、网球和篮球的学生集合。则:
|A|=12,|B|=6,|C|=14,|A∩C|=6,|B∩C|=5,|A∩B∩C|=2,|(A∪C)∩B|=6。
因为|(A∪C)∩B|=(A∩B)∪(B∩C)|=|(A∩B)|+|(B∩C)|-|A∩B∩C|=|(A∩B)|+5-2=6,所以|(A∩
B)|=3。于是|A∪B∪C|=12+6+14-6-5-3+2=20,|ABC|=25-20=5。故,不会打这三种球的共5人。
四、(10分)设A1、A2和A3是全集U的子集,则形如Ai(Ai为Ai或Ai)的集合称为由A1、A2和
i1
3A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。
证明小项共8个,设有r个非空小项s1、s2、…、sr(r≤8)。
对任意的a∈U,则a∈Ai或a∈Ai,两者必有一个成立,取Ai为包含元素a的Ai或Ai,则a∈Ai,i13即有a∈si,于是Usi。又显然有siU,所以U=si。
i1i1i1i1rrrr
任取两个非空小项sp和sq,若sp≠sq,则必存在某个Ai和Ai分别出现在sp和sq中,于是sp∩sq=。综上可知,{s1,s2,…,sr}是U的一个划分。
五、(15分)设R是A上的二元关系,则:R是传递的R*RR。
证明(5)若R是传递的,则
反之,若R*RR,则对任意的x、y、z∈A,如果xRz且zRy,则
六、(15分)若G为连通平面图,则n-m+r=2,其中,n、m、r分别为G的结点数、边数和面数。证明对G的边数m作归纳法。
当m=0时,由于G是连通图,所以G为平凡图,此时n=1,r=1,结论自然成立。
假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。
设e是G的一条边,从G中删去e后得到的图记为G,并设其结点数、边数和面数分别为n、m和r。对e分为下列情况来讨论:
若e为割边,则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1+n2=n=n,m1+m2=m=m-1,r1+r2=r+1=r+1。由归纳假设有n1-m1+r1=2,n2-m2+r2=2,从而(n1+n2)-(m1+m2)+(r1+r2)=4,n-(m-1)+(r+1)=4,即n-m+r=2。
若e不为割边,则n=n,m=m-1,r=r-1,由归纳假设有n-m+r=2,从而n-(m-1)+r-1=2,即n-m+r=2。
由数学归纳法知,结论成立。
七、(10分)设函数g:A→B,f:B→C,则:
(1)fg是A到C的函数;
(2)对任意的x∈A,有fg(x)=f(g(x))。
证明(1)对任意的x∈A,因为g:A→B是函数,则存在y∈B使
对任意的x∈A,若存在y1、y2∈C,使得
综上可知,fg是A到C的函数。
(2)对任意的x∈A,由g:A→B是函数,有
八、(15分)设
一个等价关系,且[a]R=aH。
证明对于任意a∈G,必有a1∈G使得a1*a=e∈H,所以∈R。--
若∈R,则a1*b∈H。因为H是G的子群,故(a1*b)1=b1*a∈H。所以∈R。----
若∈R,∈R,则a1*b∈H,b1*c∈H。因为H是G的子群,所以(a1*b)*(b1*c)=a----
-1*c∈H,故∈R。
综上可得,R是G中的一个等价关系。
对于任意的b∈[a]R,有∈R,a1*b∈H,则存在h∈H使得a1*b=h,b=a*h,于是b∈aH,--
[a]RaH。对任意的b∈aH,存在h∈H使得b=a*h,a1*b=h∈H,∈R,故aH[a]R。所以,[a]R-
一道数学练习题答案的探究 篇2
多年的数学教学使我认识到数学知识不是学来的,也不是教出来的,而是探究出来的,探究能使学生精力高度集中,全身心的投入,从而搞清知识的来胧去脉前因后果,进而达到融会贯通、灵活运用,正因为如此,自己在教学中特注重让学生探究,练习题的处理也不例外;学生用数学知识解决实际问题的能力较差,所以在学了勾股定理后特意安排了一道用勾股定理解决实际问题的练习题,通过探究达到提高学生运用学知识解决实际问题的能力。
题目:1个1m高的人正在一棵9m高的树旁劳动,忽起一阵大风,将大树从距地面4m处吹断,此时此人应站在何处比较安全?
师:哪位同学比较聪明且肯动脑筋能解出此题?
(大部分学生纷纷举起手来,这么同学都能解出来,我心里挺高兴的。)
生A:人应站在距树3m以的地方才安全。
师: 生A陈述你的理由。
生A: 如图(1),风是从距地面的4mB处吹断的,AB=4m,树高9m,那么断了的部分BC 长5m,树与地面垂直,在Rt△ABC中,根据勾股定理得。
AC=BC2-AB2
=52-42
=3m
所以此人此时应站在距树3m以外的地方较安全。(此时下面部分学生连声说不对!不对!)
师: A肯动脑做了,说说你的想法。
生B:生A的答案不全面,人除站在3m以外安全还可站在如图(2)所示的A与D之间,因为1m高的人站在C与D之间某处,树会压着人,A与D之间有空间,且树斜着撞不着人。(这时,教室时像煮沸的油锅,一片议论声,有的说对,有的说不对)。
师:哪位同学说“不对”,谈谈你的理由生C:人站在A与D之间也不安全,因为,折断部分BC上还有大分枝、小分枝、这些树枝可能撞着人,还有一种特殊情况可能发生,折断部分BC会从B处完全断开,整个BC部分掉下来,也会压着人,所以人站A与D之间某处也不安全。
师:生C考虑的比较细致,根据以上三位同学的回答,说明人只能站在3m以外,这个 结果正确吗?
(此时无人回答,同学们都在苦思冥想,我想此时如果通过老师点拨效果不佳,不讲同学们又得不出正确答案,心里有点着急,忽然头脑中冒出一个念头,实践出真知,不妨让学生自己动手实践,发现真谛。
师:现在动手实践:前后四个人分为一小组,先用硬纸板剪出两个长分别为45cm、5cm的硬纸条(宽度不超过1cm或可替代硬纸条的东西,按20:1比例);然后四人既要齐心协力、模仿树倒的过程,又要分工:1人纪录、1人观察、1人移动5cm硬纸条(代替1米高的人)移动范围在15cm以外,多在15cm-20cm之间移动,1人用45cm的硬纸条(从20cm处折一下,25cm代替折断部分)模仿树倒的过程;随后四人一组,根据操作结果,共同商讨,画出树倒的示意图,最后根据图形作出正确的结果,比一比,看哪一组同学齐心协力,肯动脑、动手在较短时间内作出完整的、正确的答案。
(一石激起千层浪,同学们情绪高涨,绝大数学生很快进入了探索过程,过了一 会儿同学们陆陆续续举起手来)。
师:刚才同学们做的很好,下面请D、E代表他们所在一个小组将图形和解答过程写在黑板上,一人画图,一人写出解答过程。
图(3)
如图(3):在AB上截取AF=1m,过点F作FD⊥AB圆弧于点D,连结BD,过D作CD⊥AC,BC=BD=5 m,BF=AB-AF=4-1=3m。
在Rt △BFD 中,根据勾股定理得:
DF=BD2-BF2
=52-32
=4m
DF=AG=4m
所以此人应站在距树4m以外的地方较安全。
师:问此人站在距树3m到4m间为什么不行?
生D:树倒的过程中树稍会打着人。
师:同学们,你们说这一组同学的答案对吗?
学生:正确!(学生一致认为正确)
师:这组同学合作的很好,同学们请你们想想,开始时为什么会出现“人站在距树3m以外的地方”的结果呢?原因何在?(教室里又一片议论声)
生F: 开始解答时,只想到树倒后的结果,而忽略了树倒的过程,即把动态的过程静止化了。
师:多么漂亮的回答,所以平时我们解决实际问题时应联系具体情况,必要时画出图形,做到数形结合
离散数学课后习题答案第四章 篇3
4.判断下列集合对所给的二元运算是否封闭:(1)整数集合Z和普通的减法运算。
封闭,不满足交换律和结合律,无零元和单位元(2)非零整数集合普通的除法运算。不封闭
(R)和矩阵加法及乘法运算,其中n2。(3)全体nn实矩阵集合封闭 均满足交换律,结合律,乘法对加法满足分配律; 加法单位元是零矩阵,无零元;
乘法单位元是单位矩阵,零元是零矩阵;
(4)全体nn实可逆矩阵集合关于矩阵加法及乘法运算,其中n2。不封闭(5)正实数集合和运算,其中运算定义为:
不封闭
因为 1111111R(6)n关于普通的加法和乘法运算。
封闭,均满足交换律,结合律,乘法对加法满足分配律 加法单位元是0,无零元;
乘法无单位元(n1),零元是0;n1单位元是1(7)A = {a1,a2,,an} n运算定义如下:
封闭 不满足交换律,满足结合律,(8)S = 关于普通的加法和乘法运算。
封闭
均满足交换律,结合律,乘法对加法满足分配律(9)S = {0,1},S是关于普通的加法和乘法运算。
加法不封闭,乘法封闭;乘法满足交换律,结合律(10)S = ,S关于普通的加法和乘法运算。
加法不封闭,乘法封闭,乘法满足交换律,结合律
5.对于上题中封闭的二元运算判断是否适合交换律,结合律,分配律。
见上题
7.设 * 为Z上的二元运算x,yZ,X * Y = min(x,y),即x和y之中较小的数.(1)求4 * 6,7 * 3。
4,(2)* 在Z上是否适合交换律,结合律,和幂等律? 满足交换律,结合律,和幂等律
(3)求*运算的单位元,零元及Z中所有可逆元素的逆元。单位元无,零元1, 所有元素无逆元
8.SQQ Q为有理数集,*为S上的二元运算,,
< a,b >*
(2)*运算是否有单位元,零元? 如果有请指出,并求S中所有可逆元素的逆元。
设是单位元,
设是零元,
10.令S={a,b},S上有四个运算:*,分别有表10.8确定。
(a)
(b)
(c)
(d)
(1)这4个运算中哪些运算满足交换律,结合律,幂等律?(a)交换律,结合律,幂等律都满足,零元为a,没有单位元;(b)满足交换律和结合律,不满足幂等律,单位元为a,没有零元
a1a,b1b(c)满足交换律,不满足幂等律,不满足结合律
a(bb)aab, a(bb)(ab)b
没有单位元, 没有零元
(d)不满足交换律,满足结合律和幂等律
没有单位元, 没有零元
(2)求每个运算的单位元,零元以及每一个可逆元素的逆元。见上
(ab)baba
16.设V=〈 N,+,〉,其中+,分别代表普通加法与乘法,对下面给定的每个集合确定它是否构成V的子代数,为什么?
(1)S1=(2)S2= 是
不是 加法不封闭
(3)S3 = {-1,0,1} 不是,加法不封闭
第十一章部分课后习题参考答案
8.设S={0,1,2,3},为模4乘法,即
y=(xy)mod 4 “x,y∈S, x问〈S,〉是否构成群?为什么?
y=(xy)mod 4S,是S上的代数运算。解:(1)x,y∈S, x(2)x,y,z∈S,设xy=4k+r 0r3
(xy)z =((xy)mod 4)
z=r
z=(rz)mod 4 =(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理x(yz)=(xyz)mod 4 y)z = x1)=(1(y
z),结合律成立。所以,(x(3)x∈S,(xx)=x,,所以1是单位元。
(4)111,313, 0和2没有逆元 所以,〈S,9.设Z为整数集合,在Z上定义二元运算。如下: ” x,y∈Z,xoy= x+y-2 问Z关于o运算能否构成群?为什么? 〉不构成群 解:(1)x,y∈Z, xoy= x+y-2Z,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, 所以,x1y4x 所以〈Z,o〉构成群
101011.设G=01,01,101001,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,设xak,yal,则
xyakalaklalkalakyx 所以,G是交换群
17.设G为群,证明e为G中唯一的幂等元。
22证明:设e0G也是幂等元,则e0e0,即e0e0e,由消去律知e0e
18.设G为群,a,b,c∈G,证明
∣abc∣=∣bca∣=∣cab∣ 证明:先证设(abc)ke(bca)ke 设(abc)ke,则(abc)(abc)(abc)(abc)e,即
a(bc)(abc)(abc)a(bc)aa1e 左边同乘a1,右边同乘a得
(bca)(bca)(bca)(bca)(bac)ka1eae
反过来,设(bac)ke,则(abc)ke.由元素阶的定义知,∣abc∣=∣bca∣,同理∣bca∣=∣cab∣
19.证明:偶数阶群G必含2阶元。
证明:设群G不含2阶元,aG,当ae时,a是一阶元,当ae时,a至少是3阶元,因为群G时有限阶的,所以a是有限阶的,设a是k阶的,则a1也是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阶元,则a2e,a1a
a,bG,a1a,b1b,(ab)1ab,所以aba1b1(ba)1ba,与G为Abel群矛盾;
所以,G含至少含一个3阶元,设为a,则aa2,且a2aaa2。令ba2的证。
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,eN(a)
x,yN(a),则axxa,ayya
a(xy)(ax)y(xa)yx(ay)x(ya)(xy)a,所以xyN(a)
由axxa,得x1axx1x1xax1,x1aeeax1,即x1aax1,所以x1N(a)所以N(a)构成G的子群
31.设1是群G1到G2的同态,2是G2到G3的同态,证明12是G1到G3的同态。证明:有已知1是G1到G2的函数,2是G2到G3的函数,则1·2是G1到G3的函数。
a,bG1,(12)(ab)2(1(ab))2(1(a)1(b))
(2(1(a)))(2(1(b)))(12)(a)(12)(b)所以:1·2是G1到G3的同态。
33.证明循环群一定是阿贝尔群,说明阿贝尔群是否一定为循环群,并证明你的结论。
证明:设G是循环群,令G=,x,yG,令xak,yal,那么
xyakalaklalkalakyx,G是阿贝尔群
克莱因四元群,G{e,a,b,c}
eeabceabcaaecb bbceaccbae是交换群,但不是循环群,因为e是一阶元,a,b,c是二阶元。36.设,是5元置换,且
123451234521453,34512
(1)计算,,1,1,1;(2)将,1,1表成不交的轮换之积。
(3)将(2)中的置换表示成对换之积,并说明哪些为奇置换,哪些为偶置换。
1234512345112345解:(1) 4532143125 45123
11234512345121534 54132 )1(14253(2)(1425)(25))1(143(3)(14)(12)(15)奇置换,1(14)(12)(15)(13)偶置换
离散数学习题答案 篇4
(1){xR | x是大于1的整数}
(2){xR | x是某些整数的平方}
(3){2, {2}}
(4){{2},{{2}}}
(5){{2}, {2,{2}}}
(6){{{2}}} 解:
{2}是(3),(4),(5)的元素。2是(1),(3)的元素。下列哪些命题成立?哪些不成立?为什么?
(1){,{}}
(2) {,{}}(3){}{,{}}(4){{}}{,{}} 解:
(1)
成立(2)成立(3)成立(4)成立 设A集合={a,b,{a,b},}。下列集合由哪些元素组成?
(1)A-{a,b};(2){{a.b}}-A;(3){a,b}-A;(4)A--;(5)-A;(6)A-{}.解:
(1){{a,b},}(2)(3)(4)A(5)
(6){a,b,{a,b}} 假定A是ECNU二年级的学生集合,B是ECNU必须学离散数学的学生的集合。请用A和B表示ECNU不必学习离散数学的二年级的学生的集合。解:A∩B 设A,B和C是任意集合,判断下列命题是否成立,并说明理由。(1)若AB,CD,则A∪CB∪D,A∩CB∩D;(2)若AÐB,CÐD,则A∪CÐB∪D,A∩CÐB∩D;(3)若A∪B=A∪C,则B=C;(4)若A∩B=A∩C,则B=C; 解:
(1)成立
(2)不一定成立(3)不一定成立(4)不一定成立
11(5)设A、B和C是集合,请给出(A-B)(A-C)=成立的充要条件。
解:错误!未找到引用源。AB∪C
试求:
(1)P();(2)P(P());(3)P({,a,{a}})解:
(1){}(2){,{}}(3){,{},{a},{{a}}} 设A是集合,下列命题是否必定成立?(1)AP(A)(2)AP(A)(3){A}P(A)(4){A}P(A)解:
(1)成立
(2)不一定成立(3)不一定成立(4)成立
设A={a,b},B={b,c},下列集合由哪些元素组成?(1)A×{a}×B;(2)P(A)×B;(3)(B×B)×B;解:
(1){(a,a,b),(a,a,c),(b,a,b),(b,a,c)}(2){(,c),(,b),({a},c),({a},b),({b},c),({b},b),({a,b},c),({a,b},b)}(3){((b,b),c),((b,b),b),((b,c),c),((b,c),b),((c,b),c),((c,b),b),((c,c),c),((c,c),b)} 设A是任意集合,A3=(A×A)×A=A×(A×A)是否成立?为什么? 解:不成立。22 证明证明:
x,xBBABA
AxABAB,xAB,xAxBA
综上,BBA
n-1*24 nN,An是集合,令Bn=An-∪Ak。证明:
k=1(1)i,j∈N,i≠j,Bi∩Bj=(2)An=Bn
n∈Nn∈N证明:(1)i,j∈N, i≠j,不妨设i k1k1111(A1乔LAi-1乔AiAi+1 LAj-1) n-1Bn=An-UAkk=1 Bn⊆An An⊆Bn nNnN∀x,x∈UAn错误!未找到引用源。∃n∈N,使x∈An nÎN设n0为满足x∈An的最小的自然数 n0-1n0-1k于是x∈An,xÏ0k=1UAx ?Bn0An0-k=1UAk尬xn NUBn 所以UAnÍn挝NnUBnN综上,An=Bn nNnN 以1开头或者以00结束的不同的字节(8位的二进制串)有多少个? 解:27+26-25=160 数理逻辑(离散数学一分册)王捍贫 北京大学出版社 定价:15元 集合论与图论(离散数学二分册)耿素云 北京大学出版社 定价:19元 代数结构与组合数学(离散数学三分册)屈婉玲 北京大学出版社 定价:21元 离散数学习题集——数理逻辑与集合论分册 耿素云 北京大学出版社 定价:11.5元 离散数学习题集——图论分册 耿素云 北京大学出版社 定价:8元 离散数学习题集——抽象代数分册 张立昂 北京大学出版社 定价:8.8元 离散数学 左孝凌 刘永才 上海科学技术文献出版社 定价:16元 摘要:《离散数学》是计算机和信息专业的重要基础课。离散数学的传统考核方法是试卷考试。试卷考试能比较全面地考核学生掌握数学课程的情况,但是,不能充分发挥学生的主观能动性,不能更好地启发学生的创造性思维。针对此课程的特点,我们进行了考核方法的改革尝试,提高了学生的学习热情和积极性,培养了学生的创新能力,收到了较好的教学效果。 关键词:离散数学;考核方法;改革尝试 离散数学是现代数学的一个重要分支,近几十年来,在计算机科学的推动下,它已成为计算机基础理论的核心课程,是整个计算机学科教学体系中十分重要的环节。因此,也被称为是“计算机数学”。离散数学的内容十分广泛,凡是以离散量为研究对象的数学,均是离散数学。这门课程的内容繁杂,覆盖面广,教学时数又不太多,而且,概念多,理论性强,高度抽象。所以,如何使学生能真正学好这门课,并能学以致用,不断提高创新能力,就成为《离散数学》教学中应该研究和探讨的问题。尤其是对普通本科(工科)的离散数学教学更是如此。这也是我国21世纪应用型普通本科高校离散数学课程改革的研讨内容 根据应用型普通本科(工科)的培养目标和计划学时数,我们的离散数学课程不可能像重点大学那样要求。但是,离散数学又是计算机专业的重要基础课,所以,还必须要给学生打下坚实的基础,同时,还要在离散数学的教学中培养学生的学习能力、创新能力。因此,就必须要研究如何在课时不多的情况下,充分发挥教师的教学能力,充分调动学生学习的主观能动性,做好离散数学的教学。 北华大学在这方面做了一些探讨和专项研究,经过几年来的实践,探索了一条比较适合应用型普通本科(工科)的离散数学的教学路子,并收到了较好的教学效果,离散数学课程被评为校级优秀课。 一、《离散数学》考核方法的改革尝试 本校在计算机专业和信息专业都开设了《离散数学》课程。在课时有限的情况下,基于要充分调动学生学习的主观能动性,变被动学习为主动学习,真正学好这门课,并培养学生的学习能力、应用能力和创新能力的想法,从2002届起,在信息专业结合教学,对《离散数学》课程的考核方法做了改革尝试,具体内容如下: (一)针对课程特点,改进教学方法 考核方法的改革,须要做好教法上的改革。21世纪的学生更实际、更理性,他们对知识的掌握和渴求更有时代的鲜明特点,他们不单是为了学习而学习,更是为将来能更好地适应社会的发展而学习。而传统的数学课讲法是按照数学的体系来讲,数学的严谨性和公理化体系已经成为数学教师的习惯。从定义到定理,再基本计算和基本技巧的训练,使得学生们感觉数学枯燥、难学,不利于调动学生学习的兴趣和积极性,为此,我们做了教法上的改革。 1紧密联系实际,调动学生学习的积极性。《离散数学》的基本概念、基本理论和基本方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等计算机专业课程中;同时,《离散数学》课程本身对提高学生的概括抽象能力、逻辑思维能力、归纳构造能力、应用能力和创新能力等,也是十分有益的。所以,我们在教学中,一直注意提高学生对这门课程的认识,把不断树立学生对这门课程重要性的认识作为一个教学主线来抓。并且,在教学中随时联系具体内容,介绍在专业课中的相关应用。例如,图论中的平面图、树的研究对集成电路的布线、网络线路的铺设、网络信息流量的分析有极大的使用价值。利用布尔代数研究开关电路从而建立起一门完整的数字逻辑的理论,对计算机的逻辑设计起了很大的作用。我们的习题就有和学生专业课中相同的习题。在离散数学的教学中适当穿插一些其在计算机学科和信息学科中的一些小应用,就使学生产生了很大的兴趣和对离散数学课程的重视。有的学生甚至说:把离散数学都当成是专业课了。从而,在教学中,能不断地调动学生的学习积极性,让学生变被动学习为主动学习,充分发挥学生的主观能动性。 2离散数学的教学也是数学思想的教学。离散数学充分体现了近代数学思想,也是近代数学思想的产物。离散数学的教学,除了要教给学生离散数学知识外,更重要的是要通过训练,逐步实现学生思维方式的数字化。 我们在进行离散数学的教学中,反复结合实例,介绍离散数学的思想,训练学生看到实际问题能想到如何进行数字化。例如,关系的概念,就是非常简单非常典型的数字化的方法。整个离散数学处处体现着数字化的思想。只要我们在教学中不断注意启发提醒学生,自然就能让学生在这样的反复揭示中,逐渐实现思维方式的数字化。 3改善教与学的方法,提高学生知识类化的能力。由于离散数学概念多,概念抽象,而且是多门课程的组合,知识点繁杂。所以,在教学中,我们就注意使用知识类化的方法,使知识经验在应用过程中达到举一反三、触类旁通的效果。而教与学方法的改进,有利于知识的类化。为了使学生在解决问题时能更多地利用已经获得的知识、技能和方法对学习新知识的影响,教师应该使学生已有的知识与典型事例之间形成一定的“连结”,通过联想和对比,使学生将新知识、新概念,纳入到有意义的联想认识里,能够把新观念思想。原理在有秩序的体系中加以整理,以促进知识的积累和巩固。例如,在集合中,笛卡尔积是一个基本概念,A×B={(a,b)/a∈A,b∈B},在关系概念中的关系是一个有序偶的集合,它是A×B的一个子集。在图论中有向图的边,等等,这些都是与笛卡尔积相连的概念。注意在教学中把相关的概念不断地相连结,就能使繁杂的内容形成有关联的联想,使知识形成一个统一的整体,把知识学活。 (二)离散数学考核方法的改革 传统的考核方法就是试卷考试,考察学生的基本知识和基本技能,以及解难题的能力。我们在有些班级尝试做了一些考核方法的改革,把原来的试卷考试和平时的考核两部分,改成了三部分成绩的统一,即添加了一个新的内容:写离散数学的论文。把这个成绩的评定结果作为平时成绩的一个大部分。对离散数学考察课的班级,后来在成绩的比重中所占的比例更大些,甚至达到过50%。 离散数学的论文要求是:题目由老师给个大的范围,让学生在这个范围里选择要写的题目,字数3000字左右。要求有摘要、关键词,观点明确,主题鲜明,论述严谨。我们出的论文,都是一个具体的小问题,并不是很难,目的就是要训练学生自己去研究去创新。 开始的时候,学生叫苦连天,说不会写论文。我们给学生作了一些论文的写作指导,在课程陆续讲完的过程中,我们是逐步把论文题目给出来的。由学生们自己来抽选题目,给了学生比较充分的时间。 经过老师的鼓励和学生们的努力,并且因为和成绩相联,所以,交上来的论文大多数基本符合要求,有的写得还比较好。学生们说:写这个论文要看很多书,要比平时学习课程内容投入的精力还要大,对所写内容的理解上也深入了许多,尤其是在查阅资料上,知道了很多教科书上没介绍的内容。而且,还感到了创造的快乐,不论是从能力上还是知识上都是很有收获的。自从2002级以来,我们连续几年在信息专业做了这样的离散数学课程考核方法的改革尝试,收到了比较好的效果。 二、结语 通过教学改革实践和考核方法的改革尝试,提高了学生学习《离散数学》的积极性和学习热情,提高了学生们分析问题和解决问题的能力,增强了学生们的创新意识和能力。但是,这样的考核方法,增加了教师的工作量,需要教师付出更多的责任心和精力。我们希望能在不断地尝试和探索中,总结经验和教训,不断完善我们的改革尝试。 1.(2011重庆潼南中考)4.下列说法中正确的是() A.“打开电视,正在播放《新闻联播》”是必然事件 B.想了解某种饮料中含色素的情况,宜采用抽样调查 C.数据1,1,2,2,3的`众数是3 D.一组数据的波动越大,方差越小 2.(2011衢州市中考)3、在九年级体育中考中,某校某班参加仰卧起坐测试的一组女生(每组8人)测试成绩如下(单位:次/分):44,45,42,48,46,43,47,45.则这组数据的极差为() A、2B、4C、6D、8 3.数据0、1、2、3的标准差是() A.1B.2C.3D.4 4.样本方差的计算式S2=[(x1-30)2+(x2-30)]2+…+(xn-30)2]中,数字20和30分别表示样本中的() A.众数、中位数B.方差、标准差 C.样本中数据的个数、平均数D.样本中数据的个数、中位数 5.(2011湘潭市中考)2.数据:1,3,5的平均数与极差分别是() A.3,3B.3,4C.2,3D.2,4 6.一组数据的方差为S2,将该数据每一个数据,都乘2,所得到一组新数据的方差是() A.B.S2C.2S2D.4S2 7.已知一组数据:-1,x,0,1,-2的平均数是0,那么,这组数据的方差是() 1.设A={1,2,3,4},A上二元关系 R={(a,b)|a=b+2},S={(x,y)|y=x+1 or y= x2} 求RS,SR,SRS,S2,S 3,SRc。 RS={(3,2),(4,3),(4,1)} SR={(2,1),(3,2)} SRS={(2,2),(3,3),(3,1)} S2={(1,1),(1,3),(2,2),(2,4),(3,2),(4,1),(4,3)} S3={(1,2),(1,4),(2,1),(2,2),(2,3),(3,1),(3,3),(4,2),(4,4)} SRc={(1,4),(2,3),(4,4)} 2.A={a,b,c,d,e,f,g,h},给定A上关系R的 关系图如下: 图3-14 求最小正整数m,n,m<n,使Rm=Rn。 R1=R16 这是因为R15是8个顶点以及8个自回路,相 当于左图的点各走了5圈,左图的点各走了3圈,R16就成了原来的R. 3.证明: (1)(InA)IA(a,a)I2nA,aA,(a,a)IA,...,(a,a)IA, (b,b)InA,bA,(b,b)IA.(2)IARRIAR(a,b)R,a,bA,(a,a)IA,(b,b)IA,(a,b)IAR,(a,b)RIA,即RI AR,RRIA;(a,b)IAR,若(a,b)R,则(a,b)IAR,矛盾,得IARR;同理,RIAR.事实上,当|A|有限时,R与IA复合,相当于矩阵与 单位矩阵相乘,不会变化。 (3)(RIn2nA)IARR...Rn1(RIA)IAR;设(RIk2A)IARR...Rk (RIk1(I2A)...RkARR)(RIA)(RR2...Rk1)(I2ARR...Rk)IR2...RkRk1AR 4.判断下列等式是否成立(R,R1,R2均是A到B的 二元关系) (1)(Rccc1R2)R1R2对,(a,b)(Rc1R2)(b,a)R1R2(b,a)R 1or(b,a)R2(a,b)Rc1or(a,b)Rc2(a,b)Rcc1R2 (2)(Rcc1R2)R1Rc2对(a,b)(Rc1R2)(b,a)R1R2(b,a)R 1and(b,a)R2(a,b)Rcc1and(a,b)R2(a,b)Rcc1R2 (3)(R1R2)R1R2对cccc(a,b)(R1R2)(R1R2)c(b,a)R1R2(b,a)R1,(b,a)R2 (a,b)Rc1,(a,b)Rc2(a,b)Rcccc1R2R1R2(4)(AB)cAB否,例:A{1,2},B{3,4},AB{(1,3),(2,3),(1,4),(2,4)} (AB)c{(3,1),(3,2),(4,1),(4,2)}(5)c否,c 与的定义域,值域对换了一下.(6)(R)c(Rc)对,(a,b)(R)c(b,a)R(b,a)R(a,b)Rc(a,b)Rc(7)(Rcc1R2)R2Rc1否,R2的定义域不一定与R1的值域相同(8)如果Rcc1R2,则R1R2对,(a,b)Rc1,(b,a)R1R2,(a,b)Rc2.(9)如果R1Rcc2,则R1R2对,(a,b)Rc1,(b,a)R1R2,(a,b)Rc2,R1R2,(c,d)R2,(c,d)R1,(d,c)Rc2,而(d,c)Rc1.. (10)R1R2R2R1否,R 2的定义域不一定与R1的值域相同.5.设R1,R2是集合A上的二元关系,如果R2R1,其中r,s,t分别是自反闭包,对称闭包,传递闭包的 记号。试证明:(1)r(R2)r(R1)R2R1,IAIA, R2IAR1IA (2)s(R2)s(R1)R2Rcc1,R2R1 Rcc2R2R1R1 (3)t(R2)t(R1)R222R1(R2)1(R1)1(即R2R2R1R1)(a,b)R(a,b)(R2R1(R1)1b)R22)1(a,2,cA,(a,c),(c,b)R2R1,(a,b)R21,(a,b)(R1)1(a,b)t(R2),k,使(a,b)(R2)k(R1)kt(R1).6.设R1,R2,R3,R4分别是A到B,B到C,B到C,C到D的二元关系,证明 (1)R1(R2R3)R1R2R1R3(x,y)R1(R2R3)z,(x,z)R1,(z,y)R2or(z,y)R3z,(x,z)R1,(z,y)R2or(x,z)R 1,(z,y)R3(x,y)R1R2or(x,y)R1R3(x,y)R1R2R1R3 (2)R1(R2R3)R1R2R1R3(x,y)R1(R2R3)z,(x,z)R1,(z,y)R2and(z,y)R3z,(x,z)R 1,(z,y)R2and(x,z)R1,(z,y)R3(x,y)R1R2and(x,y)R1R3(x,y)R1R2R1R3(3)(4)类(1)(2)证明。 7.设R是A上的二元关系,证明对任意自然数m,n,(1)RmRnRmn(2)(Rm)nRmn 由归 (1)1)n1,Rm1RmR2)假定RmRnRmn{(a,b)|cA,(a,c)Rm,(c,b)Rn}n1RmR{(a,b)|cA,(a,c)Rm,(c,b)Rn1}其中,Rn1{(c,b)|dA,(c,d)Rn,(d,b)R}RmRn1{(a,b)|c,dA,(a,c)Rm,(c,d)Rn,(d,b)R}{(a,b)|dA,(a,d)Rmn,(d,b)R}RmnRR(mn)1Rm(n1) (2)1)n1,RmRm2)假定(Rm)nRmn(Rm)n1(Rm)nRmRmnRm 由(1)RmnmRm(n1)8.设R是A上的二元关系,|A|=n,证明存在 自然数s,t,使RsRt,且0st2n2,其中定义 R0{(a,a)|aA}。 0(ai,aj)R证:R(rij)nn,rij1(ai,aj)R至多有2n2个不同的Rk(kN)出现, 0k2n2,由鸽洞原理,(2n21)个Rk中必存在s,t,0st2n2,RsRt.9.R1,R2是A上的二元关系,判别下列命题正确与否 (1)如果R1,R2自反,则R1R2也自反。 对,aA,(a,a)R1,(a,a)R2,(a,a)R 1R2 (2)如果R1,R2反自反,则R1R2也反自反。 否,若(a,b)R1,(b,a)R2,(a,a)R1R2 (3)如果R1,R2对称,则R1R2也对称。 否,例:A{1,2,3},R1{(1,2),(2,1)},R2{(2,3),(3,2)},(1,2)R 1,(2,3)R2,(1,3)R1R2,而(3,1)R1R2 (4)如果R1,R2反对称,则R1R2也反对称。 否,例:A{1,2,3},R1{(1,2),(3,2)},R2{(2,3),(2,1)},(1,2)R,3)R,1,(22,(1,3)R1R2(3,2)R1,(2,1)R2,(3,1)R1R2 (5)如果R1,R2传递,则R1R2也传递。 否,例:A{1,2,3,4},R1{(1,1),(2,3)},R2{(1,2),(3,3)},(1,1)R1,(1,2)R2,(1,2)R1R2,(2,3)R1,(3,3)R2,(2,3)R1R2,但(1,3)R1R2 10.设A={a,b,c},以下分别给出一个P(A)上的二元 关系,确定它们哪些是自反的,反自反的,对称的,反对称的,传递的。 P(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}(1)x是y的一个真子集 R1{(x,y)|xy,x,yP(A)} 反自反,不对称,反对称,传递(2)x与y不相交 R2{(x,y)|xy,x,yP(A)} 不自反,也不反自反(),对称,不传递(3)xyA R3{(x,y)|xyA,x,yP(A)} 不自反,也不反自反{a,b,c}{a,b,c}A,对称,不传递。 11.设R是A上二元关系,证明R是传递的当且仅当 R2R。 任(a,b)∈R2,C,(a,c)(c,b)∈R ,由R传递(a,b)∈R , 即R2 R;若(a,b)∈R,(b,c)∈R , 即(a,c)∈R2 R , 所以R传递。 12.R是A上反对称的二元关系,问t(R)总是反对称 的吗? 010111否, 例: R001,t(R)111 100111 13.设R是A上的一个自反关系,证明当且仅当(a,b)和(a,c)属于R推出(b,c)属于R时,R是一个等价 关系。 若(a,b)∈R,又自反(a,a)∈R, 推出(b,a)∈R, 所以对称; 若(a,b)(b,c)∈R , 由对称(b,a)(b,c)∈R , 推出(a,c)∈R ,所以传递。若R等价,(a,b)(a,c)∈R , 由对称性(b,a)(a,c)∈R , 由传递性 ,(b,c)∈R。 14.设R是A上的一个对称和传递的关系,证明如果对A中的每个a,在A中存在b,使得(a,b)∈R,则R是一个等价关系。 aA,bA,(a,b)R,由对称性,(b,a)R,又由传递性,(a,a)R.15.设R是A上的一个传递和自反的关系,设T是 A上的一个二元关系,使得当且仅当(a,b)和(b,a)同时 属于R时,(a,b)∈T,证明T是一个等价关系。 a(a,a)∈R,(a,a)∈R =>(a,a)∈T 若(a,a)∈T,(a,b)(b,a)∈R , 即(b,a)(a,b)∈R =>(b,a)∈T 若(a,b)(b,c)∈T,(a,b)(b,a)(b,c)(c,b)∈R =>(a,c)∈R,(c,a)∈R =>(a,c)∈T 16.设R是A上一个二元关系,设 S={(a,b)|对某个C,(a,c)∈R且(c,b)∈R} 证明如果R是等价关系,则S也是等价关系。 a,(a,a)∈R,(a,a)∈R =>(a,a)∈S 若(a,b)∈S , 存在c,(a,c)(c,b)∈R 由R对称,(b,c)(c,a)∈R , 所以(b,a)∈S 若(a,b)(b,c)∈S 存在d,e (a,d)(d,b)(b,e)(e,c)∈R 由R传递(a,b)(b,c)∈R 所以(a,c)∈S 17.设R是A上的二元关系,对所有的xi,xj,xk∈A,如果xiRxj∧xjRxkxkRxi,则称R为循环关系,试证明当且仅当R是等价关系时,R才是自反的和循环的。(其中aRb表示(a,b)∈R)。 R等价, 当然自反,如果xiRxj且xjRxk则由传递性,xiRxk, 由对称性xkRxi,R是自反, 循环的; 若(a,b)∈R, 由R自反 a,(a,a)∈R, 又(a,b)∈R, 由循环(b,a)∈R,对称,若(a,b)(b,c)∈R,由循环(c,a)∈R, 由对称(a,c)∈R,传递。 18.设R1,R2是A上二元关系,证明(1)r(R1R2)r(R1)r(R2)(2)s(R1R2)s(R1)s(R2)(3)t(R1R2)t(R1)t(R2)(1)r(R1R2)(R1R2)IAR1IAR2R1(IAIA)R2(R1IA)(IAR2)(R1IA)(R2IA)r(R1)r(R2)(2)s(Rc1R2)(R1R2)(R1R2)Rcc1R2R1R2 (Rcc1R1)(R2R2)s(R1)s(R2)(3)(R1R2)2{(a,b)|c,(a,c)R1orR2,(c,b)R1orR2}R221R2R1R2R2R1 29 R2221R2(R1R2)用归纳法可证RnRnn12(R1R2) n,可得t(R1)t(R2)t(R1R2) 19.设A={a,b,c,d},A上二元关系 R={(a,b),(b,a),(b,c),(c,d)} (1)用矩阵算法和作图法求r(R),s(R),t(R)。(2)用Warshall算法求t(R)。 110001001111 r(R)=1110101011110011 s(R)= 0101 t(R)=0001000100100000 010010011101010i10110i211100001100010001 0000j20000j1,20000i3111111111111110i311111i41111j20001000100010000j20000j1,2,30000 20.讨论正实数集上二元关系R的几何意义。(1)R是自反的(2)R是对称的(3)R是传递的 (提示:以第一象限的点讨论) (1)第一象限角平分线 (2)关于对角平分线对称的点对集合 【离散数学习题答案】推荐阅读: 离散数学练习复习题05-01 离散数学 期末考试试卷答案06-30 离散数学答案屈婉玲08-31 离散数学每一章练习题06-23 离散数学归纳06-18 离散数学一07-22 离散数学考试范围05-12 离散数学期末总结05-13 离散数学课件06-04离散数学习题集 篇5
离散数学习题答案 篇6
离散数学习题答案 篇7
离散数学习题答案 篇8