哥伦比亚大学-离散数学-笔记-第9-12章-3

第9章习题解答9. 1有5片树叶.分析设T有x个1度顶点(即树叶)•则T的顶点数n = 3 + 2 + x = 5 + x,T的边数m = n- \ =4 + x.由握手定理得方程.2m = 2(4 + x) = y^J(v f) = 3x3 + 2x2 + l- x = 13 + x./=1由方程解出*5.所求无向树T的度数列为1, 1, 1, 1, 1, 2, 2, 3, 3, 3.由这个度数列可以画多棵非同构的无向树，图9. 6给出的4棵都具有上述度数列，且它们是非同构的.9.2 T中有5个3度顶点.分析设T中有x个3度顶点，则T中的顶点数n = l + x,边数加= "-l = 6 + x,由握手定理得力程.2m = 12 + 2x =》d（片）=3x + 7/=!rtl方程解出x=5.所求无向树T的度数列为1, 1, 1, 1, 1, 2, 2, 3, 3, 3.由这个度数列可以画多棵非同构的无向树，图9.6给出的4棵都具有上述度数列，且它们是非同构的.9.2 T中有5个3度顶点.要析设T中有x个3度顶点，则T中的顶点数"7 +小边数加1=6 + .由握手定理得方程.由此解出"5,即T中有5个3度顶.T的度数列为1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3, 3.由于T中只有树叶和3度顶点, 因而3度顶点可依次相邻，见图9. 7所示.还有棵与它非同构的树，请读者自己i田i出.9. 3力肛-1条新边才能使所得图为无向树.分析设具有£个连通分支的森林为G,则G有k个连通分支人込，…八/全为树，心1,2,…&加新边不能在7；内部加，否则必产生回路.因而必须在不同的小树之间加新边.每加一条新边后，所得到的森林就减少一个连通分支.恰好加-1条新边，就使得图连通且无回路，因而是树•在加边过程屮，只需注意，不在同一人连通分支中加边.下面给出一种加边方法,取v,为7；中顶点，加新边(v,,v,+l)z = l,2,---J-l,则所得图为树, 见图9. 8给出的一个特例.图中虚线边为新加的边.9. 4不一定.分析n阶无向树T具有“-I条边，这是无向树T的必要条件，但不是充公条件•例如，阶圈(即“-1个顶点的初级回路) 和一个孤立点组成无向简单图具有”-1条边，但它显然不是树.图9.89. 5非同构的无向树共有2棵，如图9. 9所示.困9.9分析由度数列1, 1, 1, 1,2,2, 4不难看出，唯一的4度顶点必须与2度顶点相邻，它与1个2度顶点相邻，还是与两个2度顶点都相邻，所得树是非同构的，再没有其他情况. 因而是两棵非同构的树. o 、O O9.6有两棵非同构的生I ，——V(1) (2)成树，见图9. 10所示. 图9.10分析图9. 10是5阶图(5个顶点的图)，5阶非同构的无向树只有3棵，理由如下.5 阶无向树中，顶点数"=5,边数加=4,各顶点度数Z和为&度数分配方案有3种,分别为①1, 1, 1, 1,4;②1, 1, 1,2,3;③1, 1,2, 2. 2.每种方案只有一棵非同构的树•图9.10所示的5阶图的非同构的生成树的度数列不能超出以上3种，也就是说，它至多有3棵非同构的生成树，但由于图中无4度顶点，所示，不可能有度数列为①的生成树，于是该图最多有两棵非同构的生成树.但在图9. 10中已经找出了两个非同构的生成树, 其中(1)的度数列为③，(2)的度数列为②，因而该图准确地有两棵非同构的牛成树.9. 7 基本回路为：C c = cbad,C e = ead,C g = gfa,C h =hfab.基本回路系统为{C c,C e,C g,C h}.基本回路系统为{S a,S h,S d,S f}.分析1°注意基本回路用边的序列表示，而基本割集用边的集合表示.2°基本回路中，只含一条弦，其余的边全为树枝，其求法是这样的：设弦e = (fj),则％,Vj在生成树T中，且在T中, 之间存在唯一的路径「订与e = (v,,v y)组成的回路为G中对应弦e的基本回路.3°基本割集中，只含一条树枝，其余的边都是弦，其求法是这样的:设树枝e = (i;,Vj),则e为T中桥,于是T-e (将e从T 中支掉)，产生两棵小树7；和0，则={e \e在G中且e的两端点分别在7；和3中} S。

离散数学笔记（特级教师精心整理）第一章命题逻辑内容：命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法证明等方法教学目的：1．熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。

2．熟练掌握常用的基本等价式及其应用。

3．熟练掌握（主）析/合取范式的求法及其应用。

4．熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。

5．熟练掌握形式演绎的方法。

教学重点：1．命题的概念及判断2．联结词，命题的翻译3．主析（合）取范式的求法4．逻辑推理教学难点：1．主析（合）取范式的求法2．逻辑推理1.1命题及其表示法1.1.1 命题的概念数理逻辑将能够判断真假的陈述句称作命题。

1.1.2 命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。

A1:我是一名大学生.[10]：我是一名大学生。

R：我是一名大学生。

1.2命题联结词（1） P↑P⇔﹁（P∧P）⇔﹁P；（2）（P↑Q）↑（P↑Q）⇔﹁（P↑Q）⇔ P∧Q；（3）（P↑P）↑（Q↑Q）⇔﹁P↑﹁Q⇔ P∨Q。

（1）P↓P⇔﹁（P∨Q）⇔﹁P；（2）（P↓Q）↓（P↓Q）⇔﹁（P↓Q）⇔P∨Q；（3）（P↓P）↓（Q↓Q）⇔﹁P↓﹁Q⇔﹁（﹁P∨﹁Q）⇔P∧Q。

1.3 命题公式、翻译与解释1.3.1 命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P 是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、 P↔Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。

例如，下面的符号串都是公式：（（（（﹁P）∧Q）→R）∨S）（（P→﹁Q）↔（﹁R∧S））（﹁P∨Q）∧R以下符号串都不是公式：（（P∨Q）↔（∧Q））（∧Q）1.3.2 命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。

习题91. 设G 是一个(n ，m)简单图。

证明：，等号成立当且仅当G 是完全图。

证明：（1）先证结论：因为G 是简单图，所以G 的结点度上限 max(d(v)) ≤ n-1, G 图的总点度上限为 max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。

根据握手定理，G 图边的上限为 max(m) ≤ n(n-1)/2,所以。

（2） =〉G 是完全图 因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。

所以，G 的每个结点的点度都为n-1，G 为完全图。

G 是完全图 =〉 因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数 。

■2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。

证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。

与题设m = n+1，矛盾。

因此，G 中存在顶点u ，d （u ）≥3。

■3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5）解：除序列（1）不是图序列外，其余的都是图序列。

因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。

可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。

最后，将奇数序列对应的点两两一组，添加连线即可。

下面以（2）为例说明：(6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5}每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)将奇数3，3 对应的结点v 2,v 3一组，画一条连线其他序列可以类式作图，当然大家也可以画图其它不同的图形。

注意/技巧：析取符号为V，大写字母Vx + y = 3不是命题前件为假时，命题恒为真运用吸收律命题符号化过程中要注意命题间的逻辑关系，认真分析命题联结词所对应的自然语言中的联结词，不能只凭字面翻译。

也就是说，在不改变原意的基础上，按照最简单的方式翻译通用的方法：真值表法VxP（x）蕴含存在xP（x）利用维恩图解题证明两个集合相等：证明这两个集合互为子集常用的证明方法：任取待证集合中的元素<,>构造相应的图论模型第一章命题逻辑命题和联结词命题的条件：表达判断的陈述句、具有确定的真假值。

选择题中的送分题原子命题也叫简单命题，与复合命题相对简单联结词的真值表要记住非（简单）合取（当且仅当P，Q都为真时，命题为真）析取（当且仅当P，Q都为假时，命题为假），P，Q可以同时成立，是可兼的或条件（→）（当且仅当P为真，Q为假时，命题为假）P是前件，Q是后件只要P，就Q等价于P→Q只有P，才Q等价于非P→非Q，也就是Q→PP→Q特殊的表达形式：P仅当Q、Q每当P双条件（↔）（当且仅当P与Q具有相同的真假值时，命题为真，与异或相反）命题公式优先级由高到低：非、合取和析取、条件和双条件括号省略条件：①不改变先后次序的括号可省去②最外层的括号可省去重言式（永真式）、矛盾式（永假式）、偶然式可满足式：包括重言式和偶然式逻辑等价和蕴含（逻辑）等价:这是两个命题公式之间的关系，写作“⇔”，要与作为联结词的↔区分开来。

如果命题公式A为重言式，那么A⇔T常见的命题等价公式：需要背过被标出的，尽量去理解。

关键是掌握公式是将哪个符号转换为了哪个符号，这对于解证明题有很大的帮助！验证两个命题公式是否等价：当命题变元较少时，用真值表法。

当命题变元较多时，用等价变换的方法，如代入规则、替换规则和传递规则定理：设A、B是命题公式，当且仅当A↔B是一个重言式时，有A和B逻辑等价。

蕴含:若A→B是一个重言式，就称作A蕴含B，记作A⇒B常见的蕴含公式的运用方法同上面的命题等价公式证明A⇒B：①肯定前件，推出后件为真②否定后件，推出前件为假当且仅当A⇒B且B⇒A时，A⇔B，也就是说，要证明两个命题公式等价，可以证明它们相互蕴含联结词的完备集新的联结词：条件否定、异或（不可兼或）、或非（析取的否定）、与非（合取的否定）任意命题公式都可由仅含{非，析取}或{非，合取}的命题公式来等价地表示全功能联结词集合极小全功能联结词集合对偶式对偶式：将仅含有联结词非、析取、合取（若不满足，需先做转换）的命题公式A中的析取变合取，合取变析取，T变F，F变T得到的命题公式A*称为A的对偶式范式析取式：否定+析取合取式：否定+合取析取范式：（合取式）析取（合取式）……析取（合取式）。

离散数学章节总结离散数学章节总结第⼀章[命题逻辑]1.逻辑运算1.否定:Negation? NOT2.交:Conjunction AND3.并:Disjunction OR4.蕴含:Implication IMPLIES5. Biconditional ? IFFXOR2.逆/否/逆否1.逆:converse2.否:inverse3.逆否:conytrapositive3.问题的⼀致性[逻辑等价]→q 等价于?p q 等价于? q→?p2. p q 等价于?p→qp q 等价于?( p→?q)3.(p→q)(p→r) 等价于p→(q r)(p→r)(q→r) 等价于(p q)→r(p→r)(q→r)等价于(p q) →r4.证明等价: 真值表逻辑符号证明找反例(假设左为假右必为假假设右为假左必为假)[ 谓词逻辑]1.量词存在任意量词顺序不能随机改变不全为真:(p1p2…p n) (p1p2…p n) x P(x ) x P(x )没有⼀个为真:(p1p2…p n) (p1p2…p n) x P(x ) x P(x ) [ 推理][ 证明]1.证明⽅法:直接证明间接证明反证列举证明(列举所有情况) 构造证明(构造出满⾜结论的元素)2.证明步骤:正向证明反向证明第⼆章[ 集合及运算]1.特殊集合: R Q Z ⽆穷/有限集2.集合表述⽅法: 列举法描述法图表法3.集合运算: 交/并/补/差/取⼦集P(S)/元素数|S|/乘积P ×Q /BA B A B A B A ?=??=? n i iA 1= X A A ∈ ni iA 1= XA A∈容斥原理A i i =1n=Ai1≤i ≤n ∑-A iAj1≤inA ii =1n4.证明集合相等:1.证明互为⼦集 2.从属表 3.逻辑证明[ 函数]1.函数的定义2.术语：定义域，值域，象，原象，范围， (a)/f(A)第五章[序、归纳]1.序：在某种关系下存在最⼩元素则为well-ordered2.第⼀数学归纳法：basic step P(C)成⽴and inductive step P(k)→P(k+1)3.第⼆数学归纳法:basic step:P(c)成⽴ and inductive step: 任意k⼩于等于nP(k) 成⽴→P(n+1) [递归]1.递归：以相同形式⽤⼩的项来定义的⼤的项不能⼀直递归下去（存在初始项）必须存在可以直接解决问题的⼀项①basic step:原有元素② recursive step:原有元素如何产⽣新元素2.字符串的定义：空字符，回⽂3.结构归纳：⽤于证明递归结构对所有元素都成⽴：①basic step:原有元素成⽴②recursive step:⽤递归式导出的新元素成⽴[递归算法]1.定义：把问题转化为相同形式但值更⼩的算法2.递归算法有初始步骤（是可终⽌的）并且递归时⾄少改变⼀个参数值使之向初始步骤靠拢3.递归时间复杂度⾼，可以⽤⾮递归（loop或 stack）来代替[程序的正确性]1.测试与证明：证明更有说服⼒2.证明：①程序会终⽌②（部分正确）程序只要可以终⽌得出的结论都是正确的正确的程序：对任意可能的输⼊都有正确的输出部分正确，完全正确triple：P{S}QP: precondition S: assertion Q:postconditionP{S}Q:当PQ正确时为部分正确当证明了S的可终⽌性为完全正确4.程序的基本语句：赋值，命题，条件，循环5.弱化结论：P{S}R R→Q：P{S}Q强化条件Q→R R{S}P：Q{S}P复合：P{S1}R R{S2}Q: P{S1;S2}Q第六章[加法乘法原理]1.加法乘法原理：⽅法不重复，互不影响，做1or2 m+n 做1and2 mn2.容斥原理：⽅法有重叠：|A B |=|A ||B ||A B |3.包含条件的问题。

离散数学笔记总结一、命题逻辑。

1. 基本概念。

- 命题：能够判断真假的陈述句。

例如“2 + 3 = 5”是真命题，“1 > 2”是假命题。

- 命题变元：用字母表示命题，如p,q,r等。

2. 逻辑联结词。

- 否定¬：¬ p表示对命题p的否定，若p为真，则¬ p为假，反之亦然。

- 合取wedge：pwedge q表示p并且q，只有当p和q都为真时，pwedge q才为真。

- 析取vee：pvee q表示p或者q，当p和q至少有一个为真时，pvee q为真。

- 蕴含to：pto q表示若p则q，只有当p为真且q为假时，pto q为假。

- 等价↔：p↔ q表示p当且仅当q，当p和q同真同假时，p↔ q为真。

3. 命题公式。

- 定义：由命题变元、逻辑联结词和括号按照一定规则组成的符号串。

- 赋值：给命题变元赋予真假值，从而确定命题公式的真值。

- 分类：重言式（永真式）、矛盾式（永假式）、可满足式。

4. 逻辑等价与范式。

- 逻辑等价：若A↔ B是重言式，则称A与B逻辑等价，记作A≡ B。

例如¬(pwedge q)≡¬ pvee¬ q（德摩根律）。

- 范式：- 析取范式：由有限个简单合取式的析取组成的命题公式。

- 合取范式：由有限个简单析取式的合取组成的命题公式。

- 主析取范式：每个简单合取式都是极小项（包含所有命题变元的合取式，每个变元只出现一次）的析取范式。

- 主合取范式：每个简单析取式都是极大项（包含所有命题变元的析取式，每个变元只出现一次）的合取范式。

二、谓词逻辑。

1. 基本概念。

- 个体：可以独立存在的事物，如人、数等。

- 谓词：用来刻画个体性质或个体之间关系的词。

例如P(x)表示x具有性质P，R(x,y)表示x和y具有关系R。

- 量词：- 全称量词∀：∀ xP(x)表示对于所有的x，P(x)成立。

- 存在量词∃：∃ xP(x)表示存在某个x，使得P(x)成立。

离散数学知识点(总23页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--说明：定义：红色表示。

定理性质：橙色表示。

公式：蓝色表示。

算法:绿色表示页码：灰色表示数理逻辑：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.代数系统：代数系统，子代数，积代数，同态，同构。

离散数学复习笔记数理逻辑逻辑：以研究人的思维形式及思维规律为目的的一门学科数理逻辑：利用数学符号来协助推理的一门形式逻辑学命题：能表达判断并具有确定真值的陈述句真值：每个命题都具有的一个值，要么为真，要么为假，不能随着环境变化原子命题：不能再分解的命题复合命题：由原子命题符号及联结词组成的有意义的命题表达式否定非P 合取P而且Q 析取P可兼或Q 排斥析取P不可兼或Q 单条件若P 则Q 双条件P当且仅当Q命题公式：满足特定条件的合法的命题表达式分量：命题公式中的原子命题翻译：将自然语言转化为数理逻辑语言真值表：对一个命题公式而言，将对于其分量的各种可能的真值指派汇聚成的表两个命题等价：对两个命题公式A,B,若对于A\B中的所有命题变元P1\P2..对天安门的任一组真值指派A，B相同对应的行的真值相同，则称A与B等价等价定律：交换律，结合律，分配律，摩根律，否定律，同一律重言式：永真式，无论对命题变元作何种真值指派，它都等价于T的命题公式永假式：无论对命题变元作何种真值指派，它都等价于F的命题公式用一个命题公式代替重言式中同一个分量，依然为重言式蕴含式：若A->B永真则称A蕴含B，记做A=>B原命题等价于它的逆否命题三个性质：传递性，A=>B A=>C A=>(B^C)， A=>B C=>B AvC=>B有效结论：H1，H2、、、、Hn，C为一组命题公式，若H1^H2^...^Hn=>C,称C 是一组条件下的有效结论三种方法：真值表法，直接证法，间接证法其他连接词：条件否定，与非，或非规范命题表达式：只含非且或合取范氏：当且仅当具有A1^A2^...^An形式，A1，A2...An都是命题变元或其否定组成的析取式析取范式：当且仅当具有A1vA2v...vAn形式，A1，A2...An都是命题变元或其否定组成的合取式一个命题公式的合取范氏或析取范氏并不是唯一的n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次 P^Q P^非Q一般n个命题变元共有2^n个小项n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次 PvQ Pv非Q主析取范式：对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则称该等价式为原式的主析取范式主合取范式：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则称该等价式为原式的主合取范式集合论集合：满足一定特征的对象的全体扩张原则：两个集合相等，当且仅当他们有相同的元素抽象原则：任给一个集合U和一个性质P，存在一个集合A，使得A的各个元素恰好是U的具有性质P的那些成员集合表示：列举法，特征法幂集：对给定的集合A，称以A的全体子集为元素的集合为A的幂集集合的基数：|A|元素的个数无限集合：元素个数能与某个真子集一一对应的集合序偶：有序的二元数组<x,y>笛卡尔积：称A*B={<x,y>|x属于A且y属于B}二元关系：以序偶作为元素的集合即关系xRy，关系前域指x，关系值域指y，关系域是前域和值域的并集。