离散数学习题集正文

PAGEPAGE1离散数学习题集正文第一篇：离散数学习题集离散数学习题集——图论分册耿素云北京大学出版社定价：8元数理逻辑(离散数学一分册)王捍贫北京大学出版社定价：15元集合论与图论(离散数学二分册)耿素云北京大学出版社定价：19元代数结构与组合数学(离散数学三分册)屈婉玲北京大学出版社定价：21元离散数学习题集——数理逻辑与集合论分册耿素云北京大学出版社定价：11.5元离散数学习题集——图论分册耿素云北京大学出版社定价：8元离散数学习题集——抽象代数分册张立昂北京大学出版社定价：8.8元离散数学左孝凌刘永才上海科学技术文献出版社定价：16元离散数学(理论· 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ·题解)左孝凌刘永才上海科学技术文献出版社定价：22元第二篇：离散数学离散数学试题（A卷答案）一、（10分）（1）证明(PQ)∧(QR)(PR)（2）求(P∨Q)R的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值。解：（1）因为((PQ)∧(QR))(PR)((P∨Q)∧(Q∨R))∨(P∨R)(P∧Q)∨(Q∧R)∨P∨R(P∧Q)∨((Q∨P∨R)∧(R∨P∨R))(P∧Q)∨(Q∨P∨R)(P∨Q∨P∨R)∧(Q∨Q∨P∨R)T所以，(PQ)∧(QR)(PR)。（2）(P∨Q)R(P∨Q)∨R(P∧Q)∨R(P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)M2∧M4∧M6m0∨m1∨m3∨m5所以，其相应的成真赋值为000、001、011、101、111：成假赋值为：010、100、110。二、（10分）分别找出使公式x(P(x)y(Q(y)∧R(x，y)))为真的解释和为假的解释。解：设论域为{1，2}。若P(1)＝P(2)＝T，Q(1)＝Q(2)＝F，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝F，则x(P(x)y(Q(y)∧R(x，y)))x(P(x)((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))(P(1)((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))(T((F∧F)∨(F∧F)))∧(T((F∧F)∨(F∧F)))(TF)∧(TF)F若P(1)＝P(2)＝T，Q(1)＝Q(2)＝T，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝T，则x(P(x)y(Q(y)∧R(x，y)))x(P(x)((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))(P(1)((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))(T((T∧T)∨(T∧T)))∧(T((T∧T)∨(T∧T)))(TT)∧(TT)T三、（10分）在谓词逻辑中构造下面推理的证明：每个喜欢步行的人都不喜欢做汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。解论域：所有人的集合。A(x)：x喜欢步行；B(x)：x喜欢坐汽车；C(x)：x喜欢骑自行车；则推理化形式为：x(A(x)B(x))，x(B(x)∨C(x))，xC(x)xA(x)下面给出证明：(1)xC(x)P(2)xC(x)T(1)，E(3)C(c)T(2)，ES(4)x(B(x)∨C(x))P(5)B(c)∨C(c)T(4)，US(6)B(c)T(3)(5)，I(7)x(A(x)B(x))P(8)A(c)B(c)T(7)，US(9)A(c)T(6)(8)，I(10)xA(x)T(9)，EG四、（10分）下列论断是否正确？为什么？(1)若A∪B＝A∪C，则B＝C。(2)若A∩B＝A∩C，则B＝C。(3)若AB＝AC，则B＝C。解(1)不一定。例如，令A＝{1}，B＝{1，2}，C＝{2}，则A∪B＝A∪C，但B＝C不成立。(2)不一定。例如，令A＝{1}，B＝{1，2}，C＝{1，3}，则A∩B＝A∩C，但B＝C不成立。(3)成立。因为若AB＝AC，对任意的x∈B，当x∈A时，有x∈A∩BxABxAC＝(A∪C)－(A∩C)x∈A∩Cx∈C，所以BC；当xA时，有xA∩B，而x∈Bx∈A∪B，所以x∈A∪B－A∩B＝ABx∈AC，但xA，于是x∈C，所以BC。同理可证，CB。因此，当AB＝AC时，必有B＝C。五、（10分）若R是集合A上的自反和传递关系，则对任意的正整数n，R＝R。证明当n＝1时，结论显然成立。设n＝k时，Rk＝R。当n＝k＋1时，Rk+1＝Rk*R＝R*R。下面由R是自反和传递的推导出R*R＝R即可。由传递性得R*RR。另一方面，对任意的∈R，由R自反得∈R，再由关系的复合得∈R*R，从而RR*R。因此，R＝R*R。由数学归纳法知，对任意的正整数n，Rn＝R。n六、（15分）设函数f：R×RR×R，f定义为：f()＝。(1)证明f是单射。(2)证明f是满射。(3)求逆函数f。(4)求复合函数f－1f和ff。证明(1)对任意的x，y，x1，y1∈R，若f()＝f()，则＝，x＋y＝x1＋y1，x－y＝x1－y1，从而x＝x1，y＝y1，故f是单射。(2)对任意的∈R×R，令x＝uw2uw2－1，y＝uw2，则f()＝＝，所以f是满射。uw2－1(3)f()＝。xyxy2xy(xy)2(4)ff()＝f(f())＝f()＝＝ff()＝f(f())＝f()＝＝。七、（15分）设X＝{1，2，3，4}，R是X上的二元关系，R＝{，，，，，，，，}(1)画出R的关系图。(2)写出R的关系矩阵。(3)说明R是否是自反、反自反、对称、传递的。解(1)R的关系图如图所示：(2)R的关系矩阵为：10M(R)11101110110000(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反自反的；由于矩阵不对称，R不是对称的；经过计算可得102M(R)111011101100M(R)，所以R是传递的。00八、（10分）若是群，H是G的非空子集，则是的子群对任意的a、b∈H有a*b－1∈H。3证明必要性：对任意的a、b∈H，由是的子群，必有b－1∈H，从而a*b－1∈H。充分性：由H非空，必存在a∈H。于是e＝a*a∈H。任取a∈H，由e、a∈H得a－1＝e*a－1∈H。对于任意的a、b∈H，有a*b＝a*(b)∈H，即a*b∈H。又因为H是G非空子集，所以*在H上满足结合律。综上可知，是的子群。九、（10分）给定二部图G＝，且|V1∪V2|＝m，|E|＝n，证明n≤m/4。证明设|V1|＝m1，则|V2|＝m－m1，于是n≤m1(m－m1)＝m1m－m222－1－1－1m12。因为(m2m1)20，即4mm1m1，所以n≤m2/4。4离散数学试题（B卷答案）一、（2022用公式法判断下列公式的类型：(1)(P∨Q)(PQ)(2)(PQ)(P∧(Q∨R))解：（1）因为(P∨Q)(PQ)(P∨Q)∨(P∧Q)∨(P∧Q)(P∧Q)∨(P∧Q)∨(P∧Q)m1∨m2∨m3M0所以，公式(P∨Q)(PQ)为可满足式。（2）因为(PQ)(P∧(Q∨R))((P∨Q))∨(P∧Q∧R))(P∨Q)∨(P∧Q∧R))(P∨Q∨P)∧(P∨Q∨Q)∧(P∨Q∨R)(P∨Q)∧(P∨Q∨R)(P∨Q∨(R∧R))∧(P∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)M0∧M1m2∨m3∨m4∨m5∨m6∨m7所以，公式(PQ)(P∧(Q∨R))为可满足式。二、（15分）在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。Q(x)：x是勤奋的；x是科学家；C(x)：解：论域：所有人的集合。H(x)：x是身体健康的；S(x)：x是事业获得成功的人；F(x)：x是事业半途而废的人；则推理化形式为：x(S(x)Q(x))，x(Q(x)∧H(x)C(x))，x(S(x)∧H(x))x(C(x)∨F(x))下面给出证明：(1)x(S(x)∧H(x))P(2)S(a)∧H(a)T(1)，ES(3)x(S(x)Q(x))P(4)S(a)Q(a)T(1)，US(5)S(a)T(2)，I(6)Q(a)T(4)(5)，I(7)H(a)T(2)，I(8)Q(a)∧H(a)T(6)(7)，I5(9)x(Q(x)∧H(x)C(x))P(10)Q(a)∧H(a)C(a)T(9)，Us(11)C(a)T(8)(10)，I(12)xC(x)T(11)，EG(13)x(C(x)∨F(x))T(12)，I三、（10分）设A＝{，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)B。解P(A)＝{，{}，{1}，{{1}}，{，1}，{，{1}}，{1，{1}}，{，1，{1}}}P(B)－{0}＝{，{0}，{{0}}，{0，{0}}－{0}＝{，{0}，{{0}}，{0，{0}}P(B)B＝{，{0}，{{0}}，{0，{0}}{0，{0}}＝{，0，{{0}}，{0，{0}}四、（15分）设R和S是集合A上的任意关系，判断下列命题是否成立？(1)若R和S是自反的，则R*S也是自反的。(2)若R和S是反自反的，则R*S也是反自反的。(3)若R和S是对称的，则R*S也是对称的。(4)若R和S是传递的，则R*S也是传递的。(5)若R和S是自反的，则R∩S是自反的。(6)若R和S是传递的，则R∪S是传递的。解(1)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R*S，故R*S也是自反的。(2)不成立。例如，令A＝{1，2}，R＝{}，S＝{}，则R和S是反自反的，但R*S＝{}不是反自反的。(3)不成立。例如，令A＝{1，2，3}，R＝{，，}，S＝{，}，则R和S是对称的，但R*S＝{，}不是对称的。(4)不成立。例如，令A＝{1，2，3}，R＝{，，}，S＝{，，}，则R和S是传递的，但R*S＝{，，}不是传递的。(5)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R∩S，所以R∩S是自反的。五、（15分）令X＝{x1，x2，…，xm}，Y＝{y1，y2，…，yn}。问(1)有多少个不同的由X到Y的函数？(2)当n、m满足什么条件时，存在单射，且有多少个不同的单射？(3)当n、m满足什么条件时，存在双射，且有多少个不同的双射？解(1)由于对X中每个元素可以取Y中任一元素与其对应，每个元素有n种取法，所以不同的函数共n个。(2)显然当|m|≤|n|时，存在单射。由于在Y中任选m个元素的任一全排列都形成X到Y的不同的单射，故不同的单射有Cnm!＝n(n－1)(n―m―1)个。(3)显然当|m|＝|n|时，才存在双射。此时Y中元素的任一不同的全排列都形成X到Y的不同的双射，6mm故不同的双射有m!个。六、（5分）集合X上有m个元素，集合Y上有n个元素，问X到Y的二元关系总共有多少个？解X到Y的不同的二元关系对应X×Y的不同的子集，而X×Y的不同的子集共有个2mn，所以X到Y的二元关系总共有2mn个。七、（10分）若是群，则对于任意的a、b∈G，必有惟一的x∈G使得a*x＝b。证明设e是群的幺元。令x＝a－1*b，则a*x＝a*(a－1*b)＝(a*a－1)*b＝e*b＝b。所以，x＝a－1*b是a*x＝b的解。若x∈G也是a*x＝b的解，则x＝e*x＝(a*a)*x＝a*(a*x)＝a*b＝x。所以，x＝a*b是a*x－1－1－1－1＝b的惟一解。八、（10分）给定连通简单平面图G＝，且|V|＝6，|E|＝12。证明：对任意f∈F，d(f)＝3。证明由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是d(f)＝2|E|＝24。若存在f∈fFF，使得d(f)＞3，则3|F|＜2|E|＝24，于是|F|＜8，与|F|＝8矛盾。故对任意f∈F，d(f)＝3。第三篇：离散数学第一章数学语言与证明方法例1设E={x|x是北京某大学学生},A,B,C,D是E的子集,A={x|x是北京人},B={x|x是走读生},C={x|x是数学系学生},D={x|x是喜欢听音乐的学生}.试描述下列各集合中学生的特征:(AD)~C={x|x是北京人或喜欢听音乐,但不是数学系学生}~AB={x|x是外地走读生}(A-B)D={x|x是北京住校生,并且喜欢听音乐}~D~B={x|x是不喜欢听音乐的住校生}例3证明:(1)AB=BA(交换律)证xxABxAxB(并的定义)xBxA(逻辑演算的交换律)xBA(并的定义)(2)A(BC)=(AB)(AC)(分配律)证xxA(BC)xA(xBxC)(并,交的定义)(xAxB)(xAxC)(逻辑演算的分配律)x(AB)(AC)(并,交的定义)(3)AE=E(零律)证xxAExAxE(并的定义)xA1(全集E的定义)1(逻辑演算的零律)xE(全集E的定义)(4)AE=A(同一律)证xxAExAxE(交的定义)xA1(全集E的定义)xA(逻辑演算的同一律)例4证明A(AB)=A（吸收律）证利用例3证明的4条等式证明A(AB)=(AE)(AB)(同一律)=A(EB)(分配律)=A(BE)(交换律)=AE(零律)=A(同一律)例5证明(A-B)-C=(A-C)-(B-C)证(A-C)-(B-C)=(A~C)~(B~C)(补交转换律)=(A~C)(~B~~C)(德摩根律)=(A~C)(~BC)(双重否定律)=(A~C~B)(A~CC)(分配律)=(A~C~B)(A)(矛盾律)=A~C~B(零律,同一律)=(A~B)~C(交换律,结合律)=(A–B)–C(补交转换律)例6证明(AB)(AC)=(BC)(AC))((AC)A例7设A,B为任意集合,证明:(1)AAB证xxAxAxB(附加律)xAB(2)ABA证xxABxAxBxA(化简律)(3)A-BA证xxA-BxAxBxA(化简律)(4)若AB,则P(A)P(B)证xxP(A)xAxB(已知AB)xP(B)例8证明AB=AB-AB.证AB=(A~B)(~AB)=(A~A)(AB)(~B~A)(~BB)=(AB)(~B~A)=(AB)~(AB)=AB-AB例3若A-B=A,则AB=证用归谬法,假设AB,则存在x,使得xABxAxBxA-BxB(A-B=A)xAxBxBxBxB,矛盾例4证明是无理数证假设是有理数,存在正整数n,m,使得=m/n,不妨设m/n为既约分数.于是m=n,m2=2n2,m2是偶数,从而m是偶数.设m=2k,得(2k)2=2n2,n2=2k2,这又得到n也是偶数,与m/n为既约分数矛盾.例6对于每个正整数n,存在n个连续的正合数.证令x=(n+1)!则x+2,x+3,…,x+n+1是n个连续的正合数:i|x+i,i=2,3,…,n+1例7判断下述命题是真是假:若AB=AC,则B=C.解反例:取A={a,b},B={a,b,c},C={a,b,d},有AB=AC={a,b}但BC,故命题为假.例8证明:对所有n1,1+2+…+n=n(n+1)/2证归纳基础.当n=1时,1=1(1+1)/2,结论成立.归纳步骤.假设对n1结论成立,则有1+2+…+n+(n+1)=n(n+1)/2+(n+1)(归纳假设)=(n+1)(n+2)/2得证当n+1时结论也成立.例9任何大于等于2的整数均可表成素数的乘积证归纳基础.对于2,结论显然成立.归纳步骤.假设对所有的k(2kn)结论成立,要证结论对n+1也成立.若n+1是素数,则结论成立;否则n+1=ab,2a,b由12n-33，则3y,G(x,y):x个体域分别取(a)人类集合,(b)全总个体域.解:(a)(1)设F(x):x爱美,符号化为xF(x)(2)设G(x):x用左手写字,符号化为xG(x)(b)设M(x):x为人，F(x),G(x)同(a)中(1)x(M(x)F(x))(2)x(M(x)G(x))M(x)称作特性谓词例4将下列命题符号化,并讨论其真值:(1)对任意的x,均有x2-3x+2=(x-1)(x-2)(2)存在x,使得x+5=3分别取(a)个体域D1=N,(b)个体域D2=R解记F(x):x2-3x+2=(x-1)(x-2),G(x):x+5=3(a)(1)xF(x)真值为1(2)xG(x)真值为0(b)(1)xF(x)真值为1(2)xG(x)真值为1例5将下面命题符号化:(1)兔子比乌龟跑得快(2)有的兔子比所有的乌龟跑得快(3)并不是所有的兔子都比乌龟跑得快(4)不存在跑得一样快的兔子和乌龟解用全总个体域,令F(x):x是兔子,G(y):y是乌龟,H(x,y):x比y跑得快,L(x,y):x和y跑得一样快(1)xy(F(x)G(y)H(x,y))(2)x(F(x)(y(G(y)H(x,y)))(3)xy(F(x)G(y)H(x,y))(4)xy(F(x)G(y)L(x,y))例6公式x(F(x,y)yG(x,y,z))x的辖域:(F(x,y)yG(x,y,z))，指导变元为xy的辖域:G(x,y,z)，指导变元为yx的两次出现均为约束出现y的第一次出现为自由出现,第二次出现为约束出现z为自由出现.例7公式x(F(x)xG(x))x的辖域:(F(x)xG(x))，指导变元为xx的辖域:G(x)，指导变元为xx的两次出现均为约束出现.但是,第一次出现的x是x中的x,第二次出现的x是x中的x.例8给定解释I如下:(a)个体域D=N(b)(c)(d)谓词说明下列公式在I下的含义,并讨论其真值(1)xF(g(x,a),x)x(2x=x)假命题(2)xy(F(f(x,a),y)F(f(y,a),x))xy(x+2=yy+2=x)假命题(3)xyzF(f(x,y),z)xyz(x+y=z)真命题(4)xF(f(x,x),g(x,x))x(2x=x2)真命题(5)F(f(x,a),g(x,a))x+2=2x不是命题(6)x(F(x,y)F(f(x,a),f(y,a)))x(x=yx+2=y+2)真命题例8(1)~(4)都是闭式,在I下全是命题.(5)和(6)不是闭式,在I下(5)不是命题,(6)是命题例9判断下列公式的类型:(1)x(F(x)G(x))取解释I1,D1=R,:x是整数,:x是有理数,取解释I2,D2=R,:x是整数,:x是自然数,非永真式的可满足式(2)(xF(x))(xF(x))这是pp的代换实例,pp是重言式,永真式(3)(xF(x)yG(y))yG(y)这是(pq)q的代换实例,(pq)q是矛盾式矛盾式例1消去公式中既约束出现、又自由出现的个体变项真命题假命题(1)xF(x,y,z)yG(x,y,z)uF(u,y,z)yG(x,y,z)换名规则uF(u,y,z)vG(x,v,z)换名规则或者xF(x,u,z)yG(x,y,z)代替规则xF(x,u,z)yG(v,y,z)代替规则(2)x(F(x,y)yG(x,y,z))x(F(x,y)tG(x,t,z))换名规则或者x(F(x,t)yG(x,y,z))代替规则例2设个体域D={a,b,c},消去下面公式中的量词:(1)x(F(x)G(x))(F(a)G(a))(F(b)G(b))(F(c)G(c))(2)x(F(x)yG(y))xF(x)yG(y)量词辖域收缩(F(a)F(b)F(c))(G(a)G(b)G(c))(3)xyF(x,y)x(F(x,a)F(x,b)F(x,c))(F(a,a)F(a,b)F(a,c))(F(b,a)F(b,b)F(b,c))(F(c,a)F(c,b)F(c,c))例3给定解释I:(a)D={2,3},(b)(c):x是奇数,:x=2y=2,:x=y.在I下求下列各式的真值:(1)x(F(f(x))G(x,f(x)))解(F(f(2))G(2,f(2)))(F(f(3))G(3,f(3)))(11)(01)1(2)xyL(x,y)解yL(2,y)yL(3,y)(L(2,2)L(2,3))(L(3,2)L(3,3))(10)(01)0例4证明下列等值式:x(M(x)F(x))x(M(x)F(x))证左边x(M(x)F(x))量词否定等值式x(M(x)F(x))x(M(x)F(x))例5求公式的前束范式(1)xF(x)xG(x)解xF(x)xG(x)量词否定等值式x(F(x)G(x))量词分配等值式解2xF(x)yG(y)换名规则xF(x)yG(y)量词否定等值式x(F(x)yG(y))量词辖域扩张xy(F(x)G(y))量词辖域扩张第4章关系例1=，求x,y.解3y4=2,x+5=yy=2,x=3例2A={0,1},B={a,b,c}AB={,,,,,}BA={,,,,,}A={},B=P(A)A={,}P(A)B=例3(1)R={|x,yN,x+y,,,,,}(2)C={|x,yR,x2+y2=1}，其中R代表实数集合，C是直角坐标平面上点的横、纵坐标之间的关系，C中的所有的点恰好构成坐标平面上的单位圆.(3)R={|x,y,zR,x+2y+z=3}，R代表了空间直角坐标系中的一个平面.例4A={0,1},B={1,2,3},R1={},R2=A×B,R3=,R4={},从A到B的关系:R1,R2,R3,R4,A上的关系R3和R4.计数：|A|=n,|B|=m,|A×B|=nm,A×B的子集有个.所以从A到B有元关系.|A|=n,A上有不同的二元关系.例如|A|=3,则A上有512个不同的二元关系.例5A={a,b,c,d},R={,,,,},R的关系矩阵MR和关系图GR如下：1110100000000100例1R={,,,},则domR=ranR=fldR=例2R={,,,}S={,,,,}R1=R∘S=S∘R=个不同的二例3设A={a,b,c,d},R={,,,},求R的各次幂,分别用矩阵和关系图表示.解R与R2的关系矩阵分别为010001000110101010102MM00010001000000000000例1A={a,b,c},R1,R2,R3是A上的关系,其中R1={,}R2={,,,}R3={}001010010000010101000000R2自反,R3反自反,R1既不自反也不反自反.例2设A＝{a,b,c},R1,R2,R3和R4都是A上的关系,其中R1＝{,}，R2＝{,,}R3＝{,}，R4＝{,,}R1对称、反对称.R2对称，不反对称.R3反对称，不对称.R4不对称、也不反对称例3设A＝{a,b,c},R1,R2,R3是A上的关系,其中R1＝{,}R2＝{,}R3＝{}R1和R3是A上的传递关系,R2不是A上的传递关系.例4证明若IAR，则R在A上自反.证任取x,xAIAR因此R在A上是自反的.例5证明若R=R1,则R在A上对称.证任取RR1R因此R在A上是对称的.例6证明若R∩R1IA,则R在A上反对称.证任取RRRR1R∩R1IAx=y因此R在A上是反对称的.例7证明若R∘RR,则R在A上传递.证任取，RRR∘RR因此R在A上是传递的.例8判断下图中关系的性质,并说明理由(1)不自反也不反自反；对称,不反对称；不传递.(2)反自反,不是自反；反对称,不是对称；传递.(3)自反，不是反自反；反对称，不是对称；不传递.例1设A={a,b,c,d},R={,,,,},R和r(R),s(R),t(R)的关系图如下图所示.(1)(2)(3)例1设A={1,2,…,8},如下定义A上的关系R：R={|x,y↔A∧x≡y(mod3)}其中x≡y(mod3)叫做x与y模3相等,即x除以3的余数与y除以3的余数相等.不难验证R为A上的等价关系,因为x↔A,有x≡x(mod3)x,y↔A,若x≡y(mod3),则有y≡x(mod3)x,y,z↔A,若x≡y(mod3),y≡z(mod3),则有x≡z(mod3)例2令A={1,2,…,8}，A关于模3等价关系R的商集为A/R={{1,4,7},{2,5,8},{3,6}}A关于恒等关系和全域关系的商集为：A/IA={{1},{2},…,{8}}A/EA={{1,2,…,8}}例3设A＝{a,b,c,d},给定1,2,3,4,5,6如下：1={{a,b,c},{d}}，2={{a,b},{c},{d}}3={{a},{a,b,c,d}}，4={{a,b},{c}}5={,{a,b},{c,d}}，6={{a,{a}},{b,c,d}}则1和2是A的划分,其他都不是A的划分.例4给出A＝{1,2,3}上所有的等价关系求解思路：先做出A的所有划分,然后根据划分写出对应的等价关系.A上的等价关系与划分之间的对应：4对应于全域关系EA5对应于恒等关系IA1,2和3分别对应于等价关系R1,R2和R3.其中R1={,}∪IAR2={,}∪IAR3={,}∪IA例5设A={1,2,3,4}，在AA上定义二元关系R：Rx+y=u+v，求R导出的划分.解AA={,,,,,,,,,,,,,,,}根据有序对的x+y=2,3,4,5,6,7,8将AA划分.(AA)/R={{},{,},{,,},{,,,},{,,},{,},{}}例6例7已知偏序集的哈斯图如下图所示,试求出集合A和关系R的表达式.A={a,b,c,d,e,f,g,h}R={,,,,,,,,}∪IA例8设偏序集如下图所示，求A的极小元、最小元、极大元、最大元.设B＝{b,c,d},求B的下界、上界、下确界、上确界.解：极小元：a,b,c,g；极大元：a,f,h；没有最小元与最大元.B的下界和最大下界都不存在,上界有d和f,最小上界为d.第5章函数例1设A={1,2,3},B={a,b},求BA.解BA={f0,f1,…,f7},其中f0={,,}f1={,,}f2={,,}f3={,,}f4={,,}f5={,,}f6={,,}f7={,,}例2判断下面函数是否为单射,满射,双射的,为什么?（1）f:R→R,f(x)=x2+2x1（2）f:Z+→R,f(x)=lnx,Z+为正整数集（3）f:R→Z,f(x)=x（4）f:R→R,f(x)=2x+1（5）f:R+→R+,f(x)=(x2+1)/x,其中R+为正实数集.解(1)f:R→R,f(x)=x2+2x1在x=1取得极大值0.既不是单射也不是满射的.(2)f:Z+→R,f(x)=lnx单调上升,是单射的.但不满射,ranf={ln1,ln2,…}.(3)f:R→Z,f(x)=x是满射的,但不是单射的,例如f(1.5)=f(1.2)=1.(4)f:R→R,f(x)=2x+1是满射、单射、双射的,因为它是单调函数并且ranf=R.(5)f:R+→R+,f(x)=(x2+1)/x有极小值f(1)=2.该函数既不是单射的也不是满射的.例3A=P({1,2,3}),B={0,1}{1,2,3}解A={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.B={f0,f1,…,f7},其中f0={,,},f1={,,},f2={,,},f3={,,},f4={,,},f5={,,},f6={,,},f7={,,}.令f:A→B,f()=f0,f({1})=f1,f({2})=f2,f({3})=f3,f({1,2})=f4,f({1,3})=f5,f({2,3})=f6,f({1,2,3})=f7例4A=[0,1]B=[1/4,1/2]构造双射f:A→B解令f:[0,1]→[1/4,1/2]f(x)=(x+1)/4例5A=Z,B=N，构造双射f:A→B将Z中元素以下列顺序排列并与N中元素对应：Z：0112233…↓↓↓↓↓↓↓N：0123456…则这种对应所表示的函数是：x02xf:ZN,f(x)2x1x0例1设f:R→R,g:R→Rx2x3f(x)x32g(x)x2求f∘g,g∘f.如果f和g存在反函数,求出它们的反函数.解fg:RRx22x3fg(x)x30gf:RR(x2)2gf(x)2x1x1f:R→R不存在反函数；g:R→R的反函数是g1:R→R,g1(x)=x2第6章图例1下述2组数能成为无向图的度数列吗?(1)3,3,3,4;(2)1,2,2,3解(1)不可能.有奇数个奇数.(2)能例2已知图G有10条边,4个3度顶点,其余顶点的度数均小于等于2,问G至少有多少个顶点?解设G有n个顶点.由握手定理,43+2(n-4)210解得n8例3已知5阶有向图的度数列和出度列分别为3,3,2,3,3和1,2,1,2,1,求它的入度列解2,1,1,1,2例4证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.证用反证法.假设存在这样的多面体,作无向图G=,其中V={v|v为多面体的面},E={(u,v)|u,vVu与v有公共的棱uv}.根据假设,|V|为奇数且vV,d(v)为奇数.这与握手定理的推论矛盾.例5设9阶无向图的每个顶点的度数为5或6,证明它至少有5个6度顶点或者至少有6个5度顶点.证讨论所有可能的情况.设有a个5度顶点和b个6度顶点(1)a=0,b=9;(2)a=2,b=7;(3)a=4,b=5;(4)a=6,b=3;(5)a=8,b=1(1)~(3)至少5个6度顶点,(4)和(5)至少6个5度顶点方法二假设b9-5=4.由握手定理的推论,a6例6画出4阶3条边的所有非同构的无向简单图解总度数为6,分配给4个顶点,最大度为3,且奇度顶点数为偶数,有下述3个度数列:(1)1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.1,1,1,31,1,2,2例7画出3个以1,1,1,2,2,3为度数列的非同构的无向简单图0,2,2,2例1右图有4个面R1的边界:aR2的边界:bceR3的边界:fgR0的边界:abcdde,fgdeg(R1)=1deg(R2)=3deg(R3)=2deg(R0)=8例2右边2个图是同一平面图的平面嵌入.R1在(1)中是外部面,在(2)中是内部面;R2在(1)中是内部面,在(2)中是外部面.R3R1R3R2(1)R2R1(2)说明:(1)一个平面图可以有多个不同形式的平面嵌入,它们都同构.(2)可以通过变换(测地投影法)把平面图的任何一面作为外部面例3证明K5和K3,3不是平面图证K5:n=5,m=10,l=3K3,3:n=6,m=9,l=4不满足定理6.15的条件例5证明下面2个图均为非平面图.\与K3,3同胚也可收缩到K3,3与K5同胚也可收缩到K5例6画出所有非同构的6阶11条边的简单连通非平面图解在K5(5阶10条边)上加一个顶点和一条边在K3,3(6阶9条边)上加2条边例1某中学有3个课外活动小组:数学组,计算机组和生物组.有赵,钱,孙,李,周5名学生,问分别在下述3种情况下,能否选出3人各任一个组的组长?(1)赵,钱为数学组成员,赵,孙,李为计算机组成员,孙,李,周为生物组成员.(2)赵为数学组成员,钱,孙,李为计算机组成员,钱,孙,李,周为生物组成员.(3)赵为数学组和计算机组成员,钱,孙,李,周为生物组成员.解数计生数计生赵钱孙李周赵钱孙李周(1(2数计生赵钱孙李周(3(1),(2)有多种 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ,(3)不可能例2证明下述各图不是哈密顿图:(a(b(c)(c)中存在哈密顿通路例3证明右图不是哈密顿图证假设存在一条哈密顿回路,a,f,g是2度顶点,边(a,c),(f,c)和(g,c)必在这条哈密顿回路上,从而点c出现3次,矛盾.abcfdeg此外,该图满足定理6.10的条件,这表明此条件是必要、而不充分的.又,该图有哈密顿通路.例4有7个人,A会讲 英语 关于好奇心的名言警句英语高中英语词汇下载高中英语词汇 下载英语衡水体下载小学英语关于形容词和副词的题 ,B会讲英语和汉语,C会讲英语、意大利语和俄语,D会讲日语和汉语,E会讲德语和意大利语,F会讲法语、日语和俄语,G会讲法语和德语.问能否将他们沿圆桌安排就坐成一圈,使得每个人都能与两旁的人交谈?解作无向图,每人是一个顶点,2人之间有边他们有共同的语言.GFEDABCACEGFDBA是一条哈密顿回路,按此顺序就坐即可.第四篇：离散数学自学学习体会专业：计算机姓名：范文芳学号：成绩：院校：离散数学是计算机科学与技术专业的基础核心课程。通过本课程的学习，使学生具有现代数学的观点和方法，并初步掌握处理离散结构所必须的描述工具和方法。同时，也要培养学生抽象思维和慎密概括的能力，使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力，为学生以后学习计算机基础理论与专业课程打下良好的基础。学习离散数学有两项最基本的任务：其一是通过学习离散数学，使学生了解和掌握在后续课程中要直接用到的一些数学概念和基本原理，掌握计算机中常用的科学论证方法，为后续课程的学习奠定一个良好的数学基础；其二是在离散数学的学习过程中， 培训 焊锡培训资料ppt免费下载焊接培训教程 ppt 下载特设培训下载班长管理培训下载培训时间表下载 自学能力、抽象思维能力和逻辑推理能力，以提高专业理论水平。因此学习离散数学对于计算机、通信等专业后续课程的学习和今后从事计算机科学等工作是至关重要的。但是由于离散数学的离散性、知识的分散性和处理问题的特殊性，使部分学生在刚刚接触离散数学时，对其中的一些概念和处理问题的方法往往感到困惑，特别是在做证明题时感到无从下手，找不到正确的解题思路。因此，对离散数学的学习方法给予适当的指导和对学习过程中遇到的一些问题分析是十分必要的。一、认知离散数学离散数学是计算机科学基础理论的核心课程之一，是计算机及应用、通信等专业的一门重要的基础课。它以研究量的结构和相互关系为主要目标，其研究对象一般是有限个或可数个元素，充分体现了计算机科学离散性的特点。学习离散数学的目的是为学习计算机、通信等专业各后续课程做好必要的知识准备，进一步提高抽象思维和逻辑推理的能力，为计算机的应用提供必要的描述工具和理论基础。1．定义和定理多离散数学是建立在大量定义、定理之上的逻辑推理学科，因此对概念的理解是学习这门课程的核心。在学习这些概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体则是大量的定理和性质。在考试中有一部分内容是考查学生对定义和定理的识记、理解和运用，因此要真正理解离散数学中所给出的每个基本概念的真正的含义。比如，命题的定义、五个基本联结词、公式的主析取范式和主合取范式、三个推理规则以及反证法；集合的五种运算的定义；关系的定义和关系的四个性质；函数（映射）和几种特殊函数（映射）的定义；图、完全图、简单图、子图、补图的定义；图中简单路、基本路的定义以及两个图同构的定义；树与最小生成树的定义。掌握和理解这些概念对于学好离散数学是至关重要的。2.方法性强在离散数学的学习过程中，一定要注重和掌握离散数学处理问题的方法，在做题时，找到一个合适的解题思路和方法是极为重要的。如果知道了一道题用怎样的方法去做或证明，就能很容易地做或证出来。反之，则事倍功半。在离散数学中，虽然各种各样的题种类繁多，但每类题的解法均有规律可循。所以在听课和平时的复习中，要善于总结和归纳具有规律性的内容。在平时的讲课和复习中，老师会总结各类解题思路和方法。作为学生，首先应该熟悉并且会用这些方法，同时，还要勤于思考，对于一道题，进可能地多探讨几种解法。3.抽象性强离散数学的特点是知识点集中，对抽象思维能力的要求较高。由于这些定义的抽象性，使初学者往往不能在脑海中直接建立起它们与现实世界中客观事物的联系。不管是哪本离散数学教材，都会在每一章中首先列出若干个定义和定理，接着就是这些定义和定理的直接应用，如果没有较好的抽象思维能力，学习离散数学确实具有一定的困难。因此，在离散数学的学习中，要注重抽象思维能力、逻辑推理能力的培养和训练，这种能力的培养对今后从事各种工作都是极其重要的。在学习离散数学中所遇到的这些困难，可以通过多学、多看、认真分析讲课中所给出的典型例题的解题过程，再加上多练，从而逐步得到解决。在此特别强调一点：深入地理解和掌握离散数学的基本概念、基本定理和结论，是学好离散数学的重要前提之一。所以，同学们要准确、全面、完整地记忆和理解所有这些基本定义和定理。4.内在联系性离散数学的三大体系虽然来自于不同的学科，但是这三大体系前后贯通，形成一个有机的整体。通过认真的分析可寻找出三大部分之间知识的内在联系性和规律性。如：集合论、函数、关系和图论，其解题思路和证明方法均有相同或相似之处。二、认知解题 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 一般来说，离散数学的考试要求分为：了解、理解和掌握。了解是能正确判别有关概念和方法；理解是能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。为了考核学生对这三部分的理解和掌握的程度，试题类型一般可分为：判断题、填空题、选择题、计算题和证明题。判断题、填空题、选择题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算；计算题主要考核学生的基本运用技能和速度，要求写出完整的计算过程和步骤；证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出严格的推理和论证过程。学习离散数学的最大困难是它的抽象性和逻辑推理的严密性。在离散数学中，假设让你解一道题或证明一个命题，你应首先读懂题意，然后寻找解题或证明的思路和方法，当你相信已找到了解题或证明的思路和方法，你必须把它严格地写出来。一个写得很好的解题过程或证明是一系列的陈述，其中每一条陈述都是前面的陈述经过简单的推理而得到的。仔细地写解题过程或证明是很重要的，既能让读者理解它，又能保证解题过程或证明准确无误。一个好的解题过程或证明应该是条理清楚、论据充分、表述简洁的。针对这一要求，在讲课中老师会提供大量的典型例题供同学们参考和学习。通过离散数学的学习和训练，能使同学们学会在离散数学中处理问题的一般性的规律和方法，一旦掌握了离散数学中这种处理问题的思想方法，学习和掌握离散数学的知识就不再是一件难事了。复习离散数学的整个过程可大致分为三个阶段。第一阶段，大量进行知识储备的阶段。离散数学是建立在大量定义上面的逻辑推理学科。因而对概念的理解是我们学习这门学科的核心。由于这些定义非常抽象，初学者往往不能在脑海中建立起它们与现实世界中客观事物的联系。对于跨专业自学的朋友来说更是如此。这是离散数学学习中的第一个困难。因此，对于第一遍复习，我们提出一个最为重要的要求，即准确、全面、完整地记忆所有的定义和定理。具体做法可以是：在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记，直到能够全部正确地默写出来为止。无须强求一定要理解，记住并能准确复述各定义定理是此阶段的最高要求。也不需做太多的题（甚至不做课后习题也是可以的，把例题看懂就行），重心要放在对定义和定理的记忆上。请牢记，这是为未来的向广度和深度扩张作必要的准备。这一过程视各人情况不同耗时约在一到两个月内。第二阶段，深入学习，并大量做课后习题的阶段。这是最漫长的一个阶段，耗时也很难估计，一般来说，若能熟练解出某一章75%以上的课后习题，可以考虑结束该章。解离散数学的题，方法非常重要，如果拿到一道题，立即能够看出它所属的类型及关联的知识点，就不难选用正确的方法将其解决，反之则事倍功半。例如在命题逻辑部分，无非是这么几种题目：将自然语言表述的命题符号化，等价命题的相互转化（包括化为主合取范式与主析取范式），以给出的若干命题为前提进行推理和证明。相应的对策也马上就可以提出来。以推理题为例，主要是利用P、T规则，加上蕴涵和等价公式表，由给定的前提出发进行推演，或根据题目特点采用真值表法、CP规则和反证法。由此可见，在平常复习中，要善于总结和归纳，仔细体会题目类型和此类题目的解题套路。如此多作练习，则即使遇到比较陌生的题也可以较快地领悟其本质，从而轻松解出。“熟读唐诗三百首，不会做诗也会吟。”要是拿到一本习题集，从头到尾做过，甚至背会的话。那么，在考场上就会发现绝大多数题见过或似曾相识。这时，要取得较好的成绩也就不是太难的事情了。这一情况具有普遍性，对许多院校的考试都适用。第三阶段，进行真题模拟训练，提高整体水平和综合能力的阶段。这一阶段从第二阶段结束一直持续到考试。除了我们使用的课本外，应尽可能地弄到报考院校的专业课历年试题。因为每个单位对该科目的侧重点毕竟有不同，从历年试题中可以获取许多有用的信息。这些历年试题此时就有了巨大的作用。第五篇：离散数学习题集合论1.A={,1}，B={{a}}求A的幂集、A×B、A∪B、A+B。2.A={1,2,3,4,5},R={(x,y)|x4.A={a,b,c},R=IA∪{(a,b),(b,a)}，求a和b关于R的等价类。5.R是A上的等价关系，A/R={{1,2}，{3}},求A，R。6.请分别判断以下结论是否一定成立，如果一定成立请证明，否则请举出反例。①如果A∪BC，则AC或者BC。②如果A×B=A×C且A，则B=C。27.如果R是A上的等价关系，R,r(R)是否一定是A上的等价关系？证明或举例。8.已知A∩CB∩C,A-CB-C,证明：AB。9.证明：AX(B∩C)=(AXB)∩(AXC)10.证明：P(A)∪P(B)P(A∪B)-111.证明：R[sym]iffR=R-1212.证明：r(R)=R∪IA,S(R)=R∪R,t(R)=R∪R∪...13.证明：s(R∪S)=s(R)∪s(S)14.R是A上的关系，证明：如果R是对称的，则r(R)也是对称的。15.I是整数集，R={(x,y)|x-y是3的倍数}，证明：R是I上的等价关系。16.如果R是A上的等价关系，则A/R一定是A的划分。17.R是集合A上的自反关系，S是A上的自反和对称关系，证明t(R∪S)是A上的等价关系。18.I是正整数集合，R是I×I上的二元关系，R={|xv=yu},证明：R是等价关系。19.f:AB，R是B上的等价关系，令S={|xA且yA且R}，证明：S是A上的等价关系。2022R是集合A上的自反关系，S是A上的自反和对称关系，证明t(R∪S)是A上的等价关系。21.P和Q都是集合A上的划分，请问P∪Q，P-Q是否是A上的划分，22.RAXA,R[irref]且R[tra],证明：r(R)是A上的偏序关系。23.画出{1,2,3,4,6}上整除关系的哈斯图，求{2,3,6}的4种元素。24.A={a,b,c,d,e,f,g},R={(a,c),(a,e),(b,d),(b,f),(d,e),(d,f)},S=tr(R),画出S的哈斯图并求{b,c,d,f}的极大元等8种元素。25.f:A→B,g:B→C都是单（满）射，证明：复合映射gof一定是单（满）射。26.f:A→B,g:B→C，gof是单射，请问f和g是否一定是单射？请证明或举出反例。27.R是实数集，f:R×RR×R,f()=,请问f是否为单射？是否为满射？分别证明或举反例。28.已知B∩C=,令f：P(B∪C)P(B)×P(C)，对XP(B∪C),令f(X)=(B∩X,C∩X),证明：f是双射。代数系统1.是模8加群，Z8={0,1,2,3,4,5,6,7},+8是模8加法，求出的单位元、每个元素的逆元、所有的生成元和所有的子群。2.求的单位元，零元，每个元素的逆元，每个元素的阶，它是循环群吗？求出它所有的子群。3.R是实数集，在R上定义运算*为x*y=x+y+xy,问：是代数系统吗？有单位元吗？每个元素都有逆元吗？***4.R是非零实数集合，是代数系统，对于R中元素*x,y，令xoy=2x+2y-2。请问中是否存在单位元、零元、哪些元素有逆元？运算o是否满足交换律和结合律。分别说明理由。5.R是实数集，R上的6运算定义如下：对R中元素x,y，f1()=x+y；f2()=x-y；f3()=xy；f4()=x/y；f5()=max{x,y}；f6()=|x-y|。问：哪些满足交换律、结合律、有单位元、有零元？说明理由。6.是一个群，证明：G是交换群当且仅当对任意G中222元素x,y,都有等式(xy)=xy成立。7.证明：如果群G中每个元素的逆元素都是它自已，则G是交换群。8.循环群一定是交换群。9.证明：阶为素数的群一定是循环群。-110.是一个群，uG,定义运算*：x*y=xouoy,证明：是一个群。11.整数集Z上定义运算*：对任意整数x和y,x*y=x+y-4,其中+，-为普通加减法。证明：是一个群。12.证明：如果群G中至少有两个元素，则群中没有零元。13.S是G的子群，证明：{x|x是S的左陪集}是G的一个划分14.是一个群,aG,n是a的阶(周期)，证明：k是的一个子群。15.H，K都是群G的子群，请问H∩K,H∪K,H-K是否一定是G的子群？16.H，K是G的两个子群，aG,试证：aHaK当且仅当HK。17.G={1,3,4,5,9},*是模11的乘法(即x*y=xymod11)，请问(G,*)是否构成群？n18.是群，e是单位元，aG,a的阶为k,证明：a=e当且仅当n是k的倍数。19.S是G的子群，证明：{x|x是S的左陪集}是G的一个划分2022G是群，证明：S={aG|xG(ax=xa)},则S是G的子群。21.是偶数阶群，则G中必存在2阶元素。22.证明：6个元素的群在同构意义下只有两个。++23.R为实数集，R为正实数集，与是否同构？24.是有限群，证明：G不可能表示成两个真子群的并。25.图论1.如何判断二部图？完全图、完全二部图的边数。2.如何求E回路？3.Petersen图是否为E图或H图。4.哪些完全图是H图？哪些完全图是E图？5.n为何值时轮图为H图？6.如何求最小生成树。7.证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。8.证明：如果G是欧拉图，则其边图L(G)也是欧拉图。9.证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。10.G是平面图，G有m条边，n个顶点，证明：m3n-6。并由此证明K5不是平面图。11.证明：有6个顶点的简单无向图G和它的补图中