關係

數學中關係

關係常指徠二元關係,數學的基本概念之一,關係是在集合的基礎上定義的一個重要的概念,與集合的概念一樣,關係的概念在計算機科學中也是最基本的。它主要反映元素之間的聯繫和性質,在計算機科學中有重要的意義,如有限自動機和形式語言、編譯程序設計、信息檢索、數據結構以及演演算法分析和程序設計的描述中經常出現。

基本概念


定義

給定任意集合A和B,若,則稱R為從A到B的二元關係,特別在A=B時,稱R為A上的二元關係.可見,R是有序對的集合.若,則也表示為,即
,則稱R為A到B上空關係;若R=A×B,稱R為A到B上全域關係.特別當A=B時,稱為A上空關係,稱R=AXA為A上的全域關係.稱為A上的恆等關係,記為

定義域與值域和域

,且
則稱D(R)、R(R)和F(R)分別是二元關係R的定義域、值域和域。
顯然
關係是有序對的集合,對它可進行集合運算,其結果也是有序對的集合,即也是某一種二元關係。令R和S是兩個二元關係,則和R'都分別定義了某一種二元關係,並且可表示成:

矩陣


表達從有窮集合到有窮集合的二元關係時,矩陣和有向圖都是得力的工具。
定義給集合,且.若則稱矩陣為R的關係矩陣。
當給定關係R,可求出關係矩陣;反之,若給出關係矩陣,也能求出關係R。
集合A上的二元關係R也可用有向圖表示.具體方法是:用小圓圈表示A中的元素,小圓圈稱為圖的結點,把對應於元素的結點分別標記,則用弧線段或直線段把連接起來,並在弧線或直線上設置一箭頭,使之由指向;若,則在結點上畫一條帶箭頭的自封閉曲線或有向環,稱這樣的弧線或封閉曲線為弧或有向環,這樣得到的有向圖叫做關係R的圖示,簡稱關係圖,記為

性質


關係的性質是指集合中二元關係的性質,這些性質扮演著重要角色,下面將定義這些性質。並給出它的關係矩陣和關係圖的特點。
自反令,若對A中每個x,都有,則稱R是自反的,即A上關係R是自反的
在全集U中所有子集的集合中,包含關係是自反的,相等關係=也是自反的;但是,真包含關係不是自反的,整數集合Z中,關係≤是自反的,而關係<不是自反的。
反自反令
徠
,若對於A中每個x,有,則稱R是反自反的,即A上關係R是反自反的。
該定義表明了,一個反自反的關係R中,不應包括有任何相同元素的有序對,由定義說明中可知真包含關係是反自反的,但包含關係不是反自反的;小於關係<是反自反的,而≤不是反自反的。
應該指出,任何一個不是自反的關係,未必是反自反的;反之,任何一個不是反自反的關係,未必是自反的,這就是說,存在既不是自反的也不是反自反的二元關係。
對稱令,對於A中每個x和y,若xRy,則yRx,稱R是對稱的,即A上關係R是對稱的
該定義表明了,在表示對稱的關係R的有序對集合中,若有有序對,則必定還會有有序對
在全集U的所有子集的集合中,相等關係是對稱的,包含關係和真包含關係都不是對稱的;在整數集合Z中,相等關係=是對稱的,而關係≤和<都不是對稱的。
反對稱令,對於A中每個x和y,若xRy且yRx,則x=y,稱R是反對稱的,即A上關係R是反對稱的
該定義表明了,在表示反對稱關係R的有序對集合中,若存在有序對,則必定是x=y,或者說,在R中若有有序對,則除非x=y,否則必定不會出現
在全集U的所有子集的集合中,相等關係=,包含關係和真包含關係都是反對稱的,但全域關係不是反對稱的.在整數集合Z中,=,≤和<也都是反對稱的。
可見,有些關係既是對稱的,又是反對稱的,如相等關係;有些關係是對稱的,但不是反對稱的,如Z中的“絕對值相等”;有些關係是反對稱的,但不是對稱的,如Z中的≤和<;還有的關係既不是對稱的,又不是反對稱的,例如,A={a,c,b}中
傳遞令,對於A中每個x,y,z,若xRy且yRx,則xRz,稱R是傳遞的,即A上關係R是傳遞的
該定義表明了,在表示可傳遞關係R的有序對集合中,若有有序對,則必有有序對
顯然,上述提到的關係中,=和≤,<,=都是傳遞的,在直線的集合中,平行關係是傳遞的,但垂直關係不是傳遞的。
通過上面幾個實例,看出:
①若A上關係R是自反的,則中主對角線上元素全為1,而中每個結點有有向環;反之亦然;
②若A上關係R是反自反的,則中主對角線上元素全為0,而中每個結點無有向環;反之亦然;
③若A上關係R是對稱的,則是對稱矩陣,而中任何兩結點若有弧,弧必成對出現;反之亦然;
④若A上關係R是反對稱的,則中主對角線元素不能同時為1,而中若兩結點間有弧,弧不能成對出現;反之亦然;
⑤若A上關係R是傳遞的,則中若,則,而中若有弧,則必有弧;反之亦然。
此外,還有:
①任何集合上的相等關係=是自反的,對稱的、反對稱的和傳遞的,但不是反自反的。
②整數集合Z中,關係≤是自反的、反對稱的和傳遞的,但不是反自反的和對稱的,關係<是反自反的、反對稱的和傳遞的,但不是自反的和對稱的。
③非空集合上的空關係是反自反的、對稱的、反對稱的和傳遞的,但不是自反的,空集合上的空關係則是自反的、反自反的、對稱的、反對稱的和傳遞的。
④非空集合上的全域關係是自反的、對稱的和傳遞的,但不是反自反的和反對稱的。
定理設,若R是反自反的和傳遞的,則R是反對稱的。