離散數(shù)學(xué) 課件 第3章 集合

第3章集合§1集合的概念及其表示§2

集合的運算§3

集合定律§4包含容斥原理§5多重序元和笛卡爾乘積§1集合的概念及其表示1、集合2、集合的元素3、有限集和無限集4、集合的表示方法5、集合相等6、子集和包含7、真子集和真包含8、空集9、全集10、冪集1、集合

具有某種特殊性質(zhì)的客體的聚合 集合是一種不可精確定義的數(shù)學(xué)基本概念，只能給予一種描述。

用大寫的英文字母表示集合2、集合的元素

屬于集合的任何客體集合的元素集合的成員用小寫字母表示元素a屬于集合Aa∈Aa屬于A元素a不屬于集合Aa

Aa不屬于A3、有限集和無限集一個集合的元素個數(shù)是有限的有限集一個集合的元素個數(shù)是無限的無限集4、集合的表示方法（1）列舉法：（2）描述法：列出集合中的元素元素之間用逗號分開用花括號括起來用集合中元素所滿足的性質(zhì)表示集合謂詞法構(gòu)造法5、集合相等公理：集合A集合B集合A和B相等A和B具有相同的元素A=B例：一個集合可以做為

另一個集合的元素S={a,{1,2},p,{q}}S中共4個元素，分別為：a{1,2}p{q}{1,2}S{q}S1S2SqS集合的特點（1）元素的確定性（2）互異性（3）無序性集合中的元素是確定的a∈A或a

A二者必居其一集合中的每個元素均不相同集合中元素沒有先后順序6、子集和包含集合A集合BA的每一個元素都是B的元素A為B的子集A

BA包含于BB包含AB

AAB(

x)(→)x

Ax

B證明集合相等的充分必要條件定理： 集合A和B相等的充分必要條件是：A和B互為子集即：

A=B

A

B∧B

A7、真子集和真包含

集合A集合BA的每一個元素都是B的元素A為B的真子集A

BA真包含于BB真包含AA

B

A

B∧A≠Bx

Ax

BB中至少有一個元素不屬于AA

B

（x)(→)∧(

y)(∧)y

ByA8、空集不包含任何元素的集合是空集φ｛φ｝｛φ｝φ≠

例：φ{(diào)}9、全集

在一定范圍內(nèi),若所有集合均為某一集合的子集,則該集合稱為全集E求子集舉例A={1，2，3}，求A的所有子集。解：φ{(diào)1}{2}{3}{1，2}{1，3}{2，3}{1，2，3}23=8個子集集合的元素個數(shù)10、冪集

給定集合A,由集合A的所有子集為元素組成的集合,稱為集合A的冪集ρ(A)=ρ(A){x|}x

A冪集舉例A={1，2，3}，求A的冪集解：ρ(A)={φ,{1},{2},{3},{1，2},{1，3},{2，3},{1，2，3}}定理

如果有限集合A有n個元素，則它的冪集ρ(A)有2n個元素?！?

集合的運算1、交運算（∩）2、并運算（∪）3、差分運算（－）4、對稱差分運算（⊕）1、交運算（∩）集合A集合B所有共同元素組成的集合A和B的交集A∩BA∩B={x|x∈A∧x∈B}A∩B的文氏圖表示A∩B交運算的性質(zhì)(1)等冪律:A∩A=A(2)零律:A∩φ=φ(3)同一律:A∩E=A(4)交換律:A∩B=B∩A(5)結(jié)合律:(A∩B)∩C=A∩(B∩C)A∩B

AA∩B

B集合不相交集合A集合B沒有共同的元素A和B不相交A∩B＝φ2、并運算（∪）集合A集合B所有元素組成的集合A和B的并集A∪

BA∪B={x|x∈A∨x∈B}并運算的性質(zhì)(1)等冪律:A∪A=A(2)零律:A∪E=E(3)同一律:A∪φ=A(4)交換律:A∪B=B∪A(5)結(jié)合律:(A∪B)∪C=A∪(B∪C)A

A∪BBA∪B定理：分配率集合A集合B集合C∩對∪

、∪對∩滿足分配率A∪(B∩C)=(A∪B)∩(A∪C)A∩(B∪C)=(A∩B)∪(A∩C)定理：吸收律設(shè)A、B為任意的兩個集合，則：A∪(A∩B)=AA∩(A∪B)=A3、差運算（-）集合A集合B屬于A而不屬于B的一切元素組成的集合A和B的差集A-BA-B={x|x∈A∧x

B}B對A的相對補集絕對補集（補集）全集E集合AA對E的補集E－AA的絕對補集補集~Ａ~A=={x|x∈E∧x

A}E-A={x|x

A}補運算的性質(zhì)(1)~(~A)=A(2)~E=φ(3)A∪~A=E(4)A∩~A=φ定理：德.摩根定律設(shè)任意兩個集合A和B,則：(1)~(A∪B)=~A∪~B~A∩~B(2)~(A∩B)=定理設(shè)任意兩個集合A和B,則：(1)A-B=A∩~B(2)A-B=A-(A∩B)4、對稱差運算(⊕)集合A集合B或?qū)儆贏,或?qū)儆贐,但不能既屬于A又屬于B的元素組成A和B的對稱差A(yù)⊕BA⊕B=={x|x∈Ax∈B}(A－B)∪(B－A)A－BB－A對稱差運算的性質(zhì)(1)交換律B⊕AA⊕B=(2)結(jié)合律(A⊕B)⊕C=A⊕(B⊕C) (3)A⊕φ=A(4)A⊕A=φ(5)A⊕B=(A－B)∪(B－A)=(A∩~B)∪(B∩~A)§3

集合定律1、等冪律 2、結(jié)合律3、交換律 4、分配率5、同一律 6、零律7、補余律 8、吸收律9、德.摩根定律 10、雙重否定定律11、包含關(guān)系式 12、蘊涵式將命題公式轉(zhuǎn)換成集合公式的方法∧

變∩

∨變∪

變~

T 變EF變φ同一律A∪φ=AA∩E=A對應(yīng)的命題公式：P∨F

PP∧T

P德.摩根定律~(A∪B)=~A∩~B ~(A∩B)=~A∪~B ~E=φ~φ=E對應(yīng)的命題公式：

(P∨Q)

P∧

Q

(P∧Q)

P∨

Q

TFFT11、包含關(guān)系式A∩BA A∩BBAA∪B B

A∪BA-B

A§5多重序元和笛卡爾乘積一、多重序元二、笛卡爾乘積一、多重序元1、序偶2、三重序元3、n重序元1、序偶兩個具有固定次序的客體組成的序列<x,y>序偶的第一個元素序偶的第二個元素≠<x,y><y,x>兩個序偶相等的定義序偶<x,y>序偶<u,v><x,y>＝<u,v>

x=u∧y=v2、三重序元三重序元是一個序偶第一個元素本身也是個序偶<,z><x,y,z><x,y>3、n重序元n重序元是一個序偶第一個元素是(n-1)重序元<,xn><x1,x2,…,xi,…,xn

><x1,x2,…,xn-1>n重序元的第i個坐標(biāo)兩個n重序元相等的定義n重序元<x1,x2,…,xn>n重序元<a1,a2,…,an><x1,x2,…,xn>＝<a1,a2,…,an>

(x1=a1)∧(x2=a2)∧…∧(xn=an)二、笛卡爾乘積1、笛卡爾乘積的定義2、相關(guān)定理3、n個集合的笛卡爾乘積1、笛卡爾乘積的定義注意：笛卡爾乘積不滿足交換律、結(jié)合律A、B為任意集合序偶的第一個元素是A的元素序偶的第二個元素是B的元素A和B的笛卡爾乘積A×BA×B={<x,y>|}x

A∧y

B2、相關(guān)定理設(shè)A,B,C為任意三個集合，×對∩和∪滿足分配律（1）A×(B∪C)=(A×B)∪(A×C)（2）A×(B∩C)=(A×B)∩(A×C)（3）(A∪B)×C=(A×C)∪(B×C)（4）(A∩B)×C=(A×C)∩(B×C)證明：A×(B∩C)=(A×B)∩(A×C)證明：設(shè)對任意的<x,y>

A×(B∩C)

x

A∧y

B∩C

x

A∧y

B∧y

C(x

A∧y

B)∧(x

A∧y

C)

<x,y>

A×B∧<x,y>

A×C

<x,y>

(A×B)∩(A×C)笛卡爾乘積舉例A={1,2},B={α,β},C={a},D=φ求：A×B注意：笛卡爾乘積不滿足交換律={<1,α>,<1,β>,<2,α>,<2,β>}B×A={<α,1>,<α,2>,<β,1>,<β,2>}A×C={<1,a>,<2,a>}A×D=φA×A={<1,1>,<1,2>,<2,1>,<2,2>}笛卡爾乘積舉例A={1,2},B={α,β},C={a}求：A×(B×C)=?(A×B)×C=?注意：笛卡爾乘積不滿足結(jié)合律A×B={<1,α>,<1,β>,<2,α>,<2,β>}B×C={<α,a>,<β,a>}A×(B×C)={<1,<α,a>>,<2,<α,a>>,<1,<β,a>>,<2,<β,a>>}不是三重序元(A×B)×C={<<1,α>,a>,<<1,β>,a>,<<2,α>,a>,<<2,β>,a>}是三重序元3、n個集合的笛卡爾乘積A1×A2×…×An=((((A1×A2)×A3)×…×An)={<x1,x2,…,xn>|x1

A1∧x2

A2∧…∧x