离散数学课后练习3.doc

第三章习题1.判断下列各题的正确与错误。（1）xx（2）xx （3）xx, x（4）xx, x解：（1）正确，（2）错误，（3）正确，（4）正确。2.写出下列集合的表示式（1）所有一元一次方程的解能组成的集合；（2）在实数域中因式集；（3）直角坐标系中，单位圆外的点集；（4）极坐标中，单位圆外的点集；（5）能被5整除的整数集。解：（1） （2）（3） （4） （5）3.确定下列各题是真还是假，并简要说明之：（1） （5）（）（）（） （7）（） （8）解：（1）正确即命题为真。因为空集是任何集合的子集。 （）不真即假命题。属于关系是元素与集合的关系（）真命题（）真命题（）真命题（）假命题（）真命题（）真命题 设，为任意集合，证明或反驳下列命题：（）（）（）（）（）（6）（7）（）解：（）错误。反例：（2）错误。反例：（3）错误。反例： （4）错误。反例：（5）正确。因为。 又因为，所以， 又因为所以。（6）正确。由（5）。（7）错误。反例：。（8）错误。反例：。5、试求下列各集的幂集：（1）（2）（3）（4）（5）（6）（7），,，6，设某集合有101个元素，试问（1） 可构成多少个子集？（2） 其中有多少个子集的元素为奇数？（3） 是否会有102个元素的子集？解：（1）可构成个子集。（2）其中有+=个集合元素为奇数。（3）不会有102个元素的子集。7.设S=, ,由和所表达的子集是什么？又如何去规定子集，及，？(超出教科书范围)8分别求下列集合的交和并：（1）=x|0x1/n(n=1,2,3.)(2) =x|0x1/n(n=1,2,3.)（3）解：（1）（2） （3） 9给定自然数集N的下列子集：A=1、2、7、8 C=i|i可被3整除，0i30 求下列集合：（1）(2) （3) (4)解：根据定义知 B=0、1、2、C=(0、3、6、9、12、15、18、21、24、27、30)D=2 4 6 8 16 32 64 因此（1）= 0,1,2,3,4,5,6,7,9,12,15,18,21,24,27,30,8,16,32,64(2) = (3)=4,5,7(4)=0，3，4，5，6D=0，2，3，4，5，6，8，16，32，6410.证明下列各式：（1）证：有或，有（且），或，从而或即因此另一方面，有或，从而（且）或，即，从而，因此。（2）证：反证法.假设,则存在,即且.从而且且.矛盾.所以.(3)证: 首先证明从而.(4)证: 左右.(5)证:左=右(6)证:左=右（7）证：右= =左（8）证：左= = = = =右（9）证：左= = = =右（10）证：左= =右：教材印刷有误！证：左 证：利用题方法可证。证：右左证： =（CAC）(CAB) =(CAB)= C (AB)= C(A-B)=左（15）证：左 右11.证明下列各对条件是等价的：（1）证明：由（2）且证：由，显然有且.另一方面.若且，则有或.由条件得.所以.因此，与且是等价的。证：，易推出另一方面，若，则，由条件知，从而，即因此与是等价的。证：若所以， 若则所以，因此 。证：若所以若，则从而有因此，。（6）证：若 所以 因此12、要使下列等式成立，集合A与B之间应满足什么条件？从而，有 即 即同理，由 可推出所以有A=B即 （5）解：即 由得因此，（6）解：因为所以，由得从而有从而有 即因此，若，则有（9）当且仅当解： CAB由图可知：该命题为假。16设A.B是任意集合（1）若，则A.B有何关系？（2）若，则A.B又有何关系？解：见习题12。17（1）已知，求证（2）已知，问：是否有证明：（1） 因为所以从而有 因此，。 （2）结论不一定成立。 反例：，有 但。18设集合A=a,b,c,求P（a）？解：19下列各式中哪些成立，哪些不成立，为什么？解：反例： （3）不成立。反例： （4）成立。事实上，（5）成立。事实上，(6)成立事实上，20.省略21 设 试求（1）（2）（3）（4）（5）（6）解：（1）(2)(3) (4)(5)(6) 22、证明Bernoulli不等式：对每一个实数和每一个自然数n,有。证明：对n归纳。 当n=0时，结论显然成立。 假设当n=k时，有。 看的情形， 因,从而有既 归纳完成，命题得证。23 考虑Fibonacci序列 定义如下 令 证明对于所有证明：对n作归纳 当n=1时， 绪论成立、 假设 而 所以， 归纳完成，命题得证。24 证明关于x, y的方程的自然数解的组数 证明：对n归纳 当n=0时，方程的自然数解为唯一的一组x=y=0 即，结论成立 当n=1时，方程的自然数解为唯一的一组 x=1,y=0 即，结论成立假设n=K时结论成立，看n=K+1的情况此时，方程 x+2y=K+1 可以写成（x-1）+2y=K j即+2y=K。 (令=x-1)由归纳假设 方程+2y=K的自然数解得组数当K为偶数时，方程+2y=K与x+2y=K+1的自然数的组数是相等的。从而x+2y=K+1的自然数解得组数为 当K为奇数时方程+2y=K 的自然数解中0。而方程x+2y=K+1的自然数解中。包括x=0的解。因此，方程x+2y=K+1的自然数解比方程+2y=K多以组解。因此，方程x+2y=K+1的自然数解得组数为归纳完成，结论得证。25.用数学归纳法证明“从几个不同元素中取出n个不同元素的排列数”证：26.下列证明有错误吗？若有，请指出错误所在。求证：=对一切自然均真。证明：当n=0，显然=设nk时命题成立，即=，=，=，现对n=k时情况进行证明，这是= （根据归纳假设）归纳完成，命题得证。解：有错误首先数学归纳原理是定义在正整数集上。必须验证当