《离散数学》总复习

《离散数学》总复习黄玉划[e-mail]南航计算机学院A12-1161.主范式、集合、布尔格(有补分配格)运算2.命题符号化+命题/谓词逻辑推理3.前束范式4.元素与集合、集合与集合的关系(判断,证明)5.排列组合、容斥原理、递推方程6.关系合成、函数复合、置换乘法7.等价关系(等价类、商集、划分、自然映射)8.偏序集(偏序关系、覆盖、哈斯图)、格9.同构=同态∩双射10.代数系统及其性质(判断)11.域=整环∩除环0.重要概念:幂集,笛卡积,闭包,积代数,循环群;0.重要概念:生成子图,自补图,自对偶图,割集12.握手定理13.邻接矩阵14.最短路径(标号法)与关键路径(最长路径)15.图的类型(二部,欧拉,哈密顿,平面,树)判别16.平面图欧拉公式：nm+r=217.树的重要性质：m=n-118.最小生成树(避圈法)、基本回路/割集系统19.Huffman算法(最优二元树/最佳前缀码)20.二/多项式定理与组合恒等式21.分治算法的常用递推公式第1章命题逻辑1.1命题符号化及联结词（联结词是基础）1.2命题公式及分类1.3等值演算1.4联结词全功能集1.5对偶与范式（主范式演算是重点）1.6推理理论（重点）联结词与复合命题(小结)联结词优先级:(),,,,,同级按从左到右的顺序进行pqpp∧qp∨qpqpq0010011011011010001001101111基本复合命题的真值1.3命题逻辑等值演算等值式定义：(AB1)(AB)（重点）基本等值式(重点)双重否定律:AA等幂律：AAA,AAA交换律:ABBA,ABBA结合律:(AB)CA(BC)(AB)CA(BC)分配律:A(BC)(AB)(AC)A(BC)(AB)(AC)德·摩根律:(AB)AB(AB)AB基本等值式（续）吸收律:A(AB)A,A(AB)A零律:A11,A00同一律:A0A,A1A排中律:AA1矛盾律:AA0蕴涵等值式:ABAB等价等值式:AB(AB)(BA)假言易位:ABBA等价否定等值式:ABAB归谬论:(AB)(AB)A1.4复合联结词（重要的非重点）与非式:pq(pq)；或非式:pq(pq)习题1.14，1.10(4)(5)异或：pqpq(pq)pqpqAp1p2…pn,偶数个命题变项赋值为1(A0),奇数个命题变项赋值为1(A1);Bq1q2…qn,偶数个命题变项赋值为0(A1),奇数个命题变项赋值为0(A0).习题1.221.5主范式（重点）成真赋值i对应主析取范式的极小项mi；成假赋值j对应主合取范式的极大项Mj。命题公式有几个成真赋值，主析取范式就是几个极小项相或()；命题公式有几个成假赋值，主合取范式就是几个极大项相与()。例1.31，1.32分配律BjBj(pipi)(Bjpi)(Bjpi)BjBj(pipi)(Bjpi)(Bjpi)习题1.12(1),1.13(1)。五71.6命题逻辑推理（重点）“推理正确”定义：(AB1)(AB)（重点）A(AB)附加律(AB)A化简律(AB)AB假言推理(AB)BA拒取式(AB)BA析取三段论(AB)(BC)(AC)假言三段论(AB)(BC)(AC)等价三段论(AB)(CD)(AC)(BD)构造性二难(AB)(AB)(AA)B构造性二难(特殊形式)(AB)(CD)(BD)(AC)破坏性二难习题1.18,1.21,1.17(2)。六1注意事项1：命题只有能确定真假(但不能可真可假)的陈述句才是命题.不管是正确的观点,还是错误的观点,都是命题.猜想和预言是命题,如哥德巴赫猜想.感叹句,祈使句,疑问句都不是命题.陈述句中的悖论以及判断结果不惟一确定的也不是命题.有些简单命题貌似复合命题,要注意区分.题1(15)注意事项2：蕴涵联结词“”pq的逻辑关系:p为q的充分条件，q为p的必要条件.“如果p,则q”的多种表述方式：(1)若p,就q.(2)只要p,就q.(3)p仅当q.(4)只有q才p.(5)除非q,才p.(6)除非q,否则非p.pq为假当且仅当p为真q为假，即当p为假时，pq为真(不管q为真,还是为假);当q为真时，pq为真(不管p为真,还是为假).习题1.5(6)(7)了解概念、掌握方法真值表、命题公式类型所有等值的含n个命题变项的公式对应同一个n元真值函数F:{0,1}n{0,1}；哑元最小联结词组对偶式与对偶原理简单析取式、简单合取式析取范式与合取范式附加前提证明法、反证法第2章一阶逻辑2.1一阶逻辑基本概念（量词是关键）2.2一阶逻辑公式、解释及分类2.3一阶逻辑等值式、前束范式（重点）2.4一阶逻辑推理理论（重点）一阶逻辑与命题逻辑关系一阶逻辑将命题(公式)拆分为个体词、谓词、量词(、)。谓词是核心，没有谓词，不构成命题；量词是关键。个体词（元素）分为个体常项和个体变项.个体域（集合）:个体变项的取值范围.全总个体域:宇宙间一切事物组成一阶逻辑≈命题逻辑+量词xF(x)xF(x),xF(x)xF(x);xF(x)xF(x),xF(x)xF(x)2.3一阶逻辑等值式基本等值式（重点）:命题逻辑中16组基本等值式的代换实例消去量词等值式设D={a1,a2,…,an}xA(x)A(a1)A(a2)…A(an)xA(x)A(a1)A(a2)…A(an)量词辖域收缩与扩张等值式x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)量词分配等值式x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)注意事项1：前束范式（重点）设A为一个一阶逻辑公式,若A具有如下形式Q1x1Q2x2…QkxkB,则称A为前束范式,其中Qi(1ik)为或，B为不含量词的公式.1）对无分配律，对无分配律xA(x)xB(x)xy(A(x)B(y))xy(A(x)B(y))xA(x)xB(x)2）变量冲突，有一个要换名.3）x(A(x)B)xA(x)Bx(A(x)B)xA(x)B习题2.21,2.15(1),2.14(1)。四102.4一阶逻辑推理理论（重点）重要的推理定律第一组命题逻辑推理定律代换实例第二组由基本等值式生成（置换规则）第三组xA(x)xB(x)x(A(x)B(x))x(A(x)B(x))xA(x)xB(x)(12)全称量词消去规则（简记为UI规则或UI）(13)全称量词引入规则（简记为UG规则或UG）(14)存在量词引入规则（简记为EG规则或EG）(15)存在量词消去规则（简记为EI规则或EI）注:必须先消去存在量词,后消去全称量词.七1第三版:习题2.22,2.16,2.19,2.17(1),2.23；例2.18注意事项2：一阶逻辑中命题符号化无特别要求，用全总个体域量词顺序一般不要随便颠倒xyA(x,y)yxA(x,y)全称量词一般对应“”存在量词一般对应“”习题2.3(2)(5)(6)了解有限个体域,无限个体域;谓词常项,谓词变项,一元谓词,多元谓词(n元谓词,n2),0元谓词,原子公式;项字母表包含：1)个体常项,2)个体变项,3)函数符号,4)谓词符号,5)量词符号(,),6)联结词符号(,,,,),7)括号与逗号.指导变元，辖域，约束出现，自由出现闭式:不含自由出现的个体变项的公式.解释I包含：(a)非空个体域DI,(b)DI中一些特定元素集,(c)DI上特定函数集,(d)DI上特定谓词集.闭式在任何解释下都是命题，不是闭式的公式在某些解释下也可能是命题.公式类型.换名规则与代替规则第3章集合的基本概念和运算3.1集合的基本概念3.2集合的基本运算（重点）3.3集合中元素的计数（容斥原理是重点）3.1集合的基本概念元素x与集合A的关系：属于xA，不属于xA集合A与集合B的关系：习题3.2,3.8,3.12,3.16包含(子集)AB,不包含A⊈B相等A=B,不相等AB真包含AB,不真包含AB重要概念：集合A的幂集P(A)={x|xA}。如果|A|=n，则|P(A)|=2n.习题3.14(4),3.18习题3.3,3.9,3.113.2集合的基本运算（重点）集合运算符，，，分别对应联结词∧,∨，，AB=AB=A(AB)AB=(AB)(BA)=(AB)(AB)ABAABABAB=BAB=AAB=AB=AB=A习题3.17,3.16；例3.17，3.18。四3，4；六4集合运算的文氏图表示习题3.4,3.15(2)集合运算的算律（重点）交换AB=BAAB=BAAB=BA结合(AB)C=A(BC)(AB)C=A(BC)(AB)C=A(BC)幂等AA=AAA=A与与分配A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)吸收A(AB)=AA(AB)=A吸收律的前提：、可交换集合运算的算律（续）D.M律A(BC)=(AB)(AC)A(BC)=(AB)(AC)(BC)=BC(BC)=BC双重否定A=AE补元律AA=AA=E零律A=AE=E同一律A=AAE=A否定=EE=3.3集合中元素的计数|...|)1(...|||||||...|21111121mmmkjikjimimjijiimAAAAAAAAAAAA容斥原理及其推论（重点）习题3.6,3.18,3.19。五10注意1）0是自然数.2）对于任何集合A和元素x(可以是集合)，xA和xA两者成立其一，且仅成立其一.3）和是不同层次的问题.4）空集是任何集合的子集.5）在给定问题中，全集E包含任何集合，即A(AE)了解概念、掌握方法1）集合的表示法：列元素法A={a,b,c,d}谓词表示法B={x|P(x)}.习题3.10(4)2）文氏图与文氏图法.习题3.63）集合A的基数cardA=|A|=n4）证明XY命题演算法包含传递法等价条件法反证法并交运算法5）证明X=Y命题演算法等式代入法反证法运算法第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算（重点）4.3关系的性质（基础）4.4关系的闭包4.5等价关系和偏序关系（重点）4.6函数的定义和性质4.7函数的复合和反函数4.1集合的笛卡儿积和二元关系1）重要概念：集合A与B的笛卡儿积AB={x,y|xAyB}.若|A|=m,|B|=n,则|AB|=mn分配律A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)