浅谈关系矩阵在离散数学教学中的应用

李文钰　杜忠复　张丽春

【摘要】本文研究总结了关系矩阵在离散数学教学中的应用，具体包括关系矩阵、关系的复合与逆运算、关系的性质、关系的闭包运算和等价关系.这样离散数学中的问题就可以通过矩阵利用计算机来解决，进而达到化抽象为具体，化繁为简的目的.

【关键词】离散数学；关系矩阵；二元关系

离散数学是描绘一些离散量与量之间相互逻辑结构及关系的一门科学，它的思想方法及内容已经渗透到计算机科学的各个领域，因此它成为计算机及相关专业的一门重要的专业基础课.然而这门课程具有概念繁多，理论性较强，高度抽象的特点，容易致使学生对这门课的兴趣不高，产生畏惧心理.因此，如何提高这门课程的教学质量，具有很强的现实的意义.矩阵是线性代数的基本概念之一，矩阵可以使许多抽象的数学对象得到具体的表示，并把相关的运算转化为矩阵的简单运算，使其在一定程度上化繁为简，变抽象为具体.它是解决很多实际问题和数学问题的强有力工具，在离散数学上也有很大程度的应用.因此，我们希望把矩阵在离散数学中的应用实例总结出来，以期能够达到更好的教学效果.

为了更好地说明矩阵在二元关系中的应用，首先定义关系矩阵.

2.关系的性质

关系的性质主要包括：关系的自反性、反自反性、对称性、反对称性和传递性.这五条性质都可以表现在关系矩阵上.若关系R具有自反性，当且仅当其关系矩阵MR主对角线上的元素全为1；若关系R具有反自反性，当且仅当其关系矩阵MR主对角线上的元素均为0；若关系R既不是自反的也不是非自反的，当且仅当其关系矩阵MR主对角线上既有0又有1；若关系R具有传递性，当且仅当M2R+MR=MR；若关系R有对称性，当且仅当MR=MTR，即MR是对称阵.这样一来，学生有着对线性代数的基础，原本陌生的二元关系的性质就更直观，更简洁地体现出来了.

3.关系的闭包运算

二元关系的闭包运算是离散数学教学的一个重点也是难点，它包括自反闭包、对称闭包和传递闭包.我们知道闭包是包含有此关系的最小的关系.但大部分学生都会觉得闭包概念十分抽象，尤其在传递闭包的计算时感觉困难.但我们用矩阵来表述时，学生会更容易接受.

定理3 设R是集合A上的一个关系，则其自反包r（R）=R∪Q，用矩阵表示即为Mr（R）=MR+MQ，其中Q={（x，x）|x∈A}.

定理4 设R是集合A上的一个关系，则其对称闭包s（R）=R∪R-1，用矩阵表示即为Ms（R）=MR+MR-1=MR+MTR.

定理5 设R是集合A上的一个关系，则其传递闭包t（R）=∪∞i=1Ri=R∪R2∪….用矩阵表示即为Mt（R）=MR+MR2+….

推论1 设R是含有n个元素的有限集合A上的一个关系，则其传递闭包t（R）=∪ni=1Ri.用矩阵表示即为Mt（R）=MR+MR2+…+MRn.

注：上述矩阵运算均为布尔运算.

4.等价关系

在研究等价关系时，我们仍然可以利用关系矩阵的特征来进行判断.

定理6 若R是集合A上的等价关系，当且仅当R的矩阵MR具有如下特征：

（1）MR的主对角线上的元素全为1；

（2）MR是对称矩阵；

（3）MR可以经过有限次把行与行及相应的列与列调换为主对角型分块矩阵，且对角线上每个子块都是全1方阵.

本文研究总结了关系矩阵在二元关系的复合与逆运算、关系的性质、关系的闭包运算和等价关系等几方面的应用.通过上述研究以及在实际离散数学教学中的经验发现，矩阵的引入使得这一部分的知识更直观，学生更易于接受.尤其对于计算数学和计算机相关专业的学生可以通过上机来计算相应例题，把原本抽象的问题具体化、简单化，进而也提高了他们的专业兴趣，起到了良好的教学效果.

【参考文献】

[1]杜中复，陈兆均.离散数学[M].北京：高等教育出版社，2004.

[2]耿素云，屈婉玲.离散数学（修订版）[M].北京：高等教育出版社，2004.