xry

離散數學反對稱關系_《離散數學》學習記錄-集合論

來源：北京?學《離散數學》公開課

2.1有序對和卡?積

有序對：有順序，類似于數組，可以?集合定義。

性質：有序對內元素對應相等

卡?積A×B：所有元素?個來?A集合，另?個來?B集合的有序對

性質：不滿?交換律，不滿?結合律，對并和交滿?分配律，具有單調性（證明見北?教材p25）

2.2?元關系

A到B的?元關系定義：A×B的任??集，即A×B冪集中的?個元素組成的集合（注意?元關系也是集合）

A到B的?元關系的總個數：|P(A×B)|

A上的特殊?元關系：空關系、恒等關系、全域關系、整除關系，?于?于關系，包含關系（只有包含關系定義在冪集P(A)上，見

p26）

定義域、值域、域（由?元關系定義的集合）

關系的特殊情況：F是單根的、F是單值的（即F定義了?個函數）

?元關系的運算：

1.逆F^-1：將關系集合中所有的有序對反向

2.逆序合成FoG：有公共中間元素的有序對的集合

3.限制F↑A：x屬于A的關系集合

4.象F[A]：F↑A的值域，定義域為A的有序對集合對應的值域

合成運算定理1：合成運算結合律（重要）

合成運算定理2：A與B合成運算的逆=B逆與A逆的合成運算

2.3關系的表?和關系的性質

關系矩陣（圖的矩陣表?）

關系圖

關系的性質

1.?反性：每個點都有環

2.反?反性：每個點都沒有環

3.對稱性：任意兩點間要么有兩條邊要么沒邊

4.反對稱性：任意兩點間都沒有兩條邊

5.傳遞性：可?捷徑（注意考慮有環的情況）

2.4關系冪運算和關系閉包

（?）關系冪

1.關系R的n次冪：R與??合成n次后得到的關系集合。也可以理解為G(R)中長度為n的路徑的起點和終點組成的有序對的集合

2.關系冪具有指數律：R^m*R^n=R^(m+n)，(R^m)^n=R^(mn)

（?）閉包

1.R的閉包的定義：包含R，滿?給定性質，最?的有序對集合（包含于任意?個）

2.閉包的種類：

?反閉包：r(R)

對稱閉包：s(R)

傳遞閉包：t(R)

3.閉包運算的性質

定理2.19：閉包運算有不動點

定理2.20：閉包運算有單調性（即較?的集合的閉包也較?）

定理2.21：閉包運算對?反閉包和對稱閉包的并有分配律，對傳遞閉包的并沒有分配率

4.閉包的集合求法：

定理2.22：?反閉包=RU恒等關系

定理2.23：對稱閉包=RUR的逆

定理2.24：傳遞閉包=RUR^2UR^3U.....（求傳遞閉包，就是把從此點可?到的點直接連起來）

5.閉包的圖求法：

?反閉包：所有定點加環

對稱閉包：所有單向邊化為雙向邊

傳遞閉包：遍歷所有點，把從此點可達到的點直接與此點連起來

6.閉包的矩陣求法：

?反閉包：主對?線全部改成1

對稱閉包：改為對稱矩陣

傳遞閉包：矩陣R邏輯或矩陣R^2邏輯或矩陣R^3........（邏輯或指：對所有運算式中的矩陣的每個對應位置上的元素進?或運算）

7.定理2.25：求閉包后關系性質是否改變

?反性在求閉包后保持不變

對稱性在求閉包后保持不變

傳遞性在求對稱閉包后可能改變（反例：a->b具有傳遞性，但它的對稱閉包為a<->b，不具有傳遞性，因為a到a要兩步才能達到）

8.定理2.26：閉包運算的交換律

求?反閉包和對稱閉包運算可交換

求?反閉包和傳遞閉包運算可交換

求對稱閉包和傳遞閉包運算不可交換，其中先求傳遞閉包再求對稱閉包得到的閉包較?

2.5等價關系和劃分

1.等價關系

定義

等價關系R是?反，對稱，傳遞的?元關系

?等價關系分類

空關系（不是等價關系）、恒等關系（是等價關系，把每個元素??分成?類）、全域關系（是等價關系，把所有元素分成?類）

2.等價類

R的等價類定義

所有與x有R關系的y的集合，記為[x]

等價類的?個例?

R為除以3后的同余關系（即x與y除以3的余數相等）

可證：除以n后的同余關系為等價關系（證：xRy等價于關系式x-y=k*n,其中k為整數。由定義易證此關系式滿??反性、對稱性，傳遞

性）

現取dom={1,2,3,4,5}

那么有等價類：

[1]=[4]={1,4}（1,4是?個等價類，余數都是1）

[2]=[5]={2,5}（2,5是?個等價類，余數都是2）

[3]={3}（3是?個等價類，余數都是0）

在G(R)上可觀察到，1,4；2,5；3分別滿?全域關系（所有的點之間連通），即每個等價類內部具有全域關系

由此性質可知，得到關系的等價類后，就可以直接推導出所有的關系

等價類的性質（定理2.27）

1.?空（由于等價關系需滿??反性，所以等價類中?少包含x??）

2.若xRy，則[x]R=[y]R（因為等價關系R滿?對稱性和傳遞性。由對稱性：y與x有關，由傳遞性：y與x有關，x與其他元素有關，則y

與所有與x有關的元素有關。反之，x與所有與y有關的元素有關，所以x與y的相關元素相同）

3.若x和y?關，則[x]R與[y]R不相交（反證法：若[x]R與[y]R有?個共同元素z，那么參考2的思路，由對稱性和傳遞性可得x和y必有

關）

4.所有等價類的并為A（結論顯?易見，嚴格證明?集族的單調性，因為每個等價類都包含于A，所以所有等價類的并包含于A的并，即

A??）

可見：等價類是對A的?個劃分（A的每個元素都只在其中?個等價類中，且等價類的并為A）

?等價關系確定等價類的基礎。?切劃分從確定?個?反、對稱、傳遞的等價關系開始。

（插?句題外話：等價類讓我想起了麥肯錫咨詢?的?個原則：MECE：MutuallyExclusiveCollectivelyExhaustive（相互獨?、完全

窮盡）。麥肯錫把這個原則視為咨詢的黃?法則，其實也就是離散數學中的劃分等價類。可見許多商業邏輯的原型都是數學。）

3.商集

定義

A/R：A上R的等價類組成的集合（就是A?R劃分的結果）

例?（對應剛剛等價類中的那個例?）

{{1,4}，{2,5}，3}

A上的等價關系有：

恒等關系

2.E全域關系

=IAU{,}（其中i不等于j，即所有點都有環，并且i和j結點有雙向邊。易證?反，對稱，傳遞）

空關系不是等價關系

對應的商集

1.A/IA={{a1},{a2},...{an}}

2.A/E={{a1,a2,...,an}}

3.A/Rij=ai和aj為?類，其他元素各成?類

例?：求A={a,b,c}的等價關系（5種）和商集（5個）

4.劃分（和商族等價）

定義：

A的?個劃分是A的?個包含于A冪集的集族，滿?：

集族中每個集合?空、集族中每個集合不相交，集族的并為A

定理2.28：

1.R為A上的等價關系->A/R是A的劃分

2.A是A的劃分->A的同塊關系（即劃分出的其中?個集合的關系）是A上的等價關系

Stirling?集數

2.6序關系

（?）偏序

1.偏序關系

R?反、反對稱（反對稱指：若xRy且yRx，則x=y）、傳遞，則稱R為偏序關系

xRy記作x≤y

2.偏序集

?個帶有偏序關系≤的集合A即為偏序集，記作

3.加細關系

劃分x包含于劃分y，則x是y的加細，xRy成?

4.可?

x≤y或y≤x，則x和y可?

5.覆蓋

x≤y且x!=y，則y覆蓋x

6.哈斯圖

具有偏序關系的兩個結點相連接，其中若y覆蓋x，則y置于x上?

哈斯圖可?于繪制組織框架圖

7.全序關系

偏序集A中任意元素之間都可?，則為全序集

等價于哈斯圖為直線

（?）擬序

1.擬序關系

R反?反、傳遞（蘊含了R是反對稱的）

2.定理2.30

擬序關系有三歧性（要么x

(xx=y

以下4組概念可以類??數中的最?值，最?值等（嚴格定義見p52）

3.最?元，最?元

4.極?元，極?元

5.上界，下界

6.上確界，下確界

7.鏈，反鏈

偏序集中兩兩都可?，就是鏈，否則是反鏈

總結：

偏序是?反，傳遞，反對稱。實數上的?于等于是偏序關系

擬序是反?反，傳遞，反對稱。實數上的?于是偏序關系

3.1函數

（?）函數的基本概念

函數F：F為?個?元關系，且F是單值的（單值：domF中每個x?多對應ranF中?個y）

偏函數：domF包含于A，ranF包含于B，即A中每個x在F上不?定有B中對應的y，嚴格定義見p58

真偏函數：在偏函數的基礎上，domF真包含于A，即A中?定有x在F上沒有有B中對應的y，嚴格定義見p58

全函數：A中每個x在F上?定有B上對應的y

（之后討論的都是全函數上的情況）

（?）函數的性質

單射：F是單根的

滿射：值域=B

雙射：x和y??對應

象和原象

特征函數

單調函數（定義在任意的偏序關系上）

?然映射

f:A->A/R（映射到等價類上）

函數的合成

反函數

4.1?然數的定義

封閉：F是函數，F(A)屬于A->F是A上的?元運算

?亞諾系統：F:M->M

1.F是單射

2.e不屬于F的值域

3.e屬于M

4.M最?

5.M在F下封閉

后繼運算：A+=AU{A}

歸納集D：集合D含有空集合，且對后繼運算封閉

?然數?集合定義：屬于每個歸納集的集合。從空集合出發，做有限次后繼運算的集合?定是?然數集（0對應空集合，1對應空集合

的后繼，以此類推）

?然數集N：包含于每個歸納集的集合。N=歸納集D的?義交

后繼函數：N->N

后繼函數是單射

定理4.1?然數集是歸納集

定理4.2為?亞諾系統

定理4.3任何?然數的元素均為它的?集

定理4.4m,n屬于?然數集，m的后繼屬于n的后繼等價于m屬于n

定理4.5任何?然數都不是??的元素

定理4.6空集屬于除0以外的任何?然數

定理4.7單歧性：m屬于n，m=n和n屬于m有且僅有?個成?

4.2?然數的性質

傳遞集：A中的任何元素也是A的元素

?然數是傳遞集

定理4.10

A是傳遞集，等價于A的?義并包含于A，等價于y屬于A，有y包含于A，等價于A包含于P(A)

定理4.11

A為傳遞集，等價于P(A)為傳遞集

定理4.12

A為傳遞集，等價于A后繼運算的?義并為A

定理4.13

每個?然數都是傳遞集

?然數集合N時傳遞集

?然數集上的?元運算

1.加法

2.乘法

5.1集合的等勢

等勢：

A與B等勢：存在f，使A->B雙射

eg.整數集和?然數集是等勢的

康托定理：

任何的集合A和它的冪集P(A)之間都不能建?雙射

有窮集：

與某個?然數等勢的集合，不能與??的真?集建?雙射的集合

?窮集

不能與?然數等勢的集合

5.2基數

集合等勢則基數card相同

對?然數集N，cardN=N(阿列夫)

cardA=Ni,則cardP(A)=Ni=1