离散数学课本习题

c0的整倍数的集合。C={1，2，3}E={2x|x∈I}a)b)=c){}d)={}e){a,b}{a,b,c,{a,b,c}}f){a,b}={a,b,c,{a,b,c}}g){a,b}{a,b,{a,b}}h){a,b}={a,b,{a,b}}b){1，{2，3}}c){{1，{2，3}}}1/152/15d){}e){,{}}f){{1，2}，{2，1，1}，{2，1，1，2}}g){{，2}，{2}}a){a，{b}}b){1，}c){x,y,z}d){，a,{a}}e)p({})10、设p(A)=p(B)。证明A=B。1.设U={1,2,3,4,5},A={1,4},B={1,2,5},C={2,4}。试求下列集合：a)A~B；b)(AB)~C；c)~(AB)；d)~A~B；e(A–B)–C；f)A–(B–C)；g)(AB)C；h)(AB)(BC)2.设A={n|n=I+且n<12},B={n|n=I+且n8},C={2n|n=I+},D={3n|n=I+}且E={2n-1|n=I+}试bc){10}；b)A(B-A)=;c)A(B-A)=AB;dA–(BC)=(A–B)(A–C)；e)A–(BC)=(A–B)(A–C)；f)A–(A–B)=AB；g)A-(B-C)=(A-B)(AC)。4.证明aAB仅当AB=；b)AB=BA；c)(AB)C=A(BC)；d)A(BC)=(AB)(AC)；e)(BC)A=(BA)(CA)。3/156.给出下列各式成立的充分必要条件，并加以证明。a(A-B)同(A-C)=A;c)(A-B)后(A-C)=A;d(A-B)后(A-C)=A;e)(A-B)中(A-C)=A;h)A-B=B;i)A-B=B-A;j)A中B=A；k)p(A)同p(B)=p(A同B);a)p(A)同p(B)坚p(A同B);b)p(A)后p(B)=p(A后B)。8.试求出同p和后p，其中p为：a){{气}}；b){气，{气}}；c){{a},{b},{a,b}}。0ii+i0innnxxxwwiwwA=A，我们称A和A分别为集合序列A,A,A,i012 a)A为由一切属于无限多个A的元素组成的集合；ib)A为由一切属于“几乎所有”的A的元素组成的集合。i4/154f)任意三个相邻整数的立方和能被9整除；nF=00F=11n倒。规定每人每次可扳倒1至m根，且扳倒最后一根直立的大头针者为获胜者。试证明：mnn获胜。数i≥i0及j≥j0，P(i,j)皆真。5/15c)(B×A)2用反例推翻下列命题：aA∪B)×(C∪D)=(A×C)∪(B×D)b)(A∩B)×(C∩D)=(A×C)∩(B×D)c)(A－B)×(C－D)=(A×C)－(B×D)dABCDAC(B×D)3、如果B∪CA，则(A×B)－(C×D)=(A－C)×(B－D)。这个命题对吗？如果对，则给予证明；如果不对，则举出反例。f)4、证明：若x=C且y=C，则<x,y>=p(p(C))。6、把三元偶<a,b,c>定义为{{a},{a,b},{a,b,c}}合适吗？说明理由。7、为了给出序偶的另一定义，选取两个不同集合A和B(例如取A=，B={})，并定义<a,b>={{a,A},{b,B}}。证明这个定义的合理性。第二章二元关系3、设R和R都是从集合A到集合B的二元关系。证明a)既是自反的，又是反自反的；b)既不是自反的，又不是反自反的；c)既是对称的，又是反对称的；d)既不是对称的，又不是反对称的。6、试判断下面的论断正确与否。若正确，请加以证明；若不正确，请给出反例。或传递的)。y6/15R2.对图给出的集合A={1,2,3}上的十二个二元关系的关系图，写出相应的关系矩阵，并指具有的性质。LDLD关系图，并写出它们的4.设R为任意的二元关系。证明7/15试求M，M，M，M及M。IAA上的恒等关系，R为A上的任意二元关系。证明a)R是自反的，当且仅当IAR；cRRR1；dR是反对称的，当且仅当RR-1=IA；e)R是传递的，当且仅当RoRIA。10、如果集合A上的二元关系R既是自反的，又是传递的，则R2=R。C8/157、设R为集合A上的二元关系，试证明：c)(R*)*=R*；RA1a){<i,j>|i,j=I且i·j>0}；b){<i,j>|i,j=I且i·j≥0且i与j不同时为0}；c){<i,j>|i,j=I且i≤0}；d){<i,j>|i,j==I且i·j≥0}；e){<i,j>|i,j=I且i|j}；f){<i,j>|i,j=I且有x=I使10x≤i≤j≤10(x+1)}；g){<i,j>|i,j=I且|i－j|≤10}；i){<i,j>|i,j=I且有x=I使10x<i<10(x+1)}；3、设集合A上的二元关系R是自反的。证明R为等价关系的充要条件是：若<a,b>,<a,c>=R,则<b,c>=R.试证明集合A上的二元关系R为A上的等价关系，当且仅当R是自反的和循环的。19/15是集合A∩B的划分。11、设A为恰含n个元素的非空有限集，则有多少个不同的A上的等价关系？其中秩为22、画出下列集合上的整除关系的哈斯图。a){1,2,3,4,6,8,12,24}；b){i|iI且1≤i≤14}；c){i|iI且5≤i≤20}；ssss4、设R是集合A上的二元关系。证明：a)半序关系的逆关系仍然是半序关系；b)全序关系的逆关系仍然是全序关系；c)良序关系的逆关系未必是良序关系；7、举出满足下列条件的半序结构<A,≤>的实例。a)<A,≤>为全序结构，且A的某些非空子集无最小元。b)<A,≤>不是全序结构，且A的某些非空子集无最大元。c)A的某些非空子集有下确界，但无最小元。d)A的某些非空子集有上界，但无上确定界。0/1512、I+在上定义二元关系R如下：8、设<A,≤>为半序结构。证明A的每个非空有限子集都至少有一个极小元和极大元。9、设<A,≤>为全序结构。证明A的每个非空有限子集都有一个最大元和最小元12、I+在上定义二元关系R如下：1212112212121212112212121212112212nRm当且仅当f(n)<f(m),或f(n)=f(m)且n≤m其中f(n)表示n的不同素因子的个数。证明<I+,R>为良序结构。第三章cxyxyRyx2、下列集合能定义部分函数吗？如果能，试求出它们的定义域和值域。a){<1,<2,3>>,<2,<3,4>>,<3,<1,4>>,<4,<1,4>>}；b){<1,<2,3>>,<2,<3,4>>,<3,<3,2>>}；c){<1,<2,3>>,<2,<3,4>>,<1,<2,4>>}；d){<1,<2,3>>,<2,<2,3>>,<3,<2,3>>}；1212123、设A为集合。若对任意s,s=p(A)皆令f(s,s)=s∩s，则f是从p(A)121212CfD写出f的全部序偶。c)有多少个和f具有相同的定义域和值域的函数g:A2→I?试证明a)f(99)=91；b)f(x)=91，其中0≤x≤100。0,h(x)=x。试求fof,hog,goh及它们的定义域和值域。3、对于下面的函数f，确定i)f是否为内射、满射和双射；a)f:R→Rf(x)=2xs={1}b)f:N→N×Nf(n)=<n+n+1>s={<2,2>}c)f:N→Nf(n)=2n+1s={2,3}d)f:I→Nf(x)=|x|s={1,0}e)f:[0,1]→[0,1]f(x)=2/x+1/4s=[0,1/2]f)f:[0,∞]→Rf(x)=1/(1+x)s}f(x)=xah)f:(0,1)→(0,∞)2/15f(x)=1/x4、设n∈I+，f:A→A。证明：如果f是内射(满射，双射)，则fn也是内射(满射，双射)。a)fof=fb)fof=IAc)fofof=IAa)找出它们的一个共同的左逆。fABnAff逆。2、用特征函数求下列各式成立的充分必要条件。dA∩B=A∪B。aA=R,B=(0,∞)；c)A=[0,1),B=(1/4,1/2]；d)A=[0,1],B=(0,1)。4、证明在n+1个小于等于2n的不同正整数中必有两数互素，其中n≥1。7天准备考试，并决定复习60小时，每天至少用1小时，3/158、求下列集合的基数，并加以证明。002.写出图抽象数学定义。3.证明在n阶简单有向图中，完全有向图的边数最多，其边数为n(n-1)。5.在一次集会中，相互认识的人会彼此握手。试证明与奇数个人握手的人数是偶数。6.证明图的两个图同构。7.证明：在任意六个人中，若没有三个人彼此都认识，则必有三个人彼此都不认识。8.证明图的两个图不同构。10.证明任何阶大于1的简单无向图必有两个结点的度相等。11.设n阶无向图G有m条边，其中nk个结点的度为k，其余结点的度为k+1，证明1.画出K4的所有不同构的子图，并说明其中哪些是生成子图，并找出互为补图的生成子GVEVVGV3.画出图的两个图的交、并和环和。 5.我们称与其补图同构的简单无向图为自补图。证明每个自补图的阶能被4整除或被44/151.考虑图.e)求出该图的直径。f)找出该图的所有回路。2.证明图中的基本路径必为简单路径。3.考虑图b)找出所有强分支，单向分支，弱分支。4.设v1,v2,v3是任意无向图(有向图)G的三个任意节点，以下三公式是否成立？如果成立给出证明，如果不成立举出反例。5.证明有向图的每个节点和每条边恰处于