離散數(shù)學(xué)(DiscreteMathematics)祁偉電話Q:826105276使用教材書名：離散數(shù)學(xué)（第三版）“十一五”國(guó)家規(guī)劃教材主編：鄧輝文出版社：清華大學(xué)出版社講授：第1章_第6章參考書目1、邵學(xué)才.離散數(shù)學(xué)（第二版）.清華大學(xué)出版社.(應(yīng)用型規(guī)劃教材)2、周忠榮.離散數(shù)學(xué)及其應(yīng)用.清華大學(xué)出版社.3、王禮萍.離散數(shù)學(xué)簡(jiǎn)明教程.清華大學(xué)出版社.(高職教材)4、耿素云,屈婉玲.離散數(shù)學(xué)（修訂版）.高等教育出版社.(十五規(guī)劃教材，北京大學(xué))考核方式期末成績(jī)=平時(shí)成績(jī)+期末試卷成績(jī)平時(shí)成績(jī)20分平時(shí)成績(jī)=出勤+小測(cè)驗(yàn)+作業(yè)出勤=10

小測(cè)驗(yàn)=5

作業(yè)=5（獨(dú)立、自主）期末試卷成績(jī)80分。研究對(duì)象

離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及其相互之間關(guān)系的一門學(xué)科，它與當(dāng)今計(jì)算機(jī)所處理的對(duì)象相一致。

離散數(shù)學(xué)是研究計(jì)算機(jī)科學(xué)的基本數(shù)學(xué)工具和最合適的理論手段；是計(jì)算機(jī)類專業(yè)的重要課程。學(xué)習(xí)目的

離散數(shù)學(xué)是計(jì)算機(jī)及相關(guān)專業(yè)的一門核心課程，不是一門純數(shù)學(xué)課程，而是計(jì)算機(jī)學(xué)科的專業(yè)基礎(chǔ)課程。

1、為后繼課程提供必要的數(shù)學(xué)基礎(chǔ)

2、培養(yǎng)學(xué)生抽象思維能力和嚴(yán)密的邏輯推理能力。基本內(nèi)容（1）一、集合與關(guān)系：是離散數(shù)學(xué)研究的重點(diǎn)內(nèi)容

1、Chapter1集合、映射與運(yùn)算：集合是現(xiàn)代數(shù)學(xué)的最基本概念，映射是現(xiàn)代數(shù)學(xué)的基本概念，是本書的重點(diǎn)。

2、Chapter2關(guān)系：是刻畫聯(lián)系的數(shù)學(xué)模型。二、數(shù)理邏輯：研究思維形式及思維規(guī)律尤其是推理的學(xué)科。

1、Chapter3命題邏輯：研究的主要對(duì)象是命題。

2、Chapter4謂詞邏輯：研究原子命題的內(nèi)部形式結(jié)構(gòu)及其邏輯關(guān)系。基本內(nèi)容（2）三、代數(shù)結(jié)構(gòu)：研究有一般元素組成的集合上的運(yùn)算，以及運(yùn)算滿足一些給定的數(shù)學(xué)結(jié)構(gòu)的性質(zhì)。

1、Chapter5(1)代數(shù)結(jié)構(gòu)：計(jì)算機(jī)系統(tǒng)本身就是一種代數(shù)結(jié)構(gòu)。

2、Chapter5(2)群、環(huán)和域：在形式語言與自動(dòng)機(jī)理論學(xué)科中發(fā)揮作用。

3、Chapter5(3)格與布爾代數(shù)：在自動(dòng)推理和邏輯電路設(shè)計(jì)的分析和優(yōu)化等問題中得到應(yīng)用。四、圖論：廣泛應(yīng)用與解決現(xiàn)實(shí)問題。

1、Chapter6圖論：主要研究數(shù)據(jù)結(jié)構(gòu)中圖的相關(guān)性質(zhì)。

2、Chapter7幾類特殊的圖：介紹生活和研究中實(shí)際的圖論的問題。第1章集合、映射與運(yùn)算1.1集合的有關(guān)概念1.2映射的有關(guān)概念1.3運(yùn)算的定義及性質(zhì)1.4集合的運(yùn)算1.5集合的劃分與覆蓋第1章集合、映射與運(yùn)算集合是現(xiàn)代數(shù)學(xué)的最基本概念.映射又稱為函數(shù),它是現(xiàn)代數(shù)學(xué)的基本概念,可以借助于集合下定義.運(yùn)算本質(zhì)上是映射,但有其特殊性.(關(guān)系也是集合)集合、映射、運(yùn)算及關(guān)系是貫穿于本書的一條主線.1.1.1集合

集合（set）:是指具有某種特定性質(zhì)的對(duì)象匯集成的一個(gè)整體。元素（element）：集合中的每一個(gè)對(duì)象稱為集合的元素。通常用大寫字母表示集合，用小寫字母表示集合中的元素。在數(shù)學(xué)中常用{}表示整體.在討論集合時(shí)，為避免出現(xiàn)某些悖論，應(yīng)指定討論范圍，這個(gè)范圍也是一個(gè)集合，稱為全集或論域，記作U。文氏圖用矩形框表示。A隸屬關(guān)系集合與集合中元素的關(guān)系——隸屬關(guān)系給定一個(gè)集合A，（1）若x是集合A中的元素，記作xA，讀作x屬于A；（2）若x不是集合A中的元素，則記作xA，讀作x不屬于A。說明：讀作屬于；讀作不屬于例:A={a,b,c,d}，則有bA，eA．特殊集合表示幾類特殊集合的表示：N自然數(shù)集合,包括數(shù)0；Z整數(shù)集合；Q有理數(shù)集合；R實(shí)數(shù)集合；C復(fù)數(shù)集合.集合的表示⑴列舉法就是把集合中的所有元素一一列舉出來，或列出足夠多的元素以反映出集合中成員的特征，元素之間用逗號(hào)分開，并用花括號(hào)括起來。如：A={a1，a2，……，an}B={0，2，4，6，……，2n，……}。集合的表示⑵描述法是指把集合中的元素所滿足的條件或具有的性質(zhì)描述出來，即將條件或性質(zhì)用文字或符號(hào)在花括號(hào)內(nèi)豎線后面表示出來。一般形式為：

A={x|x滿足的條件或具有的性質(zhì)}如：A={x|x–1=0，xR}B={x|x是英文字母，x元音}集合的表示⑶遞歸法是指通過計(jì)算規(guī)則定義集合中的元素。首先給出該集合的初始元素；然后給出由集合中已知元素構(gòu)造其他元素的方法；最后強(qiáng)調(diào)有限次使用前面的步驟得到的元素是集合中僅有的元素。如：設(shè)a0=1,a1=1,an+1=an+an-1,A={a0,a1,a2,……}={akk0}。集合的表示⑷巴科斯范式(BNF)表示法

BNF常用來定義高級(jí)程序設(shè)計(jì)語言的標(biāo)識(shí)符或表達(dá)式集合。⑸文氏圖法(JohnVenn)

首先畫一個(gè)大矩形表示全集，然后在矩形內(nèi)畫一些圓，用圓的內(nèi)部表示集合，集合之間的相互關(guān)系和有關(guān)的運(yùn)算可以用文氏圖給予形象的描述。集合的特性⑴確定性確定性是指一旦給定了集合A，對(duì)于任意元素a，我們就可以準(zhǔn)確地判定a是否在A中。如：A={x|x是自然數(shù)，且x<100}則必有30A，101A⑵互異性互異性是指集合中的元素之間是彼此不同的，即集合中不允許出現(xiàn)重復(fù)的元素。如：集合A={a,b,c,c,b,d}應(yīng)為A={a,b,c,d}集合的特性⑶無序性無序性是指集合中的元素之間沒有次序關(guān)系。在不特別說明情況下，我們所討論的集合都不是多重集。如：

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

與A={a,b,c,{a,b}}相同⑷抽象性抽象性是指集合中元素是抽象的，甚至可以是集合。如：A={a,{a,b},b,c}；相關(guān)概念有限集由有限個(gè)元素a1,…,an組成的集合稱為有限集。基數(shù)（或勢(shì)）若集合A是有限集，則集合A中的元素個(gè)數(shù)稱為集合A的基數(shù)（或勢(shì)），通常記作|A|。無限集無限集是指由無限個(gè)元素組成的集合。空集不含有任何元素的集合是空集。記或{}。1.1.2子集子集——集合間的包含關(guān)系

給定兩個(gè)集合A和B，若A中的任意元素都屬于B，則稱A是B的子集，或稱A包含在B，或稱B包含A，通常記作AB，或BA。（若任意aA，必有aB，則AB）若A不是B的子集，則集合A中至少有一個(gè)元素不屬于B。子集定理1-1對(duì)于任意的集合A，有A。1-2設(shè)A、B、C是任意的集合，則有⑴自反性：AA.（任意集合是其子集）⑵反對(duì)稱性：AB,BAA=B.⑶傳遞性：AB,BCAC.1-3A=B的充要條件是AB且BA真子集若AB，且AB，則稱A是B的真子集，通常記作AB。（若A是B的真子集，則B中至少有一個(gè)元素不屬于A）注意區(qū)別：與的不同問題：由AB,BC可否得出AC?解：不成立,如A={a,b},B={a,b,c},C={a,{a,b,c}}.1.1.3冪集設(shè)X是一個(gè)集合，由X的所有子集作為元素構(gòu)成的集合稱為X的冪集，記以P(X)或2X。定理

設(shè)A是一個(gè)有限集且|A|=n，則|P(A)|=2n冪集示例X={a,b}P(X)={,{a},{b},{a,b}}.P({})={,{}}.習(xí)題1.1(7)1.1.4n元組將n個(gè)元素x1,x2,…,xn按一定順序排列就得到一個(gè)n元(有序)組.記為：n=2n=3一般說來(x,y)(y,x).序偶2元組常稱為有序?qū)蛐蚺?注意區(qū)別(a,b,c),((a,b),c),(a,(b,c))的不同.1.1.5笛卡兒積設(shè)A1，A2，…，An是集合，稱集合為A1，A2，…，An的笛卡兒積（直積，叉積）笛卡兒積定理A=B=例：設(shè)A={a,b},B={1,2},C={},求AB,BA,ABC,BC.解：AB={(a,1),(b,1),(a,2),(b,2)}.BA={(1,a),(1,b),(2,a),(2,b)}.

ABC={(a,1,),(b,1,),(a,2,),(b,2,)}.BC={(1,),(2,)}1.2映射的有關(guān)概念映射就是函數(shù)，研究的是任意兩個(gè)集合之間的一種對(duì)應(yīng)關(guān)系。映射是現(xiàn)代數(shù)學(xué)中的基本概念。函數(shù)在信息科學(xué)中得到了充分的應(yīng)用。與集合一樣，映射貫穿本書的所有內(nèi)容，深刻理解映射的有關(guān)內(nèi)容，對(duì)于其他內(nèi)容的學(xué)習(xí)是至關(guān)重要的。1.2.1映射的定義任意給定兩個(gè)集合A和B，若存在對(duì)應(yīng)法則f

，使得對(duì)于任意xA，均存在唯一的yB與它對(duì)應(yīng)，則稱f是集合A到B的一個(gè)映射，或稱A到B的一個(gè)函數(shù)，記為f:AB。AB映射的兩個(gè)特點(diǎn)假定f:AB,y=f(x),通常把x稱為自變量，其取值范圍稱為定義域記為domf；將y稱為因變量，其取值范圍稱為值域，記為ranf。⑴全函數(shù).

映射f的定義域是集合A,記為domf=A；⑵唯一性.

對(duì)于任意x∈A,對(duì)應(yīng)于B中唯一的元素f(x),x為f的自變量(也稱為原像),f(x)稱為x在映射f下的像,通常記為y=f(x).映射的表示（1）解析表達(dá)式（2）圖示（3）表格法函數(shù)符號(hào)的選取:f,g,…,F,G,…,,,…,sin,exp,main,add,average,…BA

（讀作B上A）定義對(duì)于集合A和B，用BA表示A到B的所有映射組成的集合，即定理：對(duì)于集合A和B，若|A|=m，|B|=n，則|BA|=nm。教材P7例題1-51.2.2映射的性質(zhì)1、單射假設(shè)f:AB,如果對(duì)任意x1,x2A,由f(x1)=f(x2)可推出x1=x2,則稱f是A到B的單射,或稱f是A到B的一對(duì)一映射。例：設(shè)f:N→N，f(x)=2x,則f是N到N的單射，試證明之。1.2.2映射的性質(zhì)2、滿射假設(shè)f:AB，如果對(duì)任意yB,均存在xA，使得y=f(x)，則稱f是A到B的滿射，或稱f是A到B的映上(onto)的映射。例：設(shè)f:Z→N,f(x)=|x|,則f是Z到N的滿射。1.2.2映射的性質(zhì)3、雙射假設(shè)f:AB，f既是單射又是滿射，則稱f是A到B的雙射,或稱f是A到B的一一對(duì)應(yīng)。例：試建立一個(gè)Z到N的一一對(duì)應(yīng)。2xx≥0f(x)=2|x|-1x<0習(xí)題1.2(2)置換的定義設(shè)A是有限集合,A到A的雙射稱為A上的置換例如：寫出A={1，2，3}上的所有置換。(個(gè)數(shù)：n!)1.2.3逆映射定義：設(shè)f:AB,若將對(duì)應(yīng)關(guān)系f逆轉(zhuǎn)后能得出一個(gè)B到A的映射,則稱該映射為f的逆映射,記為f-1.定理：設(shè)f:AB

，則f的逆映射存在的充要條件是f是雙射.1.2.4復(fù)合映射定理

設(shè)f:A

B,g:B

C，對(duì)于任意xA，令h(x)=g(f(x))則h是集合A到集合C的映射。xy=f(x)z=g(y)=g(f(x))1.2.4復(fù)合映射定義：設(shè)f:A

B,g:B

C,對(duì)于任意xA,h(x)=g(f(x))則稱h為f和g的復(fù)合映射或復(fù)合函數(shù)，記為f?g重點(diǎn)：(f?g)(x)=g(f(x))abc123復(fù)合映射例題注意：要保證復(fù)合映射有意義，必須f(A)dom(g)例2：設(shè)R到R有兩個(gè)映射f和g，定義如下：f(x)=x2,g(x)=x+2，分別計(jì)算復(fù)合映射f?g和g?f注意：一般來說，即使復(fù)合映射均有意義，也不能保證f?g=g?f成立

恒等映射設(shè)A是集合，令f:AA,f(x)=x，稱f為集合A上的恒等映射(identityfunctiononA)，記為IA

顯然恒等映射是唯一存在的。【定理1-9】若f:A

B是雙射，則有f

?

f-1=IA，f-1

?

f

=IB.特別地，若f:A

A是雙射，則f

?

f-1=f-1

?

f

=IA

復(fù)合映射性質(zhì)【定理1-10】設(shè)f:A

B,g:B

C

，(1)若f和g是單射,則f?

g是單射.(2)若f和g是滿射,則f?

g是滿射.(3)若f和g是雙射,則f?

g是雙射.【定理1-11】設(shè)f:A

B,g:B

C

，(1)若f?g是單射,則f是單射,g不一定.(2)若f?g是滿射,則g是滿射,f不一定.(3)若f?g是雙射,則f是單射且g是滿射.【定理1-12】設(shè)f:A

B,g:B

C

，h:C

D，則(f?

g)?h=f?(g?h)1.3運(yùn)算的定義及性質(zhì)運(yùn)算是由已知對(duì)象得出新對(duì)象的一種方法。運(yùn)算是討論對(duì)象之間有何聯(lián)系的一種方法。運(yùn)算本質(zhì)上是映射，但運(yùn)算更側(cè)重于研究運(yùn)算滿足的一些運(yùn)算性質(zhì)。

1.3.1運(yùn)算的定義設(shè)A1,A2,……,An和B是集合，若

f:A1×A2×……×An→B

則稱f為A1,A2,……,An到B的n元運(yùn)算。在不需要強(qiáng)調(diào)集合A1,A2,……,An和B時(shí)，可以簡(jiǎn)稱f為運(yùn)算，f:A×A×……×A→B稱f為A到B的n元運(yùn)算，或稱f為A上的n元運(yùn)算。如y=f(x1,x2,…,xn)中，x1,x2,…,xn是參加運(yùn)算的n個(gè)有順序的對(duì)象，f稱為n元運(yùn)算，y是運(yùn)算結(jié)果，由定義知道：運(yùn)算結(jié)果一定是唯一的。運(yùn)算的特征1、封閉運(yùn)算：若對(duì)于x1,x2,…,xnA，有f(x1,x2,…,xn)=yA，則稱f為A上的n元封閉運(yùn)算(closedoperation)，或稱為A上的n元代數(shù)運(yùn)算。習(xí)題1.3(1)(2)2、運(yùn)算符號(hào)的選取：常用符號(hào)和定義符號(hào)3、運(yùn)算符號(hào)的位置：前面、中間和后面4、運(yùn)算表：方便直觀運(yùn)算的例題例1（絕對(duì)值運(yùn)算）f:ZN,f(x)=|x|.（一元運(yùn)算）

例2(模運(yùn)算)f:ZN,f(x)=x(modk),例3（模m加法運(yùn)算和模m乘法運(yùn)算）例4（最大公因數(shù)gcd和最小公倍數(shù)lcm）1.3.2運(yùn)算的性質(zhì)1、對(duì)合性【定義】設(shè)*是A上的1元代數(shù)運(yùn)算，若對(duì)于xA，均有

*(*x)=x

則稱*具有對(duì)合性，或稱*滿足對(duì)合律〖例1-20〗實(shí)數(shù)集上的取反數(shù)運(yùn)算“—”具有對(duì)合性，而其上的絕對(duì)值運(yùn)算||不具有對(duì)合性。矩陣的逆運(yùn)算及轉(zhuǎn)置運(yùn)算具有對(duì)合性，因?yàn)?A-1)-1=A并且(AT)T=A1.3.2運(yùn)算的性質(zhì)2、冪等性【定義】設(shè)*是A上的2元代數(shù)運(yùn)算，若對(duì)于xA，有x*x=x

則稱x為關(guān)于*運(yùn)算的冪等元；若對(duì)于任意的xA，x均為冪等元，則稱*具有冪等性，或稱*滿足冪等率。例1：設(shè)A={1,2,3}，A上的*運(yùn)算見表，指出A中的冪等元，并判斷是否滿足冪等率？例2：正整數(shù)集合N+上gcd和lcm是否冪等率？例3：實(shí)數(shù)集合R上乘法是否滿足冪等率？1.3.2運(yùn)算的性質(zhì)3、交換性【定義】設(shè)*是A上的2元代數(shù)運(yùn)算，若對(duì)于任意x,yA，均有

x*y=y*x則稱*具有交換性，或稱*滿足交換律。例1：驗(yàn)證整數(shù)集合Z上的加法運(yùn)算和減法運(yùn)算是否滿足交換律例2：設(shè)*是有理數(shù)集合Q上的2元運(yùn)算，定義如下：任意x1,x2

Q，x1*x2=x1x2。證明*不具有交換性。例3：說明復(fù)合映射是否具有交換性。1.3.2運(yùn)算的性質(zhì)4、結(jié)合性【定義】設(shè)*是A上的2元代數(shù)運(yùn)算，若對(duì)于任意的x,y,zA

，均有(x*y)*z=x*(y*z)則稱*具有結(jié)合性，或稱*滿足結(jié)合律。

例1：驗(yàn)證整數(shù)集合Z上的加法運(yùn)算和減法運(yùn)算是否滿足結(jié)合率。53145534314421213343142254321154321*例2：判定集合A={1,2,3,4,5}見表，是否滿足交換率和結(jié)合率？例3：判定映射的復(fù)合運(yùn)算是否滿足結(jié)合率？1.3.2運(yùn)算的性質(zhì)5、單位元素【定義】設(shè)*是A上的2元代數(shù)運(yùn)算，若存在eA

，對(duì)于任意的xA

，下列條件均成立：

e*x=xx*e=x則稱e為集合A關(guān)于*運(yùn)算的單位元素或幺元素。

例1：驗(yàn)證整數(shù)集合Z關(guān)于加法運(yùn)算+的單位元素為0，而Z關(guān)于乘法運(yùn)算的單位元素為1，Z關(guān)于減法運(yùn)算沒有單位元素。定理：若A關(guān)于*運(yùn)算有單位元素，則單位元素是唯一的。1.3.2運(yùn)算的性質(zhì)6、零元素【定義】設(shè)*是A上的2元代數(shù)運(yùn)算，若存在θA

，對(duì)于任意的xA

，下列條件均成立：

θ*x=θx*θ=θ則稱為集合A關(guān)于*運(yùn)算的零元素。例1：驗(yàn)證整數(shù)集合Z關(guān)于加法運(yùn)算+和減法運(yùn)算-均沒有零元素。Z關(guān)于乘法運(yùn)算的零元素為0。1.3.2運(yùn)算的性質(zhì)7、逆元素【定義1-21】設(shè)*是A上的2元代數(shù)運(yùn)算且有單位元素e，若對(duì)于xA，存在yA，下列條件均成立：

y*x=ex*y=e則稱y為x的逆元素。注意：

1、一個(gè)方陣關(guān)于乘法運(yùn)算的逆元是其逆矩陣，單位元素是單位矩陣；

2、一個(gè)雙射的映射的復(fù)合運(yùn)算的逆元是其逆映射。單位元素是恒等映射。1.3.2運(yùn)算的性質(zhì)例1：分別考察：實(shí)數(shù)集合R中各元素關(guān)于加法運(yùn)算和乘法運(yùn)算的逆元素。例2：設(shè)A={a,b,c},關(guān)于*運(yùn)算的運(yùn)算表。分析逆元。

結(jié)論：一個(gè)元素的逆元不一定存在，存在也不一定唯一。習(xí)題1.3(8)caccaabbcbaacba*【定理】設(shè)A關(guān)于*運(yùn)算的單位元素為e且*運(yùn)算滿足結(jié)合律，若x在A中有左逆元y及右逆元z，則y=z。進(jìn)而，對(duì)于一個(gè)滿足結(jié)合律的運(yùn)算來說，若一個(gè)元素有逆元?jiǎng)t其逆元是唯一的。1.3.2運(yùn)算的性質(zhì)8、消去性【定義1-22】設(shè)*是A上的2元代數(shù)運(yùn)算，若A關(guān)于*運(yùn)算有零元素，如果對(duì)于任意x,y,zA

，只要x≠θ

，則下列條件均成立：

x*y=x*z→y=zy*x=z*x→y=z則稱*具有消去性，或稱*滿足消去律。例：驗(yàn)證整數(shù)集合Z上的加法運(yùn)算+和乘法運(yùn)算均滿足消去律。1.3.2運(yùn)算的性質(zhì)9、分配性【定義1-23】設(shè)*和

?是A上的2元代數(shù)運(yùn)算，若對(duì)于任意x,y,zA，下列條件均成立：x*(y?z)=(x*y)?(x*z)(y?z)*x=(y*x)?(z*x)則稱*運(yùn)算對(duì)?運(yùn)算具有分配性，或稱滿足分配律。注意：當(dāng)*運(yùn)算滿足交換性時(shí)，條件之一成立即可。例：實(shí)數(shù)集合R上的乘法運(yùn)算對(duì)加法運(yùn)算可分配。1.3.2運(yùn)算的性質(zhì)10、吸收性【定義1-24】設(shè)*和?是A上的兩個(gè)2元代數(shù)運(yùn)算，若對(duì)于x,yA，下列條件均成立：x*(x?y)=x(y?x)*x=x則稱*運(yùn)算對(duì)運(yùn)算?可吸收。

注意：當(dāng)*和?運(yùn)算滿足交換性，以上公式之一成立即可。1.3.2運(yùn)算的性質(zhì)11、德·摩根（DeMorgan）律【定義】設(shè)·是集合A上的1元代數(shù)運(yùn)算，*和?是A上的兩個(gè)2元代數(shù)運(yùn)算，若對(duì)于x,yA

，下列條件均成立：

·(x*y)=(·x)?(·y)·(x?y)=(·x)*(·y)則稱這三種運(yùn)算滿足DeMorgan律1.4集合的運(yùn)算1、并運(yùn)算2、交運(yùn)算3、補(bǔ)運(yùn)算4、差運(yùn)算5、對(duì)稱差運(yùn)算1.4.1并運(yùn)算【定義】設(shè)A和B是兩個(gè)任意集合，由所有屬于A或?qū)儆贐的元素組成的集合稱為集合A和B的并集，通常記作A∪B。即：A∪B={x|xA或xB}陰影部分為A∪BUBA如：設(shè)A={a，b，c，d}，B={b，d，e，f}，求A∪B定理：設(shè)A和B是集合，則A∪B是包含集合A和B的最小集合。并運(yùn)算的性質(zhì)設(shè)A，B，C是集合，則1、冪等律：A∪A=A2、交換律：A∪B=B∪A3、結(jié)合律：(A∪B)∪C=A∪(B∪C)4、∪A=A∪=A(空集是并運(yùn)算的單位元素)5、U∪A=A∪U=U(全集U是并運(yùn)算的零元素)1.4.2交運(yùn)算【定義】設(shè)A和B是兩個(gè)任意集合，由所有屬于A又屬于B的元素組成的集合，稱為A和B的交集，通常記作A∩B。即A∩B={x|xA且xB}陰影部分為A∩BUBA如：設(shè)A={a，b，c，d}，B={b，d，e，f}，求A∩B定理：設(shè)A和B是集合，則A∩B是包含在集合A和B中的最大集合。交運(yùn)算的性質(zhì)設(shè)A，B，C是集合，則1、冪等律：A∩A=A2、交換律：A∩B=B∩A3、結(jié)合律：(A∩B)∩C=A∩(B∩C)4、∩A=A∩=（空集是交運(yùn)算的零元素）5、U∩A=A∩U=A（全集U是交運(yùn)算的單位元素）交和并運(yùn)算的性質(zhì)并、交運(yùn)算的混合性質(zhì)(吸收律)：

設(shè)A，B，C是集合，則（1）∩對(duì)∪可吸收：A∩(A∪B)=A

（2）∪對(duì)∩可吸收：A∪(A∩B)=A

（3）∩對(duì)∪可分配：A∩(B∪C)=(A∩B)∪(A∩C)

（4）∪對(duì)∩可分配：A∪(B∩C)=(A∪B)∩(A∪C)

1.4.3補(bǔ)運(yùn)算【定義】設(shè)U是全集，對(duì)于集合A，定義A的補(bǔ)集如下：

={x|xU，但xA}注意：一個(gè)集合的補(bǔ)集依賴于全集的選取。陰影部分為A的補(bǔ)集UA例：設(shè)集合A={a,b,c}分別取全集U={a,b,c,d}和U={a,b,c,{a,b},{b,c},{{c}}},求A的補(bǔ)集。補(bǔ)運(yùn)算的性質(zhì)補(bǔ)運(yùn)算的性質(zhì)：

（1）A∪=U

（2）A∩=DeMorgan律1.4.4差運(yùn)算【定義】設(shè)A和B是兩個(gè)任意集合，由所有屬于A但不屬于B的元素組成的集合稱為A和B的差集，通常記作A-B。即A-B={x|xA且xB}UAB陰影部分為A-B如：設(shè)A={a，b，c，d}，B={b，d，e，f}，求A-B和B-A差運(yùn)算的性質(zhì)（1）A-A=（2）A-=A（3）A-U=定理：對(duì)于集合A,B，有A–B