集合劃分覆蓋等價(jià)及序關(guān)系

集合劃分覆蓋等價(jià)及序關(guān)系第一頁，共四十五頁，編輯于2023年，星期二例:判斷以下集合是否為集合A的覆蓋？其中A={a,b,c,d,e,f}（1）S1={,{a,b},{c,d},{f}}（2）S2={{a,b},{c,d},{f,g}}（3）S3={{a,b},{c,d},{f}}（4）S4={{a,b},{c,d,e},{e,f}}不是不是不是是第二頁，共四十五頁，編輯于2023年，星期二定義3-9.2[劃分partition]：給定集合A的一個(gè)覆蓋S，若A中的每個(gè)元素屬于且僅屬于S的一個(gè)分塊，則S稱作是A的一個(gè)劃分。即：若S是集合A的覆蓋，且滿足Si∩Sj=，（這里i≠j），則稱S是A的劃分。第三頁，共四十五頁，編輯于2023年，星期二是例:判斷以下集合是否為集合A的劃分？其中A={a,b,c,d,e,f}（1）S1={,{a,b,c,d},{f}}（2）S4={{a,b},{c,d,e},{e,f}}（3）S5={{a,b},{c,d},{e,f}}（4）S6={{a},,{c},0m2xc4m,{e},{f}}（5）S7={{a,b,c,d,e,f}}我們看到對于一個(gè)給定集合,劃分不唯一不是不是是是最大劃分最小劃分第四頁，共四十五頁，編輯于2023年，星期二定義3-9.3[交叉劃分]：若{A1,A2,…,Ar}與{B1,B2,…,Bs}是同一集合A的兩種劃分，則其中所有Ai∩Bj組成的非空集合，稱為原來兩種劃分的交叉劃分。定義3-9.4[加細(xì)]：給定X集合的任意兩個(gè)劃分{A1,A2,…,Ar}和{B1,B2,…,Bs}，若對于每一個(gè)Aj，均有Bk使Aj

Bk，則稱{A1,A2,…,Ar}為{B1,B2,…,Bs}的加細(xì)。第五頁，共四十五頁，編輯于2023年，星期二定理3-9.1:設(shè){A1,A2,…,Ar}與{B1,B2,…,Bs}是同一集合X的兩種劃分，則其交叉劃分仍是原集合的一種劃分。證明見書129頁。第六頁，共四十五頁，編輯于2023年，星期二定理3-9.2:

任何兩種劃分的交叉劃分，都是原來各劃分的一種加細(xì)。證明見書130頁。第七頁，共四十五頁，編輯于2023年，星期二3-10等價(jià)關(guān)系與等價(jià)類3-10.1等價(jià)關(guān)系定義3-10.1[等價(jià)關(guān)系EquivalenceRelations]：設(shè)A，RAA，若R是自反的、對稱的和傳遞的，則稱R為A上的等價(jià)關(guān)系。例如平面上三角形集合中，三角形的全等關(guān)系、相似關(guān)系是等價(jià)關(guān)系。一個(gè)班級中，同學(xué)之間的同姓關(guān)系也是等價(jià)關(guān)系例1:見書131頁例題2（驗(yàn)證一個(gè)等價(jià)關(guān)系）第八頁，共四十五頁，編輯于2023年，星期二3-10.2等價(jià)類定義3-10.2[等價(jià)類Equivalenceclasses]：設(shè)R是非空集合A上的等價(jià)關(guān)系，對任意的aA，定義

[a]R={xA|aRx}，稱為a關(guān)于R的等價(jià)類，簡稱a的等價(jià)類，在不混淆的情況下記為[a]。顯然[a]R非空，因?yàn)閍

[a]R

第九頁，共四十五頁，編輯于2023年，星期二定理3-10.1

設(shè)R是非空集合A上的等價(jià)關(guān)系，對于任意a,bA，有aRbiff[a]R=[b]R。證明：假設(shè)[a]R=[b]R，因?yàn)閍[a]R

，故a[b]R，即aRb。若aRb，設(shè)c[a]RaRccRacRb

c[b]R，即[a]R[b]R同理，若c[b]RbRccRbcRac[a]R，即[a]R[b]R由此證得若aRb，則[a]R=[b]R第十頁，共四十五頁，編輯于2023年，星期二定義3-10.3[商集]：設(shè)R是非空集合A上的等價(jià)關(guān)系，關(guān)于R的全體不同的等價(jià)類為元素的集合

{[a]R|aA}稱為A關(guān)于R的商集，記為A/R。例2：仍以書131頁例題2為例（給出一個(gè)集合和等價(jià)關(guān)系，求商集）。第十一頁，共四十五頁，編輯于2023年，星期二定理3-10.2：非空集合A上的等價(jià)關(guān)系R，決定了A的一個(gè)劃分，該劃分就是商集A/R。定理的證明見書133頁上，在此省略。第十二頁，共四十五頁，編輯于2023年，星期二定理3-10.3：集合A的一個(gè)劃分確定A的元素間的一個(gè)等價(jià)關(guān)系。定理的證明見書133頁下，在此省略。例：包含三個(gè)元素的集合，可以有多少種不同的劃分，就有多少種等價(jià)關(guān)系。5種?？碢134例題4第十三頁，共四十五頁，編輯于2023年，星期二定理3-10.4：設(shè)R1和R2為非空集合A上的等價(jià)關(guān)系，則R1=R2當(dāng)且僅當(dāng)A/R1=A/R2。定理的證明見書134頁中，在此省略。第十四頁，共四十五頁，編輯于2023年，星期二本次課小結(jié)及要求小結(jié)：

1.集合的劃分和覆蓋的概念

2.等價(jià)關(guān)系的概念及等價(jià)關(guān)系與劃分一一對應(yīng)要求：

1.掌握集合的劃分和覆蓋的概念

2.掌握等價(jià)關(guān)系的概念，會判斷一個(gè)關(guān)系是否是等價(jià)關(guān)系，記住幾個(gè)實(shí)例。

3.掌握等價(jià)關(guān)系與劃分一一對應(yīng)，給定劃分會求等價(jià)關(guān)系；給定等價(jià)關(guān)系會求劃分。第十五頁，共四十五頁，編輯于2023年，星期二作業(yè)（3-10）P134(3)(7)(5)選作第十六頁，共四十五頁，編輯于2023年，星期二3-11相容關(guān)系定義3-11.1[相容關(guān)系]：給定集合A上的關(guān)系r，若r是自反的，對稱的，則稱r是相容關(guān)系。我們可以知道，相容關(guān)系的關(guān)系矩陣的對角線元素都為1，且是對稱矩陣，為此，可以將矩陣用梯形表示。關(guān)系圖上，每個(gè)結(jié)點(diǎn)都有自回路，且相關(guān)結(jié)點(diǎn)間的有向邊成對出現(xiàn)，可以把圖形簡化為：不畫自回路，并用單線（無向邊）代替雙向有向邊。第十七頁，共四十五頁，編輯于2023年，星期二例1：設(shè)X={216，2234，379，648，545}，R是X中的二元關(guān)系。R={<x,y>|xX，yX，x和y有相同的數(shù)字}，試說明R是一個(gè)相容關(guān)系，并寫出R的關(guān)系矩陣，畫出關(guān)系圖。解：令X中的元素分別為x1~x5，則R={<x1,x1>,<x1,x2>,<x1,x4>,<x2,x1>,<x2,x2>,<x2,x3>,<x2,x4>,<x2,x5>,<x3,x2>,<x3,x3>,<x4,x1>,<x4,x2>,<x4,x4>,<x4,x5>,<x5,x2>,<x5,x4>,<x5,x5>第十八頁，共四十五頁，編輯于2023年，星期二關(guān)系矩陣如下：

1101011111MR=011001101101011轉(zhuǎn)化后如下：X21X301X4110X50101x1x2x3x4x5x4x1x2x3第十九頁，共四十五頁，編輯于2023年，星期二定義3-11.2[相容類]:

設(shè)r是集合A上的相容關(guān)系，若CA，如果對于C中任意兩個(gè)元素a1，a2有a1ra2，稱C是由相容關(guān)系r產(chǎn)生的相容類。上例中的相容類有：{x1,x2},{x1,x4},{x2,x4},{x2,x4,x5},{x2,x3}等。第二十頁，共四十五頁，編輯于2023年，星期二定義3-11.3[最大相容類]：設(shè)r是集合A上的相容關(guān)系，不能真包含在任何其它相容類中的相容類，稱作最大相容類。記作Cr。在相容關(guān)系圖中，最大完全多邊形的頂點(diǎn)集合，就是最大相容類。此外，一個(gè)孤立結(jié)點(diǎn)，以及不是完全多邊形的兩個(gè)結(jié)點(diǎn)的連線，也是最大相容類。例2：見P137例1。第二十一頁，共四十五頁，編輯于2023年，星期二定理3-11.1：設(shè)r是有限集合A上的相容關(guān)系，C是一個(gè)相容類，那么必存在一個(gè)最大相容類Cr，使得CCr。定義3-11.4[A的完全覆蓋]：在集合A上給定相容關(guān)系r，其最大相容類的集合稱作A的完全覆蓋，記作Cr(A).例1中X的完全覆蓋是

{{x1,x2,x4},{x2,x4,x5},{x2,x3}}第二十二頁，共四十五頁，編輯于2023年，星期二已知集合的覆蓋，求相容關(guān)系定理3-11.2：給定集合A的覆蓋{A1，A2，An}，由它確定的關(guān)系R=A1A1

A2

A2

…

An

An

是相容關(guān)系。定理3-11.3：集合A上的相容關(guān)系r與完全覆蓋Cr(A)存在一一對應(yīng)。第二十三頁，共四十五頁，編輯于2023年，星期二作業(yè)（3-11）P139(2)第二十四頁，共四十五頁，編輯于2023年，星期二3-12序關(guān)系在這一節(jié)中，我們將介紹以下一些序關(guān)系：偏序關(guān)系全序關(guān)系良序關(guān)系擬序關(guān)系*第二十五頁，共四十五頁，編輯于2023年，星期二3-12序關(guān)系在一個(gè)集合上，我們常常要考慮使得元素具有一定的次序的關(guān)系，其中很重要的一類關(guān)系稱作偏序關(guān)系。下面給出一些偏序關(guān)系的例子：實(shí)數(shù)集上的小于等于（或大于等于）關(guān)系。冪集合中的集合之間的包含關(guān)系。整數(shù)集合上的整除關(guān)系。一個(gè)單位里，部門之間的責(zé)任關(guān)系。若將命題演算中所有合式公式都以主析?。ɑ蛑骱先。┓妒奖硎?，那么可建立全體合式公式上的蘊(yùn)含關(guān)系。第二十六頁，共四十五頁，編輯于2023年，星期二3-12.1偏序關(guān)系定義3-12.1[偏序關(guān)系](partialorder):

設(shè)A，RAA，若R是自反的、反對稱的和傳遞的，則稱R是A上的偏序關(guān)系。常將偏序關(guān)系R記為“≤”，并將xRy記為x≤y。序偶<A,≤>稱為偏序集(partiallyorderedset,poset)。第二十七頁，共四十五頁，編輯于2023年，星期二例1:驗(yàn)證實(shí)數(shù)集R上的小于等于關(guān)系“”是偏序關(guān)系。（見書140頁例題1）。證明：1.對于任何實(shí)數(shù)aR,有aa成立，故“”是自反的。2.對于任何實(shí)數(shù)a,bR，如果ab，ba，則必有a=b，故“”是反對稱的。3.如果ab，bc那么必有ac，故“”是傳遞的。因此“”是一個(gè)偏序關(guān)系。第二十八頁，共四十五頁，編輯于2023年，星期二定義3-12.2[蓋住]:設(shè)<A,≤>是偏序集，若有x,yA，x≤y

，且xy，且不存在其它元素z，zA，使得x≤zz≤y，則稱元素y蓋住元素x。并且記蓋住集為：COVA={<x,y>|x,yA;y蓋住x}。例2：求蓋住集。P140例2COVA={<2,6>,<2,8>,<3,6>}。例3：

P140例3COVA={<1,2>,<1,3>,<2,4>,<2,6>,<3,6>,<4,12>,<6,12>}。第二十九頁，共四十五頁，編輯于2023年，星期二3-12.2哈斯圖根據(jù)上述定義，可以簡化偏序關(guān)系的關(guān)系圖得到哈斯圖(Hassediagram)，具體畫法如下：用小圓圈代表元素；若x≤y，xy，將代表y的小圓圈放在代表x的小圓圈之上，如果<x,y>COVA，則在y與x之間用直線連接。第三十頁，共四十五頁，編輯于2023年，星期二例3的哈斯圖1236124注意到：哈斯圖中的邊不再需要用有向邊。因?yàn)槿魎，v兩點(diǎn)間有邊，且u在v的下層，則表示u≤v，所以邊的方向一定是從下層結(jié)點(diǎn)指向上層結(jié)點(diǎn)的。第三十一頁，共四十五頁，編輯于2023年，星期二由關(guān)系圖改畫為哈斯圖的方法首先去掉自環(huán)，然后去掉封閉邊，再按照有向邊的方向，將結(jié)點(diǎn)位置進(jìn)行重新排列，即有向邊起始的結(jié)點(diǎn)放下層，終點(diǎn)的結(jié)點(diǎn)放上層；最后把有向邊改為無向邊。第三十二頁，共四十五頁，編輯于2023年，星期二例5：驗(yàn)證定義在P({a,b})上的包含關(guān)系是偏序關(guān)系，并畫出哈斯圖。證明：因?yàn)镻({a,b})有元素為{a，b}，{a}，，；又知{a}{a，b}，{a，b}，{a，b}，{a}，，{a，b}{a，b}，{a}{a}，，；可看出此包含關(guān)系具有自反，反對稱和傳遞性，所以是偏序關(guān)系。哈斯圖如下：{a，b}{a}第三十三頁，共四十五頁，編輯于2023年，星期二定義3-12.3[鏈chain，反鏈]：設(shè)<A,≤>是一個(gè)偏序集合，在A的一個(gè)子集中，如果每兩個(gè)元素都是有關(guān)系的，則稱這個(gè)子集為鏈。在A的一個(gè)子集中，如果每兩個(gè)元素都是無關(guān)的，則稱這個(gè)子集為反鏈。我們約定，若A的子集中只有單個(gè)元素，則這個(gè)子集既是鏈又是反鏈。特別地，當(dāng)A本身是鏈，稱<A,≤>是全序集，而關(guān)系“≤”稱為全序關(guān)系。第三十四頁，共四十五頁，編輯于2023年，星期二定義3-12.4[全序關(guān)系linearorder]：在偏序集<A,≤>中，如果A是一個(gè)鏈，則稱<A,≤>為全序集合或稱線序集合，在這種情況下，二元關(guān)系“≤”稱為全序關(guān)系或線序關(guān)系。全序集[linearlyorderedsets]<A,≤>就是對任意x，yA，或者有x≤y或者有y≤x成立。例如，定義在自然數(shù)集合N上的“小于等于”關(guān)系“≤”是偏序關(guān)系，且對任意i，jN，必有i≤j或j≤i成立，故也是全序關(guān)系。第三十五頁，共四十五頁，編輯于2023年，星期二3-12.3極大(小)元，最大(小)元定義3-12.5[最大(小)元、極大(小)元]：設(shè)<A,>為偏序集，BA，則：1.若存在yB，使得x(xByx)為真，則稱y為B的最小元(leastelement)。2.若存在yB，使得x(xBxy)為真，則稱y為B的最大元(greatestelement)。3.若存在yB，使得x(xBxyx=y)為真，則稱y為B的極小元(minimalelement)。4.若存在yB，使得x(xByxx=y)為真，則稱y為B的極大元(maximalelement)。第三十六頁，共四十五頁，編輯于2023年，星期二考慮偏序集<P({a,b}),>,哈斯圖為P143圖3-12.7所示。A）若B={{a}，}，則{a}是B的極、最大元，是B的極、最小元。B）若B={{a}，}，則B沒有最大元和最小元。{a}，是B的極大元，也是極小元。C）若B={，{a，b}}，則{a，b}是B的極、最大元，是B的極、最小元。D）若B={{a}，，}，則{a}，是B的極大元，是B的極、最小元。第三十七頁，共四十五頁，編輯于2023年，星期二定理3-12.1：設(shè)<A,>為偏序集，BA，若B有最?。ù螅┰瑒t該最?。ù螅┰俏ㄒ坏?。證明：假定a，b兩者都是B的最大元素，則ab，ba，從的反對稱性，得到a=b。同理可證最小元唯一。第三十八頁，共四十五頁，編輯于2023年，星期二定義3-12.6[上下（確）界]：設(shè)<A,>為偏序集，BA，則：1. 若yA滿足x(xBxy)，稱y為B的上界(upperbound)。2. 若yA滿足x(xByx)，稱y為B的下界(lowerbound)。3. 記B={y|yA且y是B的上界}，若B有最小元，則稱該最小元為B的上確界(leastupperbound，或join)，記為LUB(B)或B。4. 記B={y|yA且y是B的下界}，若B有最大元，則稱該最大元為B的下確界(greatestlowerbound，或meet)，記為GLB(B)或B。第三十九