【图文】离散数学 第四章_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
离散数学 第四章
&&离散数学
大小：255.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢【图文】离散数学二元关系_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
离散数学二元关系
大小：1.54MB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢离散数学关系部分综合练习；一、单项选择题；1．设集合A={1,a}，则A的幂集P(A)=(；A．{{1},{a}}B．{?,{1},{a}}；C．{?,{1},{a},{1,a}}D．{{1；2．若集合A的元素个数为10，则其幂集的元素个数；7．集合A={1,2,3,4,5,6,7,8}上；A．自反的B．对称的；C．传递且对称的D．反自反且传递的；8．设集合
离散数学关系部分综合练习 一、单项选择题 1．设集合A = {1, a }，则A的幂集P(A) = (
A．{{1}, {a}}
B．{?,{1}, {a}}
C．{?,{1}, {a}, {1, a }}
D．{{1}, {a}, {1, a }} 2．若集合A的元素个数为10，则其幂集的元素个数为（
7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={|x+y=10且x, y?A}，则R的性质为（
C．传递且对称的
D．反自反且传递的
8．设集合A = {1，2，3，4，5，6 }上的二元关系R ={?a , b??a , b?A , 且a +b = 8}，则R具有的性质为（
）． A．自反的
C．对称和传递的
D．反自反和传递的 9．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（
10．设集合A={1 , 2 , 3 , 4}上的二元关系 R = {?1 , 1?，?2 , 2?，?2 , 3?，?4 , 4?}， S = {?1 , 1?，?2 , 2?，?2 , 3?，?3 , 2?，?4 , 4?}， 则S是R的（
D．以上都不对
11．设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系 1 的哈斯图如图一所示，若A的子集B = {3 , 4 , 5}， 3 2 则元素3为B的（
B．最大下界
C．最小上界
D．以上答案都不对 12．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为 (
A．8、2、8、2
B．无、2、无、2
C．6、2、6、2
D．8、1、6、1 13．设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={, }，R2={, , }，R3={, }，则（
）不是从A到B的函数．
二、填空题 1．设集合A有n个元素，那么A的幂集合P(A)的元素个数为
． 2．设集合A＝{a，b}，那么集合A的幂集是
． 应该填写：{?,{a,b},{a},{b }} 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系，
R?{?x,y?x?A且y?B且x,y?A?B} 则R的有序对集合为
． 4．设集合A={0, 1, 2}，B={0, 2, 4},R是A到B的二元关系， R?{?x,y?x?A且y?B且x,y?A?B}
则R的关系矩阵MR＝
5．设集合A={a,b,c}，A上的二元关系 R={,}，S={,,} 则(R?S)－1=
． 6．设集合A=｛a,b,c｝，A上的二元关系R={, , , }，则二元关系R具有的性质是
． 7．若A={1,2}，R={|x?A, y?A, x+y=10}，则R的自反闭包为
8．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为
三、判断说明题（判断下列各题，并说明理由．） 2．如果R1和R2是A上的自反关系，判断 结论：“R-11、R1∪R2、R1?R2是自反的” 是否 成立？并说明理由．
3． 若偏序集的哈斯图如图一所示， 则集合A的最大元为a，最小元不存在．
4．若偏序集的哈斯图如图二所示， 则集合A的最大元为a，最小元不存在．
四、计算题
图二 x，y>|x?A，
4．设A={0，1，2，3，4}，R={|x?A，y?A且x+y<0}，S={<y?A且x+y?3}，试求R，S，R?S，R-1，S-1，r(R)． 5．设A={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}，R是A上的整除关系，B={2, 4, 6}． （1）写出关系R的表示式；
（2）画出关系R的哈斯图； （3）求出集合B的最大元、最小元． a
6．设集合A＝{a, b, c, d}上的二元关系R的关系图 如图三所示． （1）写出R的表达式；
（2）写出R的关系矩阵；
（3）求出R2．
7．设集合A={1，2，3，4}，R={|x, y?A；|x?y|=1或x?y=0}，试 （1）写出R的有序对表示；
（2）画出R的关系图； （3）说明R满足自反性，不满足传递性．
五、证明题
3．设R是集合A上的对称关系和传递关系，试证明：若对任意a?A，存在b?A，使得?R，则R是等价关系．
4．若非空集合A上的二元关系R和S是偏序关系，试证明：R?S也是A上的偏序关系．
参考解答 一、单项选择题 1．A
二、填空题 1．2n 2．{?,{a,b},{a},{b }} 3．{，，}， ?110?? 0004．?????110??
6．反自反的 7．{, } 8．8
三、判断说明题（判断下列各题，并说明理由．）
2．解：成立．
因为R1和R2是A上的自反关系，即IA?R1，IA?R2。
由逆关系定义和IA?R1，得IA? R1-1；
由IA?R1，IA?R2，得IA? R1∪R2，IA? R1?R2。
所以，R11、R1∪R2、R1?R2是自反的。 3．解：正确．
对于集合A的任意元素x，均有?R （或xRa），所以a是集合A中的最大元． 按照最小元的定义，在集合A中不存在最 小元． 4．解：错误． 集合A的最大元不存在，a是极大元．
四、计算题
4．解：R=?,
S={,,,,,,,,,}
12 8 r(R)=IA．
5．解：（1）R=I?{, , ?,
, 10 4 6 , , , , , ,
, 2 3 5 , , , , }
（2）关系R的哈斯图如图四 1
（3）集合B没有最大元，最小元是：2 -9 7 11 图四：关系R的哈斯图
6．解：R＝{, , , }
0??1?R2 = {, , , }?{, , , }
={, , } 7．解：（1）R={,,,, ? 1 2 ,,,,,}
3 ? ? （2）关系图如图五 4 ? （3）因为,,,均属于R， 即A的每个元素构成的有序对均在R中，故R在 图五 A上是自反的。
因有与属于R，但不属于R， 所以R在A上不是传递的。
五、证明题
3．设R是集合A上的对称关系和传递关系，试证明：若对任意a?A，存在b?A，使得?R，则R是等价关系．
证明：已知R是对称关系和传递关系，只需证明R是自反关系．
?1?0MR???0??
?a?A，?b?A，使得?R，因为R是对称的，故?R；
又R是传递的，即当?R，?R ??R； 由元素a的任意性，知R是自反的．
所以，R是等价关系．
4．若非空集合A上的二元关系R和S是偏序关系，试证明：R?S也是A上的偏序关系． 证明：.① ?x?A,?x,x??R,?x,x??S??x,x??R?S，所以R?S有自反性；
②?x,y?A,因为R，S是反对称的，
?x,y?R?S??y,x?R?S?(?x,y??R??x,y??S)?(?y,x??R??y,x??S)?(?x,y??R??y,x??R)?(?x,y??S??y,x??S)?x?y?y?x?x?y
所以，R?S有反对称性．
?x,y,z?A，因为R，S是传递的，
?x,y??R?S??y,z??R?S
??x,y??R??x,y??S??y,z??R??y,z??S
??x,y??R??y,z??R??x,y??S??y,z??S
??x,z??R??x,z??S??x,z??R?S 所以，R?S有传递性．
总之，R是偏序关系．
三亿文库包含各类专业文献、文学作品欣赏、幼儿教育、小学教育、专业论文、生活休闲娱乐、各类资格考试、行业资料、高等教育、中学教育、离散数学关系部分经典练习及答案21等内容。　
　离散数学图论部分经典试题及答案_理学_高等教育_教育...离散数学图论部分综合练习 离散数学图论部分综合练习 ...e 和 r 满足的关系式 . 8.设连通平面图 G 的... 　离散数学习题答案习题一 1、利用逻辑联结词把下列命题翻译成符号逻辑形式 (1) ...(m & n) 答:R = R ;简要说明如下:本关系图分为两个部分,R = R1 ∪... 　离散数学常见典型题练习题及参考答案 隐藏&& 第一章部分课后习题参考答案 16 设 p、q 的真值为 0;r、s 的真值为 1,求下列各命题公式的真值。 (1)p∨(... 　有些成员是青年人。所以,有些成员是青年专家。 ?个体域是人的集合? F?x?:...G?x?? ⑦EG 推理正确 《离散数学》综合练习?二?参考答案 集合、关系、函数... 　离散数学期末练习题 (带答案)_理学_高等教育_教育专区...设A={1,2,3,4,5},R是A上的二元关系,且R={...绝对经典搞笑照片 89份文档
应届生求职季宝典 英文... 　离散数学最全课后答案(屈婉玲版)word下载!!离散数学习题解 1 习题一 1.1.略...7.12.设 A={0, 1, 2, 3}, R 是 A 上的关系, 且 R={?0, 0?,... 　最新离散数学练习题(含答案)_研究生入学考试_高等教育_教育专区。易自考 离散...传递关系 第二部分 02324# 非选择题 第 3 页共4页 离散数学试题 易自考 二... 　离散数学-第七章二元关系课后练习习题及答案_教育学_高等教育_教育专区。第七章作业 评分要求: 1. 合计 100 分 2. 给出每小题得分(注意: 写出扣分理由). 3...当前位置： >>
离散数学 第二章 关系
离散数学西安交通大学 电子与信息工程学院 计算机软件所 刘国荣1空关系 全关系 幺关系 元组 叉积 关系 逆关系 复合关系 关系幂 自反关系 对称关系 反对称关系 传递关系交关系 并关系 余关系 差关系等价关系 自反传递闭包 半序关系 传递闭包2离散数学 第二章 关系 (relation)§1 . 集合的叉积 n元组 元组 §2 .关系 关系 §3 .关系的表示 关系的性质 关系的表示 关系的 §4 .关系的运算 关系的运算 §5. 等价关系 §6. 半序关系3离散数学§1 . 集合的叉积 n元组 元组定义1.叉积，笛卡尔积 定义 (cross product ,Cartesian product(1637)) ? n个集合A1， A2，… ，An的 n 维叉积定义为 … n ×1 A i =A1 × A2 × … × An i= ={(a1, a2, …, an): ai∈ Ai(1≤i ≤ n)} ； ? n 维叉积A1 × A2 × … × An的每个元素(a1, a2, …, an) 都称为一个n元组（n-tuple）；即，叉积是元组的集 合； ?每个n元组(a1, a2, …, an)的第i个位置上的元素ai称为 该n元组的第i个分量（坐标或投影）；元组各分量的 顺序不能改变； ? n 称为该叉积及其元组的维数； ?两个元组相等?它们的维数相同且对应的分量相等。4离散数学即 (a1, a2, …, an)= (b1, b2, …, bm) ?n=m∧(?i∈N)(1≤i ≤ n)(ai = bi)；注：笛卡尔( )，法国数学家， 1637年发表《方法论》之 一《几何学》，首次提出坐标及变量概念。这里是其概念的推广。定义2. 定义 ? 二个集合A，B的(二维或二重)叉积定义为 A×B ={(a, b): a∈ A ∧b∈B} ； ?其元素――二元组(a, b)通常称为序偶或偶对(ordered pair) ； ?二元组(a, b)的第一分量上的元素a称为前者；第二分 量上的元素b称为后者； ?二重叉积的A× B第一集合A称为前集；第二集合B称 为后集。5离散数学例1 . A={ a,b,c }, B={0,1} A×B={(a,0), (a,1), (b,0), (b,1), (c,0), (c,1)} B×A={(0,a), (0,b), (0,c), (1,a), (1,b), (1,c)} 例2 . A={张三,李四}，B={白狗,黄狗} A×B={(张三,白狗),(张三,黄狗),(李四,白狗),(李四, 黄狗)} B×A={(白狗,张三),(白狗,李四),(黄狗,张三),(黄狗, 李四)} 一般地说，关于叉积和元组我们有： (1) (a, b)≠ (b, a)； (2) A×B ≠ B × A ； (3)二元组不是集合，因为二元组中的分量计较顺6离散数学序,而集合中的元素是不讲顺序的。但是我们为了将所有 的概念都统一于集合概念，我们可采用克亚托斯基 (Kazimierz Kurafowski)在1921年给出的定义 (a, b)={{a},{a, b}} 将二元组定义为比其元素高二层的集合； (4)我们也可用二元组来递归的定义n元组如下： (a,b,c)=((a,b),c) ……… (a1, a2, …, an-1 , an)= ((a1, a2, …, an-1) , an) (5)这样，我们也就可用二重叉积来递归的定义n维叉 积如下： A×B×C=(A×B)×C …… … A1×A2× …×An-1×An= (A1×A2× …×An-1)×An7离散数学(6)利用(5)所给的定义，我们可以递归的定义集合的 叉积幂如下： A2= A×A A3 = A2 ×A … An = An-1 ×A (7)我们规定空集?与任何集合A的叉积是空集? 。 即 A×? = ? = ?×A 由于若偶对的第一分量或第二分量不存在就没有偶 对存在，故规定它们的叉积集合为空集是合理的。 定理1.设A,B,C,D是四个非空的集合。那么 定理 A×B = C×D ? A = C ∧ B = D 。8离散数学[证].?):显然。 ? ?)：（采用逻辑法）对任何的元素a,b a∈A∧b∈B ?(a,b)∈A×B ?(a,b)∈C×D (条件：A×B = C×D ） ? a∈C∧b∈D 所以 A = C ∧ B = D 。 定理2 定理 . 设A,B,C是三个集合。则 (1)左分配律：A×(B∪C) = (A×B)∪(A×C) (叉积对并的)； (2)左分配律：A×(B∩C) = (A×B)∩(A×C) (叉积对交的)； (3)右分配律：(A∪B)×C = (A×C)∪(B×C)9离散数学(叉积对并的)； (3)右分配律：(A∩B)×C = (A×C)∩(B×C) (叉积对交的)。 [证].只证(1)（采用逻辑法） 对任何的元素a,b (a,b)∈A×(B∪C) ?a∈A∧b∈ B∪C ? a∈A∧(b∈B∨b∈C) ? (a∈A∧b∈B)∨(a∈A∧b∈C) (分配律：p∧(q∨r)?(p∧q)∨(p∧r)) ? (a,b)∈A×B∨(a,b)∈A×C ? (a,b)∈(A×B)∪(A×C) 所以 A×(B∪C) = (A×B)∪(A×C) 。10aRb离散数学§2 .关系 关系一.关系的基本概念 关系的基本概念 定义1 定义 .二元关系(binary relation) 设A,B是两个非空的集合。 ?二重叉集A×B 的任何一个子集R都称为是从集合A 到集合B的一种二元关系。即 R?A×B ； ?当 (a,b)∈R 时，称a与b有关系R ，记为 aRb ； ?当 (a,b)?R 时，称a与b没有关系R ，记为aRb或a R b ； ?当A=B时，即R?A×A，则称R是A上的一个二元关 系。 例1 . 设A是西安交通大学全体同学组成的集合。11离散数学R={(a,b) : a∈A∧b∈A∧a与b是同乡}?A×A 于是，R是西安交通大学同学之间的同乡关系。 例2 . 设A是某一大家庭。 R1 = {(a,b) : a∈A∧b∈A∧a是b的父亲或母亲}?A×A R2 = {(a,b) : a∈A∧b∈A∧a是b的哥哥或姐姐}?A×A R3 = {(a,b) : a∈A∧b∈A∧a是b的丈夫或妻子}?A×A 于是， R1是父母与儿女之间的关系，即父母子女关系； R2是兄弟姐妹之间的关系，即兄弟姊妹关系； R3是夫妻之间的关系，即夫妻关系。 例3 . 设N是自然数集合。12离散数学R= { (a,b) : a∈N∧b∈N∧a|b }? N×N 则R就是自然数集合上的整除关系。 例4 . 设Ｉ是整数集合。 R= { (a,b) : a∈I∧b∈I∧(?k∈I)(a-b =k?m)}? I×I 则R就是整数集合上的(模m)同余关系。 例5 . 设A是某一大型FORTRAN程序中诸程序块的集合。 R= { (a,b) : a∈A∧b∈B∧a调用(call)b }?A×A 则R就是程序块集合上的调用关系。 例6 . 设A = {风，马，牛}， R = { (风,马)，(马,牛) }?A×A 则R是A上的一个二元关系。13离散数学关于关系概念，我们还有如下的几个定义和说明： 1°全关系(full relation)： 关系R=A×B称为全关系； 2°空关系(empty relation)： 关系R= ?称为空关系； ?空关系和全关系都是平凡关系； ? 3°幺关系或单位关系(identical relation)： 关系R= {(a, a): a∈A}? A×A称为A上的幺关系； 例7 . 设A={1,2,3,4}，则 R1 = {(1,1) , (2,2) , (3,3) , (4,4) }是幺关系； R2 = {(1,1) , (2,3) , (3,4) , (4,4) }不是； R3 = {(1,1) , (2,2) , (3,3) , (4,4) ,(1,2) }也不是；14离散数学4°关系的交，并，余运算： ?叉积是一种（新型的）集合；关系是叉积的子集； 因此，关系也是一种（新型的）集合； ? 从而，有关集合论的一切概念、论述、运算也都 适合于关系； ? ?尤其是集合的交，并，余，差运算也都适合于关 系；因此，关系也有交，并，余，差运算； 例8 . 设N是自然数集合。 R=小于关系={(m,n) : m∈N∧n∈N∧m&n}?N×N S=整除关系={(m,n) : m∈N∧n∈N∧m|n}?N ×N 则 R′ =大于等于关系(≥)； R∪S=小于等于关系(≤) ；15离散数学R∩S=不相等的整除关系(≠∧|)； R\S=小于又不整除关系(& ∧?)； S\R=相等关系(=) 。 5°关系的扩充(expansion)： 若R1 ? R2 ，则称关系R2 是关系R1的一个扩充；R1R26° n元关系： n元关系R是n 维叉积的一个子集；即 R? A1×A2× …×An16离散数学定义3.前域(domain) 后域(codomain) 定义 设A,B是两个非空集合，R ?A×B是一关系。则关系 R的 ?前域：? (R) = { a : a ∈A∧(?b∈B)(aRb)}?A ； ?后域： ? (R) = { b : b∈B∧(?a∈A)(aRb) }?B 。R A a ? (R) b ? (R) B例9 .设A={1,2,3,4} ，B={2,4,6,8,10} 。 R={(1,2),(2,4),(3,6)}。 则 ? (R) = {1,2,3}?A ，? (R) = {2,4,6}?B 。 二.关系的一些关联性质 关系的一些关联性质17离散数学定理1. 定理 设R1,R2 ? A×B是两个关系。若 R1 ? R2 ，则 (1)保序性：? (R1) ? ? (R2) ； (2)保序性： ? (R1) ? ? (R2) ； [证].只证(1) （采用逻辑法）对任何元素a ∈A， a ∈ ? (R1 ) ? a∈A∧(?b∈B)(a R1 b) ? a∈A∧(?b∈B)((a,b)∈R1) ? a∈A∧(?b∈B)((a,b)∈R2) (条件：R1 ? R2 ) ? a∈A∧(?b∈B)(a R2 b) ? a ∈ ? (R2 ) 所以 ? (R1) ? ? (R2) 。18离散数学定理2 定理 . 设R1, R2是A×B上的两个二元关系。则 (1)? (R1 ∪ R2) = ? (R1)∪? (R2) (2)? (R1 ∪ R2) = ? (R1)∪? (R2) (3)? (R1 ∩ R2) ? ?(R1)∩? (R2) (4)? (R1 ∩ R2) ? ? (R1)∩? (R2) [ ]. [证].只证(1)， (3) (1) (1)?先证： ? (R1)∪? (R2) ? ? (R1 ∪ R2) (采用包含 法) 由于 R1 ? R1 ∪ R2， R2 ? R1 ∪ R2 ， 依定理1，有 ? (R1) ? ? (R1∪R2)， ? (R2) ? ? (R1∪R2) 故根据第一章§2定理2的(3 ′) ，就可得 ? (R1)∪? (R2) ? ? (R1 ∪ R2) 。 ?次证：? (R1 ∪ R2) ? ? (R1)∪? (R2) (采用元素 19离散数学法) 对任何元素a ∈A ， 若 a ∈ ? (R1∪ R2)， 则存在 b∈B ，使得 a R1 ∪ R2 b 因此 (a,b)∈R1 ∪ R2 ， 从而有 (a,b)∈R1 或者 (a,b)∈R2 即 aR1b 或者 aR2b 于是 a ∈ ? (R１) 或者 a ∈ ? (R2 ) 故此 a ∈ ? (R1)∪? (R2)20离散数学所以 ? (R1 ∪ R2) ? ? (R1)∪? (R2) 。 (3) ?先证： ? (R1 ∩ R2) ? ? (R1)∩? (R2) (采用包含 法) 由于 R1∩R2 ? R1 ， R1∩R2 ? R2 ， 依定理1，有 ? (R1 ∩ R2) ?? (R1) ，? (R1 ∩ R2) ? ? (R2) 故 根据第一章§2定理2的(3″) ，就可得 ? (R1 ∩ R2) ? ? (R1)∩? (R2) 。 ?其次，反方向的包含不成立。且看下面的反例。 例9 .设 R1 ={(1,1),(2,2)} ， R2 ={(1,2),(2,1)} 。 则，由于 R1 ∩ R2 = ? ，故 ? (R1 ∩ R2) = ? 但是，由于? (R1) = {1,2 } ， ? (R2) = {1,2} 故 ? (R1)∩? (R2) = {1,2 }21离散数学所以 ? (R1)∩? (R2) ?? (R1 ∩ R2) 。 元素a∈ 和集合 和集合A 在关系R 元素 ∈A和集合 1?A在关系 ? A×B下的关联集 在关系 × 下的关联集 (1)a的R-关联集(R-relative set of a)： R(a)={b : b∈B∧aRb }?B ； (2) A1的R-关联集(R-relative set of A1)： R(A1)={b : b∈B∧ (?a∈A1)(aRb) }?B 。 于是，类似于定理1(2)，定理2(2)(4)，我们有 定理.设R? A×B是一个二元关系， A1 ,A2? A 。则 定理 (1)保序性：A1 ? A2 ? R(A1) ? R(A2) ； (2)R(A1∪A2) = R(A1)∪R(A2) ； (3)R(A1∩A2)? R(A1)∩R(A2) 。22离散数学[证].仿定理1(2)，定理2(2)(4)可证。留给读者。 例.设A={a,b,c,d}，并且设 R={(a,a),(a,b),(b,c),(c,a),(d,c),(c,b)}。 那么 R(a)= {a,b}， R(b)= {c} ； 并且如果 A1 = {c,d} ， 那么 R(A1)={a,b,c} 。23离散数学§3 .关系的表示 关系的表示 关系的性质一.关系表示法 关系表示法 1°关系的矩阵表示法 设关系R?A×B ， 这里A,B是两个非空的有限集合， A={ a1,a2,a3,…,am } ， B={ b1,b2,b3,…,bn } 。 则我们可用一个m×n阶0―1矩阵MR来表示关系R，我 们称此矩阵MR为关系R的关系矩阵(relation matrix)。 MR=(xij)m×n ，其中 1 当（ai,bj) ∈ R时 xij = ( i=1,…,m ； j=1,…,n) 0 当（ai,bj) ? R时24离散数学例1 .设关系 R?A×B ，A={ a1,a2,a3,a4 } ，B={b1,b2,b3} R ={ (a1, b2),(a1, b3),(a2, b3),(a3, b1),(a4, b2)}。 于是，我们得到R的关系矩阵MR为(下面左矩阵)b1 a1 a2 0 0 1 0 b2 1 0 0 1 b3 1 a1 1 0 0 a1 １ 0 1 a2 ０ １ １ a3 1 1 １MR =a3 a4；MS= a2a3例2 .设关系 S?A×A ，A={ a1,a2,a3} ， S={ (a1, a1),(a2, a2),(a3, a3),(a1, a3),(a3, a1) ,(a2, a3),(a3, a2)} 于是，我们得到S的关系矩阵MS为(上面右矩阵)25离散数学2°关系的图形表示法 设关系R?A×B ， 这里A,B是两个非空的有限集合， A={ a1,a2,a3,…,am } ， B={ b1,b2,b3,…,bn } 。 则我们可用一个有向图GR=(VR,ER)来表示关系R，我 们称此有向图GR为关系R的关系图(relation digraph)。 ? VR =A∪B，ER =R； ? VR中的元素称为结点，用小圆点表示；表示A中 元素的结点放在左边一块；表示B中元素的结点放在右 边一块； ? ER中的元素称为边，用有向弧表示；若aRb(即 (a,b)∈R)，则在表示a的结点和表示b的结点之间连一条 有向弧。有向弧的始端与结点a相连，有向弧的终端与 结点b相连；26离散数学?有时我们会用两个圆圈分别将表示两个集合A和B 中元素的结点圈起来。 ?所有有向弧的始端结点构成? (R)；所有有向弧的 终端结点构成? (R)。 ?若A=B，这时令VR =A，并规定只画表示一个集合 元素的结点；表示元素间关系的有向弧也只在此一个集 合的结点间画出 。 例3 .设关系 R?A×B，A={ a1,a2,a3,a4 }，B={b1,b2,b3} R ={ (a1, b2),(a1, b3),(a2, b3),(a3, b1),(a4, b2)} 于是，我们得到R的关系图GR为下面左图。27离散数学a1 a2 A a 3 a4 GR R b1 b2 B b3 a2 GS a3 a1例4 .设关系 S?A×A ，A={ a1,a2,a3} ， S={ (a1, a1),(a2, a2),(a3, a3),(a1, a3),(a3, a1) ,(a2, a3),(a3, a2)} 于是，我们得到S的关系图GS为上面右图。注： ?图中各结点所带的小圆圈称为自反圈；一对结点间的来回边 称为双向弧；否则，一对结点间只有一条边，则此边称为单向弧。 ?关系的表示法有三种:集合表示法,矩阵表示法,图形表示法。28离散数学二 .关系的性质 关系的性质 设二元关系R?X×X(或者说R?X2)，这里X≠?是一集 合。则R称为是X上的 1°自反关系(reflexive relation)：当且仅当R满足 自反性：(?x∈X)(xRx) ； 显然，对于自反关系R， ? (R) = ? (R) = X 。?反自反关系(irreflexive relation)：当且仅当R满足 反自反性：(?x ∈ X)( x R x ) 或(?x∈ X)?(xRx) ； ?常见的自反关系有相等关系(=)，小于等于关系(≤)，包含关系(?)等； 而不相等关系(≠)，小于关系(&)，真包含关系(?)等 都不是自反关系，它们都是反自反关系。29离散数学注： ?自反性和反自反性是关系的两个极端性质；因此，自反关系 和反自反关系是两种极端关系； ?从关系矩阵来看：自反关系关系矩阵的对角线上元素全是1； 反自反关系关系矩阵的对角线上元素全是0； ?从关系图来看：自反关系关系图的各结点上全都有自反圈； 反自反关系关系图的各结点上全都没有自反圈。5. X={a,b,c,d}。则关系 例5.设 X={a,b,c,d} R1={(a,b),(a,a),(b,b),(c,d),(c,c),(d,d)} 是X上的自反关系,但不是X上的幺关系,因(a,b), (c,d)∈R1；而关系 R2 ={(a,a),(b,b),(c,c),(d,d)} 是X上的自反关系,同时也是X上的幺关系； R3={(a,b),(a,c),(a,d),(c,d)}30离散数学是X上的反自反关系。注：由此例可知幺关系一定是自反关系，但自反关系不一定是幺关 系。2°对称关系(symmetric relation)：当且仅当R满足 对称性：(?x∈X)(?y∈X)(xRy ? yRx) ； 3°反对称关系(antisymmetric relation)：当且仅当R满 足 反对称性：(?x∈X)(?y∈X)(xRy∧yRx?x = y) ；?常见的对称关系有相等关系(=)，不相等关系(≠)，同余关系，朋友关系，同学关系，同乡关系等； 而小于等于关系(≤)，包含关系(?)，上下级关系，父 子关系等都不是对称关系，它们都是反对称关系。 31离散数学注：?对称性和反对称性是关系的两个极端性质；因此，对称关系 和反对称关系是两种极端关系； ?从关系矩阵来看：对称关系的关系矩阵是对称矩阵。即xij = xji (1≤i,j ≤ n)；反对称关系的关系矩阵满足如下性质 xij = 1 ? xji = 0 (1≤i,j ≤ n) ； ?从关系图来看：对称关系关系图的结点间若有弧则都是双向弧； 反对称关系关系图的结点间若有弧则都是单向弧；例6.设X={a,b,c}。则关系 . R1={(a,b),(b,a)} ，R2={(a,a),(b,b)} 都是X上的对称关系；而关系 R3={(a,b),(b,a),(b,c)} 不是X上的对称关系；因(b,c)∈ R3 ,但(c,b)? R3 。32离散数学例7.设X={a,b,c}。则关系 . R1={(a,a),(a,b) ,(a,c) ,(c,b) ,(c,c)} 是X上的反对称关系；而关系 R2={(a,a),(a,b) ,(a,c) ,(b,a) ,(c,b)} 不是X上的反对称关系；因(a,b)∈ R2 且(b,a)∈ R2 ,但 a≠b。 4°传递关系(transitive relation)：当且仅当R满足 传递性：(?x∈X)(?y∈X)(?z∈X)(xRy ∧ yRz?xRz)；?反传递关系(antisymmetric relation)：当且仅当R满足 反传递性：(?x∈X)(?y∈X)(?z∈X)(xRy ∧ yRz? x R z) ；?常见的传递关系有相等关系(=)，小于等于关系(≤)， 包含关系(?)，整除关系，同余关系，上下级33离散数学关系，同乡关系，后裔关系等； 而不相等关系(≠)，父子关系，朋友关系，同学关系 等都不是传递关系。注：?传递性和反传递性是关系的两个极端性质；因此，传递关系 和反传递关系是两种极端关系； ?概念反传递性和反传递关系一般不甚用，所以不加讨论；例8. 设X={a,b,c,d} 。则关系 R1={(a,b),(b,c),(a,c),(c,d),(a,d),(b,d)} 是X上的传递关系；而关系 R2={(a,b),(b,c),(a,c),(c,d),(a,d)} 不是X上的传递关系；因(b,c)∈ R2且(c,d)∈R2，但 (b,d)? R2 。34离散数学例9. 设X是平面上直线的集合。平行关系 R={(x,y) : x∈X ∧ y∈X ∧ x∥y} 由平面几何的知识知:若x∥y且y∥z，则 x∥z 。 由传递关系的定义知R是X上的传递关系。 例10. 设X是平面上三角形的集合。相似关系 R={(x, y) : x∈X ∧ y∈X ∧ x∽y} 由平面几何的知识知:若x∽y 且y∽z ，则 x∽z 。 由传递关系的定义知R是X上的传递关系。 例11. ?相等关系是自反的、对称的、反对称的、传递关系。 ?全关系X2是自反的、对称的、传递的。 ?幺关系I 是自反的、对称的、反对称的、传递的。35离散数学?空关系?是反自反的、对称的、反对称的、传递的。36( R离散数学§4 .关系的运算 关系的运算1°关系的逆运算 ° 定义1.逆运算(converse operation) 定义 设A，B是两个非空的集合。我们称一元运算 : 2A× B→ 2 B ×A 对任何二元关系R?A×B，使得 ( R = {(b,a) : b∈B∧a∈A∧aRb}?B×A ( 为关系的逆运算；称 R 是R的逆关系(converse of relation)。 ( 显然，对任何(b,a)∈ B×A，b R a ?aRb ；并且 T ( MR = MR 。37离散数学例1.设A={a,b,c} ，B={1,2}。则关系 R={(a,1),(a,2),(b,2),(c,1)} 的逆关系 ( R ={(1,a),(2,a),(2,b),(1,c)} 。 定理1.逆运算基本定理 定理 设两个关系R ? A×B，S ?A×B，这里 A,B是两个 非空的集合。则有 ( ( (1)反身律： R =R ； ( ( (2)保序性：R?S ? R ? S ； ( ( R=S ? R = S ； ( ( (3)分配律：R∪S= R ∪ S （逆对并的）； ( ( (4)分配律：R∩S= R ∩ S （逆对交的）； (5)X×Y=Y×X ；38离散数学( (7)交换律：(R′)=( R )′ （逆与余的）； ( ( (8)分配律：R\S= R \ S （逆对差的）； [证].只证(1)，(4)，(7) （采用逻辑法）( (6) ? =? ；(1)对任何(a,b)∈A×B ，有 ( ( (a,b)∈R ( ? (b,a)∈R ? (a,b)∈R ( ( 所以 R =R 。 (4)对任何(a,b)∈B×A ，有 (a,b)∈R∩S ? (b,a)∈R∩S39离散数学? (b,a)∈R∧(b,a)∈ S ( ( ? (a,b)∈R ∧(a,b)∈ S ( ( ? (a,b)∈ R ∩ S ( ( 所以 R∩S = R ∩ S 。 (7)对任何(a,b)∈B×A ，有 (a,b)∈(R′) ? (b,a)∈R′ ? (b,a)?R ( ? (a,b)?R ( ? (a,b)∈( R )′ ( 所以 (R′)= ( R )′ 。40离散数学2°关系的合成运算 ° 定义2.合成运算(composition operation) 定义 设A，B是两个非空的集合。我们称二元运算 o : 2A× B × 2B× C → 2 A×C 对任何两个二元关系R ?A×B ， S ?B×C ，使 得 RoS ={(a,c) : a∈A∧c∈C∧(?b∈B)(aRb∧bSc)}?A×C 为关系的合成运算；称RoS是R与S的合成关系。 显然，对任何(a,c)∈A×C，aRoSc?(?b∈B)(aRb∧bSc) 。 例2 .设A={ a1,a2,a3} ，B={b1,b2} ，C={c1, c2, c3, c4} 关系 R?A×B ， S?B×C R ={(a1, b1),(a2, b2),(a3, b1)} S ={(b1, c4),(b2, c2),(b2, c3)}41离散数学于是，我们得到R与S的合成关系为 R o S ={(a1, c4),(a2, c2) ,(a2, c3),(a3, c4)} 其合成关系的关系图为R a1 A a2 a3 b1 B b2SRoSc1 c2 c3 C c4例3.设A是老年男子的集合，B是中年男子的集合，C是 3. 青少年男子的集合。 R是由A到B的父子关系， R? A×B 42离散数学S 是由B到C的父子关系， S?B×C 则复合关系R o S是A到C的祖孙关系。 定理2.合成运算基本定理 定理 设R,R1,R2 ? A×B， S,S1,S2 ? B×C，T ? C×D ，这 里 A,B,C,D是四个非空的集合。则 (1)R o ? = ? o S = ?； (2)?( R o S ) ??( R )；?( R o S ) ??(S )； (3)保序性：R1 ?R2 ∧ S1 ? S2 ? R1 o S1 ?R2 o S2 ； (4)结合律：R o (S o T) = (R o S) o T； (5)左分配律：R o (S1∪S2) = (R o S1) ∪ (R o S2) ； (合成运算对并的) 右分配律： (S1∪S2) o T = (S1 o T) ∪ (S2 o T)； (合成运算对并的) (6)左分配不等式： R o (S1∩S2) ?(R o S1)∩(R o S2)；43离散数学(合成运算对交的) 右分配不等式： (S1∩ S2) o T ?(S1 o T)∩(S2 o T)； (合成运算对交的) (7) 鞋袜律：(R o S) = S o R 。 [证].只证(4)，(5) （采用逻辑法） (4)对任何元素a∈A,d∈D ，有 a R o (S o T)d ?(?b∈B)(aRb ∧b(S o T)d) ?(?b∈B)(aRb ∧(?c∈C)(bSc∧cTd)) ?(?b∈B)(?c∈C)(aRb∧(bSc∧cTd)) (量词前移：p∧?xA(x)? ?x(p∧A(x)) ) ? (?c∈C)(?b∈B)(aRb∧(bSc∧cTd)) (量词交换：?x?yA(x,y)??y?xA(x,y) )44离散数学? (?c∈C)(?b∈B)((aRb∧bSc)∧cTd) (∧的结合律：p∧(q ∧ r)?(p ∧ q )∧ r ) ? (?c∈C)((?b∈B)(aRb∧bSc)∧cTd) (量词后移：?x(p∧A(x)) ? p∧?xA(x) ) ? (?c∈C)(a(R o S)c∧cTd) ? a(R o S) o Td 所以 R o (S o T) = (R o S) o T； (5)对任何元素a∈A,c∈C ，有 a R o (S1∪S2)c ?(?b∈B)(aRb ∧b(S1∪S2)c) ?(?b∈B)(aRb ∧(bS1c∨bS2c)) ?(?b∈B)((aRb∧bS1c)∨(aRb∧bS2c)) (∧对∨的分配律：p∧(q∨r)?(p ∧ q ) ∨ (p ∧ r ) )45离散数学?(?b∈B)(aRb∧bS1c)∨(?b∈B)(aRb∧bS2c) (?量词对∨的分配律：?x(A(x)∨B(x)) ??x(A(x)∨?xB(x) ) ?a(R o S1)c ∨a (R o S2)c ? a(R o S1)∪(R o S2)c 所以 R o (S1∪S2) = (R o S1)∪(R o S2) 。 ?但是合成运算不满足交换律。即，一般 R o S≠S o R 例4.设A={a,b,c,d,e} 。则关系 R={(a,b),(c,d),(b,b)}，S={(b,e),(c,a),(a,c),(d,b)} 的合成 关系为46∨lk =1离散数学R o S= {(a,e),(b,e),(c,b)}，So R ={(a,d),(c,b),(d,b)} 所以 R o S≠S o R 。 3°关系矩阵的合成运算 ° 设R? A×B ， S?B×C 是两个二元关系，其合成关 系为R o S。这里A={ a1,a2,…,am} ，B={b1,b2 , …, bl} ， C={c1, c2, …,cn}。 并设它们的关系矩阵分别为 MR=(xij)m×l ， MS=(yij)l×n ， MR o S =(uij)m×n 则我们有： ? MR o S = MR o MS 其中：我们令 MR o MS = (tij)m×n l tij = ∨ (xik ∧ ykj) (1≤i ≤ m,1 ≤ j ≤ n)k =147离散数学注：这里关系矩阵的合成运算与《线性代数》中的一般矩阵的乘法 运算颇为相似。所不同的是：乘法现在换成布尔乘(∧)；加法现在换 成布尔加(∨)。值得注意的是：这里的布尔加1 ∨ 1=1（不进位）， 而非1 ∨ 1=0（进位）。例5.设A={a,b,c,d,e} 。则关系 R={(a,b),(c,d),(b,b)}，S={(b,e),(c,a),(a,c),(d,b)} 的合成关系 R o S= {(a,e),(b,e),(c,b)} 其关系矩阵分别为 MR =?0 ? ?0 ?0 ? ?0 ?0 ? 1 0 0 0? ? 1 0 0 0? 0 0 1 0? ? 0 0 0 0? ? 0 0 0 0?M S=?0 ? ?0 ?1 ? ?0 ?0 ?0 1 0 0? ? 0 0 0 1? 0 0 0 0? ? 1 0 0 0? ? 0 0 0 0?MR o S =?0 ? ?0 ?0 ? ?0 ?0 ?0 0 0 1? ? 0 0 0 1? 1 0 0 0? ? 0 0 0 0? ? 0 0 0 0?48离散数学现在我们计算 MR o MS =?0 ? ?0 ?0 ? ?0 ?0 ? 1 0 0 0? ? 1 0 0 0? 0 0 1 0? ? 0 0 0 0? ? 0 0 0 0? ?0 ? ?0 ?1 ? ?0 ?0 ? 0 1 0 0? ? 0 0 0 1? 0 0 0 0? ? 1 0 0 0? ? 0 0 0 0?=其中： 5 t25= ∨ (x2k ∧ yk5) k =1 =(x21∧ 15)∨(x22∧ 25)∨(x23∧ 35)∨(x24∧ 45)∨(x25∧ 55) ∧y ∨ ∧y ∨ ∧y ∨ ∧y ∨ ∧y =(0 ∧0)∨ (1∧1)∨ (0 ∧0)∨ (0 ∧0)∨ (0 ∧0) =0 ∨ 1 ∨ 0∨ 0 ∨ 0 =1 这说明 MR o S = MR o MS 。下面我们就来证明这个等式： [证].（采用逻辑法）49?0 ? ?0 ?0 ? ?0 ?0 ?0 0 0 1? ? 0 0 0 1? 1 0 0 0? ? 0 0 0 0? ? 0 0 0 0?离散数学对任何的i ，j (1≤i ≤ m,1 ≤ j ≤ n) ，有 uij =1 ? aiR o Scj ? (?b∈B)(aiRb ∧ bScj ) ? (aiRb1 ∧b1Scj ) ∨ (aiRb2 ∧b2Scj ) ∨ …∨ (aiRbl∧blScj ) ? (xi1 =1 ∧ y1j =1) ∨ (xi2 =1 ∧ y2j =1) ∨ …∨ (xil =1 ∧ ylj =1) (这里： ∧是命题的真值联结词‘且’； ∨是命题的真值联结词‘或’。) ? (xi1 ∧ y1j ) ∨ (xi2 ∧ y2j ) ∨ …∨ (xil ∧ ylj ) =1 (这里： ∧是布尔乘； ∨是布尔加。) l ? ∨ (xik ∧ ykj)=1 k =1 ? tij = 1 即 uij = tij 因此 (uij)m×n = (tij)m×n 所以 MR o S = MR o MS 。50离散数学4°关系的闭包运算（宏运算） °关系的闭包运算（宏运算） 定义3.关系的合成幂(nth power) 定义 设二元关系R ?A×A，n∈N 。这里A 是一个非空的集 合， N 是自然数集。我们规定： (1) R0 =I （这里I=IA={(a,a) : a∈A}是A上的幺关系）； (2) R1 =R； (3) Rn+1 =RnoR (特别地：R2 =RoR )。 定理3.指数律 定理 设二元关系R? A×A，m ,n∈N 。这里 A是一个非空 的集合， N 是自然数集。则 (1)交换律： RmoRn = RnoRm= Rm+n ； 特别地： IoR = RoI= R (幺关系是合成运算的幺元)； (2)交换律： (Rm)n = (Rn)m= Rm?n 。51离散数学[证]. （采用数学归纳法） 只证(1)的一个等式： RmoRn = Rm+n ；另一个等式： RnoRm= Rm+n 同理可证。 归纳变量选取n（让m固定） n=0时， RmoR0 = RmoI (定义3的(1)：R0 =I) = Rm n=1时， RmoR1 = RmoR (定义3的(2)：R1 =R) = Rm+1 (定义3的(3)) 结论成立； n=k时，假设结论成立。即 RmoRk = Rm+k ； n=k+1时， RmoRk+1= Rmo(RkoR) (定义3的(3)) = (RmoRk )oR (结合律) = Rm+koR (归纳假设) = Rm+k+1 (定义3的(3))52离散数学结论成立； 根据数学归纳法，即证明了该结论。 例6.设二元关系R? A×A,这里A={a,b,c} ,R={(a,b),(c,b)}。 从而有 ( I={(a,a),(b,b),(c,c)} ， R ={(b,a),(b,c)} ( ( R o R={(b,b)} ，R o R ={(a,a),(a,c),(c,a),(c,c)} ( ( ( ( o R ≠ I ，R o R ≠ I ， R o R ≠ R o R 。 于是 R注：? 这个例子说明一般情况下逆关系不是关系合成运算的逆元； ? 由定理2的(1)有：? o R = R o ? = ? ，这说明空集是合成运算 的零元。 ?一般地 a Rnb ?(?c1)(?c2) …(?cn-1)(aRc1 ∧ c1Rc2 ∧ … ∧ cn-1Rb) ； 特别地 a R２b ?(?c) (aRc∧ cR b) 。53离散数学c1Rc2Rcn-2R a R aR２ RnR cn-1 R c b R b定义4.闭包运算(closure operation) 定义 设二元关系R ?A×A 。这里A 是一个非空的集合。我 们定义： (1)传递闭包(transitive closure)： ∞ R＋ = U Rk =R∪ R２ ∪ R3 ∪ …∪ Rk ∪ … ； k =1 (2)自反传递闭包(reflexive and transitive closure)： ∞ R? = U Rk =I∪R∪ R２ ∪ R3 ∪ …∪ Rk ∪ … 。k=054离散数学注：?传递闭包有时也记为t( R)；自反传递闭包有时也记为rt( R)； 其实还有别的闭包； ? a R＋b ? (?k∈N)(k ≥1)(aRkb) ； ? a R? b ?(?k∈N)(aRkb) ?(a=b)∨(?k∈N)(k ≥1)(aRkb)?(a=b)∨(aR＋b) 。定理4.传递闭包基本定理 定理4. 设二元关系R? A×A，R≠? 。则 (1)若 m∈N，m ≥1 ，则 Rm ? R＋ ；特别地 R ? R＋ ； (2) R＋是传递关系：即，对任何元素 a，b，c ∈ A ， aR＋b∧bR＋c?aR＋c ； (3) R＋是包含R的最小传递关系：即，对任何二元关系 S?A×A，若R?S且S也是传递关系，那么 R＋?S ； n (4)若|A|=n ，则 R＋ = U Rk ；这时 55k =1离散数学a R＋b ? (?k∈N)(1≤k≤ n)(aRkb) ； (5)若R是传递关系, 则 R＋ = R 。 [证].只证(2)(采用逻辑法) (2)对任何元素a，b，c ∈ A ，有 aR＋b∧bR＋c ?(?k)(aRkb)∧(?l)(bRlc) (这里k ≥1, l ≥1) ?(?x1)(?x2) …(?xk-1)(aRx1 ∧ x1Rx2 ∧ … ∧ xk-1Rb) ∧ (?y1)(?y2) …(?yl-1)(bRy1 ∧ y1Ry2 ∧ … ∧ yl-1Rc) ?(?x1)(?x2) …(?xk-1)(aRx1 ∧ x1Rx2 ∧ … ∧ xk-1Rb ∧ (?y1)(?y2) …(?yl-1)(bRy1 ∧ y1Ry2 ∧ … ∧ yl-1Rc)) (量词前移：?xA(x)∧p??x(A(x)∧p) ) ?(?x1)(?x2) …(?xk-1)(?y1)(?y2) …(?yl-1)(aRx1 ∧ x1Rx2 ∧ … ∧ xk-1Rb∧ bRy1 ∧ y1Ry2 ∧ … ∧ yl-1Rc)56离散数学(量词前移：p∧?xA(x)??x(p∧A(x)) ) ?(?x1)(?x2) …(?xk-1)(?xk)(?xk+1)(?xk+2) …(?xk+l-1)(aRx1 ∧x1Rx2∧ … ∧xk-1Rxk∧xkRxk+1∧xk+1Rxk+2 ∧ … ∧xk+l-1Rc) (这里，我们令：xk=b , xk+1=y1, xk+2 =y2 , … , xk+l-1= yl-1) ?(?n)(aRnc) (这里，我们令：n=k+l ≥1+1 ≥1 ) ? aR＋c 所以，R＋是传递的。 定理5.自反传递闭包基本定理 定理 设二元关系R? A×A，R≠? 。则 (1)若 m∈N，则 Rm ? R* ；特别地 I? R* ， R ? R* ； (2) R*是自反传递关系：即，对任何元素 a∈A ， aR*a ；57离散数学对任何元素 a，b，c ∈ A ， aR*b∧bR*c?aR*c ； (3) R*是包含R的最小自反传递关系：即，对任何二 元关系S?A×A，若R?S且S也是自反传递关系，那么 R*?S ； n (4) |A|=n (4)若|A|=n ，则 R* = U Rk ；这时 k =0 a R*b ? (?k∈N)(0≤k≤n)(aRkb) ? (a=b)∨(?k∈N)(1≤k≤n)(aRkb) ； (5)若R是自反传递关系, 则 R* = R 。 [证].只证(3)（采用逻辑法） (3)对任何元素a，b∈ A ，有 aR*b ?(a=b)∨(?k)(aRkb) (这里k ≥1)58离散数学?(a=b)∨(?x1)(?x2) …(?xk-1)(aRx1 ∧ x1Rx2 ∧ … ∧xk-1Rb) ?aSb∨(?x1)(?x2) …(?xk-1)(aSx1 ∧ x1Sx2 ∧ … ∧xk-1Sb) (S是自反的且R?S) ?aSb∨aSb (S是传递的 且 ?xp?p ) ?aSb (幂等性：p∨p?p ) 所以 R*?S 。59离散数学§5. 等价关系1°等价关系和等价类 ° 定义1.等价关系(equivalence relation) 定义 设二元关系R? A×A。这里A是非空的集合。 R是A上的等价关系?R是自反的、对称的、传递的。 ? 显然 ?(R) = ?(R) = A (因为等价关系是自反的)；例1.同乡关系是等价关系。 例2 .平面几何中的三角形间的相似关系是等价关系。 例3 .平面几何中的三角形间的全等关系是等价关系。60离散数学例4 .平面几何中的直线间的平行关系是等价关系。 例5 .设N是自然数集，m是一正整数， R={(a,b) :a∈N ∧ b∈N ∧ a ≡ b (mod m)} 由等价关系的定义知R是N上等价关系；我们称R是N上 的模m同余关系。 例6.非空集合A上的幺关系、全关系都是等价关系。 6. 例7.非空集合A上的空关系不是等价关系(因为空关系不 7. 自反) 。 例8.设二元关系R? A×A,这里 8. A={a,b,c} , R={(a,a), (b,b), (c,c), (b,c),(c,b)} 则R是A上的等价关系。其关系图如下61离散数学abc?等价关系的实质是将集合A中的元素进行分类。 ? 定义2. 定义2.等价类(块)(equivalence classes(block)) 2. 设R是非空集合A上的等价关系。对任何元素a∈A，由 a生成的(或者说是由a诱导出的)关于R的等价类定义为 {b :b∈A∧bRa} 记为[a]R. (显然有[a]R ? A) 。同时称a为等价类[a]R的代 表元。62离散数学定义3. 定义3. 设R是非空集合A上的等价关系。我们定义集合 Π R = {[a]R : a∈A} (注意：应去掉重复的类！) 为集合A关于等价关系R的商集。记为A/R。称A/R中元素 的个数为R的秩。 例9.设N是自然数集，m是一个正整数。R是N上的模m 同余关系，即 R={(a,b) : a∈ N ∧ b∈ N ∧ a ≡ b (mod m)} 。 对于任何自然数a，b∈ N ， aRb ? a ≡ b (mod m)?(?k∈I)(a-b=km) ； 由等价关系的定义知R是N上的等价关系； 对于任何自然数a∈ N ，以a为代表元的等价类 [a]R = [a]m ={b :b∈N∧b ≡ a (mod m)}； 自然数集N关于等价关系R的商集63离散数学N/R= Π R = {[0]R,[1]R,[2]R,[3]R,…,[m-1]R } ； 或者记作 Nm = N/≡ = Π≡ = {[0]m,[1]m,[2]m,[3]m,…,[m-1]m}； 商集N/R共有m个等价类，故R的秩为m； 特别地，取m =5，则有 N５ = {[0]５,[1]５,[2]５,[3]５,[4]5}； 又如 [3]５ ={3,8,13, …,5k+3, …} (这里：k∈N) 。 例10.例8中等价关系R的等价类为 10. [a]R = {a}, [b]R = [c]R = {b,c} ； 其商集为 A/R= ΠR = {[a]R , [b]R }={{a},{b,c}}； 故其秩为2。64离散数学定理1. 定理 设R是非空集合A上的等价关系。对任意的a,b∈A， 有 (1)a∈[a]R (故[a]R ≠?) ； (2)aRb (即 (a,b)∈R) ? [a]R = [b]R ； (3)(3.1) [a]R∩ [b]R≠? ? [a]R = [b]R (? aRb，即 (a,b)∈R) ； (3.2) (a,b)?R ? [a]R∩ [b]R = ? ； (4)两个等价类[a]R和[b]R ，要么完全重合(即[a]R = [b]R )，要么不交(即[a]R∩ [b]R = ? )；二者必居其一，也 只居其一。 [证].（采用逻辑法） (1)对任何元素a，有 a∈A ?aRa (R是等价关系，故R自反)65离散数学?a∈[a]R ?[a]R ≠? ； (2) ?先证：aRb?[a]R = [b]R 为证[a]R = [b]R ，须证 (a) [a]R ?[b]R 对任何元素x∈ A ，有 x∈[a]R ? xRa ?xRa∧aRb (已知条件： aRb) ?xRb (R是等价关系，故R传递) ?x∈[b]R 所以 [a]R ? [b]R66离散数学(b) [b]R ? [a]R 对任何元素x∈ A ，有 x∈[b]R ? xRb ?xRb∧aRb (已知条件： aRb) ?xRb∧bRa (R是等价关系，故R对称) ?xRa ? (R是等价关系，故R传递) ? x∈[a]R 所以 [b]R ? [a]R 综合(a)和 (b)，即得 [b]R = [a]R ； ?次证： [a]R = [b]R ? aRb [a]R ≠? (本定理的(1)) ?(?x0∈A)(x0∈[a]R )67离散数学?(?x0∈A)(x0∈[a]R ∧ x0∈[b]R ) (已知条件：[a]R = [b]R ) ?(?x0∈A)(x0Ra∧x0Rb ) ?(?x0∈A)(aRx0∧x0Rb ) (R是等价关系，故R对称) ?aRb (R是等价关系，故R传递 且 ?xp?p ) (3)(3.1) [a]R∩[b]R≠? ?(?x0∈A)(x0∈[a]R ∩[b]R) ?(?x0∈A)(x0∈[a]R ∧ x0∈[b]R ) ?(?x0∈A)(x0Ra∧x0Rb ) ?(?x0∈A)(aRx0∧x0Rb ) (R是等价关系，故R对称) ?aRb (即 (a,b)∈R) (R是等价关系，故R传递 且 ?xp?p )68离散数学? [a]R = [b]R (本定理的(2)) ； (3.2) (整体采用反证法) 若(a,b)?R ，则 [a]R∩ [b]R = ? 。否则若 [a]R∩[b]R≠? ? [a]R = [b]R (本定理的(3.1)) ?aRb (本定理的(2)) ?(a,b)∈R ? ∈ 这就与已知条件：(a,b)?R 矛盾； (4)对任何序偶(a,b) (a,b)∈A×A ?(a,b)∈R∨(a,b)?R (二分法，互斥) ?([a]R = [b]R)∨([a]R∩ [b]R = ?) (本定理的(3.1)和(3.2)，互斥) 。69离散数学定义4. 定义4. 设R和S是非空集合A上的两个等价关系。若 R?S ，则我们称R细于S ，或S粗于R 。 例11.设A是一非空集。则 11. (1)A上最细的等价关系是幺关系；即 R细=IA ， A/R细={{a} : a∈A} ； (2)A上最粗的等价关系是全关系；即， R粗=A×A ，A/R粗={A} 。 定理2. 定理2.设R和S是非空集合A上的两个等价关系。则 2. R?S?(?a∈A)([a]R? [a]S) 。 [证].（采用逻辑法） ?先证：R?S? (?a∈A)([a]R? [a]S) 对任何元素a∈A ，有70离散数学对任何元素x∈A ，有 x∈ [a]R ? xRa ? xSa (已知条件：R?S) ? x∈[a]S 所以 [a]R? [a]S 所以(?a∈A)([a]R? [ ]S) ； ? ∈ [ ] [a] ?次证：(?a∈A)([a]R? [a]S)?R?S 对任何序偶(a,b)∈A×A (a,b)∈R ?aRb ?bRa (R是等价关系，故R对称) ?b∈[a]R71离散数学?b∈[a]S (已知条件：(?a∈A)([a]R? [a]S) ) ?bSa ?aSb (S是等价关系，故S对称) ? (a,b)∈S 所以 R ?S 。 定理3. 定理3.设R和S是非空集合A上的两个等价关系。则 3. R=S?(?a∈A)([a]R = [a]S) 。 [证].(采用逻辑法) R=S ?R?S∧S?R ? (?a∈A)([a]R ? [a]S)∧(?a∈A)([a]S ? [a]R) (定理2) ? (?a∈A)([a]R ? [a]S∧[a]S ? [a]R) (?量词对∧的分配律：72离散数学?x(A(x)∧?xB(x) ? ?x(A(x)∧B(x)) ) ?(?a∈A)([a]R = [a]S) 。注：?由定理2知，若两个等价关系相等，则每个元素所对应的等价 类也相同；若两个等价关系的等价类集合相等，则两个等价关系相 同。 ?由定理3知，等价关系与等价类集合一一对应。即相同的等价 关系对应着相同的等价类集合，不同的等价关系对应着不同的等价 类集合。2°划分与等价关系 ° 定义5. 定义5.覆盖 划分(covering partition) 5. 设A是一非空集合。则A的 (1)覆盖是一集合之集 Π={Aγ : γ∈Γ∧Aγ≠?}，满足条 件：73离散数学A ? γU Aγ ； ∈Γ (2)划分是一集合之集 Π={Aγ : γ∈Γ∧Aγ≠?}，满足条 件： (a) A = γU Aγ ； ∈Γ (b)γ1≠γ2?Aγ1∩Aγ2 = ? ； 其中Aγ称为划分Π的划分块(block of partition)。注：?由划分和覆盖的定义可知，A上的划分一定是A上的覆盖；反 之则未必。 。定理4 定理 。设R是非空集合A上的等价关系。则R的等价类 之集 ΠR = { [a]R : a∈A } 是A上的一个划分；等价类就是划分块。 [证].定理1的(1)不但直接给出等价类的非空性，而且74离散数学由它可得等价类满足划分的条件(a) ；定理1的(4)直接 给出等价类满足划分的条件(b)(详细叙述留给学者)。注：?定理4表明:由集合A上的等价关系R所产生的等价类之集构成 集合A 上的一个划分。定理5. 定理 设 Π={Aγ : γ∈Γ∧Aγ≠? }是非空集合A上的一个划 分。我们借助Π来定义A上的二元关系 RΠ ? A×A ，使 得 RΠ ={(a,b) : (?γ∈Γ )(a∈A γ ∧ b∈A γ)} 则RΠ是A上的等价关系。我们称为是由划分Π产生的(或 者说是诱导出的)A上的等价关系。 [证].(采用逻辑法) (1)自反性： 对任何元素a，有75离散数学a∈ A ?a∈ U Aγ (划分的条件(a)；A= U Aγ ) γ ∈Γ γ ∈Γ ?(?γ∈Γ)(a∈A γ ) ?(?γ∈Γ)(a∈A γ ∧ a∈A γ ) (幂等律：p? p∧p ) ?(a,a)∈RΠ ?aRΠ a 所以RΠ是自反的； (2)对称性： 对任何元素a,b∈A ，有 aRΠ b ?(a,b)∈RΠ ?(?γ∈Γ)(a∈A γ ∧b∈A γ ) ?(?γ∈Γ)(b∈A γ ∧ a∈A γ ) (交换律：p∧q?q∧p )76离散数学?(b,a)∈RΠ ? bRΠ a 所以RΠ是对称的； (3)传递性： 对任何元素a,b,c∈A ，有 aRΠ b∧bRΠ c ?(a,b)∈RΠ ∧ ? ∈ ∧(b,c)∈RΠ ∈ ?(?γ1∈Γ)(a∈Aγ1∧b∈Aγ 1)∧(?γ2∈Γ)(b∈Aγ2∧c∈Aγ2) ?(?γ∈Γ)(a∈A γ ∧ b∈A γ ∧ b∈A γ ∧ c∈A γ ) (由划分的条件(b)的逆否，有 Aγ1∩Aγ2?{b}≠? ? γ1=γ2= γ ) ?(?γ∈Γ)(a∈A γ ∧ b∈A γ ∧ c∈A γ ) (幂等律：p∧p ? p )77离散数学?(?γ∈Γ)(a∈A γ ∧ c∈A γ ) ?(a,c)∈RΠ ? aRΠ c 所以RΠ是传递的； 所以RΠ是等价的。 (合取分析式：p∧q?p )注：?定理5表明:由集合A上的划分Π可产生A上的一个等价关系； 划分块就是等价类。定理6。 定理 。设R是非空集合Ａ上的等价关系， Π是A上的一 个划分。那么 R= RΠ ? ΠR = Π 。注：? RΠ是由划分Π所产生的A上的一个等价关系； ? ΠR是由等价关系R所产生A上的一个的划分；78离散数学[证]. (采用逻辑法) ?先证： R= RΠ ? ΠR = Π 对任何元素a∈A ，有 对任何元素x∈A ，有 x∈[a]R ? xRa ? xRΠa (已知条件： R= RΠ ) ? x∈[a]R 所以 [a]R=[a]R 所以 (?a∈A)([a]R=[a]R ) 所以 ΠR ={[a]R : a∈A }={[a]R : a∈A }= Π ； ?次证： ΠR = Π? R= RΠ 对任何序偶(a,b)∈A×A (a,b)∈RΠ Π Π Π79离散数学?aRb ?bRa (R是等价关系，故R对称) ?b∈[a]R ?b∈[a]R (已知条件：ΠR = Π?(?a∈A)([a]R=[a]R ) ) ?bRΠ a ?aR ? Πb (RΠ是等价关系，故RΠ对称) ?(a,b)∈RΠ 所以 R= RΠ 。Π Π注：?由定理4,5,6可知：由等价关系可以产生一个划分，由划分可 以产生一个等价关系； ?划分与等价关系是一一对应的。即每个划分对应一个等价关 系，且每个等价关系对应一个划分。80离散数学§6. 半序关系定义1. 定义1.半序关系(partial order relation) 1. 设二元关系R? A×A。这里A是非空的集合。 R是A上的半序关系?R是自反的、反对称的、传递的。 ?显然 ?(R) = ?(R) = A (因为半序关系是自反的)； ?通常，半序关系R记为? ，称系统(A, ?)为半序集 (poset)。 例1.自然数集N、整数集I、有理数集Q 、实数集R上的 1. 小于等于关系‘ ≤ ’都分别是这些数集上的半序关系； 因为，对任何数a,b,c a ≤a ； a ≤b ∧ b ≤a ? a=b ； a ≤b ∧ b ≤c ? a ≤c ；81离散数学所以(N, ≤) ,(I , ≤) , (Q, ≤) , (R, ≤) 都是半序集。 例2.集合X的幂集2x上的包含关系‘?’是其上的半序关 系；因为对任何子集A,B,C A?A； A ? B ∧ B ? A ? A=B ； A?B∧B?C?A?C； 故(2x, ?) 是半序集。 例3. 自然数集N、整数集I、有理数集Q 、实数集R上的 小于关系‘ & ’都不是这些数集上的半序关系；因为， & 不是自反关系，即对任何数a, a ≮a ；故& 是反自反 关系。注：一般我们定义：拟序(quasi order) ?二元关系R? A×A(A≠?) 是A上的拟序关系?R是反自反的、82离散数学传递的。拟序一般记作?，称系统(A, ?)为拟序集； ?拟序与半序的关系是：对任何元素a,b∈A a?b?a?b ∧a≠b ； 因此，小于关系& 是拟序； (N, & ) ,(I , & ) , (Q, & ) , (R, & ) 都是拟 序集。例4.集合X的幂集2x上的真包含关系‘?’不是其上的半 序关系；因为， ?不是自反关系，即对任何子集A,A?A ； 故?是反自反关系注：因此，真包含关系?是拟序； (2x, ?) 是拟序集。定义2.可比较性(comparability) 定义 设(A, ?)是一半序集，a与b是A中的一对元素。我们称 a与b是可比较的 ? a ? b ∨ b ? a 。83离散数学注： ?否则，若a ? b∧b ? a ，则称a与b是不可比较的； ? ? ?半序关系?实际上是在集合A上建立了一种比较关系；例5.对于小于等于关系‘ ≤ ’，任何二数a,b都是可比较 . 的；即总有 a ≤ b∨b ≤ a 。 例6.对于包含关系‘?’ ，任何二集合A,B不都是可比 . 较的；即不总是有 A ? B∨B ? A 。 定义3.全序关系 线性序 链(total order, linear order , chain) 定义 设(A, ?)是一半序集。 ?是A上的全序关系? ?满足全可比较性： (?a∈A)(?b∈A)(a ? b ∨ b ? a) 。 这时，我们简称≤是全序或线性序；称(A, ?)是一全序 集。84离散数学注： ?否则，若(?a∈A)(?b∈A)(a ? b ∧ b ? a)，一般我们则称≤是非 ? ? 线性序(nonlinear order)； ?非线性序在实际中有很重要的作用；也是本课程的一个重要 研究对象。?字典序 字典序(lexicographic) 字典序 设(Σ, ≤)是一全序集。其中：Σ是一有限集，称为字母 表(alphabet)，任一元素a∈Σ称为字母(alpha)， ≤是字母 表中字母的自然顺序，则显然≤是一个全序。故此,则(Σ*, ≤*)是一全序集,我们称其为字典序。其中： Σ* ={Λ}∪Σ ∪Σ2 ∪Σ3 ∪…∪Σn ∪ … (Λ称为空字) 其任何元素 w∈Σ*称为一个字(word)；必有k∈N,使得 w ∈ Σk ，从而 w=(ai1,ai2,ai3,… ,aik)=ai1ai2 ai3 …aik 85 这里aij∈Σ (1 ≤ j ≤ k) 。离散数学我们定义二元关系≤* ? Σ* × Σ* ，使得； 对于任何二字w1=ai1ai2ai3…aim和w2=bi1bi2bi3…bin w1 ≤* w2当且仅当 下列三条之一成立： (1)ai1ai2ai3…aim=bi1bi2bi3…bin ；(这时：m=n, aij=bij ) (2)ai1≠bi1 且ai1≤bi1 ； (3)存在着某个k ∈N，1 ≤ k ≤min(m,n)，使得 ai1ai2ai3… ik-1=bi1bi2bi3… ik-1且aik≠ ik且aik≤ ik 。 …a …b ≠b ≤b 例7.小于等于关系‘ ≤ ’是全序关系；包含关系‘?’ 一般不是全序关系。 例8.(I , ≤) , (R, ≤) 都是全序集。但是在(I , ≤) 中每个整数， 下一个比它大的或比它小的（即紧挨着它的）那个数都 可确定；而在(R, ≤) 中却不可能。86离散数学定义3.直接后继 后继(direct successor, successor) 定义 设(A, ?)是一半序集，a与b是A中的一对元素。我们称 b是a的直接后继?a≠b∧a ? b∧(?t∈A)(a ? t∧t ? b?t=a∨t=b) 直接后继简称后继； a的后继记作a+，即b= a+ ，这时称a 是b的前驱或前趋(predecessor)。 例9. (Nm, ≤) , (N, ≤) ,(I , ≤) , (R, ≤) 都是全序集。这里≤ 都 是数的小于等于关系；而 Nm={0,1,2,…,m-1}。于是 (Nm, ≤)除尾元素m-1外，每个元素都有后继；除首元 素0外，每个元素都有前驱； (N, ≤)的每个元素都有后继；除首元素0外，每个元素 都有前驱； (I, ≤)的每个元素都有后继；每个元素都有前驱； (R, ≤)的每个元素都没有后继；每个元素都没有前驱。87离散数学?半序集的表示法 半序集的表示法――哈斯图 哈斯图(Hasse) 半序集的表示法 哈斯图 通常用Hasse图表示半序关系。半序集(A, ?)的Hasse 图是一个图 G ? =(V ? ,E ?) 其中： V ? = A 是结点集； E ? ={(a,b) : a∈A∧b∈A∧a ? b∧b= a+}是边集。 在画法上,我们规定： (1)结点a+必须画在结点a 的紧(斜)上方； {a,b,c} (2)不画边的方向。注：与关系图相比， Hasse图 ?省略了自反性的边(圈)； ?省略了(反对称性)方向； ?省略了传递性的边； {a,b} {a} {a,c} {b} { } 例10 {b,c} {c}例10. 设A ={a,b,c},88离散数学2A={?,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} 由于2A上的包含关系?是自反的、反对称的、传递的， 故包含关系?是2A上的半序关系，(2A, ?) 是半序集。 2A上的包含关系?的Hasse图如上图所示。注：从上例可以看出： ?在非线性半序集中，直接后继一般不唯一； ?其Hasse图呈现网格状；其实正是这点导致一门现代数学的重要 ? 学科――格论的出现；而此例正好给人们形象、直观的展现出布尔 代数(用其三大特例之一――集合代数来表现)的内部数学结构。例11. 设A = {2,3,4,6,7,8,12,36,60}， R ={(a,b):a∈A∧b∈A∧a | b}，即，R是A上的整除关系。 由整除的性质知R是自反的、反对称的、传递的。 由半序关系的定义知R是A上的半序关系。89离散数学R的Hasse图如下图左：60 36 8 7 24 3612 6 412632例112例123例12. 设A ={2,3,6,12,24,36},R={(a,b):a∈A∧b∈A∧a | b} R是A上的整除关系。 由整除的性质知R是自反的、反对称的、传递的。 由半序关系的定义知R是A上的半序关系。 R的Hasse图如上图右：90离散数学注：从以上两例可以看出： ?虽然同为整除关系，但由于集合不同，其Hasse图就呈现出明 显的不同；这说明两例中的半序集是不同的；所以，在论及半序关 系时，重要的是一定要指明其是那个集合上的半序关系；半序集是 一个整体，不能分而论之。定义4。 定义 。最大元 最小元(greatest element,least element) 设(A, ?)是半序集，B?A ，x0 ∈B 。则我们称 (1)x0是B的最大元?(?x∈B)(x ? x0) ； (2)x0是B的最小元?(?x∈B)(x0 ? x) 。注：?最大(小)元一般未必一定存在；即使B(甚或A)是有限集合也 未必； ? B的最大(小)元若存在，则一定在B中；91离散数学定理1. 定理 设(A, ?)是半序集,B?A。若B有最大(小)元，则 必是唯一的。 [证].（采用逻辑法）只证最大元的唯一性 x01是B的最大元 ∧ x02是B的最大元 ?(?x∈B)(x ? x01)∧(?x∈B)(x ? x02), ?x02 ? x01∧x01 ? x02 (因x01 , x02∈B又都是B的普通一元；根据 普遍性特殊化：?xA(x) ?A(y)；以及 合成律：(p → q )∧( r→s )? p ∧ r → q ∧ s ) ?x01=x02 (?是半序关系，故有反对称性) 所以， B的最大元是唯一的。 定义5.极大元 极小元 定义 (maximum element,minimal element)92离散数学设(A, ?)是半序集，B?A ， x0 ∈B 。则我们称 (1)x0是B的一个极大元 ??(?x∈B)(x0 ? x∧x ≠ x0) ??(?x∈B)(x0 ? x) ； (2)x0是B的一个极小元 ??(?x∈B)(x ? x0 ∧x ≠ x0)??(?x∈B)(x ? x0) 。注：?极大(小)元一般不一定存在；但在B(或A)是有限集合时一定 存在； ?极大(小)元即使存在，一般也是不唯一的； ? B的极大(小)元若存在，则一定在B中。定义6.上界 下界(upper bound,lower bound) 定义 设(A, ?)是半序集，B?A ， z0 ∈A 。则我们称 (1)z0是B的一个上界?(?x∈B)(x ? z0) ；93离散数学(2)z0是B的一个下界?(?x∈B)(z0 ? x) ； (3)若B有一个上界，则称B上方有界； 若B有一个下界，则称B下方有界； 若B上、下方都有界，则称B有界。注：?上界、下界、界一般不一定存在； ? B(或A)有限不一定有上界、下界、界；有上界、下界、界 B(或A)也不一定有限； ?上界、下界、界即使存在，一般也是不唯一的； ? B的上界、下界、界若存在，可以在B中，也可以不在B中。例13. (R, ≤) 是全序集。取B=(0,1)={x : x∈R∧0&x&1} ?R。 于是， B有无穷个上界，无穷个下界；从而B是有界 集。 但是B却不是有限集，而是一个无限集。94离散数学定义7.上确界 下确界 定义 (least upper bound,greatest lower bound) 设(A, ?)是半序集，B?A ， z0 ∈A 。则我们称 (1)z0是B的上确界 ?(?x∈B)(x ? z0)∧(?z∈A)((?x∈B)(x ? z) ? z0 ? z) ； (2)z0是B的下确界 ?(?x∈B)(z0 ? x)∧(?z∈A)((?x∈B)(z ? x) ? z ? z0) ； (3)上确界即是最小上界，记为LUB(B)； 下确界即是最大下界，记为GLB(B)。注：?上(下)确界一般不一定存在；即使B(甚或A)是有限集合也未必； ? B的上(下)确界若存在，可以在B中，也可以不在B中；95离散数学例14.令：A={ ? 1411 ：n∈N∧n≥1} nB={ ：n∈N∧n≥1} n X=A∪B 则B中每个元素都是集合A的上界,但A无上确界,即 LUB(A) 不存在； A中每个元素都是集合B的下界,但B无下确界,即 GLB(B) 不存在。 定理2. 定理 设(A, ?)是半序集,B?A。若B有上(下)确界，则 必是唯一的。 [证].仿定理1可证。留给学者。96离散数学注：?最大(小)元一定是极大(小)元； 极大(小)元不一定是最大(小)元； 极大(小)元存在不一定有最大(小)元； ?最大(小)元一定是上(下)确界； 上(下)确界不一定是最大(小)元； 上(下)确界存在不一定有最大(小)元； ?上(下)确界一定是上(下)界； 上(下)界不一定是上(下)确界； 上(下)界存在不一定有上(下)确界； ?讨论B的上(下)确界的前提是B的上(下)界存在；例15. 设A={2,3,4,6,7,8,12,36,60}, R={(a,b) : a∈A∧b∈A∧a | b}, R是A上的整除关系。 于是根据前面例11可知 ，R是A上的半序关系。97离散数学其对应子集的各种性质 的元素 列为下表：60 36 8 7 12 6 432例14图集合 B1={8,12} B2={2,3} B3 ={7,8} B4 ={2,4,12} 最大元 最小元 极大元 极小元 无 无 无 12 无 无 无 2 8,12 2,3 7,8 12 8,12 2,3 7,8 2 上界 无 6,12,36,60 无 12,36,60 下界 上确界 下确界 2,4 无 无 2 无 6 无 12 4 无 无 298例14表离散数学?半序集的全序化 非线性序的线性化 半序集的全序化(非线性序的线性化 半序集的全序化 非线性序的线性化) 设(A, ≤)是一半序集，其中A={a1, a2, a3,… , an}。下面 的拓扑排序(分类)(A topological sort)算法是将半序集 (A,≤)整对(或者说转化)为一个全序集(A,Q)，并且满足 保序性： (?a∈A)(?b∈A)(a≤b? aQb) (也称为遗传性)。注： ?拓扑学主要是研究变化中的不变量； ?而这里，全序化是变化；遗传性是不变量。 ?拓扑排序(分类)算法： No.1 k ← 1； (设置计数器) No.2 在A中任取半序集(A, ≤)的一个极小元 aik ； No.3 若 k=n ，则算法停止；欲得之全序为： ai1 Q ai2 Q ai3 Q … Q aik Q … Q ain ； No.4 (否则k≠n) k ← k+1 ,A ←A\{aik} ；go to No.2 。 99离散数学注： ?拓扑排序算法所得之全序不是唯一的（因为极小元不唯一）； ?例如，在例14中的半序集就可被转化为如下的全序： 7，3，2，6，4，12，8，60，36 。 问题： ?有限半序集中一定有极小元吗？定义5下的注已经回答； ?半序集的子集和原序还构成半序集吗？回答参见习题35。定义8.良序集(well ordered set) 定义 设(A, ?)是半序集。则我们称 (A, ?)是良序集?A的每个非空子集都有最小元 ?(?B? A)(?x0∈B) (?x∈B)(x0 ? x) 。这时我们称半序(关系) ?是良序(关系)。 例16. (N, ≤)是良序集；而自然数集N上的小于等于关系100离散数学≤ 是良序关系。 (I , ≤) 虽是全序集，但却不是良序集；从而整数集I上 的小于等于关系 ≤ 不是良序关系。注：从上例我们可以得到 ?全序集未必一定是良序集；定理3. 定理 设(A, ?)是良序集。那么 (1) (A, ?)是全序集；(即，良序集一定是全序集) (2)对于任何元素a∈A，若a不是A的最大元，则a的直 接后继a+一定存在；即 (?a∈A)(?(?x∈A)(x ?a)? (?b∈A)(b= a+ ) ) 。101离散数学[证]. (采用构造法) (1)对于任二元素a,b∈A,构造一子集B={a,b}?A,显然B 是非空的，由(A, ?)是良序集，知B有最小元。 若a是B的最小元，那么有a ?b； 若b是B的最小元，那么有b ?a； 因此,总有a ?b∨b ?a 。即(?a∈A)(?b∈A)(a ?b∨b ?a),全 可比较性成立，所以， ?是全序，(A, ?)是全序 集。 (2)对于任何元素a∈A,且a不是A的最大元，构造一子集 B={x:x≠a∧a ?x}?A,显然B是非空的(因为 a不是A的最大元 (已知条件) ? ?(?x∈A)(x ?a) ?(?x∈A) ?(x ?a) (量词对偶律:??xA(x)??x?A(x)) ?(?x∈A)(a≠x∧a ?x) (因≤是全序) ?B≠? )102离散数学因此,由(A, ?)是良序集，知B有最小元。 设B的最小元为b，则我们可证a的直接后继a+ = b，总 是存在。 1由于b∈B，故此b≠a，且a ?b； 2对于任何元素t∈A,若a ?t且t ?b,那么(二分法) 或者t=a； 或者t≠a,则加上a ?t,可知t∈B,因此,由b是B的最小 元,得到b ?t,再加上假设t ?b,由?的反对称性,我们得到 t=b; 因此,总有t=a 或者t=b。 所以， b是a的直接后继，即a+ = b 。103离散数学[证]. (采用逻辑法) (1) (?B?A)(?x0∈B) (?x∈B)(x0 ? x) (因≤是良序) ?(?{a,b}?A)(?x0∈{a,b})(?x∈{a,b})(x0 ? x) (普遍性特殊化) ? (?{a,b}?A)(?x0∈{a,b})(x0 ? a∧x0 ?b) ? (?a∈A)(?b∈A)((a ?a∧a ?b)∨(b ?a∧b ?b)) ? (?a∈A)(?b∈A)(a ?b∨b ?a) (合取分析式：p∧q?p ) 所以≤是全序关系； (2) (?B?A)(?x0∈B) (?x∈B)(x0 ?x) (因≤是良序) ? (?B?A)(?x0∈A)(x0∈B∧(?x∈A)(x∈B? x0 ?x) (放大缩小法。注意： ?量词的特征谓词x0∈B作为合取项； ?量词的特征谓词x∈B作为蕴含条件) ? (?B?A)(?b∈A)(b∈B∧(?t∈A)(t∈B? b ?t)104离散数学(约束变项换名： ?xA(x)??yA(y) (x0换名为b)； ?xA(x)??yA(y) (x换名为t ) ) ?(?B1={x : x≠a ∧a≤x}?A) (?b∈A)(b∈B1∧(?t∈A)(t∈B1?b ?t) (普遍性特殊化) ( a不是最大元 (已知条件) ? ?(?x∈A)(x ?a) ?(?x∈A) ?(x ?a) (量词对偶律：??xA(x)??x?A(x) ) ?(?x∈A)(a≠x∧a ?x) (因?是全序) ?B1≠? ) ? (?a∈A)(?b∈A)(b ≠a∧a ?b∧(?t∈A)(t ≠a ∧a ?t? b ?t) ( b∈B1?b ≠a∧a ?b )105离散数学? (?a∈A)(?b∈A)(b ≠a ∧a ?b∧ (?t∈A)(t ≠a ∧a ?t∧t ?b ? b ?t∧t ?b) (附加律：p→q ? p ∧ r → q ∧ r) ? (?a∈A)(?b∈A)(b ≠a∧a ?b∧ (?t∈A)(t ≠a∧a ?t∧t ?b ? t=b) (?是良序，故?是反对称的) ? (?a∈A)(?b∈A)(b ≠a ∧a ?b∧ (?t∈A)(a ?t∧t ?b ? t =a∨t=b) (相容(析取)排斥法： ? r ∧p →q ? p → r ∨ q ) ?(?a∈A)(?b∈A)(b= a+ )106离散数学作业 第二章P491.2)4) 3. 4 .1)3)5) 6. 7.1)改?为? 2) 9. 10.求R1, R3, R5, R7 11.1)3)5) 13. 15. 17.2)4) 18.2) 19.1)2)3) 20.1)2)3) 23.1)2) 25.2)4) 26.2)4) 28. 30.2)4) 31.3) 32. 34. 35. 36.1)3) 37.1)2)3)107离散数学第二章 关系到此已经结束！ 谢谢读者收看！ 作者：刘国荣108
离散数学第二章 离散数学 2.1 等值式 一、等值式的概念 两公式什么时候代表...从 A 出发,证到 B;从 B 出 C,由于等值关系有传递性和对称性,故 A | ...数学离&#8203;散&#8203;数&#8203;学&#8203;文&#8203;档&#8203;第&#8203;二&#8203;章 暂无评价|0人阅读|0...2.1.2 举例 [例 2.1.2] 设 D 为实数域,E(x,y)表示 D 上关系“x ...离散数学第二章_工学_高等教育_教育专区。离散数学第二章逻辑与推理密切相关, ...词的性质或个体词之间关系的词。如: 小李是程序员, 小李是程序员, 2 是整数...离散数学要求知识点_电脑基础知识_IT/计算机_专业资料。离散数学要求知识点:第一章 1、幂集的计算; 2、二维笛卡尔积的计算。 第二章 1、关系的三种表示法; 2...离散数学 第二章 命题逻辑 (1)命题逻辑的基本概念:命题的概念、表示及其分类;...两个重要的关系:等价关系、偏序关系 等价关系:R 是集合 A 上的关系,当 R ...湖南大学离散数学习题解答湖南大学离散数学习题解答隐藏&& 第二章习题一 1、指出下列公式 ?x?y(F(x,y)∧G(y,z)) ∨?xH(x,y,z) 中的指导变元,量词的...离散数学复习笔记数理逻辑逻辑:以研究人的思维形式及思维规律为目的的一门学科 ...第二元素, 构成有序偶 第六章 关系 1、关系:任何有序偶的集合称为二元关系...2): 表示个体词之间的关系 如 L(x,y): x 与 y 有关系 L, L(x,y):...项及对应的指导变项,改成公式中未出现过的个体变项符 5 《离散数学》讲稿 ...《离散数学》期末复习提要 《离散数学》是中央电大“数学与数学应用专业” (本科...第二章 二元关系 [复习知识点] 1、关系、关系矩阵与关系图 2、复合关系与逆...离散数学_数学_自然科学_专业资料。第二章 集合概念及集合运算 -一.集合概念 ...C=A ? A ? (BUC)=(A ? B)U(A ? C) 第三章关系的概念和关系的运算...
All rights reserved Powered by
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。}