离散数学(二元关系第二次课zyl).ppt

例6.3.6 设A={1,2,3,4}，B={a,b,c,d}，C={2,3,4,5}，R是从A到B的一个关系且R={1,a,2,c,3,b, 4,b,4,d}，S是从B到C的一个关系且S={a,2, b,4, c,3,c,5,d,5}。 （1）计算R-1，并画出R和R-1的关系图； （2）写出R和R-1的关系矩阵； （3）计算(RoS)-1和S-1oR-1。 例6.3.6 解 (1)R-1={1,a,2,c,3,b,4,b,4,d}-1 ={a,1,c,2,b,3,b,4,d,4}， R和R-1的关系图见图6.3.3和图6.3.4。 例6.3.6 解（续） 注意 将R的关系图中有向边的方向改变成相反方向即得R-1的关系图，反之亦然； 将R的关系矩阵转置即得R-1的关系矩阵，即R和R-1的关系矩阵互为转置矩阵。 R-1的前域与后域正好是R的后域和前域，即domR=ranR-1，domR-1=ranR； |R|=|R-1|； (RoS)-1=S-1oR-1。 定理6.3.3 设A、B和C是任意三个集合，R,S分别是从A到B，B到C的二元关系，则 (RoS)-1=S-1oR-1。 定理6.3.4 设R，S是从集合A到集合B的关系，则有 (R∪S)-1＝R-1∪S-1； (分配性) (R∩S)-1＝R-1∩S-1； (R-S)-1＝R-1-S-1； (　)-1＝ 　； (可换性) (A×B)-1＝(B×A)；　 S?R ? S-1?R-1； (单调性) 例6.3.7 设A={1,2,3,4,5,6}，定义在A上的关系 R={1,1,1,2,2,3,3,4,4,5,5,6}， S={1,2,2,3,3,4,4,5,5,6}， 计算： 解 解（续1） ={1,1,1,2,1,3, 1,4,1,5,1,6,2,3,2,4,2,5,2,6, 3,4,3,5,3,6,4,5,4,6,5,6}； 解（续2） （2) S1＝S， S2＝S?S＝{1,3,2,4,3,5,4,6}， S3＝S?S?S＝S2?S＝{1,4,2,5,3,6}， S4＝S3?S＝{1,5,2,6}， S5＝S4?S＝{1,6}， S6＝S5?S＝Φ， S7＝Φ， …， Sn＝Φ　(n＞5)。 解（续3） ={1,2,1,3,1,4,1,5, 1,6,2,3,2,4,2,5,2,6,3,4,3,5, 3,6,4,5,4,6,5,6}； 定理6.3.5 设A是有限集合，且|A|＝n，R是A上的二元关系，则： 6.4 关系的性质------重点 本节涉及到的关系，如无特别声明，都是假定其前域和后域相同。即都为定义在集合A上的关系，且A是非空集合。对于前后域不相同的关系，其性质无法加以定义。 6.4.1 关系性质的定义 1、自反性和反自反性 定义6.4.1设R是集合A上的关系， 如果对任意x∈A，都有x,x∈R，那么称R在A上是自反的(Reflexive)，或称R具有自反性(Reflexivity)； 例如：朋友关系。 如果对任意x∈A，都有x,x R，那么称R在A上是反自反的(Antireflexive)，或称R具有反自反性(Antireflexivity)。 例如：父子关系。 符号化 R在A上是自反的 ?(?x)((x∈A)→(x,x∈R))=1 R在A上是反自反的 ?(?x)((x∈A)→(x,x R))=1 R在A上不是自反的 ?(?x)((x∈A)∧(x,x R))=1 R在A上不是反自反的 ?(?x)((x∈A)∧(x,x∈R))=1 例6.4.1 设A={1,2,3}，定义A上的关系R,S和T如下： （1）R={1,1,1,2,2,2,3,3}； （2）S={1,2,2,3,3,1}； （3）T={1,1,1,2,1,3,3,1,3,3}。 例6.4.1 解（续） 结论 关系R是自反的?R不是反自反的 存在既不是自反的也不是反自反的关系 关系R是自反的? 关系图中每个结点都有环 关系R是反自反的? 关系图中每个结点都无环 关系R是自反的 ? 关系矩阵的主对角线上全为1 关系R是反自反的?关系矩阵的主对角线上全为0 例6.4.2 设A={a,b}，试计算A上所有具有自反性的关系R的个数。 解 因为A2={a,a,b,b,a,b,b,a}，所以A上具有自反性的关系R的个数为： C(2,0) + C(2,1) + C(2,2) = 4。 2、对称性和反对称性 定义6.4.2 设R是集合A上的关