離散數(shù)學(xué)序偶與笛卡兒積

第三章集合與關(guān)系3-4序偶與笛卡兒積

授課人：李朔Email:chn.nj.1一、序偶

生活中許多事物是成對(duì)出現(xiàn)的,并且這種成對(duì)出現(xiàn)的事物有一定的順序。（選課，任課，住宿）一般的說(shuō)，兩個(gè)具有固定順序的客體組成一個(gè)序偶，它常常表達(dá)兩個(gè)客體間的關(guān)系。序偶包含兩個(gè)元素，但它們有確定的次序。P101定義3-4.1（1）由兩個(gè)元素x,y（允許x=y）按一定順序排成的二元組稱(chēng)有序?qū)Γㄐ蚺迹?，記?lt;x,y>。稱(chēng)為序偶。定義3-4.1（2）兩個(gè)序偶相等，即<x,y>=<u,v>當(dāng)且僅當(dāng)x=u,y=v。注：序偶x,y

中，x，y分別叫做第一元素（分量）和第二元素（分量），調(diào)換第一分量和第二分量位置后，就和原來(lái)的含義不同了。即當(dāng)x

y時(shí)，<x,y>

<y,x>。例平面直角坐標(biāo)系中的點(diǎn)<1,-1>，<2,2>等

序偶<a,b>中兩個(gè)元素不定來(lái)自同一個(gè)集合2一、序偶-推廣到n元組序偶的概念推廣到三元組三元組是序偶,其第一個(gè)元素本身也是一個(gè)序偶,可形式化為<<x,y>,z>約定三元組可記作<x,y,z><<x,y>,z>=<<u,v>,w>iffx=u,y=v,z=w序偶概念可以推廣到n元組，（n

3）是一個(gè)有序?qū)Γ渲械谝粋€(gè)元素為n-1元的有序?qū)?，一個(gè)有序的n元組記作，

<x1,x2,

,xn>即<x1,x2,

,xn>=<<x1,

,xn-1>,xn>應(yīng)注意：<x1,x2,x3>

<x1,<x2,x3>>。

3二、笛卡爾積序偶<x,y>的元素可以分屬于不同的集合，因此，對(duì)給定的集A，B可以定義一種新的集合運(yùn)算，積運(yùn)算。定義3-4.2設(shè)A，B為兩個(gè)集合，用A的元素作為第一個(gè)元素，B的元素作為第二個(gè)元素組成序偶。所有這樣的序偶組成的集合稱(chēng)為A與B的笛卡兒積，記為A

B，即：A

B={<x,y>

x

A

y

B}例如A={a,b}B={0,1,2}，則A

B={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>}B

A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}

AXA？BXB？4二、笛卡爾積如果A，B都是有限集，|A|=n，|B|=m，根據(jù)排列組合原理，|A×B|=nm=|A||B|。

例設(shè)A=

a,b

，B=

1,2,3

，⑴試求A×B和B×A⑵驗(yàn)證|A×B|=|A||B|和|B×A|=|B||A|

解：⑴求A×B和B×AA×B=

a,1

,

a,2

,

a,3

,

b,1

,

b,2

,

b,3

B×A=

1,a

,

1,b

,

2,a

,

2,b

,

3,a

,

3,b

⑵驗(yàn)證|A×B|=|A||B|和|B×A|=|B||A||A×B|=6=2×3=|A||B||B×A|=6=3×2=|B||A|5二、笛卡爾積如果把×看成運(yùn)算，笛卡爾積有以下的性質(zhì)（P102）：①設(shè)A為任意的集合，則A×?=?×A=?（約定）②一般地說(shuō)，當(dāng)A

B且A，B都不空時(shí)

×不滿足交換律：即A×B≠B×A。

在上例中，A×B≠B×A③一般地說(shuō)，當(dāng)A,B,C都不是空集時(shí),×不滿足結(jié)合律：即(A×B)×C≠A×(B×C)（后者不是三元組）（P102例題1）P102定理3-4.1笛卡兒積對(duì)

或

運(yùn)算滿足分配律，即（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）（CD）=？6二、笛卡爾積定理3-4.1證明：僅證第（1）個(gè)式子對(duì)任意的<x,y><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

(B

C)=(A

B)

(A

C)*可類(lèi)似地證明⑵、⑶、⑷

7二、笛卡爾積P103定理3-4.2

設(shè)A，B，C是集合，C≠?，則⑴A

B的充分必要條件是A×C

B×C⑵A

B的充分必要條件是C×A

C×B證明:

僅證明⑴,可類(lèi)似地證明⑵。設(shè)A

B，下證A×C

B×C

a,b

A×C

a

A∧b

C

a

B∧b

C

a,b

B×C

所以A×C

B×C

設(shè)A×C

B×C，下證A

B

因?yàn)镃≠?，所以存在b

Ca

A

a

A∧b

C

a,b

A×C

a,b

B×C

a

B∧b

C

a

B

所以A

B8二、笛卡爾積P104定理3-4.3

設(shè)A，B，C，D是非空集合，則

A×B

C×D的充分必要條件是A

C且B

D。證明：設(shè)A×B

C×D，下證A

C且B

Da

A∧b

B

a,b

A×B

a,b

C×D

a

C∧b

D所以A

C且B

D

設(shè)A

C且B

D，下證A×B

C×D

a,b

A×B

a

A∧b

B

a

C∧b

D

a,b

C×D所以A×B

C×D9二、笛卡爾積兩集合的笛卡爾積仍是一個(gè)集合，故有限集可以進(jìn)行多次的乘積，為了與n元組一致，我們約定：定義笛卡爾積A1×A2×…×An定義為(A1×A2×…×An-1)×An，即A1×A2×…×An

=

x1,x2,…,xn

|x1

A1∧x2

A2∧…∧xn

An

由定義可以看出：當(dāng)n=3時(shí)，A1×A2×A3定義為(A1×A2)×A3A1×A2×A3=

x1,x2,x3

|x1

A1∧x2

A2∧x3

A3

當(dāng)n=4時(shí)，A1×A2×A3×A4定義為(A1×A2×A3)×A4