《左孝凌离散数学序偶与笛卡尔积关系及其表示》由会员分享，可在线阅读，更多相关《左孝凌离散数学序偶与笛卡尔积关系及其表示（59页珍藏版）》请在金锄头文库上搜索。
1、*1 离散数学离散数学( (Discrete MathematicsDiscrete Mathematics ) ) *1 3-4 序偶与笛卡尔积 一、序偶 二、笛卡尔积。 1.定义 两个元素x,y按给定顺序组成的2元组称为一个序 偶（有序对），记作:其中x是它的第一元素， y是它的第二元素。 序偶主要用来表示两个个体之间的联系 例：平面直角坐标系中的一个点的坐标就构成为一个有序 序偶，我们可用表示。 ， 一、序偶(有序2元组) 2.序偶的性质 如果xy,则 两个序偶相等，=，当且仅当x=u且y=v。 注： 序偶是有次序的。 例：和是表示平面上两个不同的点，这与集 合不同，1，3和3，1是两个
2、相等的集合。 序偶中的两个元素可以相等 例：代表一个序偶，而在集合中x，x与x相同。 序偶的概念可以扩展到三元组的情况 一、序偶(有序2元组) 3.有序元组: = 4.有序n元组： = =的充 要条件是xi=yi，i=1，2，n。 注 N元组的第一个分量应该是n-1元组 = 序偶中的两个元素可以来自不同集合 例：表示牛要喝水 因此任给两个集合A和B，我们可以定义一种序偶 的集合。 一、序偶 1.定义：设A和B是任意两个集合，由A中元素作第一 元素，B中元素作第二元素构成序偶，所有这样序偶的 集合称集合A和B的笛卡尔积或直积。记作AB。即 AB=|x Ay B 二、笛卡尔积 所以AB表示： 来自
3、A的元素与 来自B的元素所 构成的所有序偶 的集合 例题 若A=，B=1，2，3， 求AB， BA， AA， BB以及(AB)(BA)。 解：AB=, BA=, AA=, BB=, (AB)(BA)= 注意： 1）若A、B均是有限集，|A|=m，|B|=n，则|AB|=mn 2）一般， AB与BA不相等，即集合的笛卡尔积运算不满足交换 律。反例: A=1, B=2.AB=, BA=. 二、笛卡尔积 约定：若A=或B=，则A B= ，B A= 2.n个集合的笛卡尔积：集合A1，A2，An，则 特别地， 二、笛卡尔积 例：设A，B，C，D是任意集合，判断下列命题是否正确？ (1)ABACBC 不正
4、确，当A，BC时，AB=AC=。 (2)A-(BC)=(A-B)(A-C) 不正确，当A=B=1，C=2时，A-(BC)=1-=1，而(A- B)(A-C)=1=。 (3)A=C，B=DAB=CD 正确，由定义可以证明，在非空前提下是充要条件。 (4)存在集合A使得AAA 正确，当A=时，AAA。 (5)(AB)C = A(BC) 错。当A=B=C=1. (AB)C=, A(BC)=. (除非 A= B= C=) 二、笛卡尔积 设x A,y B,所以 AB A=C,B=D,所以x C,y D 所以 CD得证 不满足结合律 3、笛卡尔积的性质 对于任意集合A，A=， A= 。 笛卡尔积运算不满足
5、交换律，当A，B，AB 时ABBA。 笛卡尔积运算不满足结合律，即当A，B，C均非 空时(AB)CA(BC)。 二、笛卡尔积 定理1：对任意三个集合A、B、C，有 (a)A(BC)=(AB)(AC) (b)A(BC)=(AB)(AC) (c)(BC)A=(BA)(CA) (d)(BC)A=(BA)(CA) 由以上两条有：A(BC)(AB)(AC) 证明两个 集合相等 ，可以证 明它们互 相包含。 则aA，bBC，即aA，bB，且bC， 证明：(b) A(BC)， 即AB且AC， 有(AB)(AC)，得A(BC)(AB)(AC) (AB)(AC)， 则AB且AC， 则aA，bB，且aA，bC，则
6、bBC。 所以A(BC)，所以(AB)(AC)A(BC) 二、笛卡尔积 定理2：对于任意集合A、B、C，若C，则 1)AB ACBC 2)AB CACB 证明：1) 设xA，因C ，设y C ， 有AC，因为AB，xB 所以BC,所以AC BC 设AC，则xA，yC， 又因ACBC ，所以 BC ，所以 xB, y C，所以AB 同样，定理的第二部分AB CACB可以类似地 证明。 二、笛卡尔积 定理3：对任意四个非空集合，ABCD的充 分必要条件是AC，BD。 证明：充分性。设AC，BD。 由定理2，因BD，A，所以ABAD。 又AC，D ，所以ADCD，所以ABCD。 必要性。设 ABCD
7、。 xA，yB，所以AB，又因ABCD，所以CD，所以 xC，yD，所以AC，BD 证明定理3用到集合包含的 传递性： (AB)(BC) (AC) 二、笛卡尔积 练习 105页(2)-(5) 105页（2） 设A=a,b，构成集合 P(A)A。 解 P(A)=,a,b,a,b P(A)A=, , 105页（3） 下列各式中哪些成立？哪些不成立？为什么？ a)(AB) (CD)=(AC)(BD) b)(A- B) (C -D)=(AC) - (BD) c)(AB) (CD)=(AC)(BD) d)(A -B) C =(AC) -(BC) e)(AB) C =(AC) (BC) a)(AB) (C
8、D)=(AC)(BD)不成立。 设A= a，B= b，C =c，D =d， 则 AB=a，b， CD=c，d， (AB) (CD)=,， AC =， BD =， (AC)(BD)=, 故(A B) (C D) (AC) (BD) b)(A-B)(C-D)=(AC)-(BD)不成立。 设A=a,e，B=a,b，C=c,f，D=d， 则 A-B=e， C-D=c，f， (A- B)(C-D)=, ， AC =,， BD =,， (AC)-(BD)=,， 故(A- B) (C -D) (AC) - (BD) c)(AB) (CD)=(AC)(BD)不成立。 设A= a，B= b，C =c，D =d，
9、 则 AB=a，b， CD=c，d， (AB) (CD)=,， AC =， BD =， (AC)(BD)=, 故(AB) (CD) (AC)(BD) d)(A - B) C =(AC) - (BC)成立. 证明 因为(A - B) C =|(xA-B)yC 所以 (A - B) C x(A-B)yC xAx ByC ( ( xAyCx B) (xAyCy C) ( (xAyC ) )(x ByC) ( (xAyC ) ) (x B y C) A C B C (AC) - (BC) e)(AB) C =(AC) (BC)成立。 证明 (AB) C =(A-B)(B-A) C =(A-B) C(B
10、-A) C =(A C）-（B C）(B C）-（A C） =(AC) (BC) （定理1c)） d)(A - B) C =(AC) - (BC) 105页（4） 证明：若XX=YY，则X=Y。 提示：证明XY且YX 证明：设任意x X，则 XX， 因为 XX=YY YY，x Y，所以XY。 同理可证YX。 故X=Y 105页（5） 证明：若XY=XZ，且X，则Y=Z。 证明：若Y=，则XY=，从而XZ=， 即Z=，所以Y=Z。 若Y，设任意y Y，因为X， 令a X，则 XY，即 XZ， 故yZ，所以YZ。 同理可证ZY。 即Y=Z 作业 1.证明：AB=BA(A=)(B=)(A=B)。 *
11、25 离散数学离散数学( (Discrete MathematicsDiscrete Mathematics ) ) *25 一、二元关系 二、几个特殊的二元关系 三、关系的运算 四、二元关系的表示 *26 3-5关系及其表示 3-5关系及其表示 关系举例： 1）兄弟关系、长幼关系、同学关系、邻居关系，上下 级关系等。 2）在数学上有大于关系、小于关系，整除关系。 例如：“3小于5”，“x大于y”， “点a在b与c之间” 我们知道序偶可以表达两个客体、三个客体或n个客体 之间的联系，因此用序偶表达这个概念是非常自然的。 一、二元关系 例如：火车票与座位之间有对号关系。 设X表示火车票的集合，Y
12、表示座位的集合， 则对于任意的 xX 和 y Y， 必定有 x 与y有“对号”关系 x 与y没有“对号”关系。二者之一 令 R表示“对号”关系， 则上述问题可以表示为 xRy 或 xRy 。 亦可表示为 R 或 R， 因此我们看到对号关系是一个序偶的集合。 1.二元关系定义1 任一序偶的集合称为一个二元关系，简称关系，记 作R。 如果R,可记作：aRb，称为a与b有关系R； 如果R,可记作：aRb，称为a与b没有关系R； 这种记法称为中缀记法。 例：R=,则中缀记法为： aR1, bR2, bR2, a 一、二元关系 例1: 在自然数中关系“”可记作 R =“”=|x,yN且x y。 R,即3
13、R2，读作“3大于2” 例2: R1=, R1是二元关系. 例3: A=,a,1 A不是关系. 说明： 1）我们把关系R这种无形的联系同集合这种“有形”的实体来描述 ，在今后的描述和论证带来方便 2）有序对是讲究次序的，如R未必有R，即a与b有关 系R,b与a有关系R. 例：甲与乙有父与子的关系，则乙与甲肯定没有父与子的关系。 一、二元关系 2.二元关系定义2 AB的任何子集R称为A到B的二元关系。 R是A到B的二元关系 RAB RP (AB)（幂集） 若|A|=m, |B|=n, 则|AB|= mn , 故|P (AB)|=2mn，即A到B不同的二元关系共 有2mn个 一、二元关系 3.二元关系定义3 A上的二元关系： AA的任意子集R称为A上的二元关系 RAA RP (AA)。 若|A|
