主要内容
1.
无向图与有向图.
2.
简单图与多重图.
3.
顶点的度数与握手定理.
4.
图的同构.
5.
完全图与正则图.
6.
子图与补图.
7.
通路与回路的定义.
8.
n阶图中通路与回路的性质.
9.
无向图的连通性.
10
无向图中顶点之间的短程线及距离.
11
无向图的连通度.
12
有向图的连通性及其分类.
13
扩大路径法及极大路径.
14
二部图及判别定理.
学习要求
1.
熟练掌握握手定理及其推论的内容及其应用.
2.
掌握图同构的概念.
3.
加深对简单图、完全图、正则图、子图、补图等概念的理解.
4.
深刻理解通路与回路的定义及其分类.
5.
能正确地使用不同的表示法表示通路与回路.
6.
理解同构意义下与定义意义下通路与回路的区别与联系.
7.
深刻理解无向图中两个顶点之间的连通关系、短程线、距离、图的连通性等概念.
8.
深刻理解点割集、边割集、点连通度、边连通度等概念.
9.
理解有向图中, 顶点之间的可达、相互可达关系、短程线、距离等概念.
10
深刻理解有向图的连通性及分类, 以及判别定理.
11
理解并会使用扩大路径法.
12
理解无向图与有向图关联矩阵的概念.
13
会求无向图与有向图的关联矩阵.
14
深刻理解有向图的邻接矩阵与可达矩阵的概念.
15
熟练掌握求有向图的邻接矩阵及各次幂的方法, 并利用它们求D中定义意义下的通路与回路数. 典型习题
1.
无向图G有16条边, 3个4度顶点, 4个3度顶点, 其余顶点的度数均小于3, 问G的阶数n至少为几？
2.
9阶图G中, 每个顶点的度数不是5就是6, 证明G中至少有5个6度顶点或至少有6个5度顶点.
3.
在一次象棋比赛中, n名选手中的任意两名选手之间至多只下一盘, 又每人至少下一盘, 证明：总能找到两名选手, 他们下棋的盘数相同.
4.
下面两组数, 是否是可以简单图化的？若是, 请给出尽量多的非同构的无向简单图以它为度数
列.
5.
的所有非同构的生成子图.
画出K
4
6.
设无向图G中只有两个奇度顶点u与v, 试证明u与v必连通.
7.
设D=
max{δ-(D),δ+(D)}+1的圈.
8.
设n阶无向简单图G有m条边, 已知m≥(n-1)(n-2)+1, 证明G必连通.
9.
设G为n阶无向简单图, 证明以下题目：
离散数学复习要点第一章命题逻辑 一、典型考查点 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．无
离散数学图论与系中有图题目
————————————————————————————————作者：————————————————————————————————日期：
图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8个结点的三次正则图 (2) (1) (3) (2)(1)
离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 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)
第十五章习题解答 1. ()()x xS x xR ?∧?)1( ())()()()()()()(c S b S a S c R b R a R ∨∨∧∧∧解： ())()()2(x Q x P x →? ))((()()()()())()(c Q c P b Q b P a Q a P →∧→∧→解： )()()3(x xP x P x ?∨?? )(()()()())()()(c P b P a P c P b P a P ∧∧∨?∧?∧?解： 2. 指出下列命题的真值： ??-=>=>∨→?}6,3,2{,5:,"5:")(,"3:")(,"23:",)())(((1)D e x x R x x Q P e R x Q P x 论域其中 ).2.(:时不成立为当假解-x 。论域其中，}2{,"4:")(,"3:")() ()(()2(==>→?D x x Q x x P x Q x P x 解：真。 3. 在一阶逻辑中，将下列命题符号化： （1）凡有理数均可表示为分数。 解：P(x)： x 是有理数； Q （x ）:x 可表示为分数。 ))()((x Q x P x →?
())())()((. :,:)(,:)(:. ,)4()) ()((. :)(:)()3()(:)(:)()2(x S x P x W W x x S x x P x Q x P x x x Q x x P x Q x P y x x Q x x P ∧?→→??∧??明天天气好是学生是公园解有一些学生将去公园如果明天天气好是有理数是实数，解：数。 并非所有实数都是有理。 是有理数。 是实数，解：有些实数是有理数。 );()), ()((,,:) ()())()(()1(. ,.4|))) )()(|,(),(()()0,(() ,(:)(,:),(:. |)()(|: ,),,(,0)6())). ,()(()((:),(,:)(:)()5(00000x R x Q x P x x z z Q x xR x Q x P x x f x f G N n G n N x S G x b a x x S y x y x G x f x f N n N b a x x y G y Q y x P x y x y x G x x Q x x P n n 第二个是的作用域是第一个约束变元自由变元解并指出各量词的作用域变元和约束变元指出下列公式中的自由解时有使当都存在对任意给是实数是正实数，解：在大于该实数的实数。 对任意的正实数，都存∧?∧?→∧?-∧??→ ∧??∈><->∈>∧?→?>εεεεε (2)))()(())(()((z Q x xP y Q y x P x →?∨?∧? 解：自由变元z ，约束为元：x ，y 。第一个的作用域为 第二个的作用域为第二个P(x)；第二个的作用域的作用域为 Q(y) （3）)()())()((z s y yR x Q x P x ∧?∧?? 解：自由变元z ，约束为元：x ，y 。 ))()((x Q x P x ??的作用域为 解：自由变元z ，约束为元：x ，y 。 ))()((x Q x P x ??的作用域为 y ?的作用域为R(y)
离散数学 一、逻辑和证明 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也是可数的。
离散数学图论单元测验题 一、单项选择题(本大题共10小题，每小题2分，共20分) 1、在图G ＝
离散数学期末复习要点与重点 离散数学是中央广播电视大学开放教育本科电气信息类计算机科学与技术专业的一门统设必修学位课程，共72学时，开设一学期．该课程的主要内容包括：集合论、图论、数理逻辑等． 下面按章给出复习要点与重点． 第1章 集合及其运算 复习要点 1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法． 具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.． 集合的表示方法：列举法和描述法. 注意：集合的表示中元素不能重复出现，集合中的元素无顺序之分． 掌握集合包含(子集)、真子集、集合相等等概念． 注意：元素与集合，集合与子集，子集与幂集，∈与?(?),空集?与所有集合等的关系. 空集?，是惟一的，它是任何集合的子集． 集合A 的幂集P (A )＝}{A x x ?， A 的所有子集构成的集合．若∣A ∣＝n ，则∣P (A )∣=2n ． 2．熟练掌握集合A 和B 的并A ?B ，交A ?B ，补集~A (~A 补集总相对于一个全集).差集A －B ，对称差⊕，A ⊕B ＝(A －B )?(B －A )，或A ⊕B ＝(A ?B )－（A ?B ）等运算，并会用文氏图表示． 掌握集合运算律(见教材第9～11页)(运算的性质). 3．掌握用集合运算基本规律证明集合恒等式的方法． 集合的运算问题：其一是进行集合运算；其二是运算式的化简；其三是恒等式证明． 证明方法有二：(1)要证明A ＝B ，只需证明A ?B ，又A ?B ； (2)通过运算律进行等式推导． 重点：集合概念，集合的运算，集合恒等式的证明． 第2章 关系与函数 复习要点 1．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算． 有序对就是有顺序二元组，如
图论练习题 一.选择题 1、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图(2) 树(3) 平面图(4)连通图 2、下面给出的集合中，哪一个是前缀码？() (1) {0，10，110，101111}(2) {01，001，000，1} (3) {b，c，aa，ab，aba}(4) {1，11，101，001，0011} 3、一个图的哈密尔顿路是一条通过图中()的路。 4、设G是一棵树，则G 的生成树有( )棵。 (1) 0(2) 1(3) 2(4) 不能确定 5、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。 6、一棵无向树的顶点数n与边数m关系是()。 7、一个图的欧拉回路是一条通过图中( )的回路。 8、有n个结点的树，其结点度数之和是()。 9、下面给出的集合中，哪一个不是前缀码( )。 (1) {a，ab，110，a1b11} (2) {01，001，000，1} (3) {1，2，00，01，0210} (4) {12，11，101，002，0011} 10、n个结点的有向完全图边数是( )，每个结点的度数是( )。 11、一个无向图有生成树的充分必要条件是( )。 12、设G是一棵树，n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 13、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。 14、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。 15、设G是有n个结点m条边的连通平面图，且有k个面，则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 16、设T是一棵树，则T是一个连通且( )图。 17、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 18、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12
离散数学复习 2018.1.3 第1章数学语言与证明方法 知识点1：幂集的定义 幂集的元素个数计算，如果A有n个元素，那么P（A）有2的n次方个元素例1 φ的幂集P（φ）的元素个数为1，因为2的0次方为1.即{φ}。 {φ}的幂集P（{φ}）元素个数为2，其幂集为{φ，{φ}} 知识点2：集合的运算 P8的公式，特别要注意下面的公式： A-B=A ~B ~~A=A ~(A B)= ~A ~B ~(A B) = ~A ~B A⊕B=（A - B） (B - A) 知识点3 文氏图 P7 用文氏图表达集合运算 第2章命题逻辑 1 成真赋值，成假赋值 例1：求(p∨q)→r的成假赋值 若上式子成假，必须(p∨q)为1，r为0 故成假赋值为110 ，100，010 2可满足式，矛盾式，永真式的定义 3 合取范式，析取范式的定义 4 极大项，极小项的定义。 例2 求(p∨q)→r的合取范式的极大项，析取范式的极小项 解成假赋值为110，100，010，故此有三项极大项， (p∨q)→r?M2∧M4∧M6 成真赋值为000，001，011，101，111，故此析取范式有五项极小项 (p∨q)→r?m0∨m1∨m3∨m5∨m7 5 联接词完备集 {∨，?，∧}是完备的，因为→和?都可以用前三个符号来表达 例如p?q?（p→q）∧（q →p）
（p→q）??p∨q {?，∧}也是完备的 因为p∨q??(?(p∨q)) ??(?p∧?q) 但{∨，∧}就不是完备的 6 命题符号化和定理证明 例如小王学过英语或者日语。如果小王学过英语，则他去过英国，如果他去过英国，他也去过日本。所以小王学过日语或者去过日本。 证明： 1）p：小王去过英语；q：小王学过英语 r : 小王去过英国s：小王去过日本 2）前提：p∨q，p→r，r→s 结论：q∨s 3）构造证明过程： 1 p→r 前提引入 2 r→s 前提引入 3 p→s 1，2假言三段伦 4 p∨q 前提引入 5 ??p∨q 4置换 6 ?q→p 5置换 7 ?q→s 6，3假言三段 8 q∨s 7置换 7 归结法证明： 例子：用归结法证明上述命题 1）p：小王去过英语；q：小王学过英语 r : 小王去过英国s：小王去过日本 2）前提：p∨q，p→r，r→s 结论：q∨s 用归结法改写为下述形式： 前提：p∨q，?p∨r，?r∨s，?q，?s 结论0 证明： 1 ?r∨s 前提引入 2 ?s 前提引入 3 ?r 1，2归结 4 ?p∨r 前提引入 5 ?p 3，4归结 6 p∨q 前提引入 7 q 6，7归结 8 ?q 前提引入 9 0 7，8归结
1.5集合的划分与覆盖 习题1.5 1.设},,,{d c b a A =，求出集合A 的所有不同的划分. 解 可以按照划分的块的数目依次求出A 的所有不同的划分共15个. 仅一个划分块:}},,,{{1d c b a =π. 有两个划分块: }},,{},{{2d c b a =π，}},,{},{{3d c a b =π， }},,{},{{4d b a c =π，}},,{},{{5c b a d =π； }},{},,{{6d c b a =π，}},{},,{{7d b c a =π， }},{},,{{8c b d a =π. 有三个划分块: }},{},{},{{9d c b a =π，}},{},{},{{10d b c a =π， }},{},{},{{11c b d a =π，}},{},{},{{12d a c b =π， }},{},{},{{13c a d b =π，}},{},{},{{14b a d c =π. 有四个划分块: }}{},{},{},{{15d c b a =π. 2.对于整数集合Z ，令 }Z |3{1∈=k k A ，}Z |13{2∈+=k k A ，}Z |23{3∈+=k k A , 则},,{321A A A 是Z 的划分. 试验证之. 解 因为(1)≠i A ?，3,2,1=i . (2)=?j i A A ?，3,2,1,,=≠j i j i . (3)=??321A A A Z. 所以，},,{321A A A 是Z 的划分. 3.设}|{I i A i ∈=π是集合A 的一种划分，对于集合B ，所有≠?B A i ?的B A i ?组成的集合是B A ?的划分. 试证明之. 证 对于任意j i ≠，因为=?j i A A ?，于是 =??=???B A A B A B A j i j i )()(?=?B ?.
离散数学复习 第一章命题逻辑基本概念 1．掌握命题及相关概念 2．理解各联结词的逻辑关系 3．会将复合命题符号化 4．会求公式的真值表，并用它求公式的成真赋值、成假赋值及判断公式的类型 第二章命题逻辑等值演算 1．记住基本等值式，会应用它们进行公式的等值演算 2．了解简单析取式、简单合取式、析取范式、合取范式的概念 3．理解极大项、极小项的概念 4．掌握求主析取范式和主合取范式的方法(等值演算和真值表法) 5．会用主范式判断公式的类型及进行简单应用 6．了解联结词完备集的概念 第三章命题逻辑的推理理论 1．理解并记住推理形式结构的两种形式： (1) A1∧A2∧…∧A k→B (2) 前提：A1, A2, … , A k 结论：B 2．掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）3．记住自然推理系统P系统中的推理规则 4．掌握自然推理系统P系统中的推理方法 第四章一阶逻辑基本概念 1．会进行命题的符号化 2．理解公式的解释 3．理解永真式、矛盾式、可满足式的概念及相互之间的关系 4．对于给定的解释会判断公式的真值，或判定真值不确定（即仍不是命题） 第五章一阶逻辑等值演算与推理 1．理解并记住重要等值式，并能熟练地应用它们 2．会使用置换规则、换名规则(约束条变项)、代替规则(自由变项) 3．会求给定公式的前束范式 4．正确地使用UI, UG, EG, EI规则，特别要注意它们之间的关系 5．在F系统，对给定的推理，正确地构造出它的证明 第六章集合代数 1. 掌握集合的表示法 2．能够判别元素是否属于给定的集合 3．能够判别两个集合之间是否存在包含、相等、真包含等关系 第七章二元关系 1. 掌握二元关系、空关系、全域关系、恒等关系、关系的定义域、值域、域、逆关系、 左复合、右复合、限制、像的概念； 2．掌握关系的集合表达式、关系矩阵和关系图三种表示法； 3．掌握关系的基本运算和关系的幂的运算性质，掌握关系的五个性质：自反性、反自反性、对称性、反对称性和传递性等五个性质； 4．掌握关系的闭包的概念，会应用关系的性质求出关系的闭包（自反闭包、对称闭包和传递闭包）；
广东技术师范学院 模拟试题 科 目：离散数学 考试形式：闭卷 考试时间: 120 分钟 系别、班级： 姓名： 学号： 一．填空题（每小题2分，共10分） 1. 谓词公式)()(x xQ x xP ?→?的前束范式是 ?x ?y?P(x)∨Q(y) 。 2. 设全集{}{}{},5,2,3,2,1,5,4,3,2,1===B A E 则A ∩B {2}，=A _{4,5}， =B A {1,3,4,5} 3. 设{}{}b a B c b a A ,,,,==，则=-)()(B A ρρ {{c},{},{},{}} ，=-)()(A B ρρΦ。 4. 在代数系统（N ，+）中，其单位元是0，仅有 _1 有逆元。 5．如果连通平面图G 有n 个顶点，e 条边，则G 有2个面。 二．选择题（每小题2分，共10分） 1. 与命题公式)(R Q P →→等价的公式是（ ） （A ）R Q P →∨)( （B ）R Q P →∧)( （C ）)(R Q P ∧→ （D ）)(R Q P ∨→ 2. 设集合{}c b a A ,,=上的二元关系{}><><=b b a a R ,,,不具备关系( )性质 （A ） (A)传递性 (B)反对称性 (C)对称性 (D)自反性 3. 在图>= 离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝ 图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( )． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ? ? ? ? ? c a b e d ? f 图四 第一部分数理逻辑 第一章命题逻辑 重点： ●熟练掌握联结词的定义； ●掌握数理逻辑中命题的翻译及命题公式的定义； ●熟记基本的等价公式和蕴涵公式； ●利用真值表技术和公式法求公式的主析取范式和主合取范式； ●熟练掌握应用基本推理方法完成命题逻辑推理： 1.直接证法 2.反证法 3.CP规则 难点： ●如何正确地掌握对语言的翻译； ●如何利用推理方法正确的完成命题推理。 第二章谓词逻辑 重点： ●谓词、量词、个体域的概念； ●谓词逻辑中带量词命题的符号化； ●熟记基本的谓词等价公式； ●求公式的前束范式； ●掌握谓词逻辑的推理规则以及能够熟练地完成一阶逻辑推理；难点： ●谓词逻辑中带量词命题的符号化； ●如何利用推理方法正确地完成一阶逻辑推理。 第二部分集合论 第三章集合与关系 重点： ●掌握集合的五种基本运算和集合相等的证明方法； ●幂集的概念以及和子集的关系； ●序偶和笛卡尔积的概念； ●关系定义及其和笛卡尔积之间的联系； ●关系的复合； ●关系的五种性质及其判断和证明； ●关系的闭包； ●等价关系定义、证明及其与等价类、集合的划分间的关系； ●偏序关系的定义和证明，哈斯图； ●偏序关系中的特殊元素； 难点： ●如何正确证明集合之间包含和相等关系； ●如何正确地理解和判断关系的性质； ●非常重要的关系性质的证明方法——按定义证明法； ●如何正确地掌握等价关系及相应的等价类与集合划分之间的关系； ●如何正确地理解和判断偏序关系中的八种特殊元素。 第四章函数 重点： ●能够判定某个二元关系是否是函数； ●几种特殊的函数：满射，单射，双射； 难点： ●如何正确地判断三种特殊函数。 第三部分代数结构 重点： ●理解代数结构的构成和研究方法； ●代数结构中运算的性质以及特殊元素； ●广群?半群?独异点?群； ●群的定义与性质； ●环与域的判断和证明； ●格的两种定义； ●特殊格：分配格、有界格、有补格、有补分配格； ●有补分配格与布尔代数之间的联系； 难点： ●循环群的判断和证明； ●如何正确理解由偏序关系定义的格与由代数系统定义格之间的关系 和区别； ●如何正确理解布尔代数的概念。 第四部分图论 重点： ●掌握图论的基本定理：握手定理及其推论的内容，并且能灵活地应用 （如已知边数和一些结点的度数，求另一些结点的度数等），在图论 中的很多证明都要用到握手定理及推论。 ●熟悉图的矩阵表示，在理解通路和回路相关概念的基础上，掌握可达 图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8 个结点的三次正则图 (2) (1) (3) (2) (1) 离散数学(第2版)_在线作业 _4 交卷时间：2017-01-12 14:00:56 一、单选题 1. (5分) ? A. q ∧┐q ? B. p →┐q ? C. p → (p ∨q) ? D. (p ∨┐p)→q 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 2. (5分) ? A. ? B. ? C. ? D. 下列命题公式为重言式的是( )。 设，下列式子正确的是( )。 纠错 得分： 5 知识点： 离散数学(第2版 ) 收起解析 答案 C 解析 3. (5分) ? A. ? B. ? C. ? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 D 解析 4. (5分) ? A. ? B. ? C. 下列是两个命题变元的极小项的是( )。 设G 是有个顶点， 条边和个面的连通平面图，则 等于( )。 ? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 5. (5分) ? A. 满射函数 ? B. 非单射非满射函数 ? C. 双射函数 ? D. 单射函数 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 6. (5分) 设R 是实数集合，函数，则是( )。 ? A. 11，3，4 ? B. 10，4，3 ? C. 11，3，5 ? D. 12，3，6 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 A 解析 7. (5分) ? A. x*y=gcd(x,y)，即x,y 的最大公约数 ? B. x*y=lcm(x,y)，即x,y 的最小公倍数 ? C. x*y=max{x,y} ? D. x*y=min{x,y} 纠错 得分： 5 知识点： 离散数学(第2版) 下列平面图的三个面的次数分别是( )。 设集合A={1,2,3,…,10}，下面定义的哪种运算关于集合A 是不封闭的？( )。 《离散数学》习题与解答 第一篇数理逻辑 第一章命题逻辑 1-1（1）指出下列语句哪些是命题，哪些不是命题，如果是命题指出他的真值 a)离散数学是计算机科学系的一门必修棵 b)∏> 2 吗？ c)明天我去看电影 d)请勿随地吐痰 e)不存在最大质数 f)如果我掌握了英语，法语，那么学习其他欧洲的语言就容易多了 g)9+5<12 h)x<3 i)月球上有水 j)我正在说假话 [解] a)不是命题 b)是命题,真值视具体情况而定 c)不是命题 d)是命题,真值为t e)是命题,真值为t f)是命题,真值为f g)不是命题 h)是命题, 真值视具体情况而定 i)不是命题 1-2(1)用P表示命题“天下雪”,(又表示命题“我将去镇上”,R表示命题“我有时间”.以符号形式写出下列命题: (a)如果天不下雪和我有时间,那么我将去镇上. (b)我将去镇上，仅当我有时间. (c)天不下雪 (d)天下雪,那么我不去镇上 [解] a)(┐P∧R)→Q b)Q→R c)┐P d)P→┐Q 1-2(2)将下面这段述中所出现的原子命题符号化,并指出他们的真值,然后将这段述中的每一命题符号化 2 是有理数是不对的.2是偶素数.2或4是素数.如果2是素数则3也是素数.2是素数当且仅当3也是素数. [解]:述中出现5个原子命题，将他们符号化为: P: 2 是有理数其真值为F Q:2是素数其真值为T R:2是偶数其真值为T S:3是素数其真值为T U:4是素数其真值为F 述中各命题符号化为: ┐P;Q∧R;Q∨U;Q→S;Q＜＝＞S 1-2(3)将下列命题符号化 a)如果3+3=6,则雪是白色的. b)如果3+3≠6,则雪是白色的 c)如果3+3=6,则雪不是白色的. d)如果3+3≠6,则雪不是白色的 e)王强身体很好，成绩也很好. f)四边形ABCD是平行四边形,仅当其对边平行 [解]:设P:3+3=6 Q:雪是白色的 R:王强成绩很好S:王强身体很好 U: 四边形ABCD是平行四边形V: 四边形ABCD的对边是平行的于是: a)可表示为:P→Q b)可表示为: ┐P→Q c)可表示为: P→┐Q d)可表示为：┐P→┐Q e)可表示为：S∧R f)可表示为:U＜＝＞V 1-3(1)判别下列公式中哪些是合式公式,那些不是合式公式 a) (Q→R∧S) b) (P＜＝＞(R→S)) c) ((┐P→Q)→(Q→P))) d) (RS→T) e)((P→(Q→R))→((P→Q)→(P→R))) [解]: a)不是合式公式(若规定运算符优先级后也可以作为合式公式) b)是合式公式 c)不是合式公式(括号不配对) d)不是合式公式 e)是合式公式 1-3(2)对下列各式用指定的公式进行代换: a) (((A→B)→B)→A),用（A→C）代换A，用（（B∧C）→A代换B。 b)((A→B)∨(B→A),用B代换A,A代换B. [解]:a)((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C)) b)((B→A)∨(A→B)) 1-3(3)用符号形式写出下列命题 a)假如上午不下雨,我去看电影;否则就在家里读书或看报. b)我今天进城,除非下雨. c)仅当你走,我将留下. [解]a)设P:上午天下雨. Q:我去看电影离散数学图论部分经典试题及答案
离散数学重点难点复习提纲
离散数学图论与关系中有图题目
离散数学(第2版)_在线作业_4
离散数学复习资料全
相关主题
文本预览