離散數學閉包證明（離散數學-二元關係）

2023-10-19 20:49:54

離散數學閉包證明?二元關係 設S是一個非空集合,R是關於S的元素的一個條件.如果對S中任意一個有序元素對（a,b）,我們總能確定a與b是否滿足條件R,就稱R是S的一個關係（relation）.如果a與b滿足條件R,則稱a與b滿足條件R,則稱a與b有關係R,記做aRb;否則稱a與b無關係R.關係R也成為二元關係.，現在小編就來說說關於離散數學閉包證明?下面內容希望能幫助到你，我們來一起看看吧!

離散數學閉包證明

二元關係

設S是一個非空集合,R是關於S的元素的一個條件.如果對S中任意一個有序元素對（a,b）,我們總能確定a與b是否滿足條件R,就稱R是S的一個關係（relation）.如果a與b滿足條件R,則稱a與b滿足條件R,則稱a與b有關係R,記做aRb;否則稱a與b無關係R.關係R也成為二元關係.

定義：

集合 X 與集合 Y 上的二元關係是 R=(X, Y, G(R)) 當中 G(R),稱為R 的圖,是笛卡兒積 X × Y的子集.若 (x,y) ∈ G(R) 則稱 x 是 R-關係於 y 並記作 xRy 或 R(x,y).

但經常地我們把關係與其圖等價起來,即若 R ⊆ X × Y 則 R 是一個關係.

閉包

關係的閉包運算時關係上的一元運算，它把給出的關係R擴充成一新關係R』，使R』具有一定的性質，且所進行的擴充又是最「節約」的。比如自反閉包，相當於把關係R對角線上的元素全改成1，其他元素不變，這樣得到的R』是自反的，且是改動次數最少的，即是最「節約」的。

一個關係R的閉包，是指加上最小數目的有序偶而形成的具有自反性，對稱性或傳遞性的新的有序偶集，此集就是關係R的閉包。

設R是集合A上的二元關係，R的自反（對稱、傳遞）閉包是滿足以下條件的關係R'：

（i）R'是自反的（對稱的、傳遞的）；

（ii）R'⊇R；

（iii）對於A上的任何自反（對稱、傳遞）關係R"，若R"⊇R，則有R"⊇R'。

R的自反、對稱、傳遞閉包分別記為r(R）、s(R) 和t(R）。

性質1

集合A上的二元關係R的閉包運算可以複合，例如：

ts(R)=t(s(R))

表示R的對稱閉包的傳遞閉包，通常簡稱為R的對稱傳遞閉包。而tsr(R)則表示R的自反對稱傳遞閉包。

性質2

設R是集合A上的二元關係，則有

（a）如果R是自反的，那麼s(R）和t(R）也是自反的；

（b）如果R是對稱的，那麼r(R）和t(R）也是對稱的；

（c）如果R是傳遞的，那麼r(R）也是傳遞的。

性質3

設R是集合A上的二元關係，則有

（a）rs(R)=sr(R）；

（b）rt(R)=tr(R）；

（c）ts(R)⊇ st(R）。