《软件数学基础》辅导3 集合论.doc

羈膅蒈螂肀肈莄螁螀芄芀螀袂肆薈蝿羅节蒄袈肇肅莀袇螇芀芆蒄衿肃膂蒃肁荿薁蒂螁膁蒇蒁袃莇莃蒀羆膀艿葿肈羂薇蕿螈膈蒃薈袀羁荿薇羂膆莅薆螂罿芁薅袄芅薀薄羆肇蒆薄聿芃莂薃螈肆芈蚂袁芁膄蚁羃肄蒃蚀蚃艿葿虿袅肂莅蚈羇莈芁蚈肀膁蕿蚇蝿羃蒅蚆袂腿莁螅羄羂芇螄蚄膇膃螃螆羀薂螂羈膅蒈螂肀肈莄螁螀芄芀螀袂肆薈蝿羅节蒄袈肇肅莀袇螇芀芆蒄衿肃膂蒃肁荿薁蒂螁膁蒇蒁袃莇莃蒀羆膀艿葿肈羂薇蕿螈膈蒃薈袀羁荿薇羂膆莅薆螂罿芁薅袄芅薀薄羆肇蒆薄聿芃莂薃螈肆芈蚂袁芁膄蚁羃肄蒃蚀蚃艿葿虿袅肂莅蚈羇莈芁蚈肀膁蕿蚇蝿羃蒅蚆袂腿莁螅羄羂芇螄蚄膇膃螃螆羀薂螂羈膅蒈螂肀肈莄螁螀芄芀螀袂肆薈蝿羅节蒄袈肇肅莀袇螇芀芆蒄衿肃膂蒃肁荿薁蒂螁膁蒇蒁袃莇莃蒀羆膀艿葿肈羂薇蕿螈膈蒃薈袀羁荿薇羂膆莅薆螂罿芁薅袄芅薀薄羆肇蒆薄聿芃莂薃螈肆芈蚂袁芁膄蚁羃肄蒃蚀蚃艿葿虿袅肂莅蚈羇莈芁蚈肀膁蕿蚇蝿羃蒅蚆袂腿莁螅羄羂芇螄蚄膇膃螃螆羀薂螂羈膅蒈螂肀肈莄螁螀芄芀螀袂肆薈蝿羅节蒄袈肇肅莀袇螇芀芆蒄衿肃膂蒃肁荿薁 罿袀腿薀袅衿节螅螁罿莄薈蚇羈蒆莁羆羇芆薆羂羆莈葿袈羅蒀蚄螄羄膀蒇蚀羃节蚃羈羃莅蒆袄肂蒇蚁螀肁膇蒄蚆肀荿虿蚂聿蒁薂羁肈膁螈袇肇芃薀螃肇莆螆虿膆蒈蕿羇膅膈莂袃膄芀薇蝿膃蒂莀螅膂膂蚅蚁膁芄蒈羀膁莆蚄袆膀葿蒆螂艿膈蚂蚈芈芁蒅羇芇莃蚀袃芆薅蒃衿芆芅蝿螅袂莇薁蚁袁蒀螇罿袀腿薀袅衿节螅螁罿莄薈蚇羈蒆莁羆羇芆薆羂羆莈葿袈羅蒀蚄螄羄膀蒇蚀羃节蚃羈羃莅蒆袄肂蒇蚁螀肁膇蒄蚆肀荿虿蚂聿蒁薂羁肈膁螈袇肇芃薀螃肇莆螆虿膆蒈蕿羇膅膈莂袃膄芀薇蝿膃蒂莀螅膂膂蚅蚁膁芄蒈羀膁莆蚄袆膀葿蒆螂艿膈蚂蚈芈芁蒅羇芇莃蚀袃芆薅蒃衿芆芅蝿螅袂莇薁蚁袁蒀螇罿袀腿薀袅衿节螅螁罿莄薈蚇羈蒆莁羆羇芆薆羂羆莈葿袈羅蒀蚄螄羄膀蒇蚀羃节蚃羈羃莅蒆袄肂蒇蚁螀肁膇蒄蚆肀荿虿蚂聿蒁薂羁肈膁螈袇肇芃薀螃肇莆螆虿膆蒈蕿羇膅膈莂袃膄芀薇蝿膃蒂莀螅膂膂蚅蚁膁芄蒈羀膁莆蚄袆膀葿蒆螂艿膈蚂蚈芈芁蒅羇芇莃蚀袃芆薅蒃衿芆芅蝿螅袂莇薁蚁袁蒀螇罿袀腿薀袅衿节螅螁罿莄薈蚇羈蒆莁羆羇芆薆羂羆莈葿袈羅蒀蚄螄羄膀蒇蚀羃节 蒅莆蚅肅莁蒅螇芁芇蒄衿肃膃蒃羂袆薁蒂螁膂蒇蒂袄羅莃蒁羆膀艿蒀蚆羃膅葿螈膈蒄薈袀羁莀薇羃膇芆薆蚂罿节薆袅芅膈薅羇肈蒆薄蚆芃莂薃蝿肆芈薂袁芁膄蚁羃肄蒃蚀蚃袇荿蚀螅肃莅虿羈袅芁蚈蚇膁膇蚇螀羄蒆蚆袂腿莂蚅羄羂芈螄蚄膇膃螄螆羀蒂螃衿膆蒈螂肁罿莄螁螁芄芀莈袃肇膆莇羅节蒅莆蚅肅莁蒅螇芁芇蒄衿肃膃蒃羂袆薁蒂螁膂蒇蒂袄羅莃蒁羆膀艿蒀蚆羃膅葿螈膈蒄薈袀羁莀薇羃膇芆薆蚂罿节薆袅芅膈薅羇肈蒆薄蚆芃莂薃蝿肆芈薂袁芁膄蚁羃肄蒃蚀蚃袇荿蚀螅肃莅虿羈袅芁蚈蚇膁膇蚇螀羄蒆蚆袂腿莂蚅羄羂芈螄蚄膇膃螄螆羀蒂螃衿膆蒈螂肁罿莄螁螁芄芀莈袃肇膆莇羅节蒅莆蚅肅莁蒅螇芁芇蒄衿肃膃蒃羂袆薁蒂螁膂蒇蒂袄羅莃蒁羆膀艿蒀蚆羃膅葿螈膈蒄薈袀羁莀薇羃膇芆薆蚂罿节薆袅芅膈薅羇肈蒆薄蚆芃莂薃蝿肆芈薂袁芁膄蚁羃肄蒃蚀蚃袇荿蚀螅肃莅虿羈袅芁蚈蚇膁膇蚇螀羄蒆蚆袂腿莂蚅羄羂芈螄蚄膇膃螄螆羀蒂螃衿膆蒈螂肁罿莄螁螁芄芀莈袃肇膆莇羅节蒅莆蚅肅莁蒅螇芁芇蒄衿肃膃蒃羂袆薁蒂螁膂蒇蒂袄羅莃蒁羆膀艿蒀蚆羃膅葿螈 软件数学基础辅导3 集合论第6章 集 合一.主要内容 1.集合的概念与表示方法：集合、元素、子集、空集、全集、相等、幂集等概念；集合的表示方法.2.集合的运算：集合的交、并、差、补的概念.3.集合的运算性质：交换律、结合律、分配律、吸收律、 De Morgan律.4.有限集合计数的原理.二.学习要求1.掌握子集、空集、全集、相等、幂集等基本概念和集合的表示法.2.掌握集合的交、并、差、补等概念. 3.掌握交换律、结合律、分配律、De Morgan律等运算律.会证明简单的集合等式. 4.熟练掌握有限集合的计数原理和公式.三. 学习重点1. 正确理解集合的概念, 熟悉集合的有关记号: (A) A Ac2. 熟悉集合的运算和性质, 尤其是De Morgan律.3. 会证明一些简单的集合等式.4. 熟练掌握集合计数的容斥原理. 四. 重、难点解析（一）集合的概念及表示法 1集合的概念 集合的概念是通过描述而建立的, 一般都把集合描述成 “具有某种特定性质的事物的全体”. 这不能算是一个严格的定义, 因为它是用 “全体” 这个概念来说明 “集合” 这个概念. 尽管集合的概念严格来说是无法定义, 这一点非常类似于几何当中“点”的概念, 社会学当中“人”的概念, 你可以描述它, 但是无法给出一个严格确切的定义. 2集合的表示法（1）列举法: 明确列举出集合的全部元素. 一般形式为: .列举法的优点是能够做到集合的元素一览无遗, 不足是不一定能体现出集合中元素的共有特征性质, 也就是集合中元素也只有集合中的元素才具有的性质或者满足的条件, 再者, 如果集合含元素的个数, 如果很大, 列举出所有元素从理论是来说是可能的, 但是实际上做不到. 采用这种方式表示集合的时候, 有两点需要注意. 第一, 集合中元素的次序是无关紧要的. 比如1, 3, 2, 3, 2, 1, 2, 1, 3, 3, 1, 2都表示的是同一个集合A1, 2, 3. 第二, 集合中一个元素只关心是否出现, 不关心重复次数. 比如, 1, 2, a, b, a, b1, 2, a, b. 因此, 在集合的显式表示中, 应尽量避免元素重复出现. （2）描述法: 明确给出一项法则来决定一个事物是否属于这个集合. 一般形式为: . 描述法的优点是集合中元素的特征性质一目了然. 比如, 下列集合只能采用描述法 :闭区间1, 2=x | 1 x 2; Z+ = x | x是正整数;N = x | x是正整数或者0;Z = x | x是整数; Q = x | x是有理数;R = x | x是实数;C = x | x是复数. 几个特殊集合: n 空集n 全集Un 一个集合A的幂集(A). 全集和空集是两个最重要的特殊集合. 空集是唯一的. 全集随所考虑到问题不同而可能有所不同. 这一点要特别注意. 一般全集必须明确指定或者必须能根据上下文明确看出. 尤其在遇到补运算的时候, 必须有明确的全集. 一个集合A的幂集(A)也可以表示为: 2A. (二) 集合间的关系两个集合A, B之间主要有以下几种关系: (1) AB. (2) BA.(3) A=BAB且BA.(4) AB, 即, AB且AB.(5) BA, 即, BA且AB.(6) AB=(7) AB, 但是A-B, B-A.以上关系可以通过画出文氏图来正确理解, 例如, (7) AB=的文氏图如下:(三) 集合的运算 设集合A, B都是全集U的子集, 那么集合的几种常见运算可分别表示如下:交: AB=x x A且x B.并: AB=x| xA 或 xB.差: A-B=x|xA且xB.补: A=U-A=x | xU且xA. 集合A的补集也称为余集, 也可记为或者Ac.对称差: AB=(A-B)(B-A)=x | xA且xB, 或xA且xB.(四) 集合运算的性质集合运算大部分的性质都是一目了然的, 非常简单. 可以借助文氏图来认识和理解, 但是这些性质都有严格的证明, 图示不能代替证明. 下面列举了一些重要性质. 幂等律: AA=A, AA=A. 幂零律: AA=. 结合律: (AB) C=A(BC), (AB) C=A (BC), (AB)C=A(BC).交换律: AB=BA, AB=BA, AB=BA.同一律: AU=A, A=A, A=A.零 律: A=, AU=U.分配律: A(BC)=(AB)(AC), A(BC)=(AB)(AC).吸收律: A(AB)=A, A(AB)=A.矛盾律: AA=.排中律: AA=U.德摩根律: (a) (AB)=AB; 或.(b) (AB)=AB; 或 德摩根律可以推广到三个集合的情况:也可以推广到任意有限个集合的情况. (五) 集合计数的容斥原理设A是一个有限集合,用|A|来表示集合A所包含的不同元素的个数. 计算一个集合所包含的元素个数, 是一个很重要的问题. 这里我们只介绍了集合计数最简单的一个原理,也就是容斥原理, 这个原理主要用来计算若干个集合的并或者交所含元素个数. 1. 两个集合的容斥原理: 设A, B是两个有限集合. |AB| = |A| + |B| - |AB|.下面用文氏图来对三个集合的容斥原理来加以解释: 图中AB=AB.2.三个集合的容斥原理: 设A, B, C是三个有限集合.|ABC|= |A| +|B| + |C| -|AB| -|AC| -|BC| + |ABC|.下面用文氏图来对三个集合的容斥原理来加以解释: 图中AB=AB, AC=AC, BC=BC, ABC=ABC.3.n个集合的容斥原理*: 设A1, A2, , An是有限集合, 则有 容斥原理在集合计数问题中十分有用. 只要记住通过画出文氏图来理解容斥原理的方法, 就很容易掌握这个原理. 教材中也有不少的例子, 同学们可以参阅.五. 典型例题 例1 设A=a, b, a, 判断下列结论是否正确:(1) aA. (2) aA. (3) aA. (4) bA. (5) a=a. 解 (1) 正确. 因为a是集合A的元素.(2) 正确. 因为a是集合A的元素.(3) 正确. 因为a是集合A的元素.(4) 错误. 因为b不是A的元素.(5) 错误. 因为a和a是两个不同的元素.例2设A-B=, 则下列仅有( )成立.(A) B= (B) B (C) AB (D) BA 分析 根据集合差的含义, A-B=x|xA且xB=, 意味着不存在属于A而不属于B的元素, 换句话说, A中的元素都是B的元素. 解 正确答案为(C). 例3对于任意集合A、B、C, 下述结论正确的是( ).(A) 若AB, BC, 则AC.(B) 若AB, BC, 则AC.(C) 若AB, BC, 则AC.(D) 若AB, BC, 则AC.解 只有(A)正确. 其余的自己设法举出反例. 例4 填空:(1) () = . (2) () = .(3) () = .解 (1) () =(2) () = , .(3) () = , , , , .例5 对A, B是任意集合, 证明A-B = A - (AB).分析 证明集合等式一般有两种方法, 一种是证明集合两边互相包含, 另一种是利用集合的运算规律. 对于大家来说, 可能不容易记清楚那么多运算规律, 所以我们掌握第一种方法就可以了. 证明 先证: A-B A - (AB). 设x A-B, 那么x A, xB, 所以x A, x AB, 即x A - (AB). 故有A-B A - (AB).再证: A-(AB) A - B.设x A - (AB), 那么x A, x AB. 必然有xB, 否则得到xAB, 矛盾! 既然x A, xB, 我们有x A - B. 故有A-(AB) A - B.综上, A-B = A - (AB). 例6求1到500之间被5整除或者能被7整除的整数的个数. 分析:直接应用集合计数的容斥原理的公式: |AB| = |A| + |B| - |AB|. 解 设A为能被5整除的整数集合, B为能被7整除的整数集合, 用x表示x的整数部分, 则有同时能被5和7整除的整数个数为 故能被5或能被7整除的整数个数为第7章 二元关系一、主要内容1.序偶与迪卡尔积2.关系的概念和性质：二元关系、关系矩阵与关系图。3.复合关系与逆关系 4.关系的自反性、对称性与反对称性、传递性。5.等价关系与等价类。6.偏序关系、偏序集、哈斯图、序关系、序集。7.函数、复合函数、反函数、单射、满射、双射。二、学习要求1.理解序偶与迪卡尔积的概念。2.理解关系的概念,练掌握关系矩阵与关系图。3.理解复合关系与逆关系的概念，掌握其求法。4.熟练掌握等价关系的概念；会判断等价关系。5.了解偏序关系、偏序集的概念，会用哈斯图表示；6.了解函数、复合函数与反函数的概念；掌握单射、满射、双射的判断方法。 7.知道序关系与序集的概念。 三、学习重点1. 知道关系的三种不同的表示方式, 会求给定关系的关系矩阵和关系图.2. 会判断给定关系是否具有某种特殊性质.3. 能熟练判断给定集合A上的二元关系是否为等价关系.4. 会由等价关系确定划分, 也会由划分决定等价关系.5. 掌握偏序集合的概念, 会画偏序关系的Hasse图, 也会由Hasse图给出偏序关系. 四、重、难点解析(一) 集合的笛卡尔积设A, B是两个集合, 称集合(x, y) | xA, yB 为集合A与B的笛卡尔积, 记作AB, 集合AB中的元素叫做有序对. 笛卡尔积有如下简单性质:(1) 如果用|A|来表示集合A所含元素的个数, 那么| AB |=|A| |B|. (2) A=, A=.(3) AB= BAA=B或者A, B之中至少有一个为空集.(4) 笛卡尔积对并和交运算都满足分配律:A(BC) = (AB)(AC), (BC)A = (BA)(CA), A(BC) = (AB)(AC), (BC)A = (BA) (CA). (5) 如果AC, BD, 那么ABCD.请自己给出上述性质的证明. 尤其是应该给出最后一个命题的逆命题不成立的例子.(二) 集合上的二元关系我们主要研究给定集合A上的二元关系. 所谓集合A上的一个二元关系, 说通俗一点就是给定一个法则R, 对于A中任意两个元素a, b, 利用这个法则可以判定a与b是否具有关系R. 如果使用更数学化的语言来叙述, 就是: R就是AA的一个子集. 比较平凡的关系有: 空关系, 恒等关系, 全关系. 我们要研究关系所具备的一些常见性质. 这类似于我们研究函数的常见性质. 所有这些研究, 必须建立在对关系有一个比较方便的表示方式. 下面就是关系最常用的三种表示方式: 集合、关系矩阵和关系图, 其中关系矩阵和关系图只能用来表示有限集合A上的关系. 1. 集合表示法因为集合A上的关系R就是AA的一个子集, 这样作为集合的R当然也就可以用列举法和描述法来加以表示. 例如 A=2, 3, 4, 6, 对于A上的整除关系R, 我们可以用描述法也可以用列举法来表示这个关系:R=(a, b) | a, bA且a整除b 或R=(2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (6, 6).2. 矩阵表示法设R是从有限集合A=a1, a2, , am上的一个关系, 可以按照如下方式定义一个m阶矩阵:矩阵MR为R的关系矩阵. 用关系矩阵来表示二元关系, 非常方便. 上面例1中集合A=2, 3, 4, 6上的整除关系R的矩阵为:需要注意的是关系矩阵并不是绝对唯一的, 与集合A的元素次序有关系.矩阵表示法最大的优点是, 很容易判定关系是否满足自反性, 对称性, 反对称性. 对于传递性, 也可以通过计算关系矩阵的乘积来判定, 但是多少有点麻烦.3. 有向图表示法设R是从有限集合A=a1, a2, , am上的二元关系, 以A的元素为顶点, 用一个从a到b的箭头来表示aRb, 则可以得到一个有向图, 称为R的关系图.例如 设A=1, 2, 3, 4, R=(1, 1), (1, 2) , (1, 3), (2, 3), (2, 4), (3, 4), (4, 2), 则R的关系图为: (三) 关系的运算 既然关系可看作AA的子集, 因此可以说关系也是集合. 所以, 对于同一个集合A上的关系, 可以进行交、并、差、补等运算. 但是, 对于关系而言, 最重要的两种运算是逆运算和复合运算. 这两种运算可以帮助判断给定关系是否具有某种特殊的性质. 逆运算: 设RAA是集合A上的关系, 则R-1=(x, y) | (y, x)R称为R的逆关系. 复合运算: 设RAA, SAA是二元关系, 则T=(x, z)|$yB使得(x, y)R且(y, z)S称为R与S的复合关系, 记作T=RoS或T=RS. 逆关系十分容易确定. 考虑一下, 关系与其逆关系R-1关系矩阵和关系图有什么关系? 下面用一个简单例子来说明如何进行关系的复合运算. 例如 设A=a, b, c, d, 定义A上的关系R如下:R=(a, a) , (a, b), (b, d), (c, a), (d, c), 求复合关系R2=RoR.分析: 计算复合关系RoR一般有三种方法, 可以根据不同的情况选取不同的计算, 下面我们只采用其中一种, 其余见书中有关例题.解 根据关系R中所包含的有序对, 按照复合关系RoR的定义: (a,b), (b, c)R(a,c)R2. 由此可得R2=(a, a) , (a, b), (a, d), (b, c), (c, a), (c, b), (d, a). (四) 关系的常见性质对于集合A上的二元关系R, 我们最关系的性质有:自反性: 若对于任意的都有, 则称是A上的一个自反关系. 对称性: 若对于任意的都有“xRyyRx”, 则称R是A上的一个对称关系.传递性: 若对于任意的都有“xRy, yRzxRz”, 则称R是A上的一个传递关系.反对称性: 若对于任意的都有“xRy, yRxx=y”, 则称R为集合A上的一个反对称关系. 如何判断给定的二元关系是否具有上述某个性质? 可以根据关系的不同表示方式来加以考察. 1. 利用定义考察关系R的性质自反性: 对于任意aA, R必须包含(a, a). 即: IAR.对称性: 若R包含(a, b), 则R必须同时包含(b, a). 即: R-1=R.传递性: 若R包含(a, b), (b, c), 则R必须同时包含(a, c). 即: R2R.反对称性: 若R包含(a, b), 而且ab, 则R不能同时包含(b, a). 即: RR-1 IA.2. 利用关系矩阵MR考察关系R的性质自反性: MR主对角线元素必须都是1.对称性: MR必须是对称矩阵. 即: MRT=MR.传递性: MR-MR2不出现负数.反对称性: 若ij, (i, j)位置与(j, i)位置不能同时为1(但是可以同时为0).3. 利用关系图考察关系R的性质自反性: 每个顶点必须有环.对称性: 若从a到b有有向边, 则从b到a也必须有有向边.传递性: 若从a到b有有向边, 从b到c有有向边, 则必须有从a到c的有向边.反对称性: 若ab, 从a到b有有向边, 则不能有从b到a的有向边.以上方法可以说各有好处. 第一种容易理解, 第二种容易计算, 第三种比较直观. 如果所使用的计算机编程能力比较强, 不妨自己编写程序, 让计算机来判断关系是否具有某种性质. (五) 等价关系与集合的划分等价关系: 若集合A上的二元关系R具有自反性、对称性、传递性, 则称其为等价关系.等价关系是最常用也是最重要的二元关系. 我们熟悉的: 数的相等关系、直线的平行关系都是等价关系. 但是, 实数的小于等于关系、集合的包含关系都不是等价关系.划分: 若集合的一个非空子集族满足（1）; （2）, 则称是的一个划分. 设R是A上的等价关系, aA, 集合aR=xA | (x, a)R称为a所在的等价类. 设R是A上的等价关系, 则 集合上的一个等价关系可以唯一确定的一个划分：; 集合的一个划分也可以唯一确定上的一个等价关系：.认清等价关系与划分本质是一回事是理解这两个概念的关键.例如 考虑整数集合Z上模5同余关系R5. 这是一个等价关系, 即R5=(x, y) | x y (mod 5).这个等价关系刚好有下列5个等价类:(六) 偏序关系偏序关系: 若集合A上二元关系具有自反性、传递性、反对称性, 则称R为集合A上的一个偏序关系, 称A为带有偏序关系R的偏序集, 记作(A, ).偏序集合的偏序关系 “”, 也读作“小于等于”. 之所以采用这样的符号和名称, 是因为偏序关系和小于等于关系具有完全相似的性质. 集合的包含关系也是偏序关系. 设(A, )是偏序集, 则A中的任何两个元素a, b只可能出现如下四种情况之一:a = b, a b, b a, a与b不可比较.顺便提一下, 如果一个偏序集合当中任意两个元素都可以比较, 就称为全序集.偏序关系的重要性不亚于等价关系. 对于这种特殊的关系, 我们也采用特殊的方式来表示, 这种表示方式就是Hasse图表示法.设有偏序集(A, ), 则其Hasse图构造法如下：S1. 以“点”表示A中的元素; S2. 若y是x的直接后继, 则y在x的上方; S3. 在x和x的直接后继间连线.例如 设A是正整数12的全部正整数因子组成的集合, 并设偏序关系为整除关系“|”, 则这个偏序关系的Hasse图如下: 五、 典型例题例1 设A=2, 3, 6, 12, R是A上的整除关系.（1） 给出R的集合表示式.（2） 给出R的关系矩阵.（3） 画出R的有向图.（4） 考察关系R是否具有自反性、对称性、传递性、反对称性.（5） R是否为等价关系? R是否为偏序关系? 分析 首先根据整除关系的含义, 列出A中整除有序数对: 2|2, 2|6, 2|12, 3|3, 3|6, 3|12, 6|6, 6|12, 12|12. 此即R所包含的全部有序对. 至于其矩阵和有向图很容易根据R的集合表达式得到. 然后可以利用定义、关系矩阵或者关系图来判定R所具有的性质. 最后根据这些性质就能知道这个关系是一个什么样的关系. 解 （1）根据关系R的定义:R=(2, 2), (2, 6), (2, 12), (3, 3), (3, 6), (3, 12), (6, 6), (6, 12), (12, 12).（2）R的关系矩阵MR如下:（3）R的关系图略. (4) 可以从R的意义、集合表示、关系矩阵或者关系图得到R自反、传递、反对称. (5) 根据(4)我们知道R是偏序关系, 不是等价关系. 例2 设T=1, 2, 3, , 9, A=TT. 按照下列方式定义集合A上的关系R:(a, b)R(c, d) a + d= b + c(1) 证明R是A上的等价关系.(2) 求出元素(5, 2)所在的等价类(5, 2).分析 求解本题时要注意集合A的元素本身都是有序对. 这样R由形如(2, 1), (3, 2)的元素组成. 由于|A|=81, 因此并不一定非要列举出R所包含的全部元素. 可以直接按照R的定义直接验证R满足: (i)自反性: (a, b)R(a, b); (ii) 对称性: (a, b)R(c, d) (c, d)R(a, b) ; (iii) 传递性: (a, b)R(c, d), (c, d)R(u, v) (a, b)R(u, v). 由此证明R是A上的等价关系.根据R的定义, 可以看出(a, b)R(c, d) a + d= b + c a - b = c - d. 由此看见, (a, b)R(5, 2) a-b=5-2=3.根据这个特点很容易写出等价类(5, 2).解 (1) (i) R满足自反性: 设 (a, b)A, a+b=b+a(a, b)R(a, b);(ii) R满足对称性: (a, b)R(c, d)a+d=b+cc+b=d+a (c, d)R(a, b) ; (iii)R满足传递性: (a, b)R(c, d), (c, d)R(u, v)a+d=b+c, c+v=d+u a-b=c-d=u-v a + v= b + u (a, b)R(u, v) 所以R是等价关系.(2) (5, 2)=(4, 1), (5, 2), (6, 3), (7, 4), (8, 5), (9, 6).例3 设A=a, b, c, d, e, f, 有一个划分S=a, b, c, d, e, f, 试由划分S确定A上的一个等价关系R.分析 根据题设要求, 我们需要求一个等价关系R, 使得R 的等价关类恰好是上述划分S中的三个子集合. 要使得a, b, c成为R的一个等价类, 那么其中的任意两个元素都满足关系R, 从而R必须包含这个子集中元素构成的任意一个有序对, 必然有R1=a, b, ca, b, cR, R2=d, ed, e R, R3=ff R.只要令R= R1 R2 R3即可. 解 我们用如下办法产生一个等价关系R:R1=a, b, ca, b, c=(a, a), (b, b), (c, c), (a, b), (a, c), (c, a), (b, c), (c, b)R2=d, ed, e=(d, d), (e, e), (d, e), (e, d)R3=ff=(f, f) R.R=R1R2R3.容易证明R是等价关系, 而且等价类正是S中的三个子集.例4 设有集合A=a, b, c, d, e上的偏序关系:R=(a, b), (a, c), (a, d), (a, e), (b, d), (b, e), (c, d), (c, e), (d, e)IA.画出Hasse图解 根据Hasse图定义, 可以画出这个偏序关系的Hasse图如下: 例5 设偏序(A, R)的 Hasse图如下, 试求集合A和关系R.分析 本题主要可能出现的错误是把Hasse图误认为是关系图, 这样就只能写出互相之间有边连接的关系. 正确的方法是, 首先根据R必须是自反的, 得到IAR. 然后根据传递性, 和位置关系, 可以写出全部的满足关系R的有序对. 一般先从最下面开始写: 比如(a, c), (a, d), (a, e), (a, f). 其中只有(a, c)是图中直接显示出来的, 其余三个都是由Hasse图的定义隐含的关系. 类似可以写出所有(b, x)形式的关系对, (c, x)形的关系对, 等等.解 根据Hasse图的含义我们有A=a, b, c, d, e, f;R =(a, c), (a, d), (a, e), (a, f), (b, c), (b, d), (b, e), (b, f), (c, d), (c, e), (c, f), (d, e), (d, f)IA.二元关系是对于现实中我们熟悉的一些关系的抽象. 利用集合的笛卡尔积、矩阵和有向图都可以表示二元关系. 关系的性质也很容易利用这些表示方法来判断. 比较重要的关系有等价关系和序关系. 对于等价关系, 需要搞清等价关系与集合的划分之间的关系. 对于序关系需要掌握它的Hasse图的含义. 本章的内容重复体现了可以利用不同的数学方式来研究问题.第8章 命题逻辑一. 主要内容1.命题与联结词命题与命题真值，五种逻辑联结词，复合命题。 2.公式与解释 原子及其公式，公式的解释、真值表、公式的类型、公式的等价。二. 学习要求 1.了解命题、逻辑联结词的概念；掌握用联结词产生复合命题的方法。 2.了解公式与解释的概念，掌握真值表判断公式类型的方法。三. 学习重点1. 能够把自然命题符号化, 也能够把符号命题翻译成自然命题.2. 会给出简单命题公式的真值表, 由此判断命题的类型. 3. 用真值表检验简单的逻辑推理*四.重、难点解析(一) 命题逻辑基本知识数理逻辑中研究的命题必须是“能分辨真假的陈述句”.命题有两个基本特征: 其一, 必须是陈述句；其二, 必须能够分辨真假, 不能不真不假, 也不能亦真亦假. 一般来讲, 疑问句、祈使句、感叹句都不能算命题. 这里要注意, 能辨真假并不要求我们就能够回答其真假. 比如“存在外星人”是一个命题, 虽然我们目前还无法回答这个命题是真还是假. 命题既然是有真假的陈述句, 那么任何一个命题P就只有两种可能的真值: T或F, 也可以表示为1或0.1. 命题与联结词在命题逻辑中, 最基本最简单的命题是原子命题, 原子命题无法再分解为更简单的命题. 一般复杂命题可以通过原子命题用联结词复合而成. 因此搞清联结词的含义是十分重要的. 本书我们只介绍了五种最基本的联结词, 汇总在下表中: 联结词记号复合命题读法表示法否定P是不对的P的否定或非PP合取P并且QP与Q的合取PQ析取P或者QP与Q的析取PQ蕴含若P, 则QP蕴含QPQ等价P当且仅当QP等价于QPQ由联结词所产生的复合命题真值由原命题所决定, 具体情况如下表: PQPPQPQPQPQTTFTTTTTFFFTFFFTTFTTFFFTFFTT注意: (1) 析取联结词“”与我们日常生活中的“或”之间的细微差别. (2) 在数理逻辑中, 任何命题都可以复合在一起. 例如: 命题P: 213和命题Q: 今天是晴天, 可以复合成命题: PQ, PQ等. 2. 命题公式及其分类命题公式: 命题变元和命题联结词, 按照一定方式复合而成的就是命题公式. 例如, 如果P和Q是命题变元, 则P, PQ, (PQ)(GQ), P(QP)等都是命题公式. 命题变元: 命题公式中出现代命题P和Q称作命题变元.如果一个命题公式A由命题变元P1, P2, , Pn构成, 那么命题变元P1, P2, , Pn任意一组真值指派, 就能得到A的一个真值. n个命题变元所有可能的真值指派共有2n个. 如果把这些指派以及A相应的真值列成表, 就是命题公式的真值表. 例如 构造下列命题公式的真值表.(1) PQ(2) (PQ)P解 (1)命题公式PQ的真值表如下:PQPPQTTFT TFFFFTTTFFTT(2)命题公式(PQ)P的真值表如下:PQPQP(PQ)PTTTFFTFFFFFTFTFFFFTF 如果命题公式A在命题变元的任何真值指派下其值恒为真, 则称A为永真式或重言式. 如果命题公式A在命题变元的任何真值指派下其值恒为假, 则称A为永假式或矛盾式, 如果命题公式A至少有一组命题变元的真值指派使其值为真, 则称A为可满足式. 利用真值表很容易判定一个命题公式是否为永真式、永假式、可满足式. 此外, 还可以利用命题的等价和蕴含, 利用逻辑推理的方式确定命题公式的类型, 也可以利用主范式来判定. 对于初学者, 一定要掌握真值表方法, 其它方法了解一下就可以了. 如果把联结词看作命题运算符号, 它们的次序为: 、. 对于初学者来说, 如果不清楚, 可以适当使用括号. 例如命题公式PQRS相当于(P(Q)R)S. 3. 命题公式的等价与蕴含命题逻辑不仅关心一个命题公式的类型, 还关心两个命题之间的关系, 其中等价和蕴含是其中最重要的关系. 只有当命题公式“A B”是永真式时, 才说A与B等价, 并使用记号AB.而只有当AB是永真式时, 才称A蕴含B, 并记作AB.一定要搞清 “”与“”的区别和联系; “”与“” 的区别和联系.要证明两个命题公式A与B等价, 有三种方法: (1)利用真值表. 对于命题变元任何一组指派, 两个命题公式必须取得同样的真值. 或者用真值表证明A B为永真式. 利用真值表来证明命题公式等价是一个有效办法, 但是前面我们已经指出过, 这种方法有点过于复杂, 特别当命题变元比较多的时候, 这个方法更麻烦, 但是对于命题变元比较少的情况, 真值表方法无疑是一个很实用的方法. (2)利用基本等价律、替换原则、代入等方式, 把两个命题公式A, B互化. 也就是使用等值演算方法.常用基本等价律如下: 交换律ABBA ABB AE1结合律(AB)CA(BC) (AB)CA(B C)E2分配律A(BC)(AB)(AC) A(BC)(AB)(AC)E3同一律AF A AT AE4矛盾律AA =FE5排中律AAT E6双重否定律AAE7幂等律AAA AAAE8零 律AT T AFFE9吸收律A(AB) A A(AB) AE10德摩根律(AB)A B (AB)A BE11联结词归化律ABAB AB(AB)(A B)E12(3)说明两个命题有完全相同的主析取范式或者主合取范式. 4. 主析取范式和主合取范式设命题公式A由命题变元P1, P2, , Pn构成.合取式: 形如Q1Q2Qt的命题公式, 其中Qi=Pi或者Pi, i=1, 2, , t.析取式: 形如Q1Q2Qt的命题公式, 其中Qi=Pi或者Pi, i=1, 2, , t. 析取范式:A1A2Am其中A1, A2, , Am都是合取式. 例如(QR P) (PQR)是一个析取范式. 合取范式: A1A2Am其中A1, A2, , Am都是析取式. 主范式: (1) 是范式; (2)每项包含公式中出现的所有命题变元.求一个给定命题的范式和主范式有一定难度. 书中介绍的利用真值表直接给出主范式的方法比较简单. 5. 命题公式的推理理论*其实推理就是一些连续的蕴含过程, 类似于我们非常熟悉的平面几何证明题的过程. 每一步必须说明依据. 随时可以使用已知条件、已经证明的结论等等. 这里的推理理论无非就是把平时的推理过程抽象化, 一般化, 严格化. 在学习时尽量结合具体问题的推理理解书中的推理法则. 利用真值表也可以判断一个论证或者推理是否有效.在进行命题公式推理的时候, 需要经常使用下表中的基本蕴含式:P Q PI1P Q QI2P PQI 3Q PQI 4P PQI 5( PQ)PI 6( PQ) QI 7P(PQ) QI 8P( PQ) QI 9( PQ)(QR)PRI 10(PQ) ( PR)(QR)RI 11(PQ) ( RS) (PR)(QS)I 12(PQ) ( QR) (PR)I 13(二) 命题逻辑应该注意的几个问题 1. “”与“或” 在数理逻辑中最常用的逻辑联结词有五个: 、. 初学者在使用时最容易出现问题的联结词是析取联结词“”. 一般情况下我们把这个联结词翻译成“或”. 但是, 这与我们日常生活中“或”的使用有很大差别. 在现实生活中使用的或大部分情况下是指不可兼或. 例如: 我或者写作业或者去跑步. 这个或就是不可兼或. 而“2+3 = 5或者我写作业”里面的或就是可兼或. 数理逻辑中的析取总是指可兼或. 这样在把自然命题翻译成符号命题时, 一定要仔细分析其含义. 2. “”与“如果, 那么”在日常生活中, “如果A, 那么B”中间的A, B肯定有联系, 这就是我们习惯上所说的前因后果. 但是在命题逻辑中, 只要A, B是命题, “AB”总是一个有意义的命题. 更重要的是, 要接受关于这个复合命题真值的规定. 在数理逻辑中规定, 只要B真, 无论A真值如何, 复合命题都算真; 如果B不真, A也不真, 整个命题还算作真. 只有当A真但B假这一种情况下这个复合命题才算假.从以上叙述我们知道: 无论A是什么样的命题, 复合命题“1+1=3A”永远是对的. 这一点对于初学者来讲最难理解. 考察下面例子:(1) 如果我跳高能跳过3米, 那么太阳就会从西边出来. (2) 如果我跳高能跳过1米, 那么太阳就会从东边出来. (3) 如果我跳高能跳过3米, 那么太阳就会从东边出来. (4) 如果我跳高能跳过1米, 那么太阳就会从西边出来. (5) 如果我是你, 我肯定能考100分.3. “”与“”、“”与“”AB与A B 有区别也有联系. “”并不是一个命题联结词, 而只是表明两个命题公式之间的关系. 实际上, 我们是用“AB”来表示命题公式“AB”是永真式. 因此AB并不是一个命题公式. 而“”是一个命题联结词, 如果A, B是命题公式, 那么A B是一个命题公式. AB与AB 的区别和联系与“”和“”的完全类似. “”也不是一个命题联结词, 而只是表明两个命题公式之间的关系, 因此AB并不是一个命题公式. 而“”是一个命题联结词, 如果A, B是命题公式, 那么AB是一个命题公式. 这是它们的区别. 实际上, 我们是用“AB”来表示命题公式“AB”是永真式.另外需要指出的是, “”是命题公式之间的一个等价关系, 但是蕴含关系“”则不是等价关系. 主要原因是蕴含不满足对称性, 即即使AB也不一定有BA. 五. 典型例题例1 试把下列命题符号化:(1) 我们要做到身体好、学习好、工作好, 为祖国建设小康社会而奋斗. (2) 北京到西安的42次列车是下午4:30开或下午5:30开. 解 找出原子命题, 然后用适当联结词对命题进行符号化.(1) 设 A: 我们要做到身体好;B: 我们要做到学习好; C: 我们要做到工作好; P: 为祖国建设小康社会而奋斗. 原命题可符号化为: (ABC)P(2) 设 P: 北京到西安的42次列车下午4:30开; Q: 北京到西安的42次列车下午5:30开. 注意汉语的“或”有时候是不可兼或, 而逻辑联结词是“可兼或”, 因此不能直接对两命题析取. 可以通过构造下面的真值对照表来看清如何翻译不可兼或:PQ原命题PQ (PQ)TTFTFTFTFTFTTFTFFFTF从表中可以看出原命题不能用前述五个联结词单独写出, 但是如用命题和联结词组合, 可以把本命题表达为: (PQ). 有些书籍引入符号 “”来表示不可兼或.例2 把下列命题符号化:(1)他既聪明又用功. (2)他聪明但不用功. (3)他既不聪明又不用功解 设P: 他聪明; Q: 他用功, 则可根据自