第5章 等价关系与偏序关系
一、选择题（每题3分）
1、设Z 为整数集，下面哪个序偶不够成偏序集（ A ）
A 、)(,小于关系：<>< B 、)(,小于等于关系：≤>≤ C 、,()Z D D <> 关系：整除 D 、,()Z M M <>关系：整倍数 2、序偶(),A ρ<>?必为（ B ） A 、非偏序集 B 、偏序集 C 、线序集 D 、良序集 3、设≤小于等于关系：Z 为整数集，下面哪个序偶能够成良序集（ D ） A 、,()R R + <>≤：正实数集 B 、,()Q Q ++<≤>有理数集：正 C 、,()Z Z ++<≤> 整数集：正 D 、,()N N <≤>：自然数集 4、设{,{1},{1,3},{1,2,3}}A =?，则A 上包含关系“?”的哈斯图为（ C ） 5、集合{ 1, 2, 3,4 }A =上的偏序关系图为 则它的哈斯图为（ A ） 6、某人有三个儿子，组成集合123{ , , }A S S S =，则在A 上的兄弟关系一定不是（ D ） A 、偏序关系 B 、线序关系 C 、良序关系 D 、等价关系 7、有一个人群集合12{ , , , }n A P P P = ，则在A 上的同事关系一定是（ D ） A 、偏序关系 B 、线序关系 C 、良序关系 D 、等价关系 8、设A 为非空集合，则下列A 上的二元关系中为等价关系的是（ D ） A 、空关系 B 、全域关系 C 、恒等关系 D 、上述关系都是 9、设{ 1, 2, 3 }A =，则A 上不同等价关系的个数为（ C ） A 、3 B 、4 C 、5 D 、6 10、设{ 1, 2, 3, 4 }A =，则A 上不同等价关系的个数为（ C ） A 、13 B 、14 C 、15 D 、16 注：除了等价关系可以对空集定义，而划分不能外，等价关系与划分是相同概念的不同描述． 11、设{ 1, 2 }S =，“?”为S 中元素的普通乘法，定义S S ?上的等价关系 {,,, | ,,,,}R a b c d a b S S c d S S a d b c =<<><>><>∈?<>∈??=?， 则由R 产生的S S ?上一个划分的分块数为（ D ） A 、1 B 、2 C 、3 D 、4 提示：记12341,1,1,2,2,1,2,2a a a a =<>=<>=<>=<>， 则由R 的关系图易知1234{{},{},{},{}}S S a a a a ?=． 12、设} 3 ,2 ,1 {=S ，“+”为S 中元素的普通乘法，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=， 则由R 产生的S S ?上一个划分的分块数为（ C ） A 、3 B 、5 C 、7 D 、9 提示：因a d b c +=+，则a b c d -=- 因2,1,0,1,2a b -=--，则等价关系R 产生的S S ?上一个划分的分块数为5． 二、填充题（每题4分） 1、设{ , , , }A a b c d =，其上偏序关系R 的哈斯图为 则R = {,,,,,,,,,}A a b a c a d b d c d I <><><><><> ． 2、设{ , , ,,,, }A a b c d e f g =，偏序集,A R <>的哈斯图为 a b f g ， 则R = {,,,,,,,,,,,,,}A a b a c a d a e a f d f e f I <><><><><><><> ． 3、偏序集({,}),a b ρ的Hass 图为 4、对于{ 1,2,3,4,6,8,12,24 }A =，则偏序集,A <>整除关系的哈斯图为 2 3 468． 5、设{ 1,2,3,4,6,8,12,24 } A =，“≤”为A 上整除关系，则偏序集,A <≤>的极小元为1，最小元为1，极大元为24、最大元为24． 6、设{ 2,3,4,6,8,12 }A =，“≤”为A 上整除关系，则偏序集,A <≤>的极小元为2,3，最小元为无，极大元为8,12，最大元为无，既非极小元也非极大元的是4,6． 7、设},,{c b a A =考虑下列子集}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =， }},{},{{3c b a S =，}},,{{4c b a S =，}}{},{},{{5c b a S =，}},{},{{6c a a S = 则A 的覆盖有12345,,,,S S S S S ，A 的划分有345S S S ，，． 8、设{ 1, 2, 3,4 }A =，{{1},{2,3},{4}}S =为A 的一个分划，则由S 导出的等价关系为 R = {1,1,2,2,2,3,3,2,3,3,4,4}<><><><><><>． 提示：R =({1}{1})({2,3}{2,3})({4}{4})??? ． 9、非空正整数子集A 上的模k 等价关系R 的秩为k ，/A R ={[0],[1],,[1]}k k k k - ． {} b a ,{}a {}b Φ 三、问答题（每题6分） 1、试比较偏序集合、线序集合与良序集合． 答：若集合A 上的二元关系R 是自反的，反对称的和传递的，称序偶,A R <>为偏序集； 偏序集中的各元素并非都能比较，若都能比较，偏序集成为线序集； 在线序集中，若A 的任一非空子集都有一最小元素，则线序集成为良序集． 2、设||5A =，R 是A 的等价关系，由R 诱导的A 的划分块数为3，则不同的R 有多少种？ 答：一个集合上的等价关系数目与该集合的划分数目是一致的，因而，该题只需求出将5个元素的集合分成3份的划分种数即可． 如果3份中元素个数分别为3，1，1，则共有3 5C 种， 如果3份中元素个数分别为2，2，1，则共有2 5C 种， 因此，A 上秩为3的等价关系共有3 5C +2 520C =． 3、设A 是实数集合，试判断{,3}R x y x A y A x y =<>∈∧∈∧-=是A 上的偏序关系吗？等价关系吗？为什么？ 答：都不是；因 ?x ∈A ，x －x =0≠2，所以 1、设{ , , ,,}A a b c d e =上的关系R = {,}A c d I <> ，画出偏序集,A R <>的哈斯图， 列表给出A 的子集123{ ,, ,,},{ ,},{,,}B a b c d e B c d B c d e ===的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界． 解：哈斯图如图4.44所示： 其子集,1,2,3i B i =上的各种特殊元素如下表所示， 2}y ?， 画出偏序集哈斯图，列表给出子12}}c ，3{{,},{,,}}B a c a b c =的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界． 解：哈斯图如图4.45所示： 其子集,1,2,3i B i =上的各种特殊元素如下表所示， 3、试填出{1,2,3,4,5}A =上的等价关系R ， 其产生划分/{{1,2},{3},{4,5}}A R =,并画出关系图． 解：{1,2}{1,2}{3}{3}{4,5}{4,5}R =??? 其关系图为： 六、证明题（每题10分） 1、设R 是A 上的二元关系，如果R 是传递的和反自反的，称R 是A 上的拟序关系， 证明：如果R 是A 上的拟序关系，则()A r R R I = 是A 上的偏序关系． 证明：（1）因()A A r R R I I =? ，有()r R 是自反的； （2）设,(),x y r R <>∈而x y ≠，则,,x y R <>∈若,,y x R <>∈ 由R 的传递性，知,,x x R <>∈与R 的反自反性矛盾，则,,y x R <>? 又,,A y x I <>?有,()A y x R I r R <>?= ，于是有()r R 是反对称的； （3）由R 的传递性，知R R R ? ， 因()()()()(())(())A A A A A r R r R R I R I R I R R I I == (()())(()())()()A A A A A R R I R R I I I R R R I r R ==? ，则()r R 可传递； 综上所述，可证()r R 是A 上的偏序关系． 2、设R 是A 上的二元关系，如果R 是传递的和反自反的，称R 是A 上的拟序关系， 证明：如果R 是A 上的偏序关系，则A R I -是A 上的拟序关系． 证明：（1）()()()A A A A A A R I I R I I R I I R -===?=? ，则A R I -反自反； （2）设,,,A A x y R I y z R I <>∈-<>∈-，则,,,x y R y z R <>∈<>∈，而,x y y z ≠≠，因R 是传递的，有,x z R <>∈；若x z =，则,,,z y R y z R <>∈<>∈，由R 的反对称性，知y z =，与y z ≠矛盾，于是x z ≠，则,A x z R I <>∈-，有A R I -是传递的； 综上所述，可证A R I -是A 上的拟序关系． 3、设R 是A 上的对称和传递关系， 证明：若,,,a A b A a b R ?∈?∈?<>∈，则R 是A 上的等价关系． 证明：,,,a A b A a b R ?∈?∈?<>∈，因R 是对称的，有,b a R <>∈， 又因R 是传递的，所以,a a R <>∈，则R 在A 上自反，故R 是A 上的等价关系． 4、设R 是S 上的偏序关系，证明：1 R -是S 上的偏序关系． 证明：（1）x S ?∈，因R 在S 上的自反性，则,x x R <>∈， 有1 ,x x R -<>∈，于是，1R -在S 上是自反的； （2）设1 ,,x y R -<>∈而x y ≠，则,,y x R <>∈因R 在S 上的反对称性，有,,x y R <>? 则1 ,,y x R -<>?于是，1R -在S 上是反对称的； （3）设11,,,x y R y z R --<>∈<>∈，则11 ,,,z y R y x R --<>∈<>∈， 因R 在S 上的传递性，有,,z x R <>∈则1 ,,x z R -<>∈于是，'R 在'S 上是传递的； 综上所述，可证1 R -是S 上的偏序关系．（题4在证明中用了定义法） 5、设R 是S 上的等价关系，证明：1 R -是S 上的等价关系． 证明：（1）因R 在S 上的自反性，有S I R ?，则1 1 S S I I R --=?，有1R -在S 上自反； （2）因R 在S 上的对称性，有1 R R -=，则111()R R R ---==，有1R -在S 上对称； （3）因R 在S 上的传递性，有2R R ?，则1221()R R R R --=?=，有1 R -在S 上可传递； 则2 '(')('(''))('')'R R R R S S R S S R ????= ，有'R 在'S 上是对称的； 综上所述，可证1 R -是S 上的等价关系．（题5在证明中用了集合法） 6、设,R S 是A 上的偏序关系，证明：R S 是A 上的偏序关系． 证明：（1）x A ?∈，因,R S 在A 上的自反性，则,x x R S <>∈ ，有R S 在A 上自反； （2）设,,x y R S <>∈ 而x y ≠，则,,,,x y R x y S <>∈<>∈因,R S 在A 上的反对称性，有,,,,y x R y x S <>?<>?则,,y x R S <>? 于是，R S 在A 上是反对称的； （3）设,,,x y R S y z R S <>∈<>∈ ， 则,,,;,,,x y R y z R x y S y z S <>∈<>∈<>∈<>∈，因,R S 在A 上的传递性， 有,,,x z R x z S <>∈<>∈,则,x z R S <>∈ ，于是，R S 在A 上是传递的； 综上所述，可证R S 是A 上的偏序关系．（题6在证明中用了定义法） 7、设,R S 是A 上的等价关系，证明：R S 是A 上的等价关系． 证明：（1）因,R S 在A 上自反，有,A A I R I S ??，则A I R S ? ，有R S 在A 上自反； （2）因,R S 在A 上对称，有1 1,R R S S --==， 则1 11() R S R S R S ---== ，有R S 在A 上对称； （3）因,R S 在A 上传递，有2 2 ,R R S S ??， 则2 2 2 ()(())(())R S R S R R S S R S R S ??? ，有R S 在A 上可传递； 综上所述，可证R S 是A 上的等价关系．（题7在证明中用了集合法） 8、设R 是S 上的二元关系，'S S ?定义'S 上的二元关系'('')R R S S =? , 证明：如果R 是S 上的偏序关系，那么'R 是'S 上的偏序关系． 证明：（1）'x S S ?∈?，因R 在S 上的自反性，则,x x R <>∈，而,''x x S S <>∈?， 有,('')'x x R S S R <>∈?= ，于是，'R 在'S 上是自反的； （2）设,',x y R <>∈而x y ≠，则,,x y R <>∈因R 在S 上的反对称性，有,,y x R <>? 则,('')',y x R S S R <>??= 于是，'R 在'S 上是反对称的； （3）设,',,'x y R y z R <>∈<>∈，因R 在S 上的传递性，有,,x z R <>∈ 而,''x z S S <>∈?，则,('')'x z R S S R <>∈?= ，于是，'R 在'S 上是传递的； 综上所述，可证'R 是'S 上的偏序关系．（题8在证明中用了定义法） 9、设R 是S 上的二元关系，'S S ?定义'S 上的二元关系'('')R R S S =? , 证明：如果R 是S 上的等价关系，那么'R 是'S 上的等价关系． 证明：（1）因R 在S 上的自反性，则S I R ?，而'S S ?,有'S S I I R ??，而'''S I S S ??， 有'('')'S I R S S R ??= ，于是，'R 在'S 上是自反的； （2）因R 在S 上的对称性，有1 R R -=，而1('')''S S S S -?=?， 则1111 (')((''))('')'R R S S R S S R ----=?=?= ，有'R 在'S 上是对称的； （3）因R 在S 上的传递性，有2 R R ?， 有2'R R R R ?? ，而2 '('')('')''R S S S S S S ???=? ， 则2 '(')('(''))('')'R R R R S S R S S R ????= ，有'R 在'S 上是传递的； 综上所述，可证'R 是'S 上的等价关系．（题9在证明中用了集合法） 10、若R 是A 上的等价关系，则{,|,(,,)}S a b a b A c A a c R c b R =<>∈∧?∈<>∈∧<>∈也是A 上的一个等价关系． 证明：（1）A a ∈?，由R 自反，则,,a a R a a R <>∈∧<>∈，S a a >∈∴<,，有S 自反；（2）,a b S ?<>∈，则c A ?∈，使,,,,a c R c b R <>∈<>∈ 由R 在A 上对称，有,,,,b c R c a R <>∈<>∈有,b a S <>∈，知S 对称； （3）若,,,a b S b c S <>∈<>∈，则d A ?∈，使,,,,a d R d b R <>∈<>∈ 同时e A ?∈，使,,,,b e R e c R <>∈<>∈ 由R 在A 上传递，知,,,,a b R b c R <>∈<>∈有,a c S <>∈，有S 传递； 综上所述，可证S 是A 上的等价关系．（题10在证明中用了定义法） 六、证明计算题（每题10分） 1、设{1,2,3}A =，在A A ?上定义:,,,R a b c d R <<><>>∈? a b c d +=+， “+”为普通加法，证明：R 是A A ?上的等价关系，并求出[1,3],/R A A R <>?． 证明：（1）,,,,,,,a b A A a b a b a b a b R ?<>∈?+=+∴<<><>>∈ 即R 自反； （2）,,,,,,a b c d R a b c d c d a b ?<<><>>∈+=++=+∴则 则,,,c d a b R <<><>>∈，即R 对称； （3）,,,,,,,,a b c d R c d e f R ?<<><>>∈<<><>>∈a b c d e f +=+=+则， ,,,,a b e f R ∴<<><>>∈即R 传递； 综上得出，R 是A A ?上的等价关系， 且[1,3]R <>{,,,4}{1,3,2,2,3,1}a b a b A A a b =<><>∈?+==<><><>, /{[1,1],[1,2],[1,3],[2,3],[3,3]}R R R R R A A R ?=<><><><><>． 2、设{1,2,3,4}A =，在A A ?上定义:,,,R a b c d R <<><>>∈? c b d a +=+， “+”为普通加法，证明：R 是A A ?上的等价关系，并求出[2,4],/R A A R <>?． 证明：（1）,,,,,,,a b A A a b b a a b a b R ?<>∈?+=+∴<<><>>∈ 即R 自反； （2）,,,,,,a b c d R a d b c c b d a ?<<><>>∈+=++=+∴则 则,,,c d a b R <<><>>∈，即R 对称； （3）,,,,,,,,a b c d R c d e f R ?<<><>>∈<<><>>∈ ,a d b c c f d e a d c f b c d e +=++=++++=+++∴则 有 a f b e +=+，,,,,a b e f R ∴<<><>>∈即R 传递； 综上得出，R 是A A ?上的等价关系， 且[2,4]R <>{,,,2}{1,3,2,4}a b a b A A a b =<><>∈?=-=<><>, /{[1,1],[1,2],[2,1],[1,3],[3,1],[1,4],[4,1]}R R R R R R R A A R ?=<><><><><><><>． 3、设{1,2,3,4}A =，在A A ?上定义:,,,R a b c d R <<><>>∈? a d b c = ， “ ” 为普通乘法，证明： R 是A A ?上的等价关系，并求出[2,4],/R A A R <>?． 证明：（1）,,,,,,,a b A A a b b a a b a b R ?<>∈?=∴<<><>>∈ 即R 自反； （2）,,,,,,a b c d R a d b c c b d a ?<<><>>∈==∴ 则 则,,,c d a b R <<><>>∈，即R 对称； （3）,,,,,,,,a b c d R c d e f R ?<<><>>∈<<><>>∈ ,a d b c c f d e a d c f b c d e ===∴ 则， 有 a f b e = ，,,,,a b e f R ∴<<><>>∈即R 传递； 综上得出，R 是A A ?上的等价关系， 且[2,4]R <>{,,,2}{1,2,2,4}a b a b A A a b =<><>∈?==<><>, /{[1,1],[1,2],[2,1][1,3],[3,1],[1,4],[4,1]}R R R R R R R A A R ?=<><><><><><><>． 4、设{ 1, 2, 3, 4 }A =，在A 的幂集()A ρ上规定{,|,()(||||}R s t s t A s t ρ=<>∈∧=， 证明：R 是()A ρ上的等价关系，并写出商集()A R ρ． 证明：⑴()s A ρ?∈ ，由于||||s s =，所以R s s >∈<,，即R 自反的； ⑵,()s t A ρ?∈ ，若R t s >∈<,，则||||||||s t t s =?=，R s t >∈∴<,，R 是对称的； ⑶,,()s t u A ρ?∈，若R u t R t s >∈<>∈<,,且，即||||||u t s ==， 则,s u R <>∈ 所以R 是传递的； 综上得出，R 是()A ρ上的等价关系， (){[],[{1}],[{1,2}],[{1,2,3}],[{1,2,3,4}]}R R R R R A R ρ=?． “关系”一词，在日常生活中十分常见，在学校，有同学关系、师生关系、同事关系等； 在家庭中，有兄弟姐妹关系，父子关系、母女关系等；在一般的工作单位，有师徒关系、上 下级关系等等。在研究科学中也有很多关系，如数学中的数的大小比较关系、整数中整除关 系、函数关系、集合中的包含关系；计算机软件的程序与其子程序关系等。 为了数学的方法来研究这类关系，我们将用集合论的观点来描述这类关系。 例如，集合{}e d c b a A ,,,,=，为五个人组成的集合，其中他们中，a 是b 的父亲，c 是d 的 父亲，c 也是e 的父亲。现将集合A 的父子关系用有序对表示，即为),(),,(),,(e c d c b a 。把 这三个有序对组成一个集合{}),(),,(),,(e c d c b a R =，我们把R 这种由集合A 导出的有序 对组成的集合R ，叫做A 上关系 R 。 我们称集合R 为集合A 的父子关系集合（简称关系）。 我们把13个数组成的集合{}10,,3,2,1 =A 也建立几个关系。 二、建立关系举例： 1、 它们之间的小于等于关系R ； ()()()()()()(){},13,13,13,12,,3,2,2,2,3,1,2,1,1,1 =R 2、 它们除以3以后余数相同的关系1R ； ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()? ?????=,10,10,7,10,4,10,1,10,9,9,6,9,3,9,8,8,5,8,2,8,10,7,7,7,4,7,1,7,9,6,6,6,3,6,8,5,5,5,2,5,10,4,7,4,4,4,1,4,9,3,6,3,3,3,8,2,5,2,2,2,10,1,7,1,4,1,1,12R 3、它们之间的整除关系2R ； ()()()()()()()()()()()()()()()()()()()()? ?????=10,10,9,9,8,8,7,7,6,6,10,5,5,5,8,4,4,4,9,3,6,3,3,3,10,2,8,2,6,2,4,2,2,2,10,1,2,1,1,13 R 注意：关系有两大类关系：A 到B 的关系，A 上的关系；我们主要讨论A 上的关系。 三、关系的几种表示方法： 1、图形表示； 2、表格表示； 3、矩阵表示； 比如：{ }5,4,3,2,1=A 上的R 关系为()()()()()()(){},4,5,2,4,5,3,3,3,3,2,2,22,1=R 则??????? ? ??=01000000101010000110 00010R A 等价关系与偏序关系 何英华 hyh@https://www.doczj.com/doc/6e6187833.html, 集合论与图论 04 目录 ?4.1 等价关系 –等价关系 –等价类 –商集 –集合的划分 ?4.2 偏序关系 一、等价关系 ?定义：设R为非空集合上的关系。如果R是自反的、对称的和传递的，则称R为A上的等价关系。设R是一个等价关系，若 二、等价类 ?定义：设R为非空集合A上的等价关系，令x∈A [x] R ={y|y∈A∧xRy} 称[x] R 为x关于R的等价类，简称为x的等价类，简 记为[x]。 ?从以上定义可以知道，x的等价类是A中所有与x 等价的元素构成的集合。例1中的等价类是： [1]=[4]=[7]={1,4,7} [2]=[5]=[8]={2,5,8} [3]=[6]={3,6} 等价类的性质 ?定理：设R是非空集合A上的等价关系，则 1）?x∈A，[x]是A的非空子集。 2）?x,y∈A，如果xRy，则[x]=[y]。 3）?x,y∈A，如果xRy不成立，则[x]与[y]不交。4）∪{[x]|x∈A}=A 证明： 1）x∈[x]，[x] ?A。 2）集合相等。 3）反正法。 4）集合相等。 三、商集 ?定义：设R为非空集合A上的等价关系，以R的所有等价类作为元素的集合称为A关于R的商集，记做A/R，即A/R={[x] |x∈A} R ?例1中的商集为{{1,4,7},{2,5,8},{3,6}} 偏序关系 一、偏序关系和哈斯图 1、定义3-12.1 若集合A上的二元关系R是自反的、反对称的和传递的，则称R是A的偏序关系，记作?.设?为偏序关系，如果 根据不同偏序的定义，对序有着不同的解释. 例如整除关系是偏序关系， 3 ? 6的含义是3整除6. 大于或等于关系也是偏序关系，针对这个关系写5?4是说大于或等于4,关系?中5排在4的前边，也就是5比4大. 注： 和空关系都是A上的偏序关系， 1. 集合A上的恒等关系I A 但全域关系E 一般不是A上的偏序关系. A 2. 实数域上的小于等于关系（大于等于关系），自然数域上的整除关系，集合的包含关系等都是偏序关系. 定义设R为非空集合A上的偏序关系，定义 (1) ?x, y∈A, x ? y当且仅当 x ? y且x≠y; (2) ?x, y∈A, x 与 y 可比当且仅当 x ? y 或 y ? x. 注： 在具有偏序关系的集合A中任二元素 x 和 y 之间必有下列四种情形之一： x ? y ，y ? x ，x=y ，x 与 y 不可比. 例设A={1, 2, 3} (1) ?是A上的整除关系，则：1 ? 2, 1 ? 3, 1＝1, 2＝2, 3＝3， 2 和 3 不可比； (2) ?是 A 上的大于等于关系，则: 2 ? 1, 3 ? 1, 3 ? 2, 1＝1, 2＝2，3＝3. 第5章 等价关系与偏序关系 一、选择题（每题3分） 1、设Z 为整数集，下面哪个序偶不够成偏序集（ A ） A 、)(,小于关系：<>< 求偏序集中的极大元与极小元 成绩: 10 / 折扣: 0.9 输入 输入偏序集 4.6偏序关系 偏序关系：同时具有自反、反对称和传递性 4.6 偏序关系 定义4.21 设R为非空集合A上的一个二元关系，如果R是自反的、反对称的和传递的，则称R为A上的偏序关系，记作≤。设≤是偏序关系，若 4.6 偏序关系 定义4.22 设 4.6 偏序关系 Sed ut perspiciatis unde omnis.68% 设 4.6 偏序关系 定义4.24 设 概念问题 二进制关系：A和B的笛卡尔积的子集称为从A到B的二进制关系。集合上的关系：从a到a的关系。 关系的性质 反射，抗反射，对称，抗对称和传输。 没有列出概念，但应注意以下方面： （1）所有属性的概念都是逻辑表达式，即判断是非，必须严格按照定义判断是非； （2）它们都是用全名量词表示的逻辑表达式，因此必须为真才能保持一致； （3）它们全部由隐含条件语句表示。如果前提为假，则它也为真，也就是说，所有未出现在真之后再为假的内容都为真。 关系代表 （1）设置符号（适合定义和表示）； （2）图表表示（适合直观感觉和观察特性）； （3）关系矩阵表示（适合计算）；特别地，关系矩阵是布尔矩阵，即逻辑矩阵，其描述A中的第i个元素是否与B中的第j个元素有关。 关系运作 （1）交叉，合并与区别 R1?R2————M1ùM2 R1èR2————M1úM2 （2）综合 合成操作非常重要且容易出错。注意其顺序以及对集合，图形和矩阵的相应计算。 自我及其综合运算形成力量。 例如，R 2对应于由点直接连接的边，这些点可以从图形上的每个点分两步到达。 另一个例子 R1°R2 ————M2M1 R ^ 2 ————M ^ 2 关系的应用 （1）n元关系的应用 一般来说，当2元关系扩展到N元关系时，它就成为数据库的基本框架。N元有序对是N个字段的记录，因此关系操作对应于数据库操作。我们只知道这部分内容（与数据库重复）。 （2）封闭的应用 首先，介绍了三种闭包的概念。如果用一句话来概括，R的自反/对称/传递闭包是包含R的自反/对称/传递关系中最小的。 然后其应用着重于掌握传递闭包的应用，它可以显示传递性直接通过连接边可到达的点的连通性。 然后讨论三个闭包的计算： （3）等价关系的应用 首先是等价关系的概念，以及等价类和划分的扩展概念。 其次，等价关系的应用仅仅是分类。因为等价与划分之间存在一一对应的关系。 A.如果一个关系是集合a上的等价关系，写出每个元素的等价类，然后删除重复项，则由非重复等价类组成的集合就是原始集合a的除法。B，如果子集族是集合A的划分，则根据“属于同一个子集的人如果有关系就可以配对”的规则，二元有序对的集合必须满足反射性，对称性和可传递性，是等价的关系。 （4）偏序关系的应用 第一个是偏序的概念，并扩展了“小于或等于”，“小于”和“可比”。然后是整个顺序，然后是良好顺序（自己比较概念）。 ●定义：集合S上的关系R，如果它是自反的，反对称的和传递的，就称为偏序。集 合S与偏序R一起叫做偏序集，记做(S, R) ●例子： ●1、整数集合上的“大于或等于”关系 ●2、正整数集合上的整除关系 ●3、集合S的幂集合上的包含关系 ●符号： ●通常用?表示偏序关系,读作“小于等于” ● 等价关系（4学时） 【教学目的】 了解、掌握等价关系及相应的等价类与集合划分的基本概念及例子 【教学要求】 正确地掌握等价关系及相应的等价类与集合划分之间的关系；给定A上的等价关系R，会求所有的等价类和商集A/R，或者求与R相对应的划分；反之给定集合 A上的划分π，求对应于π的等价关系 【教学重点】 等价关系、偏序关系的各种性质的判断和证明； 【教学难点】 如何正确地掌握等价关系及相应的等价类与集合划分之间的关系 【教学方法】 讲练结合教学法、提问式与启发式相结合教学法。 【教学手段】 传统板书与多媒体课件辅助教学相结合。 【课型】新授课 教学过程 4.1一种特殊的二元关系——等价关系(Equivalence Relation). 一、等价关系(Equivalence Relation) 1、定义4.18 设R为非空集合上的关系.如果R是自反的、对称的和传递的, 则称R为A 上的等价关系.设R是一个等价关系, 若 《离散数学》实验报告 （2015/ 2016 学年第一学期） 题目：偏序关系中盖住关系的求取及格论中有补格的判定 专业 学生姓名 班级学号 指导教师 指导单位计算机学院计算机科学与技术系 日期2015年12月15日 评分细则 评分项优秀良好中等差遵守机房规章制度 上机时的表现 学习态度 算法思想准备情况 程序设计能力 解决问题能力 课题功能实现情况 算法设计合理性 算法效能评价 报告书写认真程度 内容详实程度 文字表达熟练程度 回答问题准确度 简 短 评 语 教师签名： 年月日 评 分 等 级 备 注 评分等级有五种：优秀、良好、中等、及格、不及格 偏序关系中盖住关系的求取及格论中有补格的判定 一、实验内容和要求 内容： 编程实现整除关系这一偏序关系上所有盖住关系的求取，并判定对应偏序集是否为格。 要求： 对任意给定正整数，利用整除关系求所有由其因子构成的集合所构成的格，判断其是否为有补格。 二、实验目的 编程实现整除关系这一偏序关系上所有盖住关系的求取，并判定对应偏序集是否为格。 三、实验任务 1、求出输入数的所有因子。 2、求出整除关系“≤”的偏序集。 3、求出盖住关系COV A。 4、判断是否有补格。 5、判断是否为布尔格。 四、实验内容 #include 离散数学等价关系 离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。离散的含义是指不同的连接在一起的元素，主要是研究基于离散量的结构和相互间的关系，其对象一般是有限个或可数个元素。 离散数学在各学科领域，特别在计算机科学与技术领域有着广泛的应用，通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。 随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。 离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。 离散数学也可以说是计算机科学的基础核心学科，在离散数学中的有一个著名的典型例子-四色定理又称四色猜想，这是世界近代三大数学难题之一，它是在1852年，由英国的一名绘图员弗南西斯·格思里提出的，他在进行地图着色时，发现了一个现象，“每幅地图都可以仅用四种颜色着色，并且共同边界的国家都可以被着上不同的颜色”。那么这能否从数学上进行证明呢？100多年后的1976年，肯尼斯·阿佩尔（Kenneth Appel）和沃尔夫冈·哈肯（Wolfgang Haken）使用计算机辅助计算，用了1200个小时和100亿次的判断，终于证明了四色定理，轰动世界，这就是离散数学与计算机科学相互协作的结果。 离散数学可以看成是构筑在数学和计算机科学之间的桥梁，因为离散数学既离不开集合论、图论等数学知识，又和计算机科学中的数据库理论、数据结构等相关，它可以引导人们进入计算机科学的思维领域，促进了计算机科学的发展。 等价关系和划分 1.等价关系 定义：如果集合A上的等价关系R是自反的、对称的和传递的，则称R是等价关系。 1）自反性：A上的每一个芫荽都和自己等价； 2）对称性：如果a等价于b，则b也等价于a，在有向图中，如果有从a到b的弧，则也有从b到a的弧。 3）传递性：如果a等价于b，b等价于c，则a等价于c.在有向图中，如果a 到c有一条路径，则a到此有一条弧。 4）数中的相等关系、集合中的相等关系、命题演算中的?关系都是等价关系。 5）空集合中的二元关系时等价关系。 定理：设k是一个正整数而I b a∈ 、.如果对某整数k m b a m? = - ,，则a和b是模k等价，写成 ) mod (k b a≡ 整数k叫做等价的模数。 定理：模k等价是任何集合I A?等等价关系。 定义：设R是集合A上的等价关系，对每一个A a∈，a关于R的等价类是集合} | {xRa x，记为[]R a，或者[]a；称a是等价类[]a的表示元素。如果等价类个数有限，则R的不同等价类的个数叫做R的秩；否则秩是无限的。 定理：设R是非空集合A上的等价关系，aRb当且仅当[][]b a=。 证明： 充分性：aRb b a b a a∴ ∈ ∴ = ∈], [ ], [ ] [ 必要性： ] [ ] [ ]. [ ] [, ] [ ] [ ]. [ . , , , ], [ , b a a b b a b x xRb aRb xRa a x b aR = ∴ ? ? ∴ ∈∴ ∈ ? 。同理 又传递性可知又 以上说明：一个等价类中的任意元素都可以作为此等价类的表示元素。因为对同一等价类中的任两个元素a和b，都有aRb。 定理：设R是集合A上的等价关系，则对于所有A b a∈ ,，或者] [ ] [b a=，或者φ = ] [ ] [b a 。 习题 5 1. 设 A={(a,b)|a,b∈N}.定义 A 上的一个二元关系 R={（（a,b ）,(c,d)）|ad=bc},证明:R 是A 上的等价关系. 证：(){}+∈=N b a b a A ,|, ，R={（（a,b ）,(c,d)）|ad=bc} ①自反性：由A 的定义，N b a ba ab ∈=, ()()()R b a b a ∈∴ ,,, ②对称性 设()()()R d c b a ∈,,,，则bc ad = 即 ()()()R b a d c da cb ∈∴ =,,, ③传递性 设()()()R d c b a ∈1111,,，则1111c b d a = ()()()R d c d c ∈2211,,，则2121c d d c = 2121211211211c b d a c d b d c b d d a =?==? ()()()R d c b a ∈∴ 2211,,, 2. 定义复数集合的子集合C 1={a+bi|i 2=-1,a 、b ∈R,a ≠0}，在C 1上定义关系S 为：(a+bi)S(c+di)?ac>0。证明：S 是C 1上的一个等价关系，并给出S 的等价类的几何说明。 证明:因为(a+b i )S(c+d i )?ac>0(a,b ∈R,a ≠0,c ≠0) r:?a ≠0,a2>0?(a+b i )S(a+b i ) s:(a+b i )S(c+d i )?ac>0?ca>0?(c+d i )S(a+b i ) t:(a+b i )S(c+d i )∧(c+d i )S(u+v i )?ac>0∧cu>0 ? au>0?(a+b i )S(u+v i ) 综上，S 是C 1上的一个等价关系。 由于ac>0，必须a ≠0,c ≠0且a 和c 同号，故S 只有2个等价类，等价关系
等价关系与偏序关系
离散数学39偏序关系
等价关系与偏序关系复习题答案
离散编程,求偏序关系的极大元与极小元
偏序关系
离散数学等价关系
偏序关系整理
等价关系离散数学
偏序关系中盖住关系的求取及格论中有补格的判定.
离散数学等价关系
等价关系
川大离散数学习题5
相关主题
文本预览