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

3-9集合的劃分和覆蓋定義3-9.1[覆蓋cover]：若把一個(gè)集合A分成若干個(gè)叫做分塊的非空子集，使得A中每個(gè)元素至少屬于一個(gè)分塊，這些分塊的全體叫做A的一個(gè)覆蓋。即：設(shè)A為非空集合，S={S1,S2,…,Sm}，其中Si

A，Si≠

(i=1,2,…,m)且S1

S2

…

Sm＝A，則集合S稱作集合A的覆蓋。3-9集合的劃分和覆蓋定義3-9.1[覆蓋cover]：若1例:判斷以下集合是否為集合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}}不是不是不是是例:判斷以下集合是否為集合A的覆蓋？其中A={a,b,2定義3-9.2[劃分partition]：給定集合A的一個(gè)覆蓋S，若A中的每個(gè)元素屬于且僅屬于S的一個(gè)分塊，則S稱作是A的一個(gè)劃分。即：若S是集合A的覆蓋，且滿足Si∩Sj=

，（這里i≠j），則稱S是A的劃分。定義3-9.2[劃分partition]：給定集合A的一個(gè)3是例:判斷以下集合是否為集合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},rcjrg60,{e},{f}}（5）S7={{a,b,c,d,e,f}}我們看到對(duì)于一個(gè)給定集合,劃分不唯一不是不是是是最大劃分最小劃分是例:判斷以下集合是否為集合A的劃分？其中A={a,4定義3-9.3[交叉劃分]：若{A1,A2,…,Ar}與{B1,B2,…,Bs}是同一集合A的兩種劃分，則其中所有Ai∩Bj組成的非空集合，稱為原來(lái)兩種劃分的交叉劃分。定義3-9.4[加細(xì)]：給定X集合的任意兩個(gè)劃分{A1,A2,…,Ar}和{B1,B2,…,Bs}，若對(duì)于每一個(gè)Aj，均有Bk使Aj

Bk，則稱{A1,A2,…,Ar}為{B1,B2,…,Bs}的加細(xì)。定義3-9.3[交叉劃分]：若{A1,A2,…,Ar}與{5定理3-9.1:設(shè){A1,A2,…,Ar}與{B1,B2,…,Bs}是同一集合X的兩種劃分，則其交叉劃分仍是原集合的一種劃分。證明見(jiàn)書129頁(yè)。定理3-9.1:設(shè){A1,A2,…,Ar}與{B1,B2,6定理3-9.2:任何兩種劃分的交叉劃分，都是原來(lái)各劃分的一種加細(xì)。證明見(jiàn)書130頁(yè)。定理3-9.2:任何兩種劃分的交叉劃分，都是原來(lái)各劃分的一73-10等價(jià)關(guān)系與等價(jià)類3-10.1等價(jià)關(guān)系定義3-10.1[等價(jià)關(guān)系EquivalenceRelations]：設(shè)A，RAA，若R是自反的、對(duì)稱的和傳遞的，則稱R為A上的等價(jià)關(guān)系。例如平面上三角形集合中，三角形的全等關(guān)系、相似關(guān)系是等價(jià)關(guān)系。一個(gè)班級(jí)中，同學(xué)之間的同姓關(guān)系也是等價(jià)關(guān)系例1:見(jiàn)書131頁(yè)例題2（驗(yàn)證一個(gè)等價(jià)關(guān)系）3-10等價(jià)關(guān)系與等價(jià)類3-10.1等價(jià)關(guān)系83-10.2等價(jià)類定義3-10.2[等價(jià)類Equivalenceclasses]：設(shè)R是非空集合A上的等價(jià)關(guān)系，對(duì)任意的aA，定義[a]R={xA|aRx}，稱為a關(guān)于R的等價(jià)類，簡(jiǎn)稱a的等價(jià)類，在不混淆的情況下記為[a]。顯然[a]R非空，因?yàn)閍

[a]R

3-10.2等價(jià)類定義3-10.2[等價(jià)類Equivale9定理3-10.1

設(shè)R是非空集合A上的等價(jià)關(guān)系，對(duì)于任意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定理3-10.1設(shè)R是非空集合A上的等價(jià)關(guān)系，對(duì)于任意a10定義3-10.3[商集]：設(shè)R是非空集合A上的等價(jià)關(guān)系，關(guān)于R的全體不同的等價(jià)類為元素的集合{[a]R|aA}稱為A關(guān)于R的商集，記為A/R。例2：仍以書131頁(yè)例題2為例（給出一個(gè)集合和等價(jià)關(guān)系，求商集）。定義3-10.3[商集]：設(shè)R是非空集合A上的等價(jià)關(guān)系，關(guān)于11定理3-10.2：非空集合A上的等價(jià)關(guān)系R，決定了A的一個(gè)劃分，該劃分就是商集A/R。定理的證明見(jiàn)書133頁(yè)上，在此省略。定理3-10.2：非空集合A上的等價(jià)關(guān)系R，決定了A的一個(gè)劃12定理3-10.3：集合A的一個(gè)劃分確定A的元素間的一個(gè)等價(jià)關(guān)系。定理的證明見(jiàn)書133頁(yè)下，在此省略。例：包含三個(gè)元素的集合，可以有多少種不同的劃分，就有多少種等價(jià)關(guān)系。5種?？碢134例題4定理3-10.3：集合A的一個(gè)劃分確定A的元素間的一個(gè)等價(jià)關(guān)13定理3-10.4：設(shè)R1和R2為非空集合A上的等價(jià)關(guān)系，則R1=R2當(dāng)且僅當(dāng)A/R1=A/R2。定理的證明見(jiàn)書134頁(yè)中，在此省略。定理3-10.4：設(shè)R1和R2為非空集合A上的等價(jià)關(guān)系，則R14本次課小結(jié)及要求小結(jié)：1.集合的劃分和覆蓋的概念2.等價(jià)關(guān)系的概念及等價(jià)關(guān)系與劃分一一對(duì)應(yīng)要求：1.掌握集合的劃分和覆蓋的概念2.掌握等價(jià)關(guān)系的概念，會(huì)判斷一個(gè)關(guān)系是否是等價(jià)關(guān)系，記住幾個(gè)實(shí)例。3.掌握等價(jià)關(guān)系與劃分一一對(duì)應(yīng)，給定劃分會(huì)求等價(jià)關(guān)系；給定等價(jià)關(guān)系會(huì)求劃分。本次課小結(jié)及要求小結(jié)：15作業(yè)（3-10）P134(3)(7)(5)選作作業(yè)（3-10）P134(3)163-11相容關(guān)系定義3-11.1[相容關(guān)系]：給定集合A上的關(guān)系r，若r是自反的，對(duì)稱的，則稱r是相容關(guān)系。我們可以知道，相容關(guān)系的關(guān)系矩陣的對(duì)角線元素都為1，且是對(duì)稱矩陣，為此，可以將矩陣用梯形表示。關(guān)系圖上，每個(gè)結(jié)點(diǎn)都有自回路，且相關(guān)結(jié)點(diǎn)間的有向邊成對(duì)出現(xiàn)，可以把圖形簡(jiǎn)化為：不畫自回路，并用單線（無(wú)向邊）代替雙向有向邊。3-11相容關(guān)系定義3-11.1[相容關(guān)系]：給定集合A上17例1：設(shè)X={216，2234，379，648，545}，R是X中的二元關(guān)系。R={<x,y>|xX，yX，x和y有相同的數(shù)字}，試說(shuō)明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>例1：設(shè)X={216，2234，379，648，545}，R18關(guān)系矩陣如下：

1101011111MR=011001101101011轉(zhuǎn)化后如下：X21X301X4110X50101x1x2x3x4x5x4x1x2x3關(guān)系矩陣如下：x5x4x1x2x319定義3-11.2[相容類]:設(shè)r是集合A上的相容關(guān)系，若CA，如果對(duì)于C中任意兩個(gè)元素a1，a2有a1ra2，稱C是由相容關(guān)系r產(chǎn)生的相容類。上例中的相容類有：{x1,x2},{x1,x4},{x2,x4},{x2,x4,x5},{x2,x3}等。定義3-11.2[相容類]:設(shè)r是集合A上的相容關(guān)系，若C20定義3-11.3[最大相容類]：設(shè)r是集合A上的相容關(guān)系，不能真包含在任何其它相容類中的相容類，稱作最大相容類。記作Cr。在相容關(guān)系圖中，最大完全多邊形的頂點(diǎn)集合，就是最大相容類。此外，一個(gè)孤立結(jié)點(diǎn)，以及不是完全多邊形的兩個(gè)結(jié)點(diǎn)的連線，也是最大相容類。例2：見(jiàn)P137例1。定義3-11.3[最大相容類]：設(shè)r是集合A上的相容關(guān)系，21定理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}}定理3-11.1：設(shè)r是有限集合A上的相容關(guān)系，C是一個(gè)相容22已知集合的覆蓋，求相容關(guān)系定理3-11.2：給定集合A的覆蓋{A1，A2，An}，由它確定的關(guān)系R=A1

A1

A2

A2

…

An

An是相容關(guān)系。定理3-11.3：集合A上的相容關(guān)系r與完全覆蓋Cr(A)存在一一對(duì)應(yīng)。已知集合的覆蓋，求相容關(guān)系定理3-11.2：給定集合A的覆蓋23作業(yè)（3-11）P139(2)作業(yè)（3-11）P139(2)243-12序關(guān)系在這一節(jié)中，我們將介紹以下一些序關(guān)系：偏序關(guān)系全序關(guān)系良序關(guān)系擬序關(guān)系*3-12序關(guān)系在這一節(jié)中，我們將介紹以下一些序關(guān)系：253-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)系。3-12序關(guān)系在一個(gè)集合上，我們常常要考慮使得元素具有一定263-12.1偏序關(guān)系定義3-12.1[偏序關(guān)系](partialorder):

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

y，且不存在其它元素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>}。定義3-12.2[蓋住]:設(shè)<A,≤>是偏序集，若有x,293-12.2哈斯圖根據(jù)上述定義，可以簡(jiǎn)化偏序關(guān)系的關(guān)系圖得到哈斯圖(Hassediagram)，具體畫法如下：用小圓圈代表元素；若x≤y，x

y，將代表y的小圓圈放在代表x的小圓圈之上，如果<x,y>COVA，則在y與x之間用直線連接。3-12.2哈斯圖根據(jù)上述定義，可以簡(jiǎn)化偏序關(guān)系的關(guān)系圖得30例3的哈斯圖1236124注意到：哈斯圖中的邊不再需要用有向邊。因?yàn)槿魎，v兩點(diǎn)間有邊，且u在v的下層，則表示u≤v，所以邊的方向一定是從下層結(jié)點(diǎn)指向上層結(jié)點(diǎn)的。例3的哈斯圖1236124注意到：哈斯圖中的邊不再需要用有向31由關(guān)系圖改畫為哈斯圖的方法首先去掉自環(huán)，然后去掉封閉邊，再按照有向邊的方向，將結(jié)點(diǎn)位置進(jìn)行重新排列，即有向邊起始的結(jié)點(diǎn)放下層，終點(diǎn)的結(jié)點(diǎn)放上層；最后把有向邊改為無(wú)向邊。由關(guān)系圖改畫為哈斯圖的方法首先去掉自環(huán)，然后去掉封閉邊，再按32例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)系具有自反，反對(duì)稱和傳遞性，所以是偏序關(guān)系。哈斯圖如下：{a，b}{a}

例5：驗(yàn)證定義在P({a,b})上的包含關(guān)系是偏序關(guān)系，并畫33定義3-12.3[鏈chain，反鏈]：設(shè)<A,≤>是一個(gè)偏序集合，在A的一個(gè)子集中，如果每?jī)蓚€(gè)元素都是有關(guān)系的，則稱這個(gè)子集為鏈。在A的一個(gè)子集中，如果每?jī)蓚€(gè)元素都是無(wú)關(guān)的，則稱這個(gè)子集為反鏈。我們約定，若A的子集中只有單個(gè)元素，則這個(gè)子集既是鏈又是反鏈。特別地，當(dāng)A本身是鏈，稱<A,≤>是全序集，而關(guān)系“≤”稱為全序關(guān)系。定義3-12.3[鏈chain，反鏈]：設(shè)<A,≤>是一34定義3-12.4[全序關(guān)系linearorder]：在偏序集<A,≤>中，如果A是一個(gè)鏈，則稱<A,≤>為全序集合或稱線序集合，在這種情況下，二元關(guān)系“≤”稱為全序關(guān)系或線序關(guān)系。全序集[linearlyorderedsets]<A,≤>就是對(duì)任意x，yA，或者有x≤y或者有y≤x成立。例如，定義在自然數(shù)集合N上的“小于等于”關(guān)系“≤”是偏序關(guān)系，且對(duì)任意i，jN，必有i≤j或j≤i成立，故也是全序關(guān)系。定義3-12.4[全序關(guān)系linearorder]：在偏353-12.3極大(小)元，最大(小)元定義3-12.5[最大(小)元、極大(小)元]：設(shè)<A,>為偏序集，BA，則：1.若存在yB，使得x(xBy

x)為真，則稱y為B的最小元(leastelement)。2.若存在yB，使得x(xBx

y)為真，則稱y為B的最大元(greatestelement)。3.若存在yB，使得x(xBx

y

x=y)為真，則稱y為B的極小元(minimalelement)。4.若存在yB，使得x(xBy

x

x=y)為真，則稱y為B的極大元(maximalelement)。3-12.3極大(小)元，最大(小)元定義3-12.5[最36考慮偏序集<P({a,b}),>,哈斯圖為P143圖3-12.7所示。A）若B={{a}，}，則{a}是B的極、最大元，是B的極、最小元。B）若B={{a}，}，則B沒(méi)有最大元和最小元。{a}，是B的極大元，也是極小元。C）若B={，{a，b}}，則{a，b}是B的極、最大元，是B的極、最小元。D）若B={{a}，，}，則{a}，是B的極大元，是B的極、最小元?？紤]偏序集<P({a,b}),>,哈斯圖為P143圖337定理3-12.1：設(shè)<A,>為偏序集，BA，若B有最?。ù螅┰瑒t該最?。ù螅┰俏ㄒ坏?。證明：假定a，b兩者都是B的最大元素，則ab，ba，從的反對(duì)稱性，得到a=b。同理可證最小元唯一。定理3-12.1：設(shè)<A,>為偏序集，BA，若B有最小38定義3-12.6[上下（確）界]：設(shè)<A,>為偏序集，BA，則：1. 若yA滿足x(xBx

y)，稱y為B的上界(upperbound)。2. 若yA滿足x(xBy

x)，稱y為B的下界(lowerbound)。3. 記B={y|yA且y是B的上界}，若B有最小元，則稱該最小元為B的上確界(leastupperbound，或join)，記為L(zhǎng)UB(B)或B。4. 記B={y|yA且y是B的下界}，若B有最大元，則稱該最大元為B的下確界(greatestlowerbound，或meet)，記為GLB(B)或B。定義3-12.6[上下（確）界]：設(shè)<A,>為偏序集，39定義3-12.7[良序集]：若偏序集A的每一個(gè)非空子集存在最小元，則稱A為良序集。定理3-12.2:

每一個(gè)良序集必是全序集，每一個(gè)有限的全序集必是良序集。如：I表示全體整數(shù)的集合，則<I,≤>就不是良序集。因?yàn)槿∫蛔蛹疘’={…,-3,-2,-1},其上就沒(méi)有最小元。擬序關(guān)系是一種反自反的、可傳遞的二元關(guān)系。定義3-12.7[良序集]：若偏序集A的每一個(gè)非空子集存在最40偏序集全序集良序集（鏈）（有最小元的全序集）偏序集全序集良序集41作業(yè)：(3-12)P145（1）（6）（7）作業(yè)：(3-12)P145（1）42本次課小結(jié)及要求小結(jié)：1.偏序關(guān)系及偏序集的概念2.偏序集的哈斯圖,極大極小元、最大最小元、上下（確）界要求：1.掌握偏序關(guān)系及偏序集的概念2.會(huì)判斷一個(gè)關(guān)系是否是偏