离散数学本科期末复习提要.DOC

1、 1 离散数学本科期末复习提要 四川电大 孙继荣 2004 年 5 月 离散数学使用的教材为中央电大出版的离散数学（刘叙华等编）和离散数学学习指导书（虞恩蔚等编）。 离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。 课程的主要内容 1、 集合论部分（集合的基本概念和运算、关系及其性质）； 2、 数理逻辑部分（命题逻辑、谓 词逻辑）； 3、 图论部分（图的基本概念、树及其性质）。 4、 布尔代数 学习建议 离散数学

2、是理论性较强的学科，学习离散数学的关键是对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。 教学要求的层次 各章教学要求的层次为了解、理解和掌握。了解即能正确判别有关概念和方法；理解是能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。 一、各章复习要求与重点 第一章 集 合 复习知识点 1、集合、元素、集合的表示方法、子集、空集、全集、 集合的包含、相等、幂集 2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan律等），文氏（ Venn）图 3、序偶与迪卡尔积 本章重点内容：集合的概念

3、、集合的运算性质、集合恒等式的证明 复习要求 1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。 2、掌握集合的表示法和集合的交、并、差、补等基本运算。 3、掌握集合运算基本规律，证明集合等式的方法。 4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。 本章重点习题 P56， 4、 6； P1415， 3、 6、 7； P20， 5、 7。 疑难解析 1、集合的概念 因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为 2n。 2、集合恒等式的证明 通过对集合恒等式证明的练习，既可以加深对集合性质的理解与

4、掌握；又可以为第三2 章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在 BABA 证明中的特殊作用。 例题分析 例 1 设 A， B 是两个集合， A=1， 2， 3， B=1， 2，则 )()( BA 。 解 3,2,1,3,2,3,1,2,1,3,2,1,)( A 2,1,2,1,)( B 于是 3,2,1,3,2,3,1,3)()( BA 例 2 设 , babaA ，试求： (1) baA , ； (2) A ； (3) A ； (4) Aba , ； (5) A ； (6) A 。 解 (1) , babaA (

5、2) AA (3) babaA , (4) Aba, (5) A (6) A 例 3 试证明 BABABABA 证明 BABABABABBBAABAABBAABABABA第二章 二元关系 复习知识点 1、关系、关系矩阵与关系图 2、复合关系与逆关系 3、关系的性质（自反性、对称性、反对称性、传递性） 4、关系的闭包（自反闭包、对称闭包、传递闭包） 5、等价关系与等价类 6、偏序关系与哈斯图（ Hasse）、极大 /小元、最大 /小元、上 /下界、最小上界、最大下界 7、函数及其性质（单射、满射、双射 ） 8、复合函数与反函数 本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序

6、关系、映射的概念 复习要求 3 1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。 2、掌握求复合关系与逆关系的方法。 3、理解关系的性质（自反性、对称性、反对称性、传递性），掌握其判别方法（定义、矩阵、图）。 4、掌握求关系的闭包 （自反闭包、对称闭包、传递闭包）的方法。 5、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元 、最大 /小元、上 /下界、最小上界、最大下界的求法。 6、理解函数概念：函数、函数相等、复合函数和反函数。 7、理解单射、满射、双射等概念，掌握其判别方法。 本章重点习题 P25

7、， 1； P3233， 4， 8， 10； P43， 2， 3， 5； P5152， 5， 6； P59， 1， 2； P64，3； P7475， 2， 4， 6， 7； P81， 5， 7； P86， 1， 2。 疑难解析 1、关系的概念 关系的概念是第二章全章的基础，又是第一章集合概念的应用。因此，学生应该真正理解并熟练掌握二元关系的概念及关系 矩阵、关系图表示。 2、关系的性质及其判定 关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。对于四种性质的判定，可以依据教材中 P49 上总结的规律。这其中对传递性的判定，难度稍大一点，这里要提及两点：一是不破坏

8、传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。另一点是介绍一种判定传递性的“跟踪法”，即若 RaaRaaRaa ii , 13221 ，则 Raa i ,1 。如若 RabRba , ，则有 Raa , ，且 Rbb , 。 、关系的闭包 在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记三个定理的结论：定理 2， AIRRr ；定理 3， 1 RRRs ；定理 4，推论 niiRRt1。 、半序关系及半序集中特殊元素的确定 理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌 握了，对于确定任一子集的最大（小）元，极大（

9、小）元也就容易了。这里要注意，最大（小）元与极大（小）元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同样。 、映射的概念与映射种类的判定 映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数。 例题分析 例 1 设集合 dcbaA , ，判定下列关系，哪些是自反的，对称的，反对称的和传递的： 4 dbcaR ccbbaaRdcRadcbaaRabaaR , ,54321 解：均不是自反的

10、； R4 是对称的； R1 ,R2 ,R3 , R4 ,R5 是反对称的； R1 ,R2 ,R3 , R4 ,R5 是传递的。 例 2 设集合 5,4,3,2,1A ， A 上的二元关系 R 为 5,5,4,5,3,5,4,4,4,3,3,3,2,2,1,1R （）写出 R 的关系矩阵，画出 R 的关系图； （）证明 R 是 A 上的半序关系，画出其哈斯图； （）若 AB ，且 5,4,3,2B ，求 B 的最大元，最小元，极大元，极小元，最小上界和最大下界。 解 （ 1） R 的关系矩阵为 1110001000011000001000001RM R 的关系图略 （ 2）因为 R 是自反的，反

11、对称的和传递的，所以 R 是 A 上的半序关系。 (A,R)为半序集， (A,R)的哈斯图如下 (3) 当 5,4,3,2B ， B 的极大元为 2， 4；极小元为 2， 5； B 无最大元与最小元； B也无上界与下界，更无最小上界与最大下界。 第三章 命题逻辑 复习知识点 、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题 、命题公式与解释，真值表，公式分类（恒真、恒假、可满足），公式的等价 、析取范式、合取范式，极小（大）项，主析取范式、主合取范式 、公式类别的判别方法（真值表法、等值演算法、主析取 /合取范式法） 、公式的蕴涵与逻辑结果 、形式演绎 本章重 点内容：命题与联结词、公

12、式与解释、析取范式与合取范式、公式恒真性的判定、形式演绎 复习要求 、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。 、理解公式与解释的概念；掌握求给定公式真值表的方法，用基本等价式化简其他公式，。 4 。 1 。 3 。 2 。 5 5 公式在解释下的真值。 、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等价式或真值表将公式化为主析取（合取）范式的方法。 、掌握利用真值表、等值演算法和主析取 /合取范式的唯一性判别公式类型和公式等价的方法。 、理 解公式蕴涵与逻辑结果的概念，掌握基本蕴涵式。 6、掌握形式演绎的证明方法。 本

13、章重点习题 P93， 1； P98， 2， 3； P104， 2， 3； P107， 1， 3； P112， 5； P115， 1， 2， 3。 疑难解析 1、公式恒真性的判定 判定公式的恒真性，包括判定公式是恒真的或是恒假的。具体方法有两种，一是真值表法，对于任给一个公式，主要列出该公式的真值表，观察真值表的最后一列是否全为 1（或全为 0），就可以判定该公式是否恒真（或恒假），若不全为 0，则为可满足的。二是推导法，即利用基本等价式推导出结果为 1，或者利用恒真（恒假）判定定理：公式 G 是恒真的（恒假的）当且仅当等价于它的合取范式（析取范式）中，每个子句（短语）均至少包含一个原子及其否定

14、。 这里要求的析取范式中所含有的每个短语不是极小项，一定要与求主析取范式相区别，对于合取范式也同样。 2、范式 求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等价式中的分配律、同一律和互补律，结果的前一步适当使用等幂律，使相同的短语（或子句）只保留一个。 另外，由已经得到的主析取（合取）范式，根据 GGGG ,1 原理，参阅离散数学学习指导书 P71 例 15，可以求得主合取（析取）范式。 3、形式演绎法 掌握形式演绎进行逻辑推理时，一是要理解并掌握 14 个基本蕴涵式，二是会使用三个规则：规则 P、规则 Q 和规则 D，需要进行

15、一定的练习。 例题分析 例 1 求 PRQPG 的主析取范式与主合取范式。 解 （ 1）求主析取范式， 方法 1：利用真值表求解 RQP QP RQP G 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 1 0 1 0 1 1 1 1 1 因此 6 RQP RQPRQPRQPRQPRQPG 方法 2：推导法 RQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRRQQPPPRQQQRPPRQRPPRQPPRQPPRRQPG（ 2）求主合取范式 方法 1：利

16、用上面的真值表 PRQP 为 0 的有两行，它们对应的极大项分别为 RQPRQP , 因此， RQPRQPPRQP 方法 2：利用已求出的主析取范式求主合取范式 已用去 6 个极小项，尚有 2 个极小项，即 RQP 与 RQP 于是 RQPRQP RQPRQPGGRQPRQPG 例 2 试证明公式 RPRQQPG 为恒真公式。 证法一： 见离散数学学习指导书 P60 例 6（ 4）的解答。（真值表法） 证法二 ： G=（ PQ） （ QR） （ PR） =（ PQ） （ QR） PR =（ PQ） （ PR） （ QQ） （ QR） P） R =（ PQP） （ PRP） （ QRP） R =

17、（ 1（ QRP） R =QRPR =1 故 G 为恒真公式。 例 3 利用形式演绎法证明 P（ QR）， SP， Q蕴涵 SR。 证明： （ 1） SP 规 则 P （ 2） S 规则 D 7 （ 3） P 规则 Q，根据（ 1），（ 2） （ 4） P（ QR） 规则 P （ 5） QR 规则 Q，根据（ 3），（ 4） （ 6） Q 规则 P （ 7） R 规则 Q，根据（ 5），（ 6） （ 8） SR 规则 D，根据（ 2），（ 7） 第四章 谓词逻辑 复习知识点 1、谓词、量词、 个体词、个体域、变元（约束变元与自由变元） 2、谓词公式与解释，谓词公式的类型（恒真、恒假、可满足）

18、3、谓词公式的等价和蕴涵 4、前束范式 本章重点内容：谓词与量词、公式与解释、前束范式 复习要求 1、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；了解命题符号化。 2、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。 3、理解用解释的方法证明等价式和蕴涵式。 4、掌握求公式前束范式的方法。 本章重点习 题 P120， 1， 2； P125126， 1， 3； P137， 1。 疑难解析 1、谓词与量词 反复理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的自由性、约束性与改名规则。

19、 2、公式与解释 能将一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后将解释 I 中的数值代入公式，求出真值。 3、前束范式 在充分理解掌握前束范式概念的基础上，利用改名规则、基本等价式与蕴涵式（一阶逻辑中），将给定公式中量词提到母式之前称为首标。 典型例题 例 1 设 I 是如下一个解释： 3,2D F(2) F(3) P(2) P(3) Q(2,2) Q(2,3) Q(3,2) Q(3,3) 3 2 0 1 1 1 0 1 求 y,xFQxPyx 的真值。 解 8 110111110003,3FQ3P2,3FQ3P3,2FQ2P2,2FQ2P3,xFQxP2,xFQxPxy,xFQ

20、xPyx例 2 试将一阶逻辑公式化成前束范式。 解 xRzQyxPzyxxRzQzyxyPxxRyQyyxyPxxRyyQyxyPxG,第五章 群与环 第六章 格和布尔代数 复习要求 1. 了解 代数运算、代数系统和子代数系统等概念。掌握二元运算的性质：结合律、交换律、分配律、幂等律、吸收律。掌握求集合上代数运算的单位元 (幺元 )、 0 元和逆元的方法。 代数运算的性质： x,yA，有 xy=xyz，运算 在 A 上适合交换律。 x,y,zA，有 (xy)z x(yz)，运算 在 A 上适合结合律。 x,y,zA，有 x(yz)=(xy)(xz) 或 (yz)x=(yx)(zx)，运算 对

21、可分配，适合分配律。 xA，有 xx=x，则运算 在 A 上适合 幂等律。 x,yA, 有 x(xy)=x, x(xy)=x， 和 满足吸收律。 el, (或 er)A，对 xA, 有 elx=x (xer=x), el(或 er)是 A 的运算 的左单位元 (或右单位元 )。若 e 既是右单位元又是左单位元，就称其为单位元。 存在 xxAxA 有, ， 就是 *的 0 元。一侧成立叫右 0 元或左 0元。 对 xA，若 x-1A, 有 x-1x=xx-1=e， x-1 是 x 的逆元。 在非空集合 A 上，定义了若干代数运算 f1,f2, ,fm, (A, f1,f2, ,fm)称为代数系统

22、。若 BA，f1,f2, ,fm 在 B 上成立， (B, f1,f2, ,fm)称为子代数系统。 2. 了解半群、群和子群等概念。掌握群的基本运算律及群的判别方法 代数系统 子群群半群）（ 存在逆元、单位元具有结合律 ),(, HG GH 3. 了解循环群、交换群和置换群的概念，掌握其判别方法。 4.了解群的同态与同构等概念，知道它们的主要性质。 5. 知道环的概念。 6. 了解格的概念。 设 (L， )是一个偏序集，如果对于 a,bL， L 的子集 a,b在 L 中都有一个 最大下界 (记为 infa,b)和一个最小上界 (记为 supa,b),则称 (L， )是一个偏序格。 9 子集在

23、L 中有上确界和下确界的偏序集，就是格。 在 L 定义二元运算 *， o 满足：对 a,b,cL,有 (1) 交换律 a*b=b*a， aob=boa (2) 结合律 (a*b)*c=a*(b*c) , (aob)oc=ao(boc) (3) 吸收律 a*(aob)=a， ao(a*b)=a 则称 (L,*,o )是 代数格 . 用代数的语言，格就是在非空集合上定义了两个满足结合律、交换律和 吸收律的运算。 7. 知道有界格、有余格、分配格的概念。 8. 了解布尔代数概念，掌握其性质和运算。 设 B 是一个至少含有两个元素的集合， ，是定义在 B 上的两种运算，如果对a,b,cB，满足下列公理

24、： H1： ab=ba a+b=b+a H2： a(b+c)=ab+ac a+(bc)=(a+b)(a+c) H3： B 中有元素 0 和 1，对 aB,有 a1 = a a+0 = a H4：对 aB,有 aB，满足 aa=0 a+a=1 则 (B， ， ， ， 0， 1)是一个布尔代数 记住布尔代数运算的 10 条算律。 【本部分重点】代数运算及性质，群的概念，格和布尔代数的概念，布尔代数的运算及其性质 例题： 例 1 试判断 (Z,)是否为格？其中 是数的小于或等于关系 . 解 显然 (Z,)是一个偏序集 . 又 Zyx , ， x, y 的最小上界为 ),max( yx , x, y

25、的最大下界为 ),min( yx ，皆为整数，仍然属于 Z. 故对 Z 的任意子集，在 Z 中都有上确界和下确 界 . 即 (Z,)是格 . 例 2 设 ( , B )是布尔代数， 1,0,2 aaBaB ，证明 ( , T )是 B 的子布尔代数，而且是布尔代数，其中 1,0 aaT . 证明 对于集合 T 中的元素作运算见表 8 3. 表 8 3 T的元素运算表 0 a a 1 0 a a 1 1 0 0 a a a 0 0 0 0 0 0 1 a a a 1 a a 0 a 0 A a a a a 1 a a a 0 0 a a a a 1 1 1 1 1 1 0 a a 1 1 0 由

26、 B 是布尔代数可知，从表 8 3 得到 T 对运算 ， ， 是封闭的，所以 ( , T )是子布尔代数 . 由定理 11 知 ( , T )也是布尔代数 . 10 例 3 单项选择题 1. 下列图 (如图 8 1)表示的偏序集中，是格的为 ( ) 图 8 1 答案 ： (C) 解答 ：所给 (A),(B),(D)的偏序集，都有两个极大元，不存在上确界，都不是格，只有 (C) 的偏序集有上确界和下确界，是格 . 故选择 (C)正确 . 2. 设 )1,0,( B 是布尔代数， baBba , ，则下式不成立的是 ( ) 1)D()C(1)B(0)A( baabababa 答案 ： (D) 解答

27、 ：因为 B 是偏序集， ；否则，不成立则若那么 1, babaabba . 故选择 (D)正确 . 3. 布尔代数式 )( cbcabab =( ) cbcbcbba )D()C()B()A( 答案 ： (B) 解答 ： bcbacabcbcabab )1()1()( . 故选择 (B)正确 . 例 4 填空题 1. 非空集合 L，其上定义二元运算 和 ，如果 是交换群， (L,)是 ，而且 满足分配律，则 L 对二元运算 和 构成环 . 答案 ： (L,)；半群；二元运算 对运算 解答 ：见环的定义 . 2. 设 L 是一个集合， 和 是 L 上两个二元运算，如果这两个二元运算满足 律， 律和 律，则 (L,)是格 . 答案 ：交换律；结合律；吸收律 解答 ：见代数格的定义 . 3. 在布尔代数中，有 babaa )( 成立 . 则该式的对偶式 也一定成立 . 答案 ： babaa )( 解答 ：见对偶原理，知 babaa )( 是原式的对偶式， 也是成立的 . (A) (B) (C) (D)