离散结构及应用-ALL解析.ppt

4.1 关系基础（概念） 定义：任何序偶的集合，称为一个二元关系。 x,y?R ? xRy 也称之为x与y有Ｒ关系。 前一个叫后缀表示，后一个叫中缀表示。 = ≤ ≥ x2+y2=4 x y 4.1 关系基础（概念） 定义域(domain) ：设R?A×B，由所有x,y?R的第一个元素组成的集合，称为R的定义域，记作dom R，即 dom R={x|?y(x,y?R)} 值域(range) ：设 R?A×B，由所有x,y?R的第二个元素组成的集合，称为R的值域，记作ran R，即 ran R={y|?x(x,y?R)} 4.1 关系基础（表示方法） 1.枚举法：即将关系中所有序偶一一列举出，写在大括号内。如前的R2 ={ 1,1,1,2,1,3, 1,4,2,2, 2,3, 2,4, 3,3, 3,4,4,4} 。 2.谓词公式法：用谓词公式表示序偶的第一元素与第二元素间的关系。例如 R={x,y|xy} 3.有向图法：R?A×B, 用两组小圆圈(称为 结点)分别表示A和B的元素，当x,y?R时，从x到y引一条有向弧(边)。这样得到的图形称为R的关系图。 4.1 关系基础（表示方法） 4.矩阵表示法：有限集合之间的关系也可以用矩阵来表示，这种表示法便于用计算机来处理关系。 设A={a1, a2, ?, am}，B={b1, b2, ?, bn}是个有限集， R?A×B，定义R的m×n阶矩阵。 MR=(rij)m×n，其中 rij= 1 若ai,bj∈R 0 若ai,bj∈R (1≤i≤m,1≤j≤n) 4.1 关系基础（表示方法） 4.矩阵表示法 R3={ 1,a,1,c,2,b,3,a,4,c} R4={ 1,1,1,4,2,3,3,1,3,4,4,1,4,2} 1 0 1 0 1 0 1 0 0 0 0 1 4×3 1 2 3 4 a b c 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 4×4 1 2 3 4 1 2 3 4 4.1 关系基础（自反性） 自反性：设R是集合A中的关系，如果对于任意x∈A，都有x,x∈R (xRx)，则称R是A中自反关系。即 R是A中自反的??x(x?A?xRx) 从关系有向图看自反性:每个结点都有环。 从关系矩阵看自反性：主对角线都为1。 反自反性：设R是集合A中的关系，如果对于任意的x∈A都有x,x?R ，则称R为A中的反自反关系。即R是A中反自反的??x(x?A?x,x?R) 从关系有向图看反自反性:每个结点都无环。 从关系矩阵看反自反性：主对角线都为0。 4.1 关系基础（对称性） 对称性：R是集合A中关系,若对任何x, y∈A,如果有xRy,必有yRx,则称R为A中的对称关系。R 是A上对称的??x?y((x?A?y?A?xRy) ?yRx) 从关系有向图看对称性:在两个不同的结点之间，若有边的话，则有方向相反的两条边。 从关系矩阵看对称性：以主对角线为对称的矩阵。 邻居关系是对称关系，朋友关系是对称关系。 4.1 关系基础（传递性） 传递性：R是A中关系，对任何x,y,z∈A,如果有xRy,和yRz,就有xRz,则称R为A中传递关系。 即R在A上传递??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz) 实数集中的≤、＜，集合?、?是传递的。 从关系关系图和关系矩阵中不易看清是否有传递性。必须直接根据传递的定义来检查。 4.1 关系基础（性质判定） 判定 关系有向图 系矩阵 自反性 反自反性 对称性 传递性 反对称性 每个结点都有环 主对角线全是1 每个结点都无环 主对角线全是0 不同结点间如果有边,则有方向相反的两条边. 是以对角线为对称 的矩阵 不同结点间,最多有一条边. 以主对角线为对称的位置不会同时为1 如果有边a,b,b,c,则也有边a,c. 或者定义的前件为假. 如果aij=1,且ajk=1,则aik=1 4.1 关系基础（3个特殊关系） 1.空关系Φ：因为Φ?A×B，(或Φ?A×A)，所以Φ也是一个从A到B(或A上)的关系，称之为空关系。即无任何元素的关系，它的关系图中只有结点,无任何边；它的矩阵中全是0。 2.完全关系(全域关系) ：A×B(或A×A)本身也是一个从A到B(或A上) 的关系，称之为完全关系。即含有全部序偶的关系。它的矩阵中全是1。 3.A上的恒等关系IA： IA ? A×A，且 IA = {x,x|x∈A} 称之为A上的恒等关系。 4.2 关系运算（基于集合的） 由于关系就是集合，所以集合的∩、∪、-、 ?和~运算对关系也适用。 例：A 是