自考2324离散数学课后答案3.1习题参考答案1、写出下列集合的的表示式。a)所有一元一次方程的解组成的集合。A={x|x是所有一元一次方程的解组成的集合}晓津答案：A={x|ax+b=0∧a∈R∧b∈R}b)x2-1在实数域中的因式集。B={1,(x-1),(x+1)|x∈R}c)直角坐标系中，单位圆内（不包括单位圆周）的点集。C={x,y|x2+y2<1}晓津答案：C={a(x,y)|a为直角坐标系中一点且x2+y2<1}d)极坐标中，单位圆外（不包括单位圆周）的点集。D={r,θ|r>1,0<=θ<=360}晓津答案：D={a(r,θ)|a为极坐标系中一点且r>1,0<=θ<=2π}e)能被5整除的整数集E={x|xmod5=0}2、判定下列各题的正确与错误。a){x}{x};正确b){x}∈{x};正确晓津观点:本命题错误。理由：{x}作为一个元素是一个集合，而右边集合中的元素并不是集合。c){x}∈{x,{x}};正确d){x}{x,{x}};正确----------------------------------------------------------------3、设A={1,2,4},B={1,3,{2}},指出下列各式是否成立。a){2}∈A; b){2}∈B c){2}Ad){2}B; e)∈A f) A解：jhju、晓津和wwbnb的答案经过综合补充，本题的正确答案是：b、c、d、f成立，a，d、e不成立。理由：a式中，{2}是一个集合，而在A中并无这样的元素。因此不能说{2}属于A，当然如果说2∈A则是正确的。对于e式也应作如此理解，空集是一个集合，在A中并无这个集合元素,如f式则是正确的。空集包含于任何集合中，但空集不一定属于任一集合。----------------------------------------------------------------4、设A={} ，B=(A),问下列各题是否正确。a) ∈B,B正确b){}∈B,{}B正确c){{}}∈B,{{}}B正确5、设A={a,{a}},问下列各题是否正确。a){a}∈(A),{a}(A);正确晓津答案：本命题不正确。(A)={，{a},{{a}},{a,{a}}},在这个集合中，并无a这个元素，因此命题的后半个{a}(A)是不成立的。b){{a}}∈(A),{{a}}(A);正确c)设A={a,{b}},a),b)是否正确。a和b都正确晓津答案：如此则a),b)均不正确。此时,(A)={，{a},{{b}},{a,{b}}}。除了a式的前半句正确，其他的都不成立，因此a),b)式均不成立。6、设某集合有101个元素，试问：a)可构成多少个子集；2n个元素(子集吧)b)其中有多少个子集元素为奇数；其中有2n-1个子集元素为奇数晓津不同意见：我认为这个答案不成立,如集合有3个元素，则它的幂集中有5个子集中元素个数为奇数，而不是7个。可是我也还没找到这个式子。sphinx提供的答案是2100，可通过多项式分解找到规律，空集不算。晓津想，应该算上，若算上则是2n-1+1c)是否有102个元素的子集。无3.2习题答案1、给定自然数集合N的下列子集：A={1,2,7,8} B={i|i^2<50}={0,1,2,3,4,5,6,7}C={i|i可被3整除0≤i≤30},={0,3,6,9,12,15,18,21,24,27,30}D={i|i=2^K,K∈Z+,1≤K≤6}={2,4,8,16,32,64}求下列各集合。a)A∪(B∪(C∪D));={2,4,8,16,32,64,0,3,6,9,12,15,18,21,24,27,30,1,5,7}b)A∩(B∩(C∩D));=A∩(B∩}=c)B-(A∪C);=B-{0,1,2,7,8,3,6,9,12,15,18,21,24,27,30}={4,5}d)(～A∩B)∪D={8}∪D={2,4,8,16,32,64}晓津补充:这里的(～A∩B)应当等于(B-A)而不是(A-B),所以最终的答案是：{0,3,4,5,6}∪D={0,2,3,4,5,6,8,16,32,64}----------------------------------------------------------------2、a)如果对于一切集合，有X∪Y=X，则Y=φ证明： X∪Y={i|i∈X∨i∈Y}=X{i|i∈X∨i∈Y}=X{i|i∈X∨i∈Y}={i|i∈X}由此可见：Y=φ晓津的证明：必要性：设Y≠φ则Y中必有一个以上元素。若有一个元素y,y∈Y∧yX则有X∪Y≠X这与前提矛盾。充分性：若Y=φ则任合集合X∪Y=X成立。本题要注意Y有时包含于X的，若用命题表达式论证，应用到量词。b)证明对所有集合A，B和C，有：(A∩B)∪C=A∩(B∪C);iffCA。(A∩B)∪C={i|(i∈A∧i∈B)∨i∈C}A∩(B∪C)={i|i∈A∧(i∈B∨i∈C)}(i∈A∧i∈B)∨i∈C=i∈A∧(i∈B∨i∈C)因为iffCA所以i∈A∨i∈C=i∈A得证：(A∩B)∪C=A∩(B∪C)晓津证明：本题也要进行双向的证明，一个是必要性，一个是充分性，这才能得出当需的结论。证：充分性：若CA则(A∩B)∪C=(A∪C)∩(B∪C)=A∩(B∪C)=右边。必要性：假设C不包含于A内，则C中必有一个以上元素xA，则A∪C≠A可得(A∩B)∪C=(A∪C)∩(B∪C)≠A∩(B∪C)假设与前提矛盾，因此假设不成立，C应当包含于A内。3、证明对任意集合A，B，C，有：a)(A-B)-C=A-(B∪C);证明：(A-B)-C={x|x∈A∧xB}-C={x|x∈A∧xB∧xC}={x|x∈A∧x∈～B∧x∈～C}={x|x∈A∧x∈(～B∩～C)}={x|x∈A∧x∈～(B∪C)}=A-(B∪C)我想，本题也可以直接应用集合运算来做。b)(A-B)-C=(A-C)-B;(A-B)-C={x|x∈((A-B)-C)}={x|x∈A∧xB∧xC}={x|x∈(A-C)∧xB}=(A-C)-Bc)(A-B)-C=(A-C)-(B-C)(A-B)-C={x|x∈((A-B)-C)}={x|x∈A∧xB∧xC}={x|x∈A∧xB∧xB∧xC}={x|x∈(A-B)∧xB∧xC}={x|x∈(A-B)∧x∈～B∧x∈～C}={x|x∈(A-B)∧x∈(～B∩～C)}={x|x∈(A-B)∧x∈～(B∪C)}={x|x∈(A-B)∧x(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∩～B)∩～C)∪Φ=(A-B)-C=左边4、设A，B，C是全集E的任意子集。a)若A∩B=A∩C,～A∩B=～A∩C,证明：B=C晓津证明此题如下:证明：由A∩B=A∩C,～A∩B=～A∩C得(A∩B)∩(～A∩B)=(A∩C)∩(～A∩C)(A∩B)∪(~A∩B)=(A∩C)∪(~A∩C)B∩(A∪~A)=A(C∪~C)即B∩E=C∩E因B，C是全集E的任意子集B=C本题的答案感谢kavana提供意见。b)若(A∩C)(B∩C),(A∩～C)(B∩～C),证明：AB由(A∩C)(B∩C),(A∩～C)(B∩～C)得：(A∩C)∪(A∩～C)(B∩C)∪(B∩～C)A∩(C∪～C)B∩(C∪～C)A∩EB∩EA，B，C是全集E的任意子集AB5、设A={φ},B=((A)),问下列各题是否正确？a)φ∈B φB正确b){φ}∈B {φ}B正确c){{φ}}∈B {{φ}}B正确本题由kavana补充：(A)={φ,{φ}}B=((A))={φ,{φ},{{φ}},{φ,{φ}}}。感谢kavana！6、在下面各题中，如果命题为真，请给证明；如果命题为假，则给出反例；a)、A∩(B-C)=(A∩B)-(A∩C)晓津证明如下：A∩(B-C)={x|x∈A∧(x∈B∧x∈～C)}={x|x∈A∧x∈B∧(x∈A∧xC)}={x|x∈A∧x∈B∧(x∈A∧x(A∩C))}={x|x∈A∧x∈B∧x(A∩C)}=(A∩B)-(A∩C)b)、(A-B)∩(B-A)=φ(A-B)∩(B-A)={x|x∈AxBxAx∈B}=φ也可以用集合运算证明：原式=(A∩～B)∩(B∩～A)=(A∩～A)∩(B∩～B)=Φc)、A-(B∪C)=(A-B)∪C不成立补充实例如下：设A={1,2,3,4}B={1,5}C={2,6}则A-(B∪C)={3,4}而(A-B)∪C={2,3,4,6}d)、 ～(A-B)=～(B-A)不成立补充实例：设E={1,2,3,4,5}A={1,2}B={1,3,4}则～(A-B)={1,3,4,5}而～(B-A)={1,2,5}e) ～(A∩B)A不成立补充实例如下:设E={1,2,3}A={1,2}B={2,3}则～(A∩B)={1,3}它不包含于A内。f)(A∩B)∪(B-A)=A不成立补充实例如下：A={1,2}B={1,2,3,4}则(A∩B)∪(B-A)={1,2,3,4}≠A7、设A，B，C是任意集，证明：a)(A∪B)-C=(A-C)∪(B-C)证明：(A∪B)-C={x|(x∈A∨x∈B)∧xC}={x|(x∈A∧xC)∨(x∈A∧xC)}=(A-C)∪(B-C)b)A-(B∪C)=(A-B)∩(A-C)证明:A-(B∪C)={x|x∈A∧x(B∪C)}={x|x∈A∧(xB∧xC)}={x|x∈A∧xB∧x∈A∧xC)}=(A-B)∩(A-C)c)、(A-B)∪(A-C)=A,当需A∩(B∩C)=φ时成立。证明:(A-B)∪(A-C)={x|(x∈A∧xB)∨(x∈A∧xC)}={x|x∈A∧(xB∨xC)}={x|x∈A∧x(B∪C)}我怎么觉得：A∩(B∪C)=φ时，(A-B)∪(A-C)=A题目是否出错了？晓津认为：红色的∪其实应为∩，xB或xC应用德摩根律，就是说x(B∩C).以上证明并未证得结论。现证明如下：充分性：若A∩(B∩C)=φ则前提的左边=(A∩～B)∪(A∩～C)=A∩(～B∪～C)=A∩～(B∩C)=A-(B∩C)=A-(B∩C)=A-(A∩(B∩C))=A-Φ=A=右边可得等式成立必要性：若设A∩(B∩C)≠φ则由上面证明可知A-(B∩C)≠A。即前提左边≠A左右不等，因此假设违反题意，不成立。所以必需A∩(B∩C)=φ8、证明：a)、A∩(BC)=(A∩B)(A∩C)??晓津证明如下：右边=((A∩B)∪(A∩C))∩～((A∩B)∩(A∩C))=(A∩(B∪C))∩～(A∩(B∩C))=(A∩(B∪C))∩(～A∪～(B∩C))=((A∩(B∪C))∩～A)∪(A∩(B∪C)∩～(B∩C))=Φ∪(A∩(B∪C)∩～(B∩C))=A∩(BC)=左边证毕我想，有时候从右边化到左边会更简便些吧。b)、A∪(BC)=(A∪B)(A∪C)，不一定成立。??晓津证明如下:设有集合A={1,2,3}B={4,5}C={5,6}则A∪(BC)={1,2,3,4,6}且(A∪B)(A∪C)={1,2,3,4,6}左右相等。等式成立。又设有集合A={1,2,3,5}B={4,5}C={5,6}则则A∪(BC)={1,2,3,4,5,6}而(A∪B)(A∪C)={1,2,3,4,6}左右不等，因此证得原式不一定成立。3.3习题答案1、设A={0,1},B={1,2},确定下面集合。a)A×{1}×B={<0,1>,<1,1>}×{1,2}={<<0,1>,1>,<<1,1>,1>,<<0,1>,2>,<<0,1>,2>}b)A2×B={<0,1>,<0,2>,<1,1>,<1,2>}×{1,2}={<<0,1>,1>,<<0,1>,2>,<<0,2>,1>,<<0,2>,2>,<<1,1>,1>,<<1,1>,2>,<<1,2>,1>,<<1,2>,2>}c)(A×B)2={<0,1>,<0,2>,<1,1>,<1,2>}2={<<0,1>,<0,1>>,<<0,1>,<0,2>>,<<0,1>,<1,1>>,<<0,1>,<1,2>>,<<0,2>,<0,1>>,<<0,2>,<0,2>>,<<0,2>,<1,1>>,<<0,2>,<1,2>>,<<1,1>,<0,1>>,<<1,1>,<0,2>>,<<1,1>,<1,1>>,<<1,1>,<1,2>>, <<1,2>,<0,1>>,<<1,2>,<0,2>>,<<1,2>,<1,1>>,<<1,2>,<1,2>>}晓津叹气，呵呵，这道题本是(B×A)2，答案就不一样了。大家做题的时候也要注意仔细看题目呀。2、下列各式中哪些成立？哪些不成立？为什么？a)(A∪B)×(C∪D)=(A×C)∪(B×D)不成立，因为笛卡尔积中。在左半式中，x的成分在A与B两个集合中，而右半式中，x的成分在A与C两个集合中。b)(A-B)×(C-D)=(A×C)-(B×D)不成立，比如设A与B中都含有含有元素a。在左半式中，a是不会出现在x中。假设(A×C)出现(a,b),(a,e),而(B×D)出现了(a,b),(a,d)，那么(a,e)将被保留下来，从而左半式不等于右半式。c)(AB)×(CD)=(A×C)(B×D)不成立。因为左半式x不可能含有A∩B的成分，而在右半式x就包含有A∩B的成分。d)(A-B)×C=(A×C)-(B×C)成立，因为左半式x不会出现B的成分，而右半式中x包含有B的成分，也会被过滤掉的。e)(AB)×C=(A×C)(B×C)成立。左半式中x不会出现A∩B的成分，而右半式中A∩B也会被过滤掉的。晓津道：这几个判断都是对的，只是证明过程好象有点生活化，不够科学，哪位朋友来做做?:)下面是ryz同学给出的证明:(晓津有所补充)d)证明：(1)设任意的＜x，y＞∈(A－B)×C∴x∈(A－B)∧y∈C∴x∈A∧xB∧y∈C∴(x∈A∧y∈C)∧xB∧y∈C∴＜x，y＞∈(A×C)∧＜x，y＞(B×C)∴＜x，y＞∈(A×C)－(B×C)；∴(A－B)×C(A×C)－(B×C)(2)设任意的＜x，y＞∈(A×C)－(B×C)；则＜x，y＞∈(A×C)∧＜x，y＞(B×C)∴x∈A∧y∈C∧(xB∨yC)∴x∈A∧((y∈C∧xB)∨(y∈C∧yC))∴x∈A∧y∈C∧xB∴(x∈A∧xB)∧y∈C∴x∈(A－B)∧y∈C∴＜x，y＞∈(A－B)×C∴(A×C)－(B×C)(A－B)×C∴(A－B)×C=(A×C)－(B×C)e)(AB)×C＝((A－B)∪(B－A))×C＝((A－B)×C))∪((B－A)×C)＝(A×C－B×C)∪(B×C－A×C)＝(A×C)(B×C)注：e)是利用d)的结果来证明的3、证明若X×Y=X×Z,且X≠φ，则Y=Z证明：X×Y={
|x∈X,y∈Y}X×Z={|x∈X,z∈Y}如果X=φ那么 X×Y=φ X×Z=φ因为 X≠φ，所以Y=Z4、设X={0,1,2,3,4,5,6},上关系为R={}(x}(x,<0,2>,<0,3>,<0,4>,<0,5>,<0,6>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,3>,<2,4>,<2,5>,<2,6>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,6>,}晓津补充：若按jhju的讨论来做，应把红色三行去掉，0和1、4都不是质数,相应的，在下面的答案里，也应把红色字去掉。domR={0,1,2,3,4,5}ranR={1,2,3,4,5,6}FLDR={0,1,2,3,4,5,6}5.设P={<1,2>,<2,4>,<3,3>}Q={<1,3>,<2,4>,<4,2>}求出P∪Q，P∩Q,domP,domQ,ranP,ranQ,dom(P∩Q),ran(P∩Q)解： P∪Q={<1,2>,<1,3>,<2,4>,<3,3>,<4,2>}P∩Q={<2,4>}domP={1,2,3}domQ={1,2,4}ranP={2,4,3}ranQ={2,4,3}dom(P∩Q)={2}ran(P∩Q)={4}--------------------------------------------------------------------------------6、设A={1,2,3,4},定义A上二元关系R：R,iff(a-b)/2是整数，称R为模2同余系，亦可称∈R,iffa≡b(mod2),求出R的序偶表达式，domR，ranR.解：R={<4,2>,<3,1>,<2,4>,<1,3>}domR={4,3,2,1}ranR={2,1,4,3}黄色字是晓津所补充。7、设A={1,2,3,4,5,6,7,8,9,10}R={|x,y∈A∧x是y的因子∧x<=5},求domR,ranR解：R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>，<1，6><1，7>，<1，8>，<1，9>，<1，10>，<2,2><2,4>,<2,6>,<2,8>,<2,10>,<3,3>,<3,6>,<3,9>,<4,4>,<4,8>,<5,5>,<5,10>} domR={1,2,3,4,5}ranR={1,2,3,4,5,6,7,8,9,10}本题答案由spinx补充纠正，特此感谢。3.4节习题答案1、给定A={1,2,3,4},考虑A上的关系R,若R={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>},a)在A×A的坐标图上标出R，并给出关系图。b)R是自反的？对称的？可传递的?反对称吗？解：我以表格形式表示坐标：4321×××××1234关系图如下：由图中可见，R不是自反的，不是对称的，是可传递的，是反对称的。2、举出A={1,2,3}上关系R的例子，使它有下列性质。a)既是对称的又是反对称的。b)R既不是对称的，又不是反对称的；c)R是可传递的。解：a)R={<1,1>} b)R={<1,3>,<2,3>,<3,1>} c)R={<1,2>,<2,3>,<1,3>}3)说明下列关系是否是自反的，对称的，传递的或反对称的。a)在{1,2,3,4,5}上定义的关系。 {|a-b是偶数}。b)在{1,2,3,4,5}上定义的关系。 {|a+b是偶数}。c)在所有人集合P上的关系，{|a,b是同一祖先}解：a)先列出其关系集合如下：R={<1,1>，<1，3>,<1,5>,<2,2>,<2,4>,<3,3>,<3,5>,<3,1>,<4,4>,<4,2>,<5,5>,<5,3>,<5,1>}由此可看出：A上关系R为自反的，对称的，传递的但不是反对称的。b)仍列出其关系集合：我们发现它和上面的集合是一样的：R={<1,1>，<1，3>,<1,5>,<2,2>,<2,4>,<3,3>,<3,5>,<3,1>,<4,4>,<4,2>,<5,5>,<5,3>,<5,1>}可知：A上关系R也是自反的，对称的，传递的但不是反对称的。。c)这个集合不便列举，就拿一个家庭来举例吧，家里有5个人，老爸x,老妈y,哥哥z,姐姐u,我v,则列出R={,,,,,,,,,}(这里我考虑老爸老妈应该不会同是一个祖先的。推广到所有人，也能得出结论,这个关系是自反的，对称的，传递的但不是反对称的。4、如果关系R和S是自反的、对称的和可传递的，证明R∩S也是自反的、对称和可传递的。证明：设有任意x,y,有∈R且∈S因为R是自反的,则有,∈R,又因为S是自反的，则有,∈S所以,∈(R∩S)即R∩S是自反的。因为R和S都是对称的，则有∈R且∈S因此∈R∩S即R∩S是对称的。再设有任意z,因为R是可传递的，则当xRy且yRz时必有xRz,同样当xSy且ySz时必有xSz,即有：,，∈R∩S所以R∩S是可传递的。5、设S={|对任一C有∈R,∈R},其中R是二元关系，证明若R是自反、对称和传递的，则S也是自反的、对称和传递的。证明：因为对于任一c有∈R且∈R，若R是自反的，则有,,∈R因为∈S即有，∈S，因此S是自反的。若R是对称的和传递的，则由∈R,∈R必有∈R，同时有，∈R则必有∈R所以S是对称的，也是传递的。6、设Z是整数集R={∈R，故R是自反的。设a-b=Kt(t为整数)，则b-a=-Kt所以b≡a(modK)成立，∈R,故R是对称的。若∈R且∈R，即a≡b(modK)且b≡c(modK)a-b=Ktb-c=Ks(t,s为整数)则a-c=Kt+Ks=K(t+s)所以a≡c(modK)即∈R，故R是传递的。7、设R是集合X上的一个自反关系。求证R是对称和传递的，当且仅当,在R中，且有在R中。证明：充分性：设任意a,b,c∈X，因为R是自反关系，则,,∈R，当有,,∈R时....我发现充分性无法证明。必要性：要使R为对称的，则对任意a,b∈X，必须有,∈R，要使R为传递的，对任意a,b,c∈X若有,∈R必要有∈R，所以应有,,,在R中。(实际上对于此题，少给出一个或或在R中的条件，故导致充分性不足。所以此题我没能证出来。3.5习题答案1、设：A={1,2,3}上关系R={|x≤y}，试求：R-1,~R解： R={<1,1>,<1,2>,<1,3>,(2,2>,<2,3>,<3,3>}R-1={<1,1>,<2,1>,<3,1>,<2,2>,<3,2>,<3,3>} ~R={<2,1>,<3,1>,<3,2>}2、设：A={0,1,2},B={0,2,4}的关系为： R={|a,b∈A∩B}求：R^-1,并求MR^-1解： R={<0,0>,<0,2>,<2,2>,<2,0>} R-1={<0,0>,<2,0>,<2,2>,<0,2>} Mr^-1=|0 0 1||1 1 1||0 0 1|应为：Mr^-1= ０ ２ ４０|1 1 0|１|1 1 0|２|0 0 0|3、集合A={a,b,c}上关系R的关系图下图所示，求r(R),s(R),t(R)，并分别画出各闭包的图形。R={,}r(R)={,,,}s(R)={,,}为了求：t(R) MR=|1 1 0||0 0 0||0 0 0|MR^2=|110||000||000| 。|110||000||000|=|110||000||000|MR^3=|110||000||000| 可见：t(R)=MR∪MR^2∪MR^3={,} 4、设A={1,2,3,4}上的二元关系，R={<1,2>,<2,4>,<3,3>,<1,3>}，则：r(R)={<1,1>,<2,2>,<4,4>,<1,2>,<2,4>,<3,3>,<1,3>}S(R)={<1,2>,<2,4>,<3,3>,<1,3>,<2,1>,<4,2>,<3,1>}t(R)= MR=|0110||0001|={<1,2>,<2,4>,<3,3>,<1,3>}|0010||0000| MR^2=|0110| |0110| |0011||0001| |0001|=|0000||0010|。|0010| |0010||0000| |0000| |0000|={<1,3>,<1,4>,<3,3>}MR^3=|0011| |0110| |0010||0000| |0001|=|0000||0010|。|0010| |0010||0000| |0000| |0000|={<1,3>,<3,3>}MR^4=|0010| |0110| |0010||0000| |0001|=|0000||0010|。|0010| |0010||0000| |0000| |0000|={<1,3>,<3,3>}可得t(R)={<1,2>,<2,4>,<3,3>,<1,3>}∪{<1,3>,<1,4>,<3,3>}∪{<1,3>,<3,3>}∪{<1,3>,<3,3>}={<1,2>,<1,4>,<2,4>,<3,3>,<1,3>}3.6习题答案1、给定集合X={x1,x2,....,x6},ρ是X上相容关系且Mρ简化矩阵为：试求X的覆盖，并画出相容关系图。解：覆盖如下：{,,,,,,,,,,,,,,,,,}晓津觉得覆盖中的元素应该是集合：我的答案是：S={{x1,x2,x3},{x4,x5,x6}}当然这只是一个覆盖。2、从下面给出的关系图中，说明哪个是相容关系。答：图3、4是相容关系。3、设集合A={1,2,3,4}中的一个覆盖为B={{1,2},{2,3,4}},求出确定的相容关系。解：S1={1,2}S2={2,3,4}根据定理3.6.1：ρ=S1×S1∪S2×S2={<1,1>,<1,2>,<2,1>,<2,2>}∪{<2,2>,<2,3>,<2,4>,<3,2>,<3,4>,<3,3>,<4,2>,<4,3>,<4,4>}={<1,1>,<1,2>,<2,1>,<2,2>,<2,3>,<2,4>,<3,2>,<3,4>,<3,3>,<4,2>,<4,3>,<4,4>}4、设αβ是A上相容关系，a)复合关系α。β是A上的相容关系吗？由于自反性通过,运算可保持;但对称性不能通过,保持。所以复合关系α。β不是A上的相容关系b)α∪β是A上相容关系吗？是的晓津补充证明如下:(1)因为α，β是A上相容关系，若有任意x∈A，则∈α且∈β，所以∈α∪β因此α∪β是自反的。(2)因为α，β是A上的相容关系，若有任意x,y∈A且∈α则有∈α；若有任意u,v∈A且∈β，则有∈β，所以有，,,∈α∪β因此α∪β是对称的。可得α∪β是A上相容关系。c)α∩β是A上相容关系吗？是的晓津证明如下：(1)因为α，β是A上相容关系，则若有任意x∈A,就有∈α∩β，因此α∩β是自反的。(2)因为α，β是A上相容关系，则若有任意x,y∈A且∈α且∈β则有∈α且∈β即,∈α∩β因此α∩β是对称的。可得α∩β是A上相容关系。5、设R、Q都是集合A上自反、对称、传递关系，则s(R∩Q)=_________，t(R∩Q)=_________.因为_________也是自反、对称、传递的。 s(R)∩s(Q) t(R)∩t(Q) R∩Q6、集合A={1,2,3,4,5,6}的关系图如下所示，求： a)R,R^2，R^3及关系图解： R={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>,<5,4>}MR^2=|001010| |001010| |001100||000010| |000010| |000100||001000| |001000|=|001000||000010|。|000010| |000100||000100| |000100| |000010||000000| |000000| |000000|R^2={<1,3>,<1,4>,<2,4>,<3,3>,<4,4>,<5,5>}MR^3=|001100| |001010| |000110||000100| |000010| |000010||001000|。|001000| = |001000||000100| |000010| |000010||000010| |000100| |000100||000000| |000000| |000000| R^3={<1,4>,<1,5>,<2,5>,<3,3>,<4,5>,<5,4>}b)r(R),s(R);r(R)={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>,<5,4>,<1,1>,<2,2>,<4,4>,<5,5>,<6,6>}s(R)={<1,3>,<3,1>,<1,5>,<5,1>,<2,5>,<5,2>,<4,5>,<5,4>}7、令S为从X到Y的关系，T为从Y到Z的关系，对于AX，定义S(A)={y|∈S∧x∈A}证明：a)S(A)Yb)(S。T)(A)=T(S(A));c)S(A∪B)=S(A)∪S(B),其中BXd)S(A∩B)S(A)∩S(B)对这道题我不能理解题目的意思，S(A)是指什么?请学友们帮助解释一下：)8、设：R1和R2是A上的关系，证明：a)r(R1∪R2)=r(R1)∪r(R2);证明如下：因为R1，R2是A上关系，所以R1∪R2也是A上关系；由r(R1)=R1∪IA和r(R2)=R2∪IA可得 r(R1)∪r(R2)=R1∪R2∪IA又因r(R1∪R2)=(R1∪R2)∪IA所以左右相等。b)s(R1∪R2)=s(R1)∪s(R2);证明如下：左边=s(R1∪R2)=(R1∪R2)∪(R1∪R2)-1右边=s(R1)∪s(R2)=R1∪R1-1∪R2∪R2-1 =R1∪R2∪R1-1∪R2-1 =(R1∪R2)∪(R1∪R2)-1 =左边等式成立。c)t(R1∪R2)t(R1)∪t(R2);因为:t(R1)=R1∪R12∪R13∪...∪R1n(n为A中元素个数) t(R2)=R2∪R22∪R23∪...∪R2n则t(R1)∪t(R2)=R1∪R2∪R12∪R22∪R13∪R23∪...∪R1n∪R2n左边=t(R1∪R2)=(R1∪R2)∪(R1∪R2)2∪......∪(R1∪R2)n设A中有任意∈R1，任意∈R2则有∈t(R1)∈t(R2)(1)因为,∈(R1∪R2)(2)则有,∈t(R1∪R2)(3)因此由(1)(2)(3)式可得：t(R1∪R2)t(R1)∪t(R2);3.7 习题参考答案 1、设R是一个二元关系，设S={ |存在某个C，使∈R且∈R}，证明R是一个等价关系，则S也是一个等价关系。 证明： 如果题目反一下是：S是一个等价关系，则R也是一个等价关系。或许能证出吧 晓津看法:题中的大写C应为小写c;请学友提供您的看法。 感谢阮允准给出了证明：（1）∵R是自反， ∴若有x∈A就有＜x，x＞∈R ∴＜x，x＞∈S ∴S是自反的。（2）因有＜a，b＞∈S且存在c，使＜a，c＞∈R且＜c，b＞∈R ∵R是对称的 ∴＜c，a＞∈R，＜b，c＞∈R ∴＜b，a＞∈S ∴S是对称的（3）设＜a，b＞，＜b，c＞∈S 则存在d,e使＜a，d＞，＜d，b＞，＜b，e＞，＜e，c＞∈R ∵R是传递的 ∴＜a，b＞，＜b，c>∈R ∴＜a，c＞∈S即S是传递的因此得证S是等价关系。 2、设R是A上一个自反关系，证明：R是一个等价关系，当且仅当若 ∈R,∈R,则∈R。 证明：由于R是一个等价关系，所以R是传递的。由此可知：若∈R,根据对称性，则有∈R 已知： ∈R且∈R,根据传递性，必有 ∈R 晓津认为：jhju的证明中，已经在前提中确定了R是一个等价关系，这种理解应是不正确的。我的理解是： 前提：R是A上的自反关系 结论：R是一个等价关系iff(aRb,aRc→bRc) 等价关系的充要条件是R为自反的，对称的和传递的。但是我也无法证出来。请胖胖、sphinx、菜虫虫和ryz和其他朋友提供您的思路好吗?下面是linuxcn和阮允准同学给出的证明(晓津作了综合)：证明：1）设有a,b,c∈A，若有∈R，∈R因为R是对称的，所以必有∈R又因为R是传递的，由,∈R，有∈R。2）由(a,b)∈R,(a,c)∈R,则(b,c)∈R。证等价关系,其实只需证传递关系和对称关系。如下：设有任意的∈R∵R是自反的∴∈R∴∈R∴R是对称的对任意的,∈R由R是对称的∴∈R∴由∈R，∈R可得∈R∴R是传递的∴R是等价关系。不对之处，还请多多指正。 3、设R为集合A上一个等价关系，对任何a∈A,集合 [a]R=____[a]R={x| x∈A,aRx}________称为元素a形成的等价类。[a]R≠φ，因为_____ A=φ______。 阮允准给出后一空的正确答案：a∈[a]R4、设R是A上的自反和传递关系，证明：R∩R-1是A上的一个等价关系。证明：R是A上的自反关系，所以 ∈R且∈R-1 ∈R∩R-1R是A上的传递关系,则：若有∈R且∈R,则有∈R由于R又具有对称性，所以∈R 且 ∈R,则有∈R R-1 也有：∈R-1且∈R-1 ,则有∈R-1可见：∈R∩R-1且∈R∩R-1 ,则有∈R∩R-1 R是A上的对称关系，则有 ∈R、∈R R-1 是A上的对称关系，也有∈R、∈R则有：∈R∩R-1、∈R∩R-1由于R∩R-1有对称性，传递性、自反性。所以说R∩R-1是等价关系。 上面的红色部分有点问题，已知条件中并未给出这样的前提。晓津证明如下：(1)因为R是A上的自反关系,若有a∈A，则∈R且∈R-1即∈R∩R-1所以R∩R-1是自反的。(2)因为R是A上的传递关系，则R-1也是A上传递关系，若有a,b,c∈A,则若∈R∩R-1且∈R∩R-1必有∈R∧∈R且∈R-1∧因此有∈R∧∈R-1即∈R∩R-1所以R∩R-1是传递的。(3)若有a,b∈A则若∈R∩R-1就有∈R且∈R-1同时因为∈R，有∈R-1;∈R-1则有∈R因此有,∈R∩R-15、集合A={1,2,3,4,5}上划分为S={{1,2},{3,4,5}},a)写出由S导出的A上等价关系ρ;b)画出ρ的关系图，求Mρ。解：a)ρ={{1,2}×{1,2}}∪{{3,4,5}×{3,4,5}}={<1,1>,<1,2>,<2,1>,<2,2>}∪{<3,3>,<3,4>,<3,5>,<4,3>,<4,4>,<4,5>,<5,3>,<5,4>,<5,5>}={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<3,4>,<3,5>,<4,3>,<4,4>,<4,5>,<5,3>,<5,4>,<5,5>}b) 上图是相容关系图（简单一些） 123Mρ= 451|11000|2|11000|3|00111|4|00111|5|00111|只画黄色部分也可以。6、设正整数的序偶集合A，在A上定义二元关系R如下：<,>∈R,当且仅当xv=yu，证明：R是一个等价关系。晓津证明如下：(1)因为xv=yu，则有x/y=u/v且有x/y=x/y,u/v=u/v因此有<,>∈R，<,>∈R所以R是自反的。(2)因为xv=yu,则有x/y=u/v，且有u/v=x/y,因此有<,>∈R，所以R是对称的。(3)设有s,t,∈A若有x/y=u/v且u/v=s/t则s/t=x/y,则有x/y=s/t因此有<,>∈R所以R是传递的。因而R是一个等价关系。7、设集合A有4个元素，那么，A中有多少个划分？A上有多少个等价关系？解：有下列几种划分：{{},{},{},{}} 四个元素的划分有1个{{},{},{}} 三个元素的划分有12种{{},{}} 二个元素的划分有6种{{}} 一个元素的划分有1种 总共有20种划分。 20种划分对应20种等价关系阮允准提醒说划分只有15种，晓津现给出确定的结果，三个元素的划分只有6种，二个元素的划分有7种。总共15种。8、设П1与П2是非空集合A的划分，问：П1∪П2、П1∩П2、和П1-П2是A的划分吗?在什么条件下，它们能构成A的划分。解：П1∪П2：不是A的划分。П1∩П2：不是划分。П1-П2:不是划分。在П1=П2的情况下，它们能构成A的划分晓津补充证明：(1)П1∪П2不一定是A的划分：若有S1∈Π1，S2∈Π2，有a∈A且a∈S1且a∈S2,则S1∪S2A,S1∪S2∈Π1∪Π2但S1∩S2≠φ所以，Π1∪Π2不一定是A的划分其他类似。3.8节习题参考答案1、画出A={3,9,27,54}上整除关系的哈斯图，并说明是否为全序关系。解：/={<3,3>,<3,9>,<3,27>,<3,54>,<9,9>,<9,27>,<9,54>,<27,27>,<27,54>,<54,54>}哈斯图见上。其不是全序关系。晓津认为这个关系应是全序关系,因为对于任意两个元素a,b,必有a<=b或b<=a。2、设A={1,2,3,4,5,6},R为A上的整除关系，试求：a)A的极大元、极小元、最大元和最小元。b)子集A1={2,3,6}和A2={2,3,5}的上界、下界、上确界、下确界。解：R={<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,4>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>}COVA={<1,2>,<1,3>,<1,5>,<2,4>,<2,6>,<3,6>}a)其极大元为{4,5,6}极小元{1}最大元不存在.最小元{1}从哈斯图上看出最大元、最小元、极小元、极大元的方法:以下均就A是一个偏序集而言，B包含于A，求B中的极大元、极小元、最大元、最小元。(1)极大元：在B的哈斯图中每一个孤立结点或只有下方连线的结点都是B的极大元。(2)极小元：在B的哈斯图中每一个孤立结点或只有上方连线的结点都是B的极小元。(3)最大元和最小元：首先找出B的极大元和极小元。若极大元或极小元只有一个，则这个极大元或极小元就是B的最大元或最小元；若不止一个，则B的最大元或最小元不存在。b)A1的上界、上确界为{6}下界、下确界为{1} A2的上界、上确界不存在，下界、下确界为{1}从哈斯图上看出上界、上确界、下界、下确界的方法:A是一个偏序集，B包含于A，在哈斯图中，求B的上界、上确界，下界、下确界。在A的哈斯图中，标出B中的结点，则不低于(不高于)其中最高结点(最低结点)并有与它们均相连且只通过下方(上方)直线相连(包括环)的结点都为B的上界(下界)；在上界集(下界集)中距B中最高结点(最低结点)路径最短的结点是上确界(下确界)。3、设集合R是A上的二元关系，证明：a)如果R是A上拟序关系，则r(R)=R∪IA是偏序关系。b)如果R是一偏序关系，则R-IA是拟序关系。证明：a)R是A上拟序关系，则有：R是反自反和传递的。 R∪IA {|∈R∧x∈A∧y∈A∧xx}∪{|x∈A∧y∈A∧xRx} {|∈R∧x∈A∧y∈A∧xx∨xRx} {|∈R∧x∈A∧y∈A∧xRx} 可见R∪IA具有自反性 R具有传递性，则 ∈R且∈R，则必有∈R ∈R=>∈R∪IA ∈R=>∈R∪IA ∈R=>∈R∪IA ∈R∪IA且∈R∪IA，则必有∈R∪IA 可见R∪IA具有传递性 根据定理3.8.1R是拟序，则R必有反对称性=>R={|x,y∈A∧xRy∧x≠y∧yx} R∪IA {|x,y∈A∧xRy∧x≠y∧yx}∪{|x∈A∧y∈A∧xRx} {|x,y∈A∧xRy∧x≠y∧yx∧xRx} 可见R∪IA具有反对称性得证：r(R)=R∪IA是偏序关系b)如果R是一偏序关系，则R-IA是拟序关系。 简略证明：偏序关系与拟序关系相比，区别在于自反性和反自反性 而R一旦失去了IA，则自反性也就丢失了。故R-IA是拟序关系阮允准同学认为上述证明不够规范，给出证明如下：a)如果R是A上拟序关系，则r(R)=R∪IA是偏序关系。a)对于任意x∈A,有＜x,x>∈IA∴∈R∪IA∴r(R)是自反的对于任意(x≠y)∈R∪IA∴∈R∵R是A上的拟序关系∴R又IA∴r(R)是反对称的设x,y,z∈A,且,∈R∪IA则,∈R或,∈IA ∴
