离散数学作业6_集合与关系答案_第1页
离散数学作业6_集合与关系答案_第2页
离散数学作业6_集合与关系答案_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、离散数学作业作业6 等价关系1. 设R和S均为A上的等价关系，确定下列各式，哪些是A上的等价关系？如果是，证明之；否则，举反例说明。（1）RS （2）RS （3）r (R-S) （4）R- S （5）RS （6）R2解：(1),(6)正确，其余错误。2. R是集合A上的二元关系，" a,b,c ,若aRb,且bRc,有cRb,则称R是循环关系。证明R是自反和循环的，当且仅当R是一等价关系。分析: 需要证明两部分:(1) 已知R是自反和循环的，证明:R是一等价关系(2) 已知R是一等价关系, 证明R是自反和循环的.证明：（1）先证必要性。只需要证明R是对陈的和传递的。 任取(x,y)R

2、。因为R是自反的，所以(y,y)R。由R是循环的可得(y,x)R，即R是对陈的。 任取(x,y)，(y,z)R。因R是循环的，所以(z,x)R。由R对称性得(x,z)R，即R是传递的。 （2）证充分性。只需要证明R是循环的。任取(x,y)，(y,z)R，下证(z,x)R。由于R是传递的，所以(x,z)R。又由R是对称的得(z,x)R。所以R是循环的。3. 设|A|=n，在A上可以确定多少个不同的等价关系？ 解：2n!/(n+1)n!n!)4. 给定集合S= 1 , 2 , 3, 4, 5 ，找出S上的等价关系R，此关系R能够产生划分1，2，3，4，5，并画出关系图。 解：5. 设A=1，2，3

3、，4，5。R是集合A上的二元关系，其关系矩阵如下图所示。求包含R的最小等价关系和该等价关系所确定的划分。 分析: 可以证明tsr(R)是包含R的最小等价关系. 解：包含R的最小等价关系的矩阵表示如下： 上述等价关系确定的划分为1,2,4,3,5.6. 自学华氏(WalShall)算法，写出算法的基本概念、基本步骤和一个求解传递闭包的具体实例，并可清晰讲解算法整体实现过程。7. （选做题）设R与S是A上的等价关系，证明：（1）RS是A上的等价关系，iff RS=SR；（2）RS是A上的等价关系，if RSS 且 SRR.分析: iff是if and only if的缩写, 是当且仅当的意思. 证

4、明：（1）先证必要性。任取(x,z)RS，则存在y使得xRy,ySz。因为R与S是A上的等价关系，所以R与S是对陈的，即yRx,zSy,所以(z,x) SR。因此，RSSR。 任取(x,z)SR，则存在y使得xSy,yRz。由R与S是对陈的得ySx,zRy，即(z,x) RS。又因为RS是对陈的，所以(x,z) RS，即SR RS。 综上RS=SR，必要性得证，下面证充分性。 因为IAR，IAS，所以IARS，即RS是自反的。 任取(x,z)RS，则存在y使得xRy,ySz。由R与S是对陈的得yRx,zSy，即(z,x)SR。因为RS=SR，所以(z,x)RS，即RS是对陈的。 因为 所以RS是传递的。 综上，RS是等价关系，充分性得证

人人文库> 全部分类> 教育资料 > 课设设计

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论