8.1-8.3

nullnull**8.1 Relations and Their Properties 关系及其性质 8.2 n-ary Relations and Their Application n元关系及其应用 8.3 Representing Relations关系的示 8.4 Closures of Relations 关系的闭包 8.5 Equivalence Relations 等价关系 8.6 Partial Orderings 偏序Chapter 8 Relations 关系null**8.1 Relations and Their Properties关系及其性质 【Definition】A binary relation R from a set A to a set B is a subset of AB. 设A、B为任意两个集合，称笛卡儿积AB的子集R为集合A到B的一个二元关系。若(x,y)∈R，则称x与y有关系R，记为 xRy Note: A binary relation R is a set. 关系R是一个集合 R  AB 关系R的范围 〖Example 1〗 (1) Let A and B be sets, null**8.1 Relations and Their Properties Function As Relation 作为关系A function f from a set A to a set B is a relation form A to B. Conversely, if R is a relation from A to B, is it a function? 〖Example 2〗f: AB, f(1)=f(3)=1,f(2)=f(4)=0 〖Example 3〗null**8.1 Relations and Their Properties Relations On A Set 集合A上的关系 【Definition】A relation on the set A is a relation form A to A. 定义：集合A的关系是从A到A的关系 Note: 特别，若关系定义中的A=B，则称R为集合A上的二元关系 R  AA〖Example 4〗 Let Question: How many binary relations are there on a set A with n elements? n元素集合有多少个关系？null**8.1 Relations and Their Properties Representing Relations关系的表示 The methods of representing relation: list its all ordered pairs using a set build notation/specification by predicates 2D table二维表格 Connection matrix /zero-one matrix Directed graph/Digraph null**8.1 Relations and Their Properties 〖Example 5〗null**8.1 Relations and Their Properties Connection Matrices 关系矩阵For example, null**8.1 Relations and Their Properties Question: How many binary relations are there on a set A with n elements? 0,1By the product rule, null**8.1 Relations and Their Properties Directed graph/Digraph 有向图【Definition】A directed graph or a digraph, consists of a set V of vertices together with a set E of ordered pairs of elements of V called edges(or arcs)。 The vertices a,b is called the initial and terminal vertices of the edge (a,b). 定义：一个有向图由顶点（或结点）集V和边（或弧）集E组成，其中边集是V中元素的有序对的集合。顶点a叫做边（a,b)的始点，而顶点b叫做这条边的终点 For example,null**8.1 Relations and Their Properties 〖Example 6〗A = {0, 1, 2,3} R = {(0,0), (0,3), (2,0),(2,1),(2,3),(3,2)}. null**8.1 Relations and Their Properties Special Properties of Binary Relations 二元关系的特殊性质Reflexive 自反的 Irreflexive 反自反的 Symmetric 对称的 Antisymmetric 反对称的 Transitive 传递的null**8.1 Relations and Their Properties Special Properties of Binary Relations Reflexive自反的 Irreflexive Symmetric Antisymmetric Transitive null**8.1 Relations and Their Properties 若对每个x∈A，均有xRx,则称R为自反的 Questions: (1) What do we know about matrices representing reflexive relations? null**(2) What do we know about digraphs representing reflexive relations? There is a loop at every vertex of the directed graph.对于有向图上的每个顶点都有个环 8.1 Relations and Their Properties null**8.1 Relations and Their Properties Special Properties of Binary Relations Reflexive Irreflexive 反自反的 Symmetric Antisymmetric Transitive null**8.1 Relations and Their Properties null**8.1 Relations and Their Properties Special Properties of Binary Relations Reflexive Irreflexive Symmetric 对称的 Antisymmetric Transitive null**8.1 Relations and Their Properties 对任意x,y∈A，若xRy,则yRx,就称R是对称的 Questions: The connection matrix of a reflexive relations? 【Definition】A relation R on a set A is symmetric if Digraph? If there is an arc (x, y) there must be an arc (y, x). null**8.1 Relations and Their Properties Special Properties of Binary Relations Reflexive Irreflexive Symmetric Antisymmetric 反对称的 Transitive null**8.1 Relations and Their Properties 对任意x,y∈A，若xRy且yRx，则x=y，就称R是反对称的 Note: (1) 【Definition】A relation R on a set A is antisymmetric if (2) null**8.1 Relations and Their Properties (3) If there is an arc from x to y there cannot be one from y to x if x y.如果x y，若有一条从x到y的弧，那么不可能存在从y到x的弧。 (4) The symmetric and antisymmetric relations are not opposites. 对称的与反对称的关系不是对立的 For example,null**8.1 Relations and Their Properties Special Properties of Binary Relations Reflexive Irreflexive Symmetric Antisymmetric Transitive 传递的null**8.1 Relations and Their Properties 定义：如果对于x,y,z ∈A （x,y) ∈R并且(y,z) ∈R则(x,z) ∈R,那么集合A上的关系R叫做传递的 Note: (1) 【Definition】A relation R on a set A is transitive if whenever Why? (2) If there is an arc from x to y and one from y to z then there must be one from x to z. null**8.1 Relations and Their Properties 〖Example 7〗Determine whether the following relations are reflexive, irreflexive, symmetric, antisymmetric and/or transitive. 判断下列关系是否是 自反的，反自反的，对称的，反对称的，或是传递的？(1) reflexive, symmetric, antisymmetric, transitive 自反的，对称的，反对称的，传递的null**(2) not reflexive, symmetric, antisymmetric, transitive 不是自反的、对称的、反对称的、传递的null**8.1 Relations and Their Properties (3) reflexive, antisymmetric, transitive 自反的、反对称的、传递的(4) reflexive, symmetric, transitive 自反的、对称的、传递的Question: Symmetric, transitive  reflexive ? null**8.1 Relations and Their Properties 〖Example 8〗How many relations are there on a set with n elements that are (1) reflexive ? 自反的？ (2) symmetric ? 对称的？ (3) antisymmetric ? 反对称的？Solution: (1) 0,1(2) null**8.1 Relations and Their Properties Solution: (3) Questions: reflexive and symmetric?自反的和对称的？ transitive?传递的？null** Since relations form A to B are subsets of AB, two relations form A to B can be combined in any way two sets can be combined.因为从A到B的关系是A×B的子集，可以按照两个集合组合的任何方式来组合两个从A到B的关系。 Set operation集合运算 Composition合成 Inverse relation关系的逆Combining Relations关系组合 8.1 Relations and Their Properties null**1 Solution:(1) Set operations Boolean operations/logical operations 布尔运算/逻辑运算 The Boolean Sum The Boolean product The complement 8.1 Relations and Their Properties null**The logical operations of matrices： 关系矩阵的逻辑运算8.1 Relations and Their Properties null**2 Composition 关系的合成 The composite of R and S: Question: How to compute SoR? (1) Using the definition directly 用定义 (2) Using the connection matrix 用关系矩阵8.1 Relations and Their Properties null**〖Example 10〗Solution: (1) Using the definition directlyNote:8.1 Relations and Their Properties null**Solution: (2) Using the connection matrix 使用关系矩阵8.1 Relations and Their Properties null**〖Example 11〗Let A={0,1,2,3}. R is the relation on the set A. R ={(0,0),(0,3),(2,3),(3,2),(2,1),(2,0)}. R2=? Solution: Using the definition R2={(0,0),(0,3),(0,2),(2,2),(3,3),(2,3),(2,0),(3,1),(3,0)} Using the digraph 8.1 Relations and Their Properties null**Using the matrix 8.1 Relations and Their Properties null**【 Theorem 】 The relation R on a set A is transitive if and only if 集合A上的关系R是传递的，当 且仅当对n=1，2，3…有Proof:(1) R is transitive (2) R is transitive  Inductive base Inductive step R is transitive 8.1 Relations and Their Properties null**〖Example 12〗 Let R be a symmetric relation on the set A. Show that Rn is symmetric for all positive integers n. 假设集 合A上的关系R是对称的，证明对于所有正整数n对于 都 是对称的Proof: Inductive base Inductive step Rn is symmetric  Rn+1 is symmetric n=1, R be a symmetric 对称的8.1 Relations and Their Properties null**3 Inverse relation 关系的逆The inverse relation form B to A: (2) Reverse all the arcs in the digraph representation of R (3) Take the transpose MR T of the connection matrix MR of R. Using the definition directly For example,8.1 Relations and Their Properties null**4 The properties of relation operations 关系运算的性质 Suppose that R, S are the relations from A to B, T is the relation from B to C, P is the relation from C to D, then (1) Proof: 8.1 Relations and Their Properties null**4 The properties of relation operations Suppose that R, S are the relations from A to B, T is the relation from B to C, P is the relation from C to D, then (1) (2) (3) (4) (5) Proof: 8.1 Relations and Their Properties null**4 The properties of relation operations Suppose that R, S are the relations from A to B, T is the relation from B to C, P is the relation from C to D, then (1) (2) (3) (4) (5) (6) (7) (8) (9) 8.1 Relations and Their Properties null**8.2 n-ary Relations and Their Application n元关系及其应用The domains of relationdegree作业题作业题P253 T4 (d) T12 T14 T22