離散數(shù)學(xué)-3-9集合的劃分和覆蓋.ppt

《離散數(shù)學(xué)-3-9集合的劃分和覆蓋.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)-3-9集合的劃分和覆蓋.ppt（11頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1,第三章集合與關(guān)系,3-9集合的劃分和覆蓋授課人：李朔Email:chn.nj.ls@,2,一、集合的覆蓋和劃分,在集合的討論中，常須把一個(gè)集合分成若干子集加以討論，這就是集的劃分問(wèn)題。如一個(gè)班男、女生。一個(gè)學(xué)院不同專業(yè)。P128定義3-9.1若把一個(gè)集合A分成若干個(gè)稱為分塊的非空子集，使得A中每個(gè)元素至少屬于一個(gè)分塊，那么這些分塊的全體構(gòu)成的集合稱為A的一個(gè)覆蓋。上述定義與下面定義是等價(jià)。令A(yù)為給定非空集合，S={S1,S2,?,Sm},其中Si?A且Si???(i=1,2,?,m)且則稱S是集合A的一個(gè)覆蓋。*如果A中每個(gè)元素屬于且僅屬于一個(gè)分塊，那么這些分塊的全體構(gòu)成的集叫做A的一個(gè)劃分（或分劃）。即：若有Si?Sj=?(i?j)，則稱S為A的一個(gè)劃分。,,3,一、集合的覆蓋和劃分,例設(shè)A=?a,b,c?，以下是A的子集構(gòu)成的集合：S=??a,b?,?b,c??Q=??a?,?a,b?,?a,c??D=??a?,?b,c??G=??a,b,c??E=??a?,?b?,?c??F=??a?,?a,c??試確定哪些集合是A的覆蓋？哪些集合是A的劃分？哪些集合既不是覆蓋，也不是劃分？,,4,一、集合的覆蓋和劃分,例設(shè)A=?a,b,c?，以下是A的子集構(gòu)成的集合：S=??a,b?,?b,c??Q=??a?,?a,b?,?a,c??D=??a?,?b,c??G=??a,b,c??E=??a?,?b?,?c??F=??a?,?a,c??試確定哪些集合是A的覆蓋？哪些集合是A的劃分？哪些集合既不是覆蓋，也不是劃分？解：S和Q是A的覆蓋，但不是劃分；D、G和E是A的覆蓋，也是劃分；F不是A的覆蓋，也不是劃分。,,5,一、集合的覆蓋和劃分,例A={a,b,c}則S={{a,b},{b,c}}、Q={{a},{a,b},{a,c}}都為A的覆蓋，而D={{a},{b,c}}、G={{a,b,c}}、E={{a},,{c}}為A的劃分。而且稱G為A的最小劃分（由集合的全部元素組成），而E為A的最大劃分（每個(gè)元素構(gòu)成一個(gè)單元素分塊）。*劃分必是覆蓋，覆蓋未必是劃分,,6,一、集合的覆蓋和劃分,例3設(shè)A=?1,2,3?，試確定A的所有劃分。,,解：有一個(gè)劃分塊的劃分是：??1,2,3??有兩個(gè)劃分塊的劃分是：??1?,?2,3????2?,?1,3????3?,?1,2??有三個(gè)劃分塊的劃分是：??1?,?2?,?3??上圖是A的所有劃分的示意圖。(a)表示有一個(gè)劃分塊的劃分??1,2,3??。(b)、(c)和(d)表示有兩個(gè)劃分塊的劃分??1?,?2,3??、??2?,?1,3??和??3?,?1,2??。(e)表示有三個(gè)劃分塊的劃分??1?,?2?,?3??。*給定一個(gè)集合A，它的劃分和覆蓋都不是唯一的。,7,一、集合的覆蓋和劃分,例：4個(gè)元素的集合A共有多少個(gè)不同的劃分。解：A的最大(所有元素），最小劃分（各元素單列）都各有一個(gè)把4個(gè)元素分成1，3兩部分，有4種可能；把4個(gè)元素分成2，2兩部分，有3種可能；把4個(gè)元素分成1，1，2三部分，有6種可能。故總共有1＋1＋3＋6＋4＝15種。,,8,二、交叉劃分,P129定義3-9.2若{A1,A2,?,Ar}與{B1,B2,?,Bs}是同一集合A的兩種劃分，則其中所有Ai?Bj??所組成的集，稱為原來(lái)兩種劃分的交叉劃分。例P129所有生物定理3-9.1設(shè){A1,A2,?,Ar}與{B1,B2,?,Bs}是同一集合X上的兩種劃分，則其交叉劃分也是原集合的一種劃分。,9,三、劃分的加細(xì),定義3-9.3對(duì)集合X上的任兩種劃分{A1,A2,?,Ar}與{B1,B2,?,Bs}，若對(duì)于每一個(gè)Aj均有Bk，使得Aj?Bk，則{A1,A2,?,,Ar}稱為{B1,B2,?,Bs}的加細(xì)。定理3.9.2任何兩種劃分的交叉劃分，都是原劃分的一種加細(xì)。證明：設(shè){A1,A2,?,Ar}和{B1,B2,?,Bs}的交叉劃分為T(mén)，對(duì)T中的任意元素Aj?Bj，必有Aj?Bj?Aj,Aj?Bj?Bj故T必是原劃分的加細(xì)。,10,本課小結(jié),覆蓋劃分交叉劃分劃分的加細(xì),11,作業(yè),P130（2）,