离散数学习题及试卷关系与映射

第四章  关系与映射 1、 解 R的关系图如图2-1所示。     图2-1 22. 在由个元素组成的集合上，可以有多少种不同的二元关系？若集合的元数分别为，试问从到有多少种不同的二元关系？ 解 因为一个由个元素组成的集合上,任何一个二元关系都是的子集,而中共有个元素,取0个到个元素可以组成子集,所以有个不同的关系。 而当时，这个全关系中共有个元素，取0个到个元素组成的子集共有个，因此从到共有种不同的二元关系。 3. 设集合，上的二元关系分别为： 试用定义求，，，，，，并画出其关系图。 解 ={} ={} ={} ={} ={} 其关系图如图2-2所示。   图2-2 说明 1. 当用定义求复合关系时，先将左关系中每个序偶的第二元素作为中介元素，到右关系中每个序偶里找与其相同的第一元素，将这个元素去掉，用剩余两个元素组成新序偶成为复合关系中的元素。 2. 用定义求出的复合关系与逆关系，可以用关系矩阵来验证其正确性。 4.     设集合，集合，是集合上的关系，是上的关系。   试验证 证 = = = = = = 故 。 5. 图2-3所示的图形是集合上关系的关系图，试根据这些关系图分别写出对应的关系矩阵，并说明每种关系所具有的性质（自反性，对称性，反对称性，传递性）。       图2-3 解 = 具有自反性，对称性，反对称性与传递性。 = 具有对称性与传递性。 = 具有反对称性。 = 具有对称性，反对称性与传递性。 说明 本 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 判断关系所具有的性质，主要通过已知关系图与求出的关系矩阵进行，同时对于比较难于判定的传递性，都可以一结合定义进行判定。如果不破坏定义所要求的条件，可以认为满足定义要求，如对的判定。 5. 5.        下列关系是否具有如下性质：自反性，对称性，反对称性，传递性？ ⑴ ； ⑵ ； ⑶上的恒等关系=； ⑷上的空关系。 解 ⑴ 具有反对称性与传递性； ⑵ 具有反对称性； ⑶ 具有自反性，对称性，反对称性与传递性； ⑷上的空关系具有对称性，反对称性与传递性。 说明 本题中的前两个小题均为无限集合，第⑶小题也未给定集合的元数，这样不能得到完整的关系图与关系矩阵。但是，可以在草纸上作出部分元素的关系图与关系矩阵进行判断，同时要充分利用定义要求，便具有该种性质。第⑷小题，与上题中⑷题类型一致，只是元数大一些，结果应与上题⑷相同。 7. 设和是集合上的任意关系，试 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 或用反例推翻下列论断： ⑴若和都是自反的，则也是自反的； ⑵若和都是对称的，则也是对称的； ⑶若和都是反对称的，则也是反对称的； ⑷若和都是传递的，则也是传递的。 证 ⑴论断正确。对任意，若和都是上的自反关系，则 所以，即也是自反的。 ⑵论断不正确。 例如，设，当 ，与都是对称的，但是已不是对称的，故原论断不正确。 ⑶论断不正确。 例如，设集合，当 与都是反对称的，但是，已不是反对称的，（因为），故故原论断不正确。 ⑷论断不正确。 例如，设集合，当，不是传递的，因为，而，故原论断不正确。证毕。 8. 设的关系图如图2-4所示，试画出，的关系图。     图2-4 解 ，的关系图如图2-5所示                 图2-5 说明 ⑴对于的关系图，因为，只要在的关系图上对没有自回路的结点都添加上自回路，使可以画成的自反闭包的关系图。 ⑵ 对于的关系图，因为，只要将的关系图中所有单向弧都画成双向弧，便可以画成的对称闭包的关系图。 ⑶ 对于的关系图，当是有限集合上的关系时，画图时，如果关系图中从结点到结点有一连串带箭头的头尾相接的弧相连着，则在的关系图上添加一条直接从到的弧，便可以画出的关系图，如图中关系图上的与，与，与，与之间都应画一条有向弧。但是这里要特别注意两个结点，原有两条到与到的有向弧，这属于 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 规律中的特殊情形，作为结点看成是两个结点的重合，所以结点处要画一条自回路， 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示从结点到结点。同理，结点也要画一条自回路。 9.     设集合，上的关系求和，并写出它们的关系矩阵 解 因为 所以 此题，故其关系矩阵为 = 说明 此题，这纯属偶然情况，一般地，。 10. 设是集合上的二元关系，若是传递的，则也是传递的，而不一定是传递的。 证 由§2.4定理1知，是传递的，当且仅当，故要证是传递的，只需证明。 因为 下面用归纳法证明 当时，左端==右端 假设当时，命题成立，即 当时， 由§2.2，习题7的结论，可得 = 故===== 即 ，故是传递的。 不一定是传递的。 例如 设集合上的二元关系，当，是传递的，而=时，已经不是传递的。 证毕。 11.    设是集合上的二元关系，判断下列命题是否正确？ ⑴； ⑵。 解 ⑴命题正确。 由于，，并利用，以及对于一切自然数，，用数学归纳法的可以证明，所以 。 ⑵ 命题不正确。可以证明。 首先证明，当时，则。 这是因为，是对称的且，但是，故。由的定义，是包含的最小对称关系，故。 同理可证，。 由对称闭包定义，有，利用上面证过的结论： 再由教材例5（2）可知，是对称的，也是对称的，又根据§2.4定理1中（2），是对称的，当且仅当，因此，即。 不一定成立。 例如，集合上关系， ，则，   而 。 故 12. 设和是集合上的二元关系，试判断下列命题是否正确？ ⑴； ⑵； ⑶。 解 ⑴命题正确。 因为。 ⑵命题正确。 首先证明 任取，当且仅当，当且仅当或，当且仅当，或，当且仅当，故证得= 而   ⑶命题不正确，可以证明。 因为，利用前一例题中⑵证明中证过的结论：当时，则，有 同理，，有 故 不一定成立。 例如，设集合，上的二元关系分别为 则 而= = = 显然， 13. 设集合，上的关系关于等价关系的等价类为： ，试求： ⑴ 等价关系；⑵写出关系矩阵； ⑶画出关系图。 解 ⑴ 因为等价关系具有自反性，所以， 。 又因为在同一个等价类中，所以 再因为在同一个等价类中，所以 因此 。   ⑵ 的关系矩阵 ⑶的关系图如图2-6所示     图2-6 14.      设和是非空集合上的等价关系，下列各式哪些是上的等价关系？哪些不是上的等价关系 ？举例说明： ⑴； ⑵； ⑶； ⑷； ⑸ 解 ⑴ 不是上的等价关系。 例如，设集合，上的关系 不具有自反性与传递性，故 不是上的等价关系。 ⑵不是上的等价关系。 例如，设集合， 不具有自反性和传递性，因此不是上的等价关系。 ⑶是集合上的等价关系。 因为是集合上的等价关系，任取，有，而且有，所以在集合上是自反的。 任取，若，则存在，使得且，因为是对称的，有且，于是，所以是对称的。 任取，若且，则存在，分别使得 ，且 ，且 由于是传递的，元素与之间以为中介元素，与之间以为中介元素，有，，再根据关系的复合，有所以是可传递的，故是集合上的等价关系 ⑷ 不是集合上的等价关系。 由⑵题所举例子， 有 不具有传递性，所以不是集合上的等价关系。 ⑸是集合上的等价关系。 对于任意，有且，故，因此是自反的 任取，若是对称的，必有，而是自反的，对于，有，由与，得，由与，得，因此是对称的。 任取，若，，是传递的，必有。由于是自反的，由 与，得 与，得 与，得 故是集合上的等价关系。 15.    设集合，上的四个半序关系分别为： 试分别画出它们的哈斯图，并判断起其中哪个具有序关系？哪个具有良序关系？ 解 集合上的半序关系的哈斯图如图2-7所示。     图2-7 其中关系图与所有元素都排在链上，即任意两个元素之间都有关系存在，所以和都是序关系。由于和中每一非空子集都有最小元，所以也都是良序关系。 说明 此题中的阿拉伯数字已经失去了它们在实数集中的大小关系，应该把它们看成四个不同符号。 16.    设集合，为上的整除关系。 ⑴画出半序集的哈斯图； ⑵写出集合中的最大元，最小元，极大元，极小元； ⑶写出的子集的上界，下界，最小上界，最大下界。 解 ⑴半序集的哈斯图如图2-8所示。     图2-8 ⑵集合中的最大元是24，无最小元，极大元也是24，极小元是2和3。 ⑶集合的上界是12与24，无下界，最小上界是12，无最大下界 说明 最大元与极大元的区别在于，最大元是一个集合中的最“大”者，若有则是唯一的；而极大元则是集合中的元素没有比它“大”的，可能不唯一。对于最小元与极小元具有同样情况。这里把“大”字用引号引起来，因为实际上不一定在研究数与数之间的大小关系，而是在研究某种半序关系。 17.    设是集合上的半序关系，且，试证明是上的半序关系。 证 对于任意，因为，故，而是上的半序关系，则在上具有自反性，于是，且，这样可得 在上是自反的。 任取，且，若，可得且，因为具有反对称性，必有，故即在上具有反对称性。 对于任意，因为，故，若且而，故，可得且，即当同时且。 同理，当，也有同时且。 因为在上具有传递性，由且，得。又，故，因此满足传递性，所以是上的半序关系。 18       设集合， 映射定义为，试求。 解 因为，，当时 而，设映射 故 即 为在上的限制，而为在上的扩充。 19. 设和是两个有限集合，它们的元数都是，则是单射的充分必要条件是为满射 证 必要性，当是单射时，的元数是，而的元数也是，故，因此是满射。 充分性，若为满射时，有，则的元数为，的元数也是，个原象对应个象，即不同元素对应不同的象，因此是到的单射。 设为实数集，试证明和都是满射，而不是单射。 证 对于任意，可以使成立的有无数对，且，也就是说值域中每个元素都有无数原象在中，所以是满射，而不是单射。 对于任意，能使成立的也不止一对实数存在。例如，而，或，即象集中每一元素都有原象，而且原象不唯一，所以是满射，而不是单射。 证毕。   说明 欲证明一个映射为满射时，通常采用取值域中任意元素，按映射对应都有原象存在时，则可确定该映射为满射，或者直接证得。 欲证一个映射为单射时，按定义一般有两种方法，一是任取属于定义域，，能证得。另一种方法是：取属于值域，证得。 21. 设集合，与为的映射， 若，试求与；若与为上的两个二元关系时，与又将怎样呢？ 解 根据复合映射的定义，有 若与为上的两个二元关系时， 则 说明 上述两种结果，当左端相同时，而右端不同，恰是一种交叉，其原因就是的复合映射与上的的规定不同，请读者再一次仔细对比两种定义的符号表示。 22. 设为实数集，都是的映射。 （1）     求，，并分别判定是否为的满射，单射，双射？ （2）        问是否存在？如果存在，试求出来。 解 （1）因为 所以 按照开口向上的抛物线确定，不是满射，也不是单射，更不是双射。 同样以开口向上的抛物线确定，不是满射，不是单射，也不是双射。 （3） 因为映射 是双射，故存在， 。 23．设映射 ， ， 都是双射，求证 。 证 由于 都是双射，因此 均可逆，分别存在逆映射， 故复合映射 。 因为 都是双射，所以也是双射，且 ，则必有逆映射 既然 与 都是 从 到的映射，对于任意 ，设 ，则有 而 可得出 因此 = 由于 是任意的，故有 = 证毕。 4 1 2 3 4 1 2 3 R-S� 2 1 3 S - R 2 4 3 1 � 1 2 3 4 � 3 4 2 � 1 2 3 4 1 � 1 2 3 1 2 3 � � 2 1 3 1 3 a b c d c a b c d c a b c d c a b c d c b c a d e 1 2 3 4 3 4 2 1 1 3 4 3 4 3 2 1 � � � 8 4 2 24 12 6 3 _1210327400.unknown _1210327852.unknown _1210327961.unknown _1210328151.unknown _1210328369.unknown _1210328417.unknown _1210402936.unknown _1210328378.unknown _1210328277.unknown _1210328351.unknown _1210327883.unknown _1210327898.unknown _1210327945.unknown _1210327869.unknown _1210327653.unknown _1210327698.unknown _1210327625.unknown _1210326829.unknown _1210327011.unknown _1210327270.unknown _1210326941.unknown _1210326690.unknown _1210326793.unknown _1210326500.unknown