關係(數學中關係)

關係(數學中關係)

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

基本介紹

  • 中文名:關係
  • 外文名:binary relation、relation
  • 別名:二元關係
  • 所屬學科:數學
  • 用途:反映元素之間的聯繫和性質
基本概念,定義,定義域、值域和域,關係矩陣與關係圖,關係的性質,

基本概念

定義

給定任意集合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是反對稱的。

相關詞條

熱門詞條

聯絡我們