离散数学-3-4-序偶与笛卡尔积3-5-关系及其表示ppt课件

1、离 散 数 学 Discrete Mathematics,山东科技大学 信息科学与工程学院,上次课内容回顾,集合的概念 集合的表示 集合的关系 特殊的集合：空集、全集、幂集 集合的运算,3-4 序偶与笛卡尔积,1、序偶(有序2元组)：两个具有固定次序的客体组成一个序偶(有序2元组)，记作，其中x是它的第一元素，y是它的第二元素,一、有序n元组,例：平面直角坐标系中的一个点的坐标就构成为一个有序序偶，我们可用表示。 注：序偶是讲究次序的。 例和表示平面上两个不同的点，这与集合不同，1，3和3，1是两个相等的集合。 2、定义3-4.1：两个序偶相等，=，当且仅当x=u且y=v,一、有序n元组,3、

2、有序元组：是一个序偶，其第一元素本身也是一个序偶，表示为，z或。 4、有序n元组：有序n元组也是一个序偶，其第一元素是一个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的笛卡尔积或直积。记作AB。 即 AB=|xAyB,二、笛卡尔积,2、n个集合的笛卡尔积：集合A1，A2，An，则 特别地,约定：若A=或B=，

3、则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=

4、(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,同样，定理的第二部分

5、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 关系及其表示,兄弟关系 师生关系 朋友关系 恋人关系 大于关系,一、关系

6、（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、前域、值域 定义3-5.2：二元关系R中， 所有序偶的第一元素的集合dom R称为R的前域，即： dom R=x|(y)R 所有序偶的第二元素的集合ran R称为R的值域，即： ran R=y

7、|(x)R 。 R的前域和值域一起称作的域，记作FLD R。即： FLD R=dom Rran R,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、X到Y的关系 定义3-5.3：令X和Y是任意两个集合，XY的子集R称作X到Y的关系。 如果R是X到Y的关系，则dom RX，ran RY。 当X=Y时，关系R是XX的子集，这时称R为在X上的二元关系,3、X到Y的关系 例题2 设X=1，2，3，4，求X上的关系及dom ，ran 。 解： =， dom =2，3，4， ran =1，2，3

8、,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=，

9、 ， ， 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

10、),(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)空关系的关系

11、矩阵的所有元素为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 ，则可自结点

12、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

13、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 设

14、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|=n, 则：|AB|=mn， 关系是AB的子集， AB的子集共有2mn个，所以，X到Y的关系共有2mn个,X到Y有多少个不同的关系,可定义n元关系。若S Ai，则称S为 Ai上 的n元关系。特别A1=A2=An时，称S为A上的n元关系,n元关系:二元关系的推广,作业,P105: 单号：(3)b,d (4)(5) 双号：(3)c,e (4)(5) P110: (5)a,b,d

15、 (6)(7)(8,第二章 习题课,作业,P59: 1,2的单数 P62: 3,4,6,P59(1)用谓词表达式写出下列命题,a)小张不是工人。 A(x):x是工人；c：小张 则 A(c) c)小莉是非常聪明和美丽的。 A(x): x聪明；B(x): x是美丽的； c：小莉 则 A(c) B(c) e) 每一个有理数是实数。 Q(x): x是有理数；R(x): x是实数 则 (x)(Q(x) R(x) g) 并非每一个实数都是有理数。 Q(x): x是有理数；R(x): x是实数 则 (x)(R(x) Q(x),P59(2)用谓词表达式写出下列命题,所有教练员是运动员 A(x): x是教练员；

16、B(x): x是运动员 则 (x)(A(x) B(x) c）某些教练是年老的，但是健壮的。 A(x): x是教练员；B(x): x是年老的； C(x):x是健壮的 (x)(A(x) B(x) C(x)） e）不是所有运动员都是教练。 A(x): x是教练员；B(x): x是运动员 则 (x)(B(x) A(x) ) g) 没有一个国家选手不是健壮的。 A(x): x是国家选手；B(x): x是健壮的 则 (x)(A(x) B(x) 或 (x)(A(x) B(x,没有一位女同志既是国家选手又是家庭妇女。 A(x): x是女同志；B(x): x是国家选手 C(x): x是家庭妇女 则 (x)(A(

17、x) B(x) C(x) k) 所有运动员都钦佩某些教练。 A(x): x是运动员；B(y): y是教练； C(x，y): x钦佩y 则 (x)(A(x)(y)(C(x,y )B(y,P62(3)利用谓词公式翻译下列命题,如果有限个数的乘积为零，则至少有一个因子等于零。 对于每一个实数x，存在一个更大的实数y。 存在实数x,y和z，使得x与y之和大于x与z之积,P62(3)利用谓词公式翻译下列命题,a)如果有限个数的乘积为零，则至少有一个因子等于零。 N(x)：x是有限个数的乘积； F(y)：y是乘积的一个因子 O(x)：x 的乘积为零 E(y)：y等于0 (x)(N(x)O(x)(y)(F(

18、y)E(y,b)对于每一个实数x，存在一个更大的实数y。 设 R(x): x是实数； Q(x,y): y大于x (x)(R(x)(y)(Q(x,y)R(y,c)存在实数x,y和z，使得x与y之和大于x与z之积。 设 R(x): x是实数 G(x,y):x大于y。 (x)(y)(z)(R(x) R(y)R(z)G(x+y, xz,P62(4)利用谓词公式表示,若xyz。 设 L(x,y): x小于y; G(x,y):x大于y。 (x) (y) (z)（L(x,y) L(z,0)G ( xz,yz,P63(6)利用谓词公式刻画,那位戴眼镜的用功的大学生在看这本大而厚的巨著。 设A(x): x是大学

19、生； B(x):x是戴眼镜的； C(x): x是用功的； D(x,y):x在看y； E(y):y是大的； F(y): y是厚的 H(y): y是巨著； a：这本；b:那位 B(b)C(b)A(b)D(b,a)E(a)F(a)H(a,P66 (3)判断各式的真假值,a)(x)(P(x)Q(x), 其中P(x): x=1，Q(x):x=2，且论域是1,2 原式 (P(1)Q(1) ) (P(2)Q(2) (TF) (FT)T,b) (x)(PQ(x)R(a), 其中P: 21，Q(x): x3, R(x): x5, 而a:5，论域是-2,3,6 (PQ(-2) )(PQ(3)(PQ(6)R(a)

20、(T T) (T T）（T F)F F,4) 对下列谓词公式中的约束变元换名,a)x y (P(x,z)Q(y) S(x,y) u v (P(u,z)Q(v) S(x,y) b)(x(P(x)(R(x)Q(x)xR(x)zS(x,z) (u(P(u)(R(u)Q(u)vR(v)zS(x,z,5)对下列公式中的自由变元进行代入,yA(x,y)xB(x,z)xzC(x,y,z) (yA(x,y)xB(x,z)xzC(x,y,z) (yA(u,y)xB(x,v)xzC(x,w,z) (yP(x,y)zQ(x,z)xR(x,y) (yP(x,y)zQ(x,z)xR(x,y) (yP(u,y)zQ(u,

21、z)xR(x,w,P72 （4）求证,x)(A(x)B(x) (x)A(x)(x)B(x) 右边=(x)A(x)(x)B(x) (x)A(x)(x)B(x) (x) A(x)(x)B(x) (x) (A(x)B(x) (x)(A(x)B(x,7）求证,x) (y)(P(x)Q(y) (x)P(x)(y)Q(y) 右边(x)P(x)(y)Q(y) (x)P(x)(y)Q(y) (x) P(x)(y)Q(y) (x) (y)(P(x)Q(y) (x) (y)(P(x)Q(y,P75 (1) 化为前束范式,x)(y)P(x,y)(z)Q(z)R(x) (x)( (y)P(x,y)(z)Q(z)R(x

22、) (x)( (y)P(x,y)(z)Q(z)R(x) (x)(y)(z)(P(x,y)(Q(z)R(x,2)求前束合取范式,b) (x)(P(x)(y)(z)Q(x,y)(z)R(y,x) (x)(P(x)(y)(Q(x,y)R(y,x)(消去多余量词） (x)(P(x)(y)(Q(x,y)R(y,x) (x)(y)(P(x)(Q(x,y)R(y,x) (x)(y)(P(x)Q(x,y)R(y,x) 前束合取范式,2)求前束合取范式,b) (x)(P(x)(y)(z)Q(x,y)(z)R(y,x) (x)(y)(P(x)Q(x,y)R(y,x) (x)(y)(P(x)Q(x,y)R(y,x)

23、(P(x)P(x) (x)(y)(P(x)P(x)(P(x)P(x)(Q(x,y)P(x)(Q(x,y)P(x)(R(y,x)P(x)(R(y,x)P(x) (x)(y)(P(x)P(x)(Q(x,y)P(x)(Q(x,y)P(x)(R(y,x)P(x)(R(y,x)P(x) 前束析取范式,2)求前束合取范式,c) (x)P(x)(x)(z)Q(x,z)(z)R(x,y,z) (x)P(x)(x)(z)Q(x,z)(z)R(x,y,z) (x) P(x)(x)(z)Q(x,z)(z)R(x,y,z) (x)(P(x)(z)Q(x,z)(u)R(x,y,u) (x)(z)(u)(P(x)Q(x,z)R(x,y,u) 前束合取范式,2)求前束合取范式,c) (x)P(x)(x)(z)Q(x,z)(z)R(x,y,z) (x)(z)(u)(P(x)Q(x,z)R(x,y,u)