chap2 关系讲义.ppt

* 离散数学 * 定理2.4.1的证明 证明: (必要性) 设A, ≦为良序集. ⅰ) 任取x,y∈A，则{x,y}有最小元x或y，于是x≦y或y≦x，故A, ≦是全序集。 ⅱ) 任取A的非空子集B，由良序集定义知B有最小元a，显然a也是B的极小元。 (充分性) 设A, ≦满足⑴, ⑵，对A的任意非空子集B，由⑵知B有极小元a，对任意x∈B，由⑴有x≦a或a≦x，∵a是B的极小元，由x的任意性,故必有a≦x，∴a是B的最小元，因而A, ≦是良序集。 * 离散数学 * (接上页)定理2.2.6 的证明 (c)设S是A上一个传递关系，且 R ? S, 下证R* ? S. 任取x,y∈ R* ,则必有正整数n, 使得x,y∈ Rn, 若n=1，则x,y∈R ? S,即x,y∈S；若n1， 则有z1, ? ? ? , zn-1，使xRz1 , z1Rz2, ? ? ? , zn-2Rzn-1, zn-1Ry ，由于S具有传递性，且 R ? S ,所以, x,z2∈S，x,z3∈S，? ? ? ，x,y∈S， 故R* ? S。 综上证得（3）成立。 * 离散数学 * A为有限集时,求 关系的传递闭包 定理2.2.7 设A为n个元素的集合，R是定义在A上的二元关系，则 t(R) = R∪R2 ∪ ? ? ? ∪ Rn n 证明：只需证明对任何整数k?1有：Rn+k ? ∪Ri . i=1 任取x,y∈ Rn+k,令z0=x , zn+k=y，存在z1,z2, ? ? ?,zn+k-1∈A 使 z0Rz1 , z1Rz2, ? ? ? , zn+k-2Rzn+k-1, zn+k-1R zn+k ，(2.1) 注意到(2.1)中共有(n+k+1)个元素，而A中只有n个元素， 故必存在0? ij ? n+k ,使得zi=zj 。于是有： z0Rz1 , z1Rz2, ? ? ? , zi-1Rzi, ziRzj+1 ,? ? ?, zn+k-1R zn+k ，(2.2) 易知，(2.2)中共有m=n+k+1-(j-i)个元素。若mn,则重复以 上过程，直到m?n。从而z0Rmzn+k , 即x,y∈Rm， n 所以Rn+k ? ∪Ri ， k?1. i=1 * 离散数学 * 定理2.2.7证明的示意图 Zn+k-1 … Z0 Zn+k Z1 ∵ |A| = n ∴其中存在Zi = Zj，即 Zj … Z0 Zn+k Zi … … Zi Zj × × × Z0 Zn+k Zi … … * 离散数学 * 用关系矩阵实现关系的运算 在有穷集合上的关系 R可以表示为关系矩阵MR。 所以，在有穷集合上的关系之间的运算可以通过它们的关系矩阵之间的运算来实现。 关系矩阵的运算有：转置，并，交以及乘积 * 离散数学 * 关系矩阵的转置 关系矩阵MR的转置是将其转置，记为MRT，令其第i行第j列元素为m’ij。 m’ij为0或1，而 m’ij = 1 当且仅当 mji = 1。 显然MRT是R-1的关系矩阵，即MR-1。 例如 若 MR= ，则 MRT= 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 1 * 离散数学 * 关系矩阵的并 如果R和S都是A到B的关系，A, B都是有穷集合，令MR和MS分别为R和S的关系矩阵，则MR和MS的并，记为MR∪S， MR∪S的元素为MR和MS的对应元素之或，即令aij，bij和cij分别表示MR、MS和MR∪S中的元素，则cij = aij ∨ bij 。 显然MR∪S就是R∪S的关系矩阵。 例如： 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0