《离散数学课本习题》由会员分享，可在线阅读，更多相关《离散数学课本习题（17页珍藏版）》请在金锄头文库上搜索。
1、习题1.11、 用列举法给出下列集合：a) 小于5的非负整数的集合；b) 10到20之间的素数的集合；c) 不超过65的12之正整数倍数的集合。2、 用命题法给出下列集合：a) 不超过100的自然数的集合；b) Ev和Od；c) 10的整倍数的集合。3、 用归纳定义法给出下列集合：a) 允许有前0的十进制无符号整数的集合；b) 不允许有前0的十进制无符号整数的集合；c) 允许有前0和后0的有有限小数部分的十进制无符号实数的集合；d) 不允许有前0的十进制无符号偶数的集合；e) Ev和Od；f) 集合0，1，4，9，16，25，。4、 确定下列集合中哪些是相等的：A=x|x为偶数且x2为奇数B=
2、x|有yI使x=2yC=1，2，3D=0，2，-2，5，-3，4，-4E=2x|xIF=3，3，2，1，2G=x|有xI且x3-6x2-7x-6=05、 确定下列关系中哪些是正确的，并简单说明理由。a) b) c) d) e) a, ba, b, c,a, b, cf) a, ba, b, c,a, b, cg) a, ba, b,a, bh) a, ba, b,a, b6、 设A、B和C为集合。证明或用反例推翻以下的各个命题：a) 若AB且BC，则AC。b) 若AB且BC，则AC。c) 若AB且BC，则AC。d) 若AB且BC，则AC。7、 若A、B为集合，则AB与AB能同时成立吗？请证明你
3、的结论。8、 列举出下列集合中每个集合的所有子集：a) 1，2，3b) 1，2，3c) 1，2，3d) e) , f) 1，2，2，1，1，2，1，1，2g) ，2，29、 给出下列集合的幂集：a) a，bb) 1，c) x, y, zd) ，a,ae) ()10、设 (A)= (B)。证明A=B。1. 设U=1,2,3,4,5,A=1,4,B=1,2,5,C=2,4。试求下列集合：a) A B；b) (A B) C；c) (A B)；d) A B；e) (A B) C；f) A (B C)；g) (A B) C；h) (A B) (B C)2. 设A=n|nI+且n10；e) n|n为正偶数
4、且n10，或n为奇数且n9。3. 证明：a) 如果AB且CD，则ACBD且ACBD；b) A(B-A)=;c) A(B-A)=AB;d) A (B C)= (A B) (A C)；e) A (B C)= (A B) (A C)；f) A (A B) = A B；g) A-(B-C)=(A-B)(AC)。4. 证明a) A=B当且仅当AB=；b) AB= BA；c) (AB)C= A(B C)；d) A(B C)=(AB)(AC)；e) (B C) A=(BA)(CA)。5. 判断一下结论是否成立，如果或成立，就给予证明，如果不成立，就用文氏图加以说明。a) 若ACBC且ACBC，则AB；b)
5、若AB=AC且AB=AC，则B=C；c) 若AB=AC，则B=C;d) 若AB=AC，则B=C;e) AB=AC，则B=C;f) 若ABC，则AB或AC；g) 若BCA，则BA或CA。6. 给出下列各式成立的充分必要条件，并加以证明。a) (A-B)(A-C)=A;b) (A-B)(A-C)=;c) (A-B)(A-C)=A;d) (A-B)(A-C)= A;e) (A-B)(A-C)=A;f) (A-B)(A-C)= ;g) AB=AB;h) A-B=B; i) A-B=B-A;j) AB=A；k) (A)(B)=(AB);7. 设A，B为任意两个集合，证明：a) (A)(B)(AB);b)
6、 (A)(B)=(AB)。8. 试求出和，其中为：a) ；b) ，；c) a,b,a,b。9. 设且，且，。 证明10. 设且，试求和11. 设且。试求和。12. 设， ，我们称和分别为集合序列的上极限和下极限，证明：a) 为由一切属于无限多个的元素组成的集合；b) 为由一切属于“几乎所有”的的元素组成的集合。习题1.31、 用归纳法证明：a)；b)2+22+23+2n=2n+1-2；c)2n=2n；d)3|n3+2n;e)123+234+n(n+1)(n+2) =f)任意三个相邻整数的立方和能被9整除；g)11n+2+122n+1是133的倍数；h)若nI+则。2、设a0，a1，a2，为由自
7、然数组成的严格单调递增序列。证明：若nN，则nan。3、斐波那契(Fibonacci)数列定义为F0=0F1=1Fn+1=Fn+Fn-1，nI+证明：若nI+，则。4、设n, mI+且nm。假定有n个直立的大头针，甲、乙两人轮流把这些直立的大头针扳倒。规定每人每次可扳倒1至根，且扳倒最后一根直立的大头针者为获胜者。试证明：如果甲先扳且(m+n)不能整除n，则甲总能获胜。5、证明以下的二重归纳原理的正确性：设i0, j0N。假定对任意自然数ii0及jj0，皆有一个命题P(i, j)满足：i) P(i0, j0)真；ii)对任意自然数ki0及lj0，若P(k, l)真，则P(k+1, l)和P(k
8、, l+1)皆真。则对任意自然数ii0及jj0，P(i, j)皆真。6、证明：若nN，则nn。7、证明：若n, mN，则n m当且仅当n m。8、证明：若n, mN，则n m当且仅当n+ m+。9、证明：若n, mN，则nm当且仅当有xN使m = n+ x+。10、证明：若nN，则不可能有mN使nmn+。习题1、 设A=0,1，B=1,2。试确定下列集合：a)A1Bb)A2Bc)(BA )2 2、证明或用反例推翻下列命题：a)(AB)(CD)= (AC)(BD) b)(AB)(CD)= (AC)(BD)c)(AB)(CD)= (AC)(BD) d)(AB)(C D)= (AC)(BD) 3、如
9、果BCA，则(AB) (CD)= (AC) (BD)。这个命题对吗？如果对，则给予证明；如果不对，则举出反例。f) 4、证明：若xC且yC，则 (C)。5、证明：a且b。6、把三元偶定义为 a , a, b , a, b, c 合适吗？说明理由。7、为了给出序偶的另一定义，选取两个不同集合A和B(例如取A=，B=)，并定义= a, A ,b, B。证明这个定义的合理性。第二章 二元关系习题2.11、 列出从A到B的关系R中的所有序偶。a)A=0, 1, 2，B=0, 2, 4，R=| x, y AB b)A=1, 2, 3, 4, 5，B=1, 2, 3，R=| x A, y B且x =y22
10、、设R1和R2都是从1, 2, 3, 4到 2, 3, 4的二元关系，并且R1=, R2=, 求R1R2, R1R2, domR1, domR2, ranR1, ranR2, dom(R1R2)和ran(R1R2)。3、设和都是从集合到集合的二元关系。证明dom(R1R2)= domR1domR2ran(R1R2) ranR1ranR24、用L和D分别表示集合1, 2, 3, 6上的普通的小于关系和整除关系，试列出L, D和LD中的所有序偶。5、给出满足下列要求的二元关系的实例：a)既是自反的，又是反自反的；b)既不是自反的，又不是反自反的；c)既是对称的，又是反对称的；d)既不是对称的，又不
11、是反对称的。6、试判断下面的论断正确与否。若正确，请加以证明；若不正确，请给出反例。设R和S都是集合A上的二元关系。若R和S都是自反的(反自反的，对称的，反对称的，或传递的)，则RS，RS，RS，RS也是自反的(反自反的，对称的，反对称的，或传递的)。7、描述R上的下列二元关系S的性质：a)S=|x, yR且x y 0；b)S=|x, yR，4整除|xy|且|xy|10；c)S=|x, yR，x2 =1且y 0；d)S=|x, yR，4 |x|1且| y|1。8、设n, mI+。若集合A恰有n个元素，则在A上能有多少个不同的m元关系？证明你的结论。9、设x和z都是由从集合A到集合B的二元关系构
12、成的集类，并且z 。证明a)dom(x)=domR|Rx； b)ran(x)=ranR|Rx；c)dom(z)domR|Rz；d)ran(z)ranR|Rz；10、设R为集合上的一个二元关系。如果R是反自反的和传递的，则R一定是反对称的。11、设R为集合上的一个二元关系，若令fldR=domRranR则fldR=(R)。12、若R为集合上的一个二元关系，则也是(R)上的二元关系。1. 设集合A=1,2,3,4,5,6上的二元关系R为R=,试画出R的关系图GR，求出R的关系矩阵MR,并指出R所具有的性质。2. 对图给出的集合A=1,2,3上的十二个二元关系的关系图，写出相应的关系矩阵，并指出各个关系所具有的性质。3. 对习题2.1种第4题所给的二元关系L,D和LD，画出它们的关系图，并写出它们的关系矩阵。4. 设A为恰有n个元素的有限集。a) 共有多少个A上的不相同的自反关系？a) 共有多少个A上的不相同的反自反关系？
