韓寶燕

（山東工藝美術(shù)學(xué)院公共課教學(xué)部，山東 濟(jì)南250000）

1 關(guān)系

宇宙萬物之間存在著形形色色的聯(lián)系，這種聯(lián)系正是各門學(xué)科所關(guān)注的根本問題.例如，人與人之間有父子、兄弟、師生關(guān)系；兩數(shù)之間有大于、等于、小于關(guān)系；電學(xué)中有電壓、電阻與電流間的關(guān)系；元素與集合之間的屬于關(guān)系；計算機(jī)科學(xué)中程序間的調(diào)用關(guān)系，程序執(zhí)行過程中狀態(tài)之間的轉(zhuǎn)換關(guān)系，程序執(zhí)行前變量取值狀況和執(zhí)行后變量取值狀況的關(guān)系，文件與路徑的關(guān)系……集合論為刻劃這種聯(lián)系提供了一種數(shù)學(xué)模型——關(guān)系，它仍然是一個集合，以具有那種聯(lián)系的對象組合為其成員.換言之，集合論中關(guān)系不是通過描述關(guān)系的內(nèi)涵來刻劃這種聯(lián)系，而是通過列舉其外延(具有那種聯(lián)系的對象組合全體)來刻劃這種聯(lián)系.這使關(guān)系的研究可以方便地使用集合論概念、運算及研究方法和研究成果.

1.1 關(guān)系的定義

在關(guān)系模型中，數(shù)據(jù)是以二維表的形式存在的，這個二維表就叫做關(guān)系.關(guān)系理論是以集合代數(shù)理論為基礎(chǔ)的，因此，我們可以用集合代數(shù)給出二維表的關(guān)系的定義.為了以集合論的角度給出關(guān)系的定義，我們先引入笛卡爾積的概念.

在定義笛卡爾積之前，先來了解有序?qū)Φ亩x.

定義1 由兩個元素x和y(允許x=y)按一定的順序排列成的二元組叫做一個有序?qū)Γㄒ卜Q序偶），記作＜x,y＞.其中x是它的第一元素，y是它的第二元素.

一般說來有序?qū)哂幸韵绿攸c：

（1）當(dāng) x≠y 時，＜x,y＞≠＜y,x＞；

（2）兩個有序?qū)ο嗟?，即＜x,y＞＝＜u,v＞的充分必要條件是 x=u 且 y=v.

這些特點是集合{x,y}所不具備的，例如，當(dāng)x≠y時，有{x,y}＝{y,x}.原因在于有序?qū)Γ紉,y＞中強(qiáng)調(diào)了x與y的序列性，而集合{x,y}中的x和y是無序的.

定義2 一個有序n元組(n≥3)是一個有序?qū)?，其中第一個元素是一個有序n-1元組，一個有序n元組記作＜x1,x2,…,xn＞，即＜x1,x2,…,xn＞＝＜＜x1,…,xn-1＞,xn＞.

下面定義給出笛卡爾積的定義，它是一種集合運算.

定義3 設(shè)A、B為集合，用A中元素為第一元素，B中元素為第二元素，構(gòu)成有序?qū)?所有這樣的有序?qū)M成的集合叫做A和B的笛卡爾積，記作A×B.符號化表示為

例 1 A={a,b},B＝{0,1,2},則

由排列組合的知識不難證明，如果A中有m個元素，B中有n個元素，則A×B和B×A中都有mn個元素.

下面研究與笛卡爾積密切相關(guān)的一個重要概念——二元關(guān)系.

在現(xiàn)階段我們用的最多的是二元關(guān)系，所謂二元關(guān)系就是在集合中兩個元素之間的某種相關(guān)性.例如，甲、乙、丙3個人進(jìn)行乒乓球比賽，如果任何兩個人之間都要賽一場，那么共要賽三場.假如三場比賽的結(jié)果是乙勝甲、甲勝丙、乙勝丙，這個結(jié)果可以記作{＜乙，甲＞,＜甲，丙＞,＜乙，丙＞}，其中＜x,y＞表示 x 勝 y.它表示了集合{甲，乙，丙}中元素之間的一種勝負(fù)關(guān)系.

除了二元關(guān)系以外，還有多元關(guān)系，在此不做討論.下面出現(xiàn)關(guān)系的地方均指二元關(guān)系.下面給出二元關(guān)系的一般定義.

定義4 如果一個集合為空集或者它的元素都是有序?qū)Γ瑒t稱這個集合是一個二元關(guān)系，一般記作R.對于二元關(guān)系R，如果＜x,y＞∈R，則記作 xRy；如果＜x,y＞?R，則記作.

定義5 設(shè)A、B為集合，A×B的任何子集所定義的二元關(guān)系稱作從A到B的二元關(guān)系，特別當(dāng)A＝B時，則叫做A上的二元關(guān)系.

定義6 對任何集合A，

EA＝{〈x,y〉｜x∈A∧y∈A}＝A×A IA={〈x,x〉｜x∈A}

1.2 關(guān)系的性質(zhì)

在一個很小的集合上就可以定義很多個不同的關(guān)系，但是真正有實際意義的只是其中很少的一部分，它們一般都是有著某些性質(zhì)的關(guān)系.

設(shè)R是A上的關(guān)系，R的性質(zhì)主要有以下5種：自反性、反自反性、對稱性、反對稱性和傳遞性.它們的定義及其在關(guān)系矩陣中的特征如表1所示.

根據(jù)表1所列的特點不難判斷關(guān)系的性質(zhì).例如，集合A上的全域關(guān)系和恒等關(guān)系是自反的、對稱的和傳遞的.整除關(guān)系、小于等于關(guān)系和冪集上的包含關(guān)系是自反的、反對稱的和傳遞的.

表1

2 在密碼學(xué)中的應(yīng)用

在離散數(shù)學(xué)中有一種關(guān)系——同余關(guān)系，面我們來看看它的具體定義.

定義4 給定正整數(shù)m，若用m去除兩個整數(shù)a和b所得余數(shù)相同，稱a和b對模m同余，記作a≡b(mod m)，并稱該式為同余式.

對于給定的b和m，與b模m同余的所有數(shù)為：

b＋km，其中 k＝0，±1，±2，±….

同余關(guān)系具有以下性質(zhì)：

（1）自反性 a≡a(mod m).

（2）對稱性 若 a≡b(mod m)，則 b≡a(mod m).

（3）傳遞性 若 a≡b(mod m)，b≡c(mod m)，則 a≡c(mod m).

不難看出，同余關(guān)系是一種等價關(guān)系.

實際應(yīng)用中，我們將這種關(guān)系推廣到了密碼學(xué)中，先看一下下面這個例子.

例 凱撒密碼

這是一個古老的加密方法，當(dāng)年凱撒大帝行軍打仗時用這種方法進(jìn)行通信，因此得名.它的原理很簡單，其實就是單字母的替換.看一個簡單的例子：“This is Caesar Code”.用凱撒密碼加密后字符串變?yōu)椤皏jku ku Ecguct Eqfg”.看起來似乎加密得很“安全”.可是你可以嘗試一下，把這段很難懂的東西每一個字母換為字母表中前移2位的字母……哦，結(jié)果出來了.

凱撒密碼的字母對應(yīng)關(guān)系：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的同余關(guān)系的一種應(yīng)用.再來看下面一個例子.

例 （rot13）ROT13是網(wǎng)絡(luò)上常見的一種簡單的“加密”方式.它的原理和凱撒密碼非常類似.凱撒密碼移了2位，而ROT13移了13位.ROT13通常作為簡單的手段使得我們的電子信件不能被直接識別和閱讀，也不會被那些匹配程序用通常的方法直接找到.

如“V Ybir lbh!”這個句子實際上是“I Love you!”.

ROT13字母對應(yīng)關(guān)系：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])

［1］[美]Paul Garrett.密碼學(xué)導(dǎo)引[M].北京：機(jī)械工業(yè)出版社,2003：107-178.

［2］斯?jié)h.密碼學(xué)與計算機(jī)網(wǎng)絡(luò)安全[M].北京：清華大學(xué)出版社,2001：17-58.

［3］耿素云,屈婉玲,張立昂,編.離散數(shù)學(xué).3 版.北京：清華大學(xué)出版社,2004,3.