多商城入住网站建设,软件开发流程教程,网站空间商查询,做减肥网站来源#xff1a;北京大学《离散数学》公开课地址#xff1a;https://www.bilibili.com/video/av18896337/?p122.1 有序对和卡氏积有序对a,b#xff1a;有顺序#xff0c;类似于数组#xff0c;可以用集合定义。性质#xff1a;有序对内元素对应相等卡氏积AB北京大学《离散数学》公开课地址https://www.bilibili.com/video/av18896337/?p122.1 有序对和卡氏积有序对a,b有顺序类似于数组可以用集合定义。性质有序对内元素对应相等卡氏积A×B所有元素一个来自A集合另一个来自B集合的有序对性质不满足交换律不满足结合律对并和交满足分配律具有单调性证明见北大教材p252.2 二元关系A到B的二元关系定义A×B的任一子集即A×B幂集中的一个元素组成的集合注意二元关系也是集合A到B的二元关系的总个数|P(A×B)|A上的特殊二元关系空关系、恒等关系、全域关系、整除关系大于小于关系包含关系只有包含关系定义在幂集P(A)上见p26定义域、值域、域由二元关系定义的集合关系的特殊情况F是单根的、F是单值的即F定义了一个函数二元关系的运算逆F^-1将关系集合中所有的有序对反向逆序合成FoG有公共中间元素的有序对的集合限制F↑Ax属于A的关系集合象F[A]F↑A的值域定义域为A的有序对集合对应的值域合成运算定理1合成运算结合律重要合成运算定理2A与B合成运算的逆B逆与A逆的合成运算2.3 关系的表示和关系的性质关系矩阵图的矩阵表示关系图关系的性质自反性每个点都有环反自反性每个点都没有环对称性任意两点间要么有两条边要么没边反对称性任意两点间都没有两条边传递性可走捷径注意考虑有环的情况2.4 关系幂运算和关系闭包一关系幂关系R的n次幂R与自己合成n次后得到的关系集合。也可以理解为G(R)中长度为n的路径的起点和终点组成的有序对的集合关系幂具有指数律R^m * R^n R^(mn)(R^m)^nR^(mn)二闭包R的闭包的定义包含R满足给定性质最小的有序对集合包含于任意一个闭包的种类自反闭包r(R)对称闭包s(R)传递闭包t(R)3. 闭包运算的性质定理2.19闭包运算有不动点定理2.20闭包运算有单调性即较大的集合的闭包也较大定理2.21闭包运算对自反闭包和对称闭包的并有分配律对传递闭包的并没有分配率4. 闭包的集合求法定理2.22自反闭包R U 恒等关系定理2.23对称闭包R U R的逆定理2.24传递闭包R U R^2 U R^3 U.....求传递闭包就是把从此点可走到的点直接连起来5. 闭包的图求法自反闭包所有定点加环对称闭包所有单向边化为双向边传递闭包遍历所有点把从此点可达到的点直接与此点连起来6. 闭包的矩阵求法自反闭包主对角线全部改成1对称闭包改为对称矩阵传递闭包矩阵R 逻辑或 矩阵R^2 逻辑或 矩阵R^3........逻辑或指对所有运算式中的矩阵的每个对应位置上的元素进行或运算7. 定理2.25求闭包后关系性质是否改变自反性在求闭包后保持不变对称性在求闭包后保持不变传递性在求对称闭包后可能改变反例a-b具有传递性但它的对称闭包为a-b不具有传递性因为a到a要两步才能达到8. 定理2.26闭包运算的交换律求自反闭包和对称闭包运算可交换求自反闭包和传递闭包运算可交换求对称闭包和传递闭包运算不可交换其中先求传递闭包再求对称闭包得到的闭包较大2.5 等价关系和划分等价关系定义等价关系R是自反对称传递的二元关系用等价关系分类空关系不是等价关系、恒等关系是等价关系把每个元素自己分成一类、全域关系是等价关系把所有元素分成一类2. 等价类R的等价类定义所有与x有R关系的y的集合记为[x]等价类的一个例子R为除以3后的同余关系即x与y除以3的余数相等可证除以n后的同余关系为等价关系证xRy等价于关系式x-yk*n, 其中k为整数。由定义易证此关系式满足自反性、对称性传递性现取dom{1,2,3,4,5}那么有等价类[1][4]{1,4}1,4是一个等价类余数都是1[2][5]{2,5}2,5是一个等价类余数都是2[3]{3}3是一个等价类余数都是0在G(R)上可观察到1,42,53分别满足全域关系所有的点之间连通即每个等价类内部具有全域关系由此性质可知得到关系的等价类后就可以直接推导出所有的关系等价类的性质定理2.27非空由于等价关系需满足自反性所以等价类中至少包含x自己若xRy则[x]R[y]R因为等价关系R满足对称性和传递性。由对称性y与x有关由传递性y与x有关x与其他元素有关则y与所有与x有关的元素有关。反之x与所有与y有关的元素有关所以x与y的相关元素相同若x和y无关则[x]R与[y]R不相交反证法若[x]R与[y]R有一个共同元素z那么参考2的思路由对称性和传递性可得x和y必有关所有等价类的并为A结论显而易见严格证明用集族的单调性因为每个等价类都包含于A所以所有等价类的并包含于A的并即A自己可见等价类是对A的一个划分A的每个元素都只在其中一个等价类中且等价类的并为A而等价关系确定等价类的基础。一切划分从确定一个自反、对称、传递的等价关系开始。 插一句题外话等价类让我想起了麦肯锡咨询里的一个原则MECEMutually Exclusive Collectively Exhaustive相互独立、完全穷尽。麦肯锡把这个原则视为咨询的黄金法则其实也就是离散数学中的划分等价类。可见许多商业逻辑的原型都是数学。3. 商集定义A/RA上R的等价类组成的集合就是A用R划分的结果例子对应刚刚等价类中的那个例子{{1,4}{2,5}3}A上的等价关系有IA 恒等关系E 全域关系Rij IA U {ai,aj,aj,ai} 其中i不等于j即所有点都有环并且i和j结点有双向边。易证自反对称传递空关系不是等价关系对应的商集A/IA {{a1},{a2},...{an}}A/E {{a1,a2,...,an}}A/Rij ai和aj为一类其他元素各成一类例子求A{a,b,c}的等价关系5种和商集5个4. 划分和商族等价定义A的一个划分是A的一个包含于A幂集的集族满足集族中每个集合非空、集族中每个集合不相交集族的并为A定理2.28R为A上的等价关系-A/R是A的划分A是A的划分-A的同块关系即划分出的其中一个集合的关系是A上的等价关系Stirling子集数2.6 序关系一偏序偏序关系R自反、反对称反对称指若xRy且yRx则xy、传递则称R为偏序关系xRy记作x≤y2. 偏序集一个带有偏序关系≤的集合A即为偏序集记作A,≤3. 加细关系划分x包含于划分y则x是y的加细xRy成立4. 可比x≤y或y≤x则x和y可比5. 覆盖x≤y且x!y则y覆盖x6. 哈斯图具有偏序关系的两个结点相连接其中若y覆盖x则y置于x上方哈斯图可用于绘制组织框架图7. 全序关系偏序集A中任意元素之间都可比则A,≤为全序集等价于哈斯图为直线二拟序拟序关系R反自反、传递蕴含了R是反对称的2. 定理2.30拟序关系有三歧性要么xy要么yx要么xy(xy v x y) ∧ (yx v x y) - xy以下4组概念可以类比高数中的最大值最小值等严格定义见p523. 最大元最小元4. 极大元极小元5. 上界下界6. 上确界下确界7. 链反链偏序集中两两都可比就是链否则是反链总结偏序是自反传递反对称。实数上的小于等于是偏序关系拟序是反自反传递反对称。实数上的小于是偏序关系3.1 函数一函数的基本概念函数FF为一个二元关系且F是单值的单值domF中每个x至多对应ranF中一个y偏函数domF包含于AranF包含于B即A中每个x在F上不一定有B中对应的y严格定义见p58真偏函数在偏函数的基础上domF真包含于A即A中一定有x在F上没有有B中对应的y严格定义见p58全函数A中每个x在F上一定有B上对应的y之后讨论的都是全函数上的情况二函数的性质单射F是单根的满射值域B双射x和y一一对应象和原象特征函数单调函数定义在任意的偏序关系上自然映射f: A-A/R映射到等价类上函数的合成反函数4.1 自然数的定义封闭F是函数F(A)属于A - F是A上的一元运算皮亚诺系统M,F,e F:M-MF是单射e不属于F的值域e属于MM最小M在F下封闭后继运算AA U {A}归纳集D集合D含有空集合且对后继运算封闭自然数用集合定义属于每个归纳集的集合。从空集合出发做有限次后继运算的集合一定是自然数集0对应空集合1对应空集合的后继以此类推自然数集N包含于每个归纳集的集合。N归纳集D的广义交后继函数N-N后继函数是单射定理4.1 自然数集是归纳集定理4.2 N,后继函数,0为皮亚诺系统定理4.3 任何自然数的元素均为它的子集定理4.4 m,n属于自然数集m的后继属于n的后继 等价于 m属于n定理4.5 任何自然数都不是自己的元素定理4.6 空集属于除0以外的任何自然数定理4.7 单歧性m属于nmn和n属于m有且仅有一个成立4.2 自然数的性质传递集A中的任何元素也是A的元素自然数是传递集定理4.10A是传递集等价于A的广义并包含于A等价于y属于A有y包含于A等价于A包含于P(A)定理4.11A为传递集等价于P(A)为传递集定理4.12A为传递集等价于A后继运算的广义并为A定理 4.13每个自然数都是传递集自然数集合N时传递集自然数集上的二元运算加法乘法5.1 集合的等势等势A与B等势存在f使A-B双射eg.整数集和自然数集是等势的康托定理任何的集合A和它的幂集P(A)之间都不能建立双射有穷集与某个自然数等势的集合不能与自己的真子集建立双射的集合无穷集不能与自然数等势的集合5.2 基数集合等势则基数card相同对自然数集NcardN N(阿列夫)card A Ni, 则card P(A) Ni1
