1、離散數學講義離散數學講義數學教研室李家林制作數學教研室李家林制作離散數學緒論離散數學緒論 離散數學是計算機科學中基礎理論的核心課程離散數學是計算機科學中基礎理論的核心課程離散數學以研究離散量相互間的關系為主要目標離散數學以研究離散量相互間的關系為主要目標,其其研究的主要對象一般是有限或可數個元素構成的集研究的主要對象一般是有限或可數個元素構成的集合合.因此它充分地描述了計算機科學離散性的特點因此它充分地描述了計算機科學離散性的特點. 離散數學對計算機科學與技術的發展離散數學對計算機科學與技術的發展,一直起著一直起著重要的作用重要的作用. 在計算機科學中普遍采用了離散數學中在計算機科學中普遍采用

2、了離散數學中的基本概念的基本概念,基本思想和基本方法基本思想和基本方法.把離散數學作為自把離散數學作為自己的理論和重要的數學工具己的理論和重要的數學工具;同時又不斷地給離散數同時又不斷地給離散數學提出一些新的課題學提出一些新的課題. 此外此外,離散數學在計算機科學與技術的教育中離散數學在計算機科學與技術的教育中也是一門必不可少的課程也是一門必不可少的課程.它不僅是計算機的專業它不僅是計算機的專業基礎課基礎課,是數據結構是數據結構,操作系統操作系統,編譯原理編譯原理,數據庫原數據庫原理以及人工智能的必備基礎理以及人工智能的必備基礎,而且對培養同學們的而且對培養同學們的抽象思維和邏輯推理能力有重要

3、的作用。抽象思維和邏輯推理能力有重要的作用。 離散數學以集合論、代數系統、圖論、數理邏離散數學以集合論、代數系統、圖論、數理邏輯為主要內容。輯為主要內容。1.1 集合集合a.概念概念 集合是數學中最基本的概念集合是數學中最基本的概念,只給予一種描述只給予一種描述:把一些確定的、彼此不同的事物作為一個整體來考慮把一些確定的、彼此不同的事物作為一個整體來考慮時時,這個整體稱為一個這個整體稱為一個集合集合.集合中的事物即個體稱為集合中的事物即個體稱為元素元素. 注意兩點注意兩點:1.每個元素一般各不相同每個元素一般各不相同; 2.每個元素有確定的性質每個元素有確定的性質.幾個常見的集合的表示符號幾個

4、常見的集合的表示符號:N: 自然數集自然數集 1, 2 ,3 ,Z: 非負整數集非負整數集 0, 1, 2 ,3 ,I: 整數集整數集 0,-1, 1, -2, 2 , -3, 3 ,P: 素數集素數集(只能被只能被1和自身整除和自身整除,不能被其他正不能被其他正 整數整除的大于整數整除的大于1的正整數稱為素數的正整數稱為素數)Nm (m1 ) :1, 2 , 3 ,mZm (m1) : 0, 1, 2 , 3 , m-1R: 全體實數全體實數.C: 全體復數全體復數(形如形如a+bi的數的數, aR, bR)Q: 全體有理數全體有理數(形如形如i/j的數的數, iI, jI )b.集合的表示

5、法集合的表示法: 1. 列舉法列舉法: 把集合的元素按任意順序寫在一個花把集合的元素按任意順序寫在一個花括號里括號里,并用逗號分開的方法稱為列舉法并用逗號分開的方法稱為列舉法.有限集及有限集及可數集可以用這種方法表示可數集可以用這種方法表示. 2. 描述法描述法: 將集合中的元素以定義的形式給出的將集合中的元素以定義的形式給出的.即給定一個條件即給定一個條件p(x),當且僅當當且僅當a使條件使條件p(x)成立時成立時,aA.一般形式一般形式A=a | p(a) . p(a) 描述了一個規則或描述了一個規則或公式公式.表示的意義可以非常廣泛表示的意義可以非常廣泛. 如如 S =a| aI , 且

6、且4a14. 又如又如B=a| a是中國是中國的省會城市的省會城市. 注意注意:用描述法表示集合用描述法表示集合,其方式并不是唯一的其方式并不是唯一的.c.關于集合中的悖論關于集合中的悖論:一般集合元素無限制一般集合元素無限制,元素本身也可是集合元素本身也可是集合.如如. A=3,1,2,1,d,q,B=1,3,1,3最重要的是把集合最重要的是把集合a元素元素a區別開區別開.如集合如集合qA.而而q是是q 的元素的元素, qq,但但q不是不是A的元素的元素. q是是q AdAdddAdAqAq ,；但但，還還有有，且且也也不不能能有有例例: 指明下列命題的真假指明下列命題的真假: 設設S=2,

7、a,3,4, R= a,3,4,1 1.aS; 2. aR ; 3. a,3,4,1 R; 4.S=R.1. 否否; 2. 對對; 3.對對; 4.否否. 要注意不能使用要注意不能使用“包含一切集合的集合包含一切集合的集合”之類的之類的語語言言.否則會導致矛盾否則會導致矛盾.下面是著名的羅素悖論下面是著名的羅素悖論: 設設c集合的集合集合的集合:使使c=A|A是一個集合是一個集合,A A那么那么cc,還是還是c c呢呢?(羅素悖論羅素悖論). 因為若因為若cc,由由c的定義的定義c c,若若c c由由c的定義的定義cc.顯然這樣的顯然這樣的c是不存在的是不存在的. 還有一個更通俗的例還有一個更

8、通俗的例:一個小鎮上有一個理發師一個小鎮上有一個理發師他他只給那些不為自己理發的人理發只給那些不為自己理發的人理發.(其余的人他都不理其余的人他都不理發發).這個悖論說的是理發師的頭無論由誰理都是矛盾這個悖論說的是理發師的頭無論由誰理都是矛盾.d.基數基數: 定義定義1: 不含任何元素的集合稱為空集不含任何元素的集合稱為空集.記為記為.我們要證明命題我們要證明命題p(x )對一切對一切x不真不真.可證可證x|p(x)= . 定義定義2: 集合集合A中不同元素的數目稱為集合中不同元素的數目稱為集合A的基的基數數.記為記為 A. 當當 A為有限數時為有限數時,稱稱A為有限集為有限集.否則稱否則稱A

9、為無限為無限集集.更詳細的以后再討論更詳細的以后再討論.1.2集合的包含和相等集合的包含和相等 定義定義1: A. B為二集合為二集合,A中的每一元素均在中的每一元素均在B中中,稱稱B包含包含A;或或A含于含于B.記為記為A B. 若若A B ,且且B A. 稱稱A與與B相等相等,記為記為A=B. 例例A=a.b.c, B=a.b.c,a,b,c, A B且且AB.此例此例說明包含說明包含 、屬于并不是相排斥的、屬于并不是相排斥的. 定義定義2: A. B為二集合為二集合, A B且且AB.稱稱A是是B的真的真子集子集. 定理定理1: 空集是任何集合的子集空集是任何集合的子集.(反證法反證法,

10、注意否定注意否定定義定義) 定理定理2: 空集是唯一的空集是唯一的. ( 假設有兩個假設有兩個,證明這兩個證明這兩個相等相等). 1.3 冪集冪集 定義定義: 集合集合A的所有子集構成的集合稱為的所有子集構成的集合稱為A的冪集的冪集.記為記為2A. 例例 寫出集合寫出集合A=1,2,3的冪集的冪集 定理定理 若若A是有限集是有限集,且且A = n,則則2 A=2 A=2n nkknnknknkknncyxyxcyx0021，有有令令）證證明明：（ 我們注意到集合我們注意到集合A 中元素為中元素為k個的子集恰有個的子集恰有 個個.于是于是 2A= =2n=2 (A)knc nKknc0關于冪集的

11、二進制表示關于冪集的二進制表示: 當當A的元素較多時的元素較多時,無遺漏的無遺漏的A較困難較困難,下面引進一下面引進一種表示法可以無遺漏的表出種表示法可以無遺漏的表出2A的每一元素的每一元素.為此為此,我們我們不妨對所給集合規定某種次序不妨對所給集合規定某種次序,即給該集合中的每個即給該集合中的每個元素附加一個標號元素附加一個標號,以使描述這個元素在該集合中的以使描述這個元素在該集合中的相應位置相應位置.如如A=a,b,c分別是一、二、三元素，在分別是一、二、三元素，在A的子集中，常有一些元素出現，另一些元素不出現。的子集中，常有一些元素出現，另一些元素不出現。 我們根據這一情況來指定集合中元

12、素的次序我們根據這一情況來指定集合中元素的次序,用用如下方式表示如下方式表示.如如A的各子集表為的各子集表為:B000=, B 001=c, B010=b, B011=b,c, B100=a,B101=a,c, B110=a,b, B111=a,b,c 則有則有2A=B000, B 001, B010, B011, B100, B101, B110, B111 = B0, B 1, B2, B3, B4, B5, B6, B7 其中前一括號其中前一括號B的下標是三位二進制數的下標是三位二進制數,每一每一位對應集合位對應集合A中的一個元素中的一個元素,左邊的第一位是左邊的第一位是1還是還是0表表

13、A中元素中元素a在子集中出現與否在子集中出現與否.第二第二.三位刻劃三位刻劃b.c是否在是否在A的子集中是否出現的子集中是否出現.在此意義下在此意義下,A的子集的子集可由可由000111中的一個數來表示中的一個數來表示. 若設集合若設集合J=j|j是二進制數是二進制數000j111,則有則有2A=Bj| jJ,這里主要是下標確定子集元素這里主要是下標確定子集元素,與表示與表示子集用的字母子集用的字母B無關無關. 一般地一般地,表示任意表示任意n個元素的各個子集個元素的各個子集,用來表示這些用來表示這些子集的下標是十進制數子集的下標是十進制數02n-1的二進制表示的二進制表示,為了湊足為了湊足n

14、個數位個數位,一定要在這些二進制數左邊添入所需個數的零一定要在這些二進制數左邊添入所需個數的零.我們也可以用從我們也可以用從02n-1的十進制數來作為子集的下標的十進制數來作為子集的下標.而只在要確定所對應子集的元素時才轉換為二進制數而只在要確定所對應子集的元素時才轉換為二進制數. 令令A=a1 ,a2, a3, a4,a5 ,a6而而2A有有64個元素個元素,我們可稱為我們可稱為B0, B1, B2, ,A中的子集的各元素是如何確定的中的子集的各元素是如何確定的呢呢? 如如B7=B000111=a4 ,a5 ,a6 B12=B001100=a3 ,a4.126B而而a2 ,a4=B01010

15、0= (010100)2 =(22 +24 )10 例例:若若B C, 則則2B 2C成立與否成立與否?討論討論: 該結論是正確的該結論是正確的.證明如下證明如下: 任意任意x2B ,即即x B可有可有x C,即即x2C 所以所以2B 2C202224BB1.4 集合的運算集合的運算一一.全集全集定義定義1: 若某集包含了某個問題所論及的一切對象若某集包含了某個問題所論及的一切對象.稱該集為全集稱該集為全集.記為記為U. 全集因所討論的問題不同可相異全集因所討論的問題不同可相異.例如例如: 討論正整數范圍內討論正整數范圍內U可取作可取作N;實數討論問題實數討論問題U可取可取作作R. 定義定義2

16、: 設設A.B為二集合為二集合.屬于屬于A或或B的所有元素構的所有元素構成的集合稱為成的集合稱為A與與B的并的并.記為記為AB.即即 AB=u | uAoruB 既屬于既屬于A又屬于又屬于B的所有元素構成的集合稱為的所有元素構成的集合稱為A與與B的交的交. 記為記為AB.即即 AB=u | uA且且uB 例例 ( 略略) 若若AB=,稱稱A.B不相交不相交.如如A1 =1,2,3 A2=1,2,3 A3=1,1,2 則則Aj Ai= 基本運算規律基本運算規律: 1.A AB B AB A AB B AB 2. 若若 A B, 則則 A=AB B=AB 定義定義3: 設設A.B為二集合為二集合.

17、屬于屬于B而不屬于而不屬于A 的元素構成的元素構成的集合的集合,稱為稱為A關于關于B的相對補集的相對補集.記為記為BA. 即即BA=u|u B ，u ABA也稱為也稱為B與與A的差集的差集. 例如例如 A=3,4,6,7 B=1,2,3,4 則則 B A =1,2 A - B =6,7定義定義4: A關于全集關于全集U的相對補集的相對補集.稱為稱為A的絕對補集的絕對補集.記為記為A. A=U A=u|uU，u A 例例: U=Z A=2K| KZ A=U-A=2K+1|K Z U = =U定義定義5 設設 是集合是集合U的一組子集的一組子集,把對把對,A1,A2, Ar ,U 任意施加任意施加

18、“”“”“”運算有限次而產生的運算有限次而產生的集合集合 稱為由稱為由A1,A2, Ar ,所產生的集合所產生的集合.,U,A(B C)等均為等均為A.B.C所產生的集合所產生的集合.例例:設設A.B是任意集合是任意集合,等式等式2A-B=2A-2B能否成立能否成立? 解解: 如如A=a,c B=b,c 有有A-B=a , 2 A-B=,a 2A=,a,c,a,c 2B= ,b,c,b,c 2A-2B= a,a,c 與與2A-B互不包含互不包含.進一步可看到進一步可看到:riiA12A 2B 但但2A-B 所以所以 2A-B 2A-2B 進一步探討進一步探討: 2A-B 2A-2B 一般也不成

19、立一般也不成立,如如s 2A-2B 有有s 2A , s 2B s A , s B .但但s中可能有元素中可能有元素在在(只要求不是所有元素都在只要求不是所有元素都在B中中) 如可能有如可能有y s, y B則則s A-B(S中可能有中可能有B的元素的元素) 即即s 2A-B . 所以所以 2A-B 2A-2B也不成立也不成立 參閱參閱P32習題習題16BA22 1.5文氏圖文氏圖 文氏圖是用來表示集合關系及運算的示意圖文氏圖是用來表示集合關系及運算的示意圖.全集全集U用矩形區域來表示用矩形區域來表示,U的子集在文圖中用圓形來表示的子集在文圖中用圓形來表示,ABBA直觀上直觀上: BABAAA

20、ABBAABBA)(AB 文圖對較復雜的運算及關系反映不甚準確文圖對較復雜的運算及關系反映不甚準確,(有時有時關系較多不易想清楚關系較多不易想清楚,文圖用來證明關于集合的命題文圖用來證明關于集合的命題也不合適只能起提示作用也不合適只能起提示作用).如下圖如下圖A B = (A B ) (B A ) (A B) (1.2)A B = (A B ) (B A ) (3)因此不能說因此不能說(1.2)式與式與(3)式總是相等的式總是相等的.ABABAB(1)(2)(3) 1.6集合成員表集合成員表 前面定義的集合運算的交前面定義的集合運算的交.并并.補補.顯然對全集顯然對全集U運算運算是封閉的是封閉

21、的.下面對這些概念以新的形式定義下面對這些概念以新的形式定義,使之數量使之數量化化.能夠更新能夠更新,更清晰更清晰,更具理論價值更具理論價值.先討論基本成員表先討論基本成員表. a.集合集合A的補集可如下定義的補集可如下定義: A的成員表的成員表 A A 0 1 1 0AuAuAuAu 則則若若則則若若 對集合對集合S(AorA)所在的列中所在的列中,數字數字0或或1表示元素表示元素u不屬于不屬于S或或u屬于屬于S. b.集合集合A與與B的并集可如下定義的并集可如下定義: A B的成員表的成員表 A B A B 0 0 0 0 1 1 1 0 1 1 1 1BAuBuAuBAuBuAuBAuB

22、uAuBAuBuAu 則則，若若則則，若若則則，若若則則，若若C .集合集合A與與B的交集可如下定義的交集可如下定義: A B的成員表的成員表 A B A B 0 0 0 0 1 0 1 0 0 表中反映元素是否屬于表中反映元素是否屬于A.B交交. 并的情形并的情形 . 1 1 1.BAuBuAuBAuBuAuBAuBuAuBAuBuAu 則則，若若則則，若若則則，若若則則，若若 A.,B產生的集合成員表產生的集合成員表.可以推廣到可以推廣到A1,A2, Ar 所產生的集所產生的集 合合S上去上去,一般由一般由A1,A2, Ar 所產生的集合所產生的集合S的成員表具體的成員表具體表示如下表示如

23、下: 該成員表的前該成員表的前r列標記列標記 A1,A2, Ar ,最后一列標記最后一列標記為為S ; 標記為標記為Ai的列中數字的列中數字1表示表示u Ai,數字數字0表示表示u Ai,若若在第在第K行上。前行上。前r列所指明的條件有列所指明的條件有u S ,則在則在S的位置的位置(第第S列第列第K行行)記記0.否則否則uS,則在則在S的位置的位置(第第S列第列第K行行)記記1. 集合成員表共有集合成員表共有2r行行,它相應于它相應于A1,A2, Ar 中的中的2r種可能種可能成員成員/非成員情況非成員情況.為簡化為簡化,有時把標記有時把標記A1,A2, Ar 列中的一行列中的一行標記數字標

24、記數字1,2,3,r(i1或或0)稱為行稱為行1,2,3,r.下面給出下面給出 S=(AB)(AC)(BC)的成員表的成員表. S=(AB)(AC)(BC) A B C A AB A C BC(AB) (A C) S 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1 1 1 0 1 0 1 1 1 上表中S是由A.B.C產生的集合,S的成員表構造其中的前r列列出了A.B.C八種可能成員/非成

25、員的情況.而最后一列列出了u在S中的成員/非成員的情況,這一列是通 過集合A, AB, A C, BC,(AB) (A C)的中的成員表相繼構造出來的,除前三列外,后面的每一列都是由前面的列參照, 成員表構造出來的. 關于表的說明關于表的說明: 若某列記值全為若某列記值全為0,則該列對應的集合為空集則該列對應的集合為空集.若全若全為為1,則該列對應的集合為全集則該列對應的集合為全集U,如果成員表中兩列標如果成員表中兩列標記的集合記的集合T.S全相同全相同.這時這時S.T相互重合相互重合.S=T. 前表中前表中(AB) (A C) = (AB)(AC)(BC) 于是集合成員表可用來證明集合相等于

26、是集合成員表可用來證明集合相等,包含包含.S與與T對對應的兩列應的兩列,S的列對應的列對應1對于對于T也是也是1,而而T中的中的1S不一定是不一定是1,這時這時 . 練習練習:1.用兩種方法證明用兩種方法證明:A(BC)=(AB)(AC) 2. 判斷判斷A(BC)=(AB)C能否成立能否成立? (可畫文圖討論可畫文圖討論)（1。7略）略）ST 定義定義1: 設設=AiiK是集合是集合A的某些非空子集的集合的某些非空子集的集合.如果集合如果集合A的每一元素在且只在其中的某一的每一元素在且只在其中的某一Ai中即若中即若 1).AiAj = i j i, jK 2). 則稱集合則稱集合是集合是集合A

27、的一個分劃的一個分劃.而每個而每個Ai稱為這個分稱為這個分劃的分劃塊劃的分劃塊. 例例: A=1,2,3 則則 1=1,2,3 ;2=1,2,33=2,1,3 4=3,1,2 5=1,2,3均為均為A的的分劃分劃,分劃一般不是唯一的分劃一般不是唯一的.AAKii 1. 8分劃分劃例例: A=I(整數集整數集,A是是A中被中被5除余數為除余數為i的所有整數的的所有整數的集合集合) 則則 A0=-10, -5, 0, 5, 10 A1=-9,-4, 1, 6, 11 A2= -8, -3, 2, 7,12 A3=-7, -2, 3, 8, 13 A4=-6, -1,4, 9, 14 構成的集合構成

28、的集合A的一個的一個分劃分劃,由于被由于被5除的每一整數余數唯一除的每一整數余數唯一,所以所以A中的每中的每一元素在且只在某一一元素在且只在某一Ai中中, 即上述元素構成的集合是即上述元素構成的集合是A的一個分劃的一個分劃.定義定義: 設設 與與 均為均為A的分劃的分劃,如果如果中的每一中的每一Ai 都是都是中的某一個中的某一個Aj的子集，則的子集，則稱分劃是分劃的一個細分稱分劃是分劃的一個細分; 若若是是的細分的細分,且且中中至少有一個至少有一個Ai 為某個為某個Aj的真子的真子 集集, 則稱則稱是是的的真細分真細分. 分劃全集分劃全集U常用常用,事實上分劃是事實上分劃是U劃分分界線劃分分界

29、線,若分劃若分劃的分界線是在分劃已有的分界線上添加新的分界線的分界線是在分劃已有的分界線上添加新的分界線,則則是是 的真細分的真細分. 練習練習: 1).P33.習題習題25. 2).在在11000000之間之間,(包括包括1和和1000000)有多少整有多少整數既不是平方數數既不是平方數,也不是立方數也不是立方數.KiiAKiiA解解: 設設S=x| xN且且1x1000000 A=x| xS且且x是完全平方數是完全平方數. B=x| xS且且x是完全立方數是完全立方數.則則S=1000000 A=1000 B=100 (AB)=10 (AB) = S - ( A+ B)+ (AB) =10

30、0000-(1000+100)+10 =998910(注意到注意到1000000=10002=1003 確定確定A與與B,最后最后的等式可由文圖確定的等式可由文圖確定) 1.9 集合的標準形式集合的標準形式一一.最小集的標準形式最小集的標準形式 定義定義: 設設A1,A2, Ar 是全集是全集U的子集的子集,形如形如 的集合稱為由的集合稱為由A1,A2, Ar所產生的最小集所產生的最小集,其中每個其中每個 為為Ai 或或Ai (注意每個注意每個 中中Ai 或或Ai至少出現且只至少出現且只出現一個出現一個). 例如由例如由A.B.C產生的最小集為產生的最小集為:A B C A BC A BC A

31、 BC A BC A B C ABC AB 由乘法原理及定義知由乘法原理及定義知:由由A1,A2, Ar所產生的最小集所產生的最小集共有共有2r個個.仔細觀察下列兩圖仔細觀察下列兩圖.iriA1iAiA ABCABC ABCABCABCABCABCABC ABCABC ABCABCABC =ABC =ABCABC=定理定理1: 由由A1,A2, Ar 所產生的非空最小集的集合構成所產生的非空最小集的集合構成U的一個分劃的一個分劃.證明證明: 只證只證 1). (其中其中Si是由是由A1,A2, Ar 所產生的最小集所產生的最小集i=1,2,2r) 2).SiSj= ij 證證: 1)只證只證

32、U Si 并集符號上的上下標省略并集符號上的上下標省略.任任意意u U, 則則uA1或或uA1 u Ai或或 uAi.所以必有所以必有 u 是某個是某個Sjo ，所以，所以U 1)成立成立.Usiir21iriA1iisr212).反證法反證法: 設設uU uS1S2 S1 , .S2是是A1,A2, Ar 所產生的兩個所產生的兩個不同不同的最小集的最小集,則必存在一個則必存在一個i0(1 i0r)使使uAi0, 同時同時uAi0(S1 與與S2中對應因子至少有一個中對應因子至少有一個不同不同), 但這與但這與Ai0Ai0=矛盾矛盾,所以所以SiSj= ij 所以由所以由A1,A2, Ar 所

33、產生的非空最小集的集合構成所產生的非空最小集的集合構成U的一個分劃的一個分劃.證畢證畢 為了討論方便為了討論方便,我們用我們用 表示最小集表示最小集 ,其中其中如如A1A2A3 A4=M1101rM 21 rAAA21 iiiiiAAAA當當當當10 A1A2A3A4=M0011 ,顯然顯然 表最表最小集是唯一的小集是唯一的. 關于最小集的成員表關于最小集的成員表 對于任一最小集對于任一最小集 = 的的 成員表中成員表中,由由定義可知定義可知:當且僅當當且僅當時時u ,故在最小集故在最小集 中中,對應所標記對應所標記的列中有且只有一個的列中有且只有一個1,其余均為其余均為0.(觀察成員表觀察成

34、員表) 因為成員表的前因為成員表的前r列列A1,A2, Ar 中取中取0,1值值,恒為恒為 對對應應Ai與與Ai,故每一行對應一個最小集故每一行對應一個最小集. A1,A2, Ar 中取中取0,1值對應值對應123r,相應的最小集相應的最小集 在在rM21rM21iriA1rAuAuAu,21rM21rM21iArM21行行123r取值為取值為1,其余行為其余行為0,如表如表A B C A AB C A BC AB CABC S =M001 =M011 =M110 =M111 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1

35、 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 0 0 1 1其中其中S=M001M011M110M111. 標記的列中只有一個標記的列中只有一個1,只在只在123r取值為取值為1,其余行為其余行為0, 理論上及實際計算都有這個結果理論上及實際計算都有這個結果.如如最小集最小集M001=ABC當且僅當當且僅當uB,uA, uC,rM21uM110,這時這時M110所處的列中僅在行所處的列中僅在行110處取處取1,而其余而其余行均為行均為0. 進一步研究由進一步研究由A1,A2, Ar 所產

36、生所產生i個個(i2r)不同的最小不同的最小集的并集集的并集(集合構造集合構造): 并集并集及其成員表及其成員表:作出其列為作出其列為A1,A2, Ar ,(j=1,2,i)及及 所標記的成員所標記的成員表表.jrjjirirrMMMMij 211221112111 jrjjM 21jijjMij 211 其中最后一列由前其中最后一列由前i列借助運算列借助運算得到得到.參閱前表可知參閱前表可知,上述并集所對應的列僅在上述并集所對應的列僅在11 2r,21 2r,i1ir這這i,行處為行處為1,其余行為其余行為0.上表還表明成員表上表還表明成員表S的構造的構造.其中其中 S=(ABC)(ABC)

37、(ABC)(ABC)定理定理2 由由A1,A2, Ar 所產生每個非空集所產生每個非空集S恒可表示為若恒可表示為若干個不同的最小集的并集干個不同的最小集的并集.證明證明 S,因此因此S的成員表中所對應的列必有的成員表中所對應的列必有L個個1,其其中中1L2r ,設這設這L個個1分別在行分別在行11 2r, 21 2r, L1 Lr,作如下最小集之并作如下最小集之并,用用T表示表示:T=將將T植于成員表的最后一列可知植于成員表的最后一列可知,這必有與這必有與S所在的列恒同所在的列恒同.LrLirrMMM 122111211即即T=S.證畢證畢 定理的證明不僅說明由定理的證明不僅說明由A1,A2,

38、 Ar 所產生每個非所產生每個非空集空集S恒可表示為若干個不同的最小集的并集恒可表示為若干個不同的最小集的并集.還指明還指明找到是哪些最小集的并找到是哪些最小集的并. 練習練習:作出作出(AB)(AC)的成員表，并求其最小的成員表，并求其最小集的標準形式。集的標準形式。如如(AB)(AC)所標記的列所標記的列(可算出可算出)在行在行001,011,110,111處取處取1故故: (AB)(AC)=M001M011M110M111= (ABC)(ABC)(ABC)(ABC)二二.最大集的標準形式最大集的標準形式 定義定義: 設設A1,A2, Ar 是全集是全集U的子集的子集,形如形如 的集合稱為

39、由的集合稱為由A1,A2, Ar所產生的最大集所產生的最大集,其中每個其中每個 為為Ai 或或Ai (注意每個注意每個 中中Ai 或或Ai至少出現且只至少出現且只出現一個出現一個). 例如由例如由A.B.C產生的最大集為產生的最大集為:A B C A BC A BC A BC A BC A B C ABC ABC由乘法原理及定義知由乘法原理及定義知:由由A1,A2, Ar所產生的最大集所產生的最大集共有共有2r個個.但所有的最大集不能構成但所有的最大集不能構成U的分劃的分劃,交集非空交集非空.iriA1iAiA一般用一般用 表示最大集表示最大集 如如A1A2A3A4= A1A2A3A4 = 一

40、般一般下面討論最大集的成員表下面討論最大集的成員表: 按并集定義按并集定義 = 當且僅當當且僅當故故 只在行只在行123r處取處取0,而其余行處而其余行處取取1,如對如對 僅當僅當uA(記記0) uB(記記1)uC (記記0) 時時, u =A B C,故只在行故只在行010處取處取0,而其余而其余行都取行都取1,參閱下表參閱下表rM21rAAA210011M0010iiiiiAAAA10當當rM21iriA1rMuAuAur211,rM21010M010M下面看下面看 成員成員 表表A B C ABC A BC A BCAB C S =M000 =M010 =M100 =M101 0 0 0

41、 0 1 1 1 0 0 0 1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1其中其中S=進一步考察進一步考察A1,A2, Ar任意任意i個不同最大集的交個不同最大集的交101100010000MMMM101100010000MMMMirirrMMM122111211及其成員表及其成員表,上述交集僅在行上述交集僅在行111r,212r,i1ir處為處為0,其它行為其它行為1,這也這也表明了構造集合表明了構造集合 (ABC)(ABC

42、)(ABC)(ABC)成員表的方法成員表的方法.定理定理3 由由A1,A2, Ar 所產生任一集合所產生任一集合S或為全集或為由或為全集或為由A1,A2, Ar 所產生的若干不同的最大集的交所產生的若干不同的最大集的交.證明證明: 因此因此S的成員表中所對應的列必有的成員表中所對應的列必有K個個0,不為全集不為全集其中其中1K2r ,設這設這K個個0分別在行分別在行11 2r, 21 2r, K1 Kr,作如下最大集之交作如下最大集之交,用用T表示表示:T=將將T植于成員表的最后一列可知植于成員表的最后一列可知,這必有與這必有與S所在的列恒同所在的列恒同.krkrrMMM122111211則則

43、T=S,若若K=2r 則則T=U例例 求求S=(AB)(AB)最大集的標準形式最大集的標準形式,其中其中S由由A.B.C所產生所產生.解解:S的成員表為的成員表為A B C AB AC (AB)(AB) 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 0 1 所以所以S=(AB)(AB)=M000M010M100M101三三.關于集合的標準形式的進一步說明關于集合的標準形式的進一步說明: 由前兩段的討論可知由前兩段的討論可知:若把空集看作自身的最若把空集看作自

44、身的最小集的標準形式小集的標準形式(空集不能表為非空集合的并空集不能表為非空集合的并),把把全集全集U看作自身的最大集的標準形式看作自身的最大集的標準形式(全集不能表全集不能表為若干集合的交為若干集合的交),則可說則可說:每個集合都能表為最小每個集合都能表為最小集的標準形式和最大集的標準形式集的標準形式和最大集的標準形式. 討論集合討論集合S=B(A(BC)的最大集及最小的最大集及最小集的標準形式集的標準形式,由由A.B.C產生產生.先討論集合的成員表先討論集合的成員表:A B C CB A (B C ) B (A (B C ) 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1

45、1 1 0 1 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 1 S=M000M001M011M100M101 =(ABC)(ABC)(ABC) (ABC)(ABC)S=M010M110M111(ABC)(ABC)(ABC) 一般一般:若集合若集合S最小集和最大集的標準形式為最小集和最大集的標準形式為 S= S= 則集合則集合=11121r,l1l2 lr的交集為空集的交集為空集. 定理定理4 S是是A1,A2 , Ar產生的集合產生的集合,不記次序不記次序,則其則其最大最大(小小)集的標準形式是唯一的集的標準形式是唯一的. 定理定

46、理5 由由A1,A2 , Ar產生的集合相等的充要條件產生的集合相等的充要條件是它們的最大是它們的最大(小小)集的標準形式是一樣的集的標準形式是一樣的lrlrrMMM122111211mrmrrMMM122111211,2111211mrmmr下面用運算規律求集合的標準形式下面用運算規律求集合的標準形式:其中其中 S=B(A(BC)1.最小集最小集: S=B(A(BC)=(BA)(BBC) =(BAC) (BAC) (ABC)(ABC) = M111M110M0102.最大集最大集:S=B(A(BC)=(B(AA) (A B)(AC)=(BA)(B A) (A B C) (A B C ) (AB C) (AB C)=(BA C) (BA C)(B A C) (B A C) (A B C) (A B C )(AB C) =M000M001M100 M101 M011這與前面的結果相同這與前面的結果相同.1.P32.16T.2.P33.20T.3.設集合設集合A的基數的基數A=55 ,試問試問: 1.A有多少個子集有多少個子集; 2.有多少個子