離散數(shù)學(xué)習(xí)題解第一部分(集合論部分)

1、離散數(shù)學(xué)輔助教材概念分析結(jié)構(gòu)思想與推理證明第一部分集合論劉國榮交大電信學(xué)院計(jì)算機(jī)系離散數(shù)學(xué)習(xí)題解答習(xí)題一 （第一章集合）1. 列出下述集合的全部元素： 1）A=x | x Nx是偶數(shù) x152）B=x|xN4+x=33）C=x|x是十進(jìn)制的數(shù)字解 1）A=2，4，6，8，10，12，142）B=Æ3）C=0，1，2，3，4，5，6，7，8，92. 用謂詞法表示下列集合：1）奇整數(shù)集合2）小于7的非負(fù)整數(shù)集合3）3，5，7，11，13，17，19，23，29解 1）nçnÎIÙ($mÎI)(n=2m+1)；2）nçnÎI

2、17;n³0Ùn<7；3）pçpÎNÙp>2Ùp<30ÙØ($dÎN)(d¹1Ùd¹pÙ($kÎN)(p=k×d)。3. 確定下列各命題的真假性：1）ÆÍÆ2）ÆÆ3）ÆÍÆ4）ÆÆ5）a，bÍa，b，c，a，b，c6）a,b(a，b，c，a，b，c)7）a，bÍa，b，a，b，8）a，ba，b，a，b，解1）

3、真。因?yàn)榭占侨我饧系淖蛹?）假。因?yàn)榭占缓魏卧兀?）真。因?yàn)榭占侨我饧系淖蛹?）真。因?yàn)?#198;是集合Æ的元素；5）真。因?yàn)閍，b是集合a，b，c，a，b，c的子集；6）假。因?yàn)閍,b不是集合a，b，c，a，b，c的元素；7）真。因?yàn)閍，b是集合a，b，a，b的子集；8）假。因?yàn)閍,b不是集合a，b，a，b的元素。4. 對任意集合A，B，C，確定下列命題的真假性： 1）如果ABBC，則AC。 2）如果ABBC，則AC。 3）如果AÌBBC，則AC。解 1）假。例如A=a，B=a，b，C=a，b，從而ABBC但AC。 2）假。例如A=a，B=a，a，C=

4、a，a，從而ABBC，但、AC。 3）假。例如A=a，B=a，b，C=a，a，b，從而ACBBC，但AC。5對任意集合A，B，C，確定下列命題的真假性： 1）如果ABBÍC，則AC。 2）如果ABBÍC，則AÍC。 3）如果AÍBBC，則AC。 3）如果AÍBBC，則AÍC。解 1）真。因?yàn)锽ÍCÛ"x（xBÞxC），因此ABÞAC。2）假。例如A=a，B=a，b，C=a，b，c從而ABBÍC，但AÏC。3）假。例如A=a，B=a，b，C=a，a，b，從而A

5、5;BBC，但AÏC。4）假。例如A=a，B=a，b，C=a，b，b，從而AÍBBC，但AÏC。6求下列集合的冪集：1）a，b，c2）a，b，c3）Æ4）Æ，Æ5）a，b，a，a，b，a，b，a，b解 1）Æ，a，b，c，a，b，a，c，b，c，a，b，c2），a，b，c，a，a，b3）Æ，Æ4）Æ，Æ，Æ，Æ，Æ5）Æ，a，b7給定自然數(shù)集合N的下列子集：A=1，2，7，8B= x|x250C=x|x可以被3整除且0x30D=x|x=2K，KI

6、OK6列出下面集合的元素：1） ABCD2） ABCD3） B（AC）4） （AB）D解 因?yàn)锽=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）ABCD=1，2，3，4，5，6，7，8，9，12，15，16，18，21，24，27，30，32，642）ABCD=Æ3）B（AC）=4，54）（AB）D=1，2，3，4，5，6，7，8，16，32，648設(shè)A、B、C是集合，證明：1）（AB）=A(BC)2）（AB）C=（AC）（BC）3）（AB）C=(AC)B證明 1）方法一：（AB）C=（AB）C

7、（差集的定義）=A（BC） （交運(yùn)算的結(jié)合律）=A（BC） （deMorgan律）=A（BC） （差集的定義）方法二：對任一元素x（AB）C，則xÏC，同時(shí)，xAB，xA，xÏB，所以，xA，xÏBC，即xA（BC），由此可見（AB）CÍA（BC）。反之，對任一元素xA（BC），則xA，且xÏBC，也就是說xÏA，xÏB，xÏC。所以x（AB）C，由此可見A（BC）Í（AB）C。因此A（BC）。2）方法一：（AB）C =A（BC） （根據(jù)1） =A（CB） （并運(yùn)算交換律） =A（CB） （01律） =A

8、（CB）（CC） （01律） =A（C（BC） （分配律） =（AC）（BC） （根據(jù)1） =（AC）（BC） （差集的定義）方法二：對任一元素x（AB）C，可知xA，xÏB，xÏC，xAC。又由xÏB，xÏBC，x（AC）（BC）（BC）。所以（AB）CÍ（AC）（BC）。反之，對任x（AC）（BC），可知xAC，xÏBC。由xAC，可知xA， xÏC。又因?yàn)閤ÏBC及xÏC，可知xÏB。所以，x（AB）C。因此（AB）CÍ（AB）C。由此可得（AB）（BC）Í（AB）C。

9、3）方法一：（AC）C =A（BC） (根據(jù)1) =A（CB） （并運(yùn)算交換律） =（AC）B （根據(jù)1）方法二：對任一元素x（AB）C，可知xA，xÏB，xÏC。由為xA，xÏC，所以，xAC。又由xÏB，x（AC）B。所以，（AB）CÍ（AC）B。同理可證得 （AC）BÍ（AB）C。9. 設(shè)A、B是全集的子集，證明： AÍBÛAB=XÛAB=Æ解(采用循環(huán)證法)(1)先證AÍBÞAB=X；方法一：AB=A(AB) （因?yàn)闂l件AÍB及定理4）=(AA)B （的結(jié)合

10、律）=(AA)B （的交換律）=XB （互補(bǔ)律）=X （零壹律）方法二：AÍBÞAB=B （定理4）ÞB=AB （等號=的對稱性）ÞAB=A(AB) （兩邊同時(shí)左并上A）ÞAB=(AA)B （的結(jié)合律）ÞAB=(AA)B （的交換律）ÞAB=XB （互補(bǔ)律）ÞAB= （零壹律）方法三：因?yàn)锳ÍX且BÍX，所以根據(jù)定理2的3¢）就有ABÍ；另一方面，由于BÍAB 及根據(jù)換質(zhì)位律可得BÍAÍAB，因此，由互補(bǔ)律及再次應(yīng)用定理2的3¢），可得

11、X=BBÍAB，即XÍAB；所以，AB=。(2)次證AB=XÞAB=Æ；AB=XÞ(AB)=X （兩邊同時(shí)取補(bǔ)運(yùn)算）Þ(A)B=X （de Morgan律）ÞAB=X （反身律）ÞAB=X （零壹律）(3)再證AB=ÆÞAÍB；方法一：A=AX (零壹律)=A(BB) (互補(bǔ)律)=(AB)(AB) (分配律)=(AB)Æ (條件AB=Æ)=AB (零壹律)ÍB （定理2的3)）方法二：AB=ÆÞB=BÆ (零壹律)=B(AB)

12、 （條件AB=Æ）=(BA)(BB) (分配律)=(AB)(BB) (的交換律)=(AB)X (互補(bǔ)律)=AB (零壹律)ÞAÍB （定理4的2)）10. 對于任意集合A，B，C，下列各式是否成立，為什么？1） AB=ACÞB=C2） AB=ACÞB=C解 1）不一定。例如：A=a，B=a，b，C=b。顯然有AB=AC，但BC。2）不一定。例如：A=a，B=a，b，C=b，c。顯然有AB=AC，但BC。11設(shè)A，B為集合，給出下列等式成立的充分必要條件：1） AB=B2） AB=BA3） AB=AB4） AÅB=A解 1）AB=AB，

13、由假設(shè)可知AB=B，即AB=B。由此可知B=ABÍB，故此B=BB=Æ。由假設(shè)可知A=AÆ=AB=B=Æ。所以當(dāng)AB=B時(shí)有A=B=ÆÆ。反之，當(dāng)A=B=Æ時(shí)，顯然AB=B。因此AB=B的充分必要條件是A=B=Æ。2）設(shè)ABÆ，則有元素aAB，那么，aA，而由假設(shè)AB=BA。所以aBA，從而aÏA，矛盾。所以AB=，故AÍB。另一方面由BA=AB=Æ。可得BÍA。因此當(dāng)AB=BA時(shí)，有A=B。反之，當(dāng)A=B時(shí)，顯然AB=BA=Æ因此，AB=BA的充要條件是

14、A=B。3）由于AB=AB，從而AÍAB=ABÍB，以及BÍAB=ABÍA故此AB=AB，有A=B。5） 根據(jù)定理6的1）有AÅÆ=A，由已知條件AÅB=A，可得AÅB=AÅÆ。從而由對稱差的消去律可得B=Æ。反之，若B=Æ，則AÅB=AÅÆ=A。所以AÅB=A的充分必要條件為B=Æ。12. 對下列集合，畫出其文圖：1） AB2） A（BC）3） A（BC）解ABA BA (B C ) BCA (B C )ACBAXX13.

15、用公式表示出下面圖中的陰影部分解ACBx(ABC)(ABC)BCAx(AC) B14. 試用成員表法證明1）（AÅB）ÅC=A（BÅC）2）（AB）（BC）ÍAB解 1）成員表如下A B CAÅB（AÅB）ÅCBÅCAÅ（BÅ） 成員表中運(yùn)算結(jié)果Å及Å（Å）的兩列狀態(tài)表明，全集中的每一個(gè)體對它倆有相同的從屬關(guān)系，故（Å）ÅÅ（Å）1） 成員表如下：A B CAB（BC）(BC)(AB)(BC)BAB 110 0010 0000

16、 1000 0111 1011 11000 10000成員表中運(yùn)算結(jié)果（AB）（BC）及AB的兩列狀態(tài)表明，全集中的每一個(gè)體，凡是從屬（AB）（BC）的，都從屬AB，故（AB）（BC）ÍAB注：自然數(shù)集N取為1，2，3，n，習(xí)題二（第二章 關(guān)系）1設(shè)A=1，2，3，B=a，b求 1）A×B 2）B×A 3）B×B 4）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），

17、（a，b），（b，a），（b，b）4）2B=Æ，a，b，a，b2B×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Æ，則存在元素xA×A，故有y1，y2A，使x=（y1，y2），從而y1，y2A×A，故此有y1，y2，y3，y4，使y1=（y1，y2），y2=（y3，y4），。這說明A中每個(gè)元素x，其結(jié)構(gòu)為元組的無窮次嵌套構(gòu)

18、成，這不可能。我們討論的元素的結(jié)構(gòu)必須是由元組的有限次嵌套構(gòu)成。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Æ，因此對任何xA及任何yB就有（x，y）A×B，根據(jù)A×B=B×A，可得（x，y）B×A，故此可得xB，yA，因此而得AÍB且BÍA，所以由Í

19、;的反對稱性A=B。充分性：即證A=ÆB=ÆA=BÞA×B=B×A 這是顯然的。4證明（AB）×（CD）=（A×C）（B×D）證證法一：（元素法）對任一（x，y）（AB）×（CD） 有xAB，yCD，于是xA，xB，yC，yD。因而（x，y）A×C，且（x，y）B×D，所以（x，y）（A×C）（B×D）。因而（AB）×（CD）Í（A×C）（B×D）另一方面，對任一（x，y）（A×C）（B×D），于是有（x，

20、y）A×C且（x，y）B×D，因而xA，yC，xB yD。所以xAB，y（CD）。所以（x，y）（AB）×（CD）。因而（A×C）（B×D）Í（AB）×（CD）。綜合這兩個(gè)方面有（AB）×（CD）=（A×C）（B×D）。證法二：（邏輯法）對任何x,y(x,y)(AB)×(CD)ÞxABÙyCDÞ(xAÙxB)Ù(yCÙyD)Þ(xAÙyC)Ù(xBÙyD) (Ù的結(jié)合律、交換律

21、)Þ(x,y)A×CÙ(x,y)B×DÞ(x,y)(A×C)(B×D)由x，y的任意性，可得：(AB)×(CD)= (A×C)(B×D) 。5下列各式中哪些成立，哪些不成立？對成立的式子給出證明，對不成立的式子給出反例。 1）（AB）×（CD）=（A×C）（B×D） 2）（AB）×（CD）=（A×C）（B×D） 3）（AÅB）×（CÅD）=（A×C）Å（B×D） 4）（AB）&

22、#215;C=（A×C）（B×C） 5）（AÅB）×C=（A×C）Å（B×C）解 1）不成立。設(shè)A=a，B=b，C=c，D=d，則（a，-d）（AB）×（CD），但（a，-d）Ï（A×C）（B×D）。所以（AB）×（CD）=（A×C）（B×D）不成立。事實(shí)上有：（A×C）（B×D）Í（AB）×（C ）Í（AB）×（CD）。2）不成立。設(shè)A=a，B=b，C=D=c，則（a，c）（A×C）（

23、B×D）但（a，c）Ï（AB）×（CD）。因而（Ab）×（CD）=（A×C）（B×D）不成立。事實(shí)上有：（AB）×（CD）Í（A×C）（B×D）。因?yàn)锳BÍA，CDÍ，故有（A×C）（B×D）Í A×C；又若（x，y）（AB）×（CD）故此xAB，從而xÏB，yCD，從而yÏD，故此（x，y）ÏB×D綜合這兩方面，有（AB）×（CD）Í（A×C）（B

24、5;D）。 3）不成立。設(shè)A=a，B=b，C=a，D=b，則（a，b）（AÅB）×（CÅD），但（a，b）Ï（A×C）Å（B×D）。所以（AÅB）×（CÅD）Í（A×）Å（B×D）不成立。又設(shè)A=a，B=b，C=a，D=c 則（a，c）（A×）Å（B×D），但（a，c）Ï（AÅB）×（CÅD）。所以（A×）Å（B×D）Í（AÅB）

25、5;（CÅD）不成立。因此（AÅB）×（CÅD）與（A×）Å（B×D）無任何包含關(guān)系。總之（AÅB）×（CÅD）=（A×）Å（B×D）不成立。4）成立。證明如下：對任一（x，y）（AB）×C，有xA，xÏB，yC 于是（x，y）A×C，且（x，y）（AB）×C，且（x，y）ÏB×C（否則xB），所以（x，y）（A×C）（B×C）。因而（AB）×CÍ（A×C）

26、（B×C）。又對任一（x，y）（A×C）（B×C），有（x，y）A×C，且（x，y）ÏB×C從而xA，yC及xÏB。即xAB，yC，故此（x，y）（AB）×C。所以（A×C）（B×C）Í（A×B）×C。因而（AB）×C=（A×C）（B×C）。另一種證明方法：（A×B）×C=（AB）×C（差集的定義）=（A×C）（B×C）（叉積對交運(yùn)算的分配律）=（A×C）（B×C）（

27、因（B×C）=（B×C）（B×C）（B×C）但（A×C）（B×C）=（A×C）（B×C）Æ=（A×C）（B×C）=（A×C）（B×C）（差集的定義）證法三：（邏輯法）對任何x,y(x,y)(A×C) (B×C)Þ(x,y)A×CÙ(x,y)ÏB×CÞ(xAÙyC)Ù(xÏBÚyÏC)Þ(xAÙyCÙx

28、7;B)Ú(xAÙyCÙyÏC) (Ù對Ú的分配律)Þ(xAÙxÏBÙyC)Ú(xAÙyCÙyÏC) (Ù的結(jié)合律、交換律)Þ(xAÙxÏB)ÙyC (Ù及Ú的零壹律、Ù的結(jié)合律)ÞxA BÙyCÞ(x,y)(A B)×C由x，y的任意性，可得：(A B)×C=(A×C) (B×C) 。5）成立。證明如下：對

29、任一（x，y）（AÅB）×C，故此xAÅB，yC于是xA且xÏB，或者xÏA且xB。因此（x，y）（A×C）Å（B×C）。所以（AÅB）×CÍ（A×C）Å（B×C）。對任一（x，y）（A×C）Å（B×C）。則（x，y）A×C且（x，y）ÏB×C，或者（x，y）ÏA×C且（x，y）B×C。因此xA，yC，xÏB，或者xB，yC，xÏA。所以xAB，或

30、xBA，并且yC，故此 xAÅB，yC。因此（x，y）（AÅB）×C，即（A×C）Å（B×C）Í（AÅB）×C。綜合兩方面、就有（AÅB）×C=（A×C）Å（B×C）另一種證明方法：（AÅB）×C=（AB）（BA）×C（對稱差的定義）=（AB）×C）（BA）×C）（叉積對并運(yùn)算的分配律）=（A×C）（B×C）（B×C）（A×C）（根據(jù)4）=（A×C）

31、7;（B×C）（對稱差的定義）6設(shè)A=1，2，3，B=a，求出所有由A到B的關(guān)系。解：R0=Æ，R1=（1，a），R2=（2，a），R3=（3，a），R4=（1，a），（2，a），Rs=（1，a），（3，a），R6=（2，a），（3，a），R7=（1，a），（2，a），（3，a）7設(shè)A=1，2，3，4，R1=（1，3），（2，2），（3，4），R2=（1，4），（2，3），（3，4），求：R1R2，R1R2，R1R2，R1，（R1），（R2），（R1），（R2），（R1R2），（R1R2）解：R1R2=（1，3），（1，4），（2，2），（2，3），（3，4）R1R2=（3

32、，4）R1R2=（1，3），（2，2）R1=（A×A）R=（1，1），（1，2），（1，4），（2，1），（2，3），（2，4），（3，1），（3，2），（3，3），（4，1），（4，2），（4，3），（4，4）（R1）=1，2，3，（R1）=2，3，4，（R2）=1，2，3，（R2）=3，4（R1R2）=1，2，3，（R1R2）=48對任意集合A及上的關(guān)系R1和R2，證明1）（R1R2）=（R1）（R2）2）（R1R2）（R1）（R2）證 1）一方面，由于R1R1R2，R2R1R2，根據(jù)定理1，有（R1）（R1R2），（R2）（R1R2）故（R1）（R2）（R1R2）另一方面，若x

33、（R1R2）那么存在著yA，使（y，x）（R1R2）因此（y，x）R1，或者（y，x）R2，從而x（R1）或者x（R2）于是x(R1) （R2），所以（R1R2）（R1）（R2）。11設(shè)A=1，2，3，4，定義A上的下列關(guān)系R1=（1，1），（1，2），（3，3），（3，4），R2=（1，2），（2，1）R3=（1，1），（1，2），（2，2），（2，1），（3，3），（3，4），（4，3），（4，4）R4=（1，2），（2，4），（3，3），（4，1）R5=（1，2），（1，3），（1，4），（2，3），（2，4），（3，4）R6=A×A，R7=Æ請給出上述每一個(gè)關(guān)系的關(guān)

34、系圖與關(guān)系矩陳，并指出它具有的性質(zhì)。解：1 0 0 23 0 0 4 1） R1是反對稱的，傳遞的。2）R2是反自反的，對稱的。3）R3是自反的，對稱的，傳遞的，因此是等價(jià)關(guān)系。循環(huán)的 綜合這兩方面，就有（R1R2）=（R1）（R2）。2）由于R1R2R1，R1R2R2，根據(jù)定理1，有（R1R2）（R1），（R1R2）R2，所以（R1R2）（R1）（R2）反方向的包含不成立，反全由第7題可得，那里（R1R2）=4，（R1）（R2）=2，3，43，4=3，4因此（R1）（R2）（R1R2）9設(shè)A有n個(gè)元素的有限集合，請指出A上有多少個(gè)二元關(guān)系？并闡明理由。解 A上有2n2個(gè)元關(guān)系。因?yàn)椴娣eA&#

35、215;A有n2個(gè)元素，因而A×A有2n2個(gè)子集，而每個(gè)子集都是A上的一個(gè)二元關(guān)系。10定義在整數(shù)集合I上的相等關(guān)系、“”關(guān)系、“”關(guān)系，全域關(guān)系，空關(guān)系，是否具有表中所指的性質(zhì)，請用Y（有）或N（元）將結(jié)果填在表中。性質(zhì)關(guān)系自反的反自反的對稱的反對稱的傳遞的相等關(guān)系YNYYY關(guān)系YNNYY關(guān)系NYNYY全域關(guān)系YNYNY空關(guān)系NYYYY4） R4是反對稱的，循環(huán)的。5） R5是反自反的，反對稱的，傳遞的。6） R6是自反的，對稱的，傳遞的，循環(huán)的。從而是等價(jià)關(guān)系。7）R7是反自反的對稱的，傳遞的，循環(huán)的，反傳遞的，反對稱的。 12設(shè)A是A上的關(guān)系，證明 1）R是自反的當(dāng)且反當(dāng)IAR

36、2）R是反自反的當(dāng)且僅當(dāng)IAR=Æ3）R是對稱的當(dāng)且反當(dāng)R=4） R是反對稱的當(dāng)且僅當(dāng)RIA5）R是傳遞的當(dāng)且僅當(dāng)RRR證 1）必要性若R是自反的，則對任何xA，都有（x，x）R，但是IA=（x，x）|xA，所以IAR。充分性若IAA則由IA=（x，x）|xA，可知對任何xA，都有（x，x）R，所以R是自反的。2）必要性若R是反自反的，則對任何xA，都是（x，x）ÏR，從而（x，x）R，由IA=（x，x）|xA 可知IAR。于是IARRR=Æ，另外ÆIAR，所以IAR=Æ。充分性若IAR=Æ，則R是反自反的。否則，不是反自反的，那么應(yīng)

37、存在某一x0A，使得（x0，x0）R。但是（x0，x0）IA，從而（x0，x0）Æ。這不可能，矛盾。3）必要性，若R是對稱的，則對任何（x，y）R，就有（y，x）R。于是根據(jù)逆關(guān)系的定義，可得（x，y），于是R；對任何（x，y），由逆關(guān)系的定義，可得（y，x）R。再次利用R的對稱性有（y，x）R，于是R；綜合兩方面，有R=。充分性若R= ，則對任何（x， y）R，由R=可得（x，y）。從而由逆關(guān)系的定義，可知（y，x）R這說明R是對稱的。4）必要性若R是反對稱的，則對任何（x，y），即有（x， y）R及（x，y），從逆關(guān)系的定義，就有（x， y）R及（y，x）R，因此，利用R的反對稱

38、性，可得x=y。于是就有（x，y）=（x，x）IA，所以RIA。充分性若R IA，則對任何（x，y）R及（y，x）R，從逆關(guān)系的定義，可得（x，y）R及（x，y），也即（x，y）R，利用R =IA可得（x，y）IA，于是x=y。所以R是反對稱的。5）必要性若R是傳遞的，則對任何（x，y）RR，由復(fù)合關(guān)系的定義可知，存在著yA，使（x，y）R且（y，y）R，從而利用R的傳遞性，可知（x，y）R。所以RRR。充分性RR。從而利用RRR可得（x，y）R。所以R是傳遞的。證法二：1)Þ):對任何x，xAÞ(x,x)IA (IA是幺關(guān)系，因此是自反關(guān)系)Þ(x,x)R (R

39、是自反關(guān)系)所以 IAÍR ；Ü):對任何xA，xAÞ(x,x)IA (IA是幺關(guān)系，因此是自反關(guān)系)Þ(x,x)R (因IAÍR)所以，R是自反關(guān)系；2)Þ)首先 ÆÍIAÇR ；其次，對任何x，yA，若(x,y)IAÇRÞ(x,y)IAÙ(x,y)RÞx=yÙ(x,y)R (IA是幺關(guān)系，因此是自反關(guān)系)Þ(x,x)R則與R是反自反關(guān)系，(x,x)ÏR矛盾。故IAÇRÍÆ ；因此，由包含關(guān)系Í

40、的反對稱性，可得 IAÇR=Æ ；Ü):對任何xA，若(x,x)RÞ(x,x)IAÙ(x,x)R (IA是幺關(guān)系，因此是自反關(guān)系)Þ(x,x)IAÇRÞ(x,x)Æ (因IAÇR=Æ)則與空集不含任何元素，(x,x)ÏÆ矛盾。故對任何xA，(x,x)ÏR ；所以，R是反自反關(guān)系；3)Þ)對任何x，yA(x,y)RÛ(y,x)R (R是對稱關(guān)系)Û(x,y)所以，R=；Ü):對任何x,yA(x,y)RÞ(x,

41、y) (R=)Þ(y,x)R所以，R是對稱的；4)Þ)對任何x，yA(x,y)RÇÞ(x,y)RÙ(x,y)Þ(x,y)RÙ(y,x)RÞx=y (R是反對稱關(guān)系)Þ (x,y)IA (IA是自反關(guān)系)所以，RÇÍIA ；Ü):對任何x,yA(x,y)RÞ(x,y) (R=)Þ(y,x)R所以，R是對稱的；13設(shè)A、B為有窮集合，R，SA×B，MR=（xij）m×n，MS=（yij）m×n1）為了RS，必須且只須"i

42、"j（xij yij）2）設(shè)MRS=（Zij）m×n，那么Zij=xijVyij，I=1，2，m，j=1，2，n.3）設(shè)MRS=（tij）m×n，那么tij=xijyij i=1，2，m；j=1，2，n.證 由于A、B是有窮集合，不妨設(shè)A=a1，a2，am，B=b1，b2，bn1）必要性若RS，則對任何i1，2，m，對任何j1，2，n，若（ai，bj）R，則R的關(guān)系矩陣MR=（xij）m×n中第I行第j列元素xij=1，根據(jù)RS，可得（ai，bj）S，從而得S的關(guān)系矩陣MS=（yij）m×n中第I行第j列元素yij=1，由于是11故此xijyi

43、j；若（ai，bj）ÏR，則R的關(guān)系矩陣MR=（xij）m×n中第i行第j列元素xij=0，因此由S的關(guān)系矩陣MS=（yij）m×n中第j列元素yij0，可得xijyij?？傊?，有（"i）("j)（xijyij）。2）充分性若（"i）("j)（xijyij），則對任何（ai，bj）R，就有R的關(guān)系矩陣MR=（xij）m×n中第i行第j列元素xij=1，由于xijyij，所以yij1，故此yij1這說明S的關(guān)系矩陣MS=（yij）m×n中第i行第j列元素yij為1，因此必有（ai，bj）S，所以RS。2）對

44、任何i1，2，m，對任何j1，2，n若Zij=1，則（ai，bj）RS，故此（ai，bj）R或者（ai，bj）S，于是xij=1或者yij=1。從而bj）S，于是xij=0且yij=0。從而xijyij=0。因而Zij=xijyij=0；綜合上述兩種情況，就有zji=xijyij，i=1，2，m，j=1,2,n，。3）對任何i1，2，m，對任何j1，2，n。若tij=1，則（ai，bj）RS，故此（ai，bj）S且（ai，bj）S，于是xij=1，且yij=1從而xijyij=1。因而tij=xijyij=1；若tij=0，則（ai，bj）RS，故此（ai，bj）S，于是xij=0或者yij=

45、0，從而xijyij=0。因而tij=xijyij=0。綜合上述兩種情況，就有tij=xijyij，i=1，2，m，j=1，2，n。14設(shè)A=1，2，3，4，R1，R2為A上的關(guān)系，R1=（1，1），（1，2），（2，4），R2=（1，4），（2，3），（2，4），（3，2），求R1R2，R2R1，R1R2R1解 ，1） 無論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得R1R2=（1，3），（1，4） R1 R22）無論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得R2R1=（3，4） R2 R13）無論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得R1R2R1=Æ 4）無論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得

46、R1R1=（1，1），（1，2），（1，4） R1 R1 R115）設(shè)R1，R2，R3是A上的二元關(guān)系，如果R1R2，證明1）R1R3R2R3 2）R3R1R3R2證明 1）對任何（x，y）R1R3，由復(fù)合關(guān)系之定義，必存在zA，使得（x，z）R1且（z，y）R3，利用R1R2可知（x，z）R2且（z，y）R3，再次利用復(fù)合關(guān)系之定義，有（x，y）R2R3。所以R1R3R2R3。2）對任何（x，y）R3R1，由復(fù)合關(guān)系之定義，必有zA，使得（x，z）R3且（z，y）R1，再由復(fù)合關(guān)系之定義，有（x，y）R3R2。所以R3R1R3R2。16設(shè)A是有限個(gè)元素的集合，在A上確定兩個(gè)不同的關(guān)系R1和R

47、2，使得=R1，=R2因?yàn)?，令R1=Æ，則R1R1=Æ，故此=R1=Æ。令R2=A×A，則=R2R2A×A=R2，故需證明R2R2R2=。為此，對任何x，yA，（x，y）A×A=R2，一定存在著zA（至少有z=x或z=y存在），使（x，z）A×A=R2且（z，y）A×A=R2，故此（x，y）R2R2=，所以R2R2R2=。于是=R2=A×A。2）由于A是有限個(gè)元素的集合，是不心設(shè)A=a1，a2，an令R1=（ai，aj）|aiAajA|in|jn-|R2=（an，an）R1 則R1R2，即R1與R1是不同

48、的關(guān)系。我們來證明=R1，=R2，（a）先征=R1若（ai，aj）R1，則由R1的定義必定1in，1in-1，并且一定存在著1kn-1（至少有k=j存在），使（ai，ak）R1且（ak，aj）R1，從而（ai，aj）R1R1=。故此R1。若（ai，aj）= R1R1，則存在著k，1kn-1，使（ai，ak）R1且（ak，aj）R1，于是由R1的定義，必有1in，1jn-1，從而根據(jù)R1的定義，有（ai，aj）R1。故此= R1綜合兩個(gè)方面，可得= R1。（b）次證=R2若（ai，aj）R2，則由R2的定義，要么1in，1jn-1，要么I=n，j=n 若1in，1jn-1，則一定存在著1kn-1

49、（至少有k=j存在），使（ai，ak）R2且（ak，aj）R2，從而（ai，aj）R2R2=；若i=n，j=n，則（ai，aj）=（an，an）R2，那么（an，an）R2，所以（ai，aj）=（an，an）R2R2=因此R2=。若（ai，aj）= R2R2，則存在著k，使（ai，ak）R2且（ak， ai）R2，于是由R2的定義，有k=n或者1kn-1。若k=n，則由（ai，ak）R2必有I=n，所以無論1jn-1還是j=n，由R2的定義，有（ai，aj）=（an，aj）R2；若1kn-1，則由（ai，ak）R2必有1jn-1故此（ai，aj）R2總之證得= R2，綜合兩方面，我們證明了=

50、R2。17設(shè)R是集合A上的反對稱關(guān)系，|A|=h，指了在R的關(guān)系矩陣中有多少個(gè)非零值？解 由第12題的4） R是反對稱關(guān)系當(dāng)且反當(dāng)RIA，及|A|=n可知，在R 的關(guān)系矩陣中非零值最多不超過n個(gè)。18設(shè)R1和R2是集合A上的關(guān)系，判斷下列命題的真假性，并闡明理由。1） 如果R1和R2都是自反的，那么R1R2是自反的。2） 如果R1和R2都是反自反的，那未R1R2是反自反的。3） 如果R1和R2都是對稱的，那末R1R2是對稱的。4） 如果R1和R2都是反對稱的，那末R1R2是反對稱的。5） 如果R1和R2都是傳遞的，那末R1R2是傳遞的。解 1）真。由于R1和R2和R2都是自反的，因而對任何，都

51、有（x，x）R1，（x，x）R2。因此，對任何xA，都有（x，x） R1R2。所以R1R2是自反的。2）假。令A(yù)=a，b，R1=（a，b），R2=b，a。那么R1R2=（a，a），它就不是A上的反自反關(guān)系。3）假。令A(yù)=a，b，c，R1=（a，b），（b，a），R2=（b，c），（c，b）。那末R1R2=（a，c），就不是A的對稱關(guān)系。4）假。令A(yù)=a，b，c，d，R1=（a，c），（b，c）R2=（c，b），（d，a）易證R1，R2都是反對稱關(guān)系。但是R1R2=（a，b），（b，a）就不是A上的反對稱關(guān)系。5）假。令A(yù)=a，b，c，R1=（a，c），（b，a），（b，c），R2=（c，b），

52、（a，c），（a，b），易證R1和R2都是傳遞關(guān)系，但R1R2=（a，b），（b，b），（b，c）就不是A上的傳遞關(guān)系。19設(shè)A=1，2，3，4，5，RA×A，R=（1，2），（2，3），（2，5），（3，4），（4，3），（5，5）用作圖方法矩陣運(yùn)算的方法求r（R），s（R），t（R）。解 1）作圖法：R的關(guān)系圖 （R）的關(guān)系圖51234123455143253241 S（R）的關(guān)系圖 t（R）的關(guān)系圖因此：r（R）=（1，1），（1，2），（2，2），（2，3），（2，5），（3，3），（3，4），（4，3），（4，4），（5，5）s（R）=（1，2），（2，1），（2，3），（2，5），（3，2），（3，4），（4，3），（5，2），（5，5）t（R）=（1，2），（1，3），（1，4），（1，5），（2，3），（2，4），（2，5），（3，3），（3，4），（4，3），（4，4），