集合和二元關(guān)系復(fù)習(xí).ppt

《集合和二元關(guān)系復(fù)習(xí).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《集合和二元關(guān)系復(fù)習(xí).ppt（67頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、C S | S W U S T XDC 溫 故 而 知 新 ! 67-1 溫故而知新 ! 2021年 3月 5日星期五 C S | S W U S T XDC 溫 故 而 知 新 ! 67-2 集合的表示法 集合是由它包含的元素完全確定的 ， 為了表示一個(gè)集合 ， 通常有： 列舉法 、 隱 式法 （ 描述法 ） 、 歸納法 、 文氏圖 等表示 方法 。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-3 2.2 集合的運(yùn)算 定義 設(shè) A、 B是兩個(gè)集合 ， 則 AB x|xA xB 仍是一個(gè)集合 ， 稱為集合 A與 B的 并集 ， 稱 “ ” 為 并運(yùn)算 （ Union

2、Operation） 。 用文氏圖表示如下： U A B C S | S W U S T XDC 溫 故 而 知 新 ! 67-4 交集 定義 設(shè) A， B是兩個(gè)集合 ， 則 AB x|xA xB 仍是一個(gè)集合 ， 稱為集合 A與 B的 交集 ， 稱 “ ” 為 交運(yùn)算 （ Intersection Operation） 。 用 文氏圖可表示如下： U A B C S | S W U S T XDC 溫 故 而 知 新 ! 67-5 差集 定義 A， B是兩個(gè)集合 ， 則 A-B x|xA xB 仍是一個(gè)集合 ， 稱為集合 A與 B的 差集 ， 稱 “ -”為 差運(yùn)算 （ Subtractio

3、n Operation)， -又 叫 相對(duì)補(bǔ)集 。 用文氏圖可表示如下： U A B C S | S W U S T XDC 溫 故 而 知 新 ! 67-6 定義 U是全集 ， A是 U的子集 ， 則 U-A x|xU并且 xA 仍是一個(gè)集合 ， 稱它為集合 A的 補(bǔ)集 ( 也可記為 ， ， AC等 ） ， “ ” 稱為 補(bǔ)運(yùn)算 （ Complement Operation） 。 用文氏圖可表示 如下： 補(bǔ)集 U A A A C S | S W U S T XDC 溫 故 而 知 新 ! 67-7 關(guān)于運(yùn)算 “ 差 ” 和 “ 補(bǔ) ” 的幾個(gè)性質(zhì) 1. ； 2. （ ） ； 3.（ ） （

4、） ； 4 （ ） ； 5 。 B C S | S W U S T XDC 溫 故 而 知 新 ! 67-8 對(duì)稱差 (環(huán)和 ) 定義：設(shè) A， B是兩個(gè)集合 ， 則 AB=x|(xA)(x B)(x B)(x A) =(A-B)(B -A) 仍是一個(gè)集合 ， 稱它為與的對(duì)稱差集 ， 稱 “ ” 為對(duì)稱差運(yùn)算 。 用文氏圖可表示如下： A B U 圖中的陰影部分為 AB。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-9 1. 等冪律： ； ； 2 交換律： ； ； 3 結(jié)合律： （ ） （ ） ； （ ） （ ） ； 4 恒等律： ； ； 5 零 律： ； ； 6 分

5、配律： （ ） （ ） （ ） ； （ ） （ ） （ ） 。 7 吸收律： A （ AB ） A； A （ AB ） =A； 8 否定律： AA 9 DeMorgan律： BABA BABA A A 10矛盾律： A = ； 11排中律： A =U ； C S | S W U S T XDC 溫 故 而 知 新 ! 67-10 冪集 定義 A的所有子集組成的集合稱為 A的 冪集 ， 記為 (A)或 2A。 (A) x|一切 xA 這種以集合為元素構(gòu)成的集合，常稱為 集合的集合 或 集族 （ Family of Set）。 對(duì)集族的研究在數(shù)學(xué)方面、知識(shí)庫和表處理語言 以及人工智能等方面都有十分

6、重要的意義。 結(jié)論 :顯然 ， 若集合有個(gè)元素 ， 則集合共 有 2n個(gè)子集 ， 即： |(A)| 2n。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-11 容斥原理 定義 所謂容斥 ， 是指我們計(jì)算某類物的數(shù)目時(shí) ， 要排斥 那些不應(yīng)包含在這個(gè)計(jì)數(shù)中的數(shù)目 ， 但同時(shí)要包容那些 被錯(cuò)誤地排斥了的數(shù)目 ， 以此補(bǔ)償 ， 這種原理稱為 容斥 原理 ， 又稱為包含 排斥原理 。 定理 設(shè) A和 B是任意有限集合 ， 有 |AB| |A| |B| |AB| 。 例 某軟件公司的程序員都熟悉 C+或 VB，其中熟 悉 C+的共 47人，熟悉 VB的共 35人， C+和 VB都

7、熟 悉的共 23人，問該公司共有多少程序員？ C S | S W U S T XDC 溫 故 而 知 新 ! 67-12 推論 設(shè) U為全集 ， A和 B是任意有限集合 ， 則 |U| (|A| |B|) |AB| 證明： = =|U-(AB)| |U| |AB| |U| (|A| |B|) |AB| 。 BA BABA 設(shè) A1,A2, ,An是任意有限集合 ， 有 : |.|)1(.|)1( |)1(|. 21 1 13 11 12 21 n n k n i n ij j n jk i j n i n ij i n i in AAAAAA AAAAAA C S | S W U S T XD

8、C 溫 故 而 知 新 ! 67-13 2.5 序偶與 笛卡爾乘積 定義 由兩個(gè)元素 x,y按照一定的次序組成的二元組 稱為 有序偶對(duì) ， 簡稱 序偶 ,記作 ,其中 ， 稱 x為 的第一元素 ， y為 的第二元素 。 例 1 平面上點(diǎn)的坐標(biāo) ， x,yR ； 中國地處亞洲 ， ,等都是 序偶 。 這 條單地址指令 也是 序偶 。 性質(zhì) （ 1） （ 當(dāng) xy 時(shí) ) （ 2） 當(dāng)且僅當(dāng) x u,y v。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-14 n重有序組 定義 由 n個(gè)元素 a1,a2,a3, ,an按照一定的次序 組成的 n元組稱為 n重有序組 ，記作

9、即： ,an。 例 2 a年 b月 c日 d時(shí) e分 f秒可用下述六重有序組來 描述： 。 性質(zhì) 當(dāng)且僅當(dāng) ai bi（ i 1,2,3, ,n） 。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-15 定義 A,B是兩個(gè)集合 ， 稱集合 A B |(x A)(y B) 為 集合 A與 B的 笛卡 兒 積 。 特別，記 A A為 A2。 笛卡兒積 B A 1 2 3 4 a b c d D C A B |(xA)(yB) C D |(xC)(yD) , , C S | S W U S T XDC 溫 故 而 知 新 ! 67-16 定義 A1,A2, ,An為 n個(gè)非空

10、集合，稱 3.1.1 關(guān)系的定義 A1 A2 An的任意子集 R為以 A1 A2 An 為基的 n元關(guān)系 。 特別： 當(dāng) R 時(shí)，則稱 R為 空關(guān)系 ； 當(dāng) R A1 A2 An時(shí)，則稱 R為 全關(guān)系 。 由于 A1 A2 An的任何子集都是一個(gè) n元 關(guān)系 ， 按照子集的定義 ， A1 A2 An共有 2|A1 A2 An| 個(gè)不同的子集 。 因此 ， 以 A1 A2 An為基的 不 同關(guān)系共有 2|A1 A2 An| 個(gè) 。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-17 定義 A， B為兩個(gè)集合， A B的任何一個(gè)子 集 R所定義的二元關(guān)系稱為 從 A到 B的

11、二元關(guān)系 ，簡稱 關(guān)系 。 如 R是從 A到 A的二元關(guān)系，則稱 R為 A上的二元關(guān)系 。 3.1.2 二元關(guān)系 由于任何 A B的子集都是一個(gè)二元關(guān)系，按照子集的 定義，知 A B共有 2|A|B| 個(gè)不同的子集。因此，從 A到 B不 同的關(guān)系共有 2|A|B| 個(gè)。 設(shè)有一序偶： R， 常把這一事實(shí)記 為 xRy， 讀作 “ x對(duì) y有關(guān)系 R”。 如 R， 則記為 xRy， 讀作 “ x對(duì) y沒有關(guān)系 R”。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-18 3.1.3 關(guān)系的表示法 1.集合表示法 由于關(guān)系也是一種特殊的集合，所以集合的 幾種基本的表示法也可以

12、用到關(guān)系的表示中。 可用枚舉法和敘述法來表示關(guān)系。 例 1) 設(shè) A 2,B 3,關(guān)系 R 2) 如定義集合 N上的 “ 小于等于 ” 關(guān)系： R |(x,yN)(xy) 。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-19 2.關(guān)系圖法 1) 設(shè) a1,a2,a3,.,an和 b1,b2,b3,.,bm分別為圖中的節(jié) 點(diǎn) ， 用 “ 。 ” 表示 ； 2) 如 R,則從 ai到 bj可用一有向邊 ai bj相連 。 為對(duì)應(yīng)圖中的有向邊 。 設(shè) A a1,a2,a3,.,an,B b1,b2,b3,.,bm， R是 從 A到 B的一個(gè)二元關(guān)系，則對(duì)應(yīng)于關(guān)系 R之關(guān)系圖

13、有如下 規(guī)定： 3) 如 R,則從 ai到 ai用一帶箭頭的小圓環(huán)表示 ai C S | S W U S T XDC 溫 故 而 知 新 ! 67-20 設(shè) A a1,a2,a3,.,an， B b1,b2,b3,.,bm， R是從 A到 B的一個(gè)二元關(guān)系 ， 稱 矩陣 MR (rij)n m為關(guān)系 R的 關(guān)系矩陣 或 鄰接矩陣 ， 其中： )m,.,3,2,1j;n,.,3,2,1i(Rb,a,0 Rb,a ,1 r ji ji ij 3.關(guān)系矩陣 顯然 ， 關(guān)系矩陣是布爾矩陣 。 注意 在寫關(guān)系矩陣時(shí)，首先應(yīng)對(duì)集合 A和 B中的元 素進(jìn)行 排序 ，不同的排序會(huì)得到不同的關(guān)系矩陣。當(dāng)集 合以

14、枚舉法表示時(shí)，如果沒有對(duì)集合的元素排序，則默 認(rèn)枚舉的次序?yàn)樵氐呐判颉?C S | S W U S T XDC 溫 故 而 知 新 ! 67-21 3.1.4 關(guān)系的性質(zhì)（ 91-93） 自反性與反自反性 定義 R是集合 A上的二元關(guān)系 ， 1) 對(duì)任意的 x A,都滿足 R， 則稱 R是 自反的 ， 或 稱 R具有 自反性 ， 即 R在 A上是自反的 (x)(xA)(R)=1 2) 對(duì)任意的 x A,都滿足 R， 則稱 R是 反自反的 ， 或稱 R具有 反自反性 ， 即 R在 A上是反自反的 (x)(xA)( R)=1 C S | S W U S T XDC 溫 故 而 知 新 ! 67-

15、22 設(shè) A=a,b,c,d， 例 1) R=,。 因?yàn)?A中每個(gè)元素 x，都有 R ，所以 R是 自反的。 R的關(guān)系圖 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 RM R的關(guān)系矩陣 C S | S W U S T XDC 溫 故 而 知 新 ! 67-23 2) S=,。 例 (續(xù) 1) S的關(guān)系圖 0 1 0 1 0 0 1 1 1 0 0 0 0 0 1 0 SM S的關(guān)系矩陣 因?yàn)?A中每個(gè)元素 x， 都有 S， 所以 S 是反自反的 。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-24 3) T=, 。 例 (續(xù) 2) 因?yàn)?A中有元素

16、 b， 使 T， 所以 T不是 自反的；因?yàn)?A中有元素 a， 使 T ， 所 以 T不是反自反的 。 T的關(guān)系圖 1 1 1 0 0 0 0 1 1 0 1 0 0 0 1 0 TM T的關(guān)系矩陣 C S | S W U S T XDC 溫 故 而 知 新 ! 67-25 1) 任何不是自反的關(guān)系未必一定是反自反的關(guān) 系 ， 反之亦然 。 即存在既不是自反的也不是 反自反的關(guān)系 。 2) 表現(xiàn)在關(guān)系圖上： 關(guān)系 R是自反的 ， 當(dāng)且僅當(dāng) 其關(guān)系圖中每個(gè)結(jié)點(diǎn)都有環(huán)；關(guān)系 R是反自反 的 ， 當(dāng)且僅當(dāng)其關(guān)系圖中每個(gè)結(jié)點(diǎn)都無環(huán) 。 3) 表現(xiàn)在關(guān)系矩陣上： 關(guān)系 R是自反的 ， 當(dāng)且僅 當(dāng)其關(guān)系矩

17、陣的主對(duì)角線上全為 1；關(guān)系 R是 反自反的當(dāng)且僅當(dāng)其關(guān)系矩陣的主對(duì)角線上 全為 0。 結(jié)論 C S | S W U S T XDC 溫 故 而 知 新 ! 67-26 對(duì)稱性與反對(duì)稱性 設(shè) R是集合 A上的二元關(guān)系 ， 1) 對(duì)任意的 x,yA ， 如果 R ， 那么 R ， 則 稱關(guān)系 R是 對(duì)稱的 ， 或稱 R具有 對(duì)稱性 ， 即 R在 A上是對(duì)稱的 (x)(y)(xA) (yA)(R)(R)=1 2) 對(duì)任意的 x,yA， 如果 R 且 R ， 那么 x=y， 則稱關(guān)系 R是 反對(duì)稱的 ， 或稱 R具有 反對(duì)稱性 ， 即 R在 A上是反對(duì)稱的 (x)(y)(xA) (yA)(R)(R)

18、(x=y)=1 C S | S W U S T XDC 溫 故 而 知 新 ! 67-27 設(shè) A=a,b,c,d， 例 1) R1=, 2) R2=, R1的關(guān)系圖 1 1 0 1 000 1 0 0 RM R1的關(guān)系矩陣 是對(duì)稱的 是反對(duì)稱的 R2的關(guān)系圖 2 1 0 1 000 000 RM R2的關(guān)系矩陣 C S | S W U S T XDC 溫 故 而 知 新 ! 67-28 3) R3=, 例 (續(xù) 1) 4) R4=, 既不是對(duì)稱的，也不是反對(duì)稱的 R3的關(guān)系圖 3 111 000 1 0 0 RM R3的關(guān)系矩陣 既是對(duì)稱的，也是反對(duì)稱的 R3的關(guān)系圖 4 1 0 0 000

19、 0 0 1 RM R3的關(guān)系矩陣 C S | S W U S T XDC 溫 故 而 知 新 ! 67-29 1) 任何不是對(duì)稱的關(guān)系未必一定是反對(duì)稱的關(guān)系 ， 反之 亦然 。 即存在既不是對(duì)稱的也不是反對(duì)稱的關(guān)系 ， 也 存在既是對(duì)稱的也是反對(duì)稱的關(guān)系 。 2) 表現(xiàn)在關(guān)系圖上： 關(guān)系 R是對(duì)稱的當(dāng)且僅當(dāng)其關(guān)系圖 中 ， 任何一對(duì)結(jié)點(diǎn)之間 ， 要么有方向相反的兩條邊 ， 要么無任何邊；關(guān)系 R是反對(duì)稱的當(dāng)且僅當(dāng)其關(guān)系圖 中 ， 任何一對(duì)結(jié)點(diǎn)之間 ， 至多有一條邊 。 3) 表現(xiàn)在關(guān)系矩陣上： 關(guān)系 R是對(duì)稱的當(dāng)且僅當(dāng)其關(guān)系 矩陣為對(duì)稱矩陣 ， 即 rij=rji， i,j=1,2, ,n；

20、關(guān)系 R 是反對(duì)稱的當(dāng)且僅當(dāng)其關(guān)系矩陣為反對(duì)稱矩陣 ， 即 rijrji=0， i,j=1,2, ,n， ij 。 結(jié)論 C S | S W U S T XDC 溫 故 而 知 新 ! 67-30 傳遞性 定義 設(shè) R是集合 A上的二元關(guān)系 ， 對(duì)任 意的 x,y,zA ， 如果 R 且 R ， 那么 R ， 則稱關(guān)系 R是 傳遞的 ， 或稱 R具有 傳遞 性 ， 即 R在 A上是傳遞的 (x)(y)(z)(xA)(yA)(zA) (R)(R)(R)=1 C S | S W U S T XDC 溫 故 而 知 新 ! 67-31 設(shè) A=a,b,c,d， 例 1) R1=, 2) R2= 是傳

21、遞的 R1的關(guān)系圖 1 1 1 1 0 0 0 1 0 0000 0000 RM R1的關(guān)系矩陣 是傳遞的 R2的關(guān)系圖 2 0 1 0 0 0000 0000 0000 RM R2的關(guān)系矩陣 C S | S W U S T XDC 溫 故 而 知 新 ! 67-32 3) R3=, 例 (續(xù) 1) 4) R4=, 不是傳遞的 R3的關(guān)系圖 3 1 1 0 0 0 0 1 0 0000 0000 RM R3的關(guān)系矩陣 不是傳遞的 R3的關(guān)系圖 4 0 1 1 0 0 0 1 0 0 0 0 1 0000 RM R3的關(guān)系矩陣 C S | S W U S T XDC 溫 故 而 知 新 ! 67

22、-33 1) 表現(xiàn)在關(guān)系圖上： 關(guān)系 R是傳遞的當(dāng)且僅當(dāng)其 關(guān)系圖中 ， 任何三個(gè)結(jié)點(diǎn) x,y,z（ 可以相同 ） 之間 ， 若從 x到 y有一條邊存在 ， 從 y到 z有一 條邊存在 ， 則從 x到 z一定有一條邊存在 。 2) 表現(xiàn)在關(guān)系矩陣上： 關(guān)系 R是傳遞的當(dāng)且僅當(dāng) 其關(guān)系矩陣中 ， 對(duì)任意 i,j,k1,2,3, ,n， 若 rij=1且 rjk=1， 必有 rik=1。 結(jié)論 C S | S W U S T XDC 溫 故 而 知 新 ! 67-34 設(shè) A是任意的集合 ， 1) A上的全關(guān)系 A A是自反的 、 對(duì)稱的 、 傳遞的 關(guān)系； 2) A上的空關(guān)系 是反自反的 、 反

23、對(duì)稱的 、 對(duì)稱 的 、 傳遞的關(guān)系； 3) A上的恒等關(guān)系 IA是自反的 、 對(duì)稱的 、 反對(duì)稱 的 、 傳遞的關(guān)系 。 例 例 1) 朋友關(guān)系是自反的、對(duì)稱的、而非傳遞的關(guān)系； 2) 父子關(guān)系是反自反的、反對(duì)稱的、而非傳遞的關(guān) 系 . C S | S W U S T XDC 溫 故 而 知 新 ! 67-35 1) 在整數(shù)集 I上定義的 “小于等于 ” 關(guān)系是自反的 、 反對(duì)稱的 、 傳遞的關(guān)系； “小于 ” 關(guān)系是反自反的 、 反對(duì)稱的 、 傳遞的關(guān)系； “等于 ” 關(guān)系是自反的 、 反對(duì)稱的 、 對(duì)稱的 、 傳遞的關(guān)系 。 例 例 8.21 設(shè) A 1,2,3,4， R ,， ， 是

24、A上的關(guān)系 。 2) 冪集上的 “包含 ” 關(guān)系是自反的 、 反對(duì)稱的 、 傳遞的關(guān)系； “真包含 ” 關(guān)系是反自反的 、 反對(duì)稱的 、 傳遞的關(guān)系； “相等 ” 關(guān)系是自反的 、 反對(duì)稱的 、 對(duì)稱的 、 傳遞的關(guān)系 。 則 R既 不是自反的，又非反自反的；即不是對(duì)稱的，也非 反對(duì)稱的；也不是傳遞的。即不具備關(guān)系的任何性質(zhì)。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-36 關(guān)系性質(zhì)的邏輯表示 設(shè) R是集合 A上的二元關(guān)系 ， 1) R是自反的 )Rx,x()Ax)(x( 是永真的 2) R不 是自反的 )Rx,x()Ax)(x( 是永真的 3) R是 反 自反的

25、)Rx,x()Ax)(x( 是永真的 4) R不 是 反 自反的 )Rx,x()Ax)(x( 是永真的 5) R是 對(duì)稱 的 )Rx,y()Ry,x)(y)(x( 是永真的 6) R不 是 對(duì)稱 的 )Rx,y()Ry,x)(y)(x( 是永真的 C S | S W U S T XDC 溫 故 而 知 新 ! 67-37 關(guān)系性質(zhì)的邏輯表示 (續(xù) ) 7) R是 反 對(duì)稱 的 9) R是 傳遞 的 )Rz,x()Rz,y()Ry,x)(z)(y)(x( 是永真的 10)R不 是 傳遞 的 )Rz,x()Rz,y()Ry,x)(z)(y)(x( 是永真的 )Rx,y()Ry,x()yx)(y)(

26、x( )yx()Rx,y()Ry,x)(y)(x( 是永真的 8) R不 是 反 對(duì)稱 的 )Rx,y()Ry,x()yx)(y)(x( 是永真的 C S | S W U S T XDC 溫 故 而 知 新 ! 67-38 設(shè) R， S都是集合 A到 B的兩個(gè)關(guān)系 ， 則： RS |(xRy)(xSy) RS |(xRy)(xSy) R-S |(xRy)(xS y) |(x y) R 3.2 關(guān)系的運(yùn)算 R RR R 關(guān)系的交、并、補(bǔ)、差運(yùn)算（補(bǔ)充） 根據(jù)定義 ， 由于 A B是相對(duì)于 R的全集 ， 所以 A B-R,且 R A B, R 。 C S | S W U S T XDC 溫 故 而

27、 知 新 ! 67-39 定義 設(shè) R是一個(gè)從集合 A到集合 B的二元 關(guān)系 ， 則從 B到 A的關(guān)系 R-1 | R稱 為 R的 逆關(guān)系 ,運(yùn)算 “ -1” 稱為 逆運(yùn)算 。 關(guān)系的 逆 運(yùn)算 P101 注意：關(guān)系是一種集合，逆關(guān)系也是一種集 合，因此，如果 R是一個(gè)關(guān)系，則 R-1和 都是關(guān) 系，但 R-1和 是完全不同的兩種關(guān)系，千萬不要 混淆。 R R C S | S W U S T XDC 溫 故 而 知 新 ! 67-40 關(guān)系 的 合成運(yùn)算 P96 設(shè) R 是一個(gè)從集合 A 到集合 B 的二元關(guān) 系 ， S是從集合 B到集合 C的二元關(guān)系 (也可 簡單地描述為 R： AB ， S

28、： BC) ， 則 R與 S的 合成關(guān)系 （ 合成關(guān)系 ） RS是從 A到 C的關(guān)系 ， 并 且： RS |(xA)(zC) (y)(yB)(xRy)(ySz) 運(yùn)算 “ ” 稱為 合成運(yùn)算 。 注意，在合成關(guān)系中， R的后域 B一定是 S的 前域 B，否則 R和 S是不可合成的。合成的結(jié)果 RS 的前域就是 R的前域 A，后域就是 S的后域 C。如果 對(duì)任意的 xA 和 zC ，不存在 yB ，使得 xRy和 ySz同時(shí)成立，則 RS為空，否則為非空。并且， R=R=。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-41 R S R。 S A B C A C 1。 。

29、 1 。 1 1。 。 1 2。 。 2 。 2 2。 。 2 3。 。 3 。 3 3。 。 3 4。 。 4 。 4 4。 。 4 2).用關(guān)系圖 求 RS。 例 R ,， S ,， 3).用關(guān)系矩陣求 RS。 P99 0000 1000 0010 0010 MRS MR.MS 0000 0010 0100 0100 0010 0001 0100 0000 C S | S W U S T XDC 溫 故 而 知 新 ! 67-42 設(shè) I是整數(shù)集合 ， R， S是 I到 I的兩個(gè)關(guān)系： R |x I； S |x I。 則： RS SR RR SS (RR)R (RS)R 例 |x I |x

30、 I |x I |x I |x I |x I C S | S W U S T XDC 溫 故 而 知 新 ! 67-43 設(shè) R是從集合 A到集合 B的關(guān)系 ， S1,S2是從集合 B到集 合 C的關(guān)系 ， T是從集合 C到集合 D的關(guān)系 ， 則： 1) R(S1S 2) (RS1)(R S2) 2) R(S1S 2)(RS1)(R S2) 3) (S1S 2)T (S1T)(S 2T) 4) (S1S 2)T(S1T)(S 2T) 定理 3.2.1 P97 證明 4) 對(duì)任意 (S1S 2)T， 則由合成運(yùn)算知 ， 至少存在 c C,使得： (S1S 2)， T。 即： S1,且 S2。 因

31、此 ， 由 S1,且 T， 則有： (S1T), 由 S2,且 T， 則有： ( S2T)。 所以 ， (S1T)(S 2T)。 即 ， (S1S 2)T(S1T)(S 2T)。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-44 設(shè) R,S,T分別是從集合 A到集合 B， 集合 B到 集合 C， 集合 C到集合 D的二元關(guān)系 ， 則 1)(RS)T R(ST) 2)(RS)-1 S-1R-1 (補(bǔ)充 ) 定理 3.2.7 證明 1)設(shè) (RS)T， cC, 使得： R S， T。 則由合成運(yùn)算知 ,至少存在 R(ST), 又對(duì)于 RS， 則至少存一個(gè) bB ， 使得

32、R， S。 因此 ,由 S, T,有 ST， 又由 R和 ST， 知： 所以 (RS)TR(ST)。 同理可證： R(ST)(RS)T。 由集合性質(zhì)知： (RS)T R(ST)。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-45 2).任取 (RS)-1， 則 RS 由 “ ” 的定義知：則至少存一個(gè) bB, 使得： R， S， 即： R-1, S-1。 由 S-1和 R-1,有： S-1R-1， 所以 ， (RS)-1S-1R-1。 反之 ， 任取 S-1R-1， 由 “ ” 的定義知：則至少 存一個(gè) bB, 使得： S-1和 R-1， 所以： R， S。 由 “

33、” 知： RS。 即有： (RS)-1。 所以 ， S-1R-1(RS)-1。 由集合的定義知： (RS)-1 S-1R-1。 定理 (續(xù) ) 2)(RS)-1 S-1R-1 C S | S W U S T XDC 溫 故 而 知 新 ! 67-46 定義 設(shè) R是集合 A上的二元關(guān)系 ， 則可 定義 R的 n次冪 Rn,該 Rn也是 A上的二元關(guān)系 ， 定義 如下： 1.R0 IA |a A； 2.R1 ； 3.Rn+1 RnR RRn。 關(guān)系的 冪 P98 顯然， RmRn Rm+n,(Rm)n Rmn。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-47 定義 設(shè)

34、 R是定義在 A上的二元關(guān)系 ， 若存在 R的一 個(gè)擴(kuò)充 ExtR滿足： 1) ExtR是 自反的 (或 對(duì)稱的 、 或 傳遞的 )。 2) 對(duì)任何的擴(kuò)充 Ext*R， 若 Ext*R是 自反的 (對(duì)稱 的 、 或 傳遞的 )， 則： ExtRExt*R。 此時(shí)稱 ExtR為 R的 自反閉包關(guān)系 (或 對(duì)稱閉包關(guān) 系 、 或 傳遞閉包關(guān)系 )， 分別記為 r(R)(s(R)或 t(R)。 關(guān)系的閉包 C S | S W U S T XDC 溫 故 而 知 新 ! 67-48 1) 求一個(gè)關(guān)系的自反閉包，即將圖中的所有無環(huán)的節(jié)點(diǎn) 加上環(huán)；關(guān)系矩陣中對(duì)角線上的值 rij 全變?yōu)?“ 1”。 2)

35、求一個(gè)關(guān)系的對(duì)稱閉包，則在圖中，任何一對(duì)節(jié)點(diǎn)之 間，若僅存在一條邊，則加一條方向相反的另一條邊； 關(guān)系矩陣中則為：若有 rij 1(ij) ，則令 rji 1(若 rji1), 即 Ms(R) MRM R-1。 3) 求一個(gè)關(guān)系的傳遞閉包，則在圖中，對(duì)任意節(jié)點(diǎn) a,b,c, 若 a到 b有一條邊，同時(shí) b到 c也有一條邊，則從 a到 c必 增加一條邊 (當(dāng) a到 c無邊時(shí) )；在關(guān)系矩陣中，若 rij 1， rjk 1,則令 rik 1( rik1) 。 利用關(guān)系圖和關(guān)系矩陣 求閉包 C S | S W U S T XDC 溫 故 而 知 新 ! 67-49 設(shè) R是集合 A上的二元關(guān)系 ，

36、則： 1) r(R) RI A。 2) s(R) RR -1。 3) t(R) ， 若 |A| n， 則 t(R) 。 Ri1i Rin1i 定理 C S | S W U S T XDC 溫 故 而 知 新 ! 67-50 設(shè) P P1,P2,P3,P4是四個(gè)程序， R,S是定義在 P上的 調(diào)用關(guān)系如下： R , S , 求 r(R),s(R),t(R)， r(S),s(S),t(S)。 例 解： r(R) RI A , , , ,。 ,。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-51 例 (續(xù) 1) s(R) RR -1 , , , , t(R) RR 2R 3

37、R 4 , ,。 r(S) SI A , , , ,。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-52 s(S) SS -1 , , , 例 (續(xù) 2) t(S) SS 2S 3S 4 , , , ,) , ,。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-53 定義 1） 集合 A上的關(guān)系的 自反對(duì)稱閉包 rs(R) r(s(R) 2） 集合 A上的關(guān)系的 自反傳遞閉包 定義為 rt(R) r(t(R) 3） 集合 A上的關(guān)系的 對(duì)稱傳遞閉包 定義為 st(R) s(t(R) 同上 ， 我們還可定義 sr(R),tr(R),ts(R),

38、多重閉包 定理 設(shè) R是集合 A上的關(guān)系，則： 1)rs(R) sr(R) 2)rt(R) tr(R) 3)st(R)ts(R) C S | S W U S T XDC 溫 故 而 知 新 ! 67-54 設(shè) A 1,2,R ,則： 例 傳遞閉包和自反傳遞閉包，常用于形式語言 與程序設(shè)計(jì)中，在計(jì)算機(jī)文獻(xiàn)中，常把關(guān)系 R的 傳遞閉包 t(R)記作 R+，而自反傳遞閉包 rt(R)記作 R*。顯然有 (R+)+=R+。 st(R) s(t(R) s() , ts(R) t(s(R) t(,) , 即： st(R)ts(R) C S | S W U S T XDC 溫 故 而 知 新 ! 67-55

39、 3.4 次序關(guān)系 次序關(guān)系的定義 定義 設(shè) R是集合 A上的自反的、反對(duì)稱的、傳遞的關(guān)系， 則稱 R是 A上的 偏序關(guān)系 (記為 “ ” )。 序偶 稱 為 偏序集 。 2) 設(shè) R是集合 A上的反自反的、反對(duì)稱的、傳遞的關(guān)系， 則稱 R是 A上的 擬序關(guān)系 (記為 “ ” )。序偶 稱 為 擬序集 。 為使敘述簡潔，我們常將 ab 并且 ab記為 a b。 容易證明：偏序 的逆關(guān)系 -1也是一個(gè)偏序，我們 用 “ ” 表示，讀作 “ 大于等于 ” ；擬序的逆關(guān)系 -1 也是一個(gè)擬序，我們用 “ ” 表示，讀作 “ 大于 ” 。 C S | S W U S T XDC 溫 故 而 知 新 !

40、 67-56 1) 集合 A的冪集 (A)上定義的“ ” 和“ ”分別是 偏 序 關(guān)系和擬序關(guān)系。 是偏序集， 是擬 序集 。 例 2) 實(shí)數(shù)集合 R上定義的 “ ” 和 “ ” 分別是偏序關(guān)系 和擬序關(guān)系。 是偏序集， 是擬序集。 3) 大于零的 自然數(shù)集合 N 上定義的 “ 整除 ” 關(guān)系 “ ” 也是一個(gè)偏序關(guān)系 , 是偏序集。 4) ALGOL或 PL/I等都是塊結(jié)構(gòu)語言，設(shè)： B b1,b2,b3, ,bn 是這種語言的一個(gè)程序中的塊的集合。對(duì)所有 i和 j， 定義關(guān)系 “ ” 如下： bib j當(dāng)且僅當(dāng) bi被 bj所包含。 則 “ ” 也是一個(gè)偏序關(guān)系 , 是偏序集。 C S |

41、 S W U S T XDC 溫 故 而 知 新 ! 67-57 定義 設(shè) 是一個(gè)偏序集，對(duì)任意 x,yA，如果 xy或 yx，則稱 x與 y是 可比的 。若 x與 y是可比的， x y，并且 不存在 z A，使得 x z y，則稱 y覆蓋 x。 可比與覆蓋 例 1） 集合 A=a,b,c， 偏序集 中 ， a與 a,b 是可比的 ， a與 b,c不是可比的； a,b覆蓋 a， 但 a,b,c不覆蓋 a。 2) 偏序集 中 ， 對(duì)任意 x,yA ， x與 y都是可比的 ， 但是 ， x不覆蓋 y， y也不覆蓋 x。 3) 偏序集 中 ， 對(duì)任意 x,yA ， x與 y都是可比的 ， 但是 ，

42、x覆蓋 x-1。 Z:所有的整數(shù) 4) 偏序集 中 ， 2與 3不是可比的； 2與 6是可比的 ， 并 且 6覆蓋 2； 2與 8是可比的 ， 但 8不覆蓋 2；對(duì)任意 nN +， 0與 n是可比的 ， 但 0不覆蓋 n。 N:自然數(shù)的全體 C S | S W U S T XDC 溫 故 而 知 新 ! 67-58 偏序集的哈斯圖 1) 用小圓圈或點(diǎn)表示 A中的元素，省掉關(guān)系圖中所有的 環(huán)。 (因自反性 ) 2) 對(duì)任意 x,y A，若 x y，則將 x畫在 y的下方，可省掉 關(guān)系圖中所有邊的箭頭。 (因反對(duì)稱性 ) 3) 對(duì)任意 x,y A，若 y覆蓋 x，則 x與 y之間用一條線相連 之，

43、否則無線相連。 (因傳遞性 ) 按 1),2),3)所作成的圖稱為 哈斯圖 (Hasse圖 )。 關(guān)系圖 2 3 6 12 36 24 C S | S W U S T XDC 溫 故 而 知 新 ! 67-59 例 設(shè) A 2,3,6,12,24,36,“ ”是 A上的整除關(guān)系，畫出 其一般的關(guān)系圖和哈斯圖。 哈斯圖 2 3 6 12 36 24 關(guān)系圖 2 3 6 12 36 24 C S | S W U S T XDC 溫 故 而 知 新 ! 67-60 例 設(shè)集合 A a， B a,b， C a,b,c， D a,b,c,d。 分別畫出集合 A、 B、 C、 D之 冪集 P(A)、 P(

44、B)、 P(C)、 P(D)上定義的 “ ” 的哈斯 圖。 a a b a,b a b c a,b a,c b,c a,b,c a b c d a,b a,c b,c a,d b,d c,d a,b,c a,b,d a,c,d b,c,d a,b,c,d C S | S W U S T XDC 溫 故 而 知 新 ! 67-61 偏序集中的特殊元素 定義 是偏序集， B是 A的任何一個(gè)子集。 1) 若存在元素 bB ,使得 對(duì)任意 xB, 都有 xb ,則稱 b為 B的 最大元 素 ，簡稱 最大元 。 2) 若存在元素 bB ,使得 對(duì)任意 xB, 都有 bx ,則稱 b為 B的 最小元 素

45、，簡稱 最小元 。 3) 若存在元素 bB ,使得 對(duì)任意 xB, 滿足 bx x b,則稱 b為 B的 極大元素 ，簡稱 極大元 。 4) 若存在元素 bB ,使得 對(duì)任意 xB, 滿足 xb x b,則稱 b為 B的 極小元素 ，簡稱 極小元 。 5) 若存在元素 aA ,使得 對(duì)任意 xB, 都有 xa ,則稱 a為 B的 上界 。 6) 若存在元素 aA ,使得 對(duì)任意 xB, 都有 ax ,則稱 a為 B的 下界 。 7) 若元素 a A是 B的上界 ,元素 aA 是 B的任何一個(gè)上界 ,若均有 a a,則稱 a為 B的 最小 上界 或 上確界 ,記 a SupB。 或 lub 8)

46、 若元素 aA 是 B的下界 ,元素 aA 是 B的任何一個(gè)下界 ,若均有 aa ,則稱 a為 B的 最 大下界 或 下確界 ,記 a InfB?；?glb C S | S W U S T XDC 溫 故 而 知 新 ! 67-62 設(shè) 是一偏序集， B是 A的子集。則： 1. 若 b B是 B的最大元 b是 B的極大元、上界、最小上 界； 2. 若 b B是 B的最小元 b是 B的極小元、下界、最大下 界； 3. 若 a A是 B的最小上界，且 a Ba是 B的最大元； 4. 若 a A是 B的最大下界，且 a Ba是 B的最小元； 5. 若 B存在最大元，則 B的最大元是惟一的； 6. 若

47、 B存在最小元，則 B的最小元是惟一的； 7. 若 b B是 B的極大元，且 b是唯一的 b是 B的最大元； 8. 若 b B是 B的極小元，且 b是唯一的 b是 B的最小元； 9. 若 B存在最小上界，則 B的最小上界是惟一的； 10. 若 B存在最大下界，則 B的最大下界是惟一的。 定理 C S | S W U S T XDC 溫 故 而 知 新 ! 67-63 集合的劃分 P120 設(shè) A是一個(gè)集合 ， A1,A2,A3.Am是 A的任何 m個(gè)子集 ， 如果 A1,A2,A3.Am滿足： 1) 對(duì)一切的 ij(i,j 1,2,3,.,m)， 都有 AiAj 。 2) 。 則稱集合 (A)

48、 A1,A2,A3,.,Am 為集合 A的 一個(gè) 劃分 ,而 A1,A2,A3,.Am叫做這個(gè)劃分的 塊 。 AA i m 1i C S | S W U S T XDC 溫 故 而 知 新 ! 67-64 例 上述劃分用文氏圖可表示如下： 對(duì)任何一個(gè)集合，我們要對(duì)集合中的元素進(jìn)行劃分， 那么，按照 “ 怎樣 ” 的方式才能得到 “ 正確 ” 的劃分呢？ 通常，不嚴(yán)格的 “ 分類 ” 是要鬧出笑話的。 下面，我們將會(huì)看到集合中的元素如果按照 “ 等價(jià) 關(guān)系 ” 進(jìn)行 “ 分類 ” 時(shí)，就可得到正確的劃分。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-65 等價(jià)關(guān)系 定義

49、 R是定義在集合 A上的關(guān)系，如果 R是 自反的、對(duì) 稱的、傳遞的 ，則稱此關(guān)系 R為 A上的 等價(jià)關(guān)系 。 例 3.4.1 1） 在全體中國人所組成的集合上定義的 “ 同姓 ” 關(guān)系 ， 就是具備自反的 、 對(duì)稱的 、 傳遞的性質(zhì) ， 因此 ， 就是一個(gè)等價(jià)關(guān)系； 2) 對(duì)任何集合 A,考慮 R A A,則 R是 A上的等價(jià)關(guān)系； 3) 三角形的 “ 相似關(guān)系 ” 、 “ 全等關(guān)系 ” 等都是等價(jià)關(guān) 系； 4) 直線的 “ 平行關(guān)系 ” 不是等價(jià)關(guān)系 ， 因?yàn)樗鼈儾皇亲?反的 。 5) 冪集上定義的 “ ” ， 整數(shù)集上定義的 “ ” 都不是 等價(jià)關(guān)系 ， 因?yàn)樗鼈儾皇菍?duì)稱的 。 6) “

50、朋友 ” 關(guān)系 ， 則不是等價(jià)關(guān)系 ， 因它不是傳遞的 。 C S | S W U S T XDC 溫 故 而 知 新 ! 67-66 以 m為模的同余關(guān)系 R稱為 Z上 以 m為模的同余關(guān)系 ， 一般記 xRy為 x y(mod m) 稱為 同余式 。 如用 resm(x)表示 x除以 m的余數(shù) ， 則 x y(mod m) resm(x) resm(y)。 此時(shí) ， R將 Z分成了如下 m個(gè)子集： ,-3m,-2m,-m,0,m,2m,3m, ,-3m+1,-2m+1,-m+1,1,m+1,2m+1,3m+1, , -3m+2,-2m+2,-m+2,2,m+2,2m+2,3m+2, ,-2m-1,-m-1,-1,m-1,2m-1,3m-1,4m-1, C S | S W U S T XDC 溫 故 而 知 新 ! 67-67 以 m為模的同余關(guān)系 這 m個(gè) Z的子集具有的 特點(diǎn) ：在同一個(gè)子集中的元素 之間都有關(guān)系 R，而不同子集的元素之間無關(guān)系 R。也就 是說，通過等價(jià)關(guān)系，將集合分成若干子集，使這些子集 構(gòu)成的集合就是 Z的一個(gè)劃分。 例如我們常見的時(shí)鐘上的時(shí)針重復(fù)關(guān)系即為 m=12， A=0,1,2,3, ,23，此等價(jià)關(guān)系 R的關(guān)系圖如下圖所示 ， A被分成了 12個(gè)子集 0,12、 1,13、 2,14、 、 11,23。