离散数学习题解第一部分(集合论部分)

1离散数学辅助教材概念分析结构思想与推理证明第一部分集合论刘国荣交大电信学院计算机系2离散数学习题解答习题一（第一章集合）1.列出下述集合的全部元素：1）A={x|x∈N∧x是偶数∧x＜15}2）B={x|x∈N∧4+x=3}3）C={x|x是十进制的数字}[解]1）A={2，4，6，8，10，12，14}2）B=3）C={0，1，2，3，4，5，6，7，8，9}2.用谓词法表示下列集合：1）{奇整数集合}2）{小于7的非负整数集合}3）{3，5，7，11，13，17，19，23，29}[解]1）{nnI(mI)(n=2m+1)}；2）{nnIn0n7}；3）{ppNp2p30(dN)(d1dp(kN)(p=kd))}。3.确定下列各命题的真假性：1）2）∈3）{}4）∈{}5）{a，b}{a，b，c，{a，b，c}}6）{a,b}∈(a，b，c，{a，b，c})7）{a，b}{a，b，{{a，b，}}}8）{a，b}∈{a，b，{{a，b，}}}[解]1）真。因为空集是任意集合的子集；2）假。因为空集不含任何元素；3）真。因为空集是任意集合的子集；4）真。因为是集合{}的元素；5）真。因为{a，b}是集合{a，b，c，{a，b，c}}的子集；6）假。因为{a,b}不是集合{a，b，c，{a，b，c}}的元素；37）真。因为{a，b}是集合{a，b，{{a，b}}}的子集；8）假。因为{a,b}不是集合{a，b，{{a，b}}}的元素。4.对任意集合A，B，C，确定下列命题的真假性：1）如果A∈B∧B∈C，则A∈C。2）如果A∈B∧B∈C，则A∈C。3）如果AB∧B∈C，则A∈C。[解]1）假。例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。2）假。例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A∈C。3）假。例如A={a}，B={a，b}，C={{a}，a，b}，从而ACB∧B∈．C，但A∈C。5．对任意集合A，B，C，确定下列命题的真假性：1）如果A∈B∧BC，则A∈C。2）如果A∈B∧BC，则AC。3）如果AB∧B∈C，则A∈C。3）如果AB∧B∈C，则AC。[解]1）真。因为BCx（x∈Bx∈C），因此A∈BA∈C。2）假。例如A={a}，B={{a}，{b}}，C={{a}，{b}，{c}}从而A∈B∧BC，但AC。3）假。例如A={a}，B={{a，b}}，C={{a，{a，b}}，从而AB∧B∈C，但AC。4）假。例如A={a}，B={{a，b}}，C={{a，b}，b}，从而AB∧B∈C，但AC。6．求下列集合的幂集：1）{a，b，c}2）{a，{b，c}}3）{}4）{，{}}5）{{a，b}，{a，a，b}，{a，b，a，b}}[解]1）{，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}}2）{，{a}，{{b，c}}，{a，{a，b}}}3）{，{}}4）{，{}，{{}}，{，{}}}5）{，{{a，b}}}7．给定自然数集合N的下列子集：4A={1，2，7，8}B={x|x2＜50}C={x|x可以被3整除且0≤x≤30}D={x|x=2K，K∈I∧O≤K≤6}列出下面集合的元素：1）A∪B∪C∪D2）A∩B∩C∩D3）B\（A∪C）4）（A′∩B）∪D[解]因为B={1，2，3，4，5，6，7}，C={3，6，9，12，15，18，21，24，27，30}，D={1，2，4，8，16，32，64，}，故此1）A∪B∪C∪D={1，2，3，4，5，6，7，8，9，12，15，16，18，21，24，27，30，32，64}2）A∩B∩C∩D=3）B\（A∪C）={4，5}4）（A′∩B）∪D={1，2，3，4，5，6，7，8，16，32，64}8．设A、B、C是集合，证明：1）（A\B）=A\(B\C)2）（A\B）\C=（A\C）\（B\C）3）（A\B）\C=(A\C)\B[证明]1）方法一：（A\B）\C=（A∩B′）∩C′（差集的定义）=A∩（B′∩C′）（交运算的结合律）=A∩（B∪C）′（deMorgan律）=A\（B∪C）（差集的定义）方法二：对任一元素x∈（A\B）\C，则xC，同时，x∈A\B，x∈A，xB，所以，x∈A，xB∪C，即x∈A\（B∪C），由此可见（A\B）\CA\（B∪C）。反之，对任一元素x∈A\（B∪C），则x∈A，且xB∪C，也就是说xA，xB，xC。所以x∈（A\B）\C，由此可见A\（B∪C）（A\B）\C。因此A\（B\C）。2）方法一：（A\B）\C=A\（B∪C）（根据1））5=A\（C∪B）（并运算交换律）=A\（（C∪B）∩Ⅹ）（0—1律）=A\（（C∪B）∩（C∪C′））（0—1律）=A\（C∪（B∩C′）（分配律）=（A\C）\（B∩C′）（根据1）=（A\C）\（B∩C）（差集的定义）方法二：对任一元素x∈（A\B）\C，可知x∈A，xB，xC，x∈A\C。又由xB，xB\C，x∈（A\C）\（B\C）\（B\C）。所以（A\B）\C（A\C）\（B\C）。反之，对任x∈（A\C）\（B\C），可知x∈A\C，xB\C。由x∈A\C，可知x∈A，xC。又因为xB\C及xC，可知xB。所以，x∈（A\B）\C。因此（A\B）\C（A\B）\C。由此可得（A\B）\（B\C）（A\B）\C。3）方法一：（A\C）\C=A\（B∪C）(根据1))=A\（C∪B）（并运算交换律）=（A\C）\B（根据1））方法二：对任一元素x∈（A\B）\C，可知x∈A，xB，xC。由为x∈A，xC，所以，x∈A\C。又由xB，x∈（A\C）\B。所以，（A\B）\C（A\C）\B。同理可证得（A\C）\B（A\B）\C。9.设A、B是Ⅹ全集的子集，证明：ABA′∪B=XA∩B′=[解](采用循环证法)(1)先证ABA′∪B=X；方法一：A′∪B=A′∪(A∪B)（因为条件AB及定理4）=(A′∪A)∪B（∪的结合律）=(A∪A′)∪B（∪的交换律）=X∪B（互补律）=X（零壹律）方法二：ABA∪B=B（定理4）B=A∪B（等号=的对称性）A′∪B=A′∪(A∪B)（两边同时左并上A′）A′∪B==(A′∪A)∪B（∪的结合律）6A′∪B=(A∪A′)∪B（∪的交换律）A′∪B=X∪B（互补律）A′∪B=Ｘ（零壹律）方法三：因为A′X且BX，所以根据定理2的3）就有A′∪BＸ；另一方面，由于BA′∪B及根据换质位律可得B′A′A′∪B，因此，由互补律及再次应用定理2的3），可得X=B∪B′A′∪B，即XA′∪B；所以，A′∪B=Ｘ。(2)次证A′∪B=XA∩B′=；A′∪B=X(A′∪B)′=X′（两边同时取补运算′）(A′)′∩B′=X′（deMorgan律）A∩B′=X′（反身律）A∩B′=X′（零壹律）(3)再证A∩B′=AB；方法一：A=A∩X(零壹律)=A∩(B∪B′)(互补律)=(A∩B)∪(A∩B′)(分配律)=(A∩B)∪(条件A∩B′=)=A∩B(零壹律)B（定理2的3)）方法二：A∩B′=B=B∪(零壹律)=B∪(A∩B′)（条件A∩B′=）=(B∪A)∩(B∪B′)(分配律)=(A∪B)∩(B∪B′)(∪的交换律)=(A∪B)∩X(互补律)=A∪B(零壹律)AB（定理4的2)）10.对于任意集合A，B，C，下列各式是否成立，为什么？1）A∪B=A∪CB=C2）A∩B=A∩CB=C[解]1）不一定。例如：A={a}，B={a，b}，C={b}。显然有A∪B=A∪C，但B≠C。2）不一定。例如：A={a}，B={a，b}，C={b，c}。显然有7A∩B=A∩C，但B≠C。11．设A，B为集合，给出下列等式成立的充分必要条件：1）A\B=B2）A\B=B\A3）A∩B=A∪B4）AB=A[解]1）A\B=A∩B′，由假设可知A\B=B，即A∩B′=B。由此可知B=A∩B′B′，故此B=B∩B′=。由假设可知A=A\=A\B=B=。所以当A\B=B时有A=B=。反之，当A=B=时，显然A\B=B。因此A\B=B的充分必要条件是A=B=。2）设A\B≠∈，则有元素a∈A\B，那么，a∈A，而由假设A\B=B\A。所以a∈B\A，从而aA，矛盾。所以A\B=，故AB。另一方面由B\A=A\B=。可得BA。因此当A\B=B\A时，有A=B。反之，当A=B时，显然A\B=B\A=因此，A\B=B\A的充要条件是A=B。3）由于A∪B=A∩B，从而AA∪B=A∩BB，以及BA∪B=A∩BA故此A∪B=A∩B，有A=B。5）根据定理6的1）有A=A，由已知条件AB=A，可得AB=A。从而由对称差的消去律可得B=。反之，若B=，则AB=A=A。所以AB=A的充分必要条件为B=。12.对下列集合，画出其文图：1）A′∩B′2）A\（B∪C）′3）A∩（B′∪C）[解]ABA′∩B′A\(B∪C)′BCA∩(B′∪C)ACBAXXXX813.用公式表示出下面图中的阴影部分[解]14.试用成员表法证明1）（AB）C=A（BC）2）（A∪B）∩（B∪C）AB′[解]1）成员表如下ABCAB（AB）CBCA（BＣ）０００００００００１０１１１０１０１１１１０１１１０００１００１１０１１０１１０１０１１０００１０１１１０１０１成员表中运算结果Ｃ及Ａ（ＢＣ）的两列状态表明，全集中的每一个体对它俩有相同的从属关系，故（ＡＢ）Ｃ＝Ａ（ＢＣ）1）成员表如下：ABCA∪B（B∪C）(B∪C)′(A∪B)∩(B∪C)′B′A∩B′０００００1０10００１０１0010０１０１１0000０１１１10０00１００１01１11１０１１10０11１１０110０00１１１1１0000ACBx(A∪B∪C)∪(A∩B∩C)′BCAx(A∩C)\B9成员表中运算结果（A∪B）∩（B∪C）′及A∩B′的两列状态表明，全集中的每一个体，凡是从属（A∪B）∩（B∪C）′的，都从属A∩B′，故（A∪B）∩（B∪C）′A∩B注：自然数集N取为{1，2，3，……，n，……}10习题二（第二章关系）1．设A={1，2，3，}，B={a，b}求1）A×B2）B×A3）B×B4）2B×B[解]1）A×B={（1，a），（1，b），（2，a），（2，a），（3，a），（3，b）}2）B×A={（a，1），（a，2），（a，3），（b，1），（b，2），（b，3）}3）B×B={（a，a），（a，b），（b，a），（b，b）}4）2B={，{a}，{b}，{a，b}}2B×B{（，{a}），（，b），（{a}，a），（{a}，b），（{b}，a），（{b}，b），（{a，b}，b）}2．使AA×A成立的集合A存在吗？请阐明理由。[解]一般地说，使AA×A成立的集合A不存在，除非A=。否则A≠，则存在元素x∈A×A，故有y1，y2∈A，使x=（y1，y2），从而y1，y2∈A×A，故此有y1，y2，y3，y4，使y1=（y1，y2），y2=（y3，y4），……。这说明A中每个元素x，其结构为元组的无穷次嵌套构成，这不可能。我们讨论的元素的结构必须是由元组的有限次嵌套构成。3．证明A×B=B×AA=∨B=∨A=B[证]必要性：即证A×B=B×AA=∨B=∨A=B若A×B=，则A=或者B=若A×B≠，则A≠且B≠，因此对任何x∈A及任何y∈B就有（x，y）∈A×B，根据A×B=B×A，可得