离散的数学结构课后习题解答

《离散的数学结构课后习题解答》由会员分享，可在线阅读，更多相关《离散的数学结构课后习题解答（166页珍藏版）》请在装配图网上搜索。

1、离散数学辅助教材概念分析结构思想与推理证明第一部分集合论刘国荣交大电信学院计算机系离散数学习题解答习题一 （第一章集合）1. 列出下述集合的全部元素： 1）A=x | x Nx是偶数 x152）B=x|xN4+x=33）C=x|x是十进制的数字解 1）A=2，4，6，8，10，12，142）B=3）C=0，1，2，3，4，5，6，7，8，92. 用谓词法表示下列集合：1）奇整数集合2）小于7的非负整数集合3）3，5，7，11，13，17，19，23，29解 1）nnI($mI)(n=2m+1)；2）nnIn0n2p30($dN)(d1dp($kN)(p=kd)。3. 确定下列各命题的真假性：1

2、）2）3）4）5）a，ba，b，c，a，b，c6）a,b(a，b，c，a，b，c)7）a，ba，b，a，b，8）a，ba，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的元素；7）真。因为a，b是集合a，b，a，b的子集；8）假。因为a,b不是集合a，b，a，b的元素。4. 对任意集合A，B，C，确定下列命题的真假性： 1）如果ABBC，则AC。 2）如果ABBC，则AC。 3）如果ABBC，则AC。解

3、 1）假。例如A=a，B=a，b，C=a，b，从而ABBC但AC。 2）假。例如A=a，B=a，a，C=a，a，从而ABBC，但、AC。 3）假。例如A=a，B=a，b，C=a，a，b，从而ACBBC，但AC。5对任意集合A，B，C，确定下列命题的真假性： 1）如果ABBC，则AC。 2）如果ABBC，则AC。 3）如果ABBC，则AC。 3）如果ABBC，则AC。解 1）真。因为BCx（xBxC），因此ABAC。2）假。例如A=a，B=a，b，C=a，b，c从而ABBC，但AC。3）假。例如A=a，B=a，b，C=a，a，b，从而ABBC，但AC。4）假。例如A=a，B=a，b，C=a，b，

4、b，从而ABBC，但AC。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给定自然数集合N的下列子集：A=1，2，7，8B= x|x250C=x|x可以被3整除且0x30D=x|x=2K，KIOK6列出下面集合的元素：1） ABCD2） ABCD3） B（AC）4） （AB）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）ABCD=1，2，

5、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设A、B、C是集合，证明：1）（AB）=A(BC)2）（AB）C=（AC）（BC）3）（AB）C=(AC)B证明 1）方法一：（AB）C=（AB）C （差集的定义）=A（BC） （交运算的结合律）=A（BC） （deMorgan律）=A（BC） （差集的定义）方法二：对任一元素x（AB）C，则xC，同时，xAB，xA，xB，所以，xA，xBC，即xA（BC），由此可见（AB）CA（BC）。反之，对任一元素xA

6、（BC），则xA，且xBC，也就是说xA，xB，xC。所以x（AB）C，由此可见A（BC）（AB）C。因此A（BC）。2）方法一：（AB）C =A（BC） （根据1） =A（CB） （并运算交换律） =A（CB） （01律） =A（CB）（CC） （01律） =A（C（BC） （分配律） =（AC）（BC） （根据1） =（AC）（BC） （差集的定义）方法二：对任一元素x（AB）C，可知xA，xB，xC，xAC。又由xB，xBC，x（AC）（BC）（BC）。所以（AB）C（AC）（BC）。反之，对任x（AC）（BC），可知xAC，xBC。由xAC，可知xA， xC。又因为xBC及xC，可知x

7、B。所以，x（AB）C。因此（AB）C（AB）C。由此可得（AB）（BC）（AB）C。3）方法一：（AC）C =A（BC） (根据1) =A（CB） （并运算交换律） =（AC）B （根据1）方法二：对任一元素x（AB）C，可知xA，xB，xC。由为xA，xC，所以，xAC。又由xB，x（AC）B。所以，（AB）C（AC）B。同理可证得 （AC）B（AB）C。9. 设A、B是全集的子集，证明： ABAB=XAB=解(采用循环证法)(1)先证ABAB=X；方法一：AB=A(AB) （因为条件AB及定理4）=(AA)B （的结合律）=(AA)B （的交换律）=XB （互补律）=X （零壹律）方法二

8、：ABAB=B （定理4）B=AB （等号=的对称性）AB=A(AB) （两边同时左并上A）AB=(AA)B （的结合律）AB=(AA)B （的交换律）AB=XB （互补律）AB= （零壹律）方法三：因为AX且BX，所以根据定理2的3）就有AB；另一方面，由于BAB 及根据换质位律可得BAAB，因此，由互补律及再次应用定理2的3），可得X=BBAB，即XAB；所以，AB=。(2)次证AB=XAB=；AB=X(AB)=X （两边同时取补运算）(A)B=X （de Morgan律）AB=X （反身律）AB=X （零壹律）(3)再证AB=AB；方法一：A=AX (零壹律)=A(BB) (互补律)=(

9、AB)(AB) (分配律)=(AB) (条件AB=)=AB (零壹律)B （定理2的3)）方法二：AB=B=B (零壹律)=B(AB) （条件AB=）=(BA)(BB) (分配律)=(AB)(BB) (的交换律)=(AB)X (互补律)=AB (零壹律)AB （定理4的2)）10. 对于任意集合A，B，C，下列各式是否成立，为什么？1） AB=ACB=C2） AB=ACB=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设A，B为集合，给出下列等式成立的充分必要条件：1） AB=B2）

10、 AB=BA3） AB=AB4） AB=A解 1）AB=AB，由假设可知AB=B，即AB=B。由此可知B=ABB，故此B=BB=。由假设可知A=A=AB=B=。所以当AB=B时有A=B=。反之，当A=B=时，显然AB=B。因此AB=B的充分必要条件是A=B=。2）设AB，则有元素aAB，那么，aA，而由假设AB=BA。所以aBA，从而aA，矛盾。所以AB=，故AB。另一方面由BA=AB=。可得BA。因此当AB=BA时，有A=B。反之，当A=B时，显然AB=BA=因此，AB=BA的充要条件是A=B。3）由于AB=AB，从而AAB=ABB，以及BAB=ABA故此AB=AB，有A=B。5） 根据定理

11、6的1）有A=A，由已知条件AB=A，可得AB=A。从而由对称差的消去律可得B=。反之，若B=，则AB=A=A。所以AB=A的充分必要条件为B=。12. 对下列集合，画出其文图：1） AB2） A（BC）3） A（BC）解ABA BA (B C ) BCA (B C )ACBAXX13. 用公式表示出下面图中的阴影部分解ACBx(ABC)(ABC)BCAx(AC) B14. 试用成员表法证明1）（AB）C=A（BC）2）（AB）（BC）AB解 1）成员表如下A B CAB（AB）CBCA（B） 成员表中运算结果及（）的两列状态表明，全集中的每一个体对它俩有相同的从属关系，故（）（）1） 成员表

12、如下：A B CAB（BC）(BC)(AB)(BC)BAB 110 0010 0000 1000 0111 1011 11000 10000成员表中运算结果（AB）（BC）及AB的两列状态表明，全集中的每一个体，凡是从属（AB）（BC）的，都从属AB，故（AB）（BC）AB注：自然数集N取为1，2，3，n，习题二（第二章 关系）1设A=1，2，3，B=a，b求 1）AB 2）BA 3）BB 4）2BB解 1）AB=（1，a），（1，b），（2，a），（2，a），（3，a），（3，b）2）BA=（a，1），（a，2），（a，3），（b，1），（b，2），（b，3）3）BB=（a，a），（a，b）

13、，（b，a），（b，b）4）2B=，a，b，a，b2BB（，a），（，b），（a，a），（a，b），（b，a），（b，b），（a，b，b）2使AAA成立的集合A存在吗？请阐明理由。解 一般地说，使AAA成立的集合A不存在，除非A=。否则 A，则存在元素xAA，故有y1，y2A，使x=（y1，y2），从而y1，y2AA，故此有y1，y2，y3，y4，使y1=（y1，y2），y2=（y3，y4），。这说明A中每个元素x，其结构为元组的无穷次嵌套构成，这不可能。我们讨论的元素的结构必须是由元组的有限次嵌套构成。3证明AB=BAA=B=A=B证 必要性：即证AB=BAA=B=A=B若AB=，则A=或者

14、B=若AB，则A且B，因此对任何xA及任何yB就有（x，y）AB，根据AB=BA，可得（x，y）BA，故此可得xB，yA，因此而得AB且BA，所以由的反对称性A=B。充分性：即证A=B=A=BAB=BA 这是显然的。4证明（AB）（CD）=（AC）（BD）证证法一：（元素法）对任一（x，y）（AB）（CD） 有xAB，yCD，于是xA，xB，yC，yD。因而（x，y）AC，且（x，y）BD，所以（x，y）（AC）（BD）。因而（AB）（CD）（AC）（BD）另一方面，对任一（x，y）（AC）（BD），于是有（x，y）AC且（x，y）BD，因而xA，yC，xB yD。所以xAB，y（CD）。所以

15、（x，y）（AB）（CD）。因而（AC）（BD）（AB）（CD）。综合这两个方面有（AB）（CD）=（AC）（BD）。证法二：（逻辑法）对任何x,y(x,y)(AB)(CD)xAByCD(xAxB)(yCyD)(xAyC)(xByD) (的结合律、交换律)(x,y)AC(x,y)BD(x,y)(AC)(BD)由x，y的任意性，可得：(AB)(CD)= (AC)(BD) 。5下列各式中哪些成立，哪些不成立？对成立的式子给出证明，对不成立的式子给出反例。 1）（AB）（CD）=（AC）（BD） 2）（AB）（CD）=（AC）（BD） 3）（AB）（CD）=（AC）（BD） 4）（AB）C=（AC）

16、（BC） 5）（AB）C=（AC）（BC）解 1）不成立。设A=a，B=b，C=c，D=d，则（a，-d）（AB）（CD），但（a，-d）（AC）（BD）。所以（AB）（CD）=（AC）（BD）不成立。事实上有：（AC）（BD）（AB）（C ）（AB）（CD）。2）不成立。设A=a，B=b，C=D=c，则（a，c）（AC）（BD）但（a，c）（AB）（CD）。因而（Ab）（CD）=（AC）（BD）不成立。事实上有：（AB）（CD）（AC）（BD）。因为ABA，CD，故有（AC）（BD） AC；又若（x，y）（AB）（CD）故此xAB，从而xB，yCD，从而yD，故此（x，y）BD综合这两方面，

17、有（AB）（CD）（AC）（BD）。 3）不成立。设A=a，B=b，C=a，D=b，则（a，b）（AB）（CD），但（a，b）（AC）（BD）。所以（AB）（CD）（A）（BD）不成立。又设A=a，B=b，C=a，D=c 则（a，c）（A）（BD），但（a，c）（AB）（CD）。所以（A）（BD）（AB）（CD）不成立。因此（AB）（CD）与（A）（BD）无任何包含关系。总之（AB）（CD）=（A）（BD）不成立。4）成立。证明如下：对任一（x，y）（AB）C，有xA，xB，yC 于是（x，y）AC，且（x，y）（AB）C，且（x，y）BC（否则xB），所以（x，y）（AC）（BC）。因而（A

18、B）C（AC）（BC）。又对任一（x，y）（AC）（BC），有（x，y）AC，且（x，y）BC从而xA，yC及xB。即xAB，yC，故此（x，y）（AB）C。所以（AC）（BC）（AB）C。因而（AB）C=（AC）（BC）。另一种证明方法：（AB）C=（AB）C（差集的定义）=（AC）（BC）（叉积对交运算的分配律）=（AC）（BC）（因（BC）=（BC）（BC）（BC）但（AC）（BC）=（AC）（BC）=（AC）（BC）=（AC）（BC）（差集的定义）证法三：（逻辑法）对任何x,y(x,y)(AC) (BC)(x,y)AC(x,y)BC(xAyC)(xByC)(xAyCxB)(xAyCyC

19、) (对的分配律)(xAxByC)(xAyCyC) (的结合律、交换律)(xAxB)yC (及的零壹律、的结合律)xA ByC(x,y)(A B)C由x，y的任意性，可得：(A B)C=(AC) (BC) 。5）成立。证明如下：对任一（x，y）（AB）C，故此xAB，yC于是xA且xB，或者xA且xB。因此（x，y）（AC）（BC）。所以（AB）C（AC）（BC）。对任一（x，y）（AC）（BC）。则（x，y）AC且（x，y）BC，或者（x，y）AC且（x，y）BC。因此xA，yC，xB，或者xB，yC，xA。所以xAB，或xBA，并且yC，故此 xAB，yC。因此（x，y）（AB）C，即（A

20、C）（BC）（AB）C。综合两方面、就有（AB）C=（AC）（BC）另一种证明方法：（AB）C=（AB）（BA）C（对称差的定义）=（AB）C）（BA）C）（叉积对并运算的分配律）=（AC）（BC）（BC）（AC）（根据4）=（AC）（BC）（对称差的定义）6设A=1，2，3，B=a，求出所有由A到B的关系。解：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设A=1，2，3，4，R1=（1，3），（2，2），（3，4），R2=（1，4），（2，3）

21、，（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，4）R1R2=（1，3），（2，2）R1=（AA）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及上的关系R1和R2，证明1）（R1R2）=（

22、R1）（R2）2）（R1R2）（R1）（R2）证 1）一方面，由于R1R1R2，R2R1R2，根据定理1，有（R1）（R1R2），（R2）（R1R2）故（R1）（R2）（R1R2）另一方面，若x（R1R2）那么存在着yA，使（y，x）（R1R2）因此（y，x）R1，或者（y，x）R2，从而x（R1）或者x（R2）于是x(R1) （R2），所以（R1R2）（R1）（R2）。11设A=1，2，3，4，定义A上的下列关系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）

23、R4=（1，2），（2，4），（3，3），（4，1）R5=（1，2），（1，3），（1，4），（2，3），（2，4），（3，4）R6=AA，R7=请给出上述每一个关系的关系图与关系矩陈，并指出它具有的性质。解：1 0 0 23 0 0 4 1） R1是反对称的，传递的。2）R2是反自反的，对称的。3）R3是自反的，对称的，传递的，因此是等价关系。循环的 综合这两方面，就有（R1R2）=（R1）（R2）。2）由于R1R2R1，R1R2R2，根据定理1，有（R1R2）（R1），（R1R2）R2，所以（R1R2）（R1）（R2）反方向的包含不成立，反全由第7题可得，那里（R1R2）=4，（R1）（R

24、2）=2，3，43，4=3，4因此（R1）（R2）（R1R2）9设A有n个元素的有限集合，请指出A上有多少个二元关系？并阐明理由。解 A上有2n2个元关系。因为叉积AA有n2个元素，因而AA有2n2个子集，而每个子集都是A上的一个二元关系。10定义在整数集合I上的相等关系、“”关系、“”关系，全域关系，空关系，是否具有表中所指的性质，请用Y（有）或N（元）将结果填在表中。性质关系自反的反自反的对称的反对称的传递的相等关系YNYYY关系YNNYY关系NYNYY全域关系YNYNY空关系NYYYY4） R4是反对称的，循环的。5） R5是反自反的，反对称的，传递的。6） R6是自反的，对称的，传递的

25、，循环的。从而是等价关系。7）R7是反自反的对称的，传递的，循环的，反传递的，反对称的。 12设A是A上的关系，证明 1）R是自反的当且反当IAR2）R是反自反的当且仅当IAR=3）R是对称的当且反当R=4） R是反对称的当且仅当RIA5）R是传递的当且仅当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，

26、所以IAR=。充分性若IAR=，则R是反自反的。否则，不是反自反的，那么应存在某一x0A，使得（x0，x0）R。但是（x0，x0）IA，从而（x0，x0）。这不可能，矛盾。3）必要性，若R是对称的，则对任何（x，y）R，就有（y，x）R。于是根据逆关系的定义，可得（x，y），于是R；对任何（x，y），由逆关系的定义，可得（y，x）R。再次利用R的对称性有（y，x）R，于是R；综合两方面，有R=。充分性若R= ，则对任何（x， y）R，由R=可得（x，y）。从而由逆关系的定义，可知（y，x）R这说明R是对称的。4）必要性若R是反对称的，则对任何（x，y），即有（x， y）R及（x，y），从逆关系

27、的定义，就有（x， y）R及（y，x）R，因此，利用R的反对称性，可得x=y。于是就有（x，y）=（x，x）IA，所以RIA。充分性若R IA，则对任何（x，y）R及（y，x）R，从逆关系的定义，可得（x，y）R及（x，y），也即（x，y）R，利用R =IA可得（x，y）IA，于是x=y。所以R是反对称的。5）必要性若R是传递的，则对任何（x，y）RR，由复合关系的定义可知，存在着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是幺关系，因此是自反

28、关系)(x,x)R (R是自反关系)所以 IAR ；):对任何xA，xA(x,x)IA (IA是幺关系，因此是自反关系)(x,x)R (因IAR)所以，R是自反关系；2)首先 IAR ；其次，对任何x，yA，若(x,y)IAR(x,y)IA(x,y)Rx=y(x,y)R (IA是幺关系，因此是自反关系)(x,x)R则与R是反自反关系，(x,x)R矛盾。故IAR ；因此，由包含关系的反对称性，可得 IAR= ；):对任何xA，若(x,x)R(x,x)IA(x,x)R (IA是幺关系，因此是自反关系)(x,x)IAR(x,x) (因IAR=)则与空集不含任何元素，(x,x)矛盾。故对任何xA，(x

29、,x)R ；所以，R是反自反关系；3)对任何x，yA(x,y)R(y,x)R (R是对称关系)(x,y)所以，R=；):对任何x,yA(x,y)R(x,y) (R=)(y,x)R所以，R是对称的；4)对任何x，yA(x,y)R(x,y)R(x,y)(x,y)R(y,x)Rx=y (R是反对称关系) (x,y)IA (IA是自反关系)所以，RIA ；):对任何x,yA(x,y)R(x,y) (R=)(y,x)R所以，R是对称的；13设A、B为有穷集合，R，SAB，MR=（xij）mn，MS=（yij）mn1）为了RS，必须且只须ij（xij yij）2）设MRS=（Zij）mn，那么Zij=xi

30、jVyij，I=1，2，m，j=1，2，n.3）设MRS=（tij）mn，那么tij=xijyij i=1，2，m；j=1，2，n.证 由于A、B是有穷集合，不妨设A=a1，a2，am，B=b1，b2，bn1）必要性若RS，则对任何i1，2，m，对任何j1，2，n，若（ai，bj）R，则R的关系矩阵MR=（xij）mn中第I行第j列元素xij=1，根据RS，可得（ai，bj）S，从而得S的关系矩阵MS=（yij）mn中第I行第j列元素yij=1，由于是11故此xijyij；若（ai，bj）R，则R的关系矩阵MR=（xij）mn中第i行第j列元素xij=0，因此由S的关系矩阵MS=（yij）mn

31、中第j列元素yij0，可得xijyij。总之，有（i）(j)（xijyij）。2）充分性若（i）(j)（xijyij），则对任何（ai，bj）R，就有R的关系矩阵MR=（xij）mn中第i行第j列元素xij=1，由于xijyij，所以yij1，故此yij1这说明S的关系矩阵MS=（yij）mn中第i行第j列元素yij为1，因此必有（ai，bj）S，所以RS。2）对任何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=

32、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=0，从而xijyij=0。因而tij=xijyij=0。综合上述两种情况，就有tij=xijyij，i=1，2，m，j=1，2，n。14设A=1，2，3，4，R1，R2为A上的关系，R1=（1，1），（1，2），（2，4），R2=（1

33、，4），（2，3），（2，4），（3，2），求R1R2，R2R1，R1R2R1解 ，1） 无论从复合关系图还是从复合关系矩阵都可得R1R2=（1，3），（1，4） R1 R22）无论从复合关系图还是从复合关系矩阵都可得R2R1=（3，4） R2 R13）无论从复合关系图还是从复合关系矩阵都可得R1R2R1= 4）无论从复合关系图还是从复合关系矩阵都可得R1R1=（1，1），（1，2），（1，4） R1 R1 R115）设R1，R2，R3是A上的二元关系，如果R1R2，证明1）R1R3R2R3 2）R3R1R3R2证明 1）对任何（x，y）R1R3，由复合关系之定义，必存在zA，使得（x，z）R

34、1且（z，y）R3，利用R1R2可知（x，z）R2且（z，y）R3，再次利用复合关系之定义，有（x，y）R2R3。所以R1R3R2R3。2）对任何（x，y）R3R1，由复合关系之定义，必有zA，使得（x，z）R3且（z，y）R1，再由复合关系之定义，有（x，y）R3R2。所以R3R1R3R2。16设A是有限个元素的集合，在A上确定两个不同的关系R1和R2，使得=R1，=R2因为，令R1=，则R1R1=，故此=R1=。令R2=AA，则=R2R2AA=R2，故需证明R2R2R2=。为此，对任何x，yA，（x，y）AA=R2，一定存在着zA（至少有z=x或z=y存在），使（x，z）AA=R2且（z，

35、y）AA=R2，故此（x，y）R2R2=，所以R2R2R2=。于是=R2=AA。2）由于A是有限个元素的集合，是不心设A=a1，a2，an令R1=（ai，aj）|aiAajA|in|jn-|R2=（an，an）R1 则R1R2，即R1与R1是不同的关系。我们来证明=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的定义，必

36、有1in，1jn-1，从而根据R1的定义，有（ai，aj）R1。故此= R1综合两个方面，可得= R1。（b）次证=R2若（ai，aj）R2，则由R2的定义，要么1in，1jn-1，要么I=n，j=n 若1in，1jn-1，则一定存在着1kn-1（至少有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-

37、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，综合两方面，我们证明了= R2。17设R是集合A上的反对称关系，|A|=h，指了在R的关系矩阵中有多少个非零值？解 由第12题的4） R是反对称关系当且反当RIA，及|A|=n可知，在R 的关系矩阵中非零值最多不超过n个。18设R1和R2是集合A上的关系，判断下列命题的真假性，并阐明理由。1） 如果R1和R2都是自反的，那么R1R2是自反的。2） 如果R1和R2都是反自反的，那

38、未R1R2是反自反的。3） 如果R1和R2都是对称的，那末R1R2是对称的。4） 如果R1和R2都是反对称的，那末R1R2是反对称的。5） 如果R1和R2都是传递的，那末R1R2是传递的。解 1）真。由于R1和R2和R2都是自反的，因而对任何，都有（x，x）R1，（x，x）R2。因此，对任何xA，都有（x，x） R1R2。所以R1R2是自反的。2）假。令A=a，b，R1=（a，b），R2=b，a。那么R1R2=（a，a），它就不是A上的反自反关系。3）假。令A=a，b，c，R1=（a，b），（b，a），R2=（b，c），（c，b）。那末R1R2=（a，c），就不是A的对称关系。4）假。令A=a

39、，b，c，d，R1=（a，c），（b，c）R2=（c，b），（d，a）易证R1，R2都是反对称关系。但是R1R2=（a，b），（b，a）就不是A上的反对称关系。5）假。令A=a，b，c，R1=（a，c），（b，a），（b，c），R2=（c，b），（a，c），（a，b），易证R1和R2都是传递关系，但R1R2=（a，b），（b，b），（b，c）就不是A上的传递关系。19设A=1，2，3，4，5，RAA，R=（1，2），（2，3），（2，5），（3，4），（4，3），（5，5）用作图方法矩阵运算的方法求r（R），s（R），t（R）。解 1）作图法：R的关系图 （R）的关系图512341234551

40、43253241 S（R）的关系图 t（R）的关系图因此：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），（5，5）2）矩阵运算法：Mr（R）=MS（R）=MRR=MRMR=MR=因此r（R），s（R），t（R）与1）作图法一致。20设RAA，证明1）（R+）+

41、R+2）=R*证明 1）一方面，由于（R+）+是R+的传递闭包，所以R+（R+）+；另一方面，由于R+是R的传递闭包，故此R+是传递的。由于R+R+及传递闭包（R+）+是包含R+的最小传递关系，就有（R+）+R+（定理4之3）；所以（R+）+=R+。2）一方面，由于（R*）*是R*的自反传递闭包，所以R*（R*）*；另一方面，由于R*是R的自反传递闭包，故此R*是自反的传递的。由于R*R*及自反传递闭包（R*）*是包含R*的最小自批传递关系，就有（R*）*R*（定理5的3）。所以（R*）*=R*。21设A=1，2，3，4，RAA，R=（1，2），（2，4），（3，4），（4，3），（3，3）

42、1）证明R不是传递的；2）求R1，使R1R并且R1是传递的；3）是否存在R2，使R2R，R2R1并且R2是传递的。解 1）由于（1，2）R且（2，4）R但（1，4） R，这说明R不是传递的。2)由于R+是包含R的最小传递关系，所以，取R1=R+即为所求。现在来R+R2=（1，4），（2，3），（3，3），（3，4），（4，3），（4，4）R3=（1，3），（2，3），（2，4），（3，3），（3，4），（4，3），（4，4）R4=（1，3），（1，4），（2，3），（2，4），（3，3），（3，4），（4，3），（4，4）故此R1=R+=RR2R3R4=（1，2），（1，3），（1，4），（2

43、，3），（2，4），（3，3），（3，4），（4，3）（4，4）（因为|A|=4有限）其关系图如下：1124311243R的关系图 R1的关系图3）能。因为R1并非全关系（否则，当R1是全关系时，就找不到了），所以只要取R2=AA是A上的全关系就可满足R2R，R2R，并且全关系R2显然是一个传递关系。22设A=1，2，3，4，9，定义AA上的关系如下：（a，b）R（c，d） a+d=b+c1） 证明R是AA上的等价关系；2） 求（2，5）R；3） RAA对吗？请阐明理由。1）证明 （a）R是自反的 对于任何（a，b）AA，由于a+b = b+a，所以（a，b）R（a，b）。（b）R是对称的对于

44、任何（a，b），（c，d）AA，若（a，b）R（c，d），则有a+d = b+c从而c+b+a，所以可得（c，d）R（a，b）。（c）R是传递的对于任何（a，b），（c，d），（e，f）AA，若（a，b）R（c，d），且（c，d）R（e，f），于是有a+d = b+c及c+f = d+e，二式相加有a+f+c+d = b+e+c+d，两边同时减c+d，可得a+f = b+e，从而可得（a，b）R（e，f）。综合（a）、（b）、（c）、说明R是AA上的等价关系。2）解 因为（2，5）R = （a，b）|（a，b）AA（a，b）R（2，5） = （a，b）|（a，b）AAa+5 = b+2 = （

45、a，b）|（a，b）AAb = a+3 =（1，4），（2，5，（3，6），（4，7），（5，8），（6，9）3）答 RAA不对。因为R是AA上的关系，所以R（AA）（AA）=。23设A是一个非空集合，RAA。如果R在A上是对称的，传递的，下面的推导说明R在A上是自反的：对任意的a，bA，由于R是对称的，有： aRbbRa于是aRbaRbbRa，又利用R是传递的，得：aRbbRaaRa从而说明R是自反的。上述推导正确吗？请阐明理由。答 上述推导不正解。推殖民地的谬论误在于假设A的每个元素都由R关联着A的某一别的元素。如果这不是真的，那么对称性的条件的假设就始终是假的，因此结论当然是假的。因而在一个空集上的空关系都是平凡的对称和可传递，但不是自反的。另外关系（a，a），（