离散数学复习资料.doc

《离散数学复习资料.doc》由会员分享，可在线阅读，更多相关《离散数学复习资料.doc（24页珍藏版）》请在三一文库上搜索。

1、离散数学复习资料一、考试内容（1）考试内容以课堂上讲的内容为范围；（2）每次课后布置的作业。二、各章节提要第一章 命题逻辑教学目的及要求：深刻理解和掌握命题逻辑中基本概念和基本方法教学内容：命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴含式、对偶与范式、推理理论。教学重点：命题逻辑中的基本概念和基本推理方法。教学难点：推理理论小结：学习第一章要注意以下几点：（1）弄清命题与陈述句的关系。（2）弄清由5种基本联结词联结的复合命题的逻辑关系及其真值。特别是要弄清蕴含式”PQ“的逻辑关系及其真值。（3）记住常用的蕴含式和等价式，这是学好命题逻辑的关键问题。（4）会准确地求出给定公式

2、的主析取范式和主合取范式。掌握主析取范式与真值表、成真赋值、主合取范式的关系。（5）会用多种方法判断公式的类型及判断两个公式是否等价。（6）会用等价变换法将一个联结词集中的公式等价地化为另一个联结词全功能集中的公式。（7）掌握推理和判断推理是否正确的方法。第二章 谓词逻辑教学目的及要求：深刻理解和掌握谓词逻辑的基本概念和基本推理方法。教学内容：谓词的概念与表示、命题函数与量词、谓词公式与翻译、变量的约束、谓词演算的等价式与蕴涵式、前束范式、谓词演算的推理理论。教学重点：谓词逻辑中的基本概念和基本推理方法。教学难点：谓词演算的推理理论。小结：学习第二章要注意以下几点：(1)同一个命题在不同个体域

3、内可能有不同的符号化形式，同时也可能有不同的真值，因而在将一个命题符号化之前，必须弄清个体域。(2)在将命题符号化时，要特别注意量词与联结词的搭配。经常的情况是全称量词与蕴含词搭配，存在量词$与合取词搭配。因此有下面两种形式的公式：（x）(A(x) B(x) （$x）(A(x) B(x) 而（x）(A(x) B(x) （$x）(A(x) B(x) 与，与的含义完全不同。(3)记住主要的等价式。会用约束变元和自由变元换名规则进行等价演算，求出给定公式的前束范式。(4)在谓词演算的推理证明中，要特别注意US，UG，ES，EG规则成立的条件。第三章 集合与关系教学目的及要求：深刻理解和掌握有关集合和

4、关系的基本概念和基本运算。 教学内容：集合的概念与表示、集合的运算、序偶与笛卡尔积、关系及表示、关系的性质、复合关系和逆关系、关系的闭包运算、等价关系与等价类、序关系。教学重点：关系及关系的运算、等价关系、序关系。教学难点：关系的闭包运算、等价关系、等价类。第四章 函数教学目的及要求：深刻理解和掌握函数的基本概念。教学内容：函数的概念、逆函数和复合函数。教学重点：函数和复合函数。小结：通过第三，第四章的学习应该达到下面的基本要求：（1） 能够正确地表示一个集合，会画文氏图。（2） 能判定元素是否属于给定的集合。（3） 能判断两个集合之间是否存在包含、相等或真包含的关系。（4） 能熟悉地进行集合

5、的并，交，相对补，绝对补，对称差运算，会计算幂集。（5） 能正确地使用集合表达式、关系矩阵和关系图表示给定的二元关系。（6） 给定A上的关系R（可能是集合表达式，也可能是关系矩阵或关系图），能判别R的性质。（7）给定关系R和S，求RS；给定A上的关系R，求Rn，r(R)， s(R)，t(R)。（8）给定A上的等价关系R，求所有的等价类和商集A/R，或者求与R相对应的划分，以及给定A的划分，求对应的等价关系。（9）给定A上的偏序关系，画出偏序集的哈斯图；给定偏序集的哈斯图，求A和的集合表达式。（10）确定偏序集的极大元、极小元、最大元、最小元、最大下界和最小上界。（11）给定集合A，B和f，判别

6、f是否为A到B的函数，如果是，说明是否为入射、满射、双射。第五章 代数结构教学目的及要求：深刻理解和掌握代数系统的基本概念和运算。教学内容：代数系统的引入、运算及性质、半群、群与子群。教学重点：群的概念及运算。小结：通过本篇的学习应达到以下基本要求：(1)给定集合与运算的解析表达式，写出该运算的运算表。(2)给定集合和运算，判别该集合对运算是否封闭。(3)给定二元运算，说明运算是否满足交换律、结合律、幂等律、分配律和吸收律。(4)给定集合S上的二元运算，求出该运算的幺元、零元、幂等元和所有可逆元素的逆元。(5)给定集合S和二元运算*，能判定是否构成半群、独异点和群。(6)给定半群S和子集B，判

7、定B是否为S的子半群；给定独异点V和子集B，判定B是否为V的子独异点，给定群G和子集H，判定H是否为G的子群。第七章 图论教学目的及要求：深刻理解和掌握图的有关概念和表示。教学内容：图的基本概念、路与回路、图的矩阵表示、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用。教学重点：图、路、图的矩阵表示、平面图、对偶图与着色、树与生成树。教学难点：树与生成树。小结：通过本篇的学习应达到以下基本要求：(1)牢记图论基本定理(握手定理)，(2)记住简单图的概念，弄清楚那些概念是用简单图定义的。(3)明白图之间同构的概念，会根据定义判断阶数n较小的两个图是否同构。(4)弄清图中路径和循

8、环的概念及其分类。(5)在讨论图的连通性时，要特别注意有向连通图的分类及它们之间的关系。(6)在图的矩阵表示中，可以用有向图的邻接矩阵及各次幂，求图中的路径数。(7)明确只存在欧拉路径而无欧拉循环的图不是欧拉图，同样，只存在汉密尔顿路径不含汉密尔顿循环的图不是汉密尔顿图。(8)对于汉密尔顿图，我们只给出了存在的充分条件和必要条件。仍没有找到充分必要条件。(9)掌握平面图的概念及判定平面图的几种方法。(10)掌握树的定义和性质并利用握手定理求树中结点的度数，会求连通图的生成树，用Kruskal算法求最小生成树。(11)掌握根树、有序树、m叉树的概念，任何一棵有序树都可以改写成为二叉树。三、课后布

9、置的作业1.习题1-7 （4）求下列各式的主合取范式和主析取范式，并指出哪些是重言式。等值演算求主析取范式的步骤：1、求A的析取范式2、消去析取范式中所有为永假的析取项3、合并相同的合取项和相同的变元4、对合取项补入没有出现的命题变元，即添加（PP式，然后，应用分配律展开公式。5、将极小项按由小到大的顺序排列。等值演算求主合取范式的步骤：1、求（A）的合取范式2、消去合取范式中所有为永真的合取项3、合并相同的析取项和相同的变元4、对析取项补入没有出现的命题变元，即添加（PP）式，然后，应用分配律展开公式。5、将极大项按由小到大的顺序排列。解：a) (PQ)(PQ)(PQ) (PQ) (PQ)

10、(PQ)(PQ) 1，2，3 PQ=P0b) Q(PQ) (PQ)(QQ) PQ =3 P0，1，2 (PQ)(PQ) (PQ)c) P(P(Q(QR)P(P(Q(QR) PQR=P01，2，3,4,5,6,7=(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)d) (P(QR) )(P(QR) (P(QR) (P(QR) (PP)(P(QR)(QR)P)(QR)(QR) (PQR)(PQR) =0,7P1，2，3,4,5,6 (PQR)(PQR)(PQR)(PQR)(PQR) (PQR)e) P(P(QP) P(P(QP)(PP)(PQP) T(TQ) T0,1,2,3=

11、 (PQ) (PQ) (PQ) (PQ)f) (QP) (PQ) (QP) PQ (QP) (PQ) FP0,1，2，3= (PQ) (PQ) (PQ) (PQ)2.习题1-8 （1）、（2）、（3）、（4）推理过程： 步骤 推理过程 规则 根据 (1) PQ P (2) P P (3) Q T(1)(2) I11 (4) Q R P (5) R T(3)(4) I11(1)用推理规则证明下列各式证明：a)(PQ)，QR，RP(1) RP(2) QR P(3) Q (1)(2)T,I(4) (PQ) P(5) PQ (4)T,E(6) P (3)(5)T,Ib)J(MN)，(HG)J，HGMN

12、(1) (HG) J P(2) (HG) P(3) J (1)(2)T,I(4) J(MN) P(5) MN (3)(4)T,Ic)BC，(BC)(HG) GH(1) BC P (2) B (1)T,I(3) C (1)T,I(4) BC (2)T,I(5) CB (3)T,I(6) CB (4)T,E(7) BC (5)T,E(8) BC (6)(7)T,E(9) (BC) (HG) P(10) HG (8)(9)T,Id)PQ，(QR)R，(PS) S(1) (QR) R (2) QR(1)T,I(3) R (1)T,I(4) Q(2)(3)T,I(5) PQP(6) P(4)(5)T,I

13、(7) (PS)P(8) PS(7)T,E(9) S(6)(8)T,I(2) 仅用规则P和T，推证以下公式证明：a)AB，CBAC(1) (AC) P (2) A(1)T,I(3) C(1)T,I(4) ABP(5) B(2)(4)T,I(6) CBP(7) B (3)(6)T,I(8) BB矛盾。(5),(7)b)A(BC)，(CD)E，F(DE) A(BF)(1) (A(BF) P(2) A(1)T,I(3) (BF) (1)T,I(4) B(3)T,I(5) F(3)T,(6) A(BC) P(7) BC (2)(6)T,I(8) C(4)(7)T,I(9) F(DE) P (10) D

14、E(5)(9)T,I(11) D (10)T,I(12) CD(8)(11)T,I (13) (CD) E P(14) E (12)(13)T,I(15) E (10)T,I(16) EE矛盾。(14),(15)c)ABCD，DEFAF(1) (AF) P(2) A(1)T,I(3) F(1)T,I(4) AB (2)T,I(5) (AB) CD P(6) CD (4)(5)T,I(7) C(6)T,I(8) D(6)T,I(9) DE (8)T,I(10) DEFP(11) F (9)(10)T,I(12) FF矛盾。(3),(11)d)A(BC)，BD，(EF)D，B(AE) BE(1)

15、(BE) P(2) B(1)T,I(3) E(1)T,I(4) BDP(5) D(2)(4)T,I(6) (EF) DP (7) (EF) (5)(6)T,I(8) E(7)T,I(9) EE 矛盾e)(AB)(CD)，(BE)(DF)，(EF)，ACA(1) (AB) (CD) P(2) AB(1)T,I(3) (BE) (DF) P(4) BE(3)T,I(5) AE(2)(4)T,I(6) (EF)P(7) EF(6)T,E(8) EF(7)T,E(9) AF(5)(8)T,I(10) CD (1)T,I(11) DF (3)T,I(12) CF (10)(10)T,I(13) AC P

16、(14) AF (13)(12)T,I(15) FA (14)T,E(16) AA (9)(15)T,I(17) AA (16)T,E(18) A(17) T,E(3) 用CP规则推证上题中的a)、b)、c)、d)各式证明：a)AB，CBAC(1) AP(2) AB P(3) B(1)(2)T,I(4) CB P(5) C(3)(4)T,I(6) ACCPb)A(BC)，(CD)E，F(DE)A(BF)(1) A P(2) A(BC) P(3) BC (1)(2)T,I(4) BP(5) C (3)(4)T,I(6) (CD) E P(7) C(DE) (6)T,E(8) DE (5)(7)T

17、,I(9) DE (8)T,E(10) (DE) (9)T,E(11) F(DE) P(12) F (10)(11)T,I(13) BF CP(14) A(BF) CPc)ABCD，DEFAF(1) AP(2) AB(1)T,I(3) ABCD P(4) CD(2)(3)T,I(5) D (4)T,I(6) DE (5)T,I(7) DEF P(8) F (6)(7)T,I(9) AF CPd)A(BC)，BD，(EF)D，B(AE)BE(1) BP(附加前提)(2) BD P(3) D (1)(2)T,I(4) (EF)DP(5) (EF) (3)(4)T,I(6) E (5)T,I(7)

18、BECP(4)证明下列各式，如果有必要，可使用间接证法证明：a) RQ，RS，SQ，PQP(1) RQP(2) RSP(3) SQP(4) Q(1)(2)(3)T,I(5) PQP(6) P (4)(5)T,Ib) SQ，SR，R，PQP证法一：(1) SRP(2) R P(3) S(1)(2)T,I(4) SQ P(5) Q(3)(4)T,I(6) PQP(7)(PQ)(QP) (6)T,E(8) PQ(7)T,I(9) P(5)(8)T,I证法二：（反证法）(1) PP（附加前提）(2) PQP(3)（PQ）(QP) (2)T，E(4) PQ(3)T,I(5) Q(1)(4)T,I(6)

19、SQ P(7) S (5)(6)T,I(8) SR P(9) R (7)(8)T,I(10) R P(11) RR 矛盾（9）（10）T，Ic)(PQ)(RS)，(QP)R)，RPQ(1) RP(2) (QP) R P(3) QP(1)(2)T,I(4)(PQ) (RS) P(5) (RS) (PQ)(4)T,E(6) RS (1)T,I(7) PQ (5)(6)(8) (PQ) (QP)(3)(7)T,I(9) PQ (8)T,E3.习题2-7 （1）、（2）、（3）(1) 证明下列各式a) (x)(A(x)B(x), ( x)B(x) ( $x)A(x)b) ($x)A(x)(x)B(x)

20、 ( x)(A(x)B(x)c) (x)(A(x)B(x), ( x)(C(x)B(x) (x)(C(x)A(x)d) (x)(A(x)B(x),( x)(B(x)C(x),( x)C(x) (x)A(x)证明：a)(x)(A(x)B(x) PA(u)B(u) US( x)B(x) PB(u) USA(u)B(u) TEA(u) TI ( $x)A(x) EGb)( x)(A(x)B(x) P（附加前提）( $x)(A(x)B(x) TE(A(c)B(c) ESA(c) TIB(c) TI( $x)A(x) EG ($x)A(x)(x)B(x) P(x)B(x) TIB(c) USB(c) B

21、(c) T矛盾c）(x)(A(x)B(x) PA(u)B(u) US( x)(C(x)B(x) PC(u)B(u) USB(u) A(u) TEC(u)A(u) TI(x)(C(x)A(x) UGd)(x)(A(x)B(x),( x)(B(x)C(x),( x)C(x) (x)A(x)( x)(B(x)C(x) PB(u)C(u) US( x)C(x) PC(u) USB(u) TI(x)(A(x)B(x) PA(u)B(u) USA(u) TI(x)A(x) UG(2) 用CP规则证明a) (x)(P(x)Q(x) ( x)P(x)(x)Q(x)b) (x)(P(x)Q(x) (x)P(x)

22、($x)Q(x)证明：a)( x)P(x) P（附加前提）P(u) US(x)(P(x)Q(x) PP(u)Q(u) USQ(u) TI(x)Q(x) UG( x)P(x)(x)Q(x) CPb)因为(x)P(x)($x)Q(x)(x)P(x) ($x)Q(x)故本题就是推证(x)(P(x)Q(x) (x)P(x) ($x)Q(x)(x)P(x) P（附加前提）( $x)P(x) TEP(c) ES(x)(P(x)Q(x) PP(c)Q(c) ESQ(c) TI( $x) Q(x) EG(x)P(x) ($x)Q(x) CP(3) a)所有的有理数都是实数某些有理数是整数，因此某些实数是整数解

23、：a)设R（x）：x是实数。Q（x）：x是有理数。I（x）：x是整数。本题符号化为： (x)(Q(x) R(x) ($x)(Q(x) I(x) ($x)(R(x) I(x)($x)(Q(x) I(x) PQ(c) I(c) ES(x)(Q(x) R(x) PQ(c) R(c) USQ(c) TIR(c) TII(c) TIR(c)I(c) TI($x)(R(x) I(x) EGb)任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或者喜欢乘汽车或者喜欢骑自行车，有的人不爱骑自行车，因而有的人不爱步行。设P（x）：x喜欢步行。Q（x）：x喜欢乘汽车。R（x）：x喜欢骑自行车本题符号化为： (x)(

24、P(x) Q(x), (x)(Q(x) R(x) , ($x) R(x) ($x) P(x)($x) R(x) PR (c) ES(x)(Q(x) R(x) PQ(c) R(c) USQ(c) TI(x)(P(x) Q(x) PP(c) Q(c) USP (c) TI($x) P(x) EGc)每个大学生不是文科学生就是理工科学生，有的大学生是优等生，小张不是理工科学生，但他是优等生，因而如果小张是大学生，他就是文科学生。设G（x）：x是大学生。L（x）：x是文科学生。P（x）：x是理工科学生。S（x）：x是优秀生。c：小张。本题符号化为：(x)(G(x) L(x)P(x), ($x)(G(x

25、) S(x), P (c) , S(c) G(c) L(c)G(c) P（附加前提）(x)(G(x) L(x)P(x) PG(c) L(c)P(c) USL(c)P(c) TIP (c) PL(c) TIG(c) L(c) CP注意：本题推证过程中未用到前提($x)(G(x) S(x)以及S(c)。主要是S（x）：x是优秀生，这个条件与其他前提的联系对证明结论没有影响，因S（x）与其他前提不矛盾，故本题的推证仍是有效的。4.习题3-10 （3）关系图表示法规定：(a)把、集合中的元素以点的形式全部画在平面上；(b)若，则xi和yi之间画一箭头弧线，反之不画任何联线。 5.习题3-11 （2）6

26、.习题3-12 （1）7.习题4-1 （1） 8.习题4-2 （1）9.习题5-1 （1）（2） 10.习题5-2（1）（2）11.习题7-1（2）12.习题7-2 （8）13.习题7-3 （3）（4）14.习题7-6 （6）15.习题7-8 （2）四、重要解题方法的整理：1.命题符号化命题符号化是指把一个用自然语言叙述的命题相应地写成由命题变元、联结词和圆括号表示的命题公式。符号化应该注意下列事项：（1）确定给定句子是否为命题。（2）句子中连词是否为命题联结词。（3）要正确地表示原子命题和适当选择命题联结词。2.求析取范式、合取范式、主析取范式、主合取范式的步骤求任一公式的析取范式和合取范式

27、的步骤: （1）利用蕴含等值式和等价等值式消去公式中的联结词“”和“”； （2）利用德摩根律和双重否定律将联结词“”向内深入，使之只作用于命题变元； （3）利用分配律将公式化为所需要的范式。等值演算求主析取范式的步骤：1、求A的析取范式2、消去析取范式中所有为永假的析取项3、合并相同的合取项和相同的变元4、对合取项补入没有出现的命题变元，即添加（PP式，然后，应用分配律展开公式。5、将极小项按由小到大的顺序排列。等值演算求主合取范式的步骤：1、求（A）的合取范式2、消去合取范式中所有为永真的合取项3、合并相同的析取项和相同的变元4、对析取项补入没有出现的命题变元，即添加（PP）式，然后，应用分

28、配律展开公式。5、将极大项按由小到大的顺序排列。3.用真值表验证推理的步骤（）检查真值表中H1，H2,Hm全部为“”的所有行，看结论是否也均为“”，若均为“”，则结论有效。否则结论无效。（）看结论为“”的所有行，检查每行前提H1，H2,Hm中是否至少有一个为，若有“”，则结论有效；若有均为“”的行，则结论无效。4.将自然语言翻译成谓词公式的步骤 （1）确定个体域，如无特别说明，一般使用全总个体域； （2）根据个体域，分析命题中的个体、个体性质以及各个个体间的关系，确定谓词； （3）根据表示数量的词确定量词； （4）利用联结词将整个命题符号化。5.约束变元的改名规则和自由变元的代入规则约束变元的

29、改名规则：(1)改名只对约束变元进行，不对自由变元进行；(2)改名必须处处进行，即对某量词约束的变元改名时，必须对原式中该变元的一切受该量词约束的约束出现改名；(3)对受某量词约束的变元改名时新名决不能与该量词的辖域中的其它自由变元同名；(4)改名前与改名后的约束关系保持不变。总之，正确的改名结果是每个变元只以一种形式出现，最多只受一个量词约束。自由变元的代入规则：代入的规则如下：(1)代入只对自由变元进行；(2)代入必须处处进行，即对某自由变元施行代入时，必须对该自由变元的一切自由出现施行代入；(3)代入前后的约束关系保持不变；(4)代入前先对原式改名，使原式中所有约束变元名与代入式中所有变元名互不相同，然后施行代入；(5)对命题变元和谓词