下载文档原格式
西北工业大学硕士研究生入学考试考研参考书目目代码考试科目参考书出版社作者21 1 翻译硕士英语《新编英语教程》（5-6册）上海外语教育出版社李观仪《现代大学英语》（5-6册）外语教学与研究出版社徐克容24 2 俄语（一外）《大学俄语》（1—2册全部）《大学俄语》（3册语法部分）外语教学与研究出版社北京外国语大学与莫斯科普希金俄语学院合编24 3 日语（一外）《中日交流标准日本语》初级上、下（新版）；中级上1-10课人民教育出版社目代码考试科目参考书出版社作者24 4 德语（一外）《大学德语教学大纲》高等教育出版社《大学德语》（1----3册）高等教育出版社张书良主编24 5 法语（一外）《法语》1-3册外语教学与研究出版社出版马晓宏等编《简明法语教程》1-42课商务印书馆出版孙辉编《大学法语》1-3册高教出版社出版李志清主编《大学法语简明教程》外语教学与研究出版社出版薛建成主编目代码考试科目参考书出版社作者24 6 英语（一外）《全国硕士研究生入学考试英语考试大纲（非英语专业）》大学英语教材《考硕词汇高效速记》王新国等35 7 英语翻译基础《英汉百科专名词典》商务印书馆赵苏苏新编英汉汉英翻译教程》-翻译技巧与误译评析北京大学出版社李青《实用翻译教程》（英汉互译增订本）上海外语教育出版社冯庆华目代码考试科目参考书出版社作者60 1 数学（理学）《高等数学》科学出版社，西北工业大学高等数学教材编写组编《线性代数》科学出版社，西北工业大学线性代数编写组编《高等数学常见题型解析及模拟题》西北工业大学出版社，陆全主编《线性代数辅导讲案》西北工业大学出版社，徐仲、张凯院主编60 2 数学分析《数学分析》科学出版社，1999李成章等《数学分析》高等教育出版社，1999陈记修等目代码考试科目参考书出版社作者《数学分析》（第三版）高等教育出版社，华东师范大学数学系44 8 汉语写作与百科知识《中国文化导读》生活.读书.新知三联书店叶朗费振刚《中国文化读本》外语教学与研究出版社叶朗，朱良志《中华科学文明史》上海人民出版社（英）李约瑟原著，（英）罗南改编73 5 英语水平测试《英汉翻译教程》上海外语教育出版社 .1张培基《实用英汉翻译教程》外语教学与研究出版社.2申雨平。
方世昌离散数学第三版教材课件第3章二元关系（可编辑）方世昌离散数学第三版教材课件第3章二元关系31 基本概念32 关系的合成33 关系上的闭包运算34 次序关系35 等价关系和划分 31 基本概念311 关系关系的数学概念是建立在日常生活中关系的概念之上的让我们先看两个例子例31-1 设 A abcd 是某乒乓球队的男队员集合 B efg 是女队员集合如果A和B元素之间有混双配对关系的是a 和gd和e我们可表达为 R 〈ag〉〈de〉这里R 表示具有混双配对关系的序偶集合所有可能具有混双配对关系的序偶集合是A×B 〈xy〉x∈A∧y∈B 〈ae〉〈af〉〈ag〉〈be〉〈bf〉〈bg〉〈ce〉〈cf〉〈cg〉〈de〉〈df〉〈dg〉例31-2 设学生集合A1 abcd 选修课集合A2 日语法语成绩等级集合A3 甲乙丙如果四人的选修内容及成绩如下 a 日乙 b 法甲c 日丙 d 法乙我们可表达为S 〈a 日乙〉〈b法甲〉〈c日丙〉〈d法乙〉这里S表示学生和选修课及成绩间的关系而可能出现的全部情况为A1×A2×A3 〈xyz〉x∈A1∧y∈A2∧z∈A3 〈a日甲〉〈a 日乙〉〈a日丙〉〈a法甲〉〈a 法乙〉〈a法丙〉〈b日甲〉〈b日乙〉〈b日丙〉〈b 法甲〉〈b法乙〉〈b法丙〉〈c日甲〉〈c日乙〉〈c日丙〉〈c法甲〉〈c法乙〉〈d法丙〉定〈c法丙〉〈d日甲〉〈d日乙〉〈d日丙〉〈d法甲〉〈d法乙〉义31―1 1 A×B的子集叫做A到B的一个二元关系2 A1×A2××An n≥1 的子集叫做A1×A2××An上的一个n元关系3 从定义可看出关系是一个集合所有定义集合的方法都可用来定义关系例31-1和例31-2是列举法的例子一个谓词Px1x2xn 可以定义一个n元关系R R 〈x1x2xn〉P x1x2xn 例如实数R上的二元关系＞可定义如下＞〈xy〉x∈R∧y∈R∧x＞y 反之一个n元关系也可定义一个谓词当n 1时R 〈x〉P x 称为一元关系它是一重组集合表示论述域上具有性质P的元素集合其意义与R xP x 相同仅记法不同而已例如设P x 表示x是质数论述域是N则质数集合可表示为〈x〉｜P x 或x｜P x 关系也可归纳地定义自然数上的小于关系可定义如下1 基础〈01〉∈＜2 归纳如果〈xy〉∈＜那么i 〈xy1〉∈＜ ii 〈x1y1〉∈＜ 3 极小性对一切xy∈Nx＜y当且仅当〈xy〉是由有限次应用条款 1 和 2 构成定义31―2 设R是的子集如果R 则称R为空关系如果则称R为全域关系现在定义关系相等的概念在关系相等的概念中不仅需要n重组集合相等还需其叉积扩集也相同定义31―3设R1 是上的n元关系R2是上的m元关系那么R1 R2当且仅当n m且对一切i1≤i≤nAi Bi并且R1和R2是相等的有序n重组集合 312 二元关系最重要的关系是二元关系本章主要讨论二元关系今后术语关系都指二元关系若非二元关系将用三元或n元一类术语指出二元关系有自己专用的记法和若干新术语设 A x1x2x7 B y1y2y6 R〈x3y1〉〈x3y2〉〈x4y4〉〈x6y2〉A到B的二元关系R可如图31―1那样形象地表示〈x3y1〉∈R也可写成x3Ry1称为中缀记法读做x3和y1有关系R中缀记法常用来表示诸如＜＞等关系例如〈35〉∈＜通常写作3＜5 A叫做关系R的前域B叫做关系R的陪域 D R x｜y 〈xy〉∈R 叫做关系R 的定义域R R y｜x 〈xy〉∈R 叫做关系R的值域关系是序偶的集合对它可进行集合运算运算结果定义一个新关系设R和S是给定集合上的两个二元关系则R∪SR∩SR-S 等可分别定义如下x R∪S y xRy∨xSy x R∩S y xRy∧xSy x R-S y xRy∧xy x y xRy 例31-3平面上的几何图形是平面R2的子集也是一种关系设参看图31―2 R1 〈xy〉｜〈xy〉∈R2∧x2y2≤9 R2 〈xy〉｜〈xy〉∈R2∧1≤x≤3 ∧0≤y≤3 R3 〈xy〉｜〈xy〉∈R2∧x2y2≥4 则R1∪R2 〈xy〉｜〈xy〉∈R2∧ x2y2 ≤9∨ 1≤x≤3∧0≤y≤3 R1∩R3〈xy〉｜〈xy〉∈R2∧ x2y2 ≤9∧x2y2≥4 R1-R3 〈xy〉｜〈xy〉∈R2∧ x2y2≤9∧ L x2y2≥4 〈xy〉｜〈xy〉∈R2∧ x2y2≥4 313 关系矩阵和关系图表达有限集合到有限集合的二元关系时矩阵是一有力工具定义31―4 给定集合A a1a2am 和B b1b2bn 及一个A 到B的二元关系R 使例31-4 设A a1a2 B b1b2b3 R 〈a1b1〉〈a2b1〉〈a1b3〉〈a2b2〉则其关系矩阵为例31-5 设A 1234 A上的二元关系R 〈xy〉｜x＞y 试求出关系矩阵解R 〈41〉〈42〉〈43〉〈31〉〈32〉〈21〉例31-6 设 A 12345 R 〈12〉〈22〉〈32〉〈34〉〈43〉其图示如图31―3所示图中结点5叫做孤立点利用关系R的图示也可写出关系R 314 关系的特性在研究各种二元关系中关系的某些特性扮演着重要角色我们将定义这些特性并给出它的图示和矩阵的特点定义31―5 设R是A上的二元关系 1如果对A中每一xxRx那么R是自反的即 A上的关系R是自反的x x∈A→xRx A 123 R1 〈11〉〈22〉〈33〉〈12〉是自反的其关系图和关系矩阵的特点如图31―4所示 2 如果对A中每一xxRx那么R是反自反的即 A上的关系R是反自反的 x x∈A→xRx 例如 A 123 R2 〈21〉〈13〉〈32〉是反自反的其关系图和关系矩阵的特点如图31―5所示有些关系既不是自反的又不是反自反的如图31―6 例如R3 〈11〉〈12〉〈32〉〈23〉〈33〉3 如果对每一xy∈AxRy蕴含着yRx那么R是对称的即A上的关系R 是对称的x y x∈A∧y∈A∧xRy→yRx 例如A 123 R4 〈12〉〈21〉〈13〉〈31〉〈11〉是对称的其关系图和关系矩阵的特点如图31―7所示 4 如果对每一xy∈AxRyyRx蕴含着x y那么R是反对称的即A上的关系R是反对称的x y x∈A∧y∈A∧xRy∧yRx→x y 例如A 123 R5 〈12〉〈23〉是反对称的其关系图和关系矩阵的特点如图31―8所示 5 如果对每一xyz∈AxRyyRz蕴含着xRz那么R是传递的即A上的关系R是传递的x y z x∈A∧y∈A∧z ∈A∧xRy∧yRz→xRz 例如A 1234R5 〈41〉〈43〉〈42〉〈32〉〈31〉〈21〉是传递的其关系图和关系矩阵如图31―10所示例31-7 1 任何集合上的相等关系是自反的对称的反对称的和传递的但不是反自反的 2 整数集合I上关系≤是自反的反对称的可传递的但不是反自反的和对称的关系＜是反自反的反对称的可传递的但不是自反的和对称的 3 设 ab 试考察上的下列关系 i 关系与有同样长度是自反的对称的可传递的但不是反自反的和反对称的 ii xRy当且仅当x是y的真词头这里R是反自反的反对称的可传递的但不是自反的和对称的 iii xRy当且仅当x的某真词头是y的一个真词尾这里R既不是自反的又不是反自反的因为aaRaa但abRab既不是对称的也不是反对称的并且不是传递的 4 非空集合上的空关系是反自反的对称的反对称的和传递的但不是自反的空集合上的空关系则是自反的反自反的对称的反对称的和可传递的 5 基数大于1的集合上的全域关系是自反的对称的和传递的但不是反自反的和反对称的例如图31―11所示的关系 321 关系的合成前边已经指出关系是序偶的集合因此可以进行集合运算本节介绍一种对关系来说更为重要的运算合成运算假设R1是A到B的关系R2是B到C的关系参看图32-1合成关系R1R2是一个A到C的关系如果在关系图上从a∈A到c∈C有一长度路径中弧的条数为2的路径其第一条弧属于R1其第二条弧属于R2那么〈ac〉∈R1R2合成关系R1R2就是由〈ac〉这样的序偶组成的集合其第一条弧属于R1其第二条弧属于R2那么〈ac〉∈R1R2合成关系R1R2就是由〈ac〉这样的序偶组成的集合定义32―1 设R1是从A到B的关系R2是从B到C的关系从A到C的合成关系记为R1R2定义为R1R2 〈ac〉｜a∈A∧c∈C∧b〔b∈B∧〈ab〉∈R1∧〈bc〉∈R2〕例32-11 如果R1是关系是的兄弟R2是关系是的父亲那么R1R2是关系是的叔伯R2R2是关系是的祖父 2 给定集合A 1234 B 234 C 123 设R是A到B的关系S是B到C的关系R 〈xy〉｜xy 6 〈24〉〈33〉〈42〉S 〈yz〉｜y-z 1 〈21〉〈32〉〈43〉则R·S 〈23〉〈32〉〈41〉如图32―2所示 3 设A 12345 R和S都是A上二元关系如果 R 〈12〉〈34〉〈22〉 S 〈42〉〈25〉〈31〉〈13〉则R·S 〈15〉〈32〉〈25〉S·R 〈42〉〈32〉〈14〉R·S ·R 〈32〉R· S·R 〈32〉R·R 〈12〉〈22〉S·S〈45〉〈33〉〈11〉 4 设R是A到B的二元关系IAIB分别是A 和B上的相等关系则IA·R R·IB R 5 如果关系R的值域与关系S的定义域的交集是空集则合成关系R·S是空关系下边介绍合成关系的性质定理32―1 设R1是从A到B的关系R2 和R3是从B到C的关系R4是从C到D的关系那么1 R1 R2∪R3 R1R2∪R1R3 2 R1 R2∩R3 R1R2∩R1R3 3 R2∪R3 R4 R2R4∪R3R4 4 R2∩R3 R4 R2R4∩R3R41 2 3 部分的证明留作练习我们仅证明 2 部分证先证明公式因为〈ac〉∈R1 R2∩R3 b〔〈ab〉∈R1∧〈bc〉∈R2∩R3 〕b 〔〈ab〉∈R1∧〈bc〉∈R2∧〈bc〉∈R3 〕b〔〈ab〉∈R1∧〈bc〉∈R2 ∧〈ab〉∈R1∧〈bc〉∈R3 〕b〔〈ab〉∈R1∧〈bc〉∈R2〕∧b〔〈ab〉∈R1∧〈bc〉∈R3〕〈ac〉∈R1R2∧〈ac〉∈R1R3 〈ac〉∈R1R2∩R1R3 即〈ac〉∈R1 R2∩R3 〈ac〉∈R1R2∩R1R3 所以R1 R2∩R3 R1R2∩R1R3 再证包含可能是真包含举反例证明如果 A a B b1b2b3 C c A到B的关系R1〈ab1〉〈ab2〉 B到C的关系R2 〈b1c〉〈b3c〉 B到C的关系R3〈b2c〉〈b3c〉那么R1 R2∩R3 R1R2∩R1R3 〈ac〉此时R1 R2∩R3 ≠R1R2∩R1R3证毕定理32―2 设R1R2和R3分别是从A到BB到C和C到D的关系那么 R1R2 R3 R1 R2R3 证先证 R1R2R3 R1 R2R3 设〈ad〉∈ R1R2 R3那么对某c∈C〈ac〉∈R1R2和〈cd〉∈R3因为〈ac〉∈R1R2存在b∈B使〈ab〉∈R1和〈bc〉∈R2因为〈bc〉∈R2和〈cd〉∈R3得〈bd〉∈R2R3所以〈ad〉∈R1 R2R3 这样就证明了 R1R2 R3 R1 R2R3 R1 R2R3 R1R2 R3的证明是类似的留给读者自证上述证明也可用等价序列表达 322 关系R的幂当R是A上的一个关系时R可与自身合成任意次而形成A上的一个新关系在这种情况下RR常表示为R2RRR表示为R3等等我们能归纳地定义这一符号如下定义32―2设R是集合A上的二元关系n∈N那么R的n次幂记为Rn定义如下 1R0是A上的相等关系R0 〈xx〉｜x∈A 2 Rn1 Rn·R 定理32―3 设R是A上的二元关系并设m和n是N的元素那么 1Rm·Rn Rmn 2 Rm n Rmn 可用归纳法证明请读者自证定理32―4 设｜A｜nR是集合A上的一个关系那么存在i和j使Ri Rj而0≤i＜j≤证A上的每一二元关系是A×A的子集因为｜A×A｜ n2｜ρ A×A ｜因此A上有个不同关系所以R的不同的幂不会超过个但序列R0R1 有项因此R的这些幂中至少有两个是相等的证毕定理32―5 设R是集合A上的一个二元关系若存在i和ji＜j 使Ri Rj记d j-i那么 1 对所有k≥0Rik Rjk 2 对所有km≥0Rimdk Rik 3 记S R0R1R2Rj-1 那么R的每一次幂是S 的元素即对n∈NRn∈S 证 1 和 2 部分用归纳法证明留作练习3 对于 c 设n∈N如果n＜j那么根据S的定义Rn∈S假设n≥j那么我们能将n表示为imdk这里k＜d根据 b 部分得Rn Rik因为ik＜j这证明了Rn∈S定理中的ij在实用时宜取最小的非负整数以保证S中无重复元素例32-2 设A abcd R 〈ab〉〈cb〉〈bc〉〈cd〉其关系图如图32―3所示则R0 〈aa〉〈bb〉〈cc〉〈dd〉 R2 〈ac〉〈bb〉〈bd〉〈cc〉R3〈ab〉〈ad〉〈bc〉〈cb〉〈cd〉R4 〈ac〉〈bb〉〈bd〉〈cc〉它们的关系图如图32―4所示由于R4 R2根据定理32―5 c 对所有n∈NRn∈ R0R1R2R3 可见不必再算了事实上易证R5 R3R6 R4 R2用归纳法可得R2n1 R3和R2n R2这里n≥1 323 合成关系的矩阵表达定理32―6 设X x1x2xm Y y1y2yn Z z1z2zp R是X到Y的关系MR 〔aij〕是m×n矩阵S是Y到Z的关系MS 〔bij〕是n×p矩阵则MR·S 〔cij〕MR·MS这里证因为如果存在某k使aik和bki都等于1则cij 1但aik和bkj都等于1意味着xiRyk和ykSzj所以xi R·S zj可见如此求得的MR·S确实表达了R·S的关系因此上述等式是正确的如果不仅存在一个k使aik和bki都是1此时cij仍为1只是从xi到zj不止一条长度为2的路径但等式仍然正确上段的论证已隐含了不止一个k的情况本定理说明合成关系矩阵可用关系矩阵布尔矩阵的乘法表达例32-3设X 12 Y abc Z αβ R 〈1a〉〈1b〉〈2c〉 S 〈aβ〉〈bβ〉则定理32―7 关系矩阵的乘法是可结合的证利用关系合成的可结合性证明MR·MS ·MT MR·S·MT M R·S ·T MR· S·T MR·MS·T MR· MS·MT 不仅合成关系可用关系矩阵表达而且关系的集合运算也可用关系矩阵表达设R和S是X到Y上的二元关系MR 〔aij〕MS 〔bij〕cij是运算后所得新关系之关系矩阵的元素则MR∩S MR∧MS cij aij∧bij MR∪S MR∨MS cij aij∨bij cij aij MR-S MR∧ cij aij∧ bij 331 逆关系在讨论闭包运算时要用到逆关系的概念因此我们先介绍逆关系定义33―1设R是从A到B的二元关系关系R的逆或叫R的逆关系记为是一从B到A的二元关系定义如下例33-11 I上的关系2 集合族上的关系的逆是关系3 空关系的逆是空关系4 B×A即A×B的全域关系的逆等于B×A的全域关系定理33―1设R是从A到B的关系而S是从B到C 的关系则定理33―2 设RR1和R2都是从A到B的二元关系那么下列各式成立 332 关系的闭包运算关系的闭包运算是关系上的一元运算它把给出的关系R扩充成一新关系R′使R′具有一定的性质且所进行的扩充又是最节约的定义33―2设R是A上的二元关系R的自反对称传递闭包是关系R′使i R′是自反的对称的传递的ii R′R iii 对任何自反的对称的传递的关系R〃如果R〃R那么R〃R′ R的自反对称和传递闭包分别记为r R s R和t R 由定义可以看出R的自反对称传递闭包是含有R并且具有自反对称传递性质的最小关系如果R已经是自反的对称的传递的那么具有该性质并含有R的最小关系就是R自身下一定理说明这一点定理33―4设R是集合A上的二元关系那么 a R是自反的当且仅当r R R b R是对称的当且仅当s R R c R是传递的当且仅当t R R 证 a 如果R是自反的那么R具有定义33―2对R′所要求的性质因此r R R反之如果r R R那么根据定义33―2的性质 i R是自反的b 和c 的证明是类似的略构造R的自反对称和传递闭包的方法就是给R补充必要的序偶使它具有所希望的特性下面我们用关系图来说明如何实现这一点定理33―5 设R是集合A上的二元关系那么r R R ∪E 这里E是A上相等关系在本节中均如此证设R′ R∪E显然R′是自反的且R′R余下只需证明最小性现假设R〃是A上的自反关系且R〃R因R〃是自反的所以R〃E又R〃R所以R〃R∪E R′这样定义33―2都满足所以R′ r R 证毕设G是集合A上二元关系R的关系图我们把G的所有弧都画成有来有往即如果有从a到b的弧那么也有从b到a的弧就得到了R的对称闭包的有向图下一定理体现了这一想法定理33―7 设R 是集合A上的二元关系那么例33-2 a 整数集合I 上的关系＜的自反闭包是≤对称闭包是关系≠传递闭包是关系＜自身b 整数集合I上的关系≤的自反闭包是自身对称闭包是全域关系传递闭包是自身 c E的自反闭包对称闭包和传递闭包都是E d ≠的自反闭包是全域关系对称闭包是≠≠的传递闭包是全域关系e 空关系的自反闭包是相等关系对称闭包和传递闭包是自身 f 设R是I上的关系xRy当且仅当y x1那么t R 是关系＜定理33―8设R是集合A上的二元关系这里A有n个元素那么证设〈xy〉∈t R 于是必存在最小的正整数k使〈xy〉∈Rk现证明k≤n若不然存在A的元素序列x a0a1a2ak-1ak y使xRa1a1Ra2ak-1Ry因k ＞na0a1ak中必有相同者不妨设ai aj0≤i＜j≤k于是xRa1a1Ra2ai-1RaiajRaj1ak-1Ry 成立即〈xy〉∈Rs这里s k- j-i但这与k是最小的假设矛盾于是k≤n又〈xy〉是任意的故定理得证例33-3 设A abcd R如图33―1 a 所示则t R R∪R2∪R3∪R4如图33―1 b 所示本例即是32-2 定理33―9 1 如果R是自反的那么s R 和t R 都是自反的 2 如果R是对称的那么r R 和t R 都是对称的 3 如果R 是传递的那么r R 是传递的定理33―10 设R是集合A上的二元关系那么 1 rs R sr R 2 rt R tr R 3 ts R st R 2 注意到ER RE R 和对一切n∈NEn E可得 34 次序关系 341 偏序集合定义34―1 如果集合A上的二元关系R是自反的反对称的和传递的那么称R为A上的偏序称序偶〈AR〉为偏序集合如果R是偏序〈AR〉常记为〈A ≤〉≤是偏序符号由于≤难以书写通常写作≤读做小于或等于因为小于或等于也是一种偏序故不会产生混乱R是偏序时aRb就记成a≤b 如果R是集合A上的偏序则R 也是A上的偏序如果用≤表示R 可用≥表示R〈A≤〉和〈A ≥〉都是偏序集合并互为对偶例34-1 1 〈I≤〉是偏序集合这里≤表示整数中的小于或等于关系2 〈ρ A 〉是偏序集合这里是集合间的包含关系 3 A 2468 D代表整除关系M代表整倍数关系则 D 〈22〉〈44〉〈66〉〈88〉〈24〉〈26〉〈28〉〈48〉M 〈22〉〈44〉〈66〉〈88〉〈42〉〈62〉〈82〉〈84〉〈AD〉〈AM〉都是偏序集合且互为对偶例2 a P 1234 〈P≤〉的哈斯图为图34―2 b A 236122436 〈A整除〉的哈斯图为图34―3 c A 1212 〈A整除〉的哈斯图为图34―4 定义34―2 设〈A≤〉是一偏序集合B是A的子集 a 元素b∈B是B的最大元素如果对每一元素x∈Bx≤b b 元素b∈B是B的最小元素如果对每一元素x∈Bb≤x 例3考虑在偏序整除下整数1到6的集合其哈斯图为图34―5 a 如果B 1236 那么1是B的最小元素6是B的最大元素 b 如果B 23 因为2和3互相不能整除那么B没有最小元素和最大元素c 如果B 4 那么4是B的最大元素也是B的最小元素定理34―1 设〈A≤〉是一偏序集合且B A如果B有最大最小元素那么它是唯一的证假设a和b 都是B的最大元素那么a≤b和b≤a从≤的反对称性得到a b当a和b都是B 的最小元素时证明是类似的定义34―3设〈A≤〉是一偏序集合B是A的子集 a 如果b∈B且B中不存在元素x使b≠x且b≤x那么元素b∈B叫做B的极大元素b 如果b∈B且B中不存在元素x使b≠x且x≤b那么元素b∈B 叫做B的极小元素定义34―4设〈A≤〉是一偏序集合B是A的子集a 如果对每一b∈Bb≤a那么元素a∈A叫做B的上界如果对每一b∈Ba≤b那么元素a∈A叫做B的下界 b 如果a是一上界并且对每一B的上界a′有a≤a′那么元素a∈A叫做B的最小上界记为lub如果a是一下界并且对每一B的下界a′有a′≤a那么元素a∈A叫做B的最大下界记为glb 例34-4 a 考虑偏序集合〈〈11〉〈10〉〈01〉〈00〉≤〉这里≤按〈 ab〉≤〈cd〉a≤c∧b≤d 规定其哈斯图如图34―6 如果B 〈10〉那么〈10〉是B的最小和最大元素也是B的极大和极小元素B的上界是〈10〉和〈11〉〈10〉是最小上界B的下界是〈00〉和〈10〉〈10〉是最大下界 b 考虑偏序集合〈I≤〉设B 2i｜i∈N那么B既没有最大元素和极大元素也没有上界和最小上界B的最小元素和极小元素是0B的下界集合是 i｜i∈I∧i≤0 0是最大下界 c 考虑在偏序集合〈256101530 整除〉其哈斯图如图34―7设B是全集合256101530 那么2和5都是B的极小元素但B没有最小元素集合B没有下界所以没有最大下界元素30是B的最大元素极大元素上界最小上界定理34―2 如果〈A≤〉是非空有限的偏序集合则A的极小大元素常存在最大下界和最小上界也可能存在或不存在但如果它们存在则是唯一的定理34―3 设〈A≤〉是偏序集合且B A 如果B的最小上界最大下界存在那么是唯一的下述定理描述了存在于诸特异元素之间的某些关系定理34―4 设〈A≤〉是偏序集合B是A的子集 a 如果b是B的最大元素那么b是B的极大元素 b 如果b是B的最大元素那么b是B的lub c 如果b是B的一个上界且b∈B那么b是B的最大元素证明可由最大元素极大元素和lub的定义直接得出故略去另外读者不难给出表达最小元素极小元素和glb间关系的定理 342 拟序集合定义34―5如果集合A上的二元关系R是传递的和反自反的那么R叫做A上的拟序〈AR〉称为拟序集合常借用符号＜表示拟序拟序是反对称的虽然定义中没有明确指出但容易证明这一点因为如果xRy和yRx由R的传递性得xRx但这与R的反自反性矛盾所以xRy∧yRx常假于是xRy∧yRx→x y常真即R是反对称的例34-5 a 实数集合中的＜是拟序关系 b 集合族中的真包含是拟序关系拟序集合和偏序集合是紧密相关的唯一区别是相等关系E下述定理将说明这一点定理34―5在集合A上 a 如果R是一拟序那么rR R∪E是偏序 b 如果R是一偏序那么R-E是一拟序 343线序集合和良序集合如果≤是一偏序或a≤b或b≤a我们说a和b 是可比较的偏序集合中的元素不一定都可比较所以叫偏序下面介绍的都是可比较的情况定义34―6在偏序集合〈A≤〉中如果每一ab∈A或者a ≤b或者b≤a那么≤叫做A上的线序或全序这时的序偶〈A≤〉叫做线序集合或链例34-6 a P a ab abc 〈P〉是线序集合其哈斯图如图34―8所示 b 〈I≤〉是线序集合其哈斯图不完全如图34―9所示 c 设S是区间套的集合〔0a ｜a∈R 则〈S〉是线序集合 d 〈 1236 整除〉不是线序集合如果A是多于一个元素的集合那么〈ρ A 〉不是线序集合定义34―7如果A上的二元关系R是一线序且A的每一非空子集都有一最小元素那么R叫做A上的良序序偶〈AR〉叫做良序集合定理34―6〈N≤〉是良序集合证我们必须证明N的每一非空子集S在关系≤之下都有一最小元素因为S非空所以在S中可以取一个数n显然S中所有不大于n的数形成非空集T S如果T有最小数那么这最小数就是S中的最小数但从0到n只有n1个自然数于是T中所含的数最多是n1个所以T有最小数因此定理成立例34-8 a 每一有限线序集合是良序的 b 线序集合〈I≤〉不是良序集合因为I的某些子集诸如I自身不包含最小元素 c 关系≤是实数R的线序但不是良序例如子集A 01〕无最小元素如果A中的a是最小元素那么也在A中而≤a且不相等这与假设a是线序关系≤下A的最小元素矛盾2 应用N上的良序定义出Nn上的良序例如n 2时N2上的次序关系可如下定义〈ab〉〈cd〉a＜c∨ a c∧b d 〈N2〉是良序集合关系严格小于可如下定义〈ab〉＜〈cd〉〈ab〉≤〈cd〉∧〈ab〉≠〈cd〉类似地应用I上的线序能定义出线序集合〈In≤〉 3 应用字母表∑上的线序可定义出∑上的通常叫词典序的线序定义34―8 设∑是一有限字母表指定了字母表序线序如果xy∈∑ a x是y的词头或 b x zu和y zv这里z∈∑是x和y的最长公共词头且在字母表序中u的第一个字符前于v的第一个字符那么x≤y≤叫做词典序4 由于〈N〉和有限线序集合都是良序集合可应用它们定义出∑上的一个良序通常叫标准序定义34―9设∑是一有限字母表指定了字母表序‖x‖表示x∈∑的长度如果xy∈∑ a ‖x‖＜‖y‖或b ‖x‖‖y‖且在∑的词典序中x前于y那么x≤y ≤叫做标准序不论在词典序和标准序下∑的每一元素都有直接后继者设∑ abc 且a≤b≤cx∈∑在标准序下xa和xb的直接后继者分别是xb和xc xc的直接后继者是ya这里y是x的直接后继者在词典序下x的直接后继者是xa 在标准序下 xb和xc的直接前趋分别是xa和xb xa的直接前趋是yc这里y是x的直接前趋在词典序下 xa的直接前趋是x非a结尾的串都无直接前趋例如babaab但有无限个前趋345 数学归纳法的推广前章我们把数学归纳法第一第二原理看作是自然数域上的一个推理规则本小节我们把它推广到一般的良序集合对任一个自然数n我们先取0如果n≠0取0的后继者1如果n≠1再取1的后继者2如此进行下去最终会得出n 给定一个良序集合如果对它的任一元素x我们先取该集合的最小元素m0如果x≠m0取m0的后继者m1如果x≠m1再取m1的后继者m2如此以往最终会得出x那么就称这样的良序集合是像自然数的例 8 1 设∑ ab 良序集合〈∑标准序〉是像自然数的因为定长的串的个数有限给定任一个串x在x之前的串的个数有限所以从∧开始反复取后继者终可得出x 2 良序集合〈N×N≤〉不像自然数这里≤按上一小节规定因为有许多元素没有直接前趋例如〈50〉就是这样因而有无限个元素前于〈50〉所以从〈00〉开始反复地取后继者不可能取得〈50〉像自然数的良序集合可以应用数学归纳法第一原理因为第一原理是建立在后继运算上而这种良序集合的每一元素都可通过重复地取后继者得到设m0是该良序集合〈S≤〉的最小元素S x 是元素x的后继者则推理规则如下对不像自然数的良序集合不能应用数学归纳法第一原理因为这种良序集合的有些元素不能由后继运算得到但对它可应用数学归纳法第二原理第二原理是建立在良序集合上的适用于一切良序集合设〈S≤〉是良序集合＜表示≤-E 即x＜y表示x≤y且x≠y 则推理规则如下下面证明良序集合上这个推理规则是有效的假设我们能证明前提例34-10〈Q≤〉是线序集合现说明在此线序集合中第二原理不是有效推理规则设谓词P x 表示x小于或等于5 i 当x≤5时 y〔y＜x→P y 〕是真P x 也真所以是真综合 i 和 ii 得在论述域Q上 x 〔 y y＜x→P y →P x 〕是真但结论x P x 是假这说明第二原理不能应用于线序集合〈Q≤〉 35 等价关系和划分 351 等价关系二元关系的另一重要类型是等价关系其定义如下定义35―1 如果集合A上的二元关系R是自反的对称的和传递的那么称R是等价关系设R是A上的等价关系abc是A的任意元素如果aRb 即〈ab〉∈R 通常我们记作a～b读做a等价于b 定义35―2 设k是一正整数而ab∈I如果对某整数ma-b m·k那么a 和b是模k等价写成a≡b modk 整数k叫做等价的模数定理35―1模k等价是任何集合A I上的等价关系证如果A 例35-1 c 已指出它是等价关系如果A≠则 i 自反的因为对任一aa-a 0·k得出a≡a modk ii 对称的因为a≡b mod k 时存在某m∈I使a-b m·k于是b-a-m·k 因此b≡a mod k iii 传递的设a≡b mod k 和b≡c mod k 那么存在m1m2∈I 使a-b m1k和b-c m2·k 将两等式两边相加得a-c m1m2 ·k所以a≡c mod k 例1 a 同学集合A abcdefgA中的关系R是住在同一房间这是等价关系因为 i 任一个人和自己同住一间具有自反性ii 若甲和乙同住一间则乙和甲也同住一间具有对称性iii 若甲和乙同住一间乙和丙同住一间则甲和丙也同住一间具有传递性现假设a 和b同住一间def同住一间c住一间则 R 〈aa〉〈ab〉〈ba〉〈bb〉〈cc〉〈dd〉〈ee〉〈ff〉〈de〉〈ed〉〈ef〉〈fe〉〈df〉〈fd〉其有向图如图35―1所示 b 数中的相等关系集合中的相等关系命题演算中的关系等都是等价关系 c 空集合中的二元关系R是等价关系因为i x x∈→xRx ii x y〔x∈∧y∈∧xRy→yRx〕iii x y z〔x∈∧y∈∧z∈∧xRy∧yRz→xRz〕都无义地真所以R是等价关系集合A上的全域关系R A×A是等价关系模数等价是整数域或其子集上的等价关系并且是等价关系中极为重要的一类定理 35-1 模k 等价是任何集合A I上的等价关系证如果A 例35-1 3 已指出它是等价关系如果A≠则 i 自反的因为对任一aa-a 0·k得出a≡a mod k ii 对称的因为a≡b modk 时存在某m∈I使a-b m·k于是b-a -m·k因此b≡a modk iii 传递的设a≡b modk 和b≡c modk 那么存在m1m2∈I 使a-b m1k和b-c m2·k将两等式两边相加得a-c m1m2 ·k所以a≡c modk 例35-2 a 若R是I上模4等价关系则〔0〕4 -8-4048 〔1〕4 -7-3159 〔2〕4 -6-22610 〔3〕4 -5-13711 b 若R是I上模2等价关系则〔0〕2 -4-2024 〔1〕2 -3-1135 每一集合中的数相互等价 c 时钟是按模12方式记数的设备13点钟和1点钟有相同的记数定义35―3 设R是集合A上等价关系对每一a∈Aa关于R 的等价类是集合x｜xRa 记为〔a〕R简记为〔a〕称a为等价类〔a〕的表示元素如果等价类个数有限则R的不同等价类的个数叫做R的秩否则秩是无限的对每一a∈A等价类〔a〕R非空因为a∈〔a〕R 例35-3 1 如图35―2设A abcdef R 〈aa〉〈bb〉〈cc〉〈ab〉〈ba〉〈ac〉〈ca〉〈bc〉〈cb〉〈dd〉〈ee〉〈de〉〈ed〉〈ff〉则等价关系R的等价类如下〔a〕〔b〕〔c〕 abc 〔d〕〔e〕 de 〔f〕 f等价关系R的秩是3 2 I上模4等价的等价类是〔0〕4〔1〕4〔2〕4〔3〕4 参看例2 a I上模2等价的等价类是〔0〕2 〔1〕2 参看例2 b3 集合A上相等关系的秩等于A的元素个数定理35―2 设R是非空集合A上的等价关系aRb 当且仅当〔a〕〔b〕证充分性因为a∈〔a〕〔b〕即a∈〔b〕所以aRb 定理35―3设R是集合A上的等价关系则对所有ab∈A或者〔a〕〔b〕或者〔a〕∩〔b〕。
方世昌离散数学第三版教材课件第3章二元关系31 基本概念 32 关系的合成 33 关系上的闭包运算 34 次序关系 35 等价关系和划分 31 基本概念311 关系关系的数学概念是建立在日常生活中关系的概念之上的让我们先看两个例子例31-1 设 A abcd 是某乒乓球队的男队员集合 B efg 是女队员集合如果A和B元素之间有混双配对关系的是a 和gd和e我们可表达为 R 〈ag〉〈de〉这里R表示具有混双配对关系的序偶集合所有可能具有混双配对关系的序偶集合是 A×B 〈xy〉x∈A∧y∈B 〈ae〉〈af〉〈ag〉〈be〉〈bf〉〈bg〉〈ce〉〈cf〉〈cg〉〈de〉〈df〉〈dg〉例31-2 设学生集合A1 abcd 选修课集合A2 日语法语成绩等级集合A3 甲乙丙如果四人的选修内容及成绩如下 a 日乙 b 法甲c 日丙 d 法乙我们可表达为S 〈a日乙〉〈b法甲〉〈c日丙〉〈d法乙〉这里S表示学生和选修课及成绩间的关系而可能出现的全部情况为 A1×A2×A3 〈xyz〉x∈A1∧y∈A2∧z∈A3 〈a日甲〉〈a 日乙〉〈a日丙〉〈a法甲〉〈a法乙〉〈a法丙〉〈b日甲〉〈b日乙〉〈b日丙〉〈b 法甲〉〈b法乙〉〈b法丙〉〈c日甲〉〈c日乙〉〈c日丙〉〈c法甲〉〈c法乙〉〈d法丙〉定〈c法丙〉〈d日甲〉〈d日乙〉〈d日丙〉〈d法甲〉〈d法乙〉义31―1 1 A×B的子集叫做A到B的一个二元关系2 A1×A2××An n≥1 的子集叫做A1×A2××An上的一个n元关系3 从定义可看出关系是一个集合所有定义集合的方法都可用来定义关系例31-1和例31-2是列举法的例子一个谓词Px1x2xn 可以定义一个n元关系R R 〈x1x2xn〉P x1x2xn 例如实数R上的二元关系＞可定义如下＞〈xy〉x∈R∧y∈R∧x＞y 反之一个n元关系也可定义一个谓词当n 1时R 〈x〉P x 称为一元关系它是一重组集合表示论述域上具有性质P的元素集合其意义与R xP x 相同仅记法不同而已例如设P x 表示x是质数论述域是N则质数集合可表示为〈x〉｜P x 或x｜P x 关系也可归纳地定义自然数上的小于关系可定义如下1 基础〈01〉∈＜2 归纳如果〈xy〉∈＜那么i 〈xy1〉∈＜ ii 〈x1y1〉∈＜ 3 极小性对一切xy∈Nx＜y当且仅当〈xy〉是由有限次应用条款 1 和 2 构成定义31―2 设R是的子集如果R 则称R为空关系如果则称R为全域关系现在定义关系相等的概念在关系相等的概念中不仅需要n重组集合相等还需其叉积扩集也相同定义31―3设R1是上的n元关系R2是上的m元关系那么R1 R2当且仅当n m且对一切i1≤i≤nAi Bi并且R1和R2是相等的有序n重组集合 312 二元关系最重要的关系是二元关系本章主要讨论二元关系今后术语关系都指二元关系若非二元关系将用三元或n元一类术语指出二元关系有自己专用的记法和若干新术语设 A x1x2x7 B y1y2y6 R〈x3y1〉〈x3y2〉〈x4y4〉〈x6y2〉 A到B的二元关系R可如图31―1那样形象地表示〈x3y1〉∈R也可写成x3Ry1称为中缀记法读做x3和y1有关系R中缀记法常用来表示诸如＜＞等关系例如〈35〉∈＜通常写作3＜5 A叫做关系R的前域B叫做关系R的陪域 D R x｜y 〈xy〉∈R 叫做关系R的定义域R R y｜x 〈xy〉∈R 叫做关系R的值域关系是序偶的集合对它可进行集合运算运算结果定义一个新关系设R和S是给定集合上的两个二元关系则R∪SR∩SR-S 等可分别定义如下x R∪S y xRy∨xSy x R∩S y xRy∧xSy x R-S y xRy∧xy x y xRy 例31-3平面上的几何图形是平面R2的子集也是一种关系设参看图31―2 R1 〈xy〉｜〈xy〉∈R2∧x2y2≤9 R2 〈xy〉｜〈xy〉∈R2∧1≤x≤3 ∧0≤y≤3 R3 〈xy〉｜〈xy〉∈R2∧x2y2≥4 则 R1∪R2 〈xy〉｜〈xy〉∈R2∧ x2y2 ≤9∨ 1≤x≤3∧0≤y≤3 R1∩R3〈xy〉｜〈xy〉∈R2∧ x2y2 ≤9∧x2y2≥4 R1-R3 〈xy〉｜〈xy〉∈R2∧ x2y2≤9∧ L x2y2≥4 〈xy〉｜〈xy〉∈R2∧ x2y2≥4 313 关系矩阵和关系图表达有限集合到有限集合的二元关系时矩阵是一有力工具定义31―4 给定集合A a1a2am 和B b1b2bn 及一个A到B的二元关系R 使例31-4 设A a1a2 B b1b2b3 R 〈a1b1〉〈a2b1〉〈a1b3〉〈a2b2〉则其关系矩阵为例31-5 设A 1234 A上的二元关系R 〈xy〉｜x＞y 试求出关系矩阵解R 〈41〉〈42〉〈43〉〈31〉〈32〉〈21〉例31-6 设 A 12345 R 〈12〉〈22〉〈32〉〈34〉〈43〉其图示如图31―3所示图中结点5叫做孤立点利用关系R的图示也可写出关系R 314 关系的特性在研究各种二元关系中关系的某些特性扮演着重要角色我们将定义这些特性并给出它的图示和矩阵的特点定义31―5 设R是A上的二元关系 1如果对A中每一xxRx那么R是自反的即 A上的关系R是自反的x x∈A→xRx A 123 R1 〈11〉〈22〉〈33〉〈12〉是自反的其关系图和关系矩阵的特点如图31―4所示 2 如果对A中每一xxRx那么R是反自反的即 A上的关系R是反自反的 x x∈A→xRx 例如 A 123 R2 〈21〉〈13〉〈32〉是反自反的其关系图和关系矩阵的特点如图31―5所示有些关系既不是自反的又不是反自反的如图31―6 例如R3 〈11〉〈12〉〈32〉〈23〉〈33〉 3 如果对每一xy∈AxRy蕴含着yRx那么R是对称的即A上的关系R是对称的x y x∈A∧y∈A∧xRy→yRx 例如A 123 R4 〈12〉〈21〉〈13〉〈31〉〈11〉是对称的其关系图和关系矩阵的特点如图31―7所示 4 如果对每一xy∈AxRyyRx蕴含着x y那么R是反对称的即A上的关系R是反对称的x y x∈A∧y∈A∧xRy∧yRx→x y 例如A 123 R5 〈12〉〈23〉是反对称的其关系图和关系矩阵的特点如图31―8所示 5 如果对每一xyz∈AxRyyRz蕴含着xRz那么R是传递的即A上的关系R是传递的x y z x∈A∧y∈A∧z ∈A∧xRy∧yRz→xRz 例如A 1234R5 〈41〉〈43〉〈42〉〈32〉〈31〉〈21〉是传递的其关系图和关系矩阵如图31―10所示例31-7 1 任何集合上的相等关系是自反的对称的反对称的和传递的但不是反自反的 2 整数集合I上关系≤是自反的反对称的可传递的但不是反自反的和对称的关系＜是反自反的反对称的可传递的但不是自反的和对称的 3 设 ab 试考察上的下列关系 i 关系与有同样长度是自反的对称的可传递的但不是反自反的和反对称的 ii xRy当且仅当x是y的真词头这里R是反自反的反对称的可传递的但不是自反的和对称的 iii xRy当且仅当x的某真词头是y的一个真词尾这里R既不是自反的又不是反自反的因为aaRaa但abRab既不是对称的也不是反对称的并且不是传递的 4 非空集合上的空关系是反自反的对称的反对称的和传递的但不是自反的空集合上的空关系则是自反的反自反的对称的反对称的和可传递的 5 基数大于1的集合上的全域关系是自反的对称的和传递的但不是反自反的和反对称的例如图31―11所示的关系 321 关系的合成前边已经指出关系是序偶的集合因此可以进行集合运算本节介绍一种对关系来说更为重要的运算合成运算假设R1是A到B的关系R2是B到C的关系参看图32-1合成关系R1R2是一个A到C的关系如果在关系图上从a∈A到c∈C有一长度路径中弧的条数为2的路径其第一条弧属于R1其第二条弧属于R2那么〈ac〉∈R1R2合成关系R1R2就是由〈ac〉这样的序偶组成的集合其第一条弧属于R1其第二条弧属于R2那么〈ac〉∈R1R2合成关系R1R2就是由〈ac〉这样的序偶组成的集合定义32―1 设R1是从A到B的关系R2是从B到C的关系从A到C的合成关系记为R1R2定义为 R1R2 〈ac〉｜a∈A∧c∈C∧b〔b∈B∧〈ab〉∈R1∧〈bc〉∈R2〕例32-11 如果R1是关系是的兄弟R2是关系是的父亲那么R1R2是关系是的叔伯R2R2是关系是的祖父 2 给定集合A 1234 B 234 C 123 设R是A到B的关系S是B到C的关系 R 〈xy〉｜xy 6 〈24〉〈33〉〈42〉S 〈yz〉｜y-z 1 〈21〉〈32〉〈43〉则R·S 〈23〉〈32〉〈41〉如图32―2所示 3 设A 12345 R和S都是A上二元关系如果 R 〈12〉〈34〉〈22〉 S 〈42〉〈25〉〈31〉〈13〉则R·S 〈15〉〈32〉〈25〉 S·R 〈42〉〈32〉〈14〉 R·S ·R 〈32〉 R· S·R 〈32〉 R·R 〈12〉〈22〉 S·S〈45〉〈33〉〈11〉 4 设R是A到B的二元关系IAIB分别是A和B上的相等关系则IA·R R·IB R 5 如果关系R的值域与关系S的定义域的交集是空集则合成关系R·S是空关系下边介绍合成关系的性质定理32―1 设R1是从A到B的关系R2和R3是从B到C的关系R4是从C到D的关系那么 1 R1 R2∪R3 R1R2∪R1R3 2 R1 R2∩R3 R1R2∩R1R3 3 R2∪R3 R4 R2R4∪R3R4 4 R2∩R3 R4 R2R4∩R3R41 2 3 部分的证明留作练习我们仅证明 2 部分证先证明公式因为〈ac〉∈R1 R2∩R3 b〔〈ab〉∈R1∧〈bc〉∈R2∩R3 〕b〔〈ab〉∈R1∧〈bc〉∈R2∧〈bc〉∈R3 〕b〔〈ab〉∈R1∧〈bc〉∈R2 ∧〈ab〉∈R1∧〈bc〉∈R3 〕b〔〈ab〉∈R1∧〈bc〉∈R2〕∧b〔〈ab〉∈R1∧〈bc〉∈R3〕〈ac〉∈R1R2∧〈ac〉∈R1R3 〈ac〉∈R1R2∩R1R3 即〈ac〉∈R1 R2∩R3 〈ac〉∈R1R2∩R1R3 所以R1 R2∩R3 R1R2∩R1R3 再证包含可能是真包含举反例证明如果 A a B b1b2b3 C c A到B的关系R1〈ab1〉〈ab2〉 B到C的关系R2 〈b1c〉〈b3c〉 B到C的关系R3〈b2c〉〈b3c〉那么R1 R2∩R3 R1R2∩R1R3 〈ac〉此时R1 R2∩R3 ≠R1R2∩R1R3证毕定理32―2 设R1R2和R3分别是从A到BB到C和C到D的关系那么 R1R2 R3 R1 R2R3 证先证 R1R2R3 R1 R2R3 设〈ad〉∈ R1R2 R3那么对某c∈C〈ac〉∈R1R2和〈cd〉∈R3因为〈ac〉∈R1R2存在b∈B使〈ab〉∈R1和〈bc〉∈R2因为〈bc〉∈R2和〈cd〉∈R3得〈bd〉∈R2R3所以〈ad〉∈R1 R2R3 这样就证明了 R1R2 R3 R1 R2R3 R1 R2R3 R1R2 R3的证明是类似的留给读者自证上述证明也可用等价序列表达 322 关系R的幂当R是A上的一个关系时R可与自身合成任意次而形成A上的一个新关系在这种情况下RR常表示为R2RRR表示为R3等等我们能归纳地定义这一符号如下定义32―2设R是集合A上的二元关系n∈N那么R的n次幂记为Rn定义如下 1R0是A上的相等关系R0 〈xx〉｜x∈A 2 Rn1 Rn·R 定理32―3 设R是A上的二元关系并设m和n是N的元素那么 1Rm·Rn Rmn 2 Rm n Rmn 可用归纳法证明请读者自证定理32―4 设｜A｜ nR是集合A上的一个关系那么存在i和j使Ri Rj而0≤i＜j≤证A上的每一二元关系是A×A的子集因为｜A×A｜ n2｜ρ A×A ｜因此A上有个不同关系所以R的不同的幂不会超过个但序列R0R1 有项因此R的这些幂中至少有两个是相等的证毕定理32―5 设R是集合A上的一个二元关系若存在i和ji＜j使Ri Rj记d j-i那么 1 对所有k≥0Rik Rjk 2 对所有km≥0Rimdk Rik 3 记S R0R1R2Rj-1 那么R的每一次幂是S的元素即对n∈NRn∈S 证 1 和 2 部分用归纳法证明留作练习3 对于 c 设n∈N如果n＜j那么根据S的定义Rn∈S假设n≥j那么我们能将n表示为imdk这里k＜d根据 b 部分得Rn Rik因为ik＜j这证明了Rn∈S定理中的ij在实用时宜取最小的非负整数以保证S中无重复元素例32-2 设 A abcd R 〈ab〉〈cb〉〈bc〉〈cd〉其关系图如图32―3所示则R0 〈aa〉〈bb〉〈cc〉〈dd〉 R2 〈ac〉〈bb〉〈bd〉〈cc〉 R3〈ab〉〈ad〉〈bc〉〈cb〉〈cd〉 R4 〈ac〉〈bb〉〈bd〉〈cc〉它们的关系图如图32―4所示由于R4 R2根据定理32―5 c 对所有n∈NRn∈ R0R1R2R3 可见不必再算了事实上易证R5 R3R6 R4 R2用归纳法可得R2n1 R3和R2n R2这里n≥1 323 合成关系的矩阵表达定理32―6 设X x1x2xm Y y1y2yn Z z1z2zp R是X到Y的关系MR 〔aij〕是m×n矩阵S是Y到Z的关系MS 〔bij〕是n×p矩阵则MR·S 〔cij〕 MR·MS这里证因为如果存在某k使aik和bki都等于1则cij 1但aik和bkj都等于1意味着xiRyk和ykSzj所以xi R·S zj可见如此求得的MR·S确实表达了R·S的关系因此上述等式是正确的如果不仅存在一个k使aik和bki都是1此时cij仍为1只是从xi到zj不止一条长度为2的路径但等式仍然正确上段的论证已隐含了不止一个k的情况本定理说明合成关系矩阵可用关系矩阵布尔矩阵的乘法表达例32-3设X 12 Y abc Z αβ R 〈1a〉〈1b〉〈2c〉 S 〈aβ〉〈bβ〉则定理32―7 关系矩阵的乘法是可结合的证利用关系合成的可结合性证明 MR·MS ·MT MR·S·MT M R·S ·T MR· S·T MR·MS·T MR· MS·MT 不仅合成关系可用关系矩阵表达而且关系的集合运算也可用关系矩阵表达设R和S是X到Y上的二元关系MR 〔aij〕MS 〔bij〕cij是运算后所得新关系之关系矩阵的元素则 MR∩S MR∧MS cij aij∧bij MR∪S MR∨MS cij aij∨bij cij aij MR-S MR∧ cij aij∧ bij 331 逆关系在讨论闭包运算时要用到逆关系的概念因此我们先介绍逆关系定义33―1设R是从A到B的二元关系关系R的逆或叫R的逆关系记为是一从B到A的二元关系定义如下例33-11 I上的关系2 集合族上的关系的逆是关系3 空关系的逆是空关系4 B×A即A×B的全域关系的逆等于B×A的全域关系定理33―1设R是从A到B的关系而S是从B到C 的关系则定理33―2 设RR1和R2都是从A到B的二元关系那么下列各式成立 332 关系的闭包运算关系的闭包运算是关系上的一元运算它把给出的关系R扩充成一新关系R′使R′具有一定的性质且所进行的扩充又是最节约的定义33―2设R是A上的二元关系R的自反对称传递闭包是关系R′使 i R′是自反的对称的传递的ii R′R iii 对任何自反的对称的传递的关系R〃如果R〃R那么R〃R′ R的自反对称和传递闭包分别记为r R s R和t R 由定义可以看出R的自反对称传递闭包是含有R并且具有自反对称传递性质的最小关系如果R已经是自反的对称的传递的那么具有该性质并含有R的最小关系就是R自身下一定理说明这一点定理33―4设R是集合A上的二元关系那么 a R是自反的当且仅当r R R b R是对称的当且仅当s R R c R是传递的当且仅当t R R 证 a 如果R是自反的那么R具有定义33―2对R′所要求的性质因此r R R反之如果r R R那么根据定义33―2的性质 i R是自反的b 和 c 的证明是类似的略构造R的自反对称和传递闭包的方法就是给R补充必要的序偶使它具有所希望的特性下面我们用关系图来说明如何实现这一点定理33―5 设R是集合A上的二元关系那么r R R ∪E 这里E是A上相等关系在本节中均如此证设R′ R∪E显然R′是自反的且R′R余下只需证明最小性现假设R〃是A上的自反关系且R〃R因R〃是自反的所以R〃E又R〃R所以R〃R∪E R′这样定义33―2都满足所以R′ r R 证毕设G是集合A上二元关系R的关系图我们把G的所有弧都画成有来有往即如果有从a到b的弧那么也有从b到a的弧就得到了R的对称闭包的有向图下一定理体现了这一想法定理33―7 设R 是集合A上的二元关系那么例33-2 a 整数集合I 上的关系＜的自反闭包是≤对称闭包是关系≠传递闭包是关系＜自身b 整数集合I上的关系≤的自反闭包是自身对称闭包是全域关系传递闭包是自身 c E的自反闭包对称闭包和传递闭包都是 E d ≠的自反闭包是全域关系对称闭包是≠≠的传递闭包是全域关系e 空关系的自反闭包是相等关系对称闭包和传递闭包是自身 f 设R是I上的关系xRy当且仅当y x1那么t R 是关系＜定理33―8设R是集合A上的二元关系这里A有n个元素那么证设〈xy〉∈t R 于是必存在最小的正整数k使〈xy〉∈Rk现证明k≤n若不然存在A的元素序列x a0a1a2ak-1ak y使xRa1a1Ra2ak-1Ry因k＞na0a1ak中必有相同者不妨设ai aj0≤i＜j≤k于是xRa1a1Ra2ai-1RaiajRaj1ak-1Ry 成立即〈xy〉∈Rs这里s k- j-i但这与k是最小的假设矛盾于是k≤n又〈xy〉是任意的故定理得证例33-3 设A abcd R如图33―1 a 所示则t R R∪R2∪R3∪R4如图33―1 b 所示本例即是32-2 定理33―9 1 如果R是自反的那么s R 和t R 都是自反的 2 如果R是对称的那么r R 和t R 都是对称的 3 如果R是传递的那么r R 是传递的定理33―10 设R是集合A上的二元关系那么 1 rs R sr R 2 rt R tr R 3 ts R st R 2 注意到ER RE R 和对一切n∈NEn E可得 34 次序关系 341 偏序集合定义34―1 如果集合A上的二元关系R是自反的反对称的和传递的那么称R为A上的偏序称序偶〈AR〉为偏序集合如果R是偏序〈AR〉常记为〈A ≤〉≤是偏序符号由于≤难以书写通常写作≤读做小于或等于因为小于或等于也是一种偏序故不会产生混乱R是偏序时aRb就记成a≤b 如果R是集合A上的偏序则 R 也是A上的偏序如果用≤表示R 可用≥表示R〈A≤〉和〈A ≥〉都是偏序集合并互为对偶例34-1 1 〈I≤〉是偏序集合这里≤表示整数中的小于或等于关系 2 〈ρ A 〉是偏序集合这里是集合间的包含关系 3 A 2468 D代表整除关系M代表整倍数关系则 D 〈22〉〈44〉〈66〉〈88〉〈24〉〈26〉〈28〉〈48〉 M 〈22〉〈44〉〈66〉〈88〉〈42〉〈62〉〈82〉〈84〉〈AD〉〈AM〉都是偏序集合且互为对偶例2 a P 1234 〈P≤〉的哈斯图为图34―2 b A 236122436 〈A整除〉的哈斯图为图34―3 c A 1212 〈A整除〉的哈斯图为图34―4 定义34―2 设〈A≤〉是一偏序集合B是A的子集 a 元素b∈B是B的最大元素如果对每一元素x∈Bx≤b b 元素b∈B是B的最小元素如果对每一元素x∈Bb≤x 例3考虑在偏序整除下整数1到6的集合其哈斯图为图34―5 a 如果B 1236 那么1是B的最小元素6是B的最大元素 b 如果B 23 因为2和3互相不能整除那么B没有最小元素和最大元素 c 如果B 4 那么4是B的最大元素也是B的最小元素定理34―1 设〈A≤〉是一偏序集合且B A如果B有最大最小元素那么它是唯一的证假设a和b都是B的最大元素那么a≤b和b≤a从≤的反对称性得到a b当a和b都是B的最小元素时证明是类似的定义34―3设〈A≤〉是一偏序集合B是A的子集 a如果b∈B且B中不存在元素x使b≠x且b≤x那么元素b∈B叫做B的极大元素b 如果b∈B且B中不存在元素x使b≠x且x≤b那么元素b∈B叫做B的极小元素定义34―4设〈A≤〉是一偏序集合B是A的子集a 如果对每一b∈Bb≤a那么元素a∈A叫做B的上界如果对每一b∈Ba≤b那么元素a∈A叫做B的下界 b 如果a是一上界并且对每一B的上界a′有a≤a′那么元素a∈A叫做B的最小上界记为lub如果a是一下界并且对每一B的下界a′有a′≤a那么元素a∈A叫做B的最大下界记为glb 例34-4 a 考虑偏序集合〈〈11〉〈10〉〈01〉〈00〉≤〉这里≤按〈 ab〉≤〈cd〉a≤c∧b≤d 规定其哈斯图如图34―6 如果B 〈10〉那么〈10〉是B的最小和最大元素也是B的极大和极小元素B的上界是〈10〉和〈11〉〈10〉是最小上界B的下界是〈00〉和〈10〉〈10〉是最大下界 b 考虑偏序集合〈I≤〉设B 2i｜i∈N那么B既没有最大元素和极大元素也没有上界和最小上界B的最小元素和极小元素是0B的下界集合是 i｜i∈I∧i≤0 0是最大下界 c 考虑在偏序集合〈 256101530 整除〉其哈斯图如图34―7设B是全集合 256101530 那么2和5都是B的极小元素但B没有最小元素集合B没有下界所以没有最大下界元素30是B的最大元素极大元素上界最小上界定理34―2 如果〈A≤〉是非空有限的偏序集合则A的极小大元素常存在最大下界和最小上界也可能存在或不存在但如果它们存在则是唯一的定理34―3 设〈A≤〉是偏序集合且B A 如果B的最小上界最大下界存在那么是唯一的下述定理描述了存在于诸特异元素之间的某些关系定理34―4 设〈A≤〉是偏序集合B是A的子集 a 如果b是B的最大元素那么b是B的极大元素 b 如果b是B的最大元素那么b是B的lub c 如果b是B的一个上界且b∈B那么b是B的最大元素证明可由最大元素极大元素和lub的定义直接得出故略去另外读者不难给出表达最小元素极小元素和glb间关系的定理 342 拟序集合定义34―5如果集合A上的二元关系R是传递的和反自反的那么R叫做A上的拟序〈AR〉称为拟序集合常借用符号＜表示拟序拟序是反对称的虽然定义中没有明确指出但容易证明这一点因为如果xRy和yRx由R的传递性得xRx但这与R的反自反性矛盾所以xRy∧yRx常假于是xRy∧yRx→x y常真即R是反对称的例34-5 a 实数集合中的＜是拟序关系 b 集合族中的真包含是拟序关系拟序集合和偏序集合是紧密相关的唯一区别是相等关系E下述定理将说明这一点定理34―5在集合A上 a 如果R是一拟序那么rR R∪E是偏序 b 如果R是一偏序那么R-E是一拟序 343线序集合和良序集合如果≤是一偏序或a≤b或b≤a我们说a和b是可比较的偏序集合中的元素不一定都可比较所以叫偏序下面介绍的都是可比较的情况定义34―6在偏序集合〈A≤〉中如果每一ab∈A或者a≤b或者b≤a那么≤叫做A上的线序或全序这时的序偶〈A≤〉叫做线序集合或链例34-6 a P a ab abc 〈P〉是线序集合其哈斯图如图34―8所示 b 〈I≤〉是线序集合其哈斯图不完全如图34―9所示 c 设S是区间套的集合〔0a ｜a∈R 则〈S〉是线序集合 d 〈 1236 整除〉不是线序集合如果A是多于一个元素的集合那么〈ρ A 〉不是线序集合定义34―7如果A上的二元关系R是一线序且A的每一非空子集都有一最小元素那么R叫做A上的良序序偶〈AR〉叫做良序集合定理34―6〈N≤〉是良序集合证我们必须证明N的每一非空子集S在关系≤之下都有一最小元素因为S非空所以在S中可以取一个数n显然S中所有不大于n的数形成非空集T S如果T有最小数那么这最小数就是S中的最小数但从0到n只有n1个自然数于是T中所含的数最多是n1个所以T有最小数因此定理成立例34-8 a 每一有限线序集合是良序的 b 线序集合〈I≤〉不是良序集合因为I的某些子集诸如I自身不包含最小元素 c 关系≤是实数R的线序但不是良序例如子集A 01〕无最小元素如果A中的a是最小元素那么也在A中而≤a且不相等这与假设a是线序关系≤下A的最小元素矛盾2 应用N上的良序定义出Nn上的良序例如n 2时N2上的次序关系可如下定义〈ab〉〈cd〉a＜c∨ a c∧b d 〈N2〉是良序集合关系严格小于可如下定义〈ab〉＜〈cd〉〈ab〉≤〈cd〉∧〈ab〉≠〈cd〉类似地应用I上的线序能定义出线序集合〈In≤〉 3 应用字母表∑上的线序可定义出∑上的通常叫词典序的线序定义34―8 设∑是一有限字母表指定了字母表序线序如果xy∈∑ a x是y的词头或 b x zu和y zv这里z∈∑是x和y的最长公共词头且在字母表序中u的第一个字符前于v的第一个字符那么x≤y≤叫做词典序4 由于〈N〉和有限线序集合都是良序集合可应用它们定义出∑上的一个良序通常叫标准序定义34―9设∑是一有限字母表指定了字母表序‖x‖表示x∈∑的长度如果xy∈∑ a ‖x‖＜‖y‖或b ‖x‖‖y‖且在∑的词典序中x前于y那么x≤y ≤叫做标准序不论在词典序和标准序下∑的每一元素都有直接后继者设∑ abc 且a≤b≤cx∈∑在标准序下 xa和xb的直接后继者分别是xb和xc xc的直接后继者是ya这里y是x的直接后继者在词典序下x的直接后继者是xa在标准序下 xb和xc的直接前趋分别是xa和xb xa的直接前趋是yc这里y是x的直接前趋在词典序下 xa的直接前趋是x非a结尾的串都无直接前趋例如babaab但有无限个前趋 345 数学归纳法的推广前章我们把数学归纳法第一第二原理看作是自然数域上的一个推理规则本小节我们把它推广到一般的良序集合对任一个自然数n我们先取0如果n≠0取0的后继者1如果n≠1再取1的后继者2如此进行下去最终会得出n 给定一个良序集合如果对它的任一元素x我们先取该集合的最小元素m0如果x≠m0取m0的后继者m1如果x≠m1再取m1的后继者m2如此以往最终会得出x那么就称这样的良序集合是像自然数的例 8 1 设∑ ab 良序集合〈∑标准序〉是像自然数的因为定长的串的个数有限给定任一个串x在x之前的串的个数有限所以从∧开始反复取后继者终可得出x 2 良序集合〈N×N≤〉不像自然数这里≤按上一小节规定因为有许多元素没有直接前趋例如〈50〉就是这样因而有无限个元素前于〈50〉所以从〈00〉开始反复地取后继者不可能取得〈50〉像自然数的良序集合可以应用数学归纳法第一原理因为第一原理是建立在后继运算上而这种良序集合的每一元素都可通过重复地取后继者得到设m0是该良序集合〈S≤〉的最小元素S x 是元素x的后继者则推理规则如下对不像自然数的良序集合不能应用数学归纳法第一原理因为这种良序集合的有些元素不能由后继运算得到但对它可应用数学归纳法第二原理第二原理是建立在良序集合上的适用于一切良序集合设〈S≤〉是良序集合＜表示≤-E 即x＜y表示x≤y且x≠y 则推理规则如下下面证明良序集合上这个推理规则是有效的假设我们能证明前提例34-10〈Q≤〉是线序集合现说明在此线序集合中第二原理不是有效推理规则设谓词P x 表示x小于或等于5 i 当x≤5时 y〔y＜x→P y 〕是真P x 也真所以是真综合 i 和 ii 得在论述域Q上 x 〔 y y＜x→P y →P x 〕是真但结论 x P x 是假这说明第二原理不能应用于线序集合〈Q≤〉 35 等价关系和划分 351 等价关系二元关系的另一重要类型是等价关系其定义如下定义35―1 如果集合A上的二元关系R是自反的对称的和传递的那么称R是等价关系设R是A上的等价关系abc是A的任意元素如果aRb 即〈ab〉∈R 通常我们记作a～b读做a等价于b 定义35―2 设k是一正整数而ab∈I如果对某整数ma-b m·k那么a和b是模k等价写成a≡b modk 整数k叫做等价的模数定理35―1模k等价是任何集合A I上的等价关系证如果A 例35-1 c 已指出它是等价关系如果A≠则 i 自反的因为对任一aa-a 0·k得出a≡a modk ii 对称的因为a≡b mod k 时存在某m∈I使a-b m·k于是b-a-m·k 因此 b≡a mod k iii 传递的设a≡b mod k 和b≡c mod k 那么存在m1m2∈I 使a-b m1k和b-c m2·k 将两等式两边相加得a-c m1m2 ·k所以a≡c mod k 例1 a 同学集合A abcdefgA中的关系R是住在同一房间这是等价关系因为 i 任一个人和自己同住一间具有自反性 ii 若甲和乙同住一间则乙和甲也同住一间具有对称性 iii 若甲和乙同住一间乙和丙同住一间则甲和丙也同住一间具有传递性现假设a和b同住一间def同住一间c住一间则 R 〈aa〉〈ab〉〈ba〉〈bb〉〈cc〉〈dd〉〈ee〉〈ff〉〈de〉〈ed〉〈ef〉〈fe〉〈df〉〈fd〉其有向图如图35―1所示 b 数中的相等关系集合中的相等关系命题演算中的关系等都是等价关系 c 空集合中的二元关系R是等价关系因为i x x∈→xRx ii x y〔x∈∧y∈∧xRy→yRx〕iii x y z〔x∈∧y∈∧z∈∧xRy∧yRz→xRz〕都无义地真所以R是等价关系集合A上的全域关系R A×A是等价关系模数等价是整数域或其子集上的等价关系并且是等价关系中极为重要的一类定理 35-1 模k等价是任何集合A I上的等价关系证如果A 例35-1 3 已指出它是等价关系如果A≠则 i 自反的因为对任一aa-a 0·k得出a≡a mod k ii 对称的因为a≡b modk 时存在某m∈I使a-b m·k于是b-a -m·k因此b≡amodk iii 传递的设a≡b modk 和b≡c modk 那么存在m1m2∈I使a-b m1k和b-c m2·k将两等式两边相加得a-c m1m2 ·k所以a≡c modk 例35-2 a 若R是I上模4等价关系则〔0〕4 -8-4048 〔1〕4 -7-3159 〔2〕4 -6-22610 〔3〕4 -5-13711 b 若R是I上模2等价关系则〔0〕2 -4-2024 〔1〕2 -3-1135 每一集合中的数相互等价 c 时钟是按模12方式记数的设备13点钟和1点钟有相同的记数定义35―3 设R是集合A上等价关系对每一a∈Aa关于R的等价类是集合 x｜xRa 记为〔a〕R简记为〔a〕称a为等价类〔a〕的表示元素如果等价类个数有限则R的不同等价类的个数叫做R的秩否则秩是无限的对每一a∈A等价类〔a〕R非空因为a∈〔a〕R 例 35-3 1 如图35―2设A abcdef R 〈aa〉〈bb〉〈cc〉〈ab〉〈ba〉〈ac〉〈ca〉〈bc〉〈cb〉〈dd〉〈ee〉〈de〉〈ed〉〈ff〉则等价关系R的等价类如下〔a〕〔b〕〔c〕 abc 〔d〕〔e〕 de 〔f〕 f等价关系R的秩是3 2 I上模4等价的等价类是〔0〕4〔1〕4〔2〕4〔3〕4 参看例2 a I上模2等价的等价类是〔0〕2 〔1〕2 参看例2 b3 集合A上相等关系的秩等于A的元素个数定理35―2 设R是非空集合A上的等价关系aRb 当且仅当〔a〕〔b〕证充分性因为a∈〔a〕〔b〕即a∈〔b〕所以aRb 定理35―3设R是集合A上的等价关系则对所有ab∈A或者〔a〕〔b〕或者〔a〕∩〔b〕证如果A 断言无义地真现设A≠若〔a〕∩〔b〕≠则存在某元素c∈〔a〕和c∈〔b〕根据定理35―2得〔a〕〔c〕〔b〕又因〔a〕和〔b〕都非空〔a〕∩〔b〕和〔a〕〔b〕不能兼得因而定理得证定义35― 4 给定非空集合A和非空集合族πA1A2Am 如果那么称集合族π是A的覆盖定理35―4设R是集合A上的等价关系则证先证定理35―5设R1和R2是集合A上的等价关系那么R1 R2当且仅当〔a〕R1｜a∈A 〔a〕R2｜a∈A 证必要性因为R1 R2所以对任意a∈A有〔a〕R1 x｜xR1a x｜xR2a。
离散数学教学常见问题及改进措施研究离散数学是研究离散对象的结构及其相互关系的一门课程，是现代数学的一个重要分支。
由于数字电子计算机总是处理离散的运算对象，因此，计算机科学的数学基础基本上也是离散的，可以说离散数学就是计算机科学的数学语言。
基于此，离散数学不仅是计算机专业的基础课程，同时也是人工智能、信号处理等相关专业必不可少的数学工具[1]。
通过该课程的学习，不但可以培养学生的数学思维能力，使学生得到良好的数学训练，提高学生的概括抽象能力、逻辑推理能力和归纳构造能力，而且可以使学生掌握处理离散结构所必须的描述工具和方法，为其从事计算机相关领域研究和应用提供坚实的理论基础[2～3]。
1 离散数学教学中普遍存在的几个问题与计算机专业的许多专业课程不同，离散数学的学习需要学生具有较强的抽象能力和逻辑推理能力，因此，该课程无论是对计算机专业的教师还是学生来说都是极具挑战的一门课程。
结合多年的离散数学教学经历，本人认为这种挑战主要体现在以下几个方面。
1.1 思维方式上的挑战对于计算机专业的学生来说，他们在中学和大学初级阶段所学习的课程内容基本上都是比较具体的，可以通过形象思维方式进行认识和理解。
与这些课程不同，离散数学课程内容具有较强的抽象性和逻辑性，这就使得熟悉和习惯形象思维方式的计算机专业学生在离散数学的学习过程中很不适应，甚至有举步维艰之感。
离散数学的学习需要他们抛弃自己熟悉的形象思维方式，而使用自己比较陌生的抽象思维方式和逻辑思维方式。
由于平时缺少必要的抽象思维和逻辑思维锻炼，这种思维方式的陡然转变对计算机专业的学生来说是一个不小的挑战。
1.2 学习目的上的挑战受当前社会上流行的功利化思想的影响（也可能部分学生受工科思维方式的影响），计算机专业的学生更关注看得见实际用途的课程，如《C语言》《C++》等。
离散数学是一门基础课程，设置该课程的主要目的是培养学生的抽象思维和逻辑思维能力，为其将来参与创新性的研究和开发工作打下坚实的基础。
⽅世昌离散数学第三版教材课件第3章⼆元关系（可编辑）⽅世昌离散数学第三版教材课件第3章⼆元关系31 基本概念 32 关系的合成 33 关系上的闭包运算 34 次序关系 35 等价关系和划分 31 基本概念311 关系关系的数学概念是建⽴在⽇常⽣活中关系的概念之上的让我们先看两个例⼦例31-1 设 A abcd 是某乒乓球队的男队员集合 B efg 是⼥队员集合如果A和B元素之间有混双配对关系的是a 和gd和e我们可表达为 R 〈ag〉〈de〉这⾥R表⽰具有混双配对关系的序偶集合所有可能具有混双配对关系的序偶集合是 A×B 〈xy〉x∈A∧y∈B 〈ae〉〈af〉〈ag〉〈be〉〈bf〉〈bg〉〈ce〉〈cf〉〈cg〉〈de〉〈df〉〈dg〉例31-2 设学⽣集合A1 abcd 选修课集合A2 ⽇语法语成绩等级集合A3 甲⼄丙如果四⼈的选修内容及成绩如下 a ⽇⼄ b 法甲c ⽇丙 d 法⼄我们可表达为S 〈a⽇⼄〉〈b法甲〉〈c⽇丙〉〈d法⼄〉这⾥S表⽰学⽣和选修课及成绩间的关系⽽可能出现的全部情况为 A1×A2×A3 〈xyz〉x∈A1∧y∈A2∧z∈A3 〈a⽇甲〉〈a ⽇⼄〉〈a⽇丙〉〈a法甲〉〈a法⼄〉〈a法丙〉〈b⽇甲〉〈b⽇⼄〉〈b⽇丙〉〈b 法甲〉〈b法⼄〉〈b法丙〉〈c⽇甲〉〈c⽇⼄〉〈c⽇丙〉〈c法甲〉〈c法⼄〉〈d法丙〉定〈c法丙〉〈d⽇甲〉〈d⽇⼄〉〈d⽇丙〉〈d法甲〉〈d法⼄〉义31―1 1 A×B的⼦集叫做A到B的⼀个⼆元关系2 A1×A2××An n≥1 的⼦集叫做A1×A2××An上的⼀个n元关系3 从定义可看出关系是⼀个集合所有定义集合的⽅法都可⽤来定义关系例31-1和例31-2是列举法的例⼦⼀个谓词Px1x2xn 可以定义⼀个n元关系R R 〈x1x2xn〉P x1x2xn 例如实数R上的⼆元关系＞可定义如下＞〈xy〉x∈R∧y∈R∧x＞y 反之⼀个n元关系也可定义⼀个谓词当n 1时R 〈x〉P x 称为⼀元关系它是⼀重组集合表⽰论述域上具有性质P的元素集合其意义与R xP x 相同仅记法不同⽽已例如设P x 表⽰x是质数论述域是N则质数集合可表⽰为〈x〉｜P x 或x｜P x 关系也可归纳地定义⾃然数上的⼩于关系可定义如下1 基础〈01〉∈＜2 归纳如果〈xy〉∈＜那么i 〈xy1〉∈＜ ii 〈x1y1〉∈＜ 3 极⼩性对⼀切xy∈Nx＜y当且仅当〈xy〉是由有限次应⽤条款 1 和 2 构成定义31―2 设R是的⼦集如果R 则称R为空关系如果则称R为全域关系现在定义关系相等的概念在关系相等的概念中不仅需要n重组集合相等还需其叉积扩集也相同定义31―3设R1是上的n元关系R2是上的m元关系那么R1 R2当且仅当n m且对⼀切i1≤i≤nAi Bi并且R1和R2是相等的有序n重组集合 312 ⼆元关系最重要的关系是⼆元关系本章主要讨论⼆元关系今后术语关系都指⼆元关系若⾮⼆元关系将⽤三元或n元⼀类术语指出⼆元关系有⾃⼰专⽤的记法和若⼲新术语设 A x1x2x7 B y1y2y6 R〈x3y1〉〈x3y2〉〈x4y4〉〈x6y2〉 A到B的⼆元关系R可如图31―1那样形象地表⽰〈x3y1〉∈R也可写成x3Ry1称为中缀记法读做x3和y1有关系R中缀记法常⽤来表⽰诸如＜＞等关系例如〈35〉∈＜通常写作3＜5 A叫做关系R的前域B叫做关系R的陪域 D R x｜y 〈xy〉∈R 叫做关系R的定义域R R y｜x 〈xy〉∈R 叫做关系R的值域关系是序偶的集合对它可进⾏集合运算运算结果定义⼀个新关系设R和S是给定集合上的两个⼆元关系则R∪SR∩SR-S 等可分别定义如下x R∪S y xRy∨xSy x R∩S y xRy∧xSy x R-S y xRy∧xy x y xRy 例31-3平⾯上的⼏何图形是平⾯R2的⼦集也是⼀种关系设参看图31―2 R1 〈xy〉｜〈xy〉∈R2∧x2y2≤9 R2 〈xy〉｜〈xy〉∈R2∧1≤x≤3 ∧0≤y≤3 R3 〈xy〉｜〈xy〉∈R2∧x2y2≥4 则 R1∪R2 〈xy〉｜〈xy〉∈R2∧ x2y2 ≤9∨ 1≤x≤3∧0≤y≤3 R1∩R3〈xy〉｜〈xy〉∈R2∧ x2y2 ≤9∧x2y2≥4 R1-R3 〈xy〉｜〈xy〉∈R2∧ x2y2≤9∧ L x2y2≥4 〈xy〉｜〈xy〉∈R2∧ x2y2≥4 313 关系矩阵和关系图表达有限集合到有限集合的⼆元关系时矩阵是⼀有⼒⼯具定义31―4 给定集合A a1a2am 和B b1b2bn 及⼀个A到B的⼆元关系R 使例31-4 设A a1a2 B b1b2b3 R 〈a1b1〉〈a2b1〉〈a1b3〉〈a2b2〉则其关系矩阵为例31-5 设A 1234 A上的⼆元关系R 〈xy〉｜x＞y 试求出关系矩阵解R 〈41〉〈42〉〈43〉〈31〉〈32〉〈21〉例31-6 设 A 12345 R 〈12〉〈22〉〈32〉〈34〉〈43〉其图⽰如图31―3所⽰图中结点5叫做孤⽴点利⽤关系R的图⽰也可写出关系R 314 关系的特性在研究各种⼆元关系中关系的某些特性扮演着重要⾓⾊我们将定义这些特性并给出它的图⽰和矩阵的特点定义31―5 设R是A上的⼆元关系 1如果对A中每⼀xxRx那么R是⾃反的即 A上的关系R是⾃反的x x∈A→xRx A 123 R1 〈11〉〈22〉〈33〉〈12〉是⾃反的其关系图和关系矩阵的特点如图31―4所⽰ 2 如果对A中每⼀xxRx那么R是反⾃反的即 A上的关系R是反⾃反的 x x∈A→xRx 例如 A 123 R2 〈21〉〈13〉〈32〉是反⾃反的其关系图和关系矩阵的特点如图31―5所⽰有些关系既不是⾃反的⼜不是反⾃反的如图31―6 例如R3 〈11〉〈12〉〈32〉〈23〉〈33〉 3 如果对每⼀xy∈AxRy蕴含着yRx那么R是对称的即A上的关系R是对称的x y x∈A∧y∈A∧xRy→yRx 例如A 123 R4 〈12〉〈21〉〈13〉〈31〉〈11〉是对称的其关系图和关系矩阵的特点如图31―7所⽰ 4 如果对每⼀xy∈AxRyyRx蕴含着x y那么R是反对称的即A上的关系R是反对称的x y x∈A∧y∈A∧xRy∧yRx→x y 例如A 123 R5 〈12〉〈23〉是反对称的其关系图和关系矩阵的特点如图31―8所⽰ 5 如果对每⼀xyz∈AxRyyRz蕴含着xRz那么R是传递的即A上的关系R是传递的x y z x∈A∧y∈A∧z ∈A∧xRy∧yRz→xRz 例如A 1234R5 〈41〉〈43〉〈42〉〈32〉〈31〉〈21〉是传递的其关系图和关系矩阵如图31―10所⽰例31-7 1 任何集合上的相等关系是⾃反的对称的反对称的和传递的但不是反⾃反的 2 整数集合I上关系≤是⾃反的反对称的可传递的但不是反⾃反的和对称的关系＜是反⾃反的反对称的可传递的但不是⾃反的和对称的 3 设 ab 试考察上的下列关系 i 关系与有同样长度是⾃反的对称的可传递的但不是反⾃反的和反对称的 ii xRy当且仅当x是y的真词头这⾥R是反⾃反的反对称的可传递的但不是⾃反的和对称的 iii xRy当且仅当x的某真词头是y的⼀个真词尾这⾥R既不是⾃反的⼜不是反⾃反的因为aaRaa但abRab既不是对称的也不是反对称的并且不是传递的 4 ⾮空集合上的空关系是反⾃反的对称的反对称的和传递的但不是⾃反的空集合上的空关系则是⾃反的反⾃反的对称的反对称的和可传递的 5 基数⼤于1的集合上的全域关系是⾃反的对称的和传递的但不是反⾃反的和反对称的例如图31―11所⽰的关系 321 关系的合成前边已经指出关系是序偶的集合因此可以进⾏集合运算本节介绍⼀种对关系来说更为重要的运算合成运算假设R1是A到B的关系R2是B到C的关系参看图32-1合成关系R1R2是⼀个A到C的关系如果在关系图上从a∈A到c∈C有⼀长度路径中弧的条数为2的路径其第⼀条弧属于R1其第⼆条弧属于R2那么〈ac〉∈R1R2合成关系R1R2就是由〈ac〉这样的序偶组成的集合其第⼀条弧属于R1其第⼆条弧属于R2那么〈ac〉∈R1R2合成关系R1R2就是由〈ac〉这样的序偶组成的集合定义32―1 设R1是从A到B的关系R2是从B到C的关系从A到C的合成关系记为R1R2定义为 R1R2 〈ac〉｜a∈A∧c∈C∧b〔b∈B∧〈ab〉∈R1∧〈bc〉∈R2〕例32-11 如果R1是关系是的兄弟R2是关系是的⽗亲那么R1R2是关系是的叔伯R2R2是关系是的祖⽗ 2 给定集合A 1234 B 234 C 123 设R是A到B的关系S是B到C的关系 R 〈xy〉｜xy 6 〈24〉〈33〉〈42〉S 〈yz〉｜y-z 1 〈21〉〈32〉〈43〉则R·S 〈23〉〈32〉〈41〉如图32―2所⽰ 3 设A 12345 R和S都是A上⼆元关系如果 R 〈12〉〈34〉〈22〉 S 〈42〉〈25〉〈31〉〈13〉则R·S 〈15〉〈32〉〈25〉 S·R 〈42〉〈32〉〈14〉 R·S ·R 〈32〉 R· S·R 〈32〉 R·R 〈12〉〈22〉 S·S〈45〉〈33〉〈11〉 4 设R是A到B的⼆元关系IAIB分别是A和B上的相等关系则IA·R R·IB R 5 如果关系R的值域与关系S的定义域的交集是空集则合成关系R·S是空关系下边介绍合成关系的性质定理32―1 设R1是从A到B的关系R2和R3是从B到C的关系R4是从C到D的关系那么 1 R1 R2∪R3 R1R2∪R1R3 2 R1 R2∩R3 R1R2∩R1R3 3 R2∪R3 R4 R2R4∪R3R4 4 R2∩R3 R4 R2R4∩R3R41 2 3 部分的证明留作练习我们仅证明 2 部分证先证明公式因为〈ac〉∈R1 R2∩R3 b〔〈ab〉∈R1∧〈bc〉∈R2∩R3 〕b〔〈ab〉∈R1∧〈bc〉∈R2∧〈bc〉∈R3 〕b〔〈ab〉∈R1∧〈bc〉∈R2 ∧〈ab〉∈R1∧〈bc〉∈R3 〕b〔〈ab〉∈R1∧〈bc〉∈R2〕∧b〔〈ab〉∈R1∧〈bc〉∈R3〕〈ac〉∈R1R2∧〈ac〉∈R1R3 〈ac〉∈R1R2∩R1R3 即〈ac〉∈R1 R2∩R3 〈ac〉∈R1R2∩R1R3 所以R1 R2∩R3 R1R2∩R1R3 再证包含可能是真包含举反例证明如果 A a B b1b2b3 C c A到B的关系R1〈ab1〉〈ab2〉 B到C的关系R2 〈b1c〉〈b3c〉 B到C的关系R3〈b2c〉〈b3c〉那么R1 R2∩R3 R1R2∩R1R3 〈ac〉此时R1 R2∩R3 ≠R1R2∩R1R3证毕定理32―2 设R1R2和R3分别是从A到BB到C和C到D的关系那么 R1R2 R3 R1 R2R3 证先证 R1R2R3 R1 R2R3 设〈ad〉∈ R1R2 R3那么对某c∈C〈ac〉∈R1R2和〈cd〉∈R3因为〈ac〉∈R1R2存在b∈B使〈ab〉∈R1和〈bc〉∈R2因为〈bc〉∈R2和〈cd〉∈R3得〈bd〉∈R2R3所以〈ad〉∈R1 R2R3 这样就证明了 R1R2 R3 R1 R2R3 R1 R2R3 R1R2 R3的证明是类似的留给读者⾃证上述证明也可⽤等价序列表达 322 关系R的幂当R是A上的⼀个关系时R可与⾃⾝合成任意次⽽形成A上的⼀个新关系在这种情况下RR常表⽰为R2RRR表⽰为R3等等我们能归纳地定义这⼀符号如下定义32―2设R是集合A上的⼆元关系n∈N那么R的n次幂记为Rn定义如下 1R0是A上的相等关系R0 〈xx〉｜x∈A 2 Rn1 Rn·R 定理32―3 设R是A上的⼆元关系并设m和n是N的元素那么 1Rm·Rn Rmn 2 Rm n Rmn 可⽤归纳法证明请读者⾃证定理32―4 设｜A｜ nR是集合A上的⼀个关系那么存在i和j使Ri Rj⽽0≤i＜j≤证A上的每⼀⼆元关系是A×A的⼦集因为｜A×A｜ n2｜ρ A×A ｜因此A上有个不同关系所以R的不同的幂不会超过个但序列R0R1 有项因此R的这些幂中⾄少有两个是相等的证毕定理32―5 设R是集合A上的⼀个⼆元关系若存在i和ji＜j使Ri Rj记d j-i那么 1 对所有k≥0Rik Rjk 2 对所有km≥0Rimdk Rik 3 记S R0R1R2Rj-1 那么R的每⼀次幂是S的元素即对n∈NRn∈S 证 1 和 2 部分⽤归纳法证明留作练习3 对于 c 设n∈N如果n＜j那么根据S的定义Rn∈S假设n≥j那么我们能将n表⽰为imdk这⾥k＜d根据 b 部分得Rn Rik因为ik＜j这证明了Rn∈S定理中的ij在实⽤时宜取最⼩的⾮负整数以保证S中⽆重复元素例32-2 设 A abcd R 〈ab〉〈cb〉〈bc〉〈cd〉其关系图如图32―3所⽰则R0 〈aa〉〈bb〉〈cc〉〈dd〉 R2 〈ac〉〈bb〉〈bd〉〈cc〉 R3〈ab〉〈ad〉〈bc〉〈cb〉〈cd〉 R4 〈ac〉〈bb〉〈bd〉〈cc〉它们的关系图如图32―4所⽰由于R4 R2根据定理32―5 c 对所有n∈NRn∈ R0R1R2R3 可见不必再算了事实上易证R5 R3R6 R4 R2⽤归纳法可得R2n1 R3和R2n R2这⾥n≥1 323 合成关系的矩阵表达定理32―6 设X x1x2xm Y y1y2yn Z z1z2zp R是X到Y的关系MR 〔aij〕是m×n矩阵S是Y到Z的关系MS 〔bij〕是n×p矩阵则MR·S 〔cij〕 MR·MS这⾥证因为如果存在某k使aik和bki都等于1则cij 1但aik和bkj都等于1意味着xiRyk和ykSzj所以xi R·S zj可见如此求得的MR·S确实表达了R·S的关系因此上述等式是正确的如果不仅存在⼀个k使aik和bki都是1此时cij仍为1只是从xi到zj不⽌⼀条长度为2的路径但等式仍然正确上段的论证已隐含了不⽌⼀个k的情况本定理说明合成关系矩阵可⽤关系矩阵布尔矩阵的乘法表达例32-3设X 12 Y abc Z αβ R 〈1a〉〈1b〉〈2c〉 S 〈aβ〉〈bβ〉则定理32―7 关系矩阵的乘法是可结合的证利⽤关系合成的可结合性证明 MR·MS ·MT MR·S·MT M R·S ·T MR· S·T MR·MS·T MR· MS·MT 不仅合成关系可⽤关系矩阵表达⽽且关系的集合运算也可⽤关系矩阵表达设R和S是X到Y上的⼆元关系MR 〔aij〕MS 〔bij〕cij是运算后所得新关系之关系矩阵的元素则 MR∩S MR∧MS cij aij∧bij MR∪S MR∨MS cij aij∨bij cij aij MR-S MR∧ cij aij∧ bij 331 逆关系在讨论闭包运算时要⽤到逆关系的概念因此我们先介绍逆关系定义33―1设R是从A到B的⼆元关系关系R的逆或叫R的逆关系记为是⼀从B到A的⼆元关系定义如下例33-11 I上的关系2 集合族上的关系的逆是关系3 空关系的逆是空关系4 B×A即A×B的全域关系的逆等于B×A的全域关系定理33―1设R是从A到B的关系⽽S是从B到C 的关系则定理33―2 设RR1和R2都是从A到B的⼆元关系那么下列各式成⽴ 332 关系的闭包运算关系的闭包运算是关系上的⼀元运算它把给出的关系R扩充成⼀新关系R′使R′具有⼀定的性质且所进⾏的扩充⼜是最节约的定义33―2设R是A上的⼆元关系R的⾃反对称传递闭包是关系R′使 i R′是⾃反的对称的传递的ii R′R iii 对任何⾃反的对称的传递的关系R〃如果R〃R那么R〃R′ R的⾃反对称和传递闭包分别记为r R s R和t R 由定义可以看出R的⾃反对称传递闭包是含有R并且具有⾃反对称传递性质的最⼩关系如果R已经是⾃反的对称的传递的那么具有该性质并含有R的最⼩关系就是R⾃⾝下⼀定理说明这⼀点定理33―4设R是集合A上的⼆元关系那么 a R是⾃反的当且仅当r R R b R是对称的当且仅当s R R c R是传递的当且仅当t R R 证 a 如果R是⾃反的那么R具有定义33―2对R′所要求的性质因此r R R反之如果r R R那么根据定义33―2的性质 i R是⾃反的b 和 c 的证明是类似的略构造R的⾃反对称和传递闭包的⽅法就是给R补充必要的序偶使它具有所希望的特性下⾯我们⽤关系图来说明如何实现这⼀点定理33―5 设R是集合A上的⼆元关系那么r R R ∪E 这⾥E是A上相等关系在本节中均如此证设R′ R∪E显然R′是⾃反的且R′R余下只需证明最⼩性现假设R〃是A 上的⾃反关系且R〃R因R〃是⾃反的所以R〃E⼜R〃R所以R〃R∪E R′这样定义33―2都满⾜所以R′ r R 证毕设G是集合A上⼆元关系R的关系图我们把G的所有弧都画成有来有往即如果有从a到b的弧那么也有从b到a的弧就得到了R的对称闭包的有向图下⼀定理体现了这⼀想法定理33―7 设R 是集合A上的⼆元关系那么例33-2 a 整数集合I 上的关系＜的⾃反闭包是≤对称闭包是关系≠传递闭包是关系＜⾃⾝b 整数集合I上的关系≤的⾃反闭包是⾃⾝对称闭包是全域关系传递闭包是⾃⾝ c E的⾃反闭包对称闭包和传递闭包都是 E d ≠的⾃反闭包是全域关系对称闭包是≠≠的传递闭包是全域关系e 空关系的⾃反闭包是相等关系对称闭包和传递闭包是⾃⾝ f 设R是I上的关系xRy当且仅当y x1那么t R 是关系＜定理33―8设R是集合A上的⼆元关系这⾥A有n个元素那么证设〈xy〉∈t R 于是必存在最⼩的正整数k使〈xy〉∈Rk现证明k≤n若不然存在A的元素序列x a0a1a2ak-1ak y使xRa1a1Ra2ak-1Ry因k＞na0a1ak中必有相同者不妨设ai aj0≤i＜j≤k于是xRa1a1Ra2ai-1RaiajRaj1ak-1Ry 成⽴即〈xy〉∈Rs 这⾥s k- j-i但这与k是最⼩的假设⽭盾于是k≤n⼜〈xy〉是任意的故定理得证例33-3 设A abcd R如图33―1 a 所⽰则t R R∪R2∪R3∪R4如图33―1 b 所⽰本例即是32-2 定理33―9 1 如果R是⾃反的那么s R 和t R 都是⾃反的 2 如果R是对称的那么r R 和t R 都是对称的 3 如果R是传递的那么r R 是传递的定理33―10 设R是集合A上的⼆元关系那么 1 rs R sr R 2 rt R tr R 3 ts R st R 2 注意到ER RE R 和对⼀切n∈NEn E可得 34 次序关系 341 偏序集合定义34―1 如果集合A上的⼆元关系R是⾃反的反对称的和传递的那么称R为A上的偏序称序偶〈AR〉为偏序集合如果R是偏序〈AR〉常记为〈A ≤〉≤是偏序符号由于≤难以书写通常写作≤读做⼩于或等于因为⼩于或等于也是⼀种偏序故不会产⽣混乱R是偏序时aRb就记成a≤b 如果R是集合A上的偏序则 R 也是A上的偏序如果⽤≤表⽰R 可⽤≥表⽰R〈A≤〉和〈A ≥〉都是偏序集合并互为对偶例34-1 1 〈I≤〉是偏序集合这⾥≤表⽰整数中的⼩于或等于关系 2 〈ρ A 〉是偏序集合这⾥是集合间的包含关系 3 A 2468 D代表整除关系M代表整倍数关系则 D 〈22〉〈44〉〈66〉〈88〉〈24〉〈26〉〈28〉〈48〉 M 〈22〉〈44〉〈66〉〈88〉〈42〉〈62〉〈82〉〈84〉〈AD〉〈AM〉都是偏序集合且互为对偶例2 a P 1234 〈P≤〉的哈斯图为图34―2 b A 236122436 〈A整除〉的哈斯图为图34―3 c A 1212 〈A整除〉的哈斯图为图34―4 定义34―2 设〈A≤〉是⼀偏序集合B是A的⼦集 a 元素b∈B是B的最⼤元素如果对每⼀元素x∈Bx≤b b 元素b∈B是B的最⼩元素如果对每⼀元素x∈Bb≤x 例3考虑在偏序整除下整数1到6的集合其哈斯图为图34―5 a 如果B 1236 那么1是B的最⼩元素6是B的最⼤元素 b 如果B 23 因为2和3互相不能整除那么B没有最⼩元素和最⼤元素 c 如果B 4 那么4是B的最⼤元素也是B的最⼩元素定理34―1 设〈A≤〉是⼀偏序集合且B A如果B有最⼤最⼩元素那么它是唯⼀的证假设a和b都是B的最⼤元素那么a≤b和b≤a从≤的反对称性得到a b当a和b都是B的最⼩元素时证明是类似的定义34―3设〈A≤〉是⼀偏序集合B是A的⼦集 a如果b∈B且B中不存在元素x使b≠x且b≤x那么元素b∈B叫做B的极⼤元素b 如果b∈B且B中不存在元素x使b≠x且x≤b那么元素b∈B叫做B的极⼩元素定义34―4设〈A≤〉是⼀偏序集合B是A的⼦集a 如果对每⼀b∈Bb≤a那么元素a∈A叫做B的上界如果对每⼀b∈Ba≤b那么元素a∈A叫做B的下界 b 如果a是⼀上界并且对每⼀B的上界a′有a≤a′那么元素a∈A叫做B的最⼩上界记为lub如果a是⼀下界并且对每⼀B的下界a′有a′≤a那么元素a∈A叫做B的最⼤下界记为glb 例34-4 a 考虑偏序集合〈〈11〉〈10〉〈01〉〈00〉≤〉这⾥≤按〈 ab〉≤〈cd〉a≤c∧b≤d 规定其哈斯图如图34―6 如果B 〈10〉那么〈10〉是B的最⼩和最⼤元素也是B的极⼤和极⼩元素B的上界是〈10〉和〈11〉〈10〉是最⼩上界B的下界是〈00〉和〈10〉〈10〉是最⼤下界 b 考虑偏序集合〈I≤〉设B 2i｜i∈N那么B既没有最⼤元素和极⼤元素也没有上界和最⼩上界B的最⼩元素和极⼩元素是0B的下界集合是 i｜i∈I∧i≤0 0是最⼤下界 c 考虑在偏序集合〈 256101530 整除〉其哈斯图如图34―7设B是全集合 256101530 那么2和5都是B的极⼩元素但B没有最⼩元素集合B没有下界所以没有最⼤下界元素30是B的最⼤元素极⼤元素上界最⼩上界定理34―2 如果〈A≤〉是⾮空有限的偏序集合则A的极⼩⼤元素常存在最⼤下界和最⼩上界也可能存在或不存在但如果它们存在则是唯⼀的定理34―3 设〈A≤〉是偏序集合且B A 如果B的最⼩上界最⼤下界存在那么是唯⼀的下述定理描述了存在于诸特异元素之间的某些关系定理34―4 设〈A≤〉是偏序集合B是A的⼦集 a 如果b是B的最⼤元素那么b是B的极⼤元素 b 如果b是B的最⼤元素那么b是B的lub c 如果b是B的⼀个上界且b∈B那么b是B的最⼤元素证明可由最⼤元素极⼤元素和lub的定义直接得出故略去另外读者不难给出表达最⼩元素极⼩元素和glb间关系的定理 342 拟序集合定义34―5如果集合A上的⼆元关系R是传递的和反⾃反的那么R叫做A上的拟序〈AR〉称为拟序集合常借⽤符号＜表⽰拟序拟序是反对称的虽然定义中没有明确指出但容易证明这⼀点因为如果xRy和yRx由R的传递性得xRx但这与R的反⾃反性⽭盾所以xRy∧yRx常假于是xRy∧yRx→x y常真即R是反对称的例34-5 a 实数集合中的＜是拟序关系 b 集合族中的真包含是拟序关系拟序集合和偏序集合是紧密相关的唯⼀区别是相等关系E下述定理将说明这⼀点定理34―5在集合A上 a 如果R是⼀拟序那么rR R∪E是偏序 b 如果R是⼀偏序那么R-E是⼀拟序 343线序集合和良序集合如果≤是⼀偏序或a≤b或b≤a我们说a和b是可⽐较的偏序集合中的元素不⼀定都可⽐较所以叫偏序下⾯介绍的都是可⽐较的情况定义34―6在偏序集合〈A≤〉中如果每⼀ab∈A或者a≤b或者b≤a那么≤叫做A上的线序或全序这时的序偶〈A≤〉叫做线序集合或链例34-6 a P a ab abc 〈P〉是线序集合其哈斯图如图34―8所⽰ b 〈I≤〉是线序集合其哈斯图不完全如图34―9所⽰ c 设S是区间套的集合〔0a ｜a∈R 则〈S〉是线序集合 d 〈 1236 整除〉不是线序集合如果A是多于⼀个元素的集合那么〈ρ A 〉不是线序集合定义34―7如果A上的⼆元关系R是⼀线序且A的每⼀⾮空⼦集都有⼀最⼩元素那么R叫做A上的良序序偶〈AR〉叫做良序集合定理34―6〈N≤〉是良序集合证我们必须证明N的每⼀⾮空⼦集S在关系≤之下都有⼀最⼩元素因为S⾮空所以在S中可以取⼀个数n显然S中所有不⼤于n的数形成⾮空集T S如果T有最⼩数那么这最⼩数就是S中的最⼩数但从0到n只有n1个⾃然数于是T中所含的数最多是n1个所以T有最⼩数因此定理成⽴例34-8 a 每⼀有限线序集合是良序的 b 线序集合〈I≤〉不是良序集合因为I的某些⼦集诸如I⾃⾝不包含最⼩元素 c 关系≤是实数R的线序但不是良序例如⼦集A 01〕⽆最⼩元素如果A中的a是最⼩元素那么也在A中⽽≤a且不相等这与假设a是线序关系≤下A的最⼩元素⽭盾2 应⽤N上的良序定义出Nn上的良序例如n 2时N2上的次序关系可如下定义〈ab〉〈cd〉a＜c∨ a c∧b d 〈N2〉是良序集合关系严格⼩于可如下定义〈ab〉＜〈cd〉〈ab〉≤〈cd〉∧〈ab〉≠〈cd〉类似地应⽤I上的线序能定义出线序集合〈In≤〉 3 应⽤字母表∑上的线序可定义出∑上的通常叫词典序的线序定义34―8 设∑是⼀有限字母表指定了字母表序线序如果xy∈∑ a x是y的词头或 b x zu和y zv这⾥z∈∑是x和y的最长公共词头且在字母表序中u的第⼀个字符前于v的第⼀个字符那么x≤y≤叫做词典序4 由于〈N〉和有限线序集合都是良序集合可应⽤它们定义出∑上的⼀个良序通常叫标准序定义34―9设∑是⼀有限字母表指定了字母表序‖x‖表⽰x∈∑的长度如果xy∈∑ a ‖x‖＜‖y‖或b ‖x‖‖y‖且在∑的词典序中x前于y那么x≤y ≤叫做标准序不论在词典序和标准序下∑的每⼀元素都有直接后继者设∑ abc 且a≤b≤cx∈∑在标准序下 xa和xb的直接后继者分别是xb和xc xc的直接后继者是ya这⾥y是x的直接后继者在词典序下x的直接后继者是xa 在标准序下 xb和xc的直接前趋分别是xa和xb xa的直接前趋是yc这⾥y是x的直接前趋在词典序下 xa的直接前趋是x⾮a结尾的串都⽆直接前趋例如babaab但有⽆限个前趋 345 数学归纳法的推⼴前章我们把数学归纳法第⼀第⼆原理看作是⾃然数域上的⼀个推理规则本⼩节我们把它推⼴到⼀般的良序集合对任⼀个⾃然数n我们先取0如果n≠0取0的后继者1如果n≠1再取1的后继者2如此进⾏下去最终会得出n 给定⼀个良序集合如果对它的任⼀元素x我们先取该集合的最⼩元素m0如果x≠m0取m0的后继者m1如果x≠m1再取m1的后继者m2如此以往最终会得出x那么就称这样的良序集合是像⾃然数的例 8 1 设∑ ab 良序集合〈∑标准序〉是像⾃然数的因为定长的串的个数有限给定任⼀个串x在x之前的串的个数有限所以从∧开始反复取后继者终可得出x 2 良序集合〈N×N≤〉不像⾃然数这⾥≤按上⼀⼩节规定因为有许多元素没有直接前趋例如〈50〉就是这样因⽽有⽆限个元素前于〈50〉所以从〈00〉开始反复地取后继者不可能取得〈50〉像⾃然数的良序集合可以应⽤数学归纳法第⼀原理因为第⼀原理是建⽴在后继运算上⽽这种良序集合的每⼀元素都可通过重复地取后继者得到设m0是该良序集合〈S≤〉的最⼩元素S x 是元素x的后继者则推理规则如下对不像⾃然数的良序集合不能应⽤数学归纳法第⼀原理因为这种良序集合的有些元素不能由后继运算得到但对它可应⽤数学归纳法第⼆原理第⼆原理是建⽴在良序集合上的适⽤于⼀切良序集合设〈S≤〉是良序集合＜表⽰≤-E 即x＜y表⽰x≤y且x≠y 则推理规则如下下⾯证明良序集合上这个推理规则是有效的假设我们能证明前提例34-10〈Q≤〉是线序集合现说明在此线序集合中第⼆原理不是有效推理规则设谓词Px 表⽰x⼩于或等于5 i 当x≤5时 y〔y＜x→P y 〕是真P x 也真所以是真综合 i 和 ii 得在论述域Q上 x 〔 y y＜x→P y →P x 〕是真但结论 x P x 是假这说明第⼆原理不能应⽤于线序集合〈Q≤〉 35 等价关系和划分 351 等价关系⼆元关系的另⼀重要类型是等价关系其定义如下定义35―1 如果集合A上的⼆元关系R是⾃反的对称的和传递的那么称R是等价关系设R是A上的等价关系abc是A的任意元素如果aRb 即〈ab〉∈R 通常我们记作a～b读做a等价于b 定义35―2 设k是⼀正整数⽽ab∈I如果对某整数ma-b m·k那么a和b是模k等价写成a≡b modk 整数k叫做等价的模数定理35―1模k等价是任何集合A I上的等价关系证如果A 例35-1 c 已指出它是等价关系如果A≠则 i ⾃反的因为对任⼀aa-a 0·k得出a≡a modk ii 对称的因为a≡b mod k 时存在某m∈I使a-b m·k于是b-a-m·k 因此 b≡a mod k iii 传递的设a≡b mod k 和b≡c mod k 那么存在m1m2∈I 使a-b m1k和b-c m2·k 将两等式两边相加得a-c m1m2 ·k所以a≡c mod k 例1 a 同学集合A abcdefgA中的关系R是住在同⼀房间这是等价关系因为 i 任⼀个⼈和⾃⼰同住⼀间具有⾃反性 ii 若甲和⼄同住⼀间则⼄和甲也同住⼀间具有对称性 iii 若甲和⼄同住⼀间⼄和丙同住⼀间则甲和丙也同住⼀间具有传递性现假设a和b同住⼀间def同住⼀间c住⼀间则 R 〈aa〉〈ab〉〈ba〉〈bb〉〈cc〉〈dd〉〈ee〉〈ff〉〈de〉〈ed〉〈ef〉〈fe〉〈df〉〈fd〉其有向图如图35―1所⽰ b 数中的相等关系集合中的相等关系命题演算中的关系等都是等价关系 c 空集合中的⼆元关系R是等价关系因为i x x∈→xRx ii x y〔x∈∧y∈∧xRy→yRx〕iii x y z〔x∈∧y∈∧z∈∧xRy∧yRz→xRz〕都⽆义地真所以R是等价关系集合A上的全域关系R A×A是等价关系模数等价是整数域或其⼦集上的等价关系并且是等价关系中极为重要的⼀类定理 35-1 模k等价是任何集合A I上的等价关系证如果A 例35-1 3 已指出它是等价关系如果A≠则 i ⾃反的因为对任⼀aa-a 0·k得出a≡a mod k ii 对称的因为a≡b modk 时存在某m∈I使a-b m·k于是b-a -m·k因此b≡amodk iii 传递的设a≡b modk 和b≡c modk 那么存在m1m2∈I使a-b m1k和b-c m2·k将两等式两边相加得a-c m1m2 ·k所以a≡c modk 例35-2 a 若R是I上模4等价关系则〔0〕4 -8-4048 〔1〕4 -7-3159 〔2〕4 -6-22610 〔3〕4 -5-13711 b 若R是I上模2等价关系则〔0〕2 -4-2024 〔1〕2 -3-1135 每⼀集合中的数相互等价 c 时钟是按模12⽅式记数的设备13点钟和1点钟有相同的记数定义35―3 设R是集合A上等价关系对每⼀a∈Aa关于R的等价类是集合 x｜xRa 记为〔a〕R简记为〔a〕称a为等价类〔a〕的表⽰元素如果等价类个数有限则R的不同等价类的个数叫做R的秩否则秩是⽆限的对每⼀a∈A等价类〔a〕R⾮空因为a∈〔a〕R 例 35-3 1 如图35―2设A abcdef R 〈aa〉〈bb〉〈cc〉〈ab〉〈ba〉〈ac〉〈ca〉〈bc〉〈cb〉〈dd〉〈ee〉〈de〉〈ed〉〈ff〉则等价关系R的等价类如下〔a〕〔b〕〔c〕 abc 〔d〕〔e〕 de 〔f〕 f等价关系R的秩是3 2 I上模4等价的等价类是〔0〕4〔1〕4〔2〕4〔3〕4 参看例2 a I上模2等价的等价类是〔0〕2 〔1〕2 参看例2 b3 集合A上相等关系的秩等于A的元素个数定理35―2 设R是⾮空集合A上的等价关系aRb 当且仅当〔a〕〔b〕证充分性因为a∈〔a〕〔b〕即a∈〔b〕所以aRb 定理35―3设R是集合A上的等价关系则对所有ab∈A或者〔a〕〔b〕或者〔a〕∩〔b〕证如果A 断⾔⽆义地真现设A≠若〔a〕∩〔b〕≠则存在某元素c∈〔a〕和c∈〔b〕根据定理35―2得〔a〕〔c〕〔b〕⼜因〔a〕和〔b〕都⾮空〔a〕∩〔b〕和〔a〕〔b〕不能兼得因⽽定理得证定义35― 4 给定⾮空集合A和⾮空集合族πA1A2Am 如果那么称集合族π是A的覆盖定理35―4设R是集合A上的等价关系则证先证定理35―5设R1和R2是集合A上的等价关系那么R1 R2当且仅当〔a〕R1｜a∈A 〔a〕R2｜a∈A 证必要性因为R1 R2所以对任意a∈A有〔a〕R1 x｜xR1a x｜xR2a〔a〕R2 故〔a〕R1｜a∈A 〔a〕R2｜a∈A 充分性因为〔a〕R1｜a∈A 〔a〕R2｜a∈A 得〔a〕R1 〔a〕R2所以对任意x∈A 有xR1a x∈〔a〕R1 x∈〔a〕R2 xR2a ⼜a是任意的故R1 R2证毕定理35―6 设R是A上的⼆元关系设R′ tsr R 是R的⾃反对称传递闭包那么 a R′是A上的等价关系叫做R诱导的等价关系 b 如果R〃是⼀等价关系且R〃R那么R〃R′就是说R′是包含R的最⼩等价关系证 a 根据闭包运算的定义和定理33―9可得 r R 是⾃反的 sr R是⾃反的和对称的 tsr R 是⾃反的对称的和传递的因此R′ tsr R 是A上的等价关系 b 设R〃是任意的包含R的等价关系那么R〃是⾃反的和对称的所以R〃R∪∪E sr R 因为R〃是传递的且包含sr R 所以R〃包含tsr R 证毕例4设A abc 且A上的⼆元关系R如图35―3所⽰则tsr R 如图35―4所⽰352 划分定义35―5给定⾮空集合A和⾮空集合族π A1A2Am 如果 i π是A的覆盖即ii Ai∩Aj Φ或Ai Aj ij 12m 那么集合族π叫做集合A的⼀个划分划分的元素Ai称为划分π的块如果划分是有限集合则不同块的个数叫划分的秩若划分是⽆限集合则它的秩是⽆限的划分的秩就是划分的⼤⼩例35-5 1 设S 123 有 A 12 23B 1 12 13C 1 23D 123E 1 2 3F 1 12 2 将⼀张纸撕成⼏⽚则所得的各个碎⽚是该纸的。
2017年中国科学技术大学0812计算机科学与技术考研专业目录及考试科目一、报考说明：接收推免生及统考生。
二、专业介绍：本学科培养学生德、智、体全面发展，适合于在高等学校、科研机构、企事业单位从事计算机系统结构相关领域的教学、科研和应用开发等工作的高层次专门人才。
掌握计算机学科方面坚实的基础理论和系统的专门知识，了解本学科的发展方向及前沿动向，具备较强的综合运用所学理论知识从事科学研究工作和独立承担专门技术工作的能力，有严谨求实的科学作风和良好的科研道德，开拓进取的创新精神，团队合作和敬业精神。
熟练掌握一门外国语，能阅读本专业的外文资料并撰写专业领域外文文章。
具有较强的综合能力、语言表达能力及写作能力；具有健康的体魄和良好的心理素质。
本学科点具有计算机系统结构、计算机软件与理论、计算机应用技术以及信息安全4个二级学科。
相应的研究方向如下：1、计算机系统结构计算机系统结构是计算机科学技术最活跃的研究领域之一，特别是最近几年，随着高性能计算机的广泛研究和应用、计算机整体设计关键技术的突破、计算机网络体系结构的迅速发展，计算机系统结构的研究出现了新的热点和重大进展。
在微处理芯片体系结构方面主要研究新型微处理芯片体系结构及其编程技术，可重构的片上并行体系结构，通用微处理芯片设计技术，指令级并行关键技术和嵌入式系统整体设计方法，多处理器体系结构等；在计算机体系结构方面主要研究新型高效能并行计算机体系结构、模型及其关键技术，包括软件技术、超高扩展高密度计算技术、高可用集群中间件技术、可重构计算等，“并行结构-并行算法-并行编程”研究一体化；在网络及分布式计算方面主要研究新型网络体系结构和协议，网格计算平台及应用，对等网络、无线网络和移动计算等。
2、计算机软件与理论计算机软件与理论是指由计算机科学理论和研究、开发计算机软件所涉及的理论、方法、技术所构成的学科，是信息科学的核心研究领域之一，是计算机学科用来为国民经济、国防建设、人民生活服务的工具和基础。
《离散数学》课程教学大纲模板（黑体 小三号 居中）（以下标题为黑体小四号，行距为18磅，内容为宋体五号）一、课程定位本课程的授课对象、课程的基本描述(课程的性质、任务、与其它课程的关系等)和在人才培养过程中的地位和作用。
《离散数学》是计算机科学以及相关专业重要的专业基础课。
包括的主要内容有：数理逻辑、集合论、二元关系、函数和图论等。
它以研究离散量的结构和相互关系为主要目标，通过该课程的学习，培养学生抽象思维和严密的逻辑推理能力，为进一步学习其它专业课打好基础，并为学生今后处理离散信息，提高专业水平，从事计算机或者相应专业以及实际工作提供必备的数学工具。
二、教学目标学生通过学习该课程后，在思维、知识和能力等方面应达到的目标。
1. 有效地掌握该门课程中的所有概念。
通过讲课和布置一定数量的习题使学生能够使用所学的概念对许多问题作出正确的判断。
2. 通过课程中许多定理的证明过程复习概念，了解证明的思路，学会证明的方法，并使学生掌握定理的内容和结果。
3. 通过介绍各种做题的方法，启发学生独立思维的能力。
创造性的提出自己解决问题的方法，提高学生解决问题的能力。
4.通过该门课程的学习使学生掌握逻辑思维和逻辑推理的能力，培养学生正规的逻辑思维方式。
课程名称：离散数学/ Discrete Mathematics课程编码： 20019703总学时数/学分数：专业基础课 实验学时：0上机学时：0 课程所属部门：信息技术工程学院 适用专业：计算机科学与技术、网络工程、软件工程及相关专业课程负责人：制定日期：2017年3月说明：1.实验和上机内容只填写项目名称及学时，具体内容和要求见实验大纲。
2.教学要求分章节按“了解”、“理解”、“掌握”三个层次编写教学内容及要求。
“了解”是指学生应能辨认的科学事实、概念、原则、术语，知道事物的分类、过程及变化倾向，包括必要的记忆；“理解”是指学生能用自己的语言把学过的知识加以叙述、解释、归纳，并能把某一事实或概念分解为若干部分，指出它们之间的内在联系或与其它事物的相互关系；“掌握”是指学生能根据不同情况对某些概念、定律、原理、方法等在正确理解的基础上结合事例加以运用，包括分析和综合。
兰州大学信息科学与工程学院2014年硕士招生参考书目2013-09-12电子线路《数字电子技术基础》，阎石主编，高等教育出版社，2006.5年第5版《模拟电子技术基础》，华成英、童诗白主编，高等教育出版社，2006年第4版《电子技术基础》（模拟部分），康华光主编，高等教育出版社，1999年第4版《模拟电子线路》，杨凌编著，机械工业出版社，2007年第1版电磁场与通信原理《电磁场与电磁波》，许福永、赵克玉主编，科学出版社，2005年版《电磁场理论基础》，王蔷等编著，清华大学出版社，2001年版《通信原理》（上、下册），周炯磐、庞沁华、续大我、吴伟陵编著，北京邮电大学出版社，2002—08—01版微机原理及应用《微机原理及应用(第三版)》，马义德等编，高等教育出版社2004年3版信号与系统《信号与系统》郑君里等主编，高等教育出版社，2000年第2版数字信号处理《数字信号处理教程》，程佩青主编，清华大学出版社，2001年2版离散数学《离散数学》，方世昌编，西安电子科技大学出版社，2000年版数据结构《数据结构》，严蔚敏主编，清华大学出版社，第2版操作系统《计算机操作系统》，汤子瀛等编著，西安电子科技大学出版社，2002年修订版计算机组成原理《计算机组成原理》，白中英主编，科学出版社，2001年1月第3版医学生物化学《生物化学》，主编周爱儒，人民卫生出版社，第6版人体生理学《生理学》，主编姚泰，人民卫生出版社，第6版医学影像学《医学影像学》，主编吴恩惠，人卫出版社（五版）病理学《病理学》，主编李玉林，人民卫生出版社，第6版信号处理《数字信号处理》(Understanding Digital Signal Processing)，RICHARD G.LYONS著，机械工业出版社，2006年2版《现代数字信号处理》(Modern Digital Signal Processing),ROBERTO CRISTI 著，机械工业出版社，2003年1版数据结构与编译原理《数据结构与算法分析－C＋＋描述》（英文版第3版）Mark Weiss著，人民邮电出版社，2006年《编译器构造：C语言描述》（英文版）C.Fisher等著，机械工业出版社，2005年计算机《计算机系统结构》，石教英著，浙江大学出版社，1998年1版《计算机网络：自顶向下方法与Internet特色（原书第3版）》，（美）库罗斯（Kurose，J.F.）等著，陈鸣等译，机械工业出版社，2005年1版《计算机网络（第5版）》，谢希仁编著，电子工业出版社，2008年版《计算机网络系统方法（英文版·第4版）》，Larry L. Peterson and Bruce S. Davie著，机械工业出版社，2007年版。
《失散数学》期末复习概要《失散数学》是中央电大“数学与数学应用专业”（本科）的一门选修课。
该课程使用新的教课纲领，在原有失散数学课程的基础上减少了教课内容（主假如群与环、格与布尔代数这两章及图论的后三节内容），使用的教材为中央电大第一版的《失散数学》（刘叙华等编）和《失散数学学习指导书》（虞恩蔚等编）。
失散数学主要研究失散量构造及互相关系，使学生获得优秀的数学训练，提升学生抽象思想和逻辑推理能力，为从事计算机的应用供给必需的描绘工具和理论基础。
其先修课程为：高等数学、线性代数；后续课程为：数据构造、数据库、操作系统、计算机网络等。
课程的主要内容1、会合论部分（会合的基本观点和运算、关系及其性质）；2、数理逻辑部分（命题逻辑、谓词逻辑）；3、图论部分（图的基本观点、树及其性质）。
学习建议失散数学是理论性较强的学科，学习失散数学的要点是对失散数学（会合论、数理逻辑和图论）相关基本观点的正确掌握，对基来源理及基本运算的运用，并要多做练习。
教课要求的层次各章教课要求的层次为认识、理解和掌握。
认识即能正确鉴别相关观点和方法；理解是能正确表达相关观点和方法的含义；掌握是在理解的基础上加以灵巧应用。
一、各章复习要求与要点第一章集合[复习知识点]1、会合、元素、会合的表示方法、子集、空集、全集、会合的包含、相等、幂集2、会合的交、并、差、补等运算及其运算律（互换律、联合律、分派律、汲取律、DeMorgan律等），文氏（Venn）图3、序偶与迪卡尔积本章要点内容：会合的观点、会合的运算性质、会合恒等式的证明[复习要求]11、理解会合、元素、子集、空集、全集、会合的包含、相等、幂集等基本观点。
2、掌握会合的表示法和会合的交、并、差、补等基本运算。
3、掌握会合运算基本规律，证明会合等式的方法。
4、认识序偶与迪卡尔积的观点，掌握迪卡尔积的运算。
[本章要点习题]P5~6，4、6；P14~15，3、6、7；P20，5、7。
