關係[數學中關係]

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

基本概念

定義

關係[數學中關係]

關係[數學中關係]

關係[數學中關係]

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