离散数学公式
基本等值式
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 ? (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→C) 假言三段论
(7) (A?B) ∧(B?C) ? (A ? C) 等价三段论
(8) (A→B)∧(C→D)∧(A∨C) ?(B∨D) 构造性二难
(A→B)∧(┐A→B)∧(A∨┐A) ? B 构造性二难(特殊形式)
(9)(A→B)∧(C→D)∧(┐B∨┐D) ?(┐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规则。
A(c)
xA(x)
或
A(y)
xA(x)
∴
?
∴
?
xA(x)
A(y)
?
∴
xA(x)
A(c)
?
∴
EI规则。
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(c)
xA(x)
∴
?
分配律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 ? 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 ? A×B ? C×D
常用的关系
对任意集合A，定义
全域关系 EA={
空关系 ?
小于或等于关系：LA={
整除关系：DB={
关系矩阵和关系图
设 A={1,2,3,4}，R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}， 则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
????
?
????
???=0010000011000011M R
设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也是传递的。 关系性质的特点 自反性反自反性对称性反对称性传递性集合表达式IA ? R R∩IA＝?R＝R-1 R∩R-1 ? IA R?R?R 关系矩阵主对角线元 素全是1 主对角线元素 全是0 矩阵是对称矩 阵 若rij＝1，且i ≠j，则rji＝0 对M2中1所在 位置，M中相 应的位置都是 1 关系图每个顶点都 有环每个顶点都没 有环 如果两个顶点 之间有边，一 定是一对方向 相反的边(无 单边) 如果两点之间 有边，一定是 一条有向边(无 双向边) 如果顶点xi到 xj有边，xj到 xk有边，则从 xi到xk也有边 关系的性质和运算之间的关系 自反性反自反性对称性反对称性传递性R1-1 √√√√√ R1∩R2 √√√√√ R1∪R2 √√√×× R1－R2 ×√√√× R1 ? R2 √×××× 闭包的构造方法 设R为A上的关系，则有 （1）自反闭包r(R)＝R∪R0 （2）对称闭包s(R)＝R∪R-1 （3）t(R)＝R∪R2∪R3∪… 关系性质与闭包运算之间的联系 设R是非空集合A上的关系， （1）若R是自反的，则s(R)与t(R)也是自反的。 （2）若R是对称的，则r(R)与t(R)也是对称的。 （3）若R是传递的，则r(R)是传递的。 等价类的性质 设R是非空集合A上的等价关系，则 （1）?x∈A，[x]是A的非空子集。 （2）?x,y∈A，如果xRy，则[x]＝[y]。 （3）?x,y∈A，如果 （4）∪{[x]|x∈A}＝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 )的。 （3）若f 既是满射又是单射的，则称f :A →B 是双射(bijection ) 单射 双射 函数 满射 例：判断下面函数是否为单射、满射、双射的，为什么? 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 a b c 1 2 3 d 36 3 24 2 12 6 a b c 1 2 3 4 a b c 1 2 3 4 d a b c 1 2 3 4 d (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 设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 离散数学自学笔记命题公式及其真值表 我们把表示具体命题及表示常命题的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/3015123055.html,/整理 例如，┐p→q∨（r∧q∨s）所表示的公式是（（┐p）→（q∨（（r∧q）∨s））） 设A是命题公式，A1是A 的一部分，且A1也是公式，则A1称为公式A的子公式。 、基本等值式 ⑴双重否定律 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分，共12分） 1.在命运题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。（） 2.与是不等值的（） 3.设是非连通平面图G的对偶图，设分别为的顶点数，边数和面数，则它们之间满足欧拉公式：。（） 4.设无向图G具有割点，则G中一定不存在哈密尔顿通路。（） 5.设，A上的恒等关系既是A上的等价关系也是A上的偏序关系。（） 6.设A,B,C,D均为非空的集合，已知A*B且C*D，则一定有。（） 二、填空题（每小题3分，共30分） 1.设p:小王走路,q:小王听音乐,在命题逻辑中，命题“小王边走路边听音乐”的符号化形式为___________________。 2.设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_________________。 3.的成真赋值为________________________。 4.设G是n阶无向带权边通图，各变的权均为a(a>0),设T是G的一棵最小生成树，则T的权W(T)=_______________________。 5.设G1,G2,G3,G4都是4阶3条边的无向简单图，则它们之间至少有 ___________________个是同构的。 6．设G是n（n2）阶二部图，又是平面图，则命题“G的对偶图是欧拉图”的真值为_______________________。 7.设为整数集，，则f的值域ranf=___________。 8.设则A上共有____________个不同的等价关系。 9.设，恒等关系IA的传递闭包t(IA)=_________________。 《离散数学》+答案 一、选择或填空: 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6） 44 第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试 3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章 离散数学公式 ————————————————————————————————作者: ————————————————————————————————日期： ? 基本等值式 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) 破坏性二难 离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q 基本等值式 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)破坏性二难 理学院 《离散数学基础》实验教学大纲 课程名称：离散数学基础实验 课程编号：080J21A 课程总学时：51 实验学时数：17 课程总学分：2.5 实验学分：0.5 开设实验项目数：5 一、实验教学目的 面向离散数学在计算机中的应用，通过实验操作，使学生掌握研究计算机科学的基础理论，进一步提高学生的抽象思维与逻辑推理能力，增强实际应用能力。 二、实验项目内容、基本要求与学时分配 注：1、实验类型：演示、验证、操作、综合、设计、研究。2、实验要求：指必做、选做。 三、实验考核方式与标准 实验考核以学生的实验态度、掌握的实验理论、实际操作技能和实验报告等为主，各单项考核内容所占分数比例为：实验态度占10%、实验理论占15%；操作技能占50%；实验报告占25%。 四、实验教材与参考书 推荐教材：《离散数学》（修订版），耿素云屈婉玲编著，高等教育出版社，2004年。 主要参考书：《离散数学导论》第二版，徐洁磬编著，高等教育出版社，1997年。 《离散数学》， [美]S.利普舒尔茨， M.利普森，周兴和、孙志人、张学斌译, 科学出版社和麦格劳-希尔教育出版集团, 2001年。 《计算方法》实验教学大纲 课程名称：计算方法实验 课程编号：080J22B 课程总学时：85 实验学时数：34 课程总学分：4 实验学分：1 开设实验项目数：5 一、实验教学目的 本课程以MATLAB或C为编程语言，将《计算方法》课程中的常用算法用MATLAB语言描述并上机进行数值实验。通过实验，使学生进一了解各个算法的特点及适用范围，提高学生用计算机解决实际问题的能力。 二、实验项目内容、基本要求与学时分配 三、实验考核方式与标准 实验考核以学生的实验态度、掌握的实验理论、实际操作技能和实验报告等为主，各单项考核内容所占分数比例为：实验态度占10%、实验理论占15%；操作技能占50%；实验报告占25%。 四、实验教材与参考书 1、《计算机数值方法》（第二版），施吉林等，高教出版社出版，2005年 2、《计算方法引论》（第二版），徐翠薇、孙绳武，高等教育出版社，2002 2 命题公式,真值表 (1) 数理逻辑是通过引入表意符号研究人类思维中的推理过程及推理正确与否的数学分支. 数学------??? 符号运算 推理---思维过程:前提 结论 命题逻辑---研究由命题为基本单位构成的前提和结论之间的可推导关系.(逻辑演算) 即将推理(不涉及内函)形式化. 例1 (a) 4是偶数. 张林学习优秀. 太阳系以外的星球上有生物. (b) 这朵花真美丽! 现在开会吗? (c) 3 5.x +> 我正在说慌. 特征分析(a) 陈述句,非真即假. (b) 感叹句,疑问句. (c) 悖论. 定义1 能辩真假的陈述句,称为命题,用,,,P Q Z 表示.其判断结果称为命题的真值. 成真的命题称为真命题,其真值为真,记为,T 或为1.成假的命题称假命题,其真值为假,记为,F 或为0. 例2 (1) 2008年奥运会在北京举行. (2) 22 5.?= (3) 计算机程序的发明者是诗人拜伦. 用符号表是上述命题,并求真值. 解 (1) :P 2008年奥运会在北京举行. .T (2) :Q 22 5.?= .F (3) :R 计算机程序的发明者是诗人拜伦. .F (2) 3, 35,+ 3(4 1).+- 例3 (1) 今天没有数学考试. (2) 下午,我写信或做练习. (3) 王芳不但用功,而且成绩优秀. (4) 如果太阳从西边出来了,那么地球停止转动. (5) 2是素数,当且仅当三角形有三条边. 特征分析(a)存在自然语言中的虚词. (b)语句可以分解,细化. 定义2 称下列符号为逻辑联结词 否定 ? 非 P ? 析取 ∨ 或者 P Q ∨ 合取 ∧ 且 P Q ∧ 蕴涵 → 若----,则----- P Q → 等价 ? 当且仅当 P Q ? 逻辑联结词真值的规定 例4 将下列命题符号化. (1) 小李聪明,但不用功. ()P Q ∧? (2) 单位派小王或小苏出差. P Q ∨ (3) 如果椅子是紫色的,且是园的,那么地是平的. ()P Q R ∧→ (4) n 是偶数当且仅当它能被2整除. P Q ? 注 1 逻辑联结词:运算符.顺序 ,,,,.?∧∨→? 2 自然语言中 虽然---,但是----; 不但---,而且----; ∧ 只有----,才----; 除非----,才-----; → 3 ∨ 可兼或(相容) ∨ 不可兼或(排斥) 小王是山东人或是河北人. ()()P Q P Q P Q ∨?∧?∨?∧ 4 ,P Q -----------------------简单命题 离散数学基本知识 体积和表面积三角形的面积,底×高?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 02任务_000 1 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 设集合A = {1, a }，则P(A) = ( )． A. {{1}, {a}} B. {,{1}, {a}} C. {{1}, {a}, {1, a }} D. {,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={ 5. 设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包． A. 自反 B. 传递 C. 对称 D. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系≤是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）结合能力平等的联结词在没有括号表示其结合状况时，采用左结合约定。 例如，┐p→q∨（r∧q∨s）所表示的公式是（（┐p）→（q∨（（r∧q）∨s））） 设A是命题公式，A1是A 的一部分，且A1也是公式，则A1称为公式A的子公式。 如对公式A：┐p→q∨（r∧q∨s），则p，┐p ，q ，（r∧q∨s）及q∨（r∧q∨s）都是公式A的子公式，而┐q，┐p→q，虽然是公式，但确不是A的一部分，因此不是A 的子公式；q∨（r∧虽然是公式A的一部分，但不是公式，因而也不是A的子公式。 如果公式A含有命题变元p1，p2，…，pn，记为A（p1，…，pn），并把联结词看作真值运算符，那么公式A可以看作是p1，…，pn的真值函数。对任意给定的p1，…，pn 的一种取值状况，称为指派（assignments），用希腊字母a，b等表示，A均有一个确定的真值。当A对取值状况a 为真时，称指派a弄真A，或a是A的成真赋值，记为a （A）= 1；反之称指派a弄假A，或a是A的成假赋值，记为a （A）= 0.对一切可能的指派， 命题：称能判断真假的陈述句为命题。 命题公式：若在复合命题中，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. 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 闭公式是指不含自由变元的谓词公式 怎样学好离散数学 最常和理论计算机科学放在一起的一个词是什么？答：离散数学。这两者的关系是如此密切，以至于它们在不少场合下成为同义词。（这一点在前面的那本书中也有体现）传统上，数学是以分析为中心的。数学系的同学要学习三四个学期的数学分析，然后是复变函数，实变函数，泛函数等等。实变和泛函被很多人认为是现代数学的入门。在物理，化学，工程上应用的，也以分析为主。 随着计算机科学的出现，一些以前不太受到重视的数学分支突然重要起来。人们发现，这些分支处理的数学对象与传统的分析有明显的区别：分析研究的问题解决方案是连续的，因而微分，积分成为基本的运算；而这些分支研究的对象是离散的，因而很少有机会进行此类的计算。人们从而称这些分支为“离散数学”。“离散数学”的名字越来越响亮，最后导致以分析为中心的传统数学分支被相对称为“连续数学”。 《离散数学》作为一个单独的分枝，在世界上出现的时间并不久，不过几十年，但它的各部分内容中有相当一部分却早已出现在数学中。为什么将各个数学分支中的一些内容集中起来加以研究，并且冠上一个新的名称——离散数学呢？这主要是因为计算机科学的产生和发展。正如恩格斯所说：“……科学的状况还更多的从属于技术的状况和需要。倘若社会上有了一种技术上的需要，那就比十个大学还更能推动科学前进。”①计算机的出现，在很大程度上影响到了人们的思想和生活，对社会生产起了重大作用。为了研究计算机科学的理论基础，离散数学也就应运而生。因此，如果我们不从纯数学的角度，而从应用数学的角度来考虑，也许给离散数学换一个名称一一计算机科学的数学基础——更能说明问题。 正是因为这个原因，在计算机科学系。信息管理系都将离散数学作为必须学习的基础课程。而实践证明这种做法是正确的。 离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。 随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。 由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现 离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B ＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________， _____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。 《离散数学》期末复习大纲（完整版）（含例题和考试说明） 一、命题逻辑 [复习知识点] 1、命题与联结词（否定￢、析取∨、合取∧、蕴涵→、等价?），复合命题 2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足），公式的基本等值式 3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式 4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法） 5、命题逻辑的推理理论 本章重点内容：命题与联结词、公式与解释、（主）析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理 [复习要求] 1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。 2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。 3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。 4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。 5、掌握命题逻辑的推理理论。 [疑难解析] 1、公式类型的判定 判定公式的类型，包括判定公式是重言的、矛盾的或是可满足的。具体方法有两种，一是真值表法，二是等值演算法。 2、范式 求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等值式中的分配律、同一律和互补律（排中律、矛盾律），结果的前一步适当使用幂等律，使相同的短语（或子句）只保留一个。 3、逻辑推理 掌握逻辑推理时，要理解并掌握12个（除第10，11）推理规则和3种证明法（直接证明法、附加前提证明法和归谬法）。 例1.试求下列公式的主析取范式：离散数学自学笔记命题公式及其真值表
离散数学基本公式
离散数学基础试题(二)
《离散数学》及答案
离散数学作业答案
离散数学公式
离散数学课后答案
离散数学公式
离散数学基础实验教学大纲Word版
2 离散数学-命题公式,真值表
离散数学基本知识
离散数学答案
离散数学自学笔记命题公式及其真值表
离散数学部分概念和公式总结(考试专用)
完整word版,离散数学知识汇总,推荐文档
怎样又快又好地学好离散数学
离散数学试题及答案(1)
离散数学复习提纲(完整版)
- 离散数学(2-1)实验2015
- 离散数学重要公式定理汇总
- 离散数学命题逻辑练习题
- 离散数学(1.3命题公式与翻译)
- 离散数学部分概念和公式总结(考试专用)
- 离散数学,逻辑学,命题公式求真值表
- 离散数学自学笔记命题公式及其真值表
- 2015离散数学命题及联结词解析
- _离散数学重要公式定理汇总
- 离散数学1命题逻辑
- 命题公式及分类(离散数学)PPT
- 离散数学部分概念和公式总结(精简版)
- 离散数学实验报告命题逻辑—构造命题公式的真值表
- 离散数学命题公式与赋值学习资料
- 离散数学-逻辑学-命题公式求真值表
- 2 离散数学-命题公式,真值表
- 离散数学PPT课件 15命题公式及命题符号(ppt文档)
- 离散数学习题问题详解-2015
- 离散数学命题逻辑练习题
- 2015离散数学命题公式