资源描述
目 录第一章命题逻辑2第二章 谓词逻辑9第三章 集合论习题答案13第四章 二元关系习题答案21第五章 函数习题答案42第六章 代数系统习题答案51第七章 群与环习题答案57第八章 格与布尔代数习题答案66第九章 图的基本概念及其矩阵表示71第十章 几种图的介绍82第十一章 树90100 / 100文档可自由编辑打印第一章 命题逻辑1. （1）不是命题；（2）不是命题；（3）不是命题；（4）是命题；（5）是命题；2. （1）并非大连的每条街都临海；（2）2不是一个偶数或者8不是一个奇数；（3）2不是偶数并且-3不是负数；3.（1） 逆命题：如果我去公园，那么天不下雨。否命题：如果天下雨，我将不去公园。逆否命题：如果我不去公园，那么天下雨。（2） 逆命题：如果我逗留，那么你去。否命题：如果你不去，那么我不逗留。逆否命题：如果我不逗留，那么你不去。（3） 逆命题：如果方程无整数解，那么n是大于2的正整数。否命题：如果n不是大于2的正整数，那么方程有整数解。逆否命题：如果方程有整数解，那么n不是大于2的正整数。（4） 逆命题：如果我不能完成这项任务，那么我不获得更多的帮助。否命题：如果我获得更多的帮助，则我能完成这项任务。逆否命题：如果我能完成这项任务，则我获得更多的帮助。4. （1）T；（2）T；（3）T；（4）F；5.（1）PQR00010011010101111000101111011111（3）PQR00000010010101111001101111011110（2）（4）略6.（1） P:他聪明；Q:他用功；命题：PQ。（2） P:天气好；Q:我骑车上班；命题：QP。（3） P:老李是球迷；Q:小李是球迷；命题：PQ。（4） P:休息好；Q:身体好；命题：QP。7. 证明：PQPQQPP«Q001110110010010111118. 真值表：xyz(xy)zx(yz)(xy)zx（yz）0000000001001101000110110011100001110100111111111xyz(xy)zx(yz)(x«y)«zx«（y«z）0000100001111101001110111100100111110111001111111可得：，«是可结合的。9. （1）（PQ）R；（2）P；（3）（PQ）R10. 不依赖于命题变元的真值指派，而总取T（1）的命题公式，称为重言式（永真式）；不依赖于命题变元的真值指派，而总取F（0）的命题公式，称为永假式（矛盾式）；至少存在一组真值指派使得命题公式取值为T的命题公式称为可满足的。本题可用真值表求解：（4）得真值表如下：PQ001011101111可见不论命题变元的真值指派如何，命题公式总取1，故为重言式。（8）得真值表如下：PQR00010011010101111001101111011111可见不论命题变元的真值指派如何，命题公式总取1，故为重言式。其他小题可用同样的方法求解。11. （2）原式Û (PQ)R)PRÛ (PQ)RPRÛ (PQ)PTÛ T（4）原式Û P（QR）P）Û P（QRP）Û PQRÛ （PQR）第（1）、（3）、（5）小题方法相同，解答略。12. （3）原式Û PQ（RP）Û （PQR）（PQP）Û （PQR）FÛ （PQR）第（1）、（2）小题方法相同，解答略。13. （2）左式Û（P（QQ）（PQ）Û （PF）（PQ）Û （PP）（PQ）Û F（PQ）Û PQ右式Û PQ故：左式Û右式，证明完毕。根据对偶式定义，该式的对偶式为：（PQ）（PQ）（PQ）第（1）、（3）小题方法相同，解答略。14. （1）原式Û（P（PQ）QÛ（PP）（PQ）QÛ（F（PQ）QÛ（PQ）QÛ PTÛ T（3）原式Û（PQ）（QR）（PR）Û（PQ）（QR）（PR）Û（PQ）Q）（PQ）R）（PR）Û（PQ）（QQ）（PR）（QR）（PR）Û（P（QR）（QR）（PR）Û（P（QR）Q）（P（QR）R）（PR）Û（P Q）（QRQ）（P R）（QRR）（PR）Û（P Q）（P R）（QR）（P R）Û（P Q）（QR）TÛ T第（2）、（4）小题方法相同，解答略。15. （1）证明：假设PQ为真，则P为真且Q为真，则PQ为真。所以：PQ Þ PQ。（3）证明：右侧ÛPQ，假设PQ为假，则P为真且Q为假，则PQ为假。所以：PQ Þ PPQ。（5）证明：假设QR为假，则Q为真且R为假，则左侧为假。所以：（PPQ）（PPR）Þ QR。第（2）、（4）、（6）小题方法相同，解答略。16. （1）代入可得：（PQ）（PQ）R）（PQ）（PQ）（2）代入可得：（QP）（PQ）17. （1）主析取范式：原式Û（PQ）（PQ）Û m2m3Û（2,3）主合取范式：原式Û（PQ）P）（PQ）Q）ÛP（PQ）（PQ）TÛ P（QQ）ÛM0M1Û（0,1）（3）主析取范式：原式Û（PQ）P）（PQ）R）（PQ）P）（PQ）R）Û（P（PQ）（PR）（QR）（PQ）（PQ）（PR）（QR）Û（PQ）（PQ）（PR）（QR）（PQ）（PQ）（PR）（QR）Û（P（QR）（Q（PR）（P（QR）（Q（PR）ÛF（Q（PR）P（QR）（P（QR）Q（PR）FÛ（PQRQ）（PQRR）（PQR）（PRR）Û（PQR）（PQR）Ûm0m7Û（0,7）主合取范式：原式Û（P（QR）（P（QR）Û（PQ）（PR）（PQ）（PR）Û（PQ）（RR）（PR）（QQ）（PQ）（RR）（PR）（QQ）Û（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）ÛM1M2M3M4M5M6Û（1,2,3,4,5,6）第（2）、（4）小题方法相同，解答略。18. （1）证明：左侧Û（PQ）（PR）Û（PQR）（PQR）（PQR）（PQR）Û（4,5,6）右侧ÛP（QR）ÛÛ（4,5,6）左侧Û右侧，得证。（3）证明：左侧Û（PQ）（PQ）Û（PQ）（PQ）Û（2,3）右侧Û（PQ）（PQ）Û（PP）（PQ）（PQ）（QQ）Û（PQ）（PQ）Û（2,3）左侧Û右侧，得证。第（2）、（4）小题方法相同，解答略。19. 对于A,B,C,D,E5个变元的所有真值指派，推出前提AB，B（CD），C（AE），AE和结论AE的值，得到真值表。当真值表中各前提的真值都为1时，若结论也为1，则结论有效，否则结论无效。20. （1）采用真值表证明：PQPQP（PQ）0011011110001111根据真值表可看出，当前提为1时，结论也为1，则结论有效。（3）采用推理方法证明：PQ为真，可得P为真且Q为真，又P（QR）为真且P、Q为真，得R也为真。则结论有效。第（2）、（4）小题方法相同，解答略。21. （1）证明：假设公式全部同时成立，由S为真得到S为假，由PS为真，得P为真，由PQ为真得到Q为真，由QR为真得到R为真，由RS为真得到S为真。这与前面“S为假”矛盾，则公式不能同时成立。（2）证明：假设公式全部同时成立，由S为真得到S为假，由RS为真得到R为假，由RM为真得到M为真，由M为真得到M为假，矛盾。则公式不能同时成立。22. 首先符号化：P:大连获得冠军；Q:北京获得亚军；R:上海获得亚军；S:广州获得亚军。即求公式：P（QR），RP，SQ，PÞS是否成立。1（1）PP规则2（2）RP P规则1,2（3）RT规则4（4）P（QR）P规则1,2,4（5）QT规则6（6）SQP规则1,2,4,6（7）ST规则23. （1）证明：（1） RP规则（2） QRP规则（3） QT规则（1）（2）（4） （PQ）P规则（5） PT规则（3）（4） （3）题目有误（5）证明：（1） PP规则（附件前提）（2） P（PQ）P规则（3） PQT规则（1）（2）（4） QT规则（1）（3）（5） PQCP规则第（2）、（4）小题方法相同，解答略。24. （1）证明：（1） PP规则（假设前提）（2） PT规则（1）（3） PQP规则（4） QT规则（2）（3）（5） RQP规则（6） RT规则（4）（5）（7） RSP规则（8） ST规则（6）（7）（9） SQP规则（10） QT规则（8）（9）（11） QQT规则（4）（10）（12） PF规则（1）（11）（2）证明：（1） RP规则（2） RSP规则（3） ST规则（1）（2）（4） SQP规则（5） QT规则（3）（4）（6） PQP规则（7） PT规则（5）（6）（3）原式修改为：（PQ）（RS），（QP）R，RÞ PQ证明：（1） RP规则（2） RST规则（1）（3） （PQ）（RS）P规则（4） PQT规则（2）（3）（5） （QP）RP规则（6） QPT规则（1）（5）（7） （PQ）（QP） T规则（4）（6）（二） PQT规则（7）第二章 谓词逻辑1. （1）S(x)：x聪明；L(x)：x好学；a：表示小明，命题：S(a)L(a)。（2）S(x)：x是素数；G(x,y)：x大于y，命题：(x)(S(x)(y)(S(y)G(y,x)（3）U(x)：x是大学生；S(x)：x能成为科学家，命题：(x)(U(x)¬S(x)（4） N(x)：x是自然数；A(x)：x是奇数；B(x)：x是偶数，命题：(x)(N(x)(A(x)B(x)（5）P(x)：x是诗人；T(x,y)：x游览y；V(x)：x是名山大川；a：表示李白 命题：(x)(PaVxTa,x)2. （1）约束变元：x，辖域：P(x)Q(x)和R(x,y)；自由变元：y。（2）约束变元：PxQy中的x,y和R(x)Sz中的z；自由变元：R(x)Sz中的x。（3）约束变元：x,y，辖域：P(x,y)Qy,z；自由变元：z。3. 参考教材2.3部分。4. （1）证明：（1）("x)¬B(x)P（2）¬B(x)US（1）（3）("x)(¬A(x)B(x)P（4）¬A(x)B(x)US（3）（5）A(x)T（2）（4）（6）($x)A(x)EG（5）（3）证明：由于：("x)(A(x)B(x) Þ("x)A(x) ("x)B(x)；("x)(C(x)¬B(x) Þ("x)C(x) ("x) ¬B(x)；("x)(C(x)¬A(x) Þ("x)C(x) ("x) ¬A(x)即证：("x)A(x) ("x)B(x)，("x)C(x) ("x) ¬B(x) Þ("x)C(x) ("x) ¬A(x)（1）("x)C(x)P（附加）（2）C(x)US（1）（3）("x)C(x) ("x) ¬B(x)P（4）C(x) ¬B(x)US（3）（5）¬B(x)T（2）（4）（6）("x)A(x) ("x)B(x)P（7）A(x) B(x)US（6）（8）¬A(x)T（5）（7）（9）("x)¬A(x)UG（8）（10）("x)C(x) ("x)¬A(x)CP（1）（9）第（2）、（4）小题方法相同，解答略。5. （1）证明：（1）("x)P(x)P（附加）（2）P(x)US（1）（3）("x)(P(x)Q(x)P（4）P(x)Q(x)US（3）（5）Q(x)T（2）（4）（6）("x)Q(x)UG（5）（7）("x)P(x) ("x)Q(x)CP（1）（6）（2）证明：由于：("x)P(x)($x)Q(x) Û($x)¬P (x) ($x)Q(x)即证：("x)(P(x)Q(x) Þ($x)¬P (x) ($x)Q(x)（1）($x)¬P (x)P（附加）（2）¬P (x)ES（1）（3）("x)(P(x)Q(x)P（4）P(x)Q(x)US（3）（5）Q(x)T（2）（4）（6）($x)Q(x)EG（5）（7）($x)¬P (x)($x)Q(x)CP（1）（6）6. （1）W(x)：x喜欢步行；C(x)：x喜欢乘汽车；B(x)：x喜欢骑自行车；即需证：("x)(W(x)¬C(x), ("x)( C(x)B(x), ($x)¬B(x) Þ($x)¬W(x)证明：（1）($x)¬B(x)P（2）¬B(x)ES（1）（3）("x)( C(x)B(x)P（4）C(x)B(x)US（3）（5）C(x)T（2）（4）（6）("x)(W(x)¬C(x)P（7）W(x)¬C(x)US（6）（8）¬W(x)T（5）（7）（9）($x)¬W(x)EG（8）（3）F(x)：x是资深人士；S(x)：x是院士；P(x)：x是参事；C(x)：x是委员；a：张伟；即需证：("x)(F(x)( S(x)P(x), ("x)(F(x)C(x), F(a)¬S(a) Þ($x)(C(x)P(x)证明： （1）("x)(F(x)C(x)P（2）F(a)C(a)US（1）（3）F(a)¬S(a)P（4）F(a)T（3）（5）C(a)T（2）（4）（6）("x)(F(x)( S(x)P(x)P（7）F(a)( S(a)P(a) US（6）（8）¬S(a)T（3）（9）P(a)T（4）（7）（8）（10）C(a)P(a)T（5）（9）（11）($x)(C(x)P(x)EG（10） 第（2）、（4）小题方法相同，解答略。7. （d）是错误的。8. 错误。第二行的y是泛指，第四行的y是特指。修改如下：（1） P（2） ，(1)（3） P（4） ，（3）（5） T，（2），（4）和（6） ，（5）9. （1）证明：（1）($x)P(x)P（2）P(a)ES（1）（3）($x)Q(x)P（4）Q(b)ES（3）（5）($x)P(x) ("x)( P(x)Q(x) R(x)P（6）("x) ( P(x)Q(x) R(x)T（1）（5）（7）( P(a)Q(a) R(a)US（6）（8）P(a)Q(a)T（2）（9）R(a)T（7）（8）（10）( P(b)Q(b) R(b)US（6）（11）P(b)Q(b)T（4）（12）R(b)T（10）（11）（13）R(a)R(b)T（9）（12）（14）($y)( R(a)R(y)EG（13）（15）($x)($y)( R(x)R(y)EG（14）（2）证明：（1）($x)P(x)("x)Q(x)P（假设）（2）¬ ($x) P(x)("x)Q(x)T（1）（3）("x)¬P(x)("x)Q(x)T（2）（4）("x)(¬P(x)Q(x)T（3）（5）("x)(P(x)Q(x)T（4）10. （1）原式Û("x)(¬P(x)($y)Q(y)Û("x)($y)(¬P(x)Q(y)（3）原式Û("x)($y)A(x,y)($x)("y)(B(x,y)("y)( A(x,y) B(x,y)Û("x)($y)A(x,y)($u)("v)(B(u,v)("z)( ¬ A(z,u) B(u,z)Û("x)($y)($u) ("v) ("z)( A(x,y)( B(u,v)(¬ A(z,u) B(u,z)11. （2）解：前束析取范式：由于是基本和，因此前束合取范式与前束析取范式一样：（4）解：前束析取范式：前束合取范式：第三章 集合论习题答案对应课本页数：P51-541. 写出下列集合的表达式。(1) 所有一元一次方程的解所组成的集合：答案：集合可表示为 (2) 在实数域中的因式集。答案：集合可表示为(3) 直角坐标系中，单位圆内（不包括单位圆）的点集。答案：集合可表示为(4) 极坐标系中单位圆外（不包括单位圆）的点集。答案：集合可表示为(5) 能被5整除的整数集。答案：集合可表示为2.解：设戏剧、音乐、广告分配的时间分别为(1) 可表示为(2) 可表示为(3) 可表示为(4) 可表示为3.给出集合、和的例子，使得，而。解：4.确定下列命题是否为真。(1) 该命题为真命题(2) 该命题为假命题(3) 该命题为真命题(4) 该命题为真命题(5) 该命题为真命题(6) 该命题为真命题(7) 该命题为真命题(8) 该命题为假命题。5. ，是可能的么，给予证明。解：可能。若，则且。6.(1) 解：设 则(2)解：设则(3) 解：设则(4) 解：设 则(5)解：设则7.设，解： (1) ，(2) ，(3) ，8.设某集合有101个元素，试问：(1) 可构成多少个子集：2101(2) 其中有多少个子集的元素为奇数：2100(3) 是否会有102个元素的子集：不会9.解：把17化为二进制，是00010001，；把31化为二进制，是00011111，编码为01000110，为，编码为10000001，为10.求AB，AB。解： 11. 解： 12.解： (1) (2) (3) (4) 13.证明对于所有集合A,B,C有，当且仅当。证明：充分性：由于 所以，即 充分性得证。 必要性：由于 所以 所以 必要性得证。14.证明对所有集合A,B，C，有：（1）证明： （2）证明： （3）证明：因此，15.确定下列各式的运算结果。解: 16.假设A和B是E的子集，证明下列各式中每个关系式彼此等价。(1) 证明： 证明BA。充分性：若，则若，那么必有。因此，若，则必有，即若xB，则有xA，即BA；必要性：若BA，则若xB，则有xA，即若，则必有。那么，若，那么必有，即；由以上两点可知：BA。 证明：AB=B 充分性：若，那么有或。 若，则由可知，必有，所以若，必有，即； 若，那么必有，即，所以AB=B，充分性得证； 必要性：因为AB=B，所以，对于任意的，必有，所以，必要性得证； 由以上两点可知：AB=B 证明：AB=A 充分性：若，那么必有，即；若，那么由可知，必有，所以，即，所以，AB=A； 必要性：因为AB=A，所以对于任意的，必有，所以；由以上两点可知，AB=A。由以上三点可知，BA AB=BAB=A。(2) 证明:AB 充分性：因为，所以对于任意的，若，则必有，即xB，所以AB； 必要性：因为AB，所以对于任意的，若，则必有xB，即，所以；由以上两点可知：AB 证明：BA 充分性：因为，所以对于任意的，若，则必有，即xA，所以BA； 必要性：因为BA，所以对于任意的，若，则必有xA，即，所以；由以上两点可知：BA.由上可知：ABBA.(3) 证明：AB=EAB充分性：因为 AB=E，所以若，则必有，即若xA，则必有，所以AB；必要性：因为AA=E，又AB，必有AB=E；由以上两点可知：AB=EAB 证明：AB=EBA充分性：因为 AB=E，所以若，则必有，即若xB，则必有，所以BA；必要性：因为BB=E，又BA，必有AB=E；由以上两点可知：AB=EBA.由上可知：AB=EABBA.。(4) 证明：A=BAB=充分性：由于A=B，所以AB=,BA= 所以AB=ABBA=必要性：因为AB=ABBA= 所以AB=且BA= 因为AB=，所以AB 又BA=，所以BA 所以A=B。由上可知：A=BAB=。17.化简下述集合公式。(1) 结果：AB(2) 结果：A-B(3) 结果：A(4) 结果：C（AB）18.设A,B,C是任意集合，分别求使得下述等式成立的充分必要条件。(1) BA(2) BA=(3) B=A=(4) B=A(5) B=(6) B=A(7)解：由于，因此必有且。也就是并且。（8）解：由于，因此必有且。也就是并且。(9) 解： 因此，意味着(10) 解： 两种可能，第一种，即B=C；第二种，或者19.借助文氏图，考察下列命题的正确性。EB(1)CAE(2)AC20.设A,B,C为任意集合，是判断下面命题的真假。如果为真，给出证明，否则给出反例。21.设在10名青年中有5名是工人，7名是学时，其中兼具工人与学生双重身份的青年有三人，求既不是学生也不是工人的青年有多少？设A，B分别代表工人、学生，则：所以既不是学生也不是工人的青年有 1 人。22.求1到250之间能够被2,3,5,7中任何一个整除的整数的个数。设A= 2502=125，B= 2503=83，C= 2505=50，D= 2507=35则所求的答案表达式为ABCD。求解：ABCD=125 + 83 +50 +31 (41+25+17+16+11+7)+(8+5+3+2)-(1) =189;所以,这样的数共有189个。23. 解： 设A，B，C分别表示参加足球队、篮球队和棒球队的队员的集合即同时参加两个对的队员共有18个。24. 解：设A，B，C分别表示读甲种、乙种、丙种杂志的学生的集合。(1) 所以确定读两种杂志的学生的百分比为60%。(2) 所以不读任何杂志的学生的百分比为30%。第四章 二元关系习题答案对应于课本88-93页1.如果A=0,2和B=1,2，试求下列集合。（1）解：（2）解（3）解：2.解：表示在在笛卡尔坐标系中，且的矩形区域内的点集。3.（1）证明：任取,有 由取值的任意性知，。（2）当且仅当才，才有证明： 当时，于是。当时，任取，可知，由知，于是得到。所以，。4.证明： 必要性：若，； 同理，若，； 若，则显然有； 必要性得证。 充分性性：由于 所以对于任意的,必有 即若则必有；若，则必有，所以当时，； 充分性得证。5.（1）解：任取,有选择A=1，B=2，C=a，D=b则因此该等式不成立。（2）解：任取,有选择A=1，2，B=1，C=a，b，D=a因此，该等式不成立。（3）解：设A=1，2，B=2，C=3，4，D=4则因此，该等式不成立。（4）解：取,有因此，该等式成立。（5）解：任取取,有因此，该等式成立。（6）存在集合A使得AA×A；取A= ，则该命题成立。（7）PA×PA=PA×A假设结合A有n个元素，则PA有2n个元素，则PA×PA共有22n个元素；则A×A有n2个元素，PA×A则有2n2个元素，显然两者元素数不一样，故命题不成立。6.设A=1,2,3,4，列出以下关系R。（1）R= x,yx,yA x+y 2 解：R=1,2，1,3，1,4，2,1，2,2，2,3，2,4，3,1，3,2，3,3，3,4，4,1，4,2，4,3，4,4（2）R= x,yx,yA x-y=1解：R=1,1，1,3，1,4，2,2，2,4，3,1，3,3，4,1，4,2，4,4（3）R= x,yx,yA xyA 解：R=1,1，2,1，2,2，3,1，3,3，4,1，4,2，4,4（4）R= x,yx,yA y 为素数解：R=1,2，1,3，2,2，2,3，3,2，3,3，4,2，4,37.列出集合A=2,3,4上的恒等关系IA和全域关系EA。解：IA= 2,2，3,3，4,4；。EA= 2,2，2,3，2,4，3,2，3,3，3,4，4,2，4,3，4,48.给出下列关系R的所有序偶。（1）解：（2）解：9.设和都是从到的二元关系，并且求、。解：fldR1-R2=fld1,2,3,3=1,22,3=1,2,3R1R2=1,4,2,2R2R1=1,3,4,4R12=1,4,3,3R23=4,4,2,210.设集合A=1,2,3，问A上有多少种不同的二元关系。解：232=512种关系。11.设关系R= 0，1，0，2，0，3，1，2，1，3，2，3，求RR，R-1，R1,2，R1,2 解：RR= 0,2，0,3，1,3R-1= 1，0，2，0，3，0，2，1，3，1，3，2R1,2= 1，2，1，3，2，3R1,2= 2,312.设关系R=，求R-1，R2，R3，R，R,R|,R， R。解：R-1=，R2= ，R3= R = ，R|= R|=， R= 13.说明以下关系R具有那些性质并说明理由。（1）：反自反的、反对称的、可传递的；（2）：反自反的、对称的、不可传递的；（3）：自反、对称、可传递；（4）：自反、对称、可传递；14.设A是所有人的集合，定义A上的二元关系R1和R2，说明R1和R2具有哪些性质。解：R1具有的性质：反自反的、反对称的、可传递的；R2具有的性质：自反、对称、可传递；15. 设和是集合X中的二元关系。试证或反证下列命题：（1）如果和是自反的，则也是自反的。（2）如果和是反自反的，则也是反自反的。（3）如果和是对称的，则也是对称的。（4）如果和是反对称的，则也是反对称的。（5）如果和是可传递的，则也是可传递的。解：（1）证明：任取，由于和是自反的，因此，可得，由x取值的任意性可知，是自反的。（2）设，则，不是反自反的。（3）设，则，不是对称的。（4）设，则，不是反对称的。（5）设 ，则，不可传递。 16.证明：若R是集合A上的自反和可传递关系，则RR=R。证明：任意取x,yA ,x,yR,由于R是集合A上的自反，则可知y,y，x,xR， 则R = x,y,x,y,y,y,x,x RR= x,y,x,y,y,y,x,x=R ;17. 如果关系R和S都是自反的。证明：，也是自反的。证明：设R是集合A上的二元关系，S是集合B上的二元关系。因为R和S都是自反的，所以对于都有，对于都有。（1）设，那么或。若，有，那么必有。若，有，那么必有。因此，当时，必有，所以也是自反的。（2）设，那么因此且，即。所以也是自反的。18.证明：如果关系R和S都是自反的、对称的、可传递的，证明：也是自反的、对称的和可传递的。证明：设R是集合A上的二元关系，S是集合B上的二元关系。自反性的证明如题4。 对于任意的，若，那么且因为R和S都是对称的，所以且，所以。即对于任意的，若，则必有，所以是对称的。 对于任意，若且，那么有。因为R和S都是可传递的，所以有且，即。即对于任意，若且，都有。所以是可传递的。19.设集合A是有限集，且A=n，求：（1）A上有多少不同的对称关系。解：也就是说集合A有n平方个有序对，由对称定义可知，对于。另外知道在n平方个有序对中有n 个有序对，相应的就有个有序对（X,Y)且X，定义可知后面的个有序对只能成对出现，所以有对。前面的那n对可以出现任意多对。图片如下。（1,1) (2,2).(n,n) (1,2) (1,3).(n-1,n) n个有序对 (2,1) (3,1).(n,n-1) ()/2个有序对对 共有n+ ()/2 个元素 即 ()/2个所以得到对称关系数为：（2）A上有多少不同的反对称关系。由定义：如果 如下图。（1,1) (2,2).(n,n) (1,2) (1,3).(n-1,n) n个有序对 (2,1) (3,1).(n,n-1)这n个有序对可以出现任意多次 ( )/2个有序对对 (由6可知）所以得结果 ：即（3）A上有多少不同的既非自反又非反自反的关系。解：20.试着画出R的关系图并写出对应的关系矩阵。解：关系图如下：21. 设，和是A中的关系，试求出关系矩阵：；。解： 由此可得： 所以： 22. 给定集合。图4-6给出了A中的关系R的12个关系图。对于每个关系图，写出相应的关系矩阵，并证明被表达的关系是否是自反的或反自反的；是否是对称的或反对称的；是否是可传递的。（1）自反的、不对称的、不可传递的；其对应的关系矩阵为：（2）不自反的、反对称的、不可传递的； 其对应的关系矩阵为：（3）自反的、对称的、可传递的； 其对应的关系矩阵为：（4）自反的、不对称的、不可传递的； 其对应的关系矩阵为:（5）不自反的、不对称的、不可传递的； 其对应的关系矩阵为：（6）不自反的、对称的、不可传递的； 其对应的关系矩阵为：（7）自反的、反对称的、可传递的； 其对应的关系矩阵为：（8）自反的、不对称的、不可传递的； 其对应的关系矩阵为：（9）不自反的、对称的、可传递的；此题图有错误 其对应的关系矩阵为：（10）自反的、反对称的、不可传递的； 其对应的关系矩阵为：（11）自反的、反对称的、可传递的； 其对应的关系矩阵为：（12）不自反的、反对称的、可传递的。 其对应的关系矩阵为：23. 设X是一个集合，和是X中的二元关系，并设，试证明：（1）（2）（3）证明：a）因为，故R1IAR2IA，即 b）因为s（R1）对称，且s（R1）R1，但R1R2，故s（R1）R2，由s（R2）的定义，s（R2）是包含R2的最小对称关系，故 s（R1）s（R2） c）因为t（R1）传递，且t（R1）R1，但R1R2，故t（R1）R2因t（R2）是包含R2的最小传递关系，所以 t（R1）t（R2）24.在图4.23中给出三个关系图。试求每一个的自反的、对称的和可传递的闭包，并画出闭包的关系图。（1）解：由关系图可知， 则： （2）解：由关系图可知， 则： （3）解：由关系图可知， 则： 25和是集合A中的关系。试证明：（1）（2）（3）证明：(1)r（R1R2）= R1R2IA= R1IAR2IA =r（R1）r（R2） 2）s（R1R2）=（R1R2）（R1R2）C = R1R2R1CR2C=（R1R1C）（R2R2C） =s（R1）s（R2） 3）因为R1R2R1，由习题3-98，则t（R1R2）=t（R1） 同理 t（R1R2）=t（R2） 所以 t（R1R2）= t（R1）t（R2）26. 设集合，是中的二元关系，图4-12给出了的关系图。试画出可传递闭包的关系图，并求出。解：由关系图可知，则：27. 设是集合中的任意关系。试证明：（1）（2）（3）证明：a）（R+）+= t（t（R），因为t（R）是传递的，根据定理3-8.1，t（t（R）= t（R），即（R+）+= R+。 b）RR*= R（tr（R）= R（rt（R）= R（t（R）IA） = Rt（R）RIA= RR i=1 =RiR=Ri= t（R）= R+ i=2 i=1同理可证 R+= R*R c）因为r（R）是自反的，有习题3-97a），tr（R）是自反的，根据定理3-8.1， rtr（R）= tr（R），即tr（R*）= R*。所以，（R*）*= R*。29设是集合A的划分。试证明：是集合的划分。证明：因为是集合的划分， 所以 （1）因为 所以 （2）（3）（1），（2），（3）构成满足划分的条件，因此是集合的划分。30. 把个元素的集合划分成两个类，共有多少种不同的分法？解：31. 在图4.25中给出了集合中的两个关系图，判断这两个关系是否是等价关系。解：左侧的关系不是等价关系，因为不满足可传递性；右侧的关系是等价关系。32. 在等价关系图中，应如何识别等价类？解：如果两个元素之间有两条连线，那么说明这两个元素是等价类。33. 设R是集合X中的关系。对于所有的，如果，就有，则称关系R是循环关系。试证明：当且仅当R是一个等价关系，R才是自反的和循环的。证明：（1）当R是个等价关系时，由等价关系的定义知，等价关系满足自反性，即R是自反的。任取，由R的可传递性，知，再由R的对称性，知。根据x，y，z取值的任意性，知R是循环的。（2）当R是自反的，可知对任意，。任取，使得，因为R是循环的，故当，时，。由x，y取值的任意性知，R是对称的；任取，由R的循环性知，因为R是对称的，因此，由x，y，z取值的任意性，知R是可传递的。因为R是自反的、对称的和可传递的，因此R是一个等价关系。34. 设和是集合X中的等价关系。试证明：当且仅当中的每一个等价类都包含于的某一个等价类之中，才有。证明：设等价关系造成的集合X的划分为，等价关系造成的集合X的划分为（1） 当中的每一个等价类都包含于的某一个等价类之中时，任取中的一个等价类，则必包含在的一个等价类里，设包含在中，。任取中两元素x，y，由等价类的性质知，。由，可知若，则，即。由i,j,x,y取值的任意性知，。（2） 如果，那么对任意的 永真，等价于x,y落入的某个等价类中，等价于x,y落入的某个等价类中，即若，则，由x,y的任意性可知，,由i的任意性可知，中的每一个等价类都包含在的某一个等价类之中。综上所述，当且仅当中的每一个等价类都包含于的某一个等价类之中，才有。37. 设和是集合X中的等价关系，并分别有秩和。试证明：也是集合X中的等价关系，它的秩至多为。还要证明不一定是集合X的一个等价关系。证明：(1) 因为是自反的，所以对于任意的，都有对于任意的，故，所以是自反的； 对于任意的，若，则且。又是对称的，所以有，故，即是对称的； 对于任意的，若，则，且，。又是可传递的，所以有，故，即是可传递的；综上，是等价关系。(2) 因为是自反的，所以对于任意的，都有对于任意的，故，所以是自反的； 对于任意的，若，则可能有三种情况：若且，那么因为是对称的，所以有，故，即是对称的； 若但，那么有且，此时，即是对称的；所以是对称的；若但，那么有且，此时，即是对称的； 对于任意的，若，当 ，时，不能确定，故不是可传递的。由上可知，不是等价关系。（1）（2），（3），合并后，有 ，（4），（5），合并，得 ，综上，最大相容类有四个，分别是，。38. 给定集合的覆盖，如何才能确定此覆盖的相容关系。解：相容关系是具有反对称性的关系，集合的任何一个覆盖均能确定一个相容关系，反之亦然。设是集合的一个覆盖，则由此覆盖确定的上的相容关系是：，其中指的子集的笛卡尔积。如是的一个覆盖，则此覆盖确定的上的相容关系是：39. 设集合，R是X中的关系。图4-23给出了R的关系图。试画出的关系图。解：40. 假定是集合X中的恒等关系，R是X中的任何关系。试证明：是相容关系。证明：设（1）由于，因此，。知是自反的；（2）任取，则或者或者。若，则，；若，则，；若，则，。可知无论任何情况，若，则。故是对称的。综上所述，既是自反的又是对称的，因此，是相容关系。41. 给定等价关系R和S，它们的关系矩阵是 试证明：不是等价关系。证明：可知不是对称的，因此，不是等价关系。42. 设集合。求出X中的等价关系和，使得也是个等价关系。解：设则和是集合X中的等价关系。此时，也是个等价关系。43. 对于下列集合中的整除关系画出哈斯图。（1）（2）解：（1）（2）44. 如果R是集合X中的偏序关系，且。试证明：是A中的偏序关系。证明：因为R是集合X中的偏序关系，所以R是自反的，反对称的，可传递的。（1）因为R是自反的，所以； 又，所以； 所以R是自反的。（2）对于任意，若,那么且；又R是反对称的，所以，即，所以是反对称的。（3）对于任意，若，那么且。又R是可传递的，所以，即：，所以是可传递的。由此可知，满足自反性、反对称性、可传递性，即是A中的偏序关系。45. 试给出集合X的实例，它能使是全序集合。解：，则此时，对于任意的，都有所以是全序集合。46. 给出一个关系，它是集合中的偏序关系又是等价关系。解：集合上的恒等关系，既是偏序关系又是等价关系。47. 证明下列命题：（1）如果是拟序关系，则也是拟序关系。（2）如果是偏序关系，则也是偏序关系。（3）如果是全序关系，则也是全序关系。（4）存在一个集合和中的关系R，使得是良序的，但不是良序的。证明：设是上的二元关系，（a）若是自反的，则，由于的转置仍是，因此，故
展开阅读全文