韩宝燕
（山东工艺美术学院公共课教学部，山东 济南 250000）
【摘 要】本文我们给出关系的定义，讨论关系学中的重要分支之一等价关系，给出关系学在密码学中的应用.
教育期刊网 http://www.jyqkw.com
关键词 密码学；离散数学；关系学
1 关系
宇宙万物之间存在着形形色色的联系，这种联系正是各门学科所关注的根本问题. 例如，人与人之间有父子、兄弟、师生关系；两数之间有大于、等于、小于关系；电学中有电压、电阻与电流间的关系；元素与集合之间的属于关系；计算机科学中程序间的调用关系，程序执行过程中状态之间的转换关系，程序执行前变量取值状况和执行后变量取值状况的关系，文件与路径的关系……集合论为刻划这种联系提供了一种数学模型——关系，它仍然是一个集合，以具有那种联系的对象组合为其成员.换言之，集合论中关系不是通过描述关系的内涵来刻划这种联系，而是通过列举其外延(具有那种联系的对象组合全体)来刻划这种联系.这使关系的研究可以方便地使用集合论概念、运算及研究方法和研究成果.
1.1 关系的定义
在关系模型中，数据是以二维表的形式存在的，这个二维表就叫做关系.关系理论是以集合代数理论为基础的，因此，我们可以用集合代数给出二维表的关系的定义.为了以集合论的角度给出关系的定义，我们先引入笛卡尔积的概念.
在定义笛卡尔积之前，先来了解有序对的定义.
定义1 由两个元素x和y(允许x=y)按一定的顺序排列成的二元组叫做一个有序对（也称序偶），记作<x,y>.其中x是它的第一元素，y是它的第二元素.
一般说来有序对具有以下特点：
（1）当x≠y时，<x,y>≠<y,x>；
（2）两个有序对相等，即<x,y>=<u,v>的充分必要条件是x=u且y=v.
这些特点是集合{x,y}所不具备的，例如，当x≠y时，有{x,y}={y,x}.原因在于有序对<x,y>中强调了x与y的序列性，而集合{x,y}中的x和y是无序的.
定义2 一个有序n元组(n≥3)是一个有序对，其中第一个元素是一个有序n-1元组，一个有序n元组记作<x1,x2,…,xn>，即<x1,x2,…,xn>=<<x1,…,xn-1>,xn>.
下面定义给出笛卡尔积的定义，它是一种集合运算.
定义3 设A、B为集合，用A中元素为第一元素，B中元素为第二元素，构成有序对.所有这样的有序对组成的集合叫做A和B的笛卡尔积，记作A×B.符号化表示为
A×B={<x,y>｜x∈A∧y∈B}.
例1 A={a,b},B={0,1,2},则
A×B={<a,0>,<a,1>,<a,2>,<a,2>,<b,0>,<b,1>,<b,2>};
B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}.
由排列组合的知识不难证明，如果A中有m个元素，B中有n个元素，则A×B和B×A中都有mn个元素.
下面研究与笛卡尔积密切相关的一个重要概念——二元关系.
在现阶段我们用的最多的是二元关系，所谓二元关系就是在集合中两个元素之间的某种相关性.例如，甲、乙、丙3个人进行乒乓球比赛，如果任何两个人之间都要赛一场，那么共要赛三场.假如三场比赛的结果是乙胜甲、甲胜丙、乙胜丙，这个结果可以记作{<乙，甲>,<甲，丙>,<乙，丙>}，其中<x,y>表示x胜y.它表示了集合{甲，乙，丙}中元素之间的一种胜负关系.
除了二元关系以外，还有多元关系，在此不做讨论.下面出现关系的地方均指二元关系.下面给出二元关系的一般定义.
定义4 如果一个集合为空集或者它的元素都是有序对，则称这个集合是一个二元关系，一般记作R.对于二元关系R，如果<x,y>∈R，则记作xRy；如果<x,y>∈R，则记作
定义5 设A、B为集合，A×B的任何子集所定义的二元关系称作从A到B的二元关系，特别当A=B时，则叫做A上的二元关系.
对于任何集合A都有3种特殊的关系.其中之一就是空集
，它是A×A的子集，也是A上的关系，称作空关系.另外两种就是全域关系EA和恒等关系IA.
定义6 对任何集合A，
EA={〈x,y〉｜x∈A∧y∈A}=A×A IA={〈x,x〉｜x∈A}
1.2 关系的性质
在一个很小的集合上就可以定义很多个不同的关系，但是真正有实际意义的只是其中很少的一部分，它们一般都是有着某些性质的关系.
设R是A上的关系，R的性质主要有以下5种：自反性、反自反性、对称性、反对称性和传递性.它们的定义及其在关系矩阵中的特征如表1所示.
根据表1所列的特点不难判断关系的性质.例如，集合A上的全域关系和恒等关系是自反的、对称的和传递的.整除关系、小于等于关系和幂集上的包含关系是自反的、反对称的和传递的.
2 在密码学中的应用
在离散数学中有一种关系——同余关系，面我们来看看它的具体定义.
定义4 给定正整数m，若用m去除两个整数a和b所得余数相同，称a和b对模m同余，记作a≡b(mod m)，并称该式为同余式.
对于给定的b和m，与b模m同余的所有数为：
b＋km，其中k＝0，±1，±2，±….
同余关系具有以下性质：
（１）自反性 a≡a(mod m).
（２）对称性 若a≡b(mod m)，则b≡a(mod m).
（３）传递性 若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m).
不难看出，同余关系是一种等价关系.
实际应用中，我们将这种关系推广到了密码学中，先看一下下面这个例子.
例 凯撒密码
这是一个古老的加密方法，当年凯撒大帝行军打仗时用这种方法进行通信，因此得名.它的原理很简单，其实就是单字母的替换.看一个简单的例子：“This is Caesar Code”.用凯撒密码加密后字符串变为“vjku ku Ecguct Eqfg”.看起来似乎加密得很“安全”.可是你可以尝试一下，把这段很难懂的东西每一个字母换为字母表中前移2位的字母……哦，结果出来了.
凯撒密码的字母对应关系：A b c d e f g h i … x y z
C d e f g h I j k … z a b （[1]） ，
从这个例子不难看出，实际上就是模为2的同余关系的一种应用.再来看下面一个例子.
例 （rot13）ROT13是网络上常见的一种简单的“加密”方式.它的原理和凯撒密码非常类似.凯撒密码移了2位，而ROT13移了13位.ROT13通常作为简单的手段使得我们的电子信件不能被直接识别和阅读，也不会被那些匹配程序用通常的方法直接找到.
如“V Ybir lbh!”这个句子实际上是“I Love you!”.
ROT13字母对应关系：A b c d e f g h I … x y z
N o p q r s t u v … k l m ([2])
教育期刊网 http://www.jyqkw.com
参考文献
［１］[美]Paul Garrett.密码学导引[M].北京:机械工业出版社,2003:107-178.
［２］斯汉.密码学与计算机网络安全[M].北京:清华大学出版社,2001:17-58.
［３］耿素云,屈婉玲,张立昂,编.离散数学.3版.北京:清华大学出版社,2004,3.
［责任编辑：汤静］