离散数学中二元关系的教学研究

[摘要] 离散数学中的二元关系是非常重要的内容。它包括关系的基本概念,而关系的基本概念中包含自反关系、反自反关系、对称关系、反对称关系、传递关系、本文对这5种关系深入讨论,分别给出定义,通过三种判断方法和两种图的教学方法直接明确,取得了良好的效果。

[关键词] 关系性质 关系图 传递性

一、引言

二元关系是离散数学教学中的一个重要内容,它也是数据结构、数据库、算法分析、计算机理论等课程的数学基础或数学工具。二元关系在散数学中的本概念是集合A、B的笛卡积A×B的子集,是序对的集合,即R={|X∈A∧y∈B},并称为集合A到集合B的二元关系,当A=B时称为集合A(或B)上的二元关系。定义在某一集合上的二元关系具有自反性、反自反性、对称性、反对称性以及传递性等性质。实际判定某个二元关系性质时,自反性、反自反性、对称性的判定比较容易,而反对称性、传递性的判定有时则较困难。通过对二元关系传递性定义的深入分析,通过关系图,可以较好地实现二元关系传递性的判定。

二、离散数学中的五种性质定义

1.自反关系

设R是集合X中的二元关系。对于每一个x∈X来说,如果有∈R,则称R

R1,R2为A上的自反关系,则经过并、交、、合成运算以后仍能保持自反性。

若用关系矩阵图表示自反关系,则矩阵的主对线元素全为1。若用关系图表示则图中每一结点上都必须有条闭路,也可以说,若关系是自反的,则每点上都有环。R是自反的充要条件是其关系图中的每个结点有自环。

2.反自反性

R1,R2为 A上的反自反关系,则经过并、交、相对补、逆运算后仍能保持反自反性。例:S={a、b、c}。R={ ( a,b ),(b,a) }则R是反自反的。R={( a,b ),( b,a ),( a,a)},则R不是反自反的。

用关系矩阵表示反自反关系,则关系矩阵的主对角线元素全为零。若用关系图表示反自反关系的话,则图中的每一结点上都没有闭路,即头上无环。R是反自反的充要条件是关系图中没有一个自环。

3.对称性

R1,R2为A上的对称关系,则经过并交、相对补、逆运算后仍能保持其对称性。对称关系的关系矩阵的特点:关系矩阵是一个对称矩阵。关系图的特点:如果两个顶点之间有边,一定是一对方向相反的边。R是对称的充要条件是关系图中任意两点间有弧线连结,且是双向的。

4.反对称关系

R1,R2为A上的反对称关系,则经过相对补逆运算后仍能保持其反对称性。

反对称关系的关系矩阵的特点:在关系矩阵中,若i≠j,如果rij=1时必有r ji =0。反对称关系的关系图的特点:如果两个顶点之间有边,一定是一条有向边。

注意1:可能有某种关系,即是对称关系,又是反对称关系。如IN为 N上的恒等关系,它既是对称的、又是反对称的。相等关系也是如此。

注意 2:可能有某种关系,即不是对称关系,又不是反对称关系。例S={1,2,3,4},S上的关系R={,,, };则R在S上既不是对称关系,也不是反对称关系。R是反对称的充要条件是:其关系图中任意两点间有弧线时,只能有一条。R是对称的,又是反对称的充要条件:是R是恒等关系,即每个结点只有自环。

5.传递性

R1,R2为A上的传递关系,则经过交和逆运算后仍保持传递性。R是传递的充要条件是:若结点a到b有弧线,b到c有弧线必有a到c有(有向)弧线。R不是传递的充要条件是:其关系图中有从结点a到b,有b到c的有向弧线,但没有从结点a到c的有向弧线。

三、判定性质的方法

上面给出了关系R的五条定义及性质特点,如果用定义来判定R的性质,一般比较困难,但通过关系的性质所具有的特点,我们就可以简化判断关系具有的性质。判断一个关系R是否具有某种性质有很多途径,我们既可以利用性质的定义和定理考察关系R本身,也可以利用其相对应的关系矩阵MR的特点,或者利用R的关系图的特点。下面总结了它们之间的对应关系。

设R为A上的关系,MR、GR分别是R的关系矩阵和关系图,则有:

要判断一个关系是否具有某种性质,很显然可以利用选择最便捷的方法。判断关系传递的性质,最好用关系图GR,这样就避免了R(R或MR2中的计算。

四、传递性的判定

传递性的判定有时则较困难。通过对二元关系传递性定义的深入分析,通过传递性的关系图无捷径可加的特点,只需要通过下列的两基本图就可完成传递性的判断。避免了R(R或MR2中的计算。看下面两图:

当G1图有黑线部分,虚线就是它的捷径,如果无虚线那么此图无传递性。

当G2图有黑线部分,两条虚线就是它的捷径,如果无其中一虚线那么此图无传递性。

(上接第1066页)

(注意:a1、a2和a3是泛指某结点)

例:A={1、2、3、4 },R是A上的关系,R={、、}

RoR={}显然R•R(R不成立,关系矩阵同样需要计算。

上图缺1到4的捷径,即G1号图。在看关系图时,出现G1、G2其中一种图也无传递性,所以我只要找到其中一种,即可判断。

我们可以从G1到G6进行快速看传递性。

观察图以最直接图看,而在观察G4发现它接近全关系,唯一没有a3a1线,我们就要根据有向线,找有没有从a3起点经过任意结点可否能到a1的路。很明显有a3a2,a2a1线,而无a3a1捷径。G5有a1a2,无a2到其它结点,a1a3同理可得。G6任意不同结点没有线相连,好比三座孤岛不可能经过一点到达其它不同点,没有路何来捷径,那么无法加捷径,所以有传递性。

五、总结

影响离散数学教学的因素很多。文中通过对二元关系性质定义的深入分析 ,给出一种等价的定义形式及通过关系矩阵、关系图的判断。提高效率,而且准确。即使遇到比较陌生的题也可以较快地领悟其本质,从而轻松解出。

参考文献:

[1]徐洁磐.离散数学导论(第三版)[M].高等教育出版社.

[2]左孝凌,李为鉴,刘永才.离散数学[M].上海科学技术文献出版社,1982.

[3]杨彦等.离散数学关系教学研究[J].大庆师范学院学报,2008.

[4]吴双全.离散数学中的二元关系[J].呼伦贝尔学报,2006.

[5]曹哓蕾,曹珍富.离散数学[M].机械工业出版社,2009.