離散數(shù)學(xué)第三章集合

離散數(shù)學(xué)第三章集合1第一頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

目標(biāo)

掌握集合論、代數(shù)系統(tǒng)、布爾代數(shù)、圖論的基本思想和方法，提高用集合論、代數(shù)系統(tǒng)、布爾代數(shù)、圖論的思想和方法分析問題和解決問題的能力。2第二頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

目錄序言第三章集合第四章關(guān)系第五章函數(shù)第六章代數(shù)系統(tǒng)第七章格與布爾系統(tǒng)第八章圖論3第三頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

DiscreteMathematics序言：離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，計(jì)算機(jī)科學(xué)基礎(chǔ)理論的核心課程。它充分描述了計(jì)算機(jī)科學(xué)的離散性特點(diǎn)，是隨著計(jì)算機(jī)科學(xué)的發(fā)展而逐步建立起來的新興的基礎(chǔ)性學(xué)科。本課程作為計(jì)算機(jī)科學(xué)的基礎(chǔ)性課程，把握離散數(shù)學(xué)的關(guān)鍵性問題，介紹五大塊內(nèi)容：集合論、代數(shù)系統(tǒng)、布爾代數(shù)、圖論、數(shù)理邏輯。這些和計(jì)算機(jī)科學(xué)密切相關(guān)的理論的結(jié)構(gòu)按排，既著重于各部分之間的緊密聯(lián)系，又深入探討各部分內(nèi)容的概念、例子、理論、算法、以及實(shí)際應(yīng)用。4第四頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)敘述恰當(dāng)嚴(yán)謹(jǐn)，論證詳盡嚴(yán)密，內(nèi)容新穎豐富是本課程的特點(diǎn)。離散數(shù)學(xué)具有抽象性、非線性、非尋繹性、構(gòu)造性、結(jié)構(gòu)性、整體性等結(jié)構(gòu)性數(shù)學(xué)特點(diǎn)。證明方法除了大量的運(yùn)用常用的（數(shù)學(xué)）歸納法、演繹法、反證法、歸謬法、二難法、二分法、枚舉法（窮舉法）、相容排斥法等方法之外，特別著重于存在性、結(jié)構(gòu)性、構(gòu)造性方法，以及各部分內(nèi)容自己所特有的方法（比如圖論的刪點(diǎn)增點(diǎn)方法、刪邊增邊方法、伸路蹦圈方法）。5第五頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)集合論在計(jì)算機(jī)科學(xué)中的應(yīng)用集合論包括集合﹑關(guān)系和函數(shù)3部分

1)集合集合不僅可以表示數(shù)，而且可以像數(shù)一樣進(jìn)行運(yùn)算，還可以用于非數(shù)值信息的表示和處理，如數(shù)據(jù)的增加、刪除、排序以及數(shù)據(jù)間關(guān)系的描述，有些很難用傳統(tǒng)的數(shù)值計(jì)算來處理的問題，卻可以用集合來處理。因此，集合論在程序語言、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫與知識(shí)庫、形式語言和人工智能等領(lǐng)域得到了廣泛的應(yīng)用。

2)關(guān)系關(guān)系也廣泛地應(yīng)用于計(jì)算機(jī)科學(xué)技術(shù)中，例如計(jì)算機(jī)程序的輸入和輸出關(guān)系、數(shù)據(jù)庫的數(shù)據(jù)特性關(guān)系和計(jì)算機(jī)語言的字符關(guān)系等，是數(shù)據(jù)結(jié)構(gòu)、情報(bào)檢索、數(shù)據(jù)庫、算法分析、計(jì)算機(jī)理論等計(jì)算機(jī)領(lǐng)域中的良好數(shù)據(jù)工具。另外，

關(guān)系中劃分等價(jià)類的思想也可用6第六頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)于求網(wǎng)絡(luò)的最小生成樹等圖的算法中。

3)函數(shù)函數(shù)可以看成是一種特殊的關(guān)系，計(jì)算機(jī)中把輸入、輸出間的關(guān)系看成是一種函數(shù)。類似地，在開關(guān)理論、自動(dòng)機(jī)原理和可計(jì)算性理論等領(lǐng)域中，函數(shù)都有極其廣泛的應(yīng)用，其中雙射函數(shù)是密碼學(xué)中的重要工具。7第七頁，共六十二頁，編輯于2023年，星期日

集合全集空集單元素集子集冪集交集并集余集差集環(huán)和集環(huán)積集8第八頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

第三章集合(set)

§１.集合理論中的一些基本概念

個(gè)體與集合之間的關(guān)系

集合的表示法

集合與集合之間的關(guān)系

冪集

§2.集合代數(shù)集合的基本運(yùn)算

集合的補(bǔ)運(yùn)算

集合的交運(yùn)算和并運(yùn)算

集合的宏運(yùn)算9第九頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

第三章集合(set)§１.集合理論中的一些基本概念

集合概念將作為一個(gè)不言自明的元概念（基本概念）。它不能用別的術(shù)語來精確的定義，只能用別的術(shù)語來加以說明。它本身就是用來定義其它概念的概念。我們來看看一些關(guān)于什么是集合的各種不同的說法，以便加深對(duì)集合這個(gè)元概念的理解。

1.莫斯科大學(xué)的那湯松教授說：凡具有某種特殊性質(zhì)的對(duì)象的匯集稱之為集。

2.復(fù)旦大學(xué)的陳建功教授說：凡可供吾人思維的，不論它有形或無形，都叫做物。具有某種條件的物，稱它們的全部謂之一集。

3.南開大學(xué)的楊宗磐教授說：

10第十頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

集就是“烏合之眾”。不考慮怎樣“烏合”起來的，眾可以具體，可以抽象。這種烏合性被歸納為集合的一條性質(zhì)

任意性：任意性是說組成集合的元素任意；構(gòu)成的法則任意；什么都可以構(gòu)成集合，不加任何限制。任意性是集合的四大性質(zhì)之一。

4.集合論之父G.Cantor（1845-1918）說：集合是由總括某些個(gè)體成一個(gè)整體而成的。對(duì)于每個(gè)個(gè)體，只設(shè)其為可思考的對(duì)象，辨別它的異同。個(gè)體之間并不需要有任何關(guān)系。

11第十一頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

因此，對(duì)于集合，我們接受以下事實(shí)：

(a)承認(rèn)集合的存在性。即，接受集合概念；

(b)承認(rèn)集合是由一些個(gè)體（對(duì)象）組成的。這些個(gè)體稱為該集合的成員或元素（member,element）；

(c)承認(rèn)個(gè)體是可辯認(rèn)的。即，一個(gè)個(gè)體要么是一個(gè)集合的成員，要么不是；二者必居其一，也只居其一。這種存在性，可辯認(rèn)性被歸納為集合的一條性質(zhì)

確定性：確定性是說集合確定；個(gè)體確定；集合與個(gè)體之間的關(guān)系確定。因此，經(jīng)典集合的邊界是分明的、清晰的。確定性是集合的四大性質(zhì)之一。12第十二頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

綜上所述集合的概念有三要素：

1.個(gè)體（元素）

2.個(gè)體的可辨認(rèn)性

3.集合（動(dòng)詞，匯到一塊）通常用小寫拉丁字母表示個(gè)體：a、b、c、d、…通常用大寫拉丁字母表示集合：A、B、C、D、…有時(shí)還用德文花寫字母表示集合：?,?,?,?,?,?,…關(guān)于個(gè)體的辨認(rèn)有賴于各方面公認(rèn)的知識(shí)。一.個(gè)體與集合之間的關(guān)系：個(gè)體與集合之間的關(guān)系稱為屬于關(guān)系。對(duì)于某個(gè)個(gè)體a和某個(gè)集合A而言，只有兩種可能：

(1)a屬于（belongto）A，記為aA（記號(hào)是希臘字i的第一個(gè)字母，意思是“是”。由意大利數(shù)學(xué)家G.Peano首先采用），同時(shí)稱a是A的元素或A13第十三頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)的成員。

(2)a不屬于A，記為aA或a

A，稱a不是A的元素或a不是A的成員。

判斷個(gè)體a屬于A還是不屬于A，必須使用個(gè)體的可辨認(rèn)性，而且個(gè)體的可辨認(rèn)性是無二義性的，即或者a屬于A或者a不屬于A，二者居其一且只居其一。AaAaAaAa14第十四頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)集合論是一種語言。它可以作為別的學(xué)科的描述工具語言。二.集合的表示法：我們規(guī)定用花括號(hào)——{}表示集合。(1)文字表示法：用文字表示集合的元素，兩端加上花括號(hào)。

{在座的同學(xué)}；

{奇數(shù)}；

{去年的下雨天}；

{高等數(shù)學(xué)中的積分公式}；

{閉區(qū)間[0,1]上的連續(xù)函數(shù)}；比較粗放。比較適合在對(duì)集合中的元素了解甚少、不詳，難以用精確的數(shù)學(xué)語言來刻劃時(shí)使用。(2)元素列舉法（羅列法）：15第十五頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)將集合中的元素逐一列出，兩端加上花括號(hào)。

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

{風(fēng)，馬，牛}；

{2，4，6，8，10，…}；

{3，7，11，15，19，…}；比較適合集合中的元素有限（較少或有規(guī)律），無限（離散而有規(guī)律）的情況。(3)謂詞表示法：

{x:P(x)}或者{x︱P(x)}

其中：P表示x

所滿足的性質(zhì)（一元謂詞）。

{x:x

I（且）x8}={…，-3，-2，-1，0，1，2，3，4，5，6,7}；16第十六頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

{x:

x2=1}；

{y

:

y

是開區(qū)間(a,b)上的連續(xù)函數(shù)}；（混合表示法）

{使

x2=1的實(shí)數(shù)}

={1，-1}

={x

:

x2=1}比較適合在對(duì)集合中的元素性質(zhì)了解甚詳，且易于用精確的數(shù)學(xué)語言來刻劃時(shí)使用。外延(extension)：集合{x:P(x)}稱為性質(zhì)謂詞P(x)的外延；內(nèi)涵(intension,connotation)：性質(zhì)謂詞P(x)稱為集合{x:P(x)}的內(nèi)涵；由此看到，采用謂詞法定義集合，關(guān)鍵是要得出內(nèi)涵P(x)，并且顯然有如下的17第十七頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)概括原理：集合{x:P(x)}恰由那些滿足性質(zhì)謂詞P(x)的元素組成。即

x{x:P(x)}(當(dāng)且僅當(dāng))

P(x)真。悖論(paradox)：所謂悖論是指這樣一個(gè)所謂的命題P，由P真立即推出P假；由P假立即推出P真；即

P真P假。理發(fā)師悖論：某偏遠(yuǎn)小山村僅有一位理發(fā)師。這位理發(fā)師規(guī)定：他只給那些不給自己刮臉的人刮臉。那么要問：這位理發(fā)師的臉由誰來刮？如果他給自己刮臉，那么，按他的規(guī)定，他不應(yīng)該給自己刮臉；如果他不給自己刮臉，那么，按他的規(guī)定，他應(yīng)該給自己刮臉；

18第十八頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)羅素悖論(Russellparadox(1902))：羅素1902年在集合論中也發(fā)現(xiàn)了如下的悖論。他構(gòu)造了這樣一個(gè)集合

S={x:xx}然后他提出問題：SS？如果SS，那么，按羅素給S的定義，則應(yīng)有SS；如果SS，那么，按羅素給S的定義，則應(yīng)有SS；羅素悖論的發(fā)現(xiàn)，幾乎毀滅集合論，動(dòng)搖數(shù)學(xué)的基礎(chǔ)，傾危數(shù)學(xué)的大廈。直接引發(fā)了數(shù)學(xué)的第三次危機(jī)。

19第十九頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

為了解決集合論中的悖論問題，人們產(chǎn)生了類型論和形式化公理化集合論(ZF和ZFC公理系統(tǒng))，以求排除集合論中的悖論。近年來，基于ZFC公理系統(tǒng)和一階邏輯(謂詞邏輯)，人們提出了抽象的計(jì)算機(jī)程序設(shè)計(jì)語言__Z語言。在公理化集合論中，人們引進(jìn)了類(class)的概念。20第二十頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)本章我們所講解的集合論是‘樸素(naive)’集合論；所討論的集合一般也不會(huì)產(chǎn)生悖論。三.集合的名字：

(1)大寫的拉丁字母：例如A={x:x=1},B={-1,1}；

(2)小寫的希臘字母：例如={a,b,c},={n:nN3︱n}；

(3)花寫的徳文字母：例如={y:yR0y1},

={u:uIu+30}；不夠用時(shí)可以加下標(biāo)。

同一個(gè)集合可以有幾個(gè)名字。四.集合的相等（equality）：

外延性原理：兩個(gè)集合相等，當(dāng)且僅當(dāng)，它們的成員完全相同。即

A=Bx(xAxB)；21第二十一頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

兩個(gè)集合不相等，記為AB；根據(jù)這個(gè)定義，關(guān)于集合我們可得下列性質(zhì)：

(1)無序性：集合中的元素是無序的。例如

{a,b,c}={b,a,c}={b,c,a}

因此，為了使用方便，我們可任意書寫集合中元素的順序。但一般情況下，通常采用字母序、字典序；有時(shí)，還需要強(qiáng)行命名一種序；無序性是集合的四大性質(zhì)之一。

(2)無重復(fù)性：集合中元素的重復(fù)是無意義的。例如

{a,a,a,a,b,b,b,c,c}={a,b,c}

包(bag)：若允許元素重復(fù)稱為包。例如

{a,a,a,a,b,b,b,c,c}

一般記為{4a,3b,2c}22第二十二頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

無重復(fù)性是集合的四大性質(zhì)之一。五.空集(empty,null,voidset)：記為空集是沒有成員的集合。即

x(x)(所謂的空集公理)；所以={}；空集是集合（作這點(diǎn)規(guī)定是運(yùn)算封閉性的要求）?？占俏ㄒ坏?。因?yàn)槿粲袃蓚€(gè)空集，則它們有完全相同的元素（都沒有任何元素），所以它們相等，是同一集合。六.全集（universeofdiscourse）：記為X全集是所要研究的問題所需的全部對(duì)象（元素）所構(gòu)成的集合。全集給個(gè)體（研究的對(duì)象）劃定適當(dāng)?shù)姆秶?3第二十三頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)全集一般用一個(gè)矩形框來表示：七.單元素集合（singletonset）：

只含一個(gè)元素的集合稱為單元素集。例如{a}；{張三}；{}左邊是空集；右邊不是空集，而是單元素集合，有一個(gè)成員；這說明：差別在于級(jí)別。即，右邊的集合級(jí)別高。單元素集合是構(gòu)造復(fù)雜集合的‘原子’。

X24第二十四頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)八.子集（subset）：對(duì)于兩個(gè)集合A，B，若A中的每個(gè)元素x都是B

的一個(gè)元素，則稱A包含在B中（或者說B包含A），記為AB。同時(shí)稱A是B的子集（稱B是A的超集(superset)）。即

ABx(xAxB)

。真子集（propersubset）：稱A是B的真子集或者說A真包含在B中（或者說B真包含A），記為AB。即

ABX例.X={a,b,c,d,e,f},A={a,c,d},B={a,b,c,d}。則。AB。25第二十五頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

AB

ABAB。子集的兩種特殊情況（平凡子集）：

(1)空集（見下面定理2）；

(2)每個(gè)集合自己（見下面定理1的(1)）；九.集合與集合之間的關(guān)系:

集合與集合之間的關(guān)系有四種。列舉如下

(1)B包含A，ABx(xAxB)

；

(2)A包含B，BAx(xBxA)；

(3)A等于B，A=Bx(xBxA)

ABBA；

(4)A與B互不包含，(AB)(BA)x(xAxB)y(yByA)；

例.X={a,b,c,d,e,f},A={a,c,d},B={a,c,d,e}。則AB。26第二十六頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)定理1.設(shè)A,B,C為任意三個(gè)集合。那么

(1)自反性：AA(每個(gè)集合是它自己的子集)；

(2)反對(duì)稱性：ABBA

A=B；

(3)傳遞性：ABBC

AC；這說明包含關(guān)系是集合間的半序關(guān)系(參見第二章§6)。[證明].（采用邏輯法）

(1)x(xAxA)(同一律：

pp)

AA

ＢＡxyX例.X={a,b,c,d,e,f},A={a,c,d},B={c,d,e}。則(AB)(BA)。即A與B互不包含27第二十七頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

所以包含關(guān)系是自反的；

(2)ABBA

x(xAxB)x(xBxA)x((xAxB)(xBxA))(量詞對(duì)的分配律：xA(x)xB(x)x(A(x)B(x)))x(xAxB)A=B

所以包含關(guān)系是反對(duì)稱的；

(3)ABBC

x(xAxB)x(xBxC)x((xAxB)(xBxC))(量詞對(duì)的分配律：xA(x)xB(x)x(A(x)B(x)))

28第二十八頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

x(xAxC)((假言)三段論原則：(pq)(qr)pr)AC

所以包含關(guān)系是傳遞的。定理2.空集是任一集合的子集。即A。[證明].(采用邏輯法)x(x）(空集的定義)x(x)x(xxA)(由析取構(gòu)成式及聯(lián)結(jié)詞歸約有：

p(pq)(pq))A。29第二十九頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)十.冪集(powerset)：定義1.冪集一個(gè)集合A的所有子集構(gòu)成的集合稱為A的冪集。記為2A(或P(A)或

P(A))

，即

2A={B：BA}。顯然，A的兩個(gè)平凡子集和A都屬于A的冪集。即

2A

，A2A

。例1.若A={1,2,3}，則

2A={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}。注：(1)包含關(guān)系兩邊必須是集合，并且這兩個(gè)集合的級(jí)別（廣義上）相同；

(2)屬于關(guān)系左邊是元素（廣義上），右邊是集合，兩邊級(jí)別差一級(jí)。30第三十頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)定義2.基數(shù)

一個(gè)有窮集合（有限集合——元素個(gè)數(shù)有限的集合）A中元素的個(gè)數(shù)稱為A的基數(shù)。記為|A|(或A，)。顯然基數(shù)有以下兩個(gè)性質(zhì)：

(1)齊性：||=0；

(2)非負(fù)性：|A|0（對(duì)任何集合A

）；另外，由于2={}，所以|2|=1。一般地，關(guān)于冪集有以下結(jié)果定理3.

若A是有限集合，則有|2A|=2|A|

。這個(gè)定理也說明，我們?yōu)槭裁窗岩磺凶蛹瘶?gòu)成的集合稱為冪集。[證明].由于集合A有限，故可設(shè)A={a1，a2，…，an}，于是31第三十一頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

|A|=n。A的子集按其基數(shù)大小可分為0，1，2，…，n共n+1類。

A的所有k個(gè)元素的子集（基數(shù)為k的類）為從n個(gè)元素中取k個(gè)元素的組合數(shù)。另外，因A，故（按加法原理）

2A=1+++…++…+=

但由于二項(xiàng)式定理(x+y)n=xkyn-k

令x=y=1，則有2n=，

從而，有|2A

|=2n=2|A|

。32第三十二頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)定理4.

若A，B是兩個(gè)集合，那么，A=B2A=2B。[證明].）：由冪集的定義，顯然；)：一方面，

AA

(自反性)A2A

(因?yàn)?A={B:BA})

A2B(充分性條件：2A

=2B)

AB(因?yàn)?B

={A:AB})另一方面，

BB

(自反性)B2B

(因?yàn)?B

={A:AB})

B2A(充分性條件：2A=2B)

BA(因?yàn)?A

={B:BA})

因此，由包含關(guān)系的反對(duì)稱性，得到

A=B。33第三十三頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)§2

.集合代數(shù)集合的基本運(yùn)算定義1.余(補(bǔ)或非)運(yùn)算((absolute)complment)

設(shè)X是全集。一元運(yùn)算:2X2X

對(duì)任何集合AX，使得A={x

:

xXxA}(當(dāng)全集明確時(shí)，

A

={x

:

xA})稱為集合的余運(yùn)算。稱A是A關(guān)于X的余集。余運(yùn)算有時(shí)也記為，或，或A或A。

XAA

集合A以外的元素!34第三十四頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)例1.X={a,b,c,d,e,f},A={a,c,d}。則

A

={b,e,f}。定理1.余運(yùn)算基本定理

設(shè)X是全集，A，B是X的子集。則

(1)反身律(對(duì)合律)：(A)=A；

(2)換質(zhì)位律（逆否律）；ABB

A；

(3)A=

BA=

B；

(4)零壹律：X=，=X。[證明].(采用邏輯法)(1)對(duì)任何元素xX，x(A)

xA

xA

所以(A)=A；35第三十五頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

(2)對(duì)任何元素xX，xB

xBxA

(條件：AB)xA

所以B

A

；

(4)對(duì)任何元素x，

xXxXx

所以X=；對(duì)任何元素x，xxxX(已證：X=)xX

所以=X。36第三十六頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)定義2.交運(yùn)算，并運(yùn)算(intersection,union)

設(shè)X是全集。

(1)二元運(yùn)算∩

:2X2X2X

對(duì)任何集合A,BX，使得

A∩B={x:

xAxB}稱為集合的交運(yùn)算。稱A∩B為A與B的交集?！捎⒄Z讀作cap（帽子）。若A∩B=，則稱A與B互不相交((pairwise)disjoint)。

(2)二元運(yùn)算∪:2X2X2X

對(duì)任何集合A,BX，使得

A∪B={x:

xAxB}稱為集合的并運(yùn)算。稱A∪B為A與B的并集?！扔⒄Z讀作cup（酒杯）。

同時(shí)屬于集合A和集合B的元素!

至少屬于集合A和集合B之一的元素!37第三十七頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

例2.設(shè)X={a,b,c,d,e,f},A={a,c,d,f},B={b,d,f}。則A∩B={d,f},

A∪B={a,b,c,d,f}。定理2.交、并、余運(yùn)算的基本定理

設(shè)X是全集，A，B，C是X的三個(gè)子集。則

(1)冪等律：A∩A=A，A∪A=A；

(2)互補(bǔ)律：A∩A=，A∪A=X；

XXA∩BA∪BABBA38第三十八頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)(2’)零壹律：A∩X=A，A∪X=X；

(全集是交的幺元,并的零元)(2”)零壹律：A∩=，A∪=A；

(空集是交的零元,并的幺元)(3)上界：AA∪B，B

A∪B；下界：A∩BA，A∩BB

；

(3’)上確界：

ACBCA∪BC；

(并集A∪B是同時(shí)包含A和B的集合中最小的一個(gè))

(3”)下確界：CACBCA∩B；

(交集A∩B是同時(shí)被A和B所包含的集合中最大的一個(gè))(4)吸收律：A∩(A∪B)=A，A∪(A∩B)=A；

(5)交換律：A∩B=B∩A，A∪B=B∪A；

39第三十九頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)(6)結(jié)合律：(A∩B)∩C=A∩(B∩C)，

(A∪B)∪C=A∪(B∪C)；

(7)分配律：A∩(B∪C)=(A∩B)∪(A∩C)，

A∪(B∩C)=(A∪B)∩(A∪C)；[證明].(3’)(采用邏輯法)

對(duì)任何元素xX

，

xA∪B

xAxBxCxC

(已知條件：AC，BC)

xC(冪等律：ppp)

所以，A∪BC。

(7)先證：A∩(B∪C)(A∩B)∪(A∩C)(采用元素法)

對(duì)任何元素xX

，若xA∩(B∪C)，則xA，且xB∪C。于是x

A，且xB或者xC。

40第四十頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

若xB，則xA且xB，于是xA∩B；

若xC，則xA且xC，于是xA∩C；綜合xA∩B或者xA∩C，因此

x(A∩B)∪(A∩C)；所以，A∩(B∪C)(A∩B)∪(A∩C)。次證：(A∩B)∪(A∩C)A∩(B∪C)(采用包含法)

由(3)有A∩BA，A∩BBB∪C（逐步放大法）。于是根據(jù)(3”)可得A∩BA∩(B∪C)

同理可得A∩CA∩(B∪C)于是根據(jù)(3’)可得

(A∩B)∪(A∩C)A∩(B∪C)。最后，根據(jù)包含關(guān)系的反對(duì)稱性，就得到

A∩(B∪C)=(A∩B)∪(A∩C)。41第四十一頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)定理3.deMorgan律（也叫對(duì)偶律）

設(shè)A，B為兩個(gè)集合。則

(1)(A∪B)=A∩B，

(2)(A∩B)=A∪B。[證明].只證(1)

先證：(A∪B)A∩B(采用包含法)

由定理2(3)有AA∪B，BA∪B于是由定理1(2)可得(A∪B)A，(A∪B)B再用定理2(3”)，就有(A∪B)A∩B；

次證：A∩B(A∪B)(采用邏輯法)

對(duì)任何元素xX

，

xA∩B42第四十二頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

xAxB

xAxB

xA∪B(否則xA∪B

xAxB，這與xAxB矛盾)

x(A∪B)

所以A∩B(A∪B)

最后，根據(jù)包含關(guān)系的反對(duì)稱性，就得到

(A∪B)=A∩B。定理4

設(shè)A，B為兩個(gè)集合。則下面三式等價(jià)。

(1)A

B；

(2)A∪B=B；

(3)A∩B=A。43第四十三頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)[證明].(采用循環(huán)論證法)(1)(2)：(采用包含法)

首先，根據(jù)定理2(3)，我們得到BA∪B；其次，由已知條件AB，及自反性BB，根據(jù)定理2(3’)，我們得到A∪BB；最后，根據(jù)包含關(guān)系的反對(duì)稱性，我們就得到

A∪B=B。

(2)(3)：(采用變換法(公式法))A∩B=A∩(A∪B)(根據(jù)(2)A∪B=B)=A(根據(jù)定理2(4)吸收律)

即A∩B=A。

(3)(1)：(采用：包含法)A=A∩B(根據(jù)(3)A∩B=A)

B(根據(jù)定理2(3)A∩BB)44第四十四頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

即AB。定義3

.差運(yùn)算(difference)

設(shè)X是全集。二元運(yùn)算\:2X2X2X

對(duì)任何集合A,BX，使得A\B={x

:

xAxB}稱為集合的差運(yùn)算。稱A\B為A和B的差集。差集有時(shí)也稱為相對(duì)補(bǔ)(relativecomplement)。

而余運(yùn)算可看成絕對(duì)補(bǔ)。即A=

X\A。A\BBAX

屬于集合A但不屬于集合B的元素!45第四十五頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)例3.X={a,b,c,d,e,f},A={a,c,d,f},B={b,d,f}。則A\B={a,c},B\A=。

由差運(yùn)算、交運(yùn)算、余運(yùn)算的定義知A\B=A∩B。由于差運(yùn)算可以由交、并、余運(yùn)算線性表出，因此稱差運(yùn)算為宏運(yùn)算。請(qǐng)問：交、并、余三個(gè)運(yùn)算是線性無關(guān)的嗎？注：答案是否定的。實(shí)際上，根據(jù)反身律、deMorgan律，我們有

A∩B=(A∪B)；

A∪B=(A∩B)。

46第四十六頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)定理5.差運(yùn)算基本定理設(shè)X是全集，A，B，C是X的三個(gè)子集。則

(1)A\BA；

(2)ABA\B=；

(3)A\A=；

(4)X\A=A；A\X=；

(5)A\=A；\A=；

(6)A∩(B\C)=(A∩B)\(A∩C)(交對(duì)差的分配律)；

(7)A\(B\C)=(A\B)∪(A∩C)；

(8)A\(B∪C)=(A\B)∩(A\C)(相對(duì)補(bǔ)的deMorgan律)；

(9)A\(B∩C)=(A\B)∪(A\C)(相對(duì)補(bǔ)的deMorgan律)。47第四十七頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)[證明].(采用包含法和變換法(公式法)法)(1)A\B=A∩B

A(根據(jù)定理2(3)A∩BA)；

(2)A\B=A∩B=(A∩B)∩B

(由已知條件AB根據(jù)定理4(3)有A∩B=A)=A∩(B∩B)(結(jié)合律)=A∩(互補(bǔ)律B∩B=)=(零壹律)；

(3)，(4)，(5)：顯然；

(6)A∩(B\C)=A∩(B∩C)=∪(A∩B∩C)(零壹律,結(jié)合律)=(B∩)∪(A∩B∩C)(零壹律)48第四十八頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

=(B∩A∩A)∪(A∩B∩C)(互補(bǔ)律,結(jié)合律)=(A∩B∩A)∪(A∩B∩C)(交換律)=(A∩B)∩(A∪C)(分配律)=(A∩B)∩(A∩C)(deMorgan律)=(A∩B)\(A∩C)；

(7)A\(B\C)=A\(B∩C)=A∩(B∩C)=A∩(B∪C)(deMorgan律,反身律)=(A∩B)∪(A∩C)(分配律)=(A\B)∪(A∩C)；

(8)A\(B∪C)=A∩(B∪C)=A∩(B∩C)(deMorgan律)=(A∩A)∩(B∩C)(冪等律)

49第四十九頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)=(A∩B)∩(Ａ∩C)(結(jié)合律，交換律)=(A\B)∩(A\C)；

(9)A\(B∩C)=A∩(B∩C)=A∩(B∪C)(deMorgan律)=(A∩B)∪(Ａ∩C)(分配律)=(A\B)∪(A\C)。定義4.

對(duì)稱差（環(huán)和）運(yùn)算(symmetricdifference)

設(shè)X是全集。二元運(yùn)算

:2X2X2X

，

對(duì)任何集合A,BX，使得

AB={x:(xAxB)(xBxA)}稱為集合的對(duì)稱差運(yùn)算。稱AB為A和B的對(duì)稱差集。

屬于集合A和集合B，但不同時(shí)屬于集合A和集合B的元素!50第五十頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)由環(huán)和運(yùn)算和并、差運(yùn)算的定義可知

AB=(A\B)∪(B\A)由環(huán)和運(yùn)算和交、并、余運(yùn)算的定義可知

AB=(A∩B)∪(B∩A)因此環(huán)和運(yùn)算也是宏運(yùn)算。例4.設(shè)X={a,b,c,d,e,f},A={a,c,d,f},B={b,d,f}。則A\B={a,c},B\A=,于是AB={a,b,c}。

ABXAB51第五十一頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)定理6.環(huán)和運(yùn)算基本定理設(shè)X是全集，A，B，C是X的三個(gè)子集。則

(1)AB=(A∪B)\(A∩B)=(A∪B)∩(A∪B)；

(2)A=A（空集是環(huán)和的幺元）；

AX=A；

(3)AA=（自己是自己（環(huán)和）的逆元）；

AA=X；

(4)AB=AB；

(5)(AB)=AB=AB

；

(6)交換律：AB=BA；

(7)結(jié)合律：A(BC)=(AB)C；

(8)分配律：A∩(BC)=(A∩B)(A∩C)(交對(duì)環(huán)和的)；

(9)消去律：AB=ACB=C。52第五十二頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)[證明].(采用變換法(公式法))只證(5)，(7)，(9)(5)(AB)=((A∩B)∪(A∩B))

=(A∩B)∩(A∩B)(deMorgan律)=(A∪B)∩(A∪B)(deMorgan律，反身律)=((A∪B)∩A)∪((A∪B)∩B)(分配律)=(A∩A)∪(B∩A)∪(A∩B)∪(B∩B)(分配律，結(jié)合律)=(A∩A)∪(A∩B)∪(A∩B)∪(B∩B)(交換律)=∪(A∩B)∪(A∩B)∪(互補(bǔ)律)=(A∩B)∪(A∩B)(零壹律)AB=(A∩B)∪(A∩B)=(A∩B)∪(A∩B)(反身律)=(A∩B)∪(A∩B)(交換律)53第五十三頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)

AB=(A∩B)∪(A∩B)=(A∩B)∪(A∩B)(反身律)

所以(AB)=AB=AB=(A∩B)∪(A∩B)；

(7)A(BC)=(A∩(BC))∪(A∩(BC))=(A∩((B∩C)∪(B∩C)))∪(A∩((B∩C)∪(B∩C)))(根據(jù)本定理的(5)的證明)=(A∩B∩C)∪(A∩B∩C)∪(A∩B∩C)∪(A∩B∩C)(分配律，結(jié)合律)(AB)C=((AB)∩C)∪((AB)∩C)=(((A∩B)∪(A∩B))∩C)∪(((A∩B)∪(A∩B))∩C)(根據(jù)本定理的(5)的證明)

(BC)=BC=BC=(B∩C)∪(B∩C)(1,1.1)=7,(1,0,0)=4,(0,1,0)=2,(0,0,1)=1(AB)=AB=AB=(A∩B)∪(A∩B)54第五十四頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)=(A∩B∩C)∪(A∩B∩C)∪(A∩B∩C)∪(A∩B∩C)(分配律，結(jié)合律)=(A∩B∩C)∪(A∩B∩C)∪(A∩B∩C)∪(A∩B∩C)(交換律，結(jié)合律)

所以A(BC)=(AB)C；

(9)B=B(根據(jù)本定理的(2))=(AA)B(根據(jù)本定理的(3))=A(AB)(根據(jù)本定理的(7)結(jié)合律)=A(AC)(已知條件AB=AC)=(AA)B(根據(jù)本定理的(7)結(jié)合律)=C(根據(jù)本定理的(3))=C(根據(jù)本定理的(2))。(1,1.1)=7,(1,0,0)=4,(0,1,0)=2,(0,0,1)=155第五十五頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)定義5

.環(huán)積運(yùn)算設(shè)X是全集。二元運(yùn)算

:2X2X2X

對(duì)任何集合A,BX，使得

AB={x:(xAxB)(xBxA)}稱為集合的環(huán)積運(yùn)算。稱AB為A和B的環(huán)積集。由環(huán)積運(yùn)算和交、并、余運(yùn)算的定義可知

AB=(A∪B)∩(B∪A)

因此環(huán)積運(yùn)算也是宏運(yùn)算。ABXAB56第五十六頁，共六十二頁，編輯于2023年，星期日離散數(shù)學(xué)例5.設(shè)X={a,b,c,d,e,f},A={a,c,d,f},B={b,d,f}。則A∪B={a,c,d,e,f},B∪A={b,d,e,f},于是

AB={d,e,f}。定理7.環(huán)積運(yùn)算基本定理

設(shè)X是全集，A，B，C是X的三個(gè)子集。則

(1)AB=(A∩B)∪(A