(精品)8.5-8.6.ppt
《(精品)8.5-8.6.ppt》由会员分享,可在线阅读,更多相关《(精品)8.5-8.6.ppt(54页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、12023/1/298.1 Relations and Their Properties 8.1 Relations and Their Properties 8.2 8.2 n-aryn-ary Relations and Their Application Relations and Their Application 8.3 Representing Relations8.3 Representing Relations7.4 Closures of Relations 7.4 Closures of Relations 8.5 Equivalence Relations 8.5 Equ
2、ivalence Relations 等价关系等价关系等价关系等价关系8.6 Partial Orderings8.6 Partial Orderings Chapter 8 Relations Chapter 8 Relations 22023/1/298.5 Equivalence Relations 8.5 Equivalence Relations【Definition】A relation R on a set A is an equivalence relation if R is(等价关系满足三个条件等价关系满足三个条件)nReflexive自反的自反的nSymmetric对称的
3、对称的ntransitive 传递的传递的Equivalence Equivalence relations relations(等等等等价价价价关关关关系系系系)and)and equivalence equivalence classesclasses (等价类)(等价类)(等价类)(等价类)For example,(2)The similarity relation between two triangles(3)The equivalent relation between two formulas in proposition logic 32023/1/298.5 Equivale
4、nce Relations Terminologies:术语术语a and b are equivalent a和和b是等价的是等价的 R is an equivalence relation,and(a,b)Rthe equivalence class of x The set of all elements that are related to an element x of A 或者:或者:设设R为为集合集合A上的等价关系,上的等价关系,对对每个每个x A,作集合,作集合Notation:a representative of the equivalence class 等价类的表示等
5、价类的表示42023/1/298.5 Equivalence Relations Example 1 Congruence Modulo 3 模模3同余同余 Show that R is an equivalence relation.And find its equivalence class.证证明它明它R是等价关系并且找出他的等价是等价关系并且找出他的等价类类Solution:reflexive 自反的自反的 R is reflexive,since symmetric 对称的对称的 transitive 传递的传递的52023/1/298.5 Equivalence Relations
6、 0=,-6,-3,0,3,6,=3k|k Z 1=,-5,-2,1,4,7,=3k+1|k Z 2=,-4,-1,2,5,8,=3k+2|k Z Congruence Modulo m:Congruence class Modulo m:62023/1/298.5 Equivalence Relations Example 2 Suppose that A is a nonempty set,and f is a function that has A as its domain.Let R be the relation on A consisting of all ordered pai
7、rs(x,y)where f(x)=f(y).(1)Show that R is an equivalence relation.(2)What are the equivalence class of R.Solution:(1)reflexive symmetric transitive(2)72023/1/298.5 Equivalence Relations Equivalence relations and Equivalence relations and partitionspartitions(划分划分划分划分)【Definition】Let be a collection o
8、f subsets of A.Then the collection forms a partition of A if and only if 集合集合 构成构成集合集合A的划分的划分当且仅当当且仅当Notation:A1A2A3A4A582023/1/298.5 Equivalence Relations【Theorem】Let R be an equivalence relation on a set A.The following statements are equivalent:设设R R是集合是集合A A上上的等价关系,下面的等价关系,下面命题是等价的命题是等价的Proof:nS
9、how that(1)implies(2)92023/1/298.5 Equivalence Relations n Show that(3)implies(1)n Show that(2)implies(3)R is reflexive a is nonempty 102023/1/298.5 Equivalence Relations Proof:【Theorem】Let R be an equivalence relation on a set A.Then the equivalence classes of R form a partition of A.Conversely,giv
10、en a partition of the set A,there is an equivalence relation R that has the sets ,as its equivalence classes.设设R是集合是集合A上的等价关系。那么上的等价关系。那么R的等价类构成的等价类构成S的划分。相反,给定集合的划分。相反,给定集合S的划分的划分 ,存在着等价关系,存在着等价关系R,它以集合,它以集合 作为它的等价类。作为它的等价类。an equivalence relation on a set A a partition of A nthe equivalence class
11、of R:112023/1/298.5 Equivalence Relations n 122023/1/298.5 Equivalence Relations Solution:0=01=1,2,34=4,5pr(A)=0,1,4Example 3 Find the partition of the set A from R.023145132023/1/29Question:Congruence Modulo m 模模 m的同余类的同余类8.5 Equivalence Relations Question:|A|=3.How many different equivalence relat
12、ions on the set A are there?Solution:an equivalence relation on a set A a partition of A 142023/1/298.5 Equivalence Relations The operations of equivalence relations The operations of equivalence relations【Theorem】If are equivalence relations on A,then is equivalence relations on A.如果如果 是是A上的等价上的等价关
13、系,那么关系,那么 也是也是A上的等价关系上的等价关系Proof:It suffices to show that the intersection ofn reflexive relations is reflexive,自反证明自反证明n symmetric relations is symmetric,andn transitive relations is transitive.152023/1/298.5 Equivalence Relations The operations of equivalence relations The operations of equivalenc
14、e relations【Theorem】If are equivalence relations on A,then is equivalence relations on A.Proof:It suffices to show that the intersection ofn reflexive relations is reflexive,n symmetric relations is symmetric,对称证明对称证明andn transitive relations is transitive.162023/1/298.5 Equivalence Relations The op
15、erations of equivalence relations The operations of equivalence relations【Theorem】If are equivalence relations on A,then is equivalence relations on A.Proof:It suffices to show that the intersection ofn reflexive relations is reflexive,n symmetric relations is symmetric,andn transitive relations is
16、transitive.传递证明传递证明172023/1/298.5 Equivalence Relations【Theorem】If are equivalence relations on A,then is reflexive and symmetric relation on A.如果如果 是是A上的等价关系,那么上的等价关系,那么 在在A上具有自反的和对称的关系上具有自反的和对称的关系Proof:(1)reflexive 证明自反的证明自反的(2)Symmetric证明对称的证明对称的Question:transitive?182023/1/298.5 Equivalence Rela
17、tions Example 4Is a transitive relation?Solution:192023/1/298.5 Equivalence Relations【Theorem】If are equivalence relations on A,then is an equivalence relation on A.如果 是A的等价关系,那么 是A上的等价关系Proof:(1)reflexive自反的自反的 (2)symmetric对称的对称的 (3)transitive传递的传递的202023/1/298.1 Relations and Their Properties 8.1
18、Relations and Their Properties 8.2 8.2 n-aryn-ary Relations and Their Application Relations and Their Application 8.3 Representing Relations8.3 Representing Relations8.4 Closures of Relations 8.4 Closures of Relations 8.5 Equivalence Relations 8.5 Equivalence Relations 8.6 Partial Orderings 8.6 Part
19、ial Orderings 偏序关系偏序关系偏序关系偏序关系Chapter 8 Relations Chapter 8 Relations 212023/1/298.6 Partial Orderings8.6 Partial Orderings偏序偏序偏序偏序【Definition】Let R be a relation on S.Then R is a partial ordering or partial order if R is nReflexive自反的自反的nantisymmetric 反对称的反对称的ntransitive 传递的传递的 Notation:(S,R)-parti
20、ally ordered set or a poset 偏序集偏序集Partial OrderingsPartial Orderings Example 1222023/1/298.6 Partial OrderingsNotation:【Definition】comparable/incomparable 可比可比/不可比不可比The elements a and b of a poset are called comparable if either .When a and b are elements of S such that neither ,a and b are called
21、incomparable.偏序集(偏序集(S,)的元素)的元素a和和b叫做可比的。如果叫做可比的。如果a b或或b a。当。当a和和b是是S的元素并且既没有的元素并且既没有a b,也没有,也没有b a,则称,则称a和和b是不可比的是不可比的For example,232023/1/298.6 Partial Orderings【Definition】If is a poset and every two elements of S are comparable,S is called a totally ordered(全序)(全序)or linearly ordered set,is cal
22、led a total order or linear order.In this case is called a chain(链)(链).如果如果 是偏序集,且是偏序集,且S的每对元素都是可比的,则的每对元素都是可比的,则S叫叫作全序集或线序集,且作全序集或线序集,且 叫做全序或线序。一个全序也叫做链。叫做全序或线序。一个全序也叫做链。Example 2(1)is a poset.In this case either .Hence,is a total order and is a chain.(2)is a poset,not a totally ordered set.(3)is a
23、 poset,not a totally ordered set.242023/1/298.6 Partial OrderingsLexicographic OrderLexicographic Order (字典顺序字典顺序字典顺序字典顺序)The lexicographic order is a special case of an ordering of strings on a set constructed from a partial ordering on the set.字典顺序是从一个集合上的偏序构造一个集合上的串的序的字典顺序是从一个集合上的偏序构造一个集合上的串的序的特殊
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 精品 8.5 8.6
限制150内