[企业管理]集合2012_83805305.ppt

《[企业管理]集合2012_83805305.ppt》由会员分享，可在线阅读，更多相关《[企业管理]集合2012_83805305.ppt（162页珍藏版）》请在三一文库上搜索。

1、第二篇 集合论,主要包括如下内容： 集合论初步 二元关系 函数,基本概念,1.集合与元素 集合：是一些确定的、可以区分的事物汇集在一起组成的一个整体。用大写的英文字母表示。 元素：集合中的每个事物，称之为元素。用小写英文字母表示 ：表示元素与集合的属于关系。,2. 有限集合与无限集合 有限集合：元素是有限个的集合。 如果A是有限集合，用|A|表示A中元素个数。 无限集合：元素是无限个的集合。,3.集合的表示方法 列举法（外延表示法）：将集合中的元素一一列出，写在大括号内。 描述法（谓词法）：用句子(或谓词公式)描述元素的属性。 A=x|P(x), 其中P(x)是谓词公式，如果论域内个体a使得P

2、(a)为真，则aA，否则aA。,4. 说明 集合中的元素间次序是无关紧要的，但是必须是可以区分的。 对集合中的元素无任何限制. 常用的几个集合符号的约定： 自然数集合N= 0,1,2,3, 整数集合Z，实数集合R，有理数集合Q.,集合中的元素也可以是集合，下面的集合的含义不同： 如 a： 张书记 a: 党支部(只有一个书记) a： 分党委(只有一个支部) a： 党委 (只有一个分党委) a： 市党委(只有一个党委) （5）对一个集合来说，任一事物或者是它的元素或者不是它的元素，二者必居其一而不可兼而有之，且结论是确定的。,集合实例,B=9，8，8，7=9，8，7=7，8，9 D=x | x B

3、（除7、8、9外的一切事物） F=7，8，9 （FB） A=年青人 罗素悖论：一个村子里的理发师说，我给而且只给自己不给自己理发的人理发。,集合间的关系,一.被包含关系(子集) 1.定义：A、B是集合，如果A中元素都是B中元素，则称B包含A，A包含于B，也称A是B的子集。记作AB。 文氏图表示如右下图。 谓词定义： ABx(xAxB),2. 性质： 有自反性，对任何集合A有AA。 有传递性，对任何集合A、B、C，有AB且 BC ，则AC。 有反对称性，对任何集合A、B，有AB且 BA ，则A=B。 例：判断下列各式的正确性。 aa,b，aa,b， a,ba,b,a, a,ba,b,a,二. 相

4、等关系 定义：A、B是集合，如果它们的元素完全相同，则称A与B相等。记作A=B。 谓词定义： A=Bx(xAxB) 定理：A=B，当且仅当AB且 BA。 证明： A=Bx(xA xB) x(xAxB)(xBxA) x(xAxB)x(xBxA) AB BA,2. 性质 有自反性，对任何集合A，有A=A。 有传递性，对任何集合A、B、C，如果有A=B且 B=C ，则A=C。 有对称性，对任何集合A、B，如果有A=B，则B=A。,三. 真被包含关系(真子集) 1. 定义：A、B是集合，如果AB且AB，则称B真包含A，A真包含于B，也称A是B的真子集。记作AB。 谓词定义：ABA BAB x(xAxB

5、)x(xAxB) x(xAxB) (x(xAxB)x(xBxA) (x(xAxB)x(xAxB) (x(xAxB) x(xBxA) x(xAxB) x(xBxA),2. 性质 对任何集合A、B、C，如果有AB且 BC ，则AC。 练习题：设A=a,a,a,b,a,b,c判断下面命题的真值。 aA (a A) cA aa,b,c aA a,ba,b,c a,bA a,ba,b,c ca,b,c (cA)(a),特殊集合,一.全集 E 定义：包含所讨论的所有集合的集合，称之为全集，记作E。 文氏图如右图。 E=x| P(x)P(x) 性质：对于任何集合A，都有AE。,二.空集 ,定义：不含任何元素

6、的集合，称之为空集，记作。 =x| x x 性质： 1.对于如何集合A，都有A。 因为x(xxA)为永真式，所以A。 2.空集是唯一的。,三.集合的幂集 定义: A是集合，由A的所有子集构成的集合，称之为A的幂集。记作P(A)或2A。 P(A)=B| BA 例如， A P(A) a a,b 结论：对任意集合A，因为A， AA，所以有P(A), AP(A) 。,集合的运算,一.交运算 1.定义：A、B是集合，由既属于A，也属于B的 元素构成的集合 ,称之为A与B的交集,记作AB。 谓词定义： AB=x|xAxB xAB xAxB,2.性质 幂等律 对任何集合A，有AA=A。 交换律 对任何集合A

7、、B，有AB=BA。 结合律 对任何集合A、B、C，有 (AB)C=A(BC)。 同一律 对任何集合A，有AE=A。 零律 对任何集合A，有A=。 AB AB=A。,证明：AB=A x(xAB xA) x(xAB xA)(xA xAB) x(xABxA)(xAxAB) x(xAxB)xA) (xA(xAxB) x(xAxB)xA) (xA(xAxB) x(T(T ( xA xB) x( xA xB) x(xAxB) AB,二.并运算 1.定义：A、B是集合，由或属于A，或属于B的 元素构成的集合 ,称之为A与B的并集,记作AB 谓词定义： AB =x|xAxB xAB xAxB 2.性质 幂等

8、律 对任何集合A，有AA=A。 交换律 对任何集合A、B，有AB=BA。 结合律 对任何集合A、B、C，有 (AB)C=A(BC)。,同一律 对任何集合A，有A=A。 零律 对任何集合A，有AE =E 。 分配律 对任何集合A、B、C，有 A(BC) =(AB)(AC)。 A(BC) =(AB)(AC)。 吸收律 对任何集合A、B，有 A(AB)=A A(AB) =A。 证明 A(AB)= (AE)(AB) (同一) = A(EB) (分配) = AE=A (零律) (同一) AB AB=B。,三. 差运算- (相对补集) 1.定义：A、B是集合，由属于A，而不属于B的 元素构成的集合 ,称之

9、为A与B的差集,或B对A的 相对补集，记作A-B。 谓词定义： A-B =x|xAx B xA-B xAxB 2.性质 设A、B、C是任意集合，则 A-=A -A= A-A= A-BA AB A-B= A-B=AAB=,四. 绝对补集 1.定义：A是集合,由不属于A的元素构成的集合 , 称之为A的绝对补集,记作A。实际上A=E-A。 谓词定义： A =E-A=x|xEx A = x|x A x A xA 2.性质 设A、B、C是任意集合，则 E= =E (A)=A AA= AA=E A-B=AB, (AB)= AB (AB)=AB 证明：任取x (AB) x (AB) xAB(xAxB) (x

10、AxB)xAxB xAB (AB)=AB AB B A 证明： AB x(xAxB) x(xBxA)x(x Bx A) B A,集合恒等式与命题演算等价式的比较,命题演算 集合运算 对象 命题A、B 集合A、B T E F 运算符 AB AB AB AB A A 关系 A=B A=B AB AB 定律 定律,五. 对称差 1.定义：A、B是集合,由属于A而不属于B， 或者属于B而不属于A的元素构成的集合,称 之为A与B的对称差,记作AB。 谓词定义： AB=(A-B)(B-A) =x|(xAxB)(xBxA) AB=(AB)-(AB),2.性质 交换律 对任何集合A、B，有AB=BA。 结合律

11、 对任何集合A、B、C，有 (AB)C=A(BC)。 同一律 对任何集合A，有A=A。 对任何集合A，有AA=。,习题,(1)判断下面命题的真值： a)如果AB，BC ，则 A C。 b)如果AB，BC，则 AC 。 c)如果AB，BC，则 AC。 d)如果AB，BC，则 AC。 e)如果AB及BC，则AC。 f)如果AB，BC，则 AC。 (2)设A=， B=P(P(A) a）是否有B ？ B？ b）是否有B？ B？ c）是否有B？ B？,（1）已知AB=AC，是否必须B=C？ （2）已知AB=AC，是否必须B=C？ （3）已知AB=AC，是否必须B=C？,有限集合的基数集合中元素的个数,(

12、1) |P(A)|=2|A| (2) |AB|A|+|B| (3) |AB| min|A|, |B| (4) |A-B| |A|-|B| (5) |A B|=|A|+|B|-2|AB| 问题: (2)、(3)、(4)等号成立的条件是什么？,序偶与集合的笛卡尔积,一.序偶与有序n元组 1.定义:由两个对象x、y组成的序列称为有序二元组，也称之为序偶，记作；称x、y分别为序偶的第一，第二元素。 注意，序偶与集合x,y不同： 序偶：元素x和y有次序； 集合x,y：元素x和y的次序是无关紧要的。,2.定义：设，是两个序偶，如果 x=u和y=v，则称和相等， 记作=. 3 .定义:有序3元组是一个序偶,

13、其第一个元素也是个序偶。 有序3元组, c可以简记成。 但不是有序3元组。 4.定义:有序n元组是一个序偶,其第一个元素本身是个有序n-1元组,记作, xn。且可以简记成。 5. 定义： = ( x1= y1) ( x2= y2) ( xn= yn),集合的笛卡尔积,例如“斗兽棋”的16颗棋子， 可看成是由两种颜色的集合A和8种动物的集合B组成的 A=红,蓝 B=象,狮,虎,豹,狼,狗,猫,鼠 每个棋子可以看成一个序偶，斗兽棋可记成集合AB ： , , ,1.定义:设A、B是集合，由A的元素为第一元素，B的元素为第二元素组成序偶的集合，称为A和B的笛卡尔积，记作AB，即 AB=|xAyB 例1

14、 设A=0,1，B=a,b，求AB ， BA， AA 。 解： AB= BA= AA= 可见 ABBA 所以，集合的笛卡尔积运算不满足交换律,也不 满足结合律。,2.性质 1) 如果A、B都是有限集，且|A|=m, |B|=n，则 |AB |=mn. 2) A=B=,3) 对和满足分配律。 设A,B,C是任意集合，则 A(BC)= (AB)(AC)； A(BC)= (AB)(AC)； (AB)C= (AC)(BC)； (AB)C= (AC)(BC) 证明 ：任取A(BC) xA yBC xA (yByC) ( xA yB)(xAyC) ABAC (AB)(AC) 所以式成立。,4)若C,则 A

15、B(ACBC) (CACB). 证明: 必要性： 设AB，求证 ACBC 任取AC xAyC xByC (因AB) BC 所以, ACBC. 充分性： 已知C 取C中元素y, 任取 xAxAyC AC BC (由ACBC ) xByC xB 所以, AB. 所以 AB(ACBC),5) 设A、B、C、D为非空集合，则 ABCDACBD. 证明: 首先,由ABCD 证明ACBD. 任取xA，任取yB，所以 xAyB AB CD (由ABCD ) xCyD 所以, ACBD. 其次, 由AC，BD. 证明ABCD 任取AB AB xAyB xCyD (由AC，BD) CD 所以, ABCD 证毕.

16、,6)约定 (A1A2)An-1)An)=A1A2An 特别 AAA = An 3.应用 1)令A1=x|x是学号 A2=x|x是姓名 A3=男,女 A4=x|x是出生日期 A5=x|x是班级 A6 =x|x是籍贯 则A1A2A3 A4A5 A6中一个元素： 这就是学生档案数据库的一条信息，所以学生 的档案就是A1A2A3 A4A5 A6的一个子集。,n 个,2) 令A=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z 是英文字母表 一个英文单词可以看成有序n元组：如 at=, boy=, data=, computer= 于是可以说： a

17、tA2 ,boyA3,dataA4,computerA8, 于是英文词典中的单词集合可以看成是 AA2An 的一个子集。,优先权,一元运算符(A, P(A) 优先于二元运算符(, , , , ) 优先于集合关系符(=, , , ) 优先于一元联结词() 优先于二元联结词(, , , ) 优先于逻辑关系符(, ) 括号内的优先于括号外的！,关系及其表示法 基本概念 1.关系的定义 定义1:设A、是集合，如果AB，则称R是一个从A到B的二元关系。如果 RAA，则称R是A上的二元关系。二元关系简称为关系。 定义2:任何序偶的集合，都称之为一个二元关系。如:R=, R xRy 也称之为x与y有关系。

18、R xRy 也称之为x与y没有关系。,关系的表示,列举法：A=0，1 B=a，b R1=,(A到B的关系） R2=,(A上的关系） 描述法：A=1，2，3 Dx=| xAyAx整除y Lx=|xAyAxy,2.关系的定义域与值域 定义域(domain) ：设RAB，称集合 dom R=x|y(R) 为R的定义域。 值域(range) ：设RAB，称集合 ran R=y|x(R) 为R的值域。 关系的域(fild)：fid R=dom R ran R. 结论： dom R A， ran R B。 R= , dom R = ran R =,三. 关系的另两种表示法,1.有向图法： RAB（A、B非

19、空、有限），用两组小圆圈(称为 结点)分别表示A和B的元素，当R时，从x到y引一条有向弧(边)（由x指向y）。这样得到的图形称为R的关系图。 如RAA,即R是集合A中关系时,用一组小圆圈表示A中的元素，若R,则从x到x画一条有向环(自回路)。,例 设A=1,2,3,4,B=a,b,c， R3 AB， R3= , 则R3的关系图如下： 例 设A=1,2,3,4, R4 AA， R4= , 则R4的关系图如右上图。,R3 :,4.矩阵表示法：,非空有限集合之间的关系也可以用矩阵来表示，这种 表示法便于用计算机来处理关系。 设A=a1, a2, , am，B=b1, b2, , bn是个有限集， R

20、AB，定义R的mn阶矩阵 MR=(rij)mn，其中 rij= 称MR为关系R的关系矩阵。,例 设A=1,2,3,4,B=a,b,c， R3 AB， R3= , 例 设A=1,2,3,4, R4 AA， R4= , , 则 MR3 = MR4=,四.三个特殊关系,1.空关系： 因为AB，(或AA)，所以也 是一个从A到B(或A上)的关系，称之为空 关系。 2. 全域关系 ： AA本身也是一个A上的关系，称之为A上的全域关系，记为EA，即 EA=|xAyA。 3. A上的恒等关系IA： IAAA，且IA =|xA称之为A 上的恒等 关系。,3. A上的恒等关系IA： IAAA，且IA =|xA称

21、之为A 上的恒等关系。 IA的关系距阵为单位距阵。 例如A=1,2,3, 则IA =, A上的、全域关系及IA的关系图及矩阵如 下：,五. 关系的集合运算,由于关系就是集合，所以集合的、 、和运算对关系也适用。 例如，A是学生集合，R是A上的同乡关系， S是A上的同姓关系，则 RS：或同乡或同姓关系 RS：既同乡又同姓关系 R S ：同乡而不同姓关系 RS：同乡而不同姓,或同姓而不同乡关系 R：不是同乡关系, 这里R=(AA)R,关系的性质,本节中所讨论的关系都是集合A中的关系。 关系的性质主要有：自反性、反自反性、 对称性、反对称性和传递性。,一. 自反性,定义:设R是集合A中的关系，如果对

22、于任意xA都有R (xRx)，则称R是A中自反关系。即 R是A中自反的x(xAxRx) 从关系图看自反性:每个结点都有环。 从关系矩阵看自反性：主对角线都为1。,令A=1,2,3,给定A上八个关系如下：,二. 反自反性,定义：设R是集合A中的关系，如果对于任 意的xA都有R ，则称R为A中的 反自反关系。即 R是A中反自反的x(xAR) 从关系图看反自反性:每个结点都无环。 从关系矩阵看反自反性：主对角线都为0。,三. 对称性,定义:R是集合A中关系, 对任何x, yA,如 果有xRy,必有yRx,则称R为A中的对称关系。 R是A上对称的 xy(xAyAxRy) yRx) 从关系图看对称性:在

23、两个不同的结点之间，若有边的话，则有方向相反的两条边。 从关系矩阵看对称性：以主对角线为对称的矩阵。,四. 反对称性,定义:设R为集合A中关系,对任何x, yA,如果有 xRy,和yRx,就有x=y,则称R为A中反对称关系 。 R是A上反对称的 xy(xAyAxRyyRx) x=y) xy(xAyAxyxRy)y x) 由R的关系图看反对称性：两个不同的结点之间 最多有一条边。 从关系矩阵看反对称性：以主对角线为对称的 两个元素中最多有一个1。,五. 传递性,定义:R是A中关系，对任何x,y,zA,如果有xRy,和yRz,就有xRz,则称R为A中传递关系。 即R在A上传递 xyz(xAyAzA

24、xRyyRz)xRz) 从关系图和关系矩阵中不易看清是否有传递性。,例如A=1,2,A中关系R=是传递的. R在A上传递 xyz(xAyAzAxRyyRz)xRz) xyz(xRyyRz)xRz) yz(1RyyRz)1Rz)yz(2RyyRz)2Rz) (z(1R11Rz)1Rz)z(1R22Rz)1Rz) (z(2R11Rz)2Rz) (z(2R22Rz)2Rz) (1R11R1)1R1)(1R11R2)1R2) (1R22R1)1R1)(1R22R2)1R2) (2R11R1)2R1) (2R11R2)2R2) (2R22R1)2R1) (2R22R2)2R2) (FF)F)(FT)T)

25、(TF)F)(TF)T) (FF)F) (FT)F)(FF)F)(FF)F)T,三个特殊关系具有的性质,非空集合A上的空关系： 非空集合A上的全域关系： 非空集合A上的恒等关系：,本节要求： 1.准确掌握这五个性质的定义。 2.熟练掌握五个性质的判断和证明。 R是A中自反的x(xAxRx) R是A中反自反的x(xAR) R是A上对称的xy(xAyAxRy) yRx) R是A上反对称的 xy(xAyAxRyyRx) x=y) xy(xAyAxyxRy)y x) R在A上传递 xyz(xAyAzAxRyyRz)xRz),关系矩阵,关系图,性质 判定:,下面归纳以上八个关系的性质：Y-有 N-无,1

26、。,2。,。,1。,2。,。,1。,2。,。,1。,2。,。,3,3,3,3,R2,R1,R3,R4,自反性 反自反性 对称性 反对称性 传递性,R1 Y N N Y Y,R2 N Y N Y N,R3 Y N Y N Y,R4 Y N Y Y Y,例1:令I是整数集合，I上关系R定义为： R=|x-y可被3整除，求证R是自反、对称和传递 的。 证明：证自反性：任取xI, 因 x-x=0, 0可被3整除,所以有R, 故R自反。 证对称性：任取x,yI,设R, 由R定义得 x-y可被3整除, 即x-y=3n(nI)， y-x=-(x-y)=-3n=3(-n), 因-nI, R, 所以R对称。 证

27、传递性:任取x,y,zI,设xRy, yRz, 由R定义得 x-y=3m, y-z=3n (m.nI) x-z= (x-y)+(y-z)=3m+3n=3(m+n), 因m+nI, 所以xRz, 所以R传递。,关系的复合,复合关系的定义： 设R是从X到Y的关系，S是从Y到Z的 关系，则R和S的复合关系记作RS 。 定义为： RS =|xXzZy(yY RS) 规定： R= R= 。,2.复合关系的计算方法 A=1,2,3 B=1,2,3.4 C=1,2,3,4,5 RAB SBC 枚举法 R=, S=, , 则 RS=,R=, S=, 有向图法 关系矩阵法 令A=a1, a2, am B=b1,

28、 b2, bn C=c1, c2, ct RAB SBC,c11=(a11b11)(a12b21).(a1nbn1) = (a1kbk1) (其中是逻辑乘,是逻辑加) 00=0, 01=10=11=1 00=01=10=0, 11=1 cij=(ai1b1j)(ai2b2j).(ainbnj) = (aikbkj) (1im, 1jt),例：已知 R=, AA S=, AA 求 ： RS， SR， RR ， SS， (RS)R，R(SR),三.性质 1.满足结合律: RAB SBC TCD 则 R(ST)= (RS)T 由于ST是B到D的关系，所以R(ST)是 A到D的关系。 (RS)是A到C

29、的关系，所以(RS)T是A 到D的关系。,证明：任取R (S T) b(bBR S T) b(bBRc(cCST) bc(bBR(cCST) cb(cC(bBRST) c(cCb(bBRS)T) c (cCR ST) (R S) T,所以,可以用下图形象表示:,2. R是从A到B的关系，则 R IB=IA R=R 令A=1,2,3, B=a,b,c,d,4. 关系的乘幂 令R是A上关系，由于复合运算可结合， 所以关系的复合可以写成乘幂形式。即 R R=R2， R2 R=R R2 =R3， 一般地 R0 =IA， Rm Rn = Rm+n (Rm)n =Rmn (m,n为非负整数),逆关系,一.

30、定义 R是从A到B的关系，如果将R中的所有序偶的 两个元素的位置互换，得到一个从B到A的关 系，称之为R的逆关系，记作R-1 ，或RC 。 RC =|R RC R 二. 计算方法 1. R=, RC =,2. RC的有向图：是将R的有向图的所有边的方向颠倒一下即可。 3. RC的矩阵 M =(MR)T 即为R矩阵的转置。如 三.性质 令R、S都是从X到Y的关系，则 1. (RC)C = R 2. (RS)C = RCSC， (RS)C = RCSC 。 3. dom RC =ran R, ran RC =dom R。 4. (R-S)C = RC-SC 。,R-1,1 0 1,5. RS RC

31、 SC 。 证明：充分性，已知RC SC ，则任取RRC SC S RS 必要性，已知R S，则任取 RC R S SC RCSC 6.(R)C=RC 证明:任取(R)C RR RC RC (R)C=RC,7.令R是从X到Y的关系，S是Y到 Z的关系，则 (R S)C= SC RC 。 证明：任取(R S)C R S y(yYRS) y(yYSCRC) SC RC 所以(RS)C= SC RC,8. R是A上关系，则R是对称的，当且仅当 RC =R,证明：充分性，已知 RC=R 任取x,yA 设R,则RC,而RC=R 所以有R ，所以R对称。 必要性，已知R 对称， 先证RCR，任取RC,则R

32、, 因R对称，所以有R，所以RCR。 再证R RC，任取R, 因R对称，所以有 R，则RC, 所以RRC。 最后得RC =R 。,9. R是A上关系，则R是反对称的，当且仅当 RRC IA。,证明： 充分性，已知RRC IA， 任取x,yA 设R 且R， RRRRC， RRC IA (因RRC IA ) x=y 所以R反对称。 必要性，已知R反对称， 任取RRC RRCRRC RR x=y (因R反对称) IA 所以RRC IA 。,10. R是A上关系，则R是传递的，当且仅当 RR R。,证明：必要性，对任意的 RR a(aAR R ) 因为R传递，有R，所以RRR。 充分性， 对任意的a、

33、b、cA，若 R R，则由合成运算的定义，有 R R，由RRR，有 R ， 所以R传递。,11 . R是A上关系，则R是自反的，当且仅当 IA R。,证明：必要性 由于R是自反的，所以，对任意的aA，有 R，而 IA=| aA，所以IA R。 充分性 由于IA=| aA且IA R 所以任意的aA，有 R， 因此R自反。,一些相关结论,定理1 设R1、R2是A上的自反关系，则R1C、R1R2、R1R2也是A上的自反关系。 定理2 设R1、R2是A上的对称关系，则R1C、R1R2、R1R2也是A上的对称关系。 证明：对任意的，若 R1R2 R1 R2 R1 R2 R1R2 所以R1R2是A上的对称

34、关系。 证明2：因为R1、R2是A上的对称关系，所以有 R1= R1C 、R2=R2C，而 （R1R2）C= R1C R2C = R1R2 所以R1R2是A上的对称关系。,定理3 设R1、R2是A上的传递关系，则R1C、R1R2也是A上的传递关系。,证明：对任意的,，若 R1 R2 R1 R2 R1 R2 R1 R2 R1 R2（ R1、R2传递） R1 R2 所以R1 R2在A上传递。,定理4 设R1、R2是A上的反对称关系，则R1C、R1R2也是A上的反对称关系。,证明：对任意的 R1 R2,且xy R1 R2 R1 R2 由于R1、R2是反对称的，且xy,所以有 R1 R2 即 R1 R

35、2 所以R1 R2在A上反对称。,关系的闭包运算,设R是A上的关系，有时希望给R增加一 些有序对，构成新关系R，使得R具有自 反性、或对称性、或传递性，但不希望R 太大，即希望增加的有序对尽量少，这就 是闭包的思想。,二.闭包的定义：,给定 A中关系R,若A上另一个关系R，满足： RR； R是自反的(对称的、传递的)； R是“最小的”，即对于任何A上自反(对称、 传递)的关系R, 如果RR, 就有RR。 则称R是R的自反(对称、传递)闭包。记作r(R)、 (s(R) 、t(R) (reflexive、 symmetric、transitive),三.计算方法 定理1.给定 A中关系R,则 r(

36、R)=RIA。 证明：令R=RIA,显然R是自反的和RR。 下面证明R是“最小的”： 如果有A上自反关系R且RR, 由于R是自反的，有IAR, 所以 RIAR, 即RR。 所以R就是R的自反闭包。即r(R)=RIA 。,定理2.给定 A中关系R,则 s(R)=RRC 。,证明： (1)显然R RRC (2)对 RRC,有R RC 即RC R 所以 RRC， 即RRC是对称的。 （3）设R是对称的，且R R， 对任意的 RRCR RC 若 R，则 R（ R R） 若 RC ，有 R，即 R， 由于R对称，所以 R， 所以RRC R。 所以s(R)= RRC,定理3. 给定 A中关系R, 则 t(

37、R)=RR2R3. 。,证明：令R= RR2R3., 显然有 RR ； 证R是传递的：任取x,y,zA,设有R R, 由R定义得必存在整数i,j使得 Ri , Rj ,根据关系的复合得 Ri+j, 又因Ri+j R,所以R, R传递。,定理3. 给定 A中关系R, 则 t(R)=RR2R3. 。,（令R= RR2R3.,） 证R是“最小的”：如果有A上传递关系R”且 RR”,（证出R R ）。 任取R,则由R定义得必存在整数i,使得Ri ,根据关系的复合得 A中必存在i-1个元素e1, e2,.,ei-1，使得 RR.R。因RR”, 有R” R” .R” 。 由于R”传递，所以有R” 。 RR

38、” 。 综上所述，R就是R的传递闭包，即 t(R)=RR2R3=Ri,例: A=1,2,3 A中关系R,S,T,如下： R=, S =, T =, 求t(R)，t()，t(),定理4. 给定 A中关系R,如果A是有限集合，|A|=n,则 t(R)=RR2.Rn 。,证明：令R=RR2R3., R=RR2.Rn ， 显然有RR。下面证明RR： 任取R,由R定义得必存在最小的正整数p 使 得RP , (下面证明Pn)如果Pn, 根据关系的复合得A中必存在p-1个元素e1, e2,.,ep-1， 使得 RR.R。 令x= e0，y= eP 因为|A|=n，所以，存在正整数t，q，0tR.R且R.R

39、所以， Rk，其中，k=t+p-qR，即R=R。,求t(R)的矩阵Warshall算法：|X|=n, RXX, 令MR=A R2的矩阵为A2， Rk的矩阵为Ak .于是 t(R)的矩阵记作MR+=A+A2+Ak + (+是逻辑加) 置新矩阵 A :=MR ; 置 i=1; 对所有 j ,如果Aj,i =1 ,则对k=1,2,n Aj,k:=Aj,k+Ai,k; /*第j行+第i行,送回第j行*/ i加1; 如果in, 则转到步骤，否则停止。 下面举例，令X=1,2,3,4, X中关系R图如右图所示。 运行该算法求t(R)的矩阵：,i=1 (i-列, j-行) A4,1=1 1行+4行4行 i=

40、2 A1,2=1 ,1行+2行1行 A2,2=1 ,2行+2行2行 A不变 A4,2=1 ,4行+2行4行,4行全1, A不变 i=3 A1,3=1,1行+3行1行, 3行全0, A不变 A2,3=1,2行+3行2行, 3行全0, A不变 A4,3=1,4行+3行4行, 3行全0, A不变 i=4 A1,4=1 ,1行+4行1行 A4,4=1 ,4行+4行4行 A不变, 最后 A=Mt(R),A=MR=,A的初值:,四. 性质,定理5. R是A上关系，则 R是自反的，当且仅当 r(R)=R. R是对称的，当且仅当 s(R)=R. R是传递的，当且仅当 t(R)=R.,四. 性质,定理6. R是A上关系，则 R是自反的，则s(R)和t(R)也自反。 R是对称的，则r(R)和t(R)也对称。 R是传递的，则r