離散數(shù)學一、集合基本概念

1.2

Sets一、集合的基本概念2集合是一些確定的、作為整體識別的、互相區(qū)別的對象的總體。組成集合的對象稱為集合的成員（member）或元素（element）。一般用大寫字母表示集合，用小寫字母表示元素。例如：A表示一個集合，a表示元素，集合是一些確定的、作為整體識別的、互相區(qū)別的對象的總體。Let

A:={

},then

A∈A

A

?

A.What

should

we

do?“Easy”,

just

rule

out

x

∈

x!Really?Let’s

see

the

Russell

Paradox:3如果a是A的元素，記為：aA，讀作“a屬于A”、“a是A的元素”、“a是A的成員”、“a在A之中”、“A

包含a”。如果a不是A的元素，記為：aA，讀作“a不屬于A”?？占?和只含有有限多個元素的集合稱為有限集（finite

sets），否則稱為無限集（infinitesets）。有限集合中元素的個數(shù)稱為集合的基數(shù)（cardinality）集合A的基數(shù)表示為A。4二、集合的表示方式有三種：（l）列舉法將集合的元素列舉出來。描述法利用一項規(guī)則（一個公式），描述集合中的元素的共同性質(zhì)，以便決定某一物體是否屬于該集合。歸納法用遞歸方法定義集合。51、列舉法：將集合的元素列舉出來例：A={a，b，c，d}，Odd={1，3，5，7，9，……}使用列舉法，須列出足夠多的元素以反映集合中成員的特征。如：B={2，4，8，……}若x=2n，則B={2，4，8，16，32，……}若x=2+n(n-1)，則B={2，4，8，14，22，……}62、描述法：A={x|P(x)}或A={x：P(x)}例：C={x|1x5，x?}，D={(x，y)|x2+y21，x，y?}的一個省}F={x|x說明：?}1、C={x|1x5，x

?}={y|1y5，y表示同一個集合。2、集合中元素是無序的：{a，b，c}={b，c，a}={c，a，b}。3、集合中的元素可能也是集合，例：A={1，2，{1}，{1，2，3}}，1

A，{1}A。7三、集合的關(guān)系相等(外延性公理)：兩個集合是相等的，當且僅當它們有相同的元素。

兩個集合A和B相等，記作A=B，兩個集合不相等，記作AB。2-2x+1)=0}{0，1}={{0，1}{1，2}注：A=B

x(xAxB)8定義

設(shè)A、B是任意兩個集合，如果A的每一個元素都是B的元素，則稱集合A是集合B的子集合（或子集，subsets），或稱A包含在B內(nèi)，記為AB

；或稱B包含A，記為BA，即AB

x(xA?xB)；若還有A

≠B，則稱A是B的真子集，記為AB。設(shè)A，B，C為任意集合，包含關(guān)系具有：自反性：A

A;傳遞性：若A

B且B

C，則A

C;稱性：A=BAB且BA。偏序關(guān)系9注：可能AB或BA

，也可能兩者均不成立，不是兩者必居其一。例：A={1，2，3}，B={1，2}，C={1，3}，D={3}，F(xiàn)={1，4}，則BA，DCA，F(xiàn)?A

。數(shù)集：?

?

?+

?

?

?

?.1四、特殊的集合空集(emptysets)定義：不含任何元素的集合稱為空集，記作。1例如：{x|x2+1=0，x注意：{}，?}=。{}定理：對于任意一個集合A，

A。證明：反證法，假設(shè)存在一個集合A，使得

A為假。則存在x

且x

A，這與空集的定義

，所以

A，空集是任意集合的子集。推論：空集是唯一的。證明：設(shè)1，2是兩個空集，則1

2，2

1，得1=2，所以空集是唯一的。1例：A={a,}，判斷下列結(jié)論是否正確。1（1）（4）{}（7）{a}A，（2）

A，（5）aA，（8）{a}A，（3）{}

A，A，（6）a

A，A，結(jié)論（1）、（2）、（3）、（5）、（8）正確。集合的運算及其性質(zhì)1、交(intersection)定義：設(shè)任意兩個集合A和B，由A和B的所有共同元素組成的集合，稱為A和B的交集，記為A

∩B，A

∩B={x|xA

xB}。The

Venn

diagram:A

B1例1：設(shè)A是平面上所有矩形的集合，B是平面上所有菱形的集合，A∩B是所有正方形的集合。例2：設(shè)A是所有能被k整除的整數(shù)的集合，B是所有能被l整除的整數(shù)的集合，A∩B是所有能被k與l最小公倍數(shù)整除的整數(shù)的集合。1性質(zhì)：AA=AA=AB=BA(AB)C=A(BC)ABA，ABB1例3：設(shè)AB，求證ACBC。思路：對任一xAC，則xA且xC，因為有若xA，則xB，所以xB且xC，故xBC。因此ACBC。12、并集(union)定義：設(shè)任意兩個集合A和B，所有屬于A或?qū)儆贐的元素組成的集合，稱為A和B的并集，記作A∪B。A∪B={x|xA

xB}The Venn

diagram:A

B1例1：設(shè)A是奇數(shù)集合，B是偶數(shù)集合，則AB=?，AB=。性質(zhì)：AA=AA=AAB=BA(AB)C=A(BC)AAB，BAB1例2：設(shè)AB，CD，求證ACBD。思路：對任一xAC，則xA或xC，若xA，則xB，故xBD；若xC，則xD，故xBD。因此ACBD。定理

設(shè)A，B，C為三個集合，則下列分配律成立。a)A(BC)=(AB)(AC)b)A(BC)=(AB)(AC)2a)A(BC)=(AB)(AC)21證明思路：a)設(shè)S=A(BC)，T=(AB)(AC)，若xS，則xA且xBC，即xA且xB或xA且xC，xAB或xAC即xT，所以S

T。反之，若xT，則xAB或xAC，xA且xB或xA且xC，即xA且xBC，于是xS，所以TS。因此，S=T。b)證明完全與a)類似。CBACBThe

Venn

diagram

of

three

setsa)A(BC)=(AB)(AC)A2定理

設(shè)A，B為任意兩個集合，則下列吸收律成立。a)A(AB)=Ab)A(AB)=A證明思路：a)

AB?A?A(AB)b)

A(AB)?A?AB2定理

ABAB=BAB=A。思路：若AB，則AB

B

AB。反之，若AB=B，則A

AB=B。同理可證得AB=A。23、差集(difference)、補集(complement)定義：設(shè)A、B是任意兩個集合，所有屬于A而不屬于B的元素組成的集合稱為A和B差集，(或B對A的補集，或相對補)記作A-B。A-B={x|xA∧xB}2The

Venn

diagram:A

B定義：設(shè)E為全集，任一集合A對E的補，稱為A的絕對補，記作Ac。Ac=E-A={x|xE∧xA}The

Venn

diagram:AcAE2性質(zhì)：(Ac)c=AEc=

c=EAAc=EAAc=2定理設(shè)A，B為任意兩個集合，則下列關(guān)系式成立。(AB)c=AcBc(AB)c=AcBcA-B=ABcA-B=A-(AB)定理設(shè)A，B，C為三個集合，則A(B-C)=(AB)-(AC)定理設(shè)A，B為任意兩個集合，若AB，則BcAc(B-A)A=B24、對稱差(symmetric

difference)定義：設(shè)A、B是任意兩個集合，集合

A和B的對稱差，其元素或?qū)儆贏，或?qū)儆贐，但不能既屬于A又屬于B，記作A?B。A?B=(A-B)(B-A)The

Venn

diagram:A

B2性質(zhì)：A?B=B?AA?=AA?A=A?B=(ABc)(AcB)(A?B)?C=A?(B?C)31.3

冪集的基數(shù)定義：給定集合A，由A的所有子集為元素組成的集合稱為A的冪集，記作

(A)或2A。(A)={S|S

A}例：2?={?}，|2?|=1；2{a}={?，{a}}，|2{a}|=2；2{a,b}={?，{a}，，{a,b}}，|2{a,b}|=22；設(shè)A={a，b，c}，則A的冪集：2A={，{a}，，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}}，|2A|=2|A|=23=8.3定理1.3.1

如果有限集A有n個元素，其冪集有2n個元素。a∈Sb∈S{a,b,c}{a,b}{a,c}YYc∈SYNNc∈SNb∈SY

Nc∈S

c∈SNY

N

Y{a}

{b,c}

{c}

?NY30000?1001{

,

,c}2010{

,b,

}3011{

,b,c}4100{a,

,

}5101{a,

,c}6110{a,b,

}7111{a,b,c}Encoding3Theorem

1.5.1

The

number

of

strings

oflength

ncomposed

of

k

given

elements

is

kn.定理1.5.2

設(shè)事件A1有k1種產(chǎn)生方式,

事件A2有k2種產(chǎn)生方式,

…,事件An有kn種產(chǎn)方式，則事件A1,A2,…,An依次接連產(chǎn)生共有k1k2…kn種不同方式.注意:這里的事件A1,A2,…,An必須是互相獨立的.1.5

Sequences3選擇,從例

如果從 到到 有2條道路可供到石家莊有3條道路可供選擇,從石家莊到太原有2條道路可供選擇,

問從

經(jīng)

、石家莊到太原有多少條道路可供選擇？石家莊太原3例從1000到9999的整數(shù)中,問(1)含有5的數(shù)有多少個?(2)含有多少個百位和十位數(shù)均為奇數(shù)的偶數(shù)?(3)各位數(shù)都不相同的奇數(shù)有多少個?解設(shè)有數(shù)字集合{0,1,2,3,4,5,6,7,8,9}.(1)先求不含5的整數(shù)的個數(shù).這時候個位數(shù)字,十位數(shù)字和百位數(shù)字各有9種選擇,而千位數(shù)字只有8種選擇,所以不含5的整數(shù)的個數(shù)=8999=5832,從1000到9999共有9000個整數(shù),所以含有5的的整數(shù)=9000-5832=3168.337(2)當個位數(shù)字為0,2,4,6,8的時候?qū)?yīng)的該整數(shù)為偶數(shù),因此個位數(shù)有5種選擇,十位數(shù)字和百位數(shù)字各有5種選擇,而千位數(shù)字有9種選擇,故含有個百位和十位數(shù)均為奇數(shù)的偶數(shù)=9555=1125.(3)當個位數(shù)字為1,3,5,7,9的時候?qū)?yīng)數(shù)字為奇數(shù).如果要求各位數(shù)都不相同,則個位數(shù)有5種選擇,當個位數(shù)選定之后,千位數(shù)只有8種選擇,而當千位數(shù)選擇之后,百位數(shù)可以有8種選擇,以上三位數(shù)都選定之后,剩下的十位數(shù)就只有7種選擇了.所以,從1000到9999的整數(shù)中,各位數(shù)字都不相同的奇數(shù)=8875=2240.排列(order)與組合定義1.1從n個不同的元素中,取k個并按次序排列,稱為從n中取k個的一個排列,全部這樣的排列數(shù)記為P(n,k).3若k=n,則稱為n個元素的一個置換(permutation)，且P(n,n)=n!。定義1.2

從n個不同的元素中,取k個但是不考慮次序時候,稱為從n中取k個的一個組合,全部這樣的組合總數(shù)記為C(n,k).Theorem

1.7.1

P(n,k)=n!/(n-k)!.Theorem

1.8.1

C(n,k)=n!/[k!(n-k)!].-k);Theorem

1.8.2

(1)C(n,k)=If

n,k>0,

then(2)

C(n-1,k-1)+C(n-1,k)=C(n,k);(3)

C(n,0)+C(n,1)+…+

)=2n.3證明(3)。一般地，如果|A|=n，則A