1、离散数学复习资料离散数学复习资料第1章 命题逻辑 本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, (主)析取(合取)范式，命题逻辑的推理理论. 一、重点内容 1. 命题 命题表述为具有确定真假意义的陈述句。命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义. 2. 六个联结词及真值表 h“?”否定联结词，P是命题，?P是P的否命题，是由联结词 ? 和命题P组成的复合命题.P取真值1，?P取真值0，P取真值0，?P取真值1. 它是一元联结词. h “?”合取联结词，P?Q是命题P，Q的合取式，是“?”和P，Q组成的复合命题. “?”在语句中相当于“不但而且”
2、，“既又”. P?Q取值1，当且仅当P，Q均取1；P?Q取值为0，只有P，Q之一取0. h “?”析取联结词，“?”不可兼析取(异或)联结词， P?Q是命题P，Q的析取式，是“?”和P，Q组成的复合命题. P?Q是联结词“?”和P，Q组成的复合命题. 联结词“?”或“?”在一个语句中都表示“或”的含义，前者表示相容或，后者表示排斥或不相容的或. 即“P?Q”?“(?P?Q)?(P?Q)”. P?Q取值1，只要P，Q之一取值1，P?Q取值0，只有P，Q都取值0. h “?”蕴含联结词， P?Q是“?”和P，Q组成的复合命题，只有P取值为1，Q取值为0时，P?Q取值为0；其余各种情况，均有P?Q的
3、真值为1，亦即1?0的真值为0，0?1，1?1，0?0的真值均为1. 在语句中，“如果P则Q”或“只有Q，才P，”表示为“P?Q”.h “?” 等价联结词，P?Q是P，Q的等价式，是“?”和P，Q组成的复合命题. “?”在语句中相当于“当且仅当”，P?Q取值1当且仅当P，Q真值相同.3. 命题公式、赋值与解释，命题公式的分类与判别 h命题公式与赋值，命题P含有n个命题变项P1，P2,Pn，给P1，P2,Pn各指定一个真值，称为对P的一个赋值(真值指派). 若指定的一组值使P的真值为1，则这组值为P的真指派；若使P的真值为0，则称这组值称为P的假指派. h命题公式分类，在各种赋值下均为真的命题公
4、式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式；判定命题公式类型的方法：其一是真值表法，任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式.其二是推导演算法. 利用基本等值式(教材的十六个等值式或演算律)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式.既非永真，也非用假，成为非永真的可满足式.其三主析取(合取)范式法，该公式的主析取范式有2n个极小项(即
5、无极大项)，则该公式是永真式；该公式的主合取范式有2n个极大项(即无极小项)，则该公式是永假式；该公式的主析取(或合取)范式的极小项(或极大项)个数大于0小于2n,，则该公式是可满足式.h等值式A?B，命题公式A，B在任何赋值下，它们的真值均相同，称A，B等值。定理1 设?(A)是含命题公式A的命题，?(B)是用命题公式B置换?(A)中的A之后得到的命题公式. 如果A?B，则?(A)?(B). 4. 范式 h 析取(合取)范式，仅有有限个简单合取式(析取式)构成的析取式(合取式)，就是析取(合取)范式. h 极小项(极大项)，n个命题变项P1,P2,Pn，每个变项或它的否定两者只有其一出现且仅
6、出现一次，第i个命题变项或者其否定出现在从左起第i个位置上(无脚标时，按字典序排列)，这样的简单合取式(析取式)为极小项(极大项). 以两个命题变项为例，m00=?P?Q，m01=?P?Q,m10=P?Q,m11=P?Q是极小项;M00=P?Q，M01=P?Q,M10=?P?Q,M11=?P?Q是极大项. h 主析取范式(主合取范式) 含有n个命题变项的命题公式，如果与一个仅有极小项(极大项)的析取(合取)构成的析取(合取)范式等值，则该等值式称为原命题公式的主析取(合取)范式。 每项含有n个命题变项(变项字母齐全)的合取式(析取式)的析取(合取)为主析取(合取)范式. 任意命题公式都存在与之
7、等值的范式，存在与之等值的主范式，且是惟一的. 求范式，包括求析取范式、合取范式、主析取范式和主合取范式. 关键有两点：其一是准确掌握范式定义；其二是巧妙使用基本等值式中的分配律、同一律和摩根律，结果的前一步适当使用幂等律. 求析取(合取)范式的步骤： 将公式中的联结词都化成?，?，?(即消去个数中的联结词?，?，?)； 将否定联结词?消去或移到各命题变项之前； 利用分配律、结合律等，将公式化为析取(合取)范式.求命题公式A的主析取(合取)范式的步骤： 求公式A的析取(合取)范式； “消去”析取(合取)范式中所有永假式(永真式)的析取项(合取项)，如P?P(P?P)用0(1)替代. 用幂等律将
8、析取(合取)范式中重复出现的合取项(析取项)或相同的变项合并，如P?P(P?P)用P替代，mi?mi(Mi?Mi)用mi(Mi)替代. 若析取(合取)范式的某个合取项(析取项)B不含有命题变项Pi或?Pi，则添加Pi?Pi(Pi?Pi)，再利用分配律展开，使得每个合取项(析取项)的命题变项齐全； 将极小(极大)项按由小到大的顺序排列，用?(?)表示. 5. 命题演算的推理理论 h设A1,A2,An,C是命题公式，如果是重言式，称C是前提集合 A1,A2,An的有效结论或A1,A2,An逻辑地推出C。记作 掌握演绎或形式证明. 要理解并掌握14个重言蕴含式(即I1I14)，17个等值式(E1E1
9、7)；二是会使用三个规则(P规则、T规则和CP规则)。 推理方法有： 真值表法；等值演算法；主析取范式法，构造证明法(直接证明法、附加前提证明法和间接证明法)第2章 谓词逻辑 本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明. ? 一、重点内容 1. 谓词与量词 h谓词，在谓词逻辑中，原子命题分解成个体词和谓词. 个体词是可以独立存在的客体，它可以是具体事物或抽象的概念。谓词是用来刻划个体词的性质或事物之间关系的词. 个体词分个体常项(用a,b,c,表示)和个体变项(用x,y,z,表示)；谓词分谓词常项(表示具体性质和关系)和谓词变项(表示抽象的或泛指的谓词)，用F,G,P,表示.
10、 注意，单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题. h量词，是在命题中表示数量的词，量词有两类：全称量词?，表示“所有的”或“每一个”；存在量词?，表示“存在某个”或“至少有一个”. 在谓词逻辑中，使用量词应注意以下几点： (1)在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变. (2)在考虑命题符号化时，如果对个体域未作说明，一律使用全总个体域. (3)多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的含义. 谓词公式只是一个符号串，没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成一个命题. 所谓解释就是使公式中的每一个变项都有个体域
11、中的元素相对应. 在谓词逻辑中，命题符号化必须明确个体域，无特别说明认为是全总个体域。一般地，使用全称量词?，特性谓词后用?；使用存在量词?，特性谓词后用?.2. 公式与解释 h谓词公式，由原子公式、联结词和量词可构成谓词公式(严格定义见教材). 命题的符号化结果都是谓词公式. 例如?x(F(x)?G(x)，?x(F(x)?G(x)，?x?y(F(x)?F(y)?L(x,y)?H(x,y)等都是谓词公式. h变元与辖域，在谓词公式?xA和?xA中，x是指导变元，A是相应量词的辖域. 在?x和?x的辖域A中，x的所有出现都是约束出现，即x是约束变元，不是约束出现的变元，就是自由变元. 也就是说，
12、量词后面的式子是辖域. 量词只对辖域内的同一变元有效. h换名规则，就是把公式中量词的指导变元及其辖域中的该变元换成该公式中没有出现的个体变元，公式的其余部分不变. h代入规则，就是把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的这个符号. h解释(赋值)，谓词公式A的个体域D是非空集合，则 (1) 每一个常项指定D中一个元素； (2) 每一个n元函数指定Dn到D的一个函数； (3) 每一个n元谓词指定Dn到0,1的一个谓词；按这个规则做的一组指派，称为A的一个解释或赋值.在有限个体域下，消除量词的规则为：如Da1,a2,an，则 h谓
13、词公式分类，在任何解释下，谓词公式A取真值1，公式A为逻辑有效式(永真式)；在任何解释下谓词公式A取真值0，公式A为永假式；至少有一个解释使公式A取真值1，公式A称为可满足式. 3. 前束范式 一个谓词公式的前束范式仍是谓词公式. 若谓词公式F等值地转化成 那么就是F的前束范式，其中Q1，Q2，Qk只能是?或?，x1,x2,xk是个体变元，B是不含量词的谓词公式. 每个谓词公式F都可以变换成与它等值的前束范式. 其步骤如下： 消去联结词?，?，?； 将联结词?移至原子谓词公式之前； 利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同；将?x,?x移至整个公式最左边
14、； 得到公式的前束范式. 4.谓词逻辑的推理理论 谓词演算的推理是命题演算推理的推广和扩充，命题演算中的基本等值公式，重言蕴含式以及P，T，CP规则在谓词演算中仍然使用. 在谓词演算推理中，某些前提和结论可能受到量词的限制，为了使用这些推理，引入消去和附加量词的规则，有US规则(全称量词消去规则)，UG规则(全称量词附加规则)，ES规则(存在量词消去规则)，EG规则(存在量词附加规则)等，以便使谓词演算公式的推理过程可类似于命题演算的推理进行. 第3章 集合与关系 本章重点：集合概念，集合的运算，集合恒等式的证明，笛卡儿积. ? 一、重点内容 1. 集合的概念h集合与元素，具有确定的，可以区分
15、的若干事物的全体称为集合，其中的事物叫元素.集合A中元素的个数为集合的元数?A?. h集合的表示方法：列举法和描述法. 列举集合的元素，元素不能重复出现，集合中的元素无顺序之分. 集合与其元素之间存在属于“?”或不属于“?”关系.2. 集合的关系：包含，子集，集合相等. h包含(子集)，若，则B包含A(或A包含于B)，称A是B的子集，记，又A?B，则A是B的真子集，记A?B. h集合相等，若A?B，B?A，则AB. 注意：元素与集合,集合与子集，子集与幂集，?与?(?)，空集?与所有集合等的关系. 3. 特殊集合：全集、空集和幂集. h全集合E，在一个具体问题中，所涉及的集合都是某个集合的子集
16、，该集合为全集. h空集?，不含任何元素的集合为空集. 空集是惟一的，它是任何集合的子集. h集合A的幂集P(A)，有集合A的所有子集构成的集合P(A)=. 若?A?n, 则?P(A)?=2n. 4. 集合的运算 h集合A和B的并A?B，由集合A和B的所有元素组成的集合. h集合A和B的交A?B，由集合A和B的公共元素组成的集合. h集合A的补集?A，属于E但不属于集合A的元素组成的集合，?A. 补集总相对于一个全集. h集合A与B的差集AB，由属于A，而不属于B的所有元素组成的集合. h集合A与B的对称差A?B，A?B(AB)?(BA)或A?B）A?B（A?B）应该很好地掌握10条运算律(运
17、算的性质)(教材P7172)，即交换律、结合律、分配律、幂等律、同一律、零律、补余律、吸收律、摩根律和双补律等. 5. 恒等式证明 集合运算部分有三个方面的问题：其一是进行集合的运算；其二是集合运算式的化简；其三是集合恒等式的推理证明. 集合恒等式的证明方法通常有二：(1)要证明AB，只需要证明A?B，又A?B；(2)通过运算律进行等式推导. 6. 有序对与笛卡儿积 h有序对，就是有顺序的数组，如，x,y 的位置是确定的，不能随意放置. 注意：有序对?，以a,b为元素的集合a,b=b,a；有序对(a,a)有意义，而集合a,a是单元素集合，应记作a. h笛卡儿积，把集合A，B合成集合AB，规定A
18、B?x?A?y?B由于有序对中x,y的位置是确定的，因此AB的记法也是确定的，不能写成BA. 笛卡儿积也可以多个集合合成，A1A2An. 笛卡儿积的运算性质. 一般不能交换.第4章 二元关系与函数 本章重点：关系概念与其性质，等价关系和偏序关系，函数. ? 一、重点内容 1. 关系的概念 包括定义、关系的表示方法：集合表示、矩阵表示、图形表示. h二元关系，是一个有序对集合，设集合A,B，记作xRy二元关系的定义域：Dom(R)； 二元关系的值域：Ran(R)h关系的表示方法： 集合表示法：关系是集合，有类似于集合的表示方法. 列举法，如R,；描述法：如 关系矩阵： R?AB，R的矩阵关系图：
19、 R是集合上的二元关系，若?R，由结点aI画有向弧到bj构成的图形.2. 几个特殊的关系空关系?；唯一是任何关系的子集的关系. 全关系恒等关系，MI是单位矩阵. 3. 关系的运算h关系的集合运算，有并、交、补、差和对称差.h复合关系 ，有 复合关系矩阵：(布尔运算)，有结合律：(R?S)?TR?(S?T) h逆关系，(R?S)1=S1?R1. 4. 关系的性质 h自反性 ；矩阵的主对角线元素全为1；关系图的每个结点都有自回路.h反自反性 ；矩阵的主对角线元素全为0；关系图的每个结点都没有自回路.h对称性 若，则；矩阵是对称矩阵，即；关系图中有向弧成对出现,方向相反.h反对称性 若且，则x=y或
20、若，则；矩阵不出现对称元素.h传递性 若且，则；在关系图中，有从a到b的弧，有从b到c的弧，则有从a到c的弧. 判断传递性较为困难.可以证明：R是集合A上的二元关系，(1)(1)R是自反的?IA?R; (2)R是反自反的?IA?R?;(3)R是对称的 ?RR1； (4)R是反对称的?R?R1?IA；(5)R是传递的?R?R?R. 关系的性质所具有的运算见表41. 表41 二元运算的并、交、补、差、逆、复合具有的性质表运算 关系性质自反性反自反性对称性反对称性传递性 R1 ? ? ? ? ? R1?R2 ? ? ? ? ? R1?R2 ? ? ? ? ? R1R2 ? ? ? ? ? R1?R2
21、 ? ? ? ? ? IA? ? ? ? ? ?由表可见，IA具有自反性，对称性、反对称性和传递性.EA具有自反性，对称性和传递性.故IA，EA是等价关系.?具有反自反性、对称性、反对称性和传递性。?是偏序关系.关系性质的判定，可以用定义、关系矩阵或关系图. 传递性的判定，难度稍大. 也常如下判定：不破坏传递性的定义，可认为具有传递性. 例如?可认为具有传递性，同时具有对称性和反对称性，但是不具有自反性； 5. 关系的闭包 设R是非空集合A上的二元关系，在关系R中，添加最少的有序对，新关系用R?表示，使得R?具有关系的自反(对称、传递)性质，R?就是R的自反(对称、传递)闭包，记作r(R) ，
22、s(R)和t(R)。闭包的求法： 定理12：；定理13：；定理14的推论： 6. 等价关系和偏序关系 极大(小)元、最大(小)元问题 h等价关系和偏序关系是具有不同性质的两个关系. h等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从a到b，从b到c各有一条有向弧线，则从a到c一定有有向弧线。 h等价类，若R是等价关系，与R中的某个元素等价的元素组成的集合，就是R的一个等价类，aR=b?b?A?aRb. h偏序集的哈斯图 偏序集概念和偏序集的哈斯图。哈斯图的画法：(1) 用空心点表示结点，自环不画；(2) 若a?b，则结点b画在上边，a画在下边，并画a到b
23、的无向弧；(3) 若,?,则?R，此时，a到c的有向弧不画出.确定任一子集的最大(小)元，极大(小)元. 极大(小)元、最大(小)元、界 一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一. 且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样. 7. 函数 h函数, 设f是集合A到B的二元关系，?a?A,?b?B,且?f，且Dom(f)=A，f是一个函数(映射). 函数是一种特殊的关系.集合AB的任何子集都是关系，但不一定是函数. 函数要求对于定义域A中每一个元素a，B中有
24、且仅有一个元素与a对应，而关系没有这个限制. 二函数相等是指：定义域相同，对应关系相同，而且定义域内每个对应值都相同. h函数的类型单射 若满射 f(A)=B. 即双射 单射且满射. h复合函数即. 复合成立的条件是：一般，但复合函数的性质： 如果f,g都是单射的，则f?g是单射的； 如果f,g都是满射的，则f?g是满射的；如果f,g都是双射的，则f?g是双射的； 如果f,g是单射的，则f是单射的；如果f,g是满射的，则g是满射的；如果f?,g是双射的，则f是单射的，g是满射的. h反函数 若f：A?B是双射，则有反函数f1：B?A ，第5章 代数结构 本章重点：代数运算及性质，群的概念，置换
25、和置换群、交换群和循环群. ? 一、重点内容 1.代数运算及其性质h二元运算，非空集合A上的函数(映射) f：A2?A就是A上的二元代数运算，就是说二元运算是一个变换(对应关系). 代数运算的性质：h交换律 ?x,y?A，有x?y=y?x，?在A上适合交换律. h结合律 ?x,y?A，有(x?y)?zx?(y?z)，运算?在A上适合结合律. h分配律 ?x,y,z?A，有x?(y?z)=(x?y)?(x?z) 或(y?z)?x=(y?x)?(z?x)，? 对 ? 适合分配律. h幂等律 ?x?A，有x?x=x，则运算?在A上适合幂等律. h 吸收律 ?x,y?A, 有x?(x?y)=x, x?
26、(x?y)=x，? 和 ? 满足吸收律. h单位元 el, (或er)?A，对?x?A, 有el?x=x (x?er=x), el(或er)是A的运算?的左单位元(或右单位元). e既是右单位元又是左单位元就是单位元. h逆元 对x?A，若x1?A, 有x1?x=x?x1=e，x1是x的逆元.h代数系统 在非空集合A上，定义了若干代数运算f1,f2,fm, (A, f1,f2,fm)称为代数系统. 若B?A，f1,f2,fm在B上成立，(B, f1,f2,fm)称为子代数系统. 2.群 h代数系统注意：由上可见，代数系统、半群、群(子群)是一条线下来，条件逐步加强，半群和群是我们讨论的重点.
27、h群的性质：(1) (a1)1=a; (2) (a*b)1=b1*a1;(3) am*an=am+n;(4) (am)n=amn; (5)(方程的可解性) 方程a*x=b或y*a=b有唯一解； (6) (消去律) 由a*c=b*c或 c*a=c*b，可得a=b3. 特殊群h交换群，群(G,*)的二元运算*满足交换律，(G,*)是交换群(阿贝尔群) . h循环群，群G能表成G=ak?k?Z，a?G G是循环群. 记作G(a)，a是群G的生成元.h变换群 设A是一个非空集合，A上的所有一一变换构成的集合E(A), 对于变换乘法，E(A)构成一个群，称为集合A上的一一变换群. E(A)的子群称为变换
28、群.h置换群，n元集合M上的所有n元置换Sn，关于置换乘法构成n元对换群，它的子群叫置换群. 4. 置换，h置换，有限集合Ma1,a2,an上的双射?：M?M，n元置换 h置换复合(乘法)，设, 那么h单位置换， h逆置换，?1=n元集合M上的n元置换有n!个，有n元置换构成的集合，记作Sn. h轮换，满足：(1)?(a1）=a2, ?(a2）=a3, ,?(am）=a1； (2)?(a)=a，当a?ak,(k=1,2,m)时. 则?是一个长度为m的轮换，记作(a1,a2,am). h重要结论：置换有结合律；不相交的轮换有交换律；Sn中任一置换都可以唯一地表示成一系列不相交的轮换之积. 5.
29、同态与同构h同态，代数系统(G,*)和(S, ?)，f是从G到S上的一个映射. ?a,b?G，有f(a*b)=f(a) ?f(b)则称f是由(G,*)到(S, ?)的一个同态映射. 并称G与S同态. 如果f 是满射，则称G与S是满同态，记作GS；如果f是单射，则称G与S是单同态. (f(G), ?)称为(G,*)在f下的同态象. h同构，代数系统(G,*)到(S, ?)，如果f是从G到S的一个双射，则称f是从G到S的同构，h群同构，设群(G,*)和(S, ?)，存在从(G,*)到(S, ?)的同态双射，则称群(G,*)与(S, ?)同构. 第7章 几种特殊的图本章重点：欧拉图和哈密顿图、平面图
30、和树的基本概念. 一、重点内容 1. 欧拉图 h 欧拉通路(回路)与欧拉图 通过图G的每条边一次且仅一次，而且走遍每个结点的通路(回路)，就是欧拉通路(回路). 存在欧拉回路的图就是欧拉图. 欧拉回路要求边不能重复，结点可以重复. 笔不离开纸，不重复地走完所有的边，且走过所有结点，就是所谓的一笔画. h欧拉图或通路的判定 (1) 无向连通图G是欧拉图?G不含奇数度结点(G的所有结点度数为偶数):(定理1) (2) 非平凡连通图G含有欧拉通路?G最多有两个奇数度的结点；(定理1的推论) (3) 连通有向图D含有有向欧拉回路(即欧拉图)?D中每个结点的入度出度连通有向图D含有有向欧拉通路?D中除两个结点外，其余每个结点的入度出度，且此两点满足deg(u)deg(v)?1. (定理2) 2. 哈密顿图h哈密
