山东科技大学 离散数学3-4 序偶与笛卡尔积3-5 关系及其表示

《山东科技大学 离散数学3-4 序偶与笛卡尔积3-5 关系及其表示》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学DiscreteMathematics曾庆田Email:qtzeng@163.com山东科技大学信息科学与工程学院调课8、9、10周四晚上7：30-9：30教室：S1-119上次课内容回顾集合的概念集合的关系特殊的集合：空集、全集、幂集集合的运算：交、并、补/差、绝对补、对称差包含排斥原理包含排斥原理定理3-3.1：设A1，A2为有限集合，其元素个数分别为

2、A1

3、，

4、A2

5、，则

6、A1A2

7、=

8、A1

9、+

10、A2

11、-

12、A1A2

13、，此定理被称作包含排斥原理。3-4序偶与笛卡尔积1、序偶(有序2元组)：两个具有固定次序的客体组成一个序偶(有序2元组)，记作，其中x是

14、它的第一元素，y是它的第二元素。一、有序n元组例：平面直角坐标系中的一个点的坐标就构成为一个有序序偶，我们可用表示。注：序偶是讲究次序的。例<1，3>和<3，1>表示平面上两个不同的点，这与集合不同，{1，3}和{3，1}是两个相等的集合。2、定义3-4.1：两个序偶相等，=，当且仅当x=u且y=v。一、有序n元组3、有序３元组：是一个序偶，其第一元素本身也是一个序偶，表示为<，z>或。4、有序n元组：有序n元组也是一个序偶，其第一元素是一个n-1元组。<，xn>，通常简记为：

15、n-1，xn>，其中xi称作它的第i坐标，i=1，2，…，n。=的充要条件是xi=yi，i=1，2，…，n。序偶其元素可以分别属于不同的集合，因此任给两个集合A和B，我们可以定义一种序偶的集合。1、定义3-4.2：设A和B是任意两个集合，由A中元素作第一元素，B中元素作第二元素构成序偶，所有这样序偶的集合称集合A和B的笛卡尔积或直积。记作AB。即AB={

16、xA∧yB}二、笛卡尔积2、n个集合的笛卡尔积：集合A1，A2，…，An，则特别地，约定：若A=或B=，则AB=，BA=

17、例题若A={，}，B={1，2，3}，求AB，BA，AA，BB以及(AB)(BA)。解：AB={<，1>，<，2>，<，3>，<，1>，<，2>，<，3>}BA={<1，>，<1，>，<2，>，<2，>，<3，>，<3，>}AA={<，>，<，>，<，>，<，>}BB={<1，1>，<1，2>，<1，3>，<2，1>，<2，2>，<2，3>，<3，1>，<3，2>，<3，3>}(AB)(BA)=若A、B均是有限集，

18、A

19、=m，

20、B

21、=n，则

22、AB

23、=mn。三、笛卡尔积的性质1、对于任意集合A，A

24、=，A=。2、笛卡尔积运算不满足交换律，当A，B，AB时ABBA。3、笛卡尔积运算不满足结合律，即当A，B，C均非空时(AB)CA(BC)。4、定理3-4.1：对任意三个集合A、B、C，有(1)A(BC)=(AB)(AC)(2)A(BC)=(AB)(AC)(3)(BC)A=(BA)(CA)(4)(BC)A=(BA)(CA)由以上两条有：A(BC)(AB)(AC)证明两个集合相等，可以证明它们互相包含。则aA，bBC，即aA，bB，且bc，证明：(2)A(BC)，即

25、AB且AC，有(AB)(AC)，得A(BC)(AB)(AC)(AB)(AC)，则AB且AC，则aA，bB，且aA，bC，则bBC。所以A(BC)，所以(AB)(AC)A(BC)5、定理3-4.2：对于任意集合A、B、C，若C，则ABACBCCACB证明：设ACBC。xA，因C，任取yC，有AC因为ACBC，所以BC所以xB，所以AB设AB。A

26、C，则xA，yC，又因AB，所以xB，所以BC，所以ACBC同样，定理的第二部分ABCACB可以类似地证明。6、定理3-4.3：对任意四个非空集合，ABCD的充分必要条件是AC，BD。证明：充分性。设AC，BD。由定理3-4.2，因BD，A，所以ABAD。又AC，D非空，所以ADCD，所以ABCD。必要性。设ABCD。xA，yB，所以AB，又因ABCD，所以CD，所以x