离散数学中关系性质的判定方法的论文

《离散数学中关系性质的判定方法的论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、离散数学中关系性质的判定方法的论文离散数学中关系性质的判定方法　　关系的概念是离散数学中关系的基础，又是集合概念的应用，因此应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。而关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。对于四种性质（自反性、对称性、反对称性、传递性），有如下方法加以判定：　　一、依据其定义　　1.自反性：　　设r是集合a上的二元关系，如果对于每一个a∈a，若有（a，a）∈r，即ara，则称r在集合a上具有自反性。　　2.对称性：　　设r是集合a上的二元关系，对于任意的a、b∈a，若有（a，b）&

2、isin;r，就有（b，a）∈r，则称r在集合a上具有对称性。　　3.反对称性：本文由论文联盟收集整理　　设r是集合a上的二元关系，对于任意的a、b∈a，若（a，b）∈r且（b，a）∈r时，必有a=b，则称r在集合a上具有反对称性。　　4.传递性：　　设r是集合a上的二元关系，对于任意的a、b、c∈r，若（a，b）∈r，且（b，c）∈r，就有（a，c）∈r，则称关系r在a上具有传递性。　　二、依据关系矩阵和关系图的关系　　1.关系r具有自反性，当且仅当在关系矩阵中，主对角线上元素全为1；或者在关系图中每个结点上都

3、有一条自回路。.cOm　　2.若关系r具有对称性，当且仅当关系矩阵是对称矩阵；或者在关系图中，若两个结点间存在有向弧，必是成对的。　　3.若关系r具有反对称性，当且仅当关系矩阵中以主对角线为对称轴的对称元素不能同时为1（可以同时为0），而主对角线上的元素是1或者是0；在关系图上，若两个结点间存在有向弧，不可能成对出现，结点可以有自回路。　　4.若关系r具有传递性，关系矩阵没有明显特征。关系图的特点是：任意两个结点a、b间若能通过一条以上的弧间接连结起来，则必有一条直接从a到b的弧。作为它的一种特殊情况，若两点间各有一条直接从a到b和由b到a的弧连接时，则在这两个结点a、b上必然各有一条自回路

4、。　　对于传递性的判定，难度稍大一些，要注意两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性和反对称性，但是不具有自反性。二是介绍一种判定传递性的跟踪法，即若（a1，a2）∈r，（a2，a3）∈r，l（ai-1，ai）∈r，则（a1，ai）∈r；如若（a，b）∈r，（b，a）∈r，则有（a，a）∈r，且（b，b）∈r。　　例1、设集合a={a，b，c，d}，判定下列关系哪些是自反的、对称的、反对称的和传递的：r1={（a，a），（b，a）}，r2={（a，a），（b，c），（

5、d，a）}，r3={（c，d）}，r4={（a，a），（b，b），（c，c）}，r5={（a，c），（b，d）}。　　解：依据关系性质的定义，可判定：均不是自反的；r4是对称的；r1、r2、r3、r5是反对称的；r1、r2、r3、r4、r5是传递的。　　例2、设集合a={1，2，3}上的关系r1={（1，1），（2，2），（3，3）}，r2={（1，1），（2，2），（2，3），（3，2），（3，3）}，r3={（1，2），（2，3），（3，1）}，r4=ψ，说明每种关系所具有的性质。　　解：先做出关系矩阵，再依据其规律加以判断。　　100100　　mr1=010mr2=011　　0

6、01011　　010000　　mr3=001mr4=000　　100000　　由判定方法二知，r1具有自反性、对称性、反对称性与传递性；r2具有对称性与传递性；r3具有反对称性；r4具有对称性、反对称性与传递性。