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 AB. 设A、B为任意两个集合,称笛卡儿积AB的子集R为集合A到B的一个二元关系。若(x,y)∈R,则称x与y有关系R,记为 xRy
Note:
A binary relation R is a set. 关系R是一个集合
R AB 关系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: AB, 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 AA〖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 AB, 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