1關系

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

1.1 關系的定義

在關系模型中，數據是以二維表的形式存在的，這個二維表就叫做關系。關系理論是以集合代數理論為基礎的，因此，我們可以用集合代數給出二維表的關系的定義。 為了以集合論的角度給出關系的定義，我們先引入笛卡爾積的概念。在定義笛卡爾積之前，先來了解有序對的定義。

定義 1 由兩個元素 x 和 y（允許 x=y）按一定的順序排列成的二元組叫做一個有序對（也稱序偶），記作.其中 x 是它的第一元素，y是它的第二元素。

一般說來有序對具有以下特點：（1）當 x≠y 時，≠;（2）兩個有序對相等，即=的充分必要條件是 x=u 且 y=v.這些特點是集合{x,y}所不具備的，例如，當 x≠y 時，有{x,y}={y,x}.原因在于有序對中強調了 x 與 y 的序列性，而集合{x,y}中的 x 和y 是無序的。定義 2 一個有序 n 元組（n≥3）是一個有序對，其中第一個元素是一個有序 n-1 元組，一個有序 n 元組記作,即=《x1,…，xn-1>,xn>.

下面定義給出笛卡爾積的定義，它是一種集合運算。定義 3 設 A、B 為集合， 用 A 中元素為第一元素，B 中元素為第二元素，構成有序對。所有這樣的有序對組成的集合叫做 A 和 B 的笛卡爾積，記作 A×B.符號化表示為A×B={|x∈A∧y∈B}.例 1 A={a,b},B={0,1,2},則A×B={,,,,,,};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.它表示了集合{甲，乙，丙}中元素之間的一種勝負關系。

除了二元關系以外，還有多元關系，在此不做討論。下面出現關系的地方均指二元關系。下面給出二元關系的一般定義。

定義 4 如果一個集合為空集或者它的元素都是有序對，則稱這個集合是一個二元關系，一般記作 R.對于二元關系 R,如果∈R,則記作 xRy;如果埸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,±…同余關系具有以下性質：

（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）。

不難看出，同余關系是一種等價關系。實際應用中，我們將這種關系推廣到了密碼學中，先看一下下面這個例子。

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

凱撒密碼的字母對應關系：A b c d e f g h i … x y zC 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 zN o p q r s t u v … k l m （[2]）

參考文獻:
[1][美]Paul Garrett.密碼學導引[M].北京：機械工業出版社，2003:107-178.
[2]斯漢.密碼學與計算機網絡安全[M].北京：清華大學出版社，2001:17-58.
[3]耿素云,屈婉玲，張立昂，編。離散數學。3 版。北京：清華大學出版社，2004,3.