离散复习参考(修改).doc

集 合复习知识点1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan律等），文氏（Venn）图3、序偶与迪卡尔积本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 复习要求1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。2、掌握集合的表示法和集合的交、并、差、补等基本运算。3、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。 疑难解析集合的概念因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n。例1 设A，B是两个集合，A=1，2，3，B=1，2，则 。解 于是例2 已知序偶 = ，则x=_; y=_。例3 设Ax，y，z，Bx，z，则下列命题不正确的是 。ABA； B B A； C ABy； D AB x，y，z 例4设A=a，b，则= ，= 。例5 x 的幂集是 ，的幂集是 。例6设A=1,1，下列选项中错误的是 。 A B C D 例7设R=1,2,3，S=a,b,则= ，= 二元关系复习知识点1、关系、关系矩阵与关系图2、复合关系与逆关系 3、关系的性质（自反性、对称性、反对称性、传递性） 4、关系的闭包（自反闭包、对称闭包、传递闭包）5、等价关系与等价类6、偏序关系与哈斯图（Hasse）、极大/小元、最大/小元、上/下界、最小上界、最大下界本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、偏序关系复习要求1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。2、掌握求复合关系与逆关系的方法。3、理解关系的性质（自反性、对称性、反对称性、传递性），掌握其判别方法（定义、矩阵、图）。4、掌握求关系的闭包 （自反闭包、对称闭包、传递闭包）的方法。5、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/小元、上/下界、最小上界、最大下界的求法。疑难解析 1、关系的概念关系的概念是全章的基础，又是集合概念的应用。因此，学生应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。 2、关系的性质及其判定关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、偏序关系的基础。对于四种性质的判定，从概念上掌握，可以利用关系图和关系矩阵综合判定。如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。、关系的闭包在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记三个定理的结论：定理， ；定理3， ；定理4，推论 。、偏序关系及偏序集中特殊元素的确定理解与掌握偏序关系与偏序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大（小）元，极大（小）元也就容易了。这里要注意，最大（小）元与极大（小）元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同样。例1 设集合，判定下列关系，哪些是自反的，对称的，反对称的和传递的：解：均不是自反的；R4是对称的；R1 ,R2 ,R3 , R4 ,R5是反对称的；R1 ,R2 ,R3 , R4 ,R5是传递的。例2 设集合，A上的二元关系R为 （）写出R的关系矩阵，画出R的关系图；（）R是A上的偏序关系，画出其哈斯图；（）若，且，求B的最大元，最小元，极大元，极小元，最小上界和最大下界。解 （1）R的关系矩阵为 R的关系图略 （2） (A,R)为偏序集， (A,R)的哈斯图如下 。4 。1 。3 。2 。5 (3) 当，B的极大元为2，4；极小元为2，5；B无最大元与最小元；B也无上界与下界，更无最小上界与最大下界。例3 设R=1,2,3，S=a,b，则= 。例4设A=1，2，3，则A上的二元关系有 个。A 23 ； B 32 ； C ； D 。例5设A=1,2,3，R是A上的二元关系，当a，bA且ab时，R，则R的前域为 ，R的值域为 。例6设集合A=1, 2, 3 ,4，A上的关系R=, ，则R不具有 性质。 A.自反性 B.对称性 C.传递性 D. 反对称性例7集合A=a，b，c，d，集合A上的二元关系R=,试画出关系R的关系图，并求出R的自反闭包，对称闭包和传递闭包。例8设A1,2,3,4,5,6,7，8,9，R为集合A上模4同余关系（即R=|y-x能被4整除），求出A中各元素关于R的等价类，并写出该等价关系对应的划分。例9 集合a,b,c上共有 个不同的等价关系。例10 设集合，A上的关系，则=（ ）。 A例11 设集合A=a，b，c，A上的关系R=（a，b），（a，c），（b，a），（b，c），（c，a），（c，b），（c，c），则R具有关系的（ ）性质。A自反 B对称 C传递 D反对称例12 设R和S是集合上的关系，其中，试求： （1）写出R和S 的关系矩阵；（2）计算。解：（1） （2）=（1，2），（3，4） =（1，1），（1，2），（1，3），（2，3），（2，4）， （3，4），（4，4） =（1，1），（3，1），（3，2），（4，3） =（2，1），（4，3） 例13 设A=a，b，c，d，R1，R2是A上的关系，其中R1=（a，a），（a，b），（b，a），（b，b），（c，c），（c，d），（d，c），（d，d），R2=（a，b），（b，a），（a，c），（c，a），（b，c），（c，b），（a，a），（b，b），（c，c）。（1） 画出R1和R2的关系图；（2） 判断它们是否为等价关系，是等价关系的求A中各元素的等价类。解： R1和R2的关系图略。 由关系图可知，R1是等价关系。R1不同的等价类有两个，即a，b和c，d。由于R2不是自反的，所以R2不是等价关系。例14设集合A=1,2,3,4, A上的二元关系R的关系矩阵为MR则关系R的表达式是( )(A) , (B) , (C) , (D) ,15设集合Aa,b,c,给出A上的二元关系R，S，使得R，S均具有传递性，但RS不具有传递性。 命题逻辑复习知识点、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题、命题公式与解释，真值表，公式分类（恒真、恒假、可满足），公式的等价、析取范式、合取范式，极小（大）项，主析取范式、主合取范式 、公式类别的判别方法（真值表法、等值演算法、主析取/合取范式法）、公式的蕴涵与逻辑结果、形式演绎本章重点内容：命题与联结词、公式与解释、析取范式与合取范式、公式恒真性的判定、形式演绎复习要求、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。、理解公式与解释的概念；掌握求给定公式真值表的方法，用基本等价式化简其他公式，公式在解释下的真值。、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等价式或真值表将公式化为主析取（合取）范式的方法。、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价的方法。、理解公式蕴涵与逻辑结果的概念，掌握基本蕴涵式。6、掌握形式演绎的证明方法。 疑难解析1、公式恒真性的判定判定公式的恒真性，包括判定公式是恒真的或是恒假的。具体方法有两种，一是真值表法，对于任给一个公式，主要列出该公式的真值表，观察真值表的最后一列是否全为1（或全为0），就可以判定该公式是否恒真（或恒假），若不全为0，则为可满足的。二是推导法，即利用基本等价式推导出结果为1，或者利用恒真（恒假）判定定理：公式G是恒真的（恒假的）当且仅当等价于它的合取范式（析取范式）中，每个子句（短语）均至少包含一个原子及其否定。这里要求的析取范式中所含有的每个短语不是极小项，一定要与求主析取范式相区别，对于合取范式也同样。2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等价式中的分配律、同一律和互补律，结果的前一步适当使用等幂律，使相同的短语（或子句）只保留一个。另外，由已经得到的主析取（合取）范式，根据原理，可以求得主合取（析取）范式。3、形式演绎法掌握形式演绎进行逻辑推理时，一是要理解并掌握14个基本蕴涵式，二是会使用三个规则：规则P、规则T和规则CP，需要进行一定的练习。例1下列语句中哪个是真命题 。A. 我正在说谎。 B. 请勿喧哗。 C. 如果4+4=8,那么5+6=12。 D. 如果4+4=9,那么5+6=12。例2 求的主析取范式与主合取范式。解 （1）求主析取范式， 方法1：利用真值表求解G 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1000000111010101101011111 因此 方法2：推导法 （2）求主合取范式方法1：利用上面的真值表为0的有两行，它们对应的极大项分别为因此，方法2：利用已求出的主析取范式求主合取范式已用去6个极小项，尚有2个极小项，即 与 于是 例3 试证明公式为恒真公式（重言式）。证法一：（真值表法）证法二 ： G=（PQ）（QR）（PR） =（PQ）（QR）PR =（PQ）（PR）（QQ）（QR）P）R =（PQP）（PRP）（QRP）R =（1（QRP）R =QRPR =1故G为恒真公式。例4 利用形式演绎法证明 P（QR），SP，Q蕴涵SR。证明：（1）SP P（2）S P（附加条件）（3）P T（1），（2） （4）P（QR） P （5）QR T（3），（4） （6）Q P （7）R T（5），（6） （8）SR CP（2），（7）例5 用形式演绎法证明：PQ， RS，PR 蕴涵QS。证明：（1） PR P （2） RP T（1） （3） PQ P （4） R Q T（2）（3） （5） QR T（4） （6） RS P （7） QS T（5）（6）（8） QS T（7） 例6利用基本等价式证明下面命题公式为恒真公式。（PQ）（QR）（PR）证明： （PQ）（QR）（PR） （PQ）（QR）（PR） （PQ）（QR）（PR）（PQ）（QR）PR （PQ）P ）（QR）R）（1（QP ）（QR）1） QPQR （QQ） P R 1 P R 1 例7设P：天下雨，Q：天刮风，H：我去书店。则将命题“如果天不下雨，而且也不刮风，我就去书店”符号化为 。 谓词逻辑复习知识点 1、谓词、量词、个体词、个体域、变元（约束变元与自由变元）2、谓词公式与解释，谓词公式的类型（恒真、恒假、可满足）3、谓词公式的等价和蕴涵4、前束范式本章重点内容：谓词与量词、公式与解释、前束范式复习要求1、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；了解命题符号化。2、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。3、理解用解释的方法证明等价式和蕴涵式。疑难解析1、谓词与量词反复理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的自由性、约束性与改名规则。2、公式与解释能将一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后将解释I中的数值代入公式，求出真值。典型例题例1 设I是如下一个解释： 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求的真值。解 例2 试将一阶逻辑公式化成前束范式。解 例3 中，约束变元是 。A. x B.y C.z D. x 和 z例4 利用谓词的约束变元改名规则和自由变元代入规则，可将如下公式：（x）（P（x）R（x，z）Q（x，z）改写成 。 A（x）（P（y）R（x，y）Q（z，s） B（z）（P（z）R（z，s）Q（x，s） C（x）（P（s）R（x，s）Q（x，y） D（s）（P（s）R（s，z）Q（x，y）例5在谓词演算中，P(a)是的有效结论，其理论根据是 。A.全称指定规则（US） B. 全称推广规则（UG） C. 存在指定规则（ES） D. 存在推广规则（EG）例6表达式x$yL（x，y）中谓词的定义域是a，b，c，将其中的量词消除，写成与之等价的命题公式为 （L（a，a）L（a，b）L（a，c）（L（b，a）L（b，b）L（b，c）（L（c，a）L（c，b）L（c，c）例7设解释I为：（1） 定义域D=-2，3，6；（2） F（x）：x3；G（x）：x5。 在解释I下求公式$x（F（x）G（x）的真值。解： $x（F（x）G（x） （F（-2）G（-2）（F（3）G（3）（F（6）G（6） （10）（10）（01） 1 例8设F(x)：x是鸟，G(x)：x会飞翔。则命题“鸟都会飞”符号化为( )例9试求谓词公式中，x,$x,$y的辖域，试问R(x,y)和A(x,y)中x,y是自由变元，还是约束变元？例10在谓词公式(x)（P（x，y）(y)Q（x,y）(z)R(x,z)中，(x)中量词的作用域是 。 例11若用公式(x)（P（x） S (x)）表示命题有些人不聪明，则其否定命题可以被表示为 。例12考虑以下赋值。论域D=1，2； 指定谓词P（1）=T，P（2）=F，Q（1）=F，Q（2）=T，则(x)P（x）(x)Q（x）的真值为 。例13 谓词公式()（）（）的前束范式为 。例14谓词公式（）（）（）中约束变元为 ，自由变元为 。例15设个体域Da, b,那么谓词公式消去量词后的等值式为 图论复习知识点1、图、完全图、子图2、关联矩阵、邻接矩阵、可达性矩阵3、权图、路4、树、K叉树、二叉树 5、权图中的最小树，克鲁斯卡尔算法（Kruskal）6、有向图、有向树本章重点内容： 通路的计算、最小生成树、最优K叉树复习要求1、理解图的有关概念：图、完全图、子图。2、掌握图的矩阵表示（关联矩阵、邻接矩阵）。3、理解权图、路的概念。4、理解树、二叉树的有关概念；，用Kruskal算法求权图中最小树的方法。5、理解有向图与有向树的概念。 疑难解析 1.本章的概念较多，学习时需要认真比较各概念的含义，如：图、子图、有向图、权图；树、二叉树、有向树；路、简单路、回路等，这些都是图的基本概念，今后将在数据结构、数据库、计算机网络等课程中用到。2、权图中的最小生成树 使用克鲁斯卡尔（Kruskal）算法。典型例题例1 在具有n个顶点的完全图Kn中删去多少条边才能得到树？解：n个顶点的完全图Kn中共有n（n-1）/2条边，n个顶点的树应有n-1条边， 于是，删去的边有：n（n-1）/2-（n-1）=（n-1）（n-2）/2例2设G是由5个顶点组成的完全图，则从G中删去（ C ）条边可以得到树。A4 B5 C6 D10例3已知图G的相邻矩阵为，则G有（ C ）。 A.5点，8边 B. 6点，7边 C. 5点，7边 D. 6点，8边例4设有5个城市v1，v2，v3，v4，v5，任意两城市之间铁路造价如下：（以百万元为单位）w（v1，v