论文部分内容阅读
【摘 要】本文利用关系矩阵Hadmard乘积判定二元关系性质的方法，给出了判定二元关系六种性质的算法。
【关键词】二元关系；性质；判定；算法
引言
关系是离散数学中非常重要的内容，关系的六种性质—自反性、反自反性、对称性、反对称性、传递性和反传递性，利用定义判定往往比较麻烦，[1-2]中介绍了利用关系的运算、关系图、关系矩阵的方法判定关系的前五种性质，[3]中利用关系矩阵的Hadmard乘积给出了关系的这六种性质的充要条件。本文利用这个结果，给出了二元关系六种性质判定方法的算法描述。
1.二元关系六种性质的定义
定义1[ 4 ] 设R为集合A上的二元关系，则
（i）若对于任意，均有，则称R在A上是自反的；
（ii） 若对于任意，均有，则称R在A上是反自反的；
（iii）若对于任意，如果，那么有，则称R在A上是对称的；
（iv）若对于任意，如果且，那么一定有，则称R在A上是反对称的；
（v） 若对于任意，如果且，那么，则称R在A上是传递的；
（vi） 若对于任意，如果且，那么，则称R在A上是反传递的.
2.关系矩阵Hadmard乘积判定方法
[3]中引入矩阵的Hadmard乘积的定义，并利用关系矩阵的Hadmard乘积给出了关系性质的充要条件。
定义2 阶矩阵和的Hadmard乘积定义为
即两个同阶矩阵的Hadmard乘积是它们对应元素相乘所得到的矩阵。
定理1 设R为集合A上的二元关系，则
（i）R是自反的当且仅当；
（ii）R是反自反的当且仅当；
（iii）R是对称的当且仅当；
（iv）R是反对称的当且仅当是对角矩阵；
（v） R是传递的当且仅当；
（vi）R是反传递的当且仅当.
其中为R的关系矩阵，为与同阶的单位矩阵，为的关系矩阵，（为矩阵的逻辑乘运算）。
3.易混淆的关系之间的联系
3.1 自反性与反自反性
空集上的空关系既是自反的，又是反自反的。非空集合上的关系，不可能既是自反的又是反自反的。自反性与反自反性的联系可以借助文氏图形象化的表示为图1。
3.2对称性与反对称性
关系矩阵主对角线以外元素全为0，则该关系既是对称的又是反对称的。对称性与反对称性的联系可以借助文氏图形象化的表示为图2。
3.3传递性与反传递性
关系复合矩阵中元素全为0，则该关系既是传递的又是反传递的。传递性与反传递性的联系可以借助文氏图形象化的表示为图3。
4.算法描述
利用定理1的结论，建立判定二元关系性质的算法，通过主函数调用判定自反与反自反、对称与反对称、传递与反传递三个子函数来实现，其主函数算法步骤描述如下：
（i）输入集合A的元素个数；
（ii）输入关系矩阵的各个元素；
（iii）分别调用判定自反与反自反、对称与反对称、传递与反传递的三个子函数。
4.1 判定自反与反自反的子函数
判定自反与反自反的子函数算法流程图如图4所示：
4.2 判定对称与反对称的子函数
判定对称与反对称的子函数算法流程图如图5所示。
4.3 判定傳递与反传递的子函数
判定传递与反传递的子函数算法流程图如图6所示。
参考文献：
[1] 赵岩. 关于离散数学中二元关系性质的探索[J]. 中国科教创新导刊，2012（17）：88.
[2] 伍庆成. 二元关系的性质及判定[J]. 科技信息，2007（9）：157.
[3] 李梅霞. 离散数学中关系性质的判定方法[J]. 大学数学，2010，26（5）：203-206.
[4] 左孝凌，李为鑑，刘永才. 离散数学[M]. 上海：上海科学技术文献出版社，2006：110-113.
作者简介：
董丽欣，女，1982年生，河北邯郸人，青海师范大学计算机学院讲师，硕士。研究方向：复杂网络及其应用。
基金项目：
青海省自然科学基金项目（2014-ZJ-721），教育部春晖计划（No. Z2014022）.
图5 判定对称与反对称的子函数算法流程图
图6判定传递与反传递的子函数算法流程图
【关键词】二元关系；性质；判定；算法
引言
关系是离散数学中非常重要的内容，关系的六种性质—自反性、反自反性、对称性、反对称性、传递性和反传递性，利用定义判定往往比较麻烦，[1-2]中介绍了利用关系的运算、关系图、关系矩阵的方法判定关系的前五种性质，[3]中利用关系矩阵的Hadmard乘积给出了关系的这六种性质的充要条件。本文利用这个结果，给出了二元关系六种性质判定方法的算法描述。
1.二元关系六种性质的定义
定义1[ 4 ] 设R为集合A上的二元关系，则
（i）若对于任意，均有，则称R在A上是自反的；
（ii） 若对于任意，均有，则称R在A上是反自反的；
（iii）若对于任意，如果，那么有，则称R在A上是对称的；
（iv）若对于任意，如果且，那么一定有，则称R在A上是反对称的；
（v） 若对于任意，如果且，那么，则称R在A上是传递的；
（vi） 若对于任意，如果且，那么，则称R在A上是反传递的.
2.关系矩阵Hadmard乘积判定方法
[3]中引入矩阵的Hadmard乘积的定义，并利用关系矩阵的Hadmard乘积给出了关系性质的充要条件。
定义2 阶矩阵和的Hadmard乘积定义为
即两个同阶矩阵的Hadmard乘积是它们对应元素相乘所得到的矩阵。
定理1 设R为集合A上的二元关系，则
（i）R是自反的当且仅当；
（ii）R是反自反的当且仅当；
（iii）R是对称的当且仅当；
（iv）R是反对称的当且仅当是对角矩阵；
（v） R是传递的当且仅当；
（vi）R是反传递的当且仅当.
其中为R的关系矩阵，为与同阶的单位矩阵，为的关系矩阵，（为矩阵的逻辑乘运算）。
3.易混淆的关系之间的联系
3.1 自反性与反自反性
空集上的空关系既是自反的，又是反自反的。非空集合上的关系，不可能既是自反的又是反自反的。自反性与反自反性的联系可以借助文氏图形象化的表示为图1。
3.2对称性与反对称性
关系矩阵主对角线以外元素全为0，则该关系既是对称的又是反对称的。对称性与反对称性的联系可以借助文氏图形象化的表示为图2。
3.3传递性与反传递性
关系复合矩阵中元素全为0，则该关系既是传递的又是反传递的。传递性与反传递性的联系可以借助文氏图形象化的表示为图3。
4.算法描述
利用定理1的结论，建立判定二元关系性质的算法，通过主函数调用判定自反与反自反、对称与反对称、传递与反传递三个子函数来实现，其主函数算法步骤描述如下：
（i）输入集合A的元素个数；
（ii）输入关系矩阵的各个元素；
（iii）分别调用判定自反与反自反、对称与反对称、传递与反传递的三个子函数。
4.1 判定自反与反自反的子函数
判定自反与反自反的子函数算法流程图如图4所示：
4.2 判定对称与反对称的子函数
判定对称与反对称的子函数算法流程图如图5所示。
4.3 判定傳递与反传递的子函数
判定传递与反传递的子函数算法流程图如图6所示。
参考文献：
[1] 赵岩. 关于离散数学中二元关系性质的探索[J]. 中国科教创新导刊，2012（17）：88.
[2] 伍庆成. 二元关系的性质及判定[J]. 科技信息，2007（9）：157.
[3] 李梅霞. 离散数学中关系性质的判定方法[J]. 大学数学，2010，26（5）：203-206.
[4] 左孝凌，李为鑑，刘永才. 离散数学[M]. 上海：上海科学技术文献出版社，2006：110-113.
作者简介：
董丽欣，女，1982年生，河北邯郸人，青海师范大学计算机学院讲师，硕士。研究方向：复杂网络及其应用。
基金项目：
青海省自然科学基金项目（2014-ZJ-721），教育部春晖计划（No. Z2014022）.
图5 判定对称与反对称的子函数算法流程图
图6判定传递与反传递的子函数算法流程图