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

1、P85: 3(4)n指出下列推演中的错误，并改正之 ( x)P(x) = F ( x)P(x) ( x)P(x)改为：改为：n( x)P(x) = F ( x)P(x) ( x)P(x)或n( x)P(x) = F ( x)P(x) ( x)P(x)必有必有( x)P(x)=F不一定有不一定有( x)P(x)=F必有必有( x)P(x) = F P195: 1(4)n列出下列各集合所有的元素：A=z|z=x, yxZyZ0 x2 -2y1A=0, -2 , 0, -1 , 0, 0 , 0, 1 1, -2 , 1, -1 , 1, 1 2, -2 , 2, -1 , 2, 0 , 2, 1

2、第10章 关 系10.1 二元关系10.2 关系矩阵和关系图10.3 关系的逆、合成、限制和象10.4 关系的性质10.5 关系的闭包10.6 等价关系和划分10.7 相容关系和覆盖10.8 偏序关系关系的合成运算 F G = | z ( G F) x1 1x2 2z3 3z2 2z1 1y1 1y2 2F GFG关系基本运算的性质 n 定理定理10.3.1设设X, Y, Z是集合是集合, R XY, S YZ1.dom(R 1)=ran(R)2. ran(R 1)=dom(R)3. (R 1) 1=R4.(S R) 1= R 1 S 1n 证证 (4) 对任取对任取 x,z(S R)-1 z

3、,x(R S) ( y)( z,yS y,xR) ( y)( y,zS-1 x,yR-1) x,zS-1 R-1R 1 = | R F G = | z ( G F) 关系基本运算的性质n 定理定理10.3.2 设X，Y，Z，W是集合，QXY，SYZ，R ZW，则 (R S) Q= R (S Q)n 证明：证明：对任取对任取 (R S) Q ( y)( x,yQ y,wR S) ( y)( x,yQ)( z)( y,zS z,wR) ( y)( z)( x,yQ) z,wR y,zS) ( z)( y)( z,wR x,yQ y,zS) ( z)( z,wR)( y)( x,yQ y,zS) (

4、 z)( z,wR x,zS Q) x,wR (S Q)n 所以所以 (R S) Q=R (S Q) F G = | z ( G F) 关系基本运算的性质n 定理10.3.3 设X, Y, Z是集合, S、TXY, R YZ, 则1. R (ST)=R SR T2. (RS) T=R TS T3. R (ST) R SR T4. (RS) T R TS Tn 证明：仅证明，类似地可证明、和。仅证明，类似地可证明、和。 x,zR (ST) ( y)( y,zR x,yST) ( y)( y,zR( x,yS x,yT) ( y)( y,zR x,yS)( y,zR x,yT) ( y)( y,z

5、R x,yS)( y)( y,zR x,yT) x,yR S x,yR T x,yR SR Tn 故故 R (ST) R SR T100010011)(RM10.4 关系的性质n 关系的自反性定义: 设RAA，( x)(x A x,xR)，则称，则称R在在A上是自反的上是自反的。n 自反关系的特点n其关系矩阵其关系矩阵M(R)的主对角线全为的主对角线全为1；n其关系图中每一个结点上都有自回路。其关系图中每一个结点上都有自回路。n 实例：设A=1,2,3，A上的二元关系R R= 1,1 , 2,2 , 3,3 , 1,2 自反关系自反关系全域关系全域关系EA恒等关系恒等关系IA 小于等于关系小于

6、等于关系LA 整除关系整除关系DA关系的反自反性n 定义： 设RAA，( x)(x A x,xR)，则称，则称R在在X上是上是反自反的反自反的。n 反自反关系的特点n其关系矩阵其关系矩阵M(R) 的主对角线全为的主对角线全为0；n其关系图中每一个结点上都没有自回路。其关系图中每一个结点上都没有自回路。n 实例：设A=1,2,3，X上的二元关系 R= 1,2 , 2,3 , 3,1 ，001100010)(RM反自反关系反自反关系实数集上的小于关系实数集上的小于关系幂集上的真包含关幂集上的真包含关实例例例1 A=1,2,3, R1, R2, R3是是A上的关系上的关系, 其中其中 R1, R2

7、R3,R1自反自反, R2反自反反自反, R3既不是自反也不是反自反的既不是自反也不是反自反的关系的对称性n 定义： 设RAA，( x)( y)(x Ay A x,yR y,xR) 则称则称R在在A上是对称的上是对称的。n 对称关系的特点n其关系矩阵其关系矩阵M(R) 是对称阵。是对称阵。n其关系图中，如果两个不同的结点间有边，一定有方其关系图中，如果两个不同的结点间有边，一定有方向相反的两条边。向相反的两条边。n 实例：设A=1,2,3，A上的二元关系R= 1,2 , 2,1 , 3,3 100001010)(RM 对称关系对称关系全域关系全域关系EA, 恒等关系恒等关系IA空关系空关系关系

8、的反对称性n 定义： 设RAA， ( x)( y)(x Ay A x,yR y,xR(x=y)则称则称R在在A上是反对称的上是反对称的。n 反对称关系的特点n 其关系矩阵其关系矩阵M(R) 中以主对角线为轴的对称位置上不能同时为中以主对角线为轴的对称位置上不能同时为1(主主对角线除外对角线除外)。n 其关系图中，每两个不同的结点间不能有方向相反的两条边。其关系图中，每两个不同的结点间不能有方向相反的两条边。n 实例：设A=1,2,3，A上的二元关系R= 1,2 , 2,3 , 3,3 反对称关系反对称关系恒等关系恒等关系IA空关系空关系100100010)(RM实例例例2 设设A1,2,3,

9、R1, R2, R3和和R4都是都是A上的关系上的关系, 其中其中 R1,， R2, R3,， R4, R1 对称、反对称对称、反对称. R2 对称，不反对称对称，不反对称. R3 反对称，不对称反对称，不对称. R4 不对称、也不反对称不对称、也不反对称.关系的传递性 n 定义：设R AA xyz(RR R) 则称R是A上的传递关系.n 传递关系的特点n其关系矩阵其关系矩阵M(R) 中中1所在位置所在位置, M(R) 中相应位置都是中相应位置都是1n如果顶点如果顶点 xi 连通到连通到xk , 则从则从 xi到到 xk 有边有边n 实例：实例：nA上的全域关系上的全域关系EA,恒等关系恒等关

10、系IA和空关系和空关系n小于等于关系小于等于关系, 小于关系，整除关系，包含关系，小于关系，整除关系，包含关系，n真包含关系真包含关系实例例例3 设设A1,2,3, R1, R2, R3是是A上的关系上的关系, 其中其中 R1, R2, R3R1 和和 R3 是是A上的传递关系上的传递关系 R2不是不是A上的传递关系上的传递关系判断下图中关系的性质 图1图2图3自反性自反性反自反反自反性性对称性对称性反对称反对称性性传递性传递性10.4.2 运算与性质的关系 设设R, S是自反的是自反的, 则则 IA R，IA S 所以所以 IA RS，IA RS， 即即 RS和和RS也是自反的也是自反的自反

11、性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R1 1 R1R2 R1R2 R1 R2 R1 R2 原有性质原有性质运算运算 设设R=, S=则则 R和和S都是都是传递的、反对称的传递的、反对称的但但 RS=, 不是传递的，不是反对称的不是传递的，不是反对称的10.5 关系的闭包n 设设R为为A上的关系上的关系, n为自然数为自然数, 则则 R 的的 n次幂次幂定义为：定义为： (1) R0= | xA =IA（恒等关系）（恒等关系） (2) Rn+1 = Rn R （n1）n 注意：注意：n 对于对于A上的任何关系上的任何关系R1和和R2都有都有 R10 = R20 = I

12、A n 对于对于A上的任何关系上的任何关系 R 都有都有 R1 = R0 R =R10.5.1 多个关系合成的运算nP174例3 设A=a,b,c,d, R=, 求R0,R1,R2,R3,R4,R5。n解：R0=IA，其关系矩阵和关系图分别为AIR10000100001000010多个关系合成的运算0000100001010010Rn设A=a,b,c,d, R=,n求R0,R1,R2,R3,R4,R5。n解：R1 = R，其关系矩阵和关系图为多个关系合成的运算n 设A=a,b,c,d, R=,n 解：R2 = R R ，其关系矩阵为0000000010100101000010000101001

13、000001000010100102R）（jkijnjikrrr12关系图关系图多个关系合成的运算n 设A=a,b,c,d, R=,n 解：R3 = R2 R ，其关系矩阵为00000000010110100000100001010010000000001010010123RRR）（jkijnjikrrr213关系图关系图同理，同理， R4 = R3 R =R2， R5=R4 R=R3还可以得到还可以得到R2=R4=R6=, R3=R5=R7=,0000000001011010,000000001010010154RR多个关系合成的运算说明：对于有限集说明：对于有限集A和和A上的关系上的关系R

14、，R的不同的幂只存的不同的幂只存在有限个在有限个R0, R1, R2, R3,的关系图如下图所示的关系图如下图所示多个关系合成的运算n定理定理 设A是的限集, R是A上的关系, m, nN, 则 (1) Rm Rn=Rm+n (2) (Rm)n=Rmn n证证(1) 用归纳法用归纳法 对对 mN, 施归纳于施归纳于n. 若若n=0, 则有则有 Rm R0=Rm IA=Rm=Rm+0 假设假设Rm Rn=Rm+n, 则有则有 Rm Rn+1 =Rm (Rn R) =(Rm Rn) R =Rm+n+1 , 所以所以, 对对 m, nN有有Rm Rn=Rm+n. 多个关系合成的运算的性质10.5.2

15、 关系闭包的定义n 闭包的定义定义 设设R是非空集合是非空集合A上的关系上的关系, R的的自反自反（对称对称或或传递传递）闭包闭包是是A上的关系上的关系R , 使得使得R 满足以下条件：满足以下条件：（1）R 是是自反的自反的（对称的对称的或或传递的传递的）（2）R R （3）对）对A上任何包含上任何包含R的的自反自反(对称对称或或传递传递)关系关系 R 有有 RR . n 一般地，将一般地，将 R 的的n自反闭包自反闭包记作记作 r(R), n对称闭包对称闭包记作记作 s(R), n传递闭包传递闭包记作记作 t(R).包含包含R的最小自反关系是的最小自反关系是R的的自反闭包自反闭包包含包含R的最小对称关系是的最小对称关系是R的的对称闭包对称闭包包含包含R的最小传递关系是的最小传递关系是R的的传递闭包传递闭包作业11nP189: 15，16,nP190: 18，22