用C程序实现对二元关系性质的判定

用C程序实现对二元关系性质的判定

ＩＴ技术

数字技术与应用

用Ｃ程序实现对二元关系性质的判定

岳晓红

（陇东学院信息工程学院　　甘肃庆阳　　７４５０００）

摘　要：本文利用Ｃ语言程序实现了对离散数学中二元关系的５种性质的判断。在计算机相关专业的教学中可以培养学生的理论和计算机操作相结合的学习能力。

关键词：Ｃ语言　　离散数学　　二元关系中图分类号：Ｏ１４１．１２文献标识码：Ａ文章编号：１００７－９４１６（２０１１）０２－００７１－０２

Ｔｏ　Ｊｕｄｇｅ　ｔｈｅ　Ｐｒｏｐｅｒｔｙ　ｏｆ　Ｂｉｎａｒｙ　Ｒｅａｌｔｉｏｎｓ　ｂｙ　Ｃ　ｐｒｏｇｒａｍ

Ｙｕｅ　Ｘｉａｏｈｏｎｇ

（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　　Ｑｉｎｇｙａｎｇ　ｇａｎｓｕ　　７４５０００）

Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ｓｏｍｅ　ｗａｙｓ　ｔｏ　ｊｕｄｇｅ　ｔｈｅ　５　ｐｒｏｐｅｒｔｉｅｓ　ｏｆ　ｂｉｎａｒｙ　ｒｅｌａｔｉｏｎｓ　ｉｎ　ｔｈｅ　ｄｉｓｃｒｅｔｅ　ｍａｔｈｅｍａｔｉｃｓ，　ａｎｄ　ｔｈｅｙ　ｃａｎ　ｂｅ　ａｐｐｌｉｅｄ　ｔｏ　ｃｕｌｔｉｖａｔｅ　ｔｈｅ　ｓｔｕｄｅｎｔｓ’ａｂｉｌｉｔｉｅｓ　ｂｙ　ｉｎｔｅｇｒａｔｉｎｇ　ｔｈｅｏｒｙ　ｗｉｔｈ　ｐｒａｃｔｉｃｅ．

Ｋｅｙ　ｗｏｒｄｓ：Ｃ　ｌａｎｇｕａｇｅ　　ｄｉｓｃｒｅｔｅ　ｍａｔｈｅｍａｔｉｃｓ　　ｂｉｎａｒｙ　ｒｅｌａｔｉｏｎｓ；

对于计算机专业的学生，《离散数学》是专业基础课，《Ｃ语言程序设计》也是专业课，两门课开设的时间大都在一年级第一或第二学期。在学习这两门课时，可以互相借鉴，离散数学中的有些问题可以利用Ｃ语言编程在计算机上实现，反之，对Ｃ语言相关知识的学习，也可以以离散数学的问题算法为例，这样的学习过程，既可以加深对两门课程相关知识的理解和掌握，也能培养学生的理论和实践相结合的学习能力。

２、二元关系的性质与关系矩阵（如下图）

性质　

自反性　反自反性　对称性　反对称性　传递性　

关系矩阵　

主对角线元素全为１　主对角线元素全为０　对称矩阵　

如r=1且i≠j,则r=0　

i,j

j,i

M2中1所在的位置，M中相应位置都是1１、离散数学中二元关系、关系矩阵及其性质的定义

定义１：设Ａ，Ｂ为集合，Ａ×Ｂ的任何子集所定义的二元关系叫做从Ａ到Ｂ的二元关系，特别当Ａ＝Ｂ时则叫做Ａ上的二元关系。

定义２：设A={a1,a2Lan}，Ｒ是Ａ上的关系。

(i,j=1,2Ln)令ri,j=

0,(ai,aj) R

1,(ai,aj)∈R

３、用Ｃ程序实现对５种性质的判定

＃ｄｅｆｉｎｅ　Ｍ　１０＃ｉｎｃｌｕｄｅ＜ｓｔｄｉｏ．ｈ＞ｖｏｉｄ　ｍａｉｎ（）

｛　ｖｏｉｄ　ｚｆｘ（ｉｎｔ　ａ［］［］，　ｉｎｔ　ｎ）；／＊函数声明＊／ｖｏｉｄ　ｄｃｘ（ｉｎｔ　ａ［］［］，　ｉｎｔ　ｎ）；ｖｏｉｄ　ｃｄｘ１（ｉｎｔ　ａ［］［］，　ｉｎｔ　ｎ）；ｖｏｉｄ　ｃｄｘ２　（ｉｎｔ　ａ［Ｍ］［Ｍ］，ｉｎｔ　ｎ）；ｉｎｔ　ａ［Ｍ］［Ｍ］，　ｉ，ｊ，ｎ；

ｐｒｉｎｔｆ（＂请输入关系矩阵的维数ｎ（ｎ＜＝Ｍ）：＼ｎ＂）；ｓｃａｎｆ（＂％ｄ＂，＆ｎ）；

ｐｒｉｎｔｆ（＂请输入关系矩阵的元素值（０，１）：＼ｎ＂）；ｆｏｒ（ｉ＝０；ｉ＜ｎ；ｉ＋＋）ｆｏｒ（ｊ＝０；ｊ＜ｎ；ｊ＋＋）ｓｃａｎｆ（＂％ｄ＂，＆ａ［ｉ］［ｊ］）；ｚｆｘ（ａ，ｎ）；／＊调用函数＊／ｄｃｘ（ａ，ｎ）；ｃｄｘ１（ａ，ｎ）；ｃｄｘ２（ａ，ｎ）；

r11

r(ri,j)= 21

M　则

rn1

r12Lr1n r22Lr2n

是Ｒ上的关系矩阵，记作MR。M

rn2Lrnn

定义３：设Ｒ为Ａ上的关系，

（１）若 x(x∈A→(x,x)∈R)，则称Ｒ在Ａ上是自反的。（２）若 x(x∈A→(x,x) R)，则称Ｒ在Ａ上是反自反的。（３）若 x y(x,y∈A∧(x,y)∈R→(y,x)∈R)，则称Ｒ为Ａ上的对称关系。

（４）若 x y(x,y∈A∧(x,y)∈R∧(y,x)∈R→x=y)，则称Ｒ为Ａ上的反对称关系。

（５）若传递关系。

x y z(x,y,z∈A∧(y,z)∈R→(x,z)∈R)

，则称Ｒ为Ａ上的ｇｅｔｃｈ（）；｝

Ｄｉｇｉｔａｌ　　ｔｅｃｈｎｏｌｏｇｙ　　ａｎｄ　　ａｐｐｌｉｃａｔｉｏｎ　　　　数字技术与应用

71

用C程序实现对二元关系性质的判定

数字技术与应用

ｖｏｉｄ　ｚｆｘ（ｉｎｔ　ａ［Ｍ］［Ｍ］，　ｉｎｔ　ｎ）　　

｛　ｉｎｔ　ｉ＝０，ｖａｌｅ１＝１，ｖａｌｅ２＝１；／＊ｖａｌｅ１确定关系的自反性，ｖａｌｅ２判断关系的反自反性＊／

ｗｈｉｌｅ（ｉ＜ｎ）　　

｛　ｉｆ　（ａ［ｉ］［ｉ］＝＝１）　ｖａｌｅ２＝０；ｅｌｓｅ　ｖａｌｅ１＝０；ｉ＋＋；｝　

ｉｆ　（ｖａｌｅ１＝＝１）　ｐｒｉｎｔｆ（＂ｚｆｘ＼ｎ＂）；ｉｆ　（ｖａｌｅ２＝＝１）　ｐｒｉｎｔｆ（＂ｆｚｆｘ＼ｎ＂）；

ｉｆ　（！（ｖａｌｅ１）＆＆！（ｖａｌｅ２））　ｐｒｉｎｔｆ（＂ｗｚｆｘｙｗｆｚｆｘ＼ｎ＂）；｝

ｖｏｉｄ　ｄｃｘ（ｉｎｔ　ａ［Ｍ］［Ｍ］，　ｉｎｔ　ｎ）

｛　ｉｎｔ　ｉ，ｊ，　ｖａｌｅ３＝１，ｖａｌｅ４＝１；／＊ｖａｌｅ３确定关系的对称性，ｖａｌｅ４判断关系的反对称性＊／

ｆｏｒ（ｉ＝０；ｉ＜ｎ；ｉ＋＋）ｆｏｒ（ｊ＝０；　ｊ＜ｉ；ｊ＋＋）ｉｆ（ａ［ｉ］［ｊ］＝＝ａ［ｊ］［ｉ］）ｖａｌｅ４＝０；ｅｌｓｅ　ｖａｌｅ３＝０；

ｉｆ　（ｖａｌｅ３＝＝１）　ｐｒｉｎｔｆ（＂ｄｃｘ＼ｎ＂）；ｉｆ　（ｖａｌｅ４＝＝１）　ｐｒｉｎｔｆ（＂ｆｄｃｘ＼ｎ＂）；

ｉｆ　（！（ｖａｌｅ３）＆＆！（ｖａｌｅ４））　ｐｒｉｎｔｆ（＂ｗｄｃｘ　ｗｆｄｃｘ＼ｎ＂）；｝

ｖｏｉｄ　ｃｄｘ１　（ｉｎｔ　ａ［Ｍ］［Ｍ］，ｉｎｔ　ｎ）／＊用M2 M算法来判断传递性＊／

｛　ｉｎｔ　ｂ［Ｍ］［Ｍ］，ｉ，ｊ，ｋ，ｖａｌｅ＝１；ｆｏｒ（ｉ＝０；ｉ＜ｎ；ｉ＋＋）ｆｏｒ（ｊ＝０；ｊ＜ｎ；　ｊ＋＋）｛ｂ［ｉ］［ｊ］＝０；

ｆｏｒ（ｋ＝０；　ｋ＜ｎ；　ｋ＋＋）

ｂ［ｉ］［ｊ］＋＝ａ［ｉ］［ｋ］＊ａ［ｋ］［ｊ］；／＊计算　M2＊／｝

ｆｏｒ（ｉ＝０；ｉ＜ｎ；ｉ＋＋）ｆｏｒ（ｊ＝０；ｊ＜ｎ；ｊ＋＋）ｉｆ（ｂ［ｉ］［ｊ］！＝０）ｂ［ｉ］［ｊ］＝１；ｆｏｒ（ｉ＝０；ｉ＜ｎ；ｉ＋＋）ｆｏｒ（ｊ＝０；ｊ＜ｎ；ｊ＋＋）ｉｆ（ｂ［ｉ］［ｊ］＝＝１）

ｉｆ（ａ［ｉ］［ｊ］！＝ｂ［ｉ］［ｊ］）ｖａｌｅ＝０；ｉｆ（ｖａｌｅ）ｐｒｉｎｔｆ（＂ｙｃｄｘ＼ｎ＂）；ｅｌｓｅ　　　　ｐｒｉｎｔｆ（＂ｗｃｄｘ＼ｎ＂）；｝

ＩＴ技术

ｖｏｉｄ　ｃｄｘ２　（ｉｎｔ　ａ［Ｍ］［Ｍ］，ｉｎｔ　ｎ）／＊用ｗａｒｓｈａｌｌ算法来求传递闭包数组ｂ　＊／

｛　ｉｎｔ　ｂ［Ｍ］［Ｍ］，ｉ，ｊ，ｋ，ｖａｌｅ＝１；ｆｏｒ（ｉ＝０；ｉ＜ｎ；　ｉ＋＋）ｆｏｒ（ｊ＝０；ｊ＜ｎ；ｊ＋＋）ｂ［ｉ］［ｊ］＝ａ［ｉ］［ｊ］；｛

ｆｏｒ（ｋ＝０；　ｋ＜ｎ；　ｋ＋＋）（ａ［ｉ］［ｊ］＆＆（ａ［ｉ］［ｋ］｜｜ａ［ｊ］［ｋ］））ｉｆ｛ｂ［ｉ］［ｋ］＝１；｝｝

ｆｏｒ（ｉ＝０；ｉ＜ｎ；ｉ＋＋）　　　　　／＊　判断数组ａ和ｂ相等　＊／ｆｏｒ（ｊ＝０；ｊ＜ｎ；ｊ＋＋）（ａ［ｉ］［ｊ］！＝ｂ［ｉ］［ｊ］）ｉｆ

｛　ｖａｌｅ＝０；　ｂｒｅａｋ；｝

ｉｆ　（ｖａｌｅ＝＝１）　ｐｒｉｎｔｆ（＂ｃｄｘ＼ｎ＂）；ｅｌｓｅ　ｐｒｉｎｔｆ（＂ｗｃｄｘ＼ｎ＂）；｝

注释

[1]对于传递性质的判定,可以利用关系矩阵的特点定义函数,但使

用warshallsuan 算法写出的函数更简洁。

[2]　以上程序在wintc环境下编译运行成功。在turboc2.0中汉字用拼音替换后运行也正常。　

参考文献

[1]谭浩强.C程序设计[M].北京:清华大学出版社,2001.[2]耿素云.离散数学[M].北京:高等教育出版社,2003.

[3]郭键.二元关系传递闭包的几种求取方法分析[J].网络安全技术

与应用,2008.

72数字技术与应用　　　　Ｄｉｇｉｔａｌ　　ｔｅｃｈｎｏｌｏｇｙ　　ａｎｄ　　ａｐｐｌｉｃａｔｉｏｎ

本文来源：https://www.bwwdw.com/article/m5zm.html