离离 散散 数数 学学 Discrete Mathematics 山东科技大学 信息科学与工程学院 上次课内容回顾 集合的概念 集合的表示 集合的关系 特殊的集合：空集、全集、幂集 集合的运算： 3-4 序偶与笛卡尔积 1、序偶(有序2元组)：两个具有固定次序的 客体组成一个序偶(有序2元组)，记作，其中x是它的第一元素，y是它的第二元 素。 一、有序n元组 例：平面直角坐标系中的一个点的坐标就构成为 一个有序序偶，我们可用表示。 注：序偶是讲究次序的。 例和表示平面上两个不同的点，这 与集合不同，1，3和3，1是两个相等的集合。 2、定义3-4.1：两个序偶相等，=， 当且仅当x=u且y=v。 一、有序n元组 3、有序元组：是一个序偶，其第一元素本身也是一个 序偶，表示为或。 4、有序n元组：有序n元组也是一个序偶，其第一元素是 一个n-1元组。，通常简记为 ：，其中xi称作它的第i坐标，i=1 ，2，n。 n =的充 要条件是xi=yi，i=1，2，n。 n 序偶其元素可以分别属于不同的集合，因此任给 两个集合A和B，我们可以定义一种序偶的集合。 1、定义3-4.2：设A和B是任意两个集合，由A中 元素作第一元素，B中元素作第二元素构成序偶 ，所有这样序偶的集合称集合A和B的笛卡尔积或 直积。记作AB。 即 AB=|xAyB 二、笛卡尔积 2、n个集合的笛卡尔积：集合A1，A2，An，则 特别地， 约定：若A=或B=，则A B= ，B A= 例题 若A=，B=1，2，3，求AB， BA， AA， BB以及(AB)(BA)。 解：AB=， BA=， AA=， BB=， ， (AB)(BA)= 若A、B均是有限集，|A|=m，|B|=n，则|AB|=mn。 三、笛卡尔积的性质 1、对于任意集合A，A=， A= 。 2、笛卡尔积运算不满足交换律，当A，B ，AB时ABBA。 3、笛卡尔积运算不满足结合律，即当A，B，C 均非空时(AB)CA(BC)。 4、定理3-4.1：对任意三个集合A、B、C，有 (1)A(BC)=(AB)(AC) (2)A(BC)=(AB)(AC) (3)(BC)A=(BA)(CA) (4)(BC)A=(BA)(CA) 由以上两条有：A(BC)(AB)(AC) 证明两个集合相 等，可以证明它 们互相包含。 则aA，bBC，即aA，bB，且bc， 证明：(2)A(BC)， 即AB且AC， 有(AB)(AC)，得A(BC)(AB)(AC) (AB)(AC)， 则AB且AC， 则aA，bB，且aA，bC，则bBC。 所以A(BC)，所以(AB)(AC)A(BC) 5、定理3-4.2：对于任意集合A、B、C，若C，则 AB ACBC CACB 证明：设ACBC 。xA，因C ，任取y C ，有 AC 因为ACBC，所以BC所以xB，所以AB 设AB。AC，则xA，yC，又因AB ，所以xB，所以BC，所以ACBC 同样，定理的第二部分AB CACB可以类似地 证明。 6、定理3-4.3：对任意四个非空集合，ABCD的充分 必要条件是AC，BD。 证明：充分性。设AC，BD。 由定理3-4.2，因BD，A，所以ABAD。又AC ，D非空，所以ADCD，所以ABCD。 必要性。设 ABCD。 xA，yB，所以AB，又因ABCD，所以CD，所以 xC，yD，所以AC，BD 证明定理3-4.3用到集合包 含的传递性： (AB)(BC) (AC) 105页（2） 设A=a，b，构成集合(A) A。 解 (A) =，a， b，a，b (A) A=， , , , , , , , 3-5 关系及其表示 兄弟关系 师生关系 朋友关系 恋人关系 大于关系 一、关系（Relation） 1、关系 定义3-5.1：任一序偶的集合确定了一个二元关系R， R记作aRb，称a与b有关系，R记 作aRb，称a与b没有关系。 例如，=|x，y是实数且xy 说明： (1)把关系R这种无形的联系用集合这种“有形”的实体 来描述，为今后的描述和论证带来方便。 (2)序偶是讲究次序的，如果有R未必有R ，即a与b有关系R，未必b与a有关系R。 例：甲与乙有父子关系，但乙与甲没有父子关系。 2 2、前域、值域、前域、值域 定义3-5.2：二元关系R中， 所有序偶的第一元素的集合dom R称为R的 前域，即： dom R=x|(y)R 所有序偶的第二元素的集合ran R称为R的 值域，即： ran R=y|(x)R 。 R的前域和值域一起称作的域，记作FLD R 。即： FLD R=dom Rran R 2 2、前域、值域、前域、值域 例题1 设H=， ，求dom H，ran H， FLD H。 解： dom H=1，2，3， ran H=2，4， FLD H=1，2，3，4 3 3、X X到到Y Y的关系的关系 定义3-5.3：令X和Y是任意两个集合，XY的 子集R称作X到Y的关系。 如果R是X到Y的关系，则dom RX，ran RY。 当X=Y时，关系R是XX的子集，这时称R为在 X上的二元关系。 3 3、X X到到Y Y的关系的关系 例题2 设X=1，2，3，4，求X上的关系及 dom ，ran 。 解： =， dom =2，3，4， ran =1，2，3 4 4、特殊的关系、特殊的关系 (1)全域关系：对于集合X和Y，称XY为X到Y的全域关 系。记作U。 称为空关系。 (2)二元关系：R是XX的子集，称R是X上的二元关系 (3)恒等关系：Ix称为X上的恒等关系iff Ix=|xX 例题3 若H=f，m，s，d表示一个家庭中的父、母、 子、女四个人的集合，确定H上的全域关系和空关系， 另外再确定H上的一个关系，指出该关系的值域和前域 。 解： 设H上的同一家庭成员的关系为H1，H上的互不相识 的关系为H2，则：H1为全域关系，H2为空关系； 设H上的长幼关系为H3 ， H3=，dom H3=f，m，ran H3=s，d 解：H=， ， S= HS=， ， HS= XX=， ， ， H=， ， S-H= 例题4 设X=1，2，3，4，若H=|(x-y)/2是整数， S=|(x-y)/3是正整数，求HS，HS， H，S-H。 5、定理3-5.1：若Z和S是集合X到Y的两个关 系，则Z和S的并、交、补、差仍是到的关系 。 关系的表示方法 集合法 关系矩阵 关系图 二、关系的表示 1、集合 为直观地表示A到B的关系,采用如下的图示: 用大圆圈表示集合A和B,里面的小圆圈表示集合中 的元素; 若aA,bB,且(a,b),则在图示中将表示a和b的 小圆圈用直线或弧线连接起来,并加上从结点a到结 点b方向的箭头。 例 设A1,2,3,4,5,Ba,b,c, 则1(1,a),(1,b),(2,b),(3,a)是A到B的关系 , 而2(a,2),(c,4),(c,5)是B到A的关系。 其集合表示法如下： 2、关系矩阵： 设给定两个有限集合X=x1，x2，xm， Y=y1，y2，yn，R是X到Y的关系，则R 的关系矩阵MR，其中rijmn， rij =1，当R， rij =0，当R 。 其关系矩阵表示为： 例 设A1,2,3,4,5,Ba,b,c, 则1(1,a),(1,b),(2,b),(3,a)是A到B的关系 , 而2(a,2),(c,4),(c,5)是B到A的关系。 关系矩阵的写法也可以简化, 当约定了元素 的次序后, 可以不写最左列和最上行的元素。 如 关于关系矩阵的几点说明： (1)空关系的关系矩阵的所有元素为0。 (2)全关系的关系矩阵的所有元素为1。 (3)恒等关系的关系矩阵的所有对角元为1，非对角 元为0，此矩阵为单位矩阵。 (4)如果R是X上的二元关系时，则其关系矩阵是一 个方阵。 例题5 设X=x1,x2,x3,x4,Y=y1,y2,y3, R=, , , , , , ，写出关系矩阵MR。 例题6 设A=1,2,3,4，写出集合A上大于关系的关 系矩阵。 P108 例题 3、关系图： 设有限集合X=x1，x2，xm， Y=y1，y2， yn，X到Y的一个关系为R，则R的关系图： (1)做出m个结点分别记作x1，x2，xm， n个结点 分别记作y1，y2，yn， (2)如果R ，则可自结点xi至yj作一有向弧; (3)如果R ，则xi至yj没有线段联结。 例 设A-2, -1, 0, 1, 写出A上的关系、 关系、 关系、 UA和IA, 并分别写出这些关系的定义域和值域（这里、 、 分别表示通常的小于、 小于等于和大于）。 并画出关系图。 解 (-2, -1), (-2, 0), (-2, 1), (-1, 0), (-1, 1), (0, 1) Dom-2, -1, 0 Ran-1, 0, 1 (-2, -2), (-2, -1), (-2, 0), (-2, 1), (-1, -1), (-1, 0), (-1, 1), (0, 0), (0, 1), (1, 1) DomA RanA (-1, -2), (0, -1), (0, -2), (1, -2), (1, -1), (1, 0) Dom-1, 0, 1 Ran-2, -1, 0 UA(-2, -2), (-2, -1), (-2,0), (-2,1), (-1,-2), (-1,-1), (-1, 0), (-1, 1), (0, -2), (0, -1), (0, 0), (0, 1), (1, -2), (1, -1), (1, 0), (1, 1) IA(-2, -2), (-1, -1), (0, 0), (1, 1) Dom UARan UADom IARan IAA 图 2 例题 用图 例题7 设X=x1,x2,x3,x4,Y=y1,y2,y3, R=, , , , , , ，画出R的关系图。 例题8 设A=1,2,3,4,5，在A上的二元关系R给定为 ： R=,画出R 的关系图。 P109 例题 如果A=|m|, |B