第七章图
在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。例如用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系等等。图论起源于18世纪，它是研究由线连成的点集的理论。一个图中的结点表示对象，两点之间的连线表示两对象之间具有某种特定关系(先后关系、胜负关系、传递关系和连接关系等)。事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。由此经数学抽象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。
7.1 图的基本概念
7.1.1图的定义
7.1.1.1无向图
定义7.1.1 设A，B是任意集合。集合{(a,b)|a∈A且b∈B}称为A和B的无序积，记为A ＆B。
在无序积中，两个元素间的顺序是无关紧要的，即(a,b)＝(b,a)。
定义7.1.2 无向图G是一个二元组
我们可用平面上的点来表示顶点，两点间的连线表示边，从而将任一个无向图用图形表示出来。
［例7.1.1］无向图G＝
7.1.1.2有向图
定义7.1.3 有向图G是一个二元组
注：1)在有向图G＝
2)自回路既可看成是有向边又可看成是无向边；
3)去掉有向图中边的方向得到的图称为该有向图的基图。
［例7.1.2］有向图G＝
7.1.1.3相关概念
在无向图或有向图中，
1）有限图与无限图；
2）n阶图；|V|=n;
3) 零图 E=Φ；
4）平凡图（|V|=n ，E=Φ）；
5)对于无向图，若边e=(u,v)，则称u和v是边 e的端点，称边 e关联于u和v，若u=v，则称此为环，边与顶点的关联次数是0，1，2；至少有一条边相连的两个顶点相邻；至少一个公共顶点的两条边相邻
6)对于有向图，若边e=
7)关联于同一个顶点的边称为环（自回路）；若关联于同一对顶点的边多于一条时，称这些边为平行边，平行边的条数称为边的重数；
8)不与任何顶点邻接的顶点称为孤立点；含有平行边的图称为多重图，不含有平行边，也不含环的图称为简单图；
7.1.2顶点的度数，握手定理
定义7.1.4 (1)在无向图G=〈V，E〉中，v∈V。与v关联的边数称为v的度数，记为deg(v)；
(2) 在有向图G=〈V，E〉中，v∈V。以v为始点的边数称为v的出度，记为deg＋(v)；以v 为终点的边数称为v的入度，记为deg－(v)；称deg(v)= deg＋(v)+ deg－(v)称为v的度(数)。［例7.1.3］求例7.1.1中无向图每个顶点的度数；求例7.1.3中有向图每个顶点的出度、入度和度。
注：若结点有自回路，则结点的度数因此而增加2；若有向图的结点v有自回路，则它的出度和入度分别因此而增加1。孤立结点的度数为0。
定理7.1.1 (Euler握手定理)在图G=
∈V
v
deg(v)=2|E|。
推论7.1.1 任何图中度数为奇数的结点为偶数个。
定理7.1.2 在有向图G=
∑∈V v deg＋(v)= ∑
∈V
v
deg－(v)=|E|。
度序列，出度序列，入度序列：
定理7.1.3：度序列可图化的充要条件是度序列之和是偶数。
［例7.1.4］（1）3，2，3，3 5，2，3，1，4，7可图化吗？
（2）一知一个图有10条边，4个3度顶点，其余顶点的度数均小于等于2，问该图至少有几个顶点？
7.1.3子图
定义7.1.5 设图G=
（1）若V′?Ｖ，Ｅ′?Ｅ，则称Ｇ′是Ｇ的子图，记为G′?G；
（2）若G′?G且V′?Ｖ或Ｅ′?Ｅ，则称Ｇ′是Ｇ的真子图，记为G′?G；
（3）若G′?G且V′=V，则称Ｇ′是Ｇ的生成子图；
（4）V′?V，V′Φ
≠，以V′为顶点集，以所有端点均在V′中的G的边为边集的图称为由V′诱导出的Ｇ的子图；
（5）E′?E，E′Φ
≠，以E′为边集，以E′中的边的端点点为顶点集的图称为由E′诱导出
的Ｇ的子图；
［例7.1.5］求例7.1.1中无向图的子图、生成子图、由边集诱导的子图和由顶点集诱导的子图。
7.1.4完全图、补图和图的同构
定义7.1.6 在无向简单图G=〈V，E〉中，|V|=n。若每对结点都邻接(即每对结点之间都有
边)，则称之为无向完全图，记为K
n
。
类似地，可以定义有向完全图。
［例7.1.6］K
2，K
3
，K
4
，K
5
及2、3、4、5个顶点的有向完全图。
定义7.1.7 设G=
G和G互为补图。
［例7.1.7］求补图。
定义7.1.8 设图G
1= 1 ，E 1 >，G 2 = 2 ，E 2 >。若存在双射f：V 1 —>V 2 ，满足：?u，v∈V1， [u,v]∈E 1?[f(u),f(v) ]∈E2且[u,v]的重数和[f(u),f(v)]的重数相等 ([u,v]指(u,v)或 [u,v])，则称G 1和G 2 同构，记为G 1 ≌G 2 。 由于一个图是由其顶点集和边集所决定的，而同构的两个图中顶点集之间存在一一对应关系，且这种对应关系保持顶点间的邻接关系及边的重数，故抽象地看，两个同构的图本质上是一样的。 两个图同构的必要条件： 顶点数相等; 边数相等; 所有顶点度数之和相等；度数相同的顶点数相等。 自补图 7.2 通路、回路、图的连通性 7.2.1通路和回路 定义7.2.1 给定图G=〈V，E〉，设v 0,v 1 ,…,v n ∈V，e 1 ,e 2 ,…,e n ∈E，顶点和边交替出现的 序列v 0e 1 v 1 e 2 …e n v n 称为从顶点v 到v n 的通路，v 和v n 分别称为该通路的起点和终点；称 通路上的边数为该通路的长度。 当v 0和v n 相等时，称该通路为回路或圈。 若通路(回路)的所有边都各不相同，则称该通路(回路)为简单通路(回路)；若通路(回路)的所有顶点都各不相同，则称该通路(回路)为初级通路(回路)。 ［例7.2.1］求下图的通路、回路、简单通路、简单回路、初级通路、初级回路 每一初级通路(回路)一定是简单通路(回路)；反之则不然。在简单图中，可以用顶点序列来表示通路(回路)，当然在不产生二义性的前提下也可以用边的序列来表示通路(回)路。 定理7.2.1 给定图G= 推论7.2.1 给定图G= 定理7.2.2 给定图G= 注： 在一个具有n 个顶点的图中， （1）任何初级通路的长度均不大于n-1； （2）任何初级回路的长度均不大于n 。 7.2.2图的连同性 定义7.2.2 给定图G=〈V ，E 〉，u,v ∈V 。若存在从u 到v 的通路，则称从u 到v 是可达的或称u 可达v 。 规定任一个顶点总是可达自身。 定义7.2.3 给定无向图G=〈V ，E 〉。若G 的任何两个顶点是相互可达的，则称G 是连通图，否则称G 是非连通图。 在无向图G=〈V ，E 〉中，定义关系R V V ??为：? u,v ∈V ，uRv ? u 可达v 。则R 是V 上的一个等价关系，从而可以决定V 的一个划分，我们称每一个由划分块诱导出的G 的子图为G 的连通分支，用p(G)表示G 的连通分支数。 每个顶点在且仅在一个连通分支中。若p(G)＝1，则G 是连通图。 ［例7.2.2］ 给出连通图、非连通图；图的连通分支。 定义7.2.4 给定有向图G=〈V ，E 〉。对任何两顶点u,v ∈V ， （1）若u 和v 相互可达，则称G 是强连通的； （2）若u 和v 至少有一个可达另一个，则称G 是单向连通的； （3）若其基图是连通的，则称G是弱连通的。 ［例7.2.3］给出强连通图、单向连通图和弱连通图。 强连通图 => 单向连通图 => 弱连通图。 定理7.2.3 有向图G是强连通的?G中有一回路，它至少通过每个顶点一次。 定义7.2.5 给定图G=〈V，E〉，u,v∈V。若u可达v，则称从u到v的长度最短的通路为u 与v之间的短程线，其长度称为u到v的距离，记为d(u,v)。 7.2.3点割集，割点，边割集，桥 (1)点割集和割点 定义7.2.6设无向图G=〈V，E〉若存在顶点子集V′?V，使G删除V′后，所得子图G-V′的连通分支数P(G-V′)>P(G),而删除V′的任何真子集V''后,P(G-V'')=P(G),则 V′为G的点割集,如果V′只有一个顶点v,则称v为割点 （2）边割集和桥 定义7.2.7设无向图G=〈V，E〉若存在边子集E′?V，使G删除E′后，所得子图G-E′的连通分支数P(G-E′)>P(G),而删除E′的任何真子集E''后,P(G-E'')=P(G),则 E′为G的边割集,如果E′只有一个顶点e,则称e为桥. 7.3 图的矩阵表示 7.3.1无向图的关联矩阵 7.3.1 设有向图G= 1，v 2 ，…，v n }，E={e 1 ,e 2 ,…,e m },则n?m阶方阵A=(a ij) 称为G的关联矩阵，记为M(G)=(m ij ),其中m ij 为v i 与边e j 关联的次数(0,1,2)。 (1)M的每列元素之和等于2; (2)M的第i行元素之和等于d(v i ); (3) M的所有元素之和2m; (4) 若M的第i行元素之和等于0,则v i 是孤立点; 7.3.1有向图的关联矩阵 定义7.3.2设无环有向图G= 1，v 2 ，…，v n }，E={e 1 ,e 2 ,…,e m },则n?m阶矩阵 A=(a ij )称为G的关联矩阵，记为M(G)=(m ij ),其中 m ij =?? ???-的起点 是不关联与的起点是j i j i j i e v e v e v 101 (1)M 的每列元素之和等于0,M 的所有元素之和0. (2) M 的所有值为1元素之和=值为-1元素之和=m. 7.3.3有向图的邻接矩阵 定义7.3.3 设有向图G= 在不考虑结点编序的情形下，图的邻接矩阵是唯一的；一个邻接矩阵可以完全确定一个有向图。在一个简单有向图G 中, deg + (v i )= ∑ =n j 1 a ij =第行中元素的和 deg - (v i )=第i 列中元素的和= ∑ =n j 1 a kj ［例7.3.1］ 求下图的邻接矩阵。 定理7.3.1 设A 有向图G= k ij )的第 i 行第j 列元素 a k ij 等于从 v i 到v j 长为k 的通路数， a k ii 等于经过 v i 长为k 的回路数。 ［例7.3.2］ 求下图的顶点b 到其他顶点长为3的通路数。 7.3.4有向图的可达矩阵 定义7.3.4 设有向图G= ??=否则可达从 0 n ,1,2,j ,i v v 1 j i 可达矩阵的元素的值表明图中任两个顶点间是否存在通路，以及经过某个结点是否存在回路。 若记B ＝A ＋A 1＋…A n-1=(b ij )n ?n ，则对i,j=1,2,…,n 且i ≠j ，若 b ij ≠0，则p ij =1，否则 p ij =0。p ii =1，i=1,2,…,n 。 ［例7.3.3］ 求下图的可达矩阵。 类似地，我们可以定义无向图的邻接矩阵和可达矩阵。无向图的邻接矩阵和可达矩阵一定是对称矩阵。 7.4最短路径和关键路径 7.4.1赋权图和最短通路问题 定义7.4.1 对于有向图或无向图，给每一条边都赋予权(正实数)的图称为赋权图，记为 G= ij 为边e的权, 称W(G)=∑ ∈) ( ) ( G E e e W为图G的权。 在赋权图中，通路的边的权权重之和叫通路的权重。 7.4.2最短路经 单源点的最短路径问题：给定带权有向图（或无向）G＝ 问题解决算法。即由迪杰斯特拉（Dijkstra）提出的一个按路径长度递增的次序产生最短路径的算法。该算法的基本思想是：设置两个顶点的集合S和T＝V－S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S 是空集，从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到S中为止。Dijkstra算法的实现。 （1）S为已找到从v0出发的最短路径的终点的集合，它的初始状态为空集，T=V-S,。引进一个辅助向量D，它的每个分量D[i] 表示始点v0到每个终点v i的最短路径的长度。它的初态为：若从v0到v i有弧（边），则D[i]为弧上的权值；否则置D[i]为∞。 (2)顶点选取，D[u]=Min{D[i]| vi∈T}, S=S+{ v u }T=T-{v u}; （3）修改D[j] D[j]=Min{D[j], D[u]+Wuj } Vj∈V-S 其中，D[i] 或者弧（v, vj）上的权值，或者是D[u]和弧（V u, Vj）上的权值之和。 (4)重复操作⑵、⑶共n-1次。由此求得从v 到图上其余各顶点的最短路径 ［例7.4.1］求下列赋权图中v 1 到其他顶点的距离。 7.4.3关键路径 若在带权的有向图中，以顶点表示事件，以有向边表示活动，边上的权值表 示活动的开销（如该活动持续的时间），则此带权的有向图称为AOE 网(PERT 图)。 利用AOE 网进行工程管理时要需解决的主要问题是： （1） 计算完成整个工程的最短路径。 （2）确定关键路径，以找出哪些活动是影响工程进度的关键。 3. 关键路径的确定 后继元集：},|{)(E x v V x x v D >∈<∧∈=Γ+ 前导元集 },|{)(E v x V x x v D >∈<∧∈=Γ- 为了在AOE 网中找出关键路径，需要定义几个参量，并且说明其计算方法。 （1）事件的最早发生时间TE[Vi] TE[Vi]是指从源点到顶点的最大路径长度代表的时间。这个时间决定了所有 从顶点发出的有向边所代表的活动能够开工的最早时间。 计算vk 发生的最早时间的方法如下： TE[Vl]=0 TE[Vi]=max{TE[Vj]+Wji,)(i D j V V - Γ∈}。 （2）事件的最迟发生时间TL[Vi] 计算vk 发生的最早时间的方法如下： TL[Vn]=最长路经长度 TL[Vi]=min{TL[Vj]-Wij,)(i D j V V +Γ∈}。 （3缓冲时间 ES(Vi)=TL(Vi)-TE(Vi) ［例7.4.2］求下列PERT 图得关键路径 离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数1 q: 3是无理数0 r: 2是无理数 1 s: 6能被2整除1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ?(?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) 2017年11月上交的离散数学形考任务一 本课程的教学内容分为三个单元，其中第三单元的名称是（A ）． 选择一项： A. 数理逻辑 B. 集合论 C. 图论 D. 谓词逻辑 题目2 答案已保存 满分10.00 标记题目 题干 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（D ）． 选择一项： A. 函数 B. 关系的概念及其运算 C. 关系的性质与闭包运算 D. 几个重要关系 题目3 答案已保存 满分10.00 标记题目 题干 本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲． 选择一项： A. 18 B. 20 C. 19 D. 17 题目4 答案已保存 满分10.00 标记题目 题干 本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（ C）．选择一项： A. 集合恒等式与等价关系的判定 B. 图论部分书面作业 C. 集合论部分书面作业 D. 网上学习问答 题目5 答案已保存 满分10.00 标记题目 题干 课程学习平台左侧第1个版块名称是：（C）． 选择一项： A. 课程导学 B. 课程公告 C. 课程信息 D. 使用帮助 题目6 答案已保存 满分10.00 标记题目 题干 课程学习平台右侧第5个版块名称是：（D）． 选择一项： A. 典型例题 B. 视频课堂 C. VOD点播 D. 常见问题 题目7 答案已保存 满分10.00 标记题目 题干 ―教学活动资料‖版块是课程学习平台右侧的第（A）个版块． 选择一项： A. 6 B. 7 C. 8 D. 9 题目8 答案已保存 满分10.00 标记题目 题干 课程学习平台中―课程复习‖版块下，放有本课程历年考试试卷的栏目名称是：（D ）． 选择一项： A. 复习指导 B. 视频 C. 课件 D. 自测 请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交． 解答：学习计划 学习离散数学任务目标： 第一章 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规则 第五章 离散数学第七章检测题 一、 单项选择题（每小题2分，共20分） 1．下图中是哈密尔顿图的是( 2 ) 2．下面给出的四个图中，哪个不是汉密尔顿图（ （4） ）． 3．下列是欧拉图的是( 2 ) 4. 下列各图不是欧拉图的是（ 4 ） 5．设()A G 是有向图,G V E =的邻接矩阵，其第i 列中“1”的数目为（ ）。 (C) (1)．结点i v 的度数； (2)．结点i v 的出度； (3)．结点i v 的入度； (4)．结点j v 的度数。 6．无向图G 中有16条边，且每个结点的度数均为2，则结点数是( 2 ) (1)．8 (2)．16 (3)．4 (4)．32 7．设Ｇ＝为无向图??E V ,，23,7==E V ，则Ｇ一定是（ （4） ）． (1)．完全图； (2)．零图； (3)．简单图； (4)．多重图． 8．若具有n 个结点的完全图是欧拉图，则n 为( 2 ). (1)．偶数；(2)．奇数； (3)． 9； (4)． 10． 9．无向图G 是欧拉图，当且仅当（ ）． (1) (1)．G 连通且所有结点的度数为偶数； (2)．G 的所有结点的度数为偶数； (3)．G 连通且所有结点的度数为奇数； (4)．G 的所有结点的度数为奇数． 10．下面哪一种图不一定是树（ ）． (3) (1)．无圈连通图； (2)．有n 个结点1n -条边的连通图； (3)．每对结点间都有路的图； (4)．连通但删去一条边就不连通的图． 二、 填空题（每空3分，共45分） 1．在下图中，结点v 2的度数是 4 ，结点v 5的度数是 3 。 2．在一棵根树中，有且只有一个结点的入度为__0___，其余所有结点的入度均为_1__。 其中入度为__0___的结点称为树根，出度为__0___的结点称为树叶。 3．设图111,G V E =，22221,,G V E E E =?且，如果 ，则称2G 是1G 的子图，如果 ，则称2G 是1G 的生成子图。(2121,V V V V ?=) 4．在任何图,G V E =中，∑∈V v v )deg(= 2 │E │ ，其奇数度结点的个数必为 偶数 。 5．一棵有6个叶结点的完全二叉树，有___5__个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有__9___个叶结点。 6 ．设图,G V E =，V ＝｛ 1v ,2v ,3v ,4v ｝的邻接矩阵()A G = ????? ???? ???00 1 00111 101 1010， 则 1v 的入度)(deg 1v ＝ 3 ，4v 的出度)(deg 4v = 1 。 7．一个无向树中有6条边，则它结点数为 7 。 三、 简答题（每小题5分，共25分） 1．对有向图,G V E =求解下列问题： （1）写出邻接矩阵A ； 第七章图 在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。例如用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系等等。图论起源于18世纪，它是研究由线连成的点集的理论。一个图中的结点表示对象，两点之间的连线表示两对象之间具有某种特定关系(先后关系、胜负关系、传递关系和连接关系等)。事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。由此经数学抽象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。 7.1 图的基本概念 7.1.1图的定义 7.1.1.1无向图 定义7.1.1 设A，B是任意集合。集合{(a,b)|a∈A且b∈B}称为A和B的无序积，记为A ＆B。 在无序积中，两个元素间的顺序是无关紧要的，即(a,b)＝(b,a)。 定义7.1.2 无向图G是一个二元组 第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为) ?，在（a）中为假命题，在(b)中为真命题。 (x xF (2)在两个个体域中都解释为) (x ?，在（a）(b)中均为真命题。 xG 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) x x∧ ? ?? F ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) x F H x→ ?? (x ) ( ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F x G y x→ ? ? y ∧ )) ( , ( ) x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) y x F G y→ ?? ∧ ? x ( ) ( , H ( x ) (y ( 9.给定解释I如下: (a) 个体域D为实数集合R. 第七章作业 评分要求: 1、合计100分 2、给出每小题得分(注意: 写出扣分理由)、 3、总得分在采分点1处正确设置、 1 设R={ 离散数学（第五版）清华大学出版社第7章习题解答 7.1 (1),(2),(3),(5)都能构成无向图的度数列,其中除(5)外又都能构成无向简单图的度数列. 分析1°非负整数列d,d ,L,d 能构成无向图的度数列当且仅当n di为 1 2n∑ i=1偶数,即d1,d2,L,dn中的奇数为偶数个.（1）,(2),(3),(5)中分别有4个,0个,4个,4 个奇数,所以,它们都能构成无向图的度数列,当然,所对应的无向图很可能是非简 单图.而(4)中有 3 个奇数,因而它不能构成无向图度数列.否则就违背了握手定理的推论. 2°(5) 虽然能构成无向图的度数列,但不能构成无向简单度数列.否则,若存在无向简单图G,以1,3,3,3 为度数列,不妨设G 中顶点为v1,v2,v3,v4,且d(vi)=1,于是d(v2)=d(v3)=d(v4)=3.而v1只能与v2,v3,v4之一相邻,设v1与v2相邻,这样一来,除v2能达到3度外, v3,v4都达不到3度,这是矛盾的. 在图7.5所示的4个图中,(1) 以1为度数列,(2)以2为度数列,(3)以3为度数列,(4)以4为度数列(非简单图). 7.2 设有几简单图D以2,2,3,3为度数列,对应的顶点分别为v1,v2,v3,v4,由于d(v)=d+(v)+d_(v),所示,d+(v)-d-(v)=2-0=2,d+(v )=d(v )-d-(v ) 11222=2-0=2,d+(v)=d(v)-d-(v)=3-2=1,d+(v)=d(v)-d-(v)=3-3=0 333444 81 由此可知,D 的出度列为2,2,1,0,且满足d+(v)= d-(v).请读者画出 ∑i∑ｉ 一个有向图.以2,2,3,3为度数列,且以0,0,2,3为入度列,以2,2,1,0为出度列. 7.3 D 的入度列不可能为1,1,1,1.否则,必有出度列为2,2,2,2(因为d(v)=d+(v)+d-(v)),)此时,入度列元素之和为4,不等于出度列元素之和8,这违背握手定理.类似地讨论可知,1,1,1,1也不能为D的出席列. 7.4 不能. N阶无向简单图的最大度Δ≤n-1.而这里的n个正整数彼此不同,因而这n个数不能构成无向简单图的度数列,否则所得图的最大度大于n,这与最大度应该小于等于n-1矛盾. 2015春课件作业 第一部分集合论 第一章集合的基本概念和运算 1-1 设集合 A ={{2，3,4}，5，1}，下面命题为真是 A （选择题） [ A ] A．1 ∈A； B．2 ∈ A； C．3 ∈A； D．{3，2,1} ? A。 1-2 A,B,C 为任意集合，则他们的共同子集是 D （选择题） [ D ] A．C； B．A； C．B； D．?。 1-3 设 S = {N，Z，Q，R}，判断下列命题是否正确（是非题） （1） N ? Q，Q ∈S，则 N ? S，否［错］（2）-1 ∈Z，Z ∈S，则 -1 ∈S 。否［错］ 1-4 设集合 B = {4，3} ∩?， C = {4，3} ∩{ ? }，D ={ 3，4，? }， E = {x│x ∈R 并且 x2 - 7x + 12 = 0}， F = { 4，?，3，3}， 试问：集合 B 与那个集合之间可用等号表示 A （选择题） [A ] A. C; B. D; C. E; D. F. 1-5 用列元法表示下列集合：A = { x│x ∈N 且 3－x 〈 3 }（选择题） [D ] A. N; B. Z; C. Q; D. Z+ 1-6 为何说集合的确定具有任意性 ? (简答题) 按照所研究的问题来确定集合的元素。而我们所要研究的问题当然是随意的。所以，集合的定义（就是集合成分的确定）就带有任意性。 第二章二元关系 2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下： R = {〈x，y〉x，y ∈X 且 x > y } （综合题） 求：(1)domR =?; (2)ranR =?; (3)R 的性质。 所谓谓词表达法，即是将集合中所有元素的共同性质用一个谓词概括起来，如本题几例所示。有的书上称其为抽象原则。反过来，列元法则是遵照元素的性质和要求，逐一将他们列出来，以备下用,结果如下： R = {<1,1>,<2,2>,<3,3>}； (1)DomR={R中所有有序对的x}={3,2,1}; (2)RanR={R中所有有序对的y}={3,2,1}； (3)R 的性质:自反,对称,传递性质. 2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即 R = {〈x，y〉│x，y ∈Z+ 且 x + 3y = 12}， 试给出 dom（R 。R）。（选择题） [ B ] A. 3； B. {3}； C. 〈3，3〉； D.{〈3，3〉}。 2-3 判断下列映射 f 是否是 A 到 B 的函数；以及函数的性质。最后指出 f：A→B 中的双射函数。（选择题） [ B ] （1）A = {1，2，3}，B = {4，5}， f = {〈1，4〉〈2，4〉〈3，5〉}。 （2）A = {1，2，3} = B， f = {〈1，1〉〈2，2〉〈3，3〉}。 （3）A = B = R， f = x 。 第七章作业 评分要求： 1. 合计100分 2. 给出每小题得分(注意: 写出扣分理由). 3. 总得分在采分点1处正确设置. 1 设R={ 4.1 （1）设S={1，2}，R 是S 上的二元关系，且xRy 。如果R=Is ，则（A ）；如 果R 是数的小于等于关系，则（B ），如果R=Es ，则（C ）。 （2）设有序对 习题七 1．对图7.7中的两个图，各作出两个顶点割。 解： 对图7.7增加加节点标记如下图所示， 则(a)的两个顶点割为： V11={a,b} ； V12={c,d} (b)的两个顶点割为： V21={u,v} ； V12={y} 2．求图7.7中两个图的()G κ和()G λ. 解：如上两个图，有 k(G1)=λ(G1)=2, k(G2)=1, λ(G2)=2 3．试作出一个连通图G , 使之满足：()()()G G G δλκ== 解：做连通图G 如下，于是有 ： （a ） （b ） 图7.7 ) (a 7 .7图w y ) ()()(G G G k δλ== 4．求证, 若()q p G ,是-k 边连通的, 则2/kp q ≥. 证明：设G 是k —边连通的，由定义有λ(G)≧k. 又由定理7.1.2知λ(G)≦ ，因此有 k ≦λ(G) ≦ ≦ 即 k ≦ ，从而 5．求证, 若G 是p 阶简单图, 且()2-≥p G δ, 则()()G G δκ=. 分析：由G 是简单图，且()2-≥p G δ，可知G 中的δ(G)只能等于 p-1或p-2； 如δ(G)= p-1,则G 是一个完全图，根据书中规定，有k(G)=p-1=δ(G)； 如δ(G)= p-2,则从G 中任取V （G ）的子集V1，其中|V1|=3，则V(G)-V1的点导出子图是连通的，否则在V1中存在一个顶点v ，与其他两个顶点都不连通。则在G 中，顶点v 最多与G 中其他p-3个顶点邻接，所以d(v)≤p-3，与δ(G)= p-2矛盾。这说明了在G 中，去掉任意p-3个顶点后G 还是连通的，按照点连通度的定义有k(G)>k-3，又根据定义7.1.1，()()G G δκ≤，有k(G)=k-2。 证明：因为G 是简单图 ,所以d(v)≦p-1,v ∈V(G),已知δ(G)≧p-2 （ⅰ）若δ(G)= p-1,则G=Kp （完全图），故k(G)=p-1=δ(G)。 （ⅱ）若δ(G)= p-2, 则 G ≠Kp,设u,v 不邻接，但对任意的w ∈V(G),有 uw,vw ∈E(G).于是，对任意的V1?V(G), | V1|=p-3 ,G-V1必连通. 因此必有k(G) ≧p-2=δ(G),但k(G) ≦δ(G)。 故k(G) =δ(G)。 6．找出一个p 阶简单图, 使()3-=p G δ, 但()()G G δκ<. 解： ??????p q 2?? ? ???p q 2p q 2p q 2。2kp q ≥。 ，如图)(1)(,32)(,5G G p G p G δκδ<=-=== 离散数学第二版邓辉文编著第一章第二节习题答案 1.2 映射的有关概念 习题1.2 1. 分别计算?1. 5?，?-1?，?-1. 5?，? 1. 5?，?-1?，?-1. 5?. 解?1. 5?=2，?-1?=-1，?-1. 5?=-1，?1. 5?=1，?-1?=-1，?-1. 5?=-2. 2. 下列映射中，那些是双射? 说明理由. (1)f :Z →Z , f (x ) =3x . (2)f :Z →N , f (x ) =|x |+1. (3)f :R →R , f (x ) =x 3+1. (4)f :N ?N →N , f (x 1, x 2) =x 1+x 2+1. (5)f :N →N ?N , f (x ) =(x , x +1). 解 (1)对于任意对x 1, x 2∈Z ，若f (x 1) =f (x 2) ，则3x 1=3x 2，于是x 1=x 2，所以f 是单射. 由于对任意x ∈Z ，f (x ) ≠2∈Z ，因此f 不是满射，进而f 不是双射. (2)由于2, -2∈Z 且f (2) =f (-2) =3，因此f 不是单射. 又由于0∈N ，而任意x ∈Z 均有f (x ) =|x |+1≠0，于是f 不是满射. 显然，f 不是双射. (3)对于任意对x 1, x 2∈R ，若f (x 1) =f (x 2) ，则x 1+1=x 2+1，于是x 1=x 2，所以f 是单射. 对于任意y ∈R ，取x =(y -1) ，这时 1??3f (x ) =x +1=?(y -1) 3?+1=(y -1) +1=y ， ??33313 所以f 是满射. 进而f 是双射. 第七章习题答案 2. 试问下列关系中哪个能构成函数： (1){< x1, x2 > | x1, x2∈N, x1 + x2 <10} (2){< x, y > | x, y∈R, y = x2} (3){< x, y > | x, y∈R, y2 = x} 解只有(2)满足单值性，能构成函数。 6. 设X = {0, 1, 2}，求出X X中的如下函数： (1)f2(x) = f (x) (2)f2(x) = x (3)f3(x) = x 解(1) 任取y∈ran( f )，则有x∈X使得f (x) = y，因而 f (y) = f2(x) = f (x) = y 若ran( f ) = {0}，则f1 = {< 0, 0 >,< 1, 0 >,< 2, 0 >}。 若ran( f ) = {1}，则f2 = {< 0, 1 >,< 1, 1 >,< 2, 1 >}。 若ran( f ) = {2}，则f3 = {< 0, 2 >,< 1, 2 >,< 2, 2 >}。 若ran( f ) = {0, 1}，则有两个函数 f4 = {< 0, 0 >,< 1, 1 >,< 2, 0 >}和 f5 = {< 0, 0 >,< 1, 1 >,< 2, 1 >}。 若ran( f ) = {0, 2}，则有两个函数 f6 = {< 0, 0 >,< 1, 0 >,< 2, 2 >}和 f7 = {< 0, 0 >,< 1, 2 >,< 2, 2 >}。 若ran( f ) = {1, 2}，则有两个函数 f8 = {< 0, 1 >,< 1, 1 >,< 2, 2 >}和 f9 = {< 0, 2 >,< 1, 1 >,< 2, 2 >}。 若ran( f ) = {0, 1, 2}，则f10必为I X 。所以，共有10个函数满足条件。 (2) 若f (x) = y≠x，则f (y) = f2(x) = x。集合 { x | x∈X∧ f (x) ≠x }的元素个数为偶数，可为0或2。若它为0，则f1必为I X 。若它为2，则有三个函数 f2 = {< 0, 0 >,< 1, 2 >,< 2, 1 >} f3 = {< 0, 2 >,< 1, 1 >,< 2, 0 >} f4 = {< 0, 1 >,< 1, 0 >,< 2, 2 >} 所以，共有4个函数满足条件。 (3) 设f (x) = y≠x，f (y) = z。若z = x，则 f3(x) = f2(y) = f (z) = f (x) = y≠x， 矛盾，所以z≠x。若z = y，则 f3(x) = f2(y) = f (z) = f (y) = z≠x， 2017年11月上交的离散数学形考任务一本课程的教学内容分为三个单元，其中第三单元的名称是（A ）． 选择一项： A. 数理逻辑 B. 集合论 C. 图论 D. 谓词逻辑 题目2 答案已保存 满分10.00 标记题目 题干 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（D ）． 选择一项： A. 函数 B. 关系的概念及其运算 C. 关系的性质与闭包运算 D. 几个重要关系 题目3 答案已保存 满分10.00 标记题目 题干 本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲． 选择一项： A. 18 B. 20 C. 19 D. 17 题目4 答案已保存 满分10.00 标记题目 题干 本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（ C）．选择一项： A. 集合恒等式与等价关系的判定 B. 图论部分书面作业 C. 集合论部分书面作业 D. 网上学习问答 题目5 答案已保存 满分10.00 标记题目 题干 课程学习平台左侧第1个版块名称是：（C）． 选择一项： A. 课程导学 B. 课程公告 C. 课程信息 D. 使用帮助 题目6 答案已保存 满分10.00 标记题目 题干 课程学习平台右侧第5个版块名称是：（D）． 选择一项： A. 典型例题 B. 视频课堂 C. VOD点播 D. 常见问题 题目7 答案已保存 满分10.00 标记题目 题干 “教学活动资料”版块是课程学习平台右侧的第（ A ）个版块． 选择一项： A. 6 B. 7 C. 8 D. 9 题目8 答案已保存 满分10.00 标记题目 题干 课程学习平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（D ）．选择一项： A. 复习指导 B. 视频 C. 课件 D. 自测 请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交． 解答：学习计划 列各组数中，那些能构成无向图的度数列？那些能构成无向简单图的度数列？ （1）1，1，1，2，3 （2）2，2，2，2，2 （3）3，3，3，3 （4）1，2，3，4，5 （5）1，3，3，3 解答：（1），（2），（3），（5）能构成无向图的度数列。 （1），（2），（3）能构成五项简单图的度数列。 设有向简单图D 的度数列为2，2，3，3，入度列为0，0，2，3，试求D 的出度列。 解：因为 出度=度数-入度，所以出度列为2，2，1，0。 设D 是4阶有向简单图，度数列为3，3，3，3。它的入度列（或出度列）能为1，1， 1，1吗？ 解：由定理可知，有向图的总入度=总出度。该有向图的总入度=1+1+1+1=4,总出度=2+2+2+2=8,4！=8，所以它的出度列（或入度列）不能为1，1，1，1。 35条边，每个顶点的度数至少为3的图最多有几个顶点？ 解：根据握手定理，所有顶点的度数之和为70，假设每个顶点的度数都为3，则 n 为小于等于3 70的最大整数，即：２３ ∴ 最多有23个顶点 7.7 设n 阶无向简单图G 中，δ（G ）=n-1，问△（G ）应为多少？ 解： 假设n 阶简单图图n 阶无向完全图，在K n 共有 2)1(-n n 条边，各个顶点度数之和为n （n-1） ∴每个顶点的度数为 n n n )1(-=n-1 ∴△（G ）=δ（G ）=n-1 一个n （n ≥２）阶无向简单图Ｇ中，n 为奇数，有r 个奇度数顶点，问Ｇ的补图G 中有几个奇度顶点？ 解：在K n 图中，每个顶点的度均为（n-1），n 为奇数，在Ｇ中度为奇数的顶点在G 中仍然为奇数， ∴共有r 个奇度顶点在G 中 ７.９ 设Ｄ是n 阶有向简单图，Ｄ’是Ｄ的子图，已知Ｄ’的边数m ’＝n （n-1），问Ｄ的边数m 为多少？ 解： 在Ｄ’中m ’＝n （n-1） 可见Ｄ’为有个n 阶有向完全图，则Ｄ＝Ｄ’ 即Ｄ’就是Ｄ本身， ∴m=n （n-1） 有向图D 入图所示。求D 中长度为4 的通路总数，并指出其中有多少条是回路？ 第七章 谓词逻辑 １．用谓词表达下列命题 1) 小张不是工人。 设 c:小张 W(x): x 是工人 )c (W ? 2) 所有教练员都是运动员。 设 J(x):x 是教练, W(x):x 是运动员 ))x (W )x (J )(x (→? 3) 没有一个国家选手不健壮。 设 C(x):x 是国家选手,J(x):x 健壮 ))x (J )x (C )(x (?∧?? 4) 有些大学生不钦佩老师。 设 D(x):x 是大学生, L(x):x 是老师, P(x,y):x 钦佩y )))y ,x (P )y (L )(y ()x (D )(x (∧?∧? 5) 小莉既聪明又美丽。 设 l:小李 C(x):x 聪明 M(x):x 美丽 )l (M )l (C ∧ 6) 不是所有的高中生都能上大学。 设 G(x):x 是高中生, D(x):x 上大学 ))x (D )x (G )(x (→?? 7) 每个有理数都是实数。 设Q(x):x 是有理数, R(x):x 是实数 ))x (R )x (Q )(x (→? 8) 某些实数是有理数。 设R(x):x 是实数, Q(x):x 是有理数 ))x (Q )x (R )(x (∧? 9) 并非每个实数都是有理数。 设R(x):x 是实数, Q(x):x 是有理数 ))x (Q )x (R )(x (→?? 10) 若m 是奇数，则2m 不是奇数。 设Q(x):x 是奇数， )m 2(Q )m (Q ?→ 11) 直线A 与直线B 平行，当且仅当直线 A 与 B 不相交。 设L(x):x 是直线，P(x,y):x 平行于y, X(x,y):x 与y 相交 →←))B ,A (X )B (L )A (L ())B ,A (P )B (L )A (L (?∧∧∧∧ 12) 对于每个实数ｘ，存在一个更大的实数ｙ。 设R(x):x 是实数, D(x,y):x 大于y, )))x ,y (D )y (R )(y ()x (R )(x (∧?→? 2. 设P(x)为“x 是质数”，E(x)为“ｘ是偶数”， Q(x)为“x 是奇数”，D(x,y)为“x 除尽y ”，把下 列各式译成汉语： 1）P(5)； 2）E(2)∧P(2)； 3）(?ｘ)(E (x)∧D(x,6))； 4）(?ｘ)(D(2,x)→E(x))； 5) (?ｘ)(E(x)→D(2,x))； 6）(?ｘ)(E(x)→(?ｙ)(D(x,y)→E(y)))； 7) (?ｘ)(P(x)→(?ｙ)(E(y)∧D(x,y)))； 8) (?ｘ)(Q(x)→(?ｙ)(P(y)→D(x,y)) 1) P(5)；5是偶数。 2) E(2)∧P(2)；2是偶数也是质数。 3) D(x,6))(E (x))x (∧?;存在偶数可以除尽6。 4) E (x))x)(D(2,)x (→?;被2除尽的数都是偶数。 5) x))D(2,E (x)()x (?→??; 非偶数都不能被2除尽。 6) )))y (E )y ,x (D )(y ()x (E )(x (→?→?; 所有能被偶数除尽的数都是偶数。 7) )))y ,x (D )y (E )(y ()x (P )(x (∧?→?; 对任给的质数，存在偶数可被质数除尽。 8) )))y ,x (D )y (P )(y ()x (Q )(x (→?→?； 所有质数都不能被任意奇数整除。 离散数学练习题 第一章 一．填空 1.公式) ∨ ? ∧的成真赋值为 01；10 ? p∧ ( (q ) p q 2.设p, r为真命题，q, s 为假命题，则复合命题) ? ? →的真 p→ ) ( (s r q 值为 0 3.公式) ∨ ? q ?与共同的成真赋值为 01；10 p ? ∧ p∧ ) ( ( ) p (q q 4.设A为任意的公式，B为重言式，则B A∨的类型为重言式 5．设p, q均为命题，在不能同时为真条件下，p与q的排斥也可以写成p与q的相容或。 二．将下列命题符合化 1. 7不是无理数是不对的。 解：) ?，其中p: 7是无理数；或p，其中p: 7是无理数。 ? (p 2.小刘既不怕吃苦，又很爱钻研。 解：其中 ?p: 小刘怕吃苦，q：小刘很爱钻研 p∧ ,q 3.只有不怕困难，才能战胜困难。 解：p q? →，其中p: 怕困难，q: 战胜困难 或q →，其中p: 怕困难， q: 战胜困难 p? 4.只要别人有困难，老王就帮助别人，除非困难解决了。 解：) → ?，其中p: 别人有困难，q:老王帮助别人，r: 困难解p r→ (q 决了 或：q (，其中p:别人有困难，q: 老王帮助别人，r: 困难解∧ ?) p r→ 决了 5.整数n是整数当且仅当n能被2整除。 解：q p?，其中p: 整数n是偶数，q: 整数n能被2整除 三、求复合命题的真值 P：2能整除5， q：旧金山是美国的首都， r：在中国一年分四季 1. )) p∧ → q ∨ r → ∧ p ( r ) ( ) ((q 2.r ?) → (( → ) ∨ (( ( )) ? r p ∨ p p q ∧ ? q∧ 解：p, q 为假命题，r为真命题 1.)) p∧ → q ∨的真值为0 r → ∧ r ( p ) ( ) ((q 2. r → ∨ → ?) ((的真值为1 ) ( )) (( ∧ p p ∨ r q ? p ? q∧ 四、判断推理是否正确 设x =为实数，推理如下： y2 若y在x=0可导，则y在x=0连续。y 在x=0连续，所以y在x=0可导。解：x =，x为实数，令p: ｙ在ｘ=0可导，q: y在x=0连续。P为y2 假命题，q为真命题，推理符号化为：p →) (，由p，q得真值可 q ∧ p→ q 知，推理的真值为0，所以推理不正确。 五、判断公式的类型 1，r ?))) → ? ( ) ( ) (( ( ? q ∧ q p p ∨ ∧ q∨ p 2. ) p∧ ∧ → ? ∧ q )) p ( ( r (q 3. ) → ? ? p? ) ( r (r q 解：设三个公式为A,B,C则真值表如下： 1.2 映射的有关概念 习题1.2 1. 分别计算??5.1，??1-，??5.1-，??5.1，??1-，??5.1-. 解 ??25.1=，??11-=-，??15.1-=-，??15.1=，??11-=-，??25.1-=-. 2.下列映射中，那些是双射? 说明理由. (1).3)(,Z Z :x x f f =→ (2).1||)(,N Z :+=→x x f f (3).1)(,R R :3+=→x x f f (4).1),(,N N N :2121++=→?x x x x f f (5)).1,()(,N N N :+=?→x x x f f 解 (1)对于任意对∈21,x x Z ，若)()(21x f x f =，则2133x x =，于是21x x =，所以f 是单射. 由于对任意∈x Z ，∈≠2)(x f Z ，因此f 不是满射，进而f 不是双射. (2)由于∈-2,2Z 且3)2()2(=-=f f ，因此f 不是单射. 又由于∈0N ，而任意∈x Z 均有01||)(≠+=x x f ，于是f 不是满射. 显然，f 不是双射. (3)对于任意对∈21,x x R ，若)()(21x f x f =，则113231+=+x x ，于是21x x =，所以f 是单射. 对于任意∈y R ，取3 1)1(-=y x ，这时 y y y x x f =+-=+??????-=+=1)1(1)1(1)(3313， 所以f 是满射. 进而f 是双射. (4)由于∈)1,2(),2,1(N ?N 且)1,2()2,1(≠，而4)1,2()2,1(==f f ，因此f 不是单射. 又由于∈0N ，而任意∈),(21x x N ?N 均有01),(2121≠++=x x x x f ，于是f 不是满射. 显然，f 就不是双射. (5)由于∈21,x x N ，若)()(21x f x f =，则)1,()1,(2211+=+x x x x ，于是21x x =，因此f 是单射. 又由于∈)0,0(N ?N ，而任意∈x N 均有)0,0()1,()(≠+=x x x f ，于是f 不是满射. 因为f 不是满射，所以f 不是双射.离散数学答案屈婉玲版第二版高等教育出版社课后答案
离散数学形考任务1-7试题及答案完整版
离散数学作业答案
离散数学 第七章检测题及答案
离散数学第七章图
离散数学课后习题答案第二章
离散数学第七章二元关系课后练习习题及答案
离散数学(第五版)清华大学出版社第7章习题解答
离散数学答案
离散数学-第七章二元关系课后练习习题及答案讲课教案
离散数学(屈婉玲版)第四章部分答案
《离散数学》刘任任版第七章
离散数学第二版邓辉文编著第一章第二节习题答案
离散数学 尹宝林版 第7章作业答案
离散数学形考任务试题及答案完整
离散数学第七章部分答案
离散数学期末复习试题及答案(七)
离散数学章练习题及答案
离散数学第二版邓辉文编著第一章第二节习题答案
相关主题
文本预览