离散数学复习要点第一章命题逻辑 一、典型考查点 1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P1 2、联结词运算定律┐∧∨→记住特殊的：1∧1?1，0∨0?0，1→0?0，11?1，00?1详见P5 3、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P5 4、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P9 5、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。 6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15 7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A?B的充要条件是A?B且B?A。主要等价式：(1)双否定：??A?A。(2)交换律：A∧B?B∧A，A∨B?B∨A，A?B?B?A。3)结合律：(A∧B)∧C?A ∧(B∧C)，(A∨B)∨C?A∨(B∨C)，(A?B)?C?A?(B?C)。(4) 分配律：A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。(5) 德·摩根律：?(A∧B)??A∨?B，?(A∨B)??A∧?B。(6) 等幂律：A∧A?A，A∨A?A。(7) 同一律：A∧T?A，A∨F?A。(8) 零律：A∧F?F，A∨T?T。(9) 吸收律：A∧(A∨B)?A，A∨(A∧B)?A。(10) 互补律：A∧?A?F，(矛盾律)，A∨?A?T。(排中律)(11) 条件式转化律：A→B??A∨B，A→B??B→?A。(12) 双条件式转化律：A?B?(A→B)∧(B→A)?(A∧B)∨(?A∧?B) 8、蕴含式详见P23表1.6.3 证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。④用定义，证A?B，即证A→B是永真式。 9、范式求法步骤：①使用命题定律，消去公式中除∧、∨和?以外公式中出现的所有联结词；②使用?(?P)?P和德·摩根律，将公式中出现的联结词?都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧P?P。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则P?P∧（?Q∨Q)或P?P∨（?Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。 注意：主析取范式与主合取范式之间的联系。例如：(P→Q)∧Q?m1∨m3?M0∧M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P16 11、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。 重点规则（主要蕴含式）：(1) P∧Q?P化简(2) P∧Q?Q化简(3) P?P∨Q附加(4) ?P?P→Q变形附加(5)Q?P→Q变形附加(6) ?(P→Q)?P变形化简(7) ?(P→Q)??Q变形化简(8) P，(P→Q)?Q假言推理(9) ?Q，(P→Q)??P拒取式(10) ?P，(P∨Q)?Q析取三段论(11) (P→Q)，(Q→R)?P→R条件三段论(12) (P?Q)，(Q?R)?P?R 双条件三段论 文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。详见P21 二、强化练习 1.命题的是( )A.走，看电影去B.x+y>0C.空集是任意集合的真子集D.你明天能来吗? 2.下列式子为重言式的是( ) A.P→P∨Q B.(┐P∧Q)∧(P∨┐Q) C.┐ (P Q) D.(P∨Q) (P→Q) 3．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 4．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的 5．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q） D．?（? P∨? Q） 6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式D．等价式 7．命题公式?（P∧Q）→R的成真指派是（） A．000，001，110，B．001，011，101，110，111 C．全体指派D．无
离散数学必备知识点总 结 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT
总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系；
2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基 2种不同的关系； 数为mn，A到B上可以定义mn 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系；
第四章代数结构（作业） 作业：P86：4、7、9 4、 （1）若a和b是整数，则a+b+ab也是整数，故a*b也是整数，所以运算*是封闭的。（2）任选整数集合中的三个元素x,y和z。则有： (x*y)*z = (x+y+xy)*z = (x+y+xy)+z+(x+y+xy)×z = x+y+z+xy+xz+yz+xyz x*(y*z) = x*(y+z+yz) = x+(y+z+yz)+x×(y+z+yz) = x+y+z+yz+xy+xz+xyz = (x*y)*z 因此，*运算满足结合律。 （3）假设e为（Z,*）的幺元，则有： 任选整数集中的一个元素x，都有 0*x = 0+x+0×x=x且 x*0 = x+0+x×0=x 故0是(Z,*)的幺元。 7、N+上的所有元素都是（N+ ,*）等幂元； （N+ ,*）无幺元； （N+ ,*）的零元为1。 9、（A,*）中的等幂元：a、b、c、d； （A,*）中的幺元：b； （A,*）中的零元：c； a-1 = d，b-1 = b，c-1 不存在，d-1 = a， 作业：P87：12、13、18 12、（A，*）到（N4,⊕4）的同构映射f为： f(a)=0, f(b)=1, f(c)=2, f(d)=3; 或者： f(a)=0, f(b)=3, f(c)=2, f(d)=1; 13、同构映射f为： f(0)=?, f(1)={a}, f(2)={b}, f(3)={a,b};
或者： f(0)=?, f(1)={b}, f(2)={a}, f(3)={a,b}; 18、任选a ∈N +,b ∈N +, 只需证明f(a+b)=f(a)+f(b) 由f 的定义可知：f(a+b)=2a+2b=f(a)+f(b)，故f 是（N +,+）到(E +,+)的同态映射。 作业：P96：3，P97：7 3、(1)显然，*运算对Z 是封闭的。 (2) (a*b)*c = (3(a+b+2)+ab)*c = 3((3(a+b+2)+ab)+c+2)+(3(a+b+2)+ab)×c = 3(3a+3b+c+ab+8+ac+bc+2c)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc a*(b*c) = a*(3(b+c+2)+bc) = 3(a+(3(b+c+2)+bc)+2)+a(3(b+c+2)+bc) = 3(a+3b+3c+bc+8+ab+ac+2a)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc = (a*b)*c 故*运算满足结合律。 （3）任选a ∈Z ，(-2)*a=a 且a*(-2)=a ，所以-2是(Z,*)的幺元。 所以（Z,*）是独异点。 7、因为1为(A,*)运算的幺元，而且对任意A 的子集A ’,*在A ’上都是封闭和可结合的运算，因此，（A,*）的所有子独异点为(A ’,*)，其中A ’必须包含1。即：(A,*)的所有子独异点为： ({1},*),({1,2},*),({1,3},*),({1,4},*),({1,2,3},*),({1,2,4},*),({1,3,4},*),({1,2,3,4},*) P105：3、4、13 3、??????1100b a ×??????220 0b a ＝??? ?? ?212100b b a a ,a 1,a 2∈{1,-1}, 所以a 1×a 2∈{1,-1}，b 1×b 2∈{1,-1}。 故（G,×）是封闭的。 而 (??????1100b a ×??????2200b a )×??????3300b a =??????212 100b b a a ×????? ?3300b a =??????3213 2100b b b a a a ??????1100b a ×(????? ?22 00b a ×??????3300b a )=??????1100b a ×??????323 200b b a a =??????3213210 0b b b a a a 故（G,×）是可结合的。（也可以说因为矩阵乘法是可结合的。）
离散数学 一、逻辑和证明 1.1命题逻辑 命题：是一个可以判断真假的陈述句。 联接词：∧、∨、→、?、?。记住“p仅当q”意思是“如果p，则q”，即p→。记住“q除非p”意思是“?p→q”。会考察条件语句翻译成汉语。 系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。 1.3命题等价式 逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。
谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如?x>0P(x)。 当论域中的元素可以一一列举，那么?xP(x)就等价于P(x1)∧P(x2)...∧P(xn)。同理，?xP(x)就等价于P(x1)∨P(x2)...∨P(xn)。 两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如?x（P(x)∧Q(x))和(?xP(x))∧(?xQ(x))。 量词表达式的否定：??xP(x) ??x?P(x)，??xP(x) ??x?P(x)。 1.5量词嵌套 我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。 1.6推理规则 一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证
二、集合、函数、序列、与矩阵 2.1集合 ∈说的是元素与集合的关系，?说的是集合与集合的关系。常见数集有N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。 A和B相等当仅当?x(x∈A?x∈B)；A是B的子集当仅当?x(x∈A→x∈B)；A是B的真子集当仅当?x(x∈A→x∈B)∧?x(x?A∧x∈B)。 幂集：集合元素的所有可能组合，肯定有?何它自身。如?的幂集就是{?}，而{?}的幂集是{?，{?}}。 考虑A→B的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。 一对一或者单射：B可能有多余的元素，但不重复指向。 映上或者满射：B中没有多余的元素，但可能重复指向。 一一对应或者双射：符合上述两种情况的函数关系。 反函数：如果是一一对应的就有反函数，否则没有。 合成函数：fοg(a)=f(g(a))，一般来说交换律不成立。 2.4序列 无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。 如果A和B是可数的，则A∪B也是可数的。
数理逻辑部分 第2章一阶逻辑 2.1 一阶逻辑基本概念 个体词（个体）: 所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域: 个体变项的取值范围 有限个体域，如{a, b, c}, {1, 2} 无限个体域，如N, Z, R, … 全总个体域: 宇宙间一切事物组成 谓词: 表示个体词性质或相互之间关系的词 谓词常项：F(a)：a是人 谓词变项：F(x)：x具有性质F 一元谓词: 表示事物的性质 多元谓词(n元谓词, n≥2): 表示事物之间的关系 如L(x,y)：x与y有关系L，L(x,y)：x≥y，… 0元谓词: 不含个体变项的谓词, 即命题常项或命题变项 量词: 表示数量的词 全称量词?: 表示任意的, 所有的, 一切的等 如?x 表示对个体域中所有的x
存在量词?: 表示存在, 有的, 至少有一个等 如?x表示在个体域中存在x 一阶逻辑中命题符号化 例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1) 墨西哥位于南美洲 在命题逻辑中, 设p:墨西哥位于南美洲 符号化为p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲 符号化为F(a) 例2 在一阶逻辑中将下面命题符号化 (1)人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域 . 解：(a) (1) 设G(x)：x爱美, 符号化为?x G(x) (2) 设G(x)：x用左手写字, 符号化为?x G(x) (b) 设F(x)：x为人，G(x)：同(a)中
习题5 1．设个体域D={a,b,c}，消去下列各式的量词： (1) x y(F(x)∧G(y)) (2) x y(F(x)∨G(y)) (3) xF(x)→yG(y) (4) x(F(x,y)→yG(y)) 答案 (1) x y(F(x)∧G(y)) xF(x)∧yG(y) (F(a)∧F(b))∧F(c))∧(G(a)∨G(b)∨G(c)) (2) x y(F(x)∨G(y)) xF(x)∨yG(y) (F(a)∧F(b)∧F(c))∨(G(a)∧G(b)∧G(c)) (3) xF(x)→yG(y) (F(a)∧F(b)∧F(c))→(G(a)∧G(b)∧G(c)) (4) x(F(x,y)→yG(y)) xF(x,y)→yG(y) (F(a,y)∨F(b,y)∨F(c,y))→(G(a)∨G(b)∨G(c)) 2．设个体域D={1,2}，请给出两种不同的解释I1和I2，使得下面公式在I1下都是真命题，而在I2下都是假命题。 (1) x(F(x)→G(x)) (2) x(F(x)∧G(x)) .(1) 答案 I1: F(x):x≤2,G(x):x≤3 F(1),F(2),G(1),G(2)均为真，所以 x(F(x)→G(x)) (F(1)→G(1)∧(F(2)→G(2))为真。 I2: F(x)同I1,G(x):x≤0 则F(1),F(2)均为真，而G(1),G(2)均为假， x(F(x)→G(x))为假。 (2)留给读者自己做。 3．给定解释I如下： (a) 个体域D={3,4}。 (b) (x)为(3)=4，(4)=3。 (c) (x,y)为(3,3)=(4,4)=0，(3,4)=(4,3)=1。 答案 试求下列公式在I下的真值： (1) x yF(x,y) (2) x yF(x,y)
说明： 定义:红色表示。 定理性质：橙色表示。 ?公式：蓝色表示。 ?算法:绿色表示 页码:灰色表示 数理逻辑： 1.命题公式:命题, 联结词(,，，，），合式公式,子公式 2.公式的真值：赋值，求值函数,真值表,等值式，重言式,矛盾式 3.范式：析取范式，极小项,主析取范式，合取范式，极大项,主合取范式 4.联结词的完备集：真值函数，异或,条件否定，与非,或非，联结词完备集 5.推理理论：重言蕴含式,有效结论,P规则,T规则, ＣP规则，推理 6.谓词与量词:谓词，个体词,论域,全称量词,存在量词 7.项与公式:项，原子公式，合式公式，自由变元,约束变元，辖域，换名，代入 8.公式语义:解释，赋值,有效的，可满足的,不可满足的 9.前束范式:前束范式 10.推理理论:逻辑蕴含式，有效结论，-规则(US)，+规则(ＵG), -规则(ＥS)， +规则(ＥG), 推理 集合论： 1.集合: 集合, 外延性原理, , , , 空集, 全集, 幂集，文氏图, 交, 并， 差, 补, 对称差 2.关系: 序偶, 笛卡尔积, 关系, ｄomR，ｒａnR，关系图, 空关系, 全域关系， 恒等关系 3.关系性质与闭包：自反的, 反自反的，对称的, 反对称的, 传递的，自反闭包 r(R), 对称闭包 s(R），传递闭包 t(Ｒ) 4.等价关系: 等价关系, 等价类, 商集, 划分 5.偏序关系:偏序，哈斯图，全序（线序), 极大元／极小元，最大元／最小元， 上界/下界 6.函数: 函数，常函数, 恒等函数, 满射,入射，双射,反函数，复合函数 7.集合基数：基数, 等势，有限集／无限集，可数集, 不可数集 代数结构: 1.运算及其性质：运算,封闭的，可交换的,可结合的,可分配的,吸收律, 幂等的,幺 元,零元,逆元 2.代数系统:代数系统，子代数,积代数,同态,同构。 3.群与子群:半群,子半群,元素的幂，独异点，群，群的阶数，子群,平凡子群，陪集, 拉格朗日(Lａgranｇe)定理 4.阿贝尔群和循环群：阿贝尔群(交换群),循环群，生成元 5.环与域：环，交换环,含幺环,整环,域 6.格与布尔代数：格，对偶原理,子格,分配格,有界格,有补格，布尔代数,有限布尔代 数的表示定理 图论: 1.图的基本概念：无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、 补图,握手定理，图的同构
数理逻辑部分 第1章命题逻辑 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。 简单命题(原子命题)：简单陈述句构成的命题 复合命题：由简单命题与联结词按一定规则复合而成的命题 简单命题符号化 用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示 简单命题 用“1”表示真，用“0”表示假 例如，令p：是有理数，则p 的真值为 0 q：2 + 5 = 7，则q 的真值为 1 联结词与复合命题 1.否定式与否定联结词“” 定义设p为命题，复合命题“非p”（或“p的否定”）称 为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假. 2.合取式与合取联结词“∧” 定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p 与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题 例将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解令p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) p∧q. 令r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令t : 张辉与王丽是同学，t 是简单命题 . 说明:
第5章 一.填空题 1. 群中有唯一的（）。 2. 如果群运算是可交换的，则群为（）。 3. 设*是定义在集合A上的二元运算，如果对于A中任意的两个元素x,y，都有x*y∈A，则称二元运算*在A上是（）。 4. 设*是定义在集合A上的二元运算，如果对于A中任意的两个元素x,y，都有x*y=y*x，则称二元运算*在A上是（）。 5. 设★是定义在有理数集合Q上的二元运算，如果对于Q中任意的两个元素x,y，都有x★y=x+y-x*y，其中*表示普通乘法元算，则二元运算★在Q 上是（）。（填写可交互/不可交换） 6. 设*是定义在集合A上的二元运算，如果对于A中任意的元素x,y,z，都有(x*y)*z=x*(y*z) ，则称二元运算*在A上是（）。 7. 设★是定义在非空集合A上的二元运算，如果对于A中任意的两个元素x,y，都有x*y=y， 则二元运算★在A上是（）。（填写可结合/不可结合） 8. 设*，★是定义在集合A上的两个二元运算，如果对于A中任意的元素x,y,z，都有(x*y) ★z=（x★z）*(y★z)，z★(x*y)=(z★x)*(z★y),则称二元运算★对于*在A上是（）。 9. 设*，★是定义在集合A上的两个可交换的二元运算，如果对于A中任意的元素x,y，都有x*(x★y)=x, x★(x*y)=x,则称二元运算*对于★在A上满 足（）。 10. 设*是定义在集合A上的二元运算，如果对于A中任意的元素x，都有x*x=x，则称二元运算*是（）。 11. 设*是定义在集合A上的二元运算，如果在A中存在元素el，对于A中任意的元素x，都有el*x=x，则称el为A中关于运算*的（）。 12. 设*是定义在集合A上的二元运算，如果在A中存在元素ol，对于A中任意的元素x，都有ol*x=x，则称ol为A中关于运算*的（）。 13. 设*是定义在集合A上的二元运算，如果在A中存在元素er，对于A中任意的元素x，都有x*erl =x，则称er为A中关于运算*的（）。 14. 设*是定义在集合A上的二元运算，如果在A中存在元素or，对于A中任意的元素x，都有x*or=x，则称or为A中关于运算*的（）。 15. 如果对于集合中的二元运算*，存在左零元和右零元，且左零元等于右零元，则零元是（）。 16. 如果对于集合中的二元运算*，存在左么元和右么元，且左么元等于右么元，则么元是（）。 17. 设*是定义在集合A上的二元运算，且e是A中关于运算*的么元，如果对于A中的元素x，存在A中的元素y，有y*x=e，则称y为x的 （）。 18. 对于实数域上的乘法元算，每个元素（）逆元。（填写一定有/不一定有） 19. 对于实数域上的加法运算，（）零元。（填写存在/不存在） 20. 对于整数域上的加法运算，（）么元。（填写存在/不存在） 21. 对于非空集合S上二元运算*，是封闭且可结合的，那么
总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项 (m) 之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为 0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项 时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R 的顺序依次写； 6.真值表中值为 1 的项为极小项，值为0 的项为极大项； 7.n 个变元共有2n个极小项或极大项，这2n为(0~ 2n -1)刚好为化简完 后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法 (=>) ：真值表法；分析法 (假定前键为真推出后键 为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则， T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取 ^;
3.既有存在又有全称量，先消存在量，再消全称量； 第四章集合 1.N ，表示自然数集， 1,2,3 ??，不包括 0； 2.基：集合 A 中不同元素的个数， |A|； 3.集：定集合 A，以集合 A 的所有子集元素成的集合，P(A) ； 4.若集合 A 有 n 个元素，集 P(A) 有2 n个元素， |P(A)|= 2| A| = 2 n； 5.集合的分划： (等价关系 ) ①每一个分划都是由集合 A 的几个子集构成的集合； ② 几个子集相交空，相并全(A)； 6.集合的分划与覆盖的比： 分划：每个元素均出且出一次在子集中； 覆盖：只要求每个元素都出，没有要求只出一次； 第五章关系 1.若集合 A 有 m 个元素，集合 B 有 n 个元素，笛卡 A×B 的基数mn， A 到 B 上可以定2mn种不同的关系； 2.若集合 A 有 n 个元素， |A ×A|= n2，A 上有2n2个不同的关系； 3.全关系的性：自反性，称性，性； 空关系的性：反自反性，反称性，性；
【半群】G非空，·为G上的二元代数运算，满足结合律。 【群】（非空，封闭，结合律，单位元，逆元）恰有一个元素1适合1·a=a·1=a,恰有一个元素a-1适合a·a-1=a-1·a=1。 【Abel群/交换群】·适合交换律。可能不只有两个元素适合x2=1 【置换】n元置换的全体作成的集合Sn对置换的乘法作成n 次对称群。 【子群】按照G中的乘法运算·,子集H仍是一个群。单位子群{1}和G称为平凡子群。 【循环群】G可以由它的某元素a生成,即G=（a）。a所有幂的集合an，n=0，±1，±2，…做成G的一个子群，由a生成的子群。若G的元数是一个质数，则G必是循环群。 n元循环群（a）中,元素ak是（a）的生成元的充要条件是（n，k）=1。共有?（n）个。【三次对称群】{I（12）（13）（23）（123）（132）} 【陪集】a，b∈G，若有h∈H，使得a =bh，则称a合同于b（右模H），a≡b（右mod H）。H有限，则H的任意右陪集aH的元数皆等于H的元数。任意两个右陪集aH和bH或者相等或者不相交。 求右陪集：H本身是一个；任取a?H而求aH又得到一个；任取b?H∪aH而求bH又一个。G=H∪aH∪bH∪… 【正规子群】G中任意g，gH=Hg。（H=gHg-1对任意g∈G都成立） Lagrange定理G为有限群，则任意子群H的元数整除群G的元数。 1有限群G的元数除以H的元数所得的商，记为（G：H），叫做H在G中的指数，H的指数也就是H的右（左）陪集的个数。 2设G为有限群,元数为n,对任意a∈G，有an=1。 3若H在G中的指数是2，则H必然是G的正规子群。证明：此时对H的左陪集aH，右陪集Ha，都是G中元去掉H的所余部分。故Ha=aH。 4G的任意多个子群的交集是G的子群。并且，G的任意多个正规子群的交集仍是G的正规子群。 5 H是G的子群。N是G的正规子群。命HN为H的元素乘N的元素所得的所有元素的集合，则HN是G的子群。 【同态映射】K是乘法系统，G到K的一个映射σ（ab）=σ（a）σ（b）。 设（G，*），（K，+）是两个群，令σ：x→e，?x∈G，其中e是K的单位元。则σ是G到K 内的映射，且对a，b∈G，有σ（a*b）=e=σ（a）+ σ（b）。即，σ是G到K的同态映射，G～σ（G）。σ（G）={e}是K的一个子群。这个同态映射是任意两个群之间都有的。 【同构映射】K是乘法系统，σ是G到σ（G）上的1-1映射。称G与σ（G）同构，G?G′。同构的群或代数系统，抽象地来看可以说毫无差别。G和G′同态，则可以说G′是G的一个缩影。 【同态核】σ是G到G′上的同态映射，核N为G中所有变成G′中1′的元素g的集合，即N=σ-1（1′）={g∈G∣σ（g）=1′}。 N是G的一个正规子群。对于Gˊ的任意元素aˊ，σ-1(aˊ)={x|x∈G ,σ(x)= aˊ}是N在G 中的一个陪集。Gˊ的元素和N在G中的陪集一一对应。 设N是G的正规子群。若A，B是N的陪集，则AB也是N的陪集。 【环】R非空，有加、乘两种运算 a+b=b+a2）a+（b+c）=（a+b）+c， 3）R中有一个元素0，适合a+0=a， 4）对于R中任意a,有-a,适合a+(-a)=0， 5）a（bc）=（ab）c，
离散数学笔记 第一章命题逻辑 合取 析取 定义 1. 否定：当某个命题为真时.其否定为假.当某个命题为假时.其否定为真定义 1. 条件联结词.表示“如果……那么……”形式的语句 定义 1. 双条件联结词.表示“当且仅当”形式的语句 定义合式公式 (1)单个命题变元、命题常元为合式公式.称为原子公式。 (2)若某个字符串 A 是合式公式.则?A、(A)也是合式公式。 (3)若 A、B 是合式公式.则 A ∧B、A∨B、A→ B、A?B 是合式公式。 (4)有限次使用(2)~(3)形成的字符串均为合式公式。 等值式 析取范式与合取范式
将一个普通公式转换为范式的基本步骤
推理 定义 设 A 与 C 是两个命题公式. 若 A → C 为永真式、 重言式.则称 C 是 A 的有 效结论.或称 A 可以逻辑推出 C.记为 A => C 。（用等值演算或真值表） 第二章 谓词逻辑 、基本概念 ?：全称量词 ?：存在量词 一般情况下. 如果个体变元的取值范围不做任何限制即为全总个体域时. 带 “全称量词”的谓词公式形如"?x(H(x)→B(x)).即量词的后面为条件式.带“存在量词”的谓词公式形如?x(H(x)∨WL(x)).即量词的后面为合取式 例题 R(x)表示对象 x 是兔子.T(x)表示对象 x 是乌龟. H(x,y)表示 x 比 y 跑得快.L(x,y)表示x 与 y 一样快.则兔子比乌龟跑得快表示为： ?x ?y(R(x)∧T(y)→H(x,y)) 有的兔子比所有的乌龟跑得快表示为：?x ?y(R(x)∧T(y)→H(x,y)) 、谓词公式及其解释 定义 、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22 y x 的 f(x,y))、 谓词常元(如表示人 类的 H(x))。 定义 、逻辑符号：个体变元、量词(??)、联结词(﹁∨∧→?)、逗号、括号。 定义 、项的定义：个体常元、变元及其函数式的表达式称为项(item)。 定义 、原子公式：设 R(n x x ... 1)是 n 元谓词.n t t ...1是项.则 R(t)是原子公式。原子公式中的个体变元.可以换成个体变元的表达式(项).但不能出现任何联结词与量词.只能为单个的谓词公式。 定义 合式公式：(1)原子公式是合式公式；(2)若 A 是合式公式.则(﹁A)也是合式公式；(3)若 A,B 合式.则 A ∨B, A ∧B, A →B , A ?B 合式(4)若 A 合式.则?xA 、?xA 合式(5)有限次使用(2)~(4)得到的式子是合式。 定义 量词辖域：?xA 和?xA 中的量词?x/?x 的作用范围.A 就是作用范围。 定义 约束变元：在?x 和?x 的辖域 A 中出现的个体变元 x.称为约束变元.这是与量词相关的变元.约束变元的所有出现都称为约束出现。 定义 自由变元：谓词公式中与任何量词都无关的量词.称为自由变元.它的每次出现称为自由出现。一个公式的个体变元不是约束变元.就是自由变元。 注意：为了避免约束变元和自由变元同名出现.一般要对“约束变元”改名.而不对自由变元改名。 定义 闭公式是指不含自由变元的谓词公式 从本例(已省)可知. 不同的公式在同一个解释下. 其真值可能存在. 也可能不存在. 但是对于没有自由变元
说明： 定义：红色表示。 定理性质：橙色表示。 公式：蓝色表示。 算法:绿色表示 页码：灰色表示 数理逻辑： 1.命题公式：命题，联结词(，，，，)，合式公式，子公式 2.公式的真值：赋值，求值函数，真值表，等值式，重言式，矛盾式 3.范式：析取范式，极小项，主析取范式，合取范式，极大项，主合取范式 4.联结词的完备集：真值函数，异或，条件否定，与非，或非，联结词完备集 5.推理理论：重言蕴含式，有效结论，P规则，T规则， CP规则，推理 6.谓词与量词:谓词，个体词，论域，全称量词，存在量词 7.项与公式:项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入 8.公式语义:解释，赋值，有效的，可满足的，不可满足的 9.前束范式:前束范式 10.推理理论:逻辑蕴含式，有效结论，-规则（US），+规则（UG），-规则(ES)， +规则(EG), 推理 集合论： 1.集合: 集合, 外延性原理, , , , 空集, 全集, 幂集, 文氏图, 交, 并, 差, 补, 对称差 2.关系: 序偶, 笛卡尔积, 关系, domR, ranR, 关系图, 空关系, 全域关系, 恒等关 系 3.关系性质与闭包:自反的, 反自反的, 对称的, 反对称的, 传递的,自反闭包 r(R), 对称闭包 s(R), 传递闭包 t(R) 4.等价关系: 等价关系, 等价类, 商集, 划分
5.偏序关系:偏序, 哈斯图, 全序(线序), 极大元/极小元, 最大元/最小元, 上界/下 界 6.函数: 函数, 常函数, 恒等函数, 满射,入射,双射，反函数, 复合函数 7.集合基数:基数, 等势, 有限集/无限集, 可数集, 不可数集 代数结构： 1.运算及其性质：运算，封闭的,可交换的,可结合的,可分配的,吸收律, 幂等的，幺 元,零元,逆元 2.代数系统：代数系统，子代数，积代数，同态，同构。 3.群与子群：半群,子半群,元素的幂，独异点，群，群的阶数，子群,平凡子群，陪集， 拉格朗日（Lagrange）定理 4.阿贝尔群和循环群：阿贝尔群(交换群)，循环群,生成元 5.环与域：环，交换环，含幺环，整环，域 6.格与布尔代数：格，对偶原理，子格，分配格，有界格，有补格，布尔代数，有限 布尔代数的表示定理 图论： 1.图的基本概念：无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、 补图，握手定理，图的同构 2.图的连通性:通路，回路，简单通路，简单回路（迹）初级通路（路径），初级回路 （圈），点连通，连通图，点割集，割点，边割集，割边，点连通度，边连通度，弱连通图，单向连通图，强连通图，二部图（二分图） 3.图的矩阵表示：关联矩阵，邻接矩阵，可达矩阵 4.欧拉图与哈密顿图：欧拉通路、欧拉回路、欧拉图、半欧拉图，哈密顿通路、哈密 顿回路、哈密顿图、半哈密顿图 5.无向树与根树：无向树，生成树，最小生成树，Kruskal，根树，m叉树，最优二叉 树，Huffman算法 6.平面图:平面图，面，欧拉公式，Kuratoski定理
离散数学复习资料 一、填空 1. 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x 为实数，y x y x L >:),(则命题的逻辑谓词公式为 。 2. 设p ：王大力是100米冠军，q ：王大力是500米冠军，在命题逻辑中，命题“王大力不 但是100米冠军，而且是500米冠军”的符号化形式为 。命题“存在一个人不但是100米冠军，而且是500米冠军”的符号化形式为____。 3. 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集” 则A= 。 4. 设 P （x ）：x 是素数， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数y 。则谓词 (()(()(,)))x P x y O y N y x ?→?∧ 的自然语言是 对于任意一个素数都存在一个奇数使 该素数都能被整除 。 5. 设个体域是{a,b}，谓词公式()()()()x P x x P x ??∨?写成不含量词的形式是 。 6. 谓词(((,)(,))(,,))x y z P x z P y z uQ x y u ???∧→?的前束范式为 。 7. 命题公式)))(((R Q Q P P A →?∧→?∨?的主合取范式为 ，其编码表示为 。 8. 设E 为全集， ，称为A 的绝对补，记作～A ，且～（～A ）= ，～E = ， ～Φ= 。 9. 设={256},{234},{134}A B C ==， ，，，，，，则A-B= ，A ⊕B = ，A ×C = 。 10. 设},,{c b a A =考虑下列子集}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =，
习题13参考答案 1.图13.9中给出六个偏序集的哈斯图。判断其中哪些是格。如果不是格,说明理由。 图13.9 答案：(1),(3),(6)是格。(2)中的{e,d}没有最大下界。(4)中的{d,e}没有最大下界。(5)中的{a,b}没有最大下界。 2.下列各集合对于整除关系都构成偏序集,判断哪些偏序集是格。 (1) L={1,2,3,4,5} (2) L={1,2,3,6,12} (3) L={1,2,3,4,6,9,12,18,36} (4) L={1,2,22,...,2n},n∈Z+ 答案：(1)不是格,其他都是。
3.(1)画出Klein四元群的子群格。 (2)画出模12的整数群Z12的子群格。 (3)画出3元对称群S3的子群格。 答案：(1) (2) (3) 4.设L是格,求以下公式的对偶式: (1) a∧(a∨b) a (2) a∨(b∧c)(a∨b)∧(a∨c) (3) b∨(c∧a)(b∨c)∧a 答案：(1) a∨(a∧b) a (2) a∧(b∨c)(a∧b)∨(a∧c) (3) b∧(c∨a)(b∧c)∨a
5.设L是格,a,b,c∈L,且a b c,证明 a∨b=b∧c 答案：a∨b=b b∧c=b 6.针对图13.10中的格L1,L2和L3,求出他们的所有子格。 图13.10 答案： L1的子格：{a},{b},{c},{d},{a,b},{a,c},{a,d}, {b,d},{c,d},{a,b,d},{a,c,d},L1 L2的子格：{a1},{d1},L2 L3的子格：{a2},{b2},{c2},{d2},{a2,b2},{a2,c2}, {a2,d2},{b2,c2},{b2,d2},{c2,d2},{a2,b2,c2}, {a2,b2,d2},{a2,c2,d2},{b2,c2,d2},L3 7.针对图13.9中的每个格,如果格中的元素存在补元,则求出这些补元。 答案：（1）a与d互补；b,c没有补元。 （3）a与f互补；b的补元为c,d；c的补元为b,e；d的补元为b,e；e的补元为c,d. （6）a与f互补；b的补元为e；c和d没有补元；e的补元为b. 8.说明图13.9中的每个格是否为分配格、有补格和布尔格,并说明理由。 答案： （1）是分配格，因为不包含与钻石格和五角格同构的子格；不是有补格和布尔格，b,c没有补元。 （3）不是分配格，不是布尔格，因为包含五角格作为子格；是有补格，a与f互补，b和e的补元有c,d；c,d的补元有b,e. （6）是分配格，因为没有5元子格与钻石格或五角格同构；不是有
离散数学知识点总结 一、各章复习要求与重点 第一章 集 合 [复习知识点] 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集 2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan 律等），文氏（V enn ）图 3、序偶与迪卡尔积 本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 [复习要求] 1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。 2、掌握集合的表示法和集合的交、并、差、补等基本运算。 3、掌握集合运算基本规律，证明集合等式的方法。 4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。 [本章重点习题] P5~6，4、6； P14~15，3、6、7； P20，5、7。 [疑难解析] 1、集合的概念 因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n 。 2、集合恒等式的证明 通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~?=-证明中的特殊作用。 [例题分析] 例1 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则=-)()(B A ρρ 。 解 }}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{{)()(=-B A ρρ