离散数学公式
基本等值式
1.双重否定律 A ?┐┐A
2.幂等律 A ? A∨A, A ? A∧A
3.交换律A∨B ? B∨A， A∧B ? B∧A
4.结合律(A∨B)∨C ? A∨(B∨C) (A∧B)∧C ? A∧(B∧C)
5.分配律A∨(B∧C) ? (A∨B)∧(A∨C) （∨对∧的分配律）
A∧(B∨C) ? (A∧B)∨(A∧C) （∧对∨的分配律）
6.德·摩根律┐(A∨B) ?┐A∧┐B ┐(A∧B) ?┐A∨┐B
7.吸收律 A∨(A∧B) ? A，A∧(A∨B) ? A
8.零律A∨1 ? 1,A∧0 ? 0
9.同一律A∨0 ? A，A∧1 ? A
10.排中律A∨┐A ? 1
11.矛盾律A∧┐A ? 0
12.蕴涵等值式A→B ?┐A∨B
13.等价等值式A?B ? (A→B)∧(B→A)
14.假言易位A→B ?┐B→┐A
15.等价否定等值式 A?B ?┐A?┐B
16.归谬论(A→B)∧(A→┐B) ?┐A
求给定公式范式的步骤
(1)消去联结词→、?(若存在)。
(2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。
(3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。
推理定律--重言蕴含式
(1) A T (A∨B) 附加律
(2) (A∧B) T A 化简律
(3) (A→B)∧A T B 假言推理
(4) (A→B)∧┐B T┐A 拒取式
(5) (A∨B)∧┐B T A 析取三段论
(6) (A→B) ∧(B→C) T (A→C) 假言三段论
(7) (A?B) ∧(B?C) T (A ? C) 等价三段论
(8) (A→B)∧(C→D)∧(A∨C) T(B∨D) 构造性二难
(A→B)∧(┐A→B)∧(A∨┐A) T B 构造性二难(特殊形式)
(9)(A→B)∧(C→D)∧(┐B∨┐D) T(┐A∨┐C)破坏性二难
设个体域为有限集D={a1,a2,…,an},则有
（1）"xA(x) ? A(a1)∧A(a2)∧…∧A(an)
（2）$xA(x) ? A(a1)∨A(a2)∨…∨A(an)
设A(x)是任意的含自由出现个体变项x的公式，则
（1）┐"xA(x) ? $x┐A(x)
（2）┐$xA(x) ? "x┐A(x)
设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则（1）"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)
（2）$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)
设A(x)，B(x)是任意的含自由出现个体变项x的公式，则
（1）"x(A(x)∧B(x)) ? "xA(x)∧"xB(x)
（2）$x(A(x)∨B(x)) ? $xA(x)∨$xB(x)
全称量词“"”对“∨”无分配律。
存在量词“$”对“∧”无分配律。
UI规则。
UG规则。EG规则。EI规则。
A(c)
xA(x)
或
A(y)
xA(x)
∴
?
∴
?
xA(x)
A(y)
?
∴
xA(x)
A(c)
?
∴
A(c)
xA(x)
∴
?
A∪B＝{x|x∈A∨x∈B } 、
A∩B＝{x|x∈A∧x∈B }
A－B＝{x|x∈A∧x?B }
幂集P(A)＝{x | xíA}
对称差集A?B＝(A－B)∪(B－A)
A?B＝(A∪B)－(A∩B)
绝对补集～A＝{x|x ? A }
广义并∪A＝{x | $z(z∈A∧x∈z)} 广义交∩A＝{x | "z(z∈A→x∈z)}设A＝{{a,b,c},{a,c,d},{a,e,f}} B＝{{a}} C＝{a,{c,d}}
则∪A＝{a,b,c,d,e,f}
∪B＝{a}
∪C＝a∪{c,d}
∪?＝?
∩A＝{a}
∩B＝{a}
∩C＝a∩{c,d}
集合恒等式
幂等律A∪A＝A A∩A＝A
结合律(A∪B)∪C＝A∪(B∪C)(A∩B)∩C＝A∩(B∩C)
交换律A∪B＝B∪A A∩B＝B∩A
分配律A∪(B∩C)＝(A∪B)∩(A∪C) A∩(B∪C)＝(A∩B)∪(A∩C)
同一律A∪?＝A A∩E＝A
零律A∪E＝E A∩?＝?
排中律A∪～A＝E
矛盾律A∩～A＝?
吸收律A∪(A∩B)＝A A∩(A∪B)＝A
德摩根律A－(B∪C)＝(A－B)∩(A－C) A－(B∩C)＝(A－B)∪(A－C)
～(B∪C)＝～B∩～C～(B∩C)＝～B∪～C
～?＝E～E＝?
双重否定律～(～A)＝A
集合运算性质的一些重要结果
A∩BíA，A∩BíB
AíA∪B，BíA∪B
A－BíA
A－B＝A∩～B
A∪B＝B ? AíB ? A∩B＝A ? A－B＝?
A?B＝B?A
(A?B)?C＝A?(B?C)
A??＝A
A?A＝?
A?B＝A?C T B＝C
对偶(dual)式：一个集合表达式，如果只含有∩、∪、～、?、E、＝、í、ê，那么同时把∩与∪互换，把?与E互换，把í与ê互换，得到式子称为原式的对偶式。
有序对
（2）
笛卡儿积的符号化表示为A×B＝{
如果|A|=m,|B|=n,则|A×B|=mn。
笛卡儿积的运算性质
(1)对任意集合A，根据定义有
A×?＝?, ?×A＝?
(2)一般的说，笛卡儿积运算不满足交换律，即
A×B≠B×A (当A≠?∧B≠?∧A≠B 时)
(3)笛卡儿积运算不满足结合律，即
(A×B)×C≠A×(B×C) (当A≠?∧B≠?∧C≠?时)
(4)笛卡儿积运算对并和交运算满足分配律，即
A×(B∪C)=(A×B)∪(A×C) (B∪C)×A=(B×A)∪(C×A)
A×(B∩C)=(A×B)∩(A×C) (B∩C)×A=(B×A)∩(C×A)
(5)AíC ∧BíD T A×B í C×D
常用的关系
对任意集合A，定义
全域关系EA={
恒等关系IA={
空关系?
小于或等于关系：LA={
整除关系：DB={
关系矩阵和关系图
设 A={1,2,3,4}，R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}， 则R 的关系矩阵和关系图分别是
?????
????
???=00
1
000011000011M R
定义域 dom R ＝ {x | $y(
例 求R={<1,2>,<1,3>,<2,4>,<4,3>}的定义域、值域和域。 解答 dom R ＝{1,2,4} ran R ＝{2,3,4} fld R ＝{1,2,3,4}
逆 R-1＝{
右复合 F °G ＝{
限制 R ↑A={
例 设R ＝{<1,2>，<1,3>，<2,2>，<2,4>，<3,2>}
R ↑{1}＝{<1,2>，<1,3>} R ↑? ＝? R ↑{2,3}＝{<2,2>，<2,4>}，<3,2>} R[{1}]＝{2,3} R[?] ＝? R[{3}]＝{2}
设F 是任意的关系，则 (1)(F-1)-1＝F
(2)dom F-1＝ran F ，ran F-1＝dom F
设F ，G ，H 是任意的关系，则 (1)(F °G)°H ＝F °(G °H) (2)(F °G)-1＝G-1 ° F-1
设R 为A 上的关系，则R ° IA ＝IA ° R ＝R
设F ，G ，H 是任意的关系，则 (1) F °(G ∪H)＝F °G ∪F °H (2) (G ∪H)°F ＝G °F ∪H °F (3) F °(G ∩H)íF °G ∩F °H (4) (G ∩H)°F íG °F ∩H °F
设F为关系，A,B为集合，则
(1) F↑(A∪B)＝F↑A∪F↑B
(2) F[A∪B]＝F[A]∪F[B]
(3) F↑(A∩B)＝F↑A∩F↑B
(4) F[A∩B]íF[A]∩F[B]
关系的幂运算
设R为A上的关系，n为自然数，则R的n次幂定义为：（1）R0＝{
（2）Rn+1＝Rn ° R
幂运算的性质
设A为n元集，R是A上的关系，则存在自然数s和t,使得Rs=Rt。设R是A上的关系，m,n∈N，则
(1)Rm ° Rn＝Rm+n (2)(Rm)n＝Rmn
设R是A上的关系，若存在自然数s,t(s (1) 对任何k∈N有Rs+k=Rt+k (2) 对任何k,i∈N有Rs+kp+i=Rs+i，其中p=t-s (3) 令S={R0，R1，…，Rt-1}，则对于任意的q∈N有Rq∈S 自反"x(x∈A→ 反自反"x(x∈A→ 对称"x"y(x,y∈A∧ 反对称"x"y(x,y∈A∧ 传递"x"y"z(x,y,z∈A∧ 关系性质的等价描述 设R为A上的关系，则 （1）R在A上自反当且仅当IA í R （2）R在A上反自反当且仅当R∩IA＝? （3）R在A上对称当且仅当R＝R-1 （4）R在A上反对称当且仅当R∩R-1 í IA （5）R在A上传递当且仅当R°RíR (1)若R1，R2是自反的和对称的，则R1∪R2也是自反的和对称的。 (2)若R1和R2是传递的，则R1∩R2也是传递的。 等价类的性质 设R 是非空集合A 上的等价关系，则 （1）"x ∈A ，[x]是A 的非空子集。 （2）"x,y ∈A ，如果xRy ，则[x]＝[y]。 （3）"x,y ∈A ，如果 偏序集中的特殊元素 （1）若"x(x ∈B →y ≤x)成立，则称y 为B 的最小元。 （2）若"x(x ∈B →x ≤y)成立，则称y 为B 的最大元。 （3）若"x(x ∈B ∧x ≤y →x ＝y)成立，则称y 为B 的极小元。 （4）若"x(x ∈B ∧y ≤x →x ＝y)成立，则称y 为B 的极大元 B 上界 下界 上确界 下确界 {2,3,6,12,24,36} 无 无 无 无 {6,12} 12,24,36 2,3,6 12 6 {2,3,6} 6,12,24,36 无 6 无 {6} 6,12,24,36, 2,3,6, 6 6 函数相等 由定义可知，两个函数F 和G 相等, 一定满足下面两个条件： （1）dom F ＝dom G （2）"x ∈dom F ＝dom G ，都有 F(x )＝G(x ) 所有从A 到B 的函数的集合记作BA ，读作“B 上A ”，符号化表示为 BA ＝{f | f ：A →B} 。 例：设A ＝{1,2,3}，B ＝{a,b}，求BA 。 BA ＝{ f 0, f 1, f 2, f 3, f 4, f 5, f 6, f 7} 。其中 f 0＝{<1,a>,<2,a>,<3,a>} f 1＝{<1,a>,<2,a>,<3,b>} f 2＝{<1,a>,<2,b>,<3,a>} f 3＝{<1,a>,<2,b>,<3,b>} f 4＝{<1,b>,<2,a>,<3,a>} f 5＝{<1,b>,<2,a>,<3,b>} f 6＝{<1,b>,<2,b>,<3,a>} f 7＝{<1,b>,<2,b>,<3,b>} 设f :A →B ，（1）若ran f ＝B ，则称f :A →B 是满射(surjection )的。 （2）若"y ∈ran f 都存在唯一的x ∈A 使得f (x )＝y ，则称 f :A →B 是单射(injection )的。 B 最大元 最小元 极大元 极小元 {2,3,6,12,24,36} 无 无 24，36 2,3 {6,12} 12 6 12 6 {2,3,6} 6 无 6 2,3 {6} 6 6 6 6 36 3 24 2 12 6 （3）若f 既是满射又是单射的，则称f:A→B是双射(bijection) 单射双射函数满射 例：判断下面函数是否为单射、满射、双射的，为什么? (1) f：R→R，f(x)= -x2+2x-1 (2) f：Z+→R，f(x)=ln x，Z+为正整数集 (3) f：R→Z，f(x)=?x? (4) f：R→R，f(x)=2x+1。 解（1）f 在x=1取得极大值0。既不是单射也不是满射的。 （2）f 是单调上升的，是单射的，但不满射。ran f={ln1, ln2, …}。 （3）f 是满射的，但不是单射的，例如f(1.5)=f(1.2)=1。 （4）f 是满射、单射、双射的，因为它是单调函数并且ran f=R。 例：(1) 给定无向图G＝ E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}. (2) 给定有向图D= E＝{ 画出G与D的图形。 邻域：NG(v1) ＝{v2，v5} 后继元集：Г+D(d ) ＝{c} 闭邻域：NG(v1) ＝{v1，v2，v5} 先驱元集：Г-D(d ) ＝{a，c} 关联集：IG(v1) ＝{e1，e2，e3} 邻域：ND(d ) ＝{a，c} 闭邻域：ND(d )＝{a，c，d} d(v1)＝4(注意，环提供2度)，出度：d+(a)＝4，入度：d-(a)＝1 △＝4，δ＝1，(环e1提供出度1，提供入度1)， v4是悬挂顶点，e7是悬挂边。d(a)＝4+1＝5。△＝5，δ＝3， △+＝4 (在a点达到) 度数列为4,4,2,1,3。δ+＝0(在b点达到) △-＝3(在b点达到) δ-＝1(在a和c点达到) 按字母顺序，度数列：5,3,3,3 出度列：4,0,2,1 入度列：1,3,1,2 a b c 1 2 3 d a b c 1 2 3 4 a b c 1 2 3 4 d a b c 1 2 3 4 d 设G＝ （1）G是树。（2）G中任意两个顶点之间存在唯一的路径。 （3）G中无回路且m＝n-1。（4）G是连通的且m＝n-1。 （5）G是连通的且G中任何边均为桥。 （6）G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。例题已知无向树T中，有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树。 解答设有x片树叶，于是结点总数 n＝1+2+x＝3+x 由握手定理和树的性质m＝n-1可知， 2m＝2(n-1)＝2×(2+x) ＝1×3+2×2+x 解出x＝3，故T有3片树叶。 故T的度数应为1、1、1、2、2、3。 求最小生成树的算法（避圈法(Kruskal)） (1)设n阶无向连通带权图G＝ (2)取e1在T中。 (3)依次检查e2,…,em，若ej(j≥2)与已在T中的边不构成回路，取ej也在T中，否则弃去ej。 (4)算法停止时得到的T为G的最小生成树为止。 例：求下图所示两个图中的最小生成树。 W(T1)＝6 W(T2)＝12 T是n(n≥2)阶有向树， (1) T为根树—T中有一个顶点入度为0，其余顶点的入度均为1 (2) 树根——入度为0的顶点 (3) 树叶——入度为1，出度为0的顶点 (4) 内点——入度为1，出度不为0的顶点 (5) 分支点——树根与内点的总称 (6) 顶点v的层数——从树根到v的通路长度 (7) 树高——T中层数最大顶点的层数 根树的画法：树根放上方，省去所有有向边上的箭头。 树叶——8片内点—— 6个分支点—— 7个高度—— 5求带权为1、1、2、3、4、5的最优树。 W(T)=38 中序行遍法：b a (f d g) c e前序行遍法：a b (c (d f g) e) 后序行遍法：b ((f g d) e c) a 离散数学必备知识点总 结 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个不同的关系； 、基本等值式 ⑴双重否定律 A A ⑵籍等律 A A A A A V A A ⑶交换律 A A B BA A A V B BV A ⑷结合律 A V (B V C) (A V B) V C A A (B A C) (A A B) A C ⑸分配律 A V (B A C) (A V B) A (A V C) A A (B V C) (A A B) V (A A C) (6)德摩根律(A V B) AA B (A A B) AV B ⑺吸收律 A (8)零律A ⑼同一律 A (10) 排中律 A (11) 矛盾律 A (12) 蕴含等值式A (13) 等价等值式A V (A A B) V1 1 A1 A V A 1 A A 0 B AV B (A A A A A B B) A (B A) A (A V B) A 0 0 V 0 A A A B (AV B) A (A V B) A B (A A B) V ( AA B ) (14) 假言易位ABBA (15) 等价否定等值式ABA B (16)归谬论(A B) A (A B) A 一、推理定律里口编涵式 1.A ( A B) 附加律 2.( A B) A 化简律 3.( A B) A B 假言推理 4.( A B) B A 拒取式 5.( A B) B A 析取三段论 6.( A B) (B C) (A 假言三段论 7.( A B) (B Q (A C) 等价三段论 8.( A B) (C D) (A C) (B D) 构造性二难 (A B) ( A B) B 构造性二难(特殊形式) 9.( A B) (C D) ( B D) ( A Q 破坏性二难 三、量词辖域收缩与扩张 x(A(x) V B) xA(x) VB x(A(x) A B) xA(x) AB x(A(x) —B) xA(x) F x(B t A(x)) B T xA(x) x(A(x) V B) xA(x) VB x(A(x) A B) xA(x) A B x(A(x) —B) xA(x) F x(B t A(x)) B T xA(x) 四、量词分配 x(A(x) A B(x)) xA(x) A xB(x) x(A(x) V B(x)) xA(x) V xB(x) x(A(x) V B(x)) xA(x) V xB(x) 第二章谓词逻辑 2—1基本概念 例题1. 所有的自然数都是整数。 设N(x):x是自然数。I(x):x是整数。此命题可以写成?x(N(x)→I(x)) 例题2. 有些自然数是偶数。 设E(x):x是偶数。此命题可以写成?x(N(x)∧E(x)) 例题3. 每个人都有一个生母。 设P(x):x是个人。M(x,y):y是x的生母。此命题可以写 成:?x(P(x)→?y(P(y)∧M(x,y))) 2-2 谓词公式及命题符号化 例题1. 如果x是奇数,则2x是偶数。 其中客体x与客体2x之间就有函数关系,可以设客体函数g(x)=2x, 谓词O(x):x是奇数,E(x):x是偶数, 则此命题可以表示为:?x(O(x)→E(g(x))) 例题2 小王的父亲是个医生。 设函数f(x)=x的父亲,谓词D(x):x是个医生,a:小王,此命题可以表示为D(f(a))。 例题3 如果x和y都是奇数,则x+y是偶数。 设h(x,y)=x+y ,此命题可以表示为:?x?y((O(x)∧O(y))→E(h(x,y)) 命题的符号表达式与论域有关系 两个公式:一般地,设论域为{a1,a2,....,an},则有 (1). ?xA(x)?A(a1)∧A(a2)∧......∧A(an) (2). ?xB(x)?B(a1)∨B(a2)∨......∨B(an) 1.每个自然数都是整数。该命题的真值是真的。 表达式?x(N(x)→I(x))在全总个体域的真值是真的, 因?x(N(x)→I(x))?(N(a1)→I(a1))∧(N(a2)→I(a2))∧…∧(N(an)→I(an)) 式中的x不论用自然数客体代入,还是用非自然数客体代入均为真。例如(N(0.1)→I(0.1))也为真。 而?x(N(x)∧I(x))在全总个体域却不是永真式。 离散数学公式 ————————————————————————————————作者: ————————————————————————————————日期： ? 基本等值式 1．双重否定律A?┐┐A ２．幂等律 A ? A∨A,?A ?A∧A 3．交换律?Ａ∨Ｂ?B∨A，?A∧B ?B∧A 4.结合律??（Ａ∨Ｂ)∨Ｃ? A∨（B∨Ｃ) ?(A∧B)∧C ? A∧(Ｂ∧Ｃ) ５.分配律Ａ∨(B∧C）?（Ａ∨B)∧(Ａ∨C）(∨对∧的分配律）??A∧(B∨Ｃ）?(A∧B）∨（A∧Ｃ) (∧对∨的分配律) 6.德·摩根律?┐(A∨B) ?┐A∧┐B ┐（A∧Ｂ）?┐A∨┐B 7.吸收律?Ａ∨(Ａ∧Ｂ) ?A,A∧(A∨B) ?Ａ 8．零律?A∨１?1,A∧0 ?０ ９.同一律?A∨0 ?A，A∧1?Ａ 10．排中律A∨┐A ?１ 11．矛盾律?A∧┐Ａ? 0 12.蕴涵等值式Ａ→B?┐A∨B １3．等价等值式??Ａ?Ｂ?(A→B）∧(Ｂ→Ａ) １4.假言易位A→Ｂ?┐Ｂ→┐A 15.等价否定等值式 A?B ?┐Ａ?┐Ｂ 16.归谬论(A→Ｂ)∧（A→┐B)?┐A 求给定公式范式的步骤 (1)消去联结词→、?(若存在)。 (2）否定号的消去(利用双重否定律)或内移(利用德摩根律)。 (３）利用分配律：利用∧对∨的分配律求析取范式,∨对∧的分配律求合取范式。 推理定律-－重言蕴含式 (１）A ?(A∨B) 附加律 (2) （A∧B）? A ?化简律 （3） (Ａ→B)∧Ａ? B ??假言推理 (４) (Ａ→B)∧┐Ｂ?┐A 拒取式 （5）(A∨B）∧┐B? A ?析取三段论 (6) (A→B) ∧（Ｂ→C)?（A→C) ?假言三段论 (7) (Ａ?B) ∧（B?C) ? (Ａ? C)?等价三段论 （8) (A→B)∧（Ｃ→Ｄ）∧(A∨Ｃ) ?(B∨Ｄ) 构造性二难 (A→B)∧(┐Ａ→B)∧(Ａ∨┐A) ?Ｂ构造性二难（特殊形式) （9)(A→B)∧(Ｃ→Ｄ)∧(┐B∨┐D) ?(┐Ａ∨┐C) 破坏性二难 数理逻辑部分 第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)中 离散数学自学笔记命题公式及其真值表 我们把表示具体命题及表示常命题的p，q，r，s等与f，t统称为命题常元（proposition constant）。深入的讨论还需要引入命题变元（proposition variable）的概念，它们是以“真、假”或“1，0”为取值范围的变元，为简单计，命题变元仍用p，q，r，s等表示。相同符号的不同意义，容易从上下文来区别，在未指出符号所表示的具体命题时，它们常被看作变元。 命题常元、变元及联结词是形式描述命题及其推理的基本语言成分，用它们可以形式地描述更为复杂的命题。下面我们引入高一级的语言成分——命题公式。 定义1.1 以下三条款规定了命题公式（proposition formula）的意义： （1）命题常元和命题变元是命题公式，也称为原子公式或原子。 （2）如果A，B是命题公式，那么（┐A），（A∧B），（A∨B），（A→B），（A？B）也是命题公式。 （3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。 命题公式简称公式，常用大写拉丁字母A，B，C等表示。公式的上述定义方式称为归纳定义，第四章将对此定义方式进行讨论。 例1.8 （┐（p→（q∧r）））是命题公式，但（qp），p→r，p1∨p2∨…均非公式。 为使公式的表示更为简练，我们作如下约定： （1）公式最外层括号一律可省略。 （2）联结词的结合能力强弱依次为┐，（∧，∨），→，？，（∧，∨）表示∧与∨平等。 （3）结合能力平等的联结词在没有括号表示其结合状况时，采用左结合约定。湖南省自考网：https://www.wendangku.net/doc/1a2466843.html,/整理 例如，┐p→q∨（r∧q∨s）所表示的公式是（（┐p）→（q∨（（r∧q）∨s））） 设A是命题公式，A1是A 的一部分，且A1也是公式，则A1称为公式A的子公式。 基本等值式 1.双重否定律 A ?┐┐A 2.幂等律 A ? A∨A, A ? A∧A 3.交换律A∨B ? B∨A， A∧B ? B∧A 4.结合律(A∨B)∨C ? A∨(B∨C) (A∧B)∧C ? A∧(B∧C) 5.分配律A∨(B∧C) ? (A∨B)∧(A∨C) （∨对∧的分配律） A∧(B∨C) ? (A∧B)∨(A∧C) （∧对∨的分配律） 6.德·摩根律┐(A∨B) ?┐A∧┐B ┐(A∧B) ?┐A∨┐B 7.吸收律 A∨(A∧B) ? A，A∧(A∨B) ? A 8.零律A∨1 ? 1,A∧0 ? 0 9.同一律A∨0 ? A，A∧1 ? A 10.排中律A∨┐A ? 1 11.矛盾律A∧┐A ? 0 12.蕴涵等值式A→B ?┐A∨B 13.等价等值式A?B ? (A→B)∧(B→A) 14.假言易位A→B ?┐B→┐A 15.等价否定等值式 A?B ?┐A?┐B 16.归谬论(A→B)∧(A→┐B) ?┐A 求给定公式范式的步骤 (1)消去联结词→、?(若存在)。 (2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。 (3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。 推理定律--重言蕴含式 (1) A T (A∨B) 附加律 (2) (A∧B) T A 化简律 (3) (A→B)∧A T B 假言推理 (4) (A→B)∧┐B T┐A 拒取式 (5) (A∨B)∧┐B T A 析取三段论 (6) (A→B) ∧(B→C) T (A→C) 假言三段论 (7) (A?B) ∧(B?C) T (A ? C) 等价三段论 (8) (A→B)∧(C→D)∧(A∨C) T(B∨D) 构造性二难 (A→B)∧(┐A→B)∧(A∨┐A) T B 构造性二难(特殊形式) (9)(A→B)∧(C→D)∧(┐B∨┐D) T(┐A∨┐C)破坏性二难 离散数学部分概念和公式总结 命题：称能判断真假的陈述句为命题。 命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。 命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。若指定的一组值使A的值为真，则称成真赋值。真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。 命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。 （2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。 （3）若A至少存在一组赋值是成真赋值，则A是可满足式。 主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。 主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。 命题的等值式：设A、B为两命题公式，若等价式A?B是重言式，则称A与B是等值的，记作A<=>B。 约束变元和自由变元：在合式公式?x A和?x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A?B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。 前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。集合的基本运算：并、交、差、相对补和对称差运算。 笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。 二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。特殊关系：（1）、空关系：Φ（2）全域关系：EA={ 离散数学的基础知识点总结 第一章命题逻辑 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.全称量词用蕴含T,存在量词用合取“； 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0; 2.基：集合A中不同元素的个数，|A|; 3.幕集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幕集P(A)有2°个元素，|P(A)|= 2|A|= 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔AXB的基数为mn , A到B上可以定义2mn种不同的关系； 2.若集合A有n个元素，则|A X\|= n2, A上有2n个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全圭寸闭环的性质：自反性，对称性，反对称性，传递性； 4.前域（domR）:所有元素x组成的集合； 总结离散数学知识点 第二章命题逻辑 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个不同的关系； 第2章谓词逻辑 一、教学要求 1. 理解谓词、量词、个体词、个体域、原子公式、谓词公式和变元等概念。会将不太复杂的命题符号化。 2. 掌握在有限个体域下求公式的真值和某些公式在给定解释下真值的方法，判别公式类型(永真式、永假式和可满足式)的方法。 3. 掌握谓词演算的等值式和重言蕴含式(六种情况：(1)命题公式的推广；(2)量词否定式的等值式；(3)量词辖域扩张和收缩的等值式；(4)量词与联结词∨，∧，→的等值式；(5)量词与联结词的重言蕴含式；(6)两个量词公式间的等值式与重言蕴含式)。会进行谓词公式的等值演算。 4. 了解前束范式的概念，会求公式的前束范式。 5. 了解谓词逻辑推理的规则：全量词消去规则(US规则)；全量词附加规则(UG规则)；存在量词消去规则(ES规则)；存在量词附加规则(EG规则) 本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明。 二、学习辅导 在命题逻辑中，我们把原子命题作为基本研究单位，对原子命题不再进行分解，只有复合命题才可以分解，揭示了一些有效的推理过程. 但是进一步研究发现，仅有命题逻辑是无法把一些常见的推理形式包括进去. 例如 “凡人要死，张三是人，张三要死” 显然是正确推理. 用命题逻辑解释三段式. 设 P：人要死；Q张三是人；R：张三要死。 表示成复合命题有 P∧Q→R 这不是重言式，即R不是前提P，Q的有效结论. 这反映了命题逻辑的局限性，其原因是把本来有内在联系的命题P，Q，R，视为独立的命题。要反映这种内在联系，就要对命题逻辑进行分析，分析出其中的个体词、谓词和量词，再研究它们之间的逻辑关系，总结出正确的推理形式和规则，这就是谓词逻辑的研究内容。 1. 谓词与量词 学习这一部分要反复理解谓词和量词引入的意义，概念的含义。 在谓词逻辑中，原子命题分解成个体词和谓词。个体词是可以独立存在的客体，它可以是具体事物或抽象的概念，如小张，房子，南京，大米，思想，实数2等等。谓词是用来刻划个体词的性质或事物之间的关系的词。例如 (1)(1)ln5是无理数； (2)(2)高可比李木相高4cm； (3) 郑州位于北京和广州之间。 这时三个简单命题，其中ln5，高可，李木相，郑州，北京，广州等都是个体词，而“是无理数”，“……比……高4cm”，“……位于……和……之间”等都是谓词。 个体词分个体常项(用a,b,c,d,…表示)和个体变项(用x,y,z,…表示)；谓词分谓词常项(表 离散数学总结 班级：学号：姓名： 临近期末各科课程已经结束，随之而来就是总结各科学习总结和对这门学科的建议。《离散数学》这门课程当然也不会例外了。经过一个学期的学习我发现《离散数学》是一门理论性非常强的课程，而且知识点非常多，定义和定理以及定律是数之不尽。 《离散数学》顾名思义就是一门数学，它是数学众多领域中的一个小分支，即使是一个小小的分支，但是它的内容也非常之多，同时也非常抽象。自认我的数学成绩还是不错的，但是面对《离散数学》我就头痛，书本里面很多知识点我都是似懂非懂地。但鉴于《离散数学》在计算科学中的重要性，这是一门必须牢牢掌握的课程。因此我也很无奈，只好硬着头皮去学好它了。 离散数学是理论性较强的学科，学习离散数学的关键是对离散数学(集合论、数理逻辑和图论)有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。 《离散数学》的特点是： 1、知识点集中，概念和定理多。《离散数学》是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心。不管哪本离散数学教材，都会在每一章节列出若干定义和定理，接着就是这些定义定理的直接应用。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意概念之间的联系，而描述这些联系的则是定理和性质。 2、方法性强：离散数学的特点是抽象思维能力的要求较高。通过对它的学习，能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。《离散数学》的证明题多，不同的题型会需要不同的证明方法（如直接证明法、反证法、归纳法等），同一个题也可能有几种方法。但是《离散数学》证明题的方法性是很强的，如果知道一道题用什么方法讲明，则很容易可以证出来，否则就会事倍功半。因此在平时的学习中，要勤于思考，对于同一个问题，尽可能多探讨几种证明方法，从而学会熟练运用这些证明方法，再者要善于总结。 在学习《离散数学》的过程中，我明白了理解概念是至关重要的。只有概念明确，才有可能将离散数学学好。但是初学者往往不能够将概念与现实世界中的事物联系起来，这是学好离散数学的基础，因此也是初学者面临的一个困难。只有克服它，你才能有可能学好《离散数学》。 学完这门课后，我总结到了，如果你想学得更好——你可以在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记。只有这样才可能本课程的抽象能够适应，并为后续学习打下良好的基础。而且必须及时复习和总结。 《离散数学》是一门数学科，大家都知道学数学就是要大量做数学，因此《离散数学》也不会例外。学习数学不仅限于学习数学知识，更重要的还在于学习数学的思维方法。这一点非常重要。 课程虽然是上完了，但是老师你的教学方法独特而新颖，思想开化而先进，是个容易沟通的老师。有你带着我们学习《离散数学》就是我们不想学好，我想也是很难吧！就我来说每次上课时在我快要与“周公”会面之际，你突然一个笑话和雷人的语录，我和“周公”迫不得已就分开了。当我再次看到周公时，耳边 离散数学笔记 第一章命题逻辑 合取 析取 定义 1. 1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义 1. 1.4条件联结词，表示“如果……那么……”形式的语句 定义 1. 1.5双条件联结词，表示“当且仅当”形式的语句 定义 1.2.1合式公式 (1)单个命题变元、命题常元为合式公式，称为原子公式。 (2)若某个字符串A 是合式公式，则?A、(A)也是合式公式。 (3)若A、B 是合式公式，则A ∧B、A∨B、A→B、A?B 是合式公式。 (4)有限次使用(2)~(3)形成的字符串均为合式公式。 1.3等值式 1.4析取范式与合取范式 将一个普通公式转换为范式的基本步骤 1.6推理 定义 1.6.1 设 A 与 C 是两个命题公式， 若 A → C 为永真式、 重言式，则称 C 是 A 的有 效结论，或称 A 可以逻辑推出 C ，记为 A => C 。（用等值演算或真值表） 第二章 谓词逻辑 2.1、基本概念 ?：全称量词 ?：存在量词 一般情况下， 如果个体变元的取值范围不做任何限制即为全总个体域时， 带 “全称量词”的谓词公式形如"?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)) 2.2、谓词公式及其解释 定义 2.2.1、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22 y x 的 f(x,y))、 谓词常元(如表示人 类的 H(x))。 定义 2.2.2、逻辑符号：个体变元、量词(??)、联结词(﹁∨∧→?)、逗号、括号。 定义 2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。 定义 2.2.4、原子公式：设 R(n x x ... 1)是 n 元谓词，n t t ...1是项，则 R(t)是原子公式。原子公式中的个体变元，可以换成个体变元的表达式(项)，但不能出现任何联结词与量词，只能为单个的谓词公式。 定义 2.2.5 合式公式：(1)原子公式是合式公式；(2)若 A 是合式公式，则(﹁A)也是合式公式；(3)若 A,B 合式，则 A ∨B, A ∧B, A →B , A ?B 合式(4)若 A 合式，则?xA 、?xA 合式(5)有限次使用(2)~(4)得到的式子是合式。 定义 2.2.6 量词辖域：?xA 和?xA 中的量词?x/?x 的作用范围，A 就是作用范围。 定义 2.2.7 约束变元：在?x 和?x 的辖域 A 中出现的个体变元 x ，称为约束变元，这是与量词相关的变元，约束变元的所有出现都称为约束出现。 定义 2.2.8 自由变元：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一个公式的个体变元不是约束变元，就是自由变元。 注意：为了避免约束变元和自由变元同名出现，一般要对“约束变元”改名，而不对自由变元改名。 定义 2.2.9 闭公式是指不含自由变元的谓词公式 方法、知识点总结（知识重点和考题重点） 前三章重点内容（知识重点）： 1、蕴含（条件）“→”的真值 P→Q的真值为假，当且仅当P为真，Q为假。 2、重言(永真)蕴涵式证明方法 <1>假设前件为真，推出后件也为真。 <2>假设后件为假，推出前件也为假。 易错 3、等价公式和证明中运用 4、重要公式 重言蕴涵式：P∧Q => P or Q P or Q => p∨Q A->B =>(A∧or∨C)->(B∧or∨C) 其他是在此基础上演变 等价公式：幂等律 P∧P=P P∨P=P 吸收律 P∧(P∨Q)=P P∨(P∧Q)=P 同一律 P∨F=P P∧T=P P∨T=T P∧F=F P <-> Q = (P->Q)∧(Q->P) = (P∧Q)∨(﹁P∧﹁Q) 5、范式的写法（最方便就是真值表法） 6、派遣人员、课表安排类算法： 第一步：列出所有条件，写成符号公式 第二步：用合取∧连接 第三步：求上一步中的析取范式即可 7、逻辑推理的写法 直接推理论证：其中I公式是指重言蕴涵式那部分 其中E公式是指等价公式部分 条件论证: 形如 ~ , ~, ~ => R->S R P(附加条件) ... ... S T R->S CP 8、谓词基本内容 注意：任意用—> 连接 存在用∧连接 量词的否定公式 量词的辖域扩充公式 量词分配公式 其他公式 9、带量词的公式在论域内的展开 10、量词辖域的扩充公式 11、前束范式的写法 给定一个带有量词的谓词公式， 1)消去公式中的联接词→和←→(为了便于量词辖域的扩充)； 2)如果量词前有“﹁?”，则用量词否定公式﹁?”后移。再用摩根定律或求公式的否定公式，将“﹁?”后移到原子谓词公式之前； 3)用约束变元的改名规则或自由变元的代入规则对变元换名(为量词辖域扩充作准备)； 图论部分 第七章、图的基本概念 7.1 无向图及有向图 无向图与有向图 多重集合: 元素可以重复出现的集合 无序积: A&B={(x,y) | x∈A∧y∈B} 定义无向图G= 通常用G表示无向图, D表示有向图, 也常用G泛指 无向图和有向图, 用e k表示无向边或有向边. V(G), E(G), V(D), E(D): G和D的顶点集, 边集. n 阶图: n个顶点的图 有限图: V, E都是有穷集合的图 零图: E=? 平凡图: 1 阶零图 空图: V=? 顶点和边的关联与相邻：定义设e k=(v i,v j)是无向图G= 离散数学（课件上习题） 第一章 例1-1.1 判定下面这些句子哪些是命题。 ⑴2是个素数。 ⑵雪是黑色的。 ⑶2013年人类将到达火星。 ⑷如果a>b且b>c，则a>c 。（其中a,b,c都是 确定的实数） ⑸x+y<5 ⑹请打开书！ ⑺您去吗？ ⑴⑵⑶⑷是命题 例1-2.1 P：2是素数。 ?P：2不是素数。 例1-2.2 P：小王能唱歌。 Q：小王能跳舞。 P∧Q：小王能歌善舞。 例1-2.3. 灯泡或者线路有故障。（析取“∨”） 例1-2.4. 第一节课上数学或者上英语。（异或、排斥或。即“?”） 注意：P ?Q 与(P∧?Q)∨(Q∧?P ) 是一样的。 归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：（1）否定“?”(2) 合取“∧”(3) 析取“∨”(4) 异或“?”(5) 蕴涵“→”(6) 等价“?” 例1-2.5：P表示：缺少水分。 Q表示：植物会死亡。 P→Q：如果缺少水分，植物就会死亡。 P→Q：也称之为蕴涵式，读成“P蕴涵Q”，“如果P则Q”。 也说成P是P→Q 的前件，Q是P→Q的后件。 还可以说P是Q的充分条件，Q是P的必要条件。 以下是关于蕴含式的一个例子 P：天气好。Q：我去公园。 1.如果天气好，我就去公园。 2.只要天气好，我就去公园。 3.天气好，我就去公园。 4.仅当天气好，我才去公园。 5.只有天气好，我才去公园。 6.我去公园，仅当天气好。 命题1.、2.、3.写成：P→Q 命题4.、5.、6.写成：Q→P 例1-2.6：P：△ABC 是等边三角形。Q ：△ABC是等角三角形。 P?Q ：△ABC 是等边三角形当且仅当它是等角三角形。 命题：称能判断真假的陈述句为命题。 命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。 命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。若指定的一组值使A的值为真，则称成真赋值。真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。 命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。 （2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。 （3）若A至少存在一组赋值是成真赋值，则A是可满足式。 主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。 主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。 命题的等值式：设A、B为两命题公式，若等价式A?B是重言式，则称A与B是等值的，记作A<=>B。 约束变元和自由变元：在合式公式?x A和?x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A?B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。 前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。集合的基本运算：并、交、差、相对补和对称差运算。 笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。 二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。特殊关系：（1）、空关系：Φ（2）全域关系：EA={ 离散数学基本知识 体积和表面积三角形的面积,底×高?2。公式S= a×h?2 正方形的面积,边长×边长公式 S= a2 长方形的面积,长×宽公式S= a×b 平行四边形的面积,底×高公式S= a×h 梯形的面积,(上底+下底)×高?2 公式 S=(a+b)h?2 内角和:三角形的内角 和,180度。 长方体的表面积,(长×宽，长×高，宽×高) ×2 公 式:S=(a×b+a×c+b×c)×2 正方体的表面积,棱长×棱长×6 公式: S=6a2 长方体的体积,长×宽×高公式:V = abh 长方体(或正方体)的体积,底面积×高公式:V = abh 正方体的体积,棱长×棱长×棱长公式:V = a3 圆的周长,直径×π公式:L,πd,2πr 1 圆的面积,半径×半径×π公式:S,πr2 圆柱的表(侧)面积:圆柱的表(侧)面积等于底面的周长乘高。公 式:S=ch=πdh,2πrh 圆柱的表面积:圆柱的表面积等于底面的周长乘高再加上两头的圆的面积。公式:S=ch+2s=ch+2πr2 圆柱的体积:圆柱的体积等于底面积乘高。公式:V=Sh 圆锥的体积,1/3底面×积高。公式:V=1/3Sh 算术 1、加法交换律:两数相加交换加数的位置，和不变。 2、加法结合律:a + b = b + a 3、乘法交换律:a × b = b × a 4、乘法结合律:a × b × c = a ×(b × c) 5、乘法分配律:a × b + a × c = a × b + c 6、除法的性质:a ? b ? c = a ?(b × c) 7、7、除法的性质:在除法里，被除数和除数同时扩大(或缩小)相同的倍数，商不变。 O除以任何不是O的数都得O。简便乘法:被乘数、乘数末尾有O的乘法，可以先把O前面的相乘，零不参加运算，有几个零都落下，添在积的末尾。 8、 8、有余数的除法: 被除数,商×除数+余数方程、代数与等式 2 9、等式:等号左边的数值与等号右边的数值相等的式子叫做等式。等式的基本性质:等式两边同时乘以(或除以)一个相同的数，等式仍然成立。 10、方程式:含有未知数的等式叫方程式。一元一次方程式:含有一个未知数，并且未知数的次数是一次的等式叫做一元一次方程式。学会一元一次方程式的例法及计算。即例出代有χ的算式并计算。 11、代数: 代数就是用字母代替数。代数式:用字母表示的式子叫做代数式。如:3x =ab+c 分数:把单位“1”平均分成若干份，表示这样的一份或几分的数,叫做分数。 分数大小的比较:同分母的分数相比较，分子大的大，分子小的小。异分母的分数相比较，先通分然后再比较;若分子相同，分母大的反而小。 分数的加减法则:同分母的分数相加减，只把分子相加减，分母不变。异分母的分数相加减， 先通分，然后再加减。 分数乘整数，用分数的分子和整数相乘的积作分子，分母不变。 分数乘分数，用分子相乘的积作分子，分母相乘的积作为分母。 3离散数学必备知识点总结
离散数学基本公式
离散数学谓词逻辑课后总结
离散数学公式
离散数学第二章一阶逻辑知识点总结
离散数学自学笔记命题公式及其真值表
离散数学公式
离散数学部分概念和公式总结
离散数学的基础知识点总结
离散数学知识点总结
《计算机数学基础(2)—离散数学》 谓词逻辑
离散数学总结
完整word版,离散数学知识汇总,推荐文档
东北大学离散数学复习总结
离散数学第七章图的基本概念知识点总结docx
离散数学(命题逻辑)课后总结
离散数学部分概念和公式总结(考试专用)
离散数学基本知识