离散数学序偶与笛卡儿积

第三章集合与关系3-4序偶与笛卡儿积

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

生活中许多事物是成对出现的,并且这种成对出现的事物有一定的顺序。（选课，任课，住宿）一般的说，两个具有固定顺序的客体组成一个序偶，它常常表达两个客体间的关系。序偶包含两个元素，但它们有确定的次序。P101定义3-4.1（1）由两个元素x,y（允许x=y）按一定顺序排成的二元组称有序对（序偶），记为<x,y>。称为序偶。定义3-4.1（2）两个序偶相等，即<x,y>=<u,v>当且仅当x=u,y=v。注：序偶x,y

中，x，y分别叫做第一元素（分量）和第二元素（分量），调换第一分量和第二分量位置后，就和原来的含义不同了。即当x

y时，<x,y>

<y,x>。例平面直角坐标系中的点<1,-1>，<2,2>等

序偶<a,b>中两个元素不定来自同一个集合2一、序偶-推广到n元组序偶的概念推广到三元组三元组是序偶,其第一个元素本身也是一个序偶,可形式化为<<x,y>,z>约定三元组可记作<x,y,z><<x,y>,z>=<<u,v>,w>iffx=u,y=v,z=w序偶概念可以推广到n元组，（n

3）是一个有序对，其中第一个元素为n-1元的有序对，一个有序的n元组记作，

<x1,x2,

,xn>即<x1,x2,

,xn>=<<x1,

,xn-1>,xn>应注意：<x1,x2,x3>

<x1,<x2,x3>>。

3二、笛卡尔积序偶<x,y>的元素可以分属于不同的集合，因此，对给定的集A，B可以定义一种新的集合运算，积运算。定义3-4.2设A，B为两个集合，用A的元素作为第一个元素，B的元素作为第二个元素组成序偶。所有这样的序偶组成的集合称为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，根据排列组合原理，|A×B|=nm=|A||B|。

例设A=

a,b

，B=

1,2,3

，⑴试求A×B和B×A⑵验证|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

⑵验证|A×B|=|A||B|和|B×A|=|B||A||A×B|=6=2×3=|A||B||B×A|=6=3×2=|B||A|5二、笛卡尔积如果把×看成运算，笛卡尔积有以下的性质（P102）：①设A为任意的集合，则A×Æ=Æ×A=Æ（约定）②一般地说，当A

B且A，B都不空时

×不满足交换律：即A×B≠B×A。

在上例中，A×B≠B×A③一般地说，当A,B,C都不是空集时,×不满足结合律：即(A×B)×C≠A×(B×C)（后者不是三元组）（P102例题1）P102定理3-4.1笛卡儿积对

或

运算满足分配律，即（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）个式子对任意的<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)*可类似地证明⑵、⑶、⑷

7二、笛卡尔积P103定理3-4.2

设A，B，C是集合，C≠Æ，则⑴A

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

B×C⑵A

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

C×B证明:

仅证明⑴,可类似地证明⑵。设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

设A×C

B×C，下证A

B

因为C≠Æ，所以存在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

设A，B，C，D是非空集合，则

A×B

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

C且B

D。证明：设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

设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二、笛卡尔积两集合的笛卡尔积仍是一个集合，故有限集可以进行多次的乘积，为了与n元组一致，我们约定：定义笛卡尔积A1×A2×…×An定义为(A1×A2×…×An-1)×An，即A1×A2×…×An

=

x1,x2,…,xn

|x1

A1∧x2

A2∧…∧xn

An

由定义可以看出：当n=3时，A1×A2×A3定义为(A1×A2)×A3A1×A2×A3=

x1,x2,x3

|x1

A1∧x2

A2∧x3

A3

当n=4时，A1×A2×A3×A4定义为(A1×A2×A3)×A4