交大数理逻辑课件102-关系

《交大数理逻辑课件102-关系》由会员分享，可在线阅读，更多相关《交大数理逻辑课件102-关系（27页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,P85: 3(4),指出下列推演中的错误，并改正之,(,,x,),P,(,x,) = F,(,,x,),P,(,x,),,(,,x,),P,(,x,),改为：,(,,x,),P,(,x,) = F,(,,x,),P,(,x,),,(,,x,),P,(,x,),或,(,,x,),P,(,x,),= F,(,,x,),P,(,x,),,(,,x,),P,(,x,),必有,(,,x,),P,(,x,)=F,,不一定有,(,,x,),P,(,x,)=F,,必有,(,,x,),P,(,x,)

2、 = F,,,P85: 3(4)指出下列推演中的错误，并改正之必有(x),P195: 1(4),列出下列各集合所有的元素：,A={z|z={x, y}∧x∈Z∧y∈Z∧,0≤x≤2,∧,-2≤y≤1,},A={,{,0, -2,},,,{,0, -1,},,,{,0, 0,},,,{,0, 1,},,{,1, -2,},,,{,1, -1,},,,{,1, 1,},,{,2, -2,},,,{,2, -1,},,,{,2, 0,},,,{,2, 1,},},P195: 1(4)列出下列各集合所有的元素：,第10章 关 系,,10.1 二元关系,10.2 关系矩阵和关系图,10.3 关系

3、的逆、合成、限制和象,10.4 关系的性质,10.5 关系的闭包,10.6 等价关系和划分,10.7 相容关系和覆盖,10.8 偏序关系,第10章 关 系,关系的合成运算,,F,∘,G,= {<,x,, y> |,,z,(<,x,,,z,>,,G,,<,z,,,y,>,,F,) },,,,,,,,,,,,,x,1,x,2,z,3,z,2,z,1,y,1,y,2,F,∘,G,F,G,关系的合成运算 F∘G = { | z (

4、,(R),,ran,(R,,1,)=,dom,(R),(,R,,1,),,1,=R,(,S,∘,R,),,1,=,R,,1,∘,S,,1,证,,(4),对任取,<,x,,,z,>,,,x,,z,,(,S,∘,R,),-1,,z,,x,,(,R,∘,S,),,(,,y,)(,,z,,,y,,S,∧,,y,,x,,R,),,(,,y,)(,,y,,z,S,-1,∧,x,,,y,R,-1,),,x,,,z,,S,-1,∘,R,-1,R,,1,,= {<,y,,,x,> | <,x,,,y,>,R,},,F,∘,G,= {<,x,,

5、 y> |,,z,(<,x,,,z,>,,G,,<,z,,,y,>,,F,) },,关系基本运算的性质 定理10.3.1设X, Y, Z是集合,,关系基本运算的性质,定理10.3.2,,设,X,，,Y,，,Z,，,W,是集合，,Q,,X,×,Y,，,S,,Y,×,Z,，,R,,,Z,×,W,，则,,(,R,∘,S,)∘,Q,=,R,∘(,S,∘,Q,),证明：,对任取<,x,,,w,>,,(,R,∘,S,),∘,Q,,(,,y,)(,x,,y,,Q,,∧,,y,,,w,,R,∘,S,),,(,,y,)(,,x,,,y,,Q,),∧(,,z,)(,y

6、,,,z,,S,∧,z,,,w,,R,)),,(,,y,)(,,z,)(,,x,,,y,,Q,),∧,z,,,w,,R,∧,y,,,z,,S,),,(,,z,)(,,y,)(,z,,,w,,R,∧,,x,,,y,,Q,∧,y,,,z,,S,),,(,,z,)(,z,,,w,,R,)∧(,,y,)(,,x,,,y,,Q,∧,y,,,z,,S,),,(,,z,)(,z,,,w,,R,∧,,x,,,z,,S,∘,Q,),,x,,,w,,R,∘,(,S,∘,Q,),所以 (,R,∘,S,)∘,Q,

7、=,R,∘(,S,∘,Q,),,F,∘,G,= {<,x,, y> |,,z,(<,x,,,z,>,,G,,<,z,,,y,>,,F,) },,关系基本运算的性质定理10.3.2 设X，Y，Z，W是集合,关系基本运算的性质,定理10.3.3,,设,X, Y, Z,是集合,,S、T,,X,×,Y,,,R,,,Y,×,Z,,,则,,R,∘(,S,∪,T,)=,R,∘,S,∪,R,∘,T,(,R,∪,S,)∘,T,=,R,∘,T,∪,S,∘,T,,R,∘(,S,∩,T,),,R,∘,S,∩,R,∘,T,(,R,∩,S,)∘,T,,R,∘,T,∩,S,∘,T,证明：,仅证明⑶，类似地

8、可证明⑴、⑵和⑷。,,,x,,,z,,R,∘,(,S,∩,T,),,(,,y,)(,,y,,,z,,R,∧,,x,,,y,,S,∩,T,),,(,,y,)(,,y,,,z,,R,∧(,,x,,,y,,S,∧,,x,,,y,,T,)),,(,,y,)((,,y,,,z,,R,∧,,x,,,y,,S,)∧(,y,,,z,,R,∧,,x,,,y,,T,)),,(,,y,)(,,y,,,z,,R,∧,,x,,,y,,S,)∧(,,y,)(,,y,,,z,,R,∧,,x,,,y,,T,),,x,,,

9、y,,R,∘,S,∧,,x,,,y,,R,∘,T,,x,,,y,,R,∘,S,∩,R,∘,T,故,R,∘(,S,∩,T,),,R,∘,S,∩,R,∘,T,关系基本运算的性质 定理10.3.3 设X, Y, Z是,,10.4 关系的性质,关系的,自反性,定义:,设,R,A,×A，,(,,x,)(,x,A,→,,x,,,x,,R,),，则称,R,在A,上是自反的,。,自反关系的特点,其关系矩阵,M,(,R,)的主对角线全为1,；,其关系图中每一个结点上都有自回路。,实例,：设,A={1,2,3}，A上的二元关系R,R,={,,1,1,,,,,2,2,,,

10、,,3,3,,,,,1,2,},自反关系,——,全域关系,E,A,恒等关系,I,A,,小于等于关系,L,A,,整除关系,D,A,,10.4 关系的性质关系的自反性定义: 设RA×A，自反关,关系的,反自反性,定义：,设,R,,A,×,A,，,(,,x,)(,x,,A,→,,x,,,x,,R,),，则称,R,在,X,上是,反自反的,。,反自反关系的特点,其关系矩阵,M,(,R,) 的主对角线全为0,；,其关系图中每一个结点上都没有自回路。,实例：,设,A,={1,2,3,},，,X,上的二元关系,,R,={,,1,2,,,,,2,3,,,,,3,1,},，,反自

11、反关系,——,实数集上的小于关系,幂集上的真包含关,,关系的反自反性定义： 设RA×A，反自反关系——,实例,例1,A,={1,2,3},,R,1,,,R,2,,,R,3,是,A,上的关系, 其中,R,1,＝{,,,},R,2,＝{},R,3,＝{,},R,1,自反,,,R,2,反自反,,,R,3,既不是自反也不是反自反的,,实例例1 A={1,2,3}, R1, R2, R3是,关系的,对称性,定义：,,设,R,A,×A，,(,,x,)(,,y,)(,x,A,∧,y,A,∧,,x,,,y,,R,→,,y,,,x,,R,),则称,R,在,A,上是对称的,。,对称

12、关系的特点,其关系矩阵,M,(,R,),是对称阵。,其关系图中，如果两个不同的结点间有边，一定有方向相反的两条边。,实例：,设,A,={1,2,3}，,A,上的二元关系,R,={,,1,2,,,,,2,1,,,,,3,3,},,对称关系,——,全域关系,E,A,,,恒等关系,I,A,空关系,,关系的对称性定义： 设RA×A， 对称关系——,关系的,反对称性,定义：,,设,R,A,×A，,(,,x,)(,,y,)(,x,A,∧,y,A,∧,,x,,,y,,R,∧,,y,,,x,,R,→(,x,=,y,)),则称,R,在,A,上是反对称的,。,反对称关系的特点

13、,其关系矩阵,M,(,R,) 中以主对角线为轴的对称位置上不能同时为1(主对角线除外),。,其关系图中，每两个不同的结点间不能有方向相反的两条边。,实例：,设,A,={1,2,3}，,A,上的二元关系,R,={,,1,2,,,,,2,3,,,,,3,3>,},,反对称关系,——,恒等关系,I,A,空关系,关系的反对称性定义： 设RA×A， (,实例,例2 设,A,＝{1,2,3},,R,1,,,R,2,,,R,3,和,R,4,都是,A,上的关系,,其中,R,1,＝{,}，,R,2,＝{,,},R,3,＝{,}，,R,4,＝{,,},,R,1,,对称、反对称,

14、.,R,2,,对称，不反对称,.,R,3,,反对称，不对称,.,R,4,,不对称、也不反对称,.,,实例例2 设A＝{1,2,3}, R1, R2, R3和,关系的,传递性,,定义：,设,R,,A,×,A,,,x,,y,,z,(<,x,,,y,>∈,R,∧<,y,,,z,>∈,R,→<,x,,,z,>∈,R,),,则称,R,是,A,上的,传递,关系.,传递关系的特点,其关系矩阵,M,(,R,),中1所在位置,,M,(,R,),中相应位置都是1,如果顶点,x,i,连通到,x,k,, 则从,x,i,到,x,k,有边,实例：,A,上的全域关系,E,A,,恒等关系,I,A,和空关系,,小

15、于等于关系, 小于关系，整除关系，包含关系，,真包含关系,,关系的传递性 定义：设R A×A,实例,例3 设,A,＝{1,2,3},,R,1,,,R,2,,,R,3,是,A,上的关系, 其中,R,1,＝{,},R,2,＝{,},R,3,＝{},R,1,和,R,3,是,A,上的传递关系,R,2,不是,A,上的传递关系,,实例例3 设A＝{1,2,3}, R1, R2, R3是A,判断下图中关系的性质,,图1,图2,图3,自反性,×,×,√,反自反性,×,√,×,对称性,√,×,×,反对称性,×,√,√,传递性,×,√,×,判断下图中关系的性质 图1图2图3自反性××√反自反性×√×,10

16、.4.2 运算与性质的关系,设,R, S,是自反的,,则,,I,A,,R,，,I,A,,S,所以,I,A,,R,∪,S,，,I,A,,R,∩,S,，,即,R,∪,S,和,R,∩,S,也是自反的,,自反性,反自反性,对称性,反对称性,传递性,R,1,,1,,√,√,√,√,√,R,1,∩,R,2,,√,√,√,√,√,R,1,∪,R,2,,√,√,√,×,×,R,1,,R,2,,×,√,√,√,×,R,1,∘,R,2,,√,×,×,×,×,原有性质,运算,,,设,R,={},,S,={},则,,R,和,S,都是,传递的、反对称的,但,R,∪,S,={,},,不是传递的，不是反对称的,

17、,10.4.2 运算与性质的关系 设R, S是自反的, 自反性,10.5 关系的闭包,设,R,为,A,上的关系,,,n,为自然数,,,则,R,的,n,次幂,定义为：,,(1),R,0,={<,x,,,x,> |,x,∈,A,}=,I,A,（恒等关系）,,,(2),R,n,+1,=,R,n,∘,R,,（,n,≥,1,）,注意：,对于,A,上的任何关系,R,1,和,R,2,都有,,R,1,0,=,R,2,0,=,I,A,,,对于,A,上的任何关系,R,都有,,R,1,=,R,0,∘,,R,,=R,10.5 关系的闭包设R为A上的关系, n为自然数, 则 R,10.5.1 多个关系合成的运算,[P1

18、74例3] 设,A,={,a,,,b,,,c,,,d,},,R,={<,a,,,b,>,<,b,,,a,>,<,b,,,c,>,<,c,,,d,>},,求,R,0,,R,1,,R,2,,R,3,,R,4,,R,5,。,解：,R,0,=,I,A,，其关系矩阵和关系图分别为,,,10.5.1 多个关系合成的运算[P174例3] 设A={,多个关系合成的运算,,设,A,={,a,,,b,,,c,,,d,}, R={<,a,,,b,>,<,b,,,a,>,<,b,,,c,>,<,c,,,d,>},求,R,0,,R,1,,R,2,,R,3,,R,4,,R,5,。,解：,R,1,=,R,，其关系矩阵和

19、关系图为,,多个关系合成的运算设A={a,b,c,d}, R={,<,b,,,a,>,<,b,,,c,>,<,c,,,d,>},解：,R,2,=,R,∘,R,,，其关系矩阵为,,,,,,关系图,,多个关系合成的运算设A={a,b,c,d}, R={,<,b,,,a,>,<,b,,,c,>,<,c,,,d,>},解：,R,3,=,R,2,∘,R,,，其关系矩阵为,,,,,,关系图,,多个关系

20、合成的运算设A={a,b,c,d}, R={

21、A,上的关系,,,m,,,n,∈,N,,,则,,(1),R,m,∘,R,n,=,R,m,+,n,(2) (,R,m,),n,=,R,mn,,证,(1),,用归纳法  对,,m,∈,N,,,施归纳于,n,.,,若,n,=0,,,则有,R,m,∘,R,0,=,R,m,∘,I,A,=,R,m,=,R,m,+0,,,假设,R,m,∘,R,n,=,R,m,+,n,,,则有,,R,m,∘,R,n,+1,=,R,m,∘(,R,n,∘,R,),=(,R,m,∘,R,n,)∘,R,=,R,m,+,n,+1,,,,所以,,,对,,m,,,n,∈,N,有,R,m,∘,R,n,=,R,m,+,n,.,多

22、个关系合成的运算的性质,定理 设A是的限集, R是A上的关系, m, n∈N, 则,10.5.2 关系闭包的定义,闭包的,定义,,设,R,是非空集合,A,上的关系,,R,的,自反,（,对称,或,传递,）,闭包,是,A,上的关系,R,,, 使得,R,,满足以下条件：,（1）,R,,是,自反的,（,对称的,或,传递的,）,（2）,R,,R,,（3）对,A,上任何包含,R,的,自反,(,对称,或,传递,)关系,R,,有,R,,R,,.,一般地，将,,R,的,自反闭包,记作,r,(,R,),,对称闭包,记作,s,(,R,),,传递闭包,记作,t,(,R,).,包含,R,的最小自反关系是,R,的,自反闭包,包含,R,的最小对称关系是,R,的,对称闭包,包含,R,的最小传递关系是,R,的,传递闭包,10.5.2 关系闭包的定义闭包的定义 包含R的最小自反关,作业11,P189: 15，16,,P190: 18，22,作业11P189: 15，16,,